Теорема 2. Перечень важнейших тавтологий

План курса лекций

1.Введение. ВС. Истинностные значения ВС. Тавтологии.

2.Равносильность ВС. Равносильные преобразования ВС.

3.Отношение следования. Необходимое и достаточное условия. Правильные рассуждения.

4.КНФ, ДНФ, СКНФ, СДНФ. Принцип двойственности.

5.Булевы функции. Многочлены Жегалкина.

6.Классы булевых функций. Теорема Поста.

7.Высказывательные формы. Кванторы. Геометрическое истолкование кванторов.

8.Языки первого порядка. Синтаксис и семантика ЯПП. Истинностные значения формул.

9.Логически истинные формулы.

10.Дедуктивная сила и равносильность формул.

11.Свойства кванторов. Алфавитные варианты.

12.Распределительные законы для кванторов. ПНФ.

13.Типовые кванторы.

14.Исчисление высказываний. Выводимость из гипотез.

15.Теорема дедукции. Принцип приведения к абсурду. Максимальные множества. Теорема полноты ИВ.

16.Теории первого порядка. Некоторые методы доказательства.

17.Модели теорий первого порядка.

Глава I. Логика высказываний

§ 1. Высказывательные схемы

Высказывания и логические операции над ними. Отрицание, конъюнкция, дизъюнкция, импликация, эквиваленция. Истинностные значения высказываний.

Высказывательные переменные. Высказывательные схемы (индуктивное определение).

Правила опускания скобок.

Подстановка А и одновременная подстановка A .

Теорема 1*. Грамматические свойства подстановок

1°. Если А и В – ВС, X_j – ВП, то А также ВС.

2°^*. Если А и В₁, В₂, …, В_n – ВС, – ВП, то A также ВС.

3°^*. Если А, В, С – ВС и А₁ получено из А заменой некоторых вхождений В на С, то А₁ также ВС.

Таблицы истинности.

Тавтологии, противоречивые, выполнимые, опровержимые ВС. ⊨.

§ 2. Свойства тавтологий

Теорема 1. Свойства тавтологий

1°. ⊨ А и ⊨ В Û ⊨АÙВ.

2°. ⊨ А или ⊨В Þ ⊨АÚВ.

3°. ⊨А и ⊨А®В Þ ⊨В.

4°. ⊨А Þ ⊨ØА®В для любой ВС В.

5°. ⊨А Þ⊨В®А для любой ВС В.

6°. ⊨А Þ ⊨А для любой ВС В и любой ВП X_j.

7°. ⊨А Þ ⊨A для любых ВС В₁, В₂, …, В_n и любых ВП .

Теорема 2. Перечень важнейших тавтологий

1. X®X
2. X«X
3. ØØX«X
4. ØXÚX
5. Ø(XÙØX)
6. XÙY®X, XÙY®Y
7. XÙX«X
8. XÙY«YÙX
9. XÙ(YÙZ)«(XÙY)ÙZ

10. X®XÚY, Y®XÚY

11. XÚX«X

12. XÚY«YÚX

13. XÚ(YÚZ)«(XÚY)ÚZ

14. XÙ(YÚZ)«(XÙY)Ú(XÙZ)

15. XÚ(YÙZ)«(XÚY)Ù(XÚZ)

16. (X®YÙZ)«(X®Y)Ù(X®Z)

17. (XÚY®Z)«(X®Z)Ù(Y®Z)

18. (X®Y)Ù(ØX®Y)«Y

19. Ø(XÙY)«ØXÚØY

20. Ø(XÚY)«ØXÙØY

21. (X®Y)«ØXÚY

22. Ø(X®Y)«XÙØY

23. (X®Y)«Ø(XÙØY)

24. (X«Y)«(X®Y)Ù(Y®X)

25. (X«Y)«(Y«X)

26. (X«Y)Ù(Y«Z)®(X«Z)

27. (X®Y)«(ØY®ØX)

28. (X®Y)®(XÙZ®YÙZ)

29. (X®Y)®(XÚZ®YÚZ)

30. (X®Y)®((Y®Z)®(X®Z))

31. (X®Y)®((Z®X)®(Z®Y))

32. X®(Y®Z)«Y®(X®Z)

33. X®(Y®Z)«(XÙY®Z)

34. (X®Y)«(X®XÙY)

35. (X®Y)«(XÚY®Y)

36. X®(Y®XÙY)

37. X®(Y®X)

38. ØX®(X®Y)

39. (X®(Y®Z))®((X®Y)®(X®Z))

40. (ØX®Y)®((ØX®ØY)®X)

41. (ØX®YÙØY)®X

42. X®(XÙY«(ØXÚY))

43. X®((X®Y)«(X«Y))

44. X®((X«Y)«Y)

45. Y®((X®ØY)«(X«ØY))

46. Y®((X®ØY)«ØX))

47. XÙ(X®Y)«XÙY

48. (X®YÚZ)®(X®Y)ÚXÙZ

Примечание. Тавтологии 1 и 2 называются законами тождества, 3 – закон двойного отрицания, 4 – закон исключенного третьего, 5 – закон противоречия, 7 и 11 – идемпотентность конъюнкции и дизъюнкции, 8 и 12 – коммутативность, 9 и 13 – ассоциативность, 14 и 15 – законы дистрибутивности, 16 – закон соединения и разъединения заключений, 17 – закон соединения и разъединения посылок, а также (ещё чаще) – закон перебора случаев, 19 и 20 – законы де-Моргана, 21 и 23 – определения импликации, 22 – отрицание импликации, 24 – определение эквиваленции, 25 – симметричность эквиваленции, 26 – транзитивность эквиваленции, 27–31 – законы импортации, кроме того, 27 – закон контрапозиции, 32 – закон перестановки посылок, 33 – закон соединения и разъединения посылок, 34 – закон присоединения заключения, 35 – закон присоединения условия, 37 – ‘истина следует из чего угодно’, 38 – ‘изо лжи следует что угодно’, 39 – самодистрибутивность импликации, 40–41 – законы противоречия, 42–46 – законы поглощения.

§ 3. Равносильность высказывательных схем

Равносильность ВС. º.

Теорема 1. Свойства равносильности

1°. Отношение равносильности является отношением эквивалентности.

2°. (Критерий равносильности) ВС А и В равносильны тогда и только тогда, когда (А«В) является тавтологией.

3°. (Правило подстановки) Если А, В и С – ВС и А₁ получено из А заменой некоторых вхождений В на вхождения С, и если В º С, то А º А₁.

Теорема 2. Важнейшие равносильности ВС

1°. ØØА º А.

2°. АÙА º А. 2¢. АÚА º А.

3°. АÙВ º ВÙА. 3¢. АÚВ º ВÚА.

4°. АÙ(ВÙС) º (АÙВ)ÙС. 4¢. АÚ(ВÚС) º (АÚВ)ÚС.

5°. АÙ(ВÚС) º (АÙВ)Ú(АÙС). 5¢. АÚ(ВÙС) º (АÚВ)Ù(АÚС).

6°. Ø(АÙВ) º ØАÚØВ. 6¢. Ø(АÚВ) º ØАÙØВ.

7°. АÙ(АÚВ) º А. 7¢. АÚ(АÙВ) º А.

8°. ИÙА º А. 8¢. ЛÚА º А.

ЛÙА º Л. ИÚА º И.

9°. АÙØА º Л. 9¢. АÚØА º И.

10°. А®В º ØАÚВ.

11°. АÚВ º ØА®В.

12°. Ø(А®В) º АÙØВ.

13°. А«В º (А®В)Ù(В®А).

А«В º (ØАÚВ)Ù(ØВÚА).

А«В º (АÙВ)Ú(ØАÙØВ).

§ 4. КНФ ДНФ. СКНФ и СДНФ

Литеры. Контрарные литеры. ВС с тесными отрицаниями.

Теорема 1. Всякая ВС равносильна ВС с тесными отрицаниями.

Конъюнкты и дизъюнкты. ДНФ и КНФ.

Полные конъюнкты и дизъюнкты над списком Х₁, Х₂, …, Х_n. СДНФ и СКНФ.

Теорема 2. Всякая ВС равносильна некоторой ДНФ и некоторой КНФ.

Теорема 3. 1°. Всякая ВС над списком Х₁, Х₂, …, Х_n, не являющаяся противоречивой, единственным образом представляется в виде СДНФ.

2°. Всякая ВС над списком Х₁, Х₂, …, Х_n, не являющаяся тавтологией, единственным образом представляется в виде СКНФ.

§ 5. Принцип двойственности

Негатив А¢ и двойственная А^* высказывательные схемы к ВС с тесными отрицаниями А.

Теорема. Принцип двойственности

1°. ØА º А¢.

2°. Если ВС А является противоречием, то А^* является тавтологией.

3°. Если ВС А является тавтологией, то А^* является противоречием.

4°. Если А º В, то А^* º В^*.

5°. Если ВС А®В является тавтологией, то ВС В^*®А^* также является тавтологией.

§ 6. Отношение следования

Отношение следования на множестве ВС. А ⊨ В или А É В. А сильнее В. В слабее А. А является достаточным условием для В. В является необходимым условием для А.

Теорема. Свойства отношения следования

1°. Отношение следования является рефлексивным и транзитивным.

2°. (Критерий равносильности) А É В тогда и только тогда, когда (А®В) является тавтологией.

3°. А º В тогда и только тогда, когда А É В и В É А.

Правильные рассуждения.

§ 7. Булевы функции. Полиномы Жегалкина

Булевы функции и их композиция. Количество булевых функций от n переменных. Каталог бинарных булевых функций.

Высказывательные схемы в базисе F. ВС(F).

Полные и независимые множества булевых функций F.

Одночлены и многочлены над списком Х₁, Х₂, …, Х_n.

Теорема. Всякая булева функция от n переменных единственным образом представляется в виде многочлена Жегалкина.

§ 8. Замкнутые классы булевых функций

Сохраняющие 0 функции. С₀. Сохраняющие 1 функции. С₁. Самодвойственные функции. S. Линейные функции. L. Монотонные функции. M.

Теорема. Каждый из классов С₀, С₁, S, L, M замкнут относительно композиции.

§ 9. Теорема Поста

Теорема Поста^*. Множество F булевых функций является полным тогда и только тогда, когда оно не содержится ни в одном из классов С₀, С₁, S, L, M.

Глава II.

Формальные языки первого порядка (Логика предикатов)

§ 1. Высказывательные формы. Кванторы

Высказывательные формы. Предикаты. Логические операции над ними. Кванторы. Грамматика и семантика кванторов. Геометрическое истолкование кванторов.

§ 2. Алфавит и грамматика языков первого порядка*

Алфавит, грамматика и семантика формального языка.

Алфавит – перечень всех знаков, с помощью которых составляются все ЗС данного формального языка.

Грамматика – перечень правил, с помощью которых составляются некоторые категории ЗС – так называемые ППЗС, которые считаются осмысленными в данном языке. Эти правила позволяют также классифицировать ППЗС.

Семантика – совокупность правил, с помощью которых ППЗС придается смысл.

Общие требования к алфавиту, грамматике, семантике.

1. Считается, что мы умеем воспроизводить, распознавать и отождествлять два конкретных начертания данного знака и различать различные знаки.

2. Нас не интересует физическое строение знаков. Вместо этого мы предполагаем, что знаки обладают новым содержанием. Смысл его заключается в форме знаков и возможности их различного сочетания. Ввиду того, что форма знаков и ЗС будет определять их содержание, языки и называются формальными.

3. Знаки алфавита и правила их сочетания должны обеспечить однозначное прочтение ЗС.

4. Правила грамматики должны обеспечить выяснение, является ли ППЗС произвольное ЗС, а в случае положительного ответа, определять категорию этого ППЗС.

5. Правила семантики, придающие смысл ППЗС, должны это делать единственным образом.

Алфавит, категории алфавита: C,V, F, R, L, S.

L_Set, L_Ar.

Определение терма.

Определение формулы.

Соглашения об употреблении греческих букв в метаязыке.

§ 3. Чтение знакосочетаний*

Экономия скобок

Правила опускания и восстановления скобок в формулах.

1. Областью действия знака отрицания и квантора является ближайшая от него правая часть, являющаяся формулой.

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

2. Заключаем в скобки (если они отсутствуют) знаки отрицания и кванторы с их областями действия. Затем последовательно заключаем в скобки знак конъюнкции с его областью действия, а далее знак дизъюнкции, импликации и эквиваленции с их областями действия.

3. Если в ЗС встречаются подряд несколько одинаковых бинарных знаков, то скобки восстанавливаются справа

В конкретных языках первого порядка встречаются конкретные знаки операций и отношений. В этих языках восстановление скобок начинается с восстановления скобок при знаках операций, затем – при знаках отношений, и только потом восстанавливаются скобки по правилам 1–3.

§ 4. Грамматика языков первого порядка: свобода, связанность, подстановки

I. Свобода и связанность

Связанные и свободные вхождения переменных и ЗС.

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

II. Подстановки

Подстановка. Последовательная (цепная) подстановка. Одновременная подстановка. m , .

Теорема 1^*. Общие свойства подстановок

1°. Вообще говоря, ¹ и оба они отличны от .

2°. = , где = q₁ ,

= , где = q₂ .

3°. = ... ... , где b₁, b₂, ..., b_n – различные новые переменные.

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

1°. Если s и t – термы, a – переменная, то t – терм.

2°. Если t – терм, j – формула, a – переменная, то j – формула.

3°. Если s, s¢ и t – термы, а t¢ получается из t заменой некоторых выделенных вхождений s на вхождения s¢, то t¢ – терм.

4°. Если s и s¢– термы, j – формула, и j¢ получается из j заменой некоторых выделенных вхождений s на вхождения s¢, то j¢ – формула.

5°. Если j, y и c – формулы, и j¢ получается из j заменой некоторых выделенных вхождений y на вхождения c, то j¢ – формула.

III. Термы, допустимые для подстановки

Примеры термов, допустимых для подстановки и не допустимых для подстановки.

Теорема 3.Простейшие свойства допустимости

1°. Если терм не содержит свободных вхождений переменных, то он допустим для подстановки в любую формулу.

2°. Если формула не содержит свободных вхождений переменной a, то любой терм допустим для подстановки в эту формулу на месте a.

3°. Если формула не содержит связанных вхождений переменных, то любой терм допустим для подстановки на месте любой переменной.

§ 5. Семантика языков первого порядка: интерпретации и значения термов

D: I₁(=D)+I₂(z_i c_iÎD)+I₃(w O )+I₄(p R ). sqD.

Определение значения терма на последовательности d. át, dñ_D.

d – изменение e по V₀, (совпадает на V \ V₀).

Теорема 1*.Если d совпадает с e на Free t, то át, dñ_D = át, eñ_D.

Следствие. Если Free t = Æ, то át, dñ_D – величина постоянная для любой

dÎ sq D. Она называется значением терма t в данной интерпретации и обозначается átñ_D.

Теорема 2*.Семантическое правило замены в термах

Пусть s и t – термы, a_j – переменная, t¢ = t , d – произвольная последовательность из sq D, d ¢ – изменение d по a_j такое, что d = ás, dñ_D.

Тогда át¢, dñ_D = át, d ¢ñ_D.

Равнозначность термов. Логическая равнозначность. º_D. º.

Теорема 3*.Свойства равнозначности

1°. Отношение равнозначности является отношением эквивалентности.

2°. (Правило замены) Пусть s, s¢ и t – термы, t¢ получается из t заменой некоторых выделенных вхождений s на вхождения s¢. Тогда если s º s¢, то t º t¢.

§ 6. Семантика языков первого порядка: истинностные значения формул

B = {0, 1}. 0 < 1.

Определение значения формулы на последовательности d. áj, dñ_D.

Теорема 1*.Если d совпадает с e на Free j, то áj, dñ_D = áj, eñ_D.

Следствие. Если Free j = Æ, то áj, dñ_D – величина постоянная для любой dÎsqD. Оно называется значением формулы j в данной интерпретации и обозначается ájñ_D.

D⊨j[d] – формула j выполняется на последовательности d в интерпретации D (d удовлетворяет j).

Теорема 2.Свойства выполнимости

1°. Если j = p(t₁, t₂, ..., t_n), то D⊨j[d] Û (át₁, dñ_D, át₂, dñ_D, ..., át_n, dñ_D)ÎR, где R – значение p в интерпретации D.

2°. Если j = Øy, то D⊨j[d] Û D⊭y[d].

3°. Если j = j₁Új₂, то D⊨j[d] Û D⊨j₁[d] или D⊨j₂[d].

4°. Если j = j₁Ùj₂, то D⊨j[d] Û D⊨j₁[d] и D⊨j₂[d].

5°. Если j = j₁®j₂, то D⊨j[d] Û D⊨j₁[d] и D⊭j₂[d].

6°. Если j = j₁«j₂, то D⊨j[d] Û D⊨j₁[d] и D⊨j₂[d] или D⊭j₁[d] и D⊭j₂[d].

7°. Если j = ("a)y, то D⊨j[d] Û D⊨y[d ¢] для всех d ¢, являющихся изменениями d по a.

8°. Если j = ($a)y, то D⊨j[d] Û D⊨y[d ¢] для некоторой d ¢, являющейся изменением d по a.

§ 7. Понятие истины для языков первого порядка

Высказывания. Истинность и ложность высказывания в данной интерпретации. D⊨j. D⊭j.

Теорема 1.Свойства истинности высказываний

Пусть j – высказывание.

1°. Всякое высказывание либо истинно, либо ложно. Высказывание не может быть одновременно истинным и ложным.

2°. Если j = p(t₁, t₂, ..., t_n), то D⊨j Û (át₁ñ_D, át₂ñ_D, ..., át_nñ_D)ÎR, где R – значение p в интерпретации D.

3°. Если j = Øy, то D⊨j Û D⊭y.

4°. Если j = j₁Új₂, то D⊨j Û D⊨j₁ или D⊨j₂.

5°. Если j = j₁Ùj₂, то D⊨j Û D⊨j₁ и D⊨j₂.

6°. Если j = j₁®j₂, то D⊨j Û D⊨j₁ и D⊭j₂.

7°. Если j = j₁«j₂, то D⊨j Û D⊨j₁ и D⊨j₂ или D⊭j₁ и D⊭j₂.

8°. Если j = ("a)y, то D⊨j Û D⊨y[d] для всех dÎsqD.

9°. Если j = ($a)y, то D⊨j Û D⊨y[d] для некоторой d.

§ 8. Истинность и логическая истинность

Истинные в данной интерпретации формулы. D⊨j.

Логически истинные формулы. ⊨j.

Формулы, являющиеся частными случаями высказывательных схем.

Теорема 1*. Пусть j – частный случай высказывательной схемы F, D – интерпретация, dÎ sq D. Тогда существует sÎ q B такая, что áj, dñ_D = áF, sñ.

Теорема 2. Всякая формула ЯПП, являющаяся частным случаем тавтологии, логически истинна.

Теорема 3.Простейшие свойства логически истинных формул

Совпадает с Теоремой I.2.1.

Некоторые не тавтологические логически истинные формулы

Теорема 4*.Семантическое правило замены в формулах

Пусть j – формула, a_j – переменная, t – терм, допустимый для подстановки в j на месте a_j, j¢ = j , d – произвольная последовательность из sq D, d ¢ – изменение d по a_j такое, что d = át, dñ_D. Тогда áj¢, dñ_D = áj, d ¢ñ_D.

Теорема 5.Если формула j готова для подстановки терма t на месте переменной a и если j¢ = j , то

1) ⊨ ("a)j®j¢;

2) ⊨j¢®($a)j.

Теорема 6.1°.Если aÏ Free j, то

а) ⊨ ("a)(jÚy)®jÚ("a)y, в частности,

б) ⊨ ("a)(j®y)®(j®("a)y).

2°. Если aÏ Free y, то

а) ⊨ ("a)(jÚy)®($a)jÚy;

б) ⊨ ("a)(j®y)®(($a)j®y).

3°. ⊨j Û ⊨ ("a)j.

§ 9. Дедуктивная сила и равносильность формул

Дедуктивная сила и равносильность формул. j É y. j º y.

Теорема 1. Простейшие свойства дедуктивной силы

1°.j É j.

2°. Если j É y и y É y, то j º y и наоборот.

3°. Если j É y и y É c, то j É c.

Теорема 2. Простейшие свойства равносильности

1°.j º j.

2°. Если j º y, то y º j.

3°. Если j º y и y º c, то j º c.

Теорема 3. Согласованность дедуктивной силы с логическими операциями

Пусть j É y. Тогда

1°.Øy É Øj.

2°. cÚj É cÚy.

3°. cÙj É cÙy.

4°.c®j É c®y.

5°. c«j É c«y.

6°. Если aÏ Free j, то j É ("a)y.

7°. ("a)j É ("a)y.

jÚc É yÚc.

jÙc É yÙc.

y®c É j®c.

j«c É y«c.

Если aÏ Free y, то ($a)j É y.

($a)j É ($a)y

Теорема 4.Согласованность равносильности с логическими операциями

Пусть j º y. Тогда

1°.Øj º Øy.

2°. cÚj º cÚy.

3°. cÙj º cÙy.

4°.c®j º c®y.

5°. c«j º c«y.

6°. Если aÏ Free j, то j º ("a)y.

7°. ("a)j º ("a)y.

jÚc º yÚc.

jÙc º yÙc.

j®c º y®c.

j«c º y«c.

Если aÏ Free y, то ($a)j º y.

($a)jº ($a)y

Теорема 5. Теорема о равносильной замене

Пусть формула y¢ получается из формулы y заменой некоторых вхождений ее подформулы j на вхождения j¢. Тогда если j º j¢ то y º y¢.

Теорема 6. Пусть формулы j и y получаются из высказывательных схем F и Y заменой всех высказывательных переменных формулами, при условии, что все вхождения одной и той же переменой заменяются вхождениями одной и той же формулы. Тогда

1°. Если F ® Y тавтология, то j É y.

2°. Если F « Y тавтология, то j º y.

Теорема 7. Законы поглощения

1°. Если ⊨j, то jÙy º ØjÚy º j®y º j«y º y.

2°. Если ⊨y, то j®Øy º j«Øy º Øj.

Теорема 8. 1°. Если j É y, то jÙy º j и jÚy º y.

2°. Если j₁ É y₁ и j₂ É y₂, то j₁Új₂ É y₁Úy₂, j₁Ùj₂ É y₁Ùy₂.

3°. Если j É c, y Éc, то jÚy Éc.

4°. Если j É y, j Éc, то j É yÙc.

§ 10. Простейшие свойства кванторов

Теорема 1.1°. ("a)j É j, j É ($a)j.

2°. Если aÏFree j, то ("a)j º j, j º ($a)j.

Теорема 2. Правила отрицания

1°.($a)j º Ø("a)Øj.

2°. Ø($a)j º ("a)Øj.

3°. ("a)j º Ø($a)Øj.

4°.Ø("a)j º ($a)Øj.

Теорема 3. Правила перестановки кванторов

1°.("a)("b)j º ("b)("a)j.

2°. ($a)($b)j º ($b)($a)j.

3°. ($a)("b)j É ("b)($a)j.

4°. ("b)($a)j É ($a)("b)j.

Непосредственные алфавитные варианты. Алфавитные варианты.

Теорема 4. Теорема об алфавитных вариантах

1°.Непосредственные алфавитные варианты равносильны.

2°. Алфавитные варианты равносильны.

§ 11. Распределительные законы для кванторов

Теорема.Распределительные законы для кванторов

($a)jÚ("a)y

⇗ ⇘

1°. ("a)jÚ("a)y⇒ ("a)(jÚy) ($a)jÚ($a)y º ($a)(jÚy).

⇘ ⇗

("a)jÚ($a)y

($a)jÙ("a)y

⇗ ⇘

2°. ("a)(jÙy) º ("a)jÙ("a)y ($a)(jÙy)⇒ ($a)jÙ ($a)y.

⇘ ⇗

("a)jÙ($a)y

("a)j®("a)y

⇗ ⇘

3°. ($a)j®("a)y⇒ ("a)(j®y) ("a)j®($a)yº($a)(j®y).

⇘ ⇗

($a)j®($a)y

("a)j«("a)y ($a)j«("a)y

⇗ ⇘

4°. ("a)(j«y) ($a)(j«y).

⇘ ⇗

($a)j«($a)y ("a)j«($a)y

5°. Во всех схемах знак “⇒” нельзя заменить на знак “º”.

§ 12. Дальнейшие распределительные законы. Предварённая нормальная форма

Теорема 1. Дальнейшие распределительные законы

Если aÏ Free j, то

1°.("a)(jÚy) º jÚ("a)y.

2°. ("a)(jÙy) º jÙ("a)y.

3°.("a)(j®y) º j®("a)y.

4°. ($a)(jÚy) º jÚ($a)y.

5°. ($a)(jÙy) º jÙ($a)y.

6°. ($a)(j®y) º j®($a)y.

Если aÏ Free y, то

("a)(jÚy) º ("a)jÚy.

("a)(jÙy) º ("a)jÙy.

("a)(j®y) º ($a)j®y.

($a)(jÚy) º ($a)jÚy.

($a)(jÙy) º ($a)jÙy.

($a)(j®y) º ("a)j®y.

Предварённая нормальная форма.

Теорема 2. Для каждой формулы существует равносильная ей формула, имеющая предварённую нормальную форму.

§ 13. Типовые кванторы

(D1) Считаем ("a)_cj сокращением для ("a)(c®j).

(D2) Считаем ($a)_cjсокращением для ($a)(cÙj).

Теорема 1. Связь типовых кванторов с обычными

1°. ("a)j É ("a)_cj.

2°. ($a)_cj É ($a)j.

Теорема 2. 1°. Если ⊨ ($a)c, то ("a)_cj É ($a)_cj.

2°. Вообще говоря, ("a)_cj É ($a)_cj.

Теорема 3.Если aÏ Free j, то ("a)_c(jÚy) É jÚ("a)_cy.

Теорема 4. Пусть j¢ = j , c¢ = c , причём обе подстановки допустимы. Тогда

1°. ("a)_cj É c¢®j¢.

2°. c¢Ùj¢ É ($a)_cj.

3°. Если ⊨c¢, то ("a)_cj É j¢ É ($a)_cj.

Теорема 5. Пусть j É y.

1°. Если aÏ Free j, то j É ("a)_cy. Если aÏ Free y, то ($a)_cj É y.

2°. ("a)_cj É ("a)_cy. ($a)_cj É ($a)_cy.

Теорема 6. Если aÏ Free j и ⊨ ($a)c, то ("a)_cj º j º ($a)_cj.

Теорема 7.Законы отрицания для типовых кванторов

1°. Ø("a)_cj º ($a)_cØj.

2°. Ø($a)_cj º ("a)_cØj.

Теорема 8. Законы перестановочности типовых кванторов

Если aÏ Free c¢ и a¢Ï Free c, то

1°. ("a)_c("a¢)_c¢j º ("a¢)_c¢("a)_cj.

2°. ($a)_c($a¢)_c¢j º ($a¢)_c¢($a)_cj.

3°. ($a)_c("a¢)_c¢j É ("a¢)_c¢($a)_cj.

4°. Вообще говоря, обращение к 3° неверно.

Теорема 9. Пусть ⊨ ($a)c. Тогда для кванторов типа c имеют место аналоги всех утверждений, сформулированных в теореме о распределительных законах для кванторов.

Примечание. На самом деле это предположение используется в каждой строке только в одном месте.

Теорема 10. Пусть ⊨ ($a)c. Тогда для кванторов типа c имеют место аналоги всех утверждений, сформулированных в теореме 7.1.

Теорема 11. Для каждой формулы с кванторами типа c существует равносильная ей формула, имеющая ПНФ.