Matematicheskaya_logika

4. Аксиомами (логическими) теории К для любых формул А, В, С являются формулы:

(А1): А→(В→А)

(А2): (А→(В→С))→((А→В)→(А→С)) (А3): (¬В→¬А)→((¬В→А)→В)

(А4): Если t является свободным термом для xi в формуле А(xi), то

xiА(xi)→А(t)

( xi А(xi)→ А(xi))

(А5): Если формула А не имеет свободных вхождений переменной xi, то

xi (А→В)→(А→ xiВ).

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

1.МР: А, А→В В.

2.ПО (правило обобщения): А xiА(xi).

Если в А4 избавиться от ограничения, то возможна такая аксиома:

х1 ¬х2 А12(х1, х2)→¬х2 А12(х1, х2),где терм х не является свободным для хi в формуле А(х1)=¬х2А12(х1, х2).

Эта формула не является логически общезначимой, т.к. в любой интерпретации, в которой D состоит хотя бы из двух элементов и А12интерпретируется как отношение тождества, посылка - истина, а заключение - ложно.

Если убрать ограничение в А5, то возможна , например, формула

х1 (А11(х1)→А11(х1))→(А11(х1)→х1 А11(х1)).

Если ее проинтерпретировать при помощи D, имеющего 2 элемента и А11 при помощи свойства, которым обладают не все элементы из D, тогда посылка будет истинной, а заключение будет ложным. Формула не является логически общезначимой.

Заметим, что в силу свойств 3 и 6, правило вывода сохраняет свойство быть истинной формулой.

Кроме логических аксиом в теориях I порядка рассматриваются собственные аксиомы.

Теория I порядка без собственных аксиом называется исчислением предикатов. Примеры теорий I порядка.

1.Теория Р имеет 1 предикатный символ А12. Собственными аксиомами теории являются:

Частично упорядоченная структура

1) х1 ¬А12(х1, х1)

2) х1 х2 х3 (А12(х1, х2)→(А12(х2, х3)→А12(х1, х3))) - транзитивность.

2. Теория групп.

Теория Р имеет 1 предикатный символ А12, 1 функциональный символ f12 и одну предметную константу а. Собственными аксиомами теории являются:

1)х1 х2 х3 А12( f12(х1, f12(х2, х3)), f12(f12(х1, х2), х3)) ассоциативность

2)х1 А12(f12(х1, а), х1) правый нейтральный элемент

3)х1 х2 А12(f12(х1, х2), а) правый симметрический элемент

4)х1 А12(х1, х1) рефлексивность равенства

5) х1 х2 (А12(х1, х2)→А12(х2, х1)) симметричность 6) х1 х2 х3 (А12(х1, х2)→(А12(х2, х3)→А12(х1, х3))) транзитивность

7) х1 х2 х3 (А12(х1, х2) →(А12(f12(х1, х3), f12(х2, х3))&А12(f12(х3, х1), f12(х3, х2)))

4), 5), 6), 7) - характеризует А12 как равенство 7) характеризует свойство подстановочности равенства.

Любая модель данной теории называется группой.

5.Теорема 1 (о частном случае тавтологии) Всякий частный случай тавтологии является теоремой теории I порядка, причем существует вывод с

использованием только 1-3 аксиом и МР.

Доказательство: Пусть А является частным случаем некоторой тавтологии Т, тогда по теореме о полноте, Т является теоремой, то есть существует вывод формулы Т в теории L из пустого множества при помощи А1-А3 и МР. Преобразуем данный вывод так:

1.Каждую букву этого вывода, которая встречается в Т, заменим на ту же формулу, на которую мы ее заменили при получении формулы А.

2.Если в выводе встречается буква, которой нет в Т, то ее заменим на произвольную одну и ту же формулу теории К. Этот вывод является выводом из пустого множества формулы А в теории К.

Пример: Если Т - ¬А→(А→В) и

А заменяем на хi ¬В(хi), В - на хi хj А(хi, хj), то

К В(хi)→ ( хi ¬В(хi)→ хi А(хi, хj)).

Теорема 2. Исчисление предикатов непротиворечиво.

Доказательство: Рассмотрим преобразование h(А) формулы А в исчислении предикатов, которое убирает все кванторы, термы и скобки из данной формулы А.

Например, А=А13(х1, f11(х2), f12(х1, х2))→ х1 А11(х1)&А12(х1, х2)

h(А)=А13→А11&А12.

Тогда, h(¬А)= ¬h(А); h(А→В)=h(А)→h(В)

h применённое к аксиомам А1-А3 приводит к тавтологии , что очевидно. h( хi А(хi) →А(t))=В→В – тавтология. h( х2(А→В)→(А→ хВ)=(С→D)→(С→D) – тавтология.

Кроме того, если А при помощи h даст тавтологию, то и h( xiА) – тавтология.и Если h(А) - тавтологии и h(А→В), то h(В) - тавтологии.

Таким образом, если исчисления предикатов не является непротиворечивым,

т.е. для некоторой формулы В имеем В и ¬В, то тогда в следствие того, что h от аксиомы оставляет тавтологию., правило обобщения и МР при помощи h сохраняет тавтологию, то тогда h(В) - тавтология, h(¬В) – тавтология то есть ¬(h(В)) - является тавтологией, что невозможно. Таким образом, исчисление предикатов непротиворечиво.

6. Теорема дедукции.

Теорема дедукции в общем видеГ, А В Г А→В в исчислении предикатов не верна. Например, применяя к выводимости

А11 К х1А11(х1), получим А11(х1)→ х1А11(х1).Однако, если данную формулу проинтерпретировать при помощи некоторого множества D содержащего не менее

одного элемента, а А11 – одноместным отношением, которым обладает только один элемент из D, то формула не является истинной в данной интерпретации, следовательно не является логически общезначимой.

Поэтому имеем следующую формулировку.

Теорема 3 Если из множества формул Г и из формулы А выводима в исчислении предикатов формула В и существует вывод, в котором ни при каком применении правила обобщения не связывается квантором никакая свободная переменная из

формулы А, тогда из Г А→В.

Доказательство: Пусть В1, В2,..., Вк- - В является указанным в условии теоремы выводом Г, А В, тогда для i Bi является либо

1.аксиомой, либо

2.гипотезой, то есть либо 2.1 Bi Г, либо 2.2. Bi=А, либо

3.Bi является непосредственным следствием предыдущих, либо

3.1.формул Bj и Bk-Bj→Bi, j, k < i.. по правилу МР либо

3.2.формулы Bj, j<i, по правилу ПО (Bi= xkBj ). При этом xk не является

свободной переменной формулы А. Докажем утверждение теоремы индукцией по i. I. i=1

1)В1 - аксиома Г В1→(А→В1) (МР)Г А→В1.

2)гипотеза 2.1. В1 Г Г В1 Г А→В1.

2.2.В1=А Г А→В1 (в следствие теоремы 1).

II.Предположим, что утверждение справедливо для всех j<i. Докажем для Bi.

Если Bi 1. Аксиома или

2. 2.1. Bi Г аналогично I с заменой 1 на i Г А→ Bi.

2.2. Bi=А

Если же Bi является непосредственным следствием по 3.1.

3.1.Г А→Вj&Г А→(Вj→Bi), то т.к. к, j<i

по А2: Г (А→(Вj→Bi))→((А→Вj)→(А →Bi)) (МР 2)Г А→ Bi

3.2.j<i Г А→Вj (ПО)Г хк(А→Вj)

по А5: Г хк(А→Вj)→(А→хк(Вj)) (МР) Г А→хкВj

Следствие из теоремы дедукции. Если формула А замкнутая и Г, А В, то

Г А→В.

Пример. Докажите, что К х1 х2 А→х2 х1 А.

1.х1 х2 А (гипотеза).

2.х1 х2 А→х2 А.(А4)

3.х2 А (1, 2, МР)

4.х2 А→А (А4)

5.А (3, 4, МР)

6.х1 А (5, ПО)

7.х2 х1 А (6, ПО)

По 1 – 7 имеем х1 х2 А х2 х1 А поэтому по теореме дедукции х1 х2 А→х2 х1 А

7. Теорема 4. Всякая теорема исчисления предикатов является логически общезначимой.

Доказательство: т.к. в силу свойства 7 истинности формул частный случай тавтологии является логически общезначимой формулой, то аксиомы из А1, А2, А3 являются логически общезначимыми. Вследствие свойства 10 аксиомы из А4 логически общезначимы; по свойству 11 А5 логически общезначима; по свойству 3 правило МР сохраняет свойство формул быть логически общезначимыми; ПО сохраняет истинность в силу свойства 6. Следовательно, теорема является логически общезначимой.

Формула A(xj) называется подобной A(xi), если получена из нее при помощи подстановки вместо всех свободных вхождений переменной xi переменной xj, A(xi) не имеет свободных вхождений переменной xj и xj является свободным термом для xi в A(xi).

Тогда терм xi является свободным для xj в A(xj) и A(xj)не имеет свободных вхождений переменой xi, т.е. формула A(xi) подобна A(xj). Поэтому подобие является симметричным.

Две формулы A(xi) и A(xj) подобны, если свободное вхождение переменной xj в A(xj) имеются в тех же местах, что и свободное вхождение xi в A(xi).

Лемма 1. Если формулы А(xi) и А(xj) подобны, то K xiA(xi)↔xjA(xj).

Доказательство: докажем, что xiA(xi) → xjA(xj).

1.xiA(xi)→A(xj) (А4)

2.xj ( xiA(xi)→A(xj)) (1, ПО)

3.xj ( xiA(xi)→A(xj))→ ( xiA(xi)→ xjA(xj)) (А5)

4.xiA(xi)→ xjA(xj) (2, 3, МР)

По 1 - 4 имеем xiA(xi)→ xjA(xj)

Аналогично xjA(xj)→ xiA(xi). Тогда по теореме 1 (о частном случае тавтологии) по тавтологии А→(В→(А&В)) и правилу МР, применённому дважды

,получаем К xiA(xi) ↔ xjA(xj).

Лемма 2.Если для некоторой замкнутой формулы А теории I порядка К не выводится из пустого множества ¬А, то теории К =К А , где А добавляется в качестве аксиомы, непротиворечивы.

Доказательство. От противного. Пусть для некоторой формулы В имеем К|В и

К|¬В (в следствие тавтологии ¬А→(А→В), теоремы 1 о тавтологии)

К|¬В→(В→¬А)/где ¬А - любая формула/ (МРдважды) К|¬А А К¬А

(теорема дедукции) КА→¬А (по теореме 1 К(А→¬А)→¬А) (МР) К¬А, что противоречит условию, следовательно К непротиворечива.

Замечание. Если для некоторой замкнутой формулы А из теории К формула А не является теоремой, то теория К { А} - непротиворечива.

Доказательство: аналогично лемме 2.

Лемма Гёделя (о нумерации). Множество всех выражений исчисления предикатов счётно, следовательно, счётно и множество всех термов и формул.

Доказательство: каждому символу исчисления поставим в соответствие некоторое нечетное число g(u) следующим образом.

g(()=3, g())=5, g( , )=7, g(¬)=9, g(→)=11.

g(xk)=5+8k, g(ak)=7+8k, g(fkn)=9+8(2k3k), g(Akn)=11+8(2k3k), g( xk)=g(xk).

Тогда каждому выражению u0, u1,...,us сопоставляется четное число

2g(u) 3g(u) 5g(u) ... ps+1g(u), где ps - s-ое простое число.

Тогда разным выражениям соответствуют разные числа, следовательно все выражения можно занумеровать. И все аксиомы и теоремы тоже, однако, по числу не всегда можно установить, является ли данная формула теоремой, т.к. не во всякой теории для всех формул можно определить теорема она или нет, то есть не всякая теория является разрешимой.

6. Установите истинность высказываний:

1) y z x / x + y =z,D =N; 2) x y z / x + y =z,D =N;

3) x y z / x + yz =0,D =N0; 4) z y x / НОД(x, y) =z,D =Z;

5) x y z / x + y + z =x y z,D =N; 6) x y z /(x + y) z =0,D =Z;

7) x y z / x + y =xz,D =N0; 8) x y z / x + z =x y,D =N;

9) x y /(x > y) →(x > y2 ),D =N; 10) y x /(x < y) →(x2 > y),D =Z; 11) x y /(x > y) & (x2 < y),D =Q.

7. Напишите формулы, которым в интерпретации с

D =N 0

символ

A12"=", f12 ="+", f22 ="×"

соответствует отношение:

1)быть нулем;

2)быть 1;

3)быть 2;

4)быть четным;

5)быть нечетным;

6)быть простым;

8)“< ”;

9)быть простыми числами – близнецами;

10)быть НОК;

11)отношение “делит”:

12)быть НОД.

8.Докажите, что следующие формулы не являются логически общезначимыми:

1) x1A11(x1) A21(x1) → x1A11(x1) x1A21(x1);

2)( x1A11(x1) → x1A21(x1)) → x1(A11(x1)) →A21(x1)).

9. Докажите логическую общезначимость формул:

1)A(t) →xi A(xi ),

Если t – свойство терм для

xi

в

A(xi );

2) xi A→xi A;

3) xi x j A↔x j xi A;

4) xi A↔¬xi¬A;

5) xi (A→B) →( xi A→xi B); 6) xi A& xi B ↔xi A& B; 7) xi A xi B →xi A B; 8) xi x j A↔x j xi A;

9) xi x j A→x j xi A.

10. Докажите, построив вывод:

1)x(A→B) →( xA→ xB);

2)x(A→B) →( xA→xB);

3)x(A& B) ↔xA& xB;

4)x1 x2... xn A→ A;

11.Докажите, что если формы:

A(xi ), A(x j )

подобны, то:

1)xi A(xi ) ↔x j A(x j );

2)A↔xA,

если х не является свободной переменной А.

3)xA→ A;

4)x(B → A) ↔( xB → A),

где х – связная в А.

5)A(t) →xA(x),

Если t – свободная для х в А.

6)x(A↔B) →( xA↔ xB);

7)x(A(x) →B(x)) →( xA(x) → xB(x)); 8) x(A→B) ↔(A→ xB).