Теорема 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 существует равносильная ей формула, имеющая ПНФ.