Математическая логика — логические аксиомы

Логические аксиомы

1) A -> (B -> A)

2) (A -> (B -> C)) =>( (A -> B) -> (A -> C))

3) (˥B -> ˥A) => ((˥B -> A) -> B)

4) xi A(xi) -> A(t), где A(xi), где A(xi)- формула теории Т, t – предметная переменная или предметная константа, t может совпадать с x.

5) xi (A -> B) -> (A -> xi B), если xi не входит свободно в формулу А.

Правила вывода:

1) правило заключения или Модус Понес

| = A, |= A -> B (посылки)

———————

|= B (заключение)

2) правило связывания квантором всеобщности или правило обобщения.

|= A

————————

|= xi A

Доказательством или выводом называют конечную последовательность S1, S2, …, Sn высказываний рассматриваемой теории, каждая из которых является либо аксиомой, либо выводится из одного или более предыдущих высказываний по логическим правилам теории.

Теоремой или докзанным высказыванием называется высказывание, являющееся последним высказыванием некоторого доказательства.

Формула А называется следствием множества формул ɣ т. и т. т., когда существует такая последовательность формул A1, A2, …, An, что An совпадает с А и все Ai есть либо аксиомы теории Т, либо формула из множества ɣ(ГА), либо непосредств. следствие из некоторой предыдущей формулы. Эта последовательность называется выводом формулы А из множества гипотез ɣ(ГА) и Г |= A

Свойства понятия выводимости:

Пусть Г – призвольное множество формул и A, B, C – формулы. Рассмотрим множество свойств:

1) Г, A |= A

2) Г, А, В |= С, то Г, В, А |= C

3) Если из Г выводится В, А – призводная формула, то из Г, А тоже выводится В

Г |= B, A

Г, А |= B

4) Если из Г вывоится А, из Г выводится В, из формул А, В выводится С, то из Г выводится С

Г |= А; Г |= B; А, В |= C, то Г |= C

5) Г, А |= B, Г |= A, то Г |= B

6) Г |= A->B ʌ Г |= A, то Г |= B

В качестве акс. теорий рассматривают исчисление высказываний и исчисление предикатов, где четко задается алфавит, формулы, аксиомы, правила вывода.

Теория Т называется противоречивой, если она содержит такое высказывае S, что S и ˥S одновременно являются теоремами. В противном случае теория Т называется непротиворечивой.

Моделью теории называется интерпретация языка этой теории.

Аксиомаическая теория называется полной в узком смысле, если добавление в ней утверждения с сокращением в ней всех правил вывода приводит к противоречивости теории.

Теория Т называется абсолютно полной или полной в широком смысле, если для любого высказывания S этой теории или S, или ˥S есть теорема.

Т. 1. Исчисление высказываний полно в узком и широком смысле.

Т. 2. Выское исчисление предикатов 1-ого порядка Т непротиворечивого.

Теория алгоритмов. Интуитивное понятие алгоритма.

Все алгоритмы представляют собой правила, предписывающие последовательность действий, ведущих к достижению результата.

Классификация алгоритмов: 1) технологические; 2) управляющие; 3) информационно-вычислительные.

Алгоритм (в интуитивном смысле) – правило, сформулированное на некотором языке и определяющее процесс переработки допустимых данных в искомые результаты.

Машина Тьюринга (МТ) – это четверка вида T = (A, Q, P, q0), где А – конечный алфавит ленточных символов, Q – конечное непустое множество состояний головки МТ, Р – конечное множество команд, q0 – начальное состояние головки МТ.

Под конфигурацией МТ принято понимать слово VqisjF, где V и F – слова в алфавите МТ, sj – символ, обозреваемый головкой МТ, qi – текущее состояние головки МТ.

Функция F(x1, x2, …, xn) называется вычислимой по Тьюрингу, если существует МТ, вычисляющая эту функцию.

Тезис Тьюринга.

Изучая МТ, обнаружили, что это мощное вычислительное устройство.

Неразрешимые проблемы.

1) проблемы, которые алгоритмически неразрешимы;

2) проблемы, которые алгоритмически разрешимы, но не разрешимы в реальном времени.

Теорема 1.

Проблема самоприменимости нерарешима, т. е. не существует алгоритма, отличного по номеру самопримен-е машины от несамоприменимых (смотри стр. 149 у С. Яблокова).

Теорема 2.

Проблема останова неразрешима, т. е. не существует алгоритма, определяющего для МТ Т и входной ленты L, остан-ся ли Т, получив на вход ленту L.

Полиномиальным алгоритмом или алгоритмом полиномиальной врем-й сложности называют алгоритм, у которого временная сложность равна O(P(n)), P(n) – некоторая полиномиальная функция от входной длины n.

Алгоритмы, для временной сложности которых не существует оценки, называют экспотенциальными.

ФОРМАЛЬНЫЕ ЯЗЫКИ И ГРАММАТИКИ

Алфавит V – конечное множество символов, которые являются неделимыми объектами и используются при составлении цепочки.

Цепочка длины K над алфавитом V – произвольная последовательность k символов из алфавита V, не обязательно различных.

Ԑ — пустая цепочка, не содержит ни одного символа.

Формально понятие цепочки над алфавитом V определяется следующим образом:

1) Ԑ — цепочка над алфавитом V;

2) если x – цепочка над алфавитом V и символ Vi принадлежит V, то xVi – тоже цепочка над V;

3) других цепочек нет.

Vk — множество всех цепочек длины k над алфавитом V.

Vk = { w | |w| = k}

V0 = E = {Ԑ}

V* = . Его элементами являются все цепочки над алфавитом V, в том числе и Ԑ.

V+ = V*{Ԑ}

Конкатенация цепочек w и n — это последовательность символов, получившаяся приписыванием справа символов цепочки w символов цепочки n. Обозначается умножением “*”.

Если цепочка w = n*R, то цепочка n — префикс цепочки w. Если цепочка R не пуста, то R — собственный префикс. Аналогично, R — суффикс w. Если n не пуста, то R — собственный суффикс.

Свойства конкатенации:

1) V* замкнуто относительно конкатенации, т. е. любое n, R ϵ V*;

2) конкатенация ассоциативна w, n, R (w*n)*R = w*(n*R), n*R ϵ V*;

3) пустая цепочка – единица конкатенации w Ԑw = wԐ = w;

4) если V содержит более одного символа, то операция конкатенации некоммутативна:

существуют такие w, n ϵ V* => w*n!= n*w;

5) w, n ϵ V* |w*n| = |w| + |n|.

wk – конкатенация k цепочек w, т. е.

wk = w * w * … w

k раз

Будем считать, что w0 = Ԑ.

Обращением цепочки w = v1v2 … Vn назовем цепочку wR = vn vn-1 … v1. ԐR = Ԑ.

Теорема

Если V!= , то множество всех цепочек над алфавитом V счетно.

Формальный язык над алфавитом V – произв-е множество цепочек над алфавитом V. Т. о., любой язык L над алфавитом V является подмножеством V* => язык L – не более чем счетное множество.

Класс всех языков над V – множество всех подмножеств V*. Поскольку V* счетно, если V!= , то класс всех языков над V имеет мощность континуума.

Конкатенация языков A и B – множество всех цепочек, получающихся в результате приписания к цепочке языка А цепочки языка B.

A*B = {w*n| w ϵ A, n ϵ B}

E = {Ԑ} — единица конкатенации языка.

AE = { a Ԑ = a, abԐ = ab} = A

A = {w n | w ϵ A, n ϵ } = , т. к. в языке нет цепочек. и E — два различных языка!

Основные свойства конкатенации языков:

1) операция конкатенации языков ассоциативна: