Лемма доказана.
13. Теорема о том, что любая тавтология выводима в ИВ Тавтология — тождественно истинное высказывание.
Теорема. Если формула тождественно истинна / является тавтологией, то она выводима.
Доказательство.
[Для доказательства этой теоремы нужна лемма 12-го вопроса!]
Будем использовать лемму и ( ) ((¬ ) ).
( ) ((¬ ) )?
По свойству ИВ №2 («если , то , ») — переносим два раза влево:
( ), (¬ ) ?
По уже доказанному в 9-ом вопросе утверждению (« ≡ ¬ ¬»):
¬ ¬ ! ¬ ¬ ¬¬ !
По уже доказанному в 9-ом вопросе утверждению («¬¬ ≡ »):
¬ ¬ !
Далее по аксиоме А3:
(¬ ¬ ) ((¬ ) )!
По свойству ИВ №2 («если , то , ») — переносим два раза влево:
(¬ ¬ ), (¬ ) !
По свойству №3 («лишняя формула не мешает») — добавляем ( ), (¬ ):
(¬ ¬ ), (¬ ), ( ), (¬ ) !
По свойству №4 («удаление выводимой формулы») — так как ¬ ¬ и ¬ ¬ , то удаляем (¬ ¬ ), (¬ ):
( ), (¬ ) !
По теореме дедукции («если , , то ») — переносим два раза вправо:
( ) ((¬ ) )! (1) Следствие. Если , и , ¬ , то .
Применяя теорему о дедукции к условиям, получим:
(2) и ¬ (3).
.. к (1) и (2): (¬ ) (4).
.. к (3) и (4): .
Теперь перейдём к основному доказательству.
Пусть тождественно истинная формула и 1, 2, … , — список её переменных. Тогда при любом наборе 1, 2, … , значение формулы на этом наборе = 1 (по условию формула тождественно истинна). Таким образом, по лемме имеем:
1 |
, 2 |
, … , (1) |
1 |
2 |
|
Так как в любом случае будет равно 1, то из (1) будем иметь две секвенции (для
|
= 1 и = 0): |
|
|
|
|
|
|
|
|
|
1 |
, 2 |
, … , −1 |
, |
|
1 |
2 |
−1 |
|
|
1, 2, … , −1, ¬ |
|||
|
1 |
2 |
−1 |
|
|
Отсюда по доказанному ранее «если , и , ¬ , то », получим: |
|||
|
1 |
, 2 |
, … , −1 |
(2) |
|
1 |
2 |
−1 |
|
|
Далее точно также из секвенции (2) можно убрать −1. |
|||
|
|
|
|
−1 |
Продолжая этот процесс, получим (то есть выводится из аксиом). Теорема доказана.
14. Полнота и непротиворечивость ИВ
Некоторая теория называется противоречивой, если существует формула в этой теории такая, что из аксиом в ней можно вывести как , так и ¬. В противном случае теория называется непротиворечивой.
Теорема (о непротиворечивости ИВ). В теории ИВ невозможно вывести из аксиом одновременно формулы и ¬.
Доказательство. Если выводима (из аксиом), то она тождественно истинна (см. 11ый вопрос), значит ¬ не является тождественно-истинной ( ¬ на любом наборе переменных равна 0), а это значит (см. 13-ый вопрос), что ¬ не выводима (из аксиом).
Замечание. Мы доказали, что теория ИВ непротиворечива. Однако это доказательство связано с тем, что формулы в ИВ (в возможной интерпретации) принимают лишь два значения 0 и 1. Сравнительно нетрудно аксиоматически ввести арифметику. Однако в ней формулы уже могут принимать счётное множество значений (то есть по крайней мере все целые числа). Гёдель показал, что невозможно доказать противоречивость или непротиворечивость арифметики. После этого про любую науку доказывают или опровергают утверждение: данная наука непротиворечива, если непротиворечива арифметика.
Теорема (о полноте ИВ). ИВ — полная теория в узком смысле слова.
ФАТ называется полной в узком смысле, если добавление любой не выводимой формулы в качестве аксиомы приводит к противоречивой теории.
Доказательство (от противного).
Пусть — какая-нибудь невыводимая формула. Докажем, что присоединение к аксиомам приводит к противоречивой теории.
В ИВ — 3 аксиомы: 1, 2, 3 . В новой теории высказываний — 4 аксиомы:1, 2, 3, . Выводимость в этой теории будем обозначать (F). Требуется доказать, что
1, 2, 3, (F).
Пусть 1, 2, … , — набор переменных формулы . Так как невыводима в ИВ из аксиом, значит она не тождественно истинна (см. 11-ый вопрос), следовательно, она принимает значение 0 на каком-то наборе значений переменных 1, 2, … , , то есть
(1, 2, … , ) = 0.
Возьмём какую-нибудь новую переменную . Введем следующие формулы:
|
= ( ) = { |
, = 1 |
|
|
|
|
|
¬( ), = 0 |
|
|
|
Тогда ( , , … , ) ≡ 0. |
|
|
1 2 |
|
|
Пусть теперь — произвольная формула в ИВ, а ¬ — её отрицание. Тогда по определению импликации тождественно истинны формулы (1, 2, … , ) (1)
и (1, 2, … , ) ¬(2). Так как (1, 2, … , )(3) — аксиома, то применив
правило . . к (1) и (3), а также (2) и (3), получим, что (F) и (F) ¬ . Это и значит, что теория противоречива, и теорема доказана.
15. Предикаты. Кванторы. Свойства кванторов
Предикат — функция нескольких переменных, которая в области задания этих переменных, может принимать лишь два значения 1 или 0 (которые мы можем рассматривать как истину или ложь). Обозначается заглавными латинскими буквами, а участвующие в нем переменные — строчными латинскими буквами.
Пример предиката: ( , ) — двуместный предикат.
Предикат может иметь верхний индекс, который обозначает количество аргументов, и нижний для различения букв с одним и тем же числом аргументов. 12( , ).
Если предикат зависит от переменных, то он называется -местным.
Предикатом также является сама переменная в случае, если она принимает только два значения 1 и 0. В этом случае предикат считается нульместным.
Высказывания — это нульместные предикаты.
Область определения предиката называется интерпретацией.
Например, предложение «(конкретный) студент Иванов имеет дома компьютер» является высказыванием или нульместным предикатом. Это высказывание может принять значение 1 или 0. Однако предложение «студент имеет дома компьютер» уже не является высказыванием, а является одноместным предикатом. Область определения такого предиката — студенты (либо все, либо данного города, ВУЗа или группы).
Квантор — логическая операция, ограничивающая область истинности какого-либо предиката и создающая высказывание.
Особенность предикатов состоит в возможности введения для них кванторов существования и всеобщности .
Пусть — интерпретация предиката ( , ). Высказывания: ( ) ( ) истинно, если ( ) = 1 для всех .
( ) ( ) истинно, если ( ) = 1 для хотя бы одного . ( ) (без квантора) содержит свободную переменную .
(/ ) ( ) (с квантором) содержит связанную переменную .
Более сложный пример: ( 1)( 2) 13(1, 2, 3) ( 1) 22(1, 4).
В данном случае 1, 2 — связанные, а 3, 4 — свободные.
Причём ( 1)( 2) 12( 1, 3) 22( 1, 2) — не является формулой, так как 1 и 2 не могут быть связанными и свободными одновременно (кванторы примыкают к
первому предикату; можно исправить ситуацию, добавив скобки ( 12 22)).
Формулы, в которых нет свободных переменных, называются замкнутыми, а формулы, содержащие свободные переменные, — открытыми.
Свойства кванторов:
1) Перенос квантора через отрицание.
¬( ) ( ) ≡ ( ) ¬ ( ) ¬( ) ( ) ≡ ( ) ¬ ( )
Докажем первую равносильность. Пусть 1, 2, … , — набор всех свободных переменных формулы , отличных от , 1, 2, … , — любой набор значений свободных переменных, — произвольная интерпретация. Возможны два случая:
• Для любого элемента ( )| ,1,…, = 1. Тогда для любого элемента
¬ ( )| ,1,…, = 0. Отсюда по определению: ( ) ¬ ( )| 1,2,…, = 0. С
другой стороны, в этом случае ( ) ( )| 1,2,…, = 1 . Отсюда
¬( ) ( )| 1,2,…, = 0.
•Для некоторого элемента 0 ( )| 0, 1,…, = 0. Тогда для элемента 0
¬ ( )| 0, 1,…, = 1. Отсюда ( ) ¬ ( )| 1,2,…, = 1. С другой стороны, в
этом случае ( ) ( )| 1,2,…, = 0. Отсюда ¬( ) ( )| 1,2,…, = 1.
Докажем вторую равносильность. Применим первую равносильность к формуле
¬ ( ) . Тогда ¬( ) ¬ ( ) ≡ ( ) ¬¬ ( ) ≡ ( ) ( ) и, кроме того, ¬( ) ( ) ≡ ¬¬( ) ¬ ( ) ≡ ( )¬ ( ).
2) Вынос квантора за скобки.
Пусть формула содержит свободную переменную , а формула не содержит . Тогда имеют место следующие 4 формулы:
( ) ( ( ) ) ≡ ( ) ( ) ( ) ( ( ) ) ≡ ( ) ( ) ( ) ( ( ) ) ≡ ( ) ( ) ( ) ( ( ) ) ≡ ( ) ( )
Если формула также зависит от , то будут выполняться только две равносильности:
( ) ( ( ) ( )) ≡ ( ) ( ) ( ) ( ) ( ) ( ( ) ( )) ≡ ( ) ( ) ( ) ( )
Докажем первую из этих равносильностей (остальные доказываются аналогично).
Пусть 1, 2, … , — набор всех свободных переменных формулы ( ) ( ( )). Тогда они же и все свободные переменные формулы ( ) ( ) . Рассмотрим произвольную интерпретацию , пусть 1, 2, … , — любой набор значений свободных переменных 1, 2, … , . Так как формула не содержит переменной , то можно определить значение этой формулы на наборе 1, 2, … , (точнее, на его части, относящейся к свободным переменным формулы ). Если
| 1,2,…, = 0, то (( ) ( ) )| 1,2,…, = 0, и для любого элемента на
наборе значений , 1, 2, … , своих свободных переменных , 1, 2, … , формула ( ) принимает значение 0. Отсюда ( ) ( ( ) )| 1,2,…, = 0 . Если | 1,2,…, = 1, то для любого элемента на наборе , 1, 2, … ,
формулы ( ) и ( ) принимают одинаковые истинные значения. Отсюда
(( ) ( ) )| 1,2,…, = ( ) ( )| 1,2,…, = ( ) ( ( ) )| 1,2,…, .
3) Перестановка одноименных кванторов.
( )( ) ( , ) ≡ ( )( ) ( , ) ( )( ) ( , ) ≡ ( )( ) ( , )
4)Переименование связанной переменной.
Заменяя связанную переменную формулы другой переменной, не входящей в эту формулу, всюду в области действия квантора, мы получим равносильную формулу.
16. ИП — исчисление предикатов. Алфавит ИП. Формулы в ИП. Равносильность формул ИП. Приведённые и нормальные формулы ИП. Теоремы
о приведённой и нормальной форме формул ИП
Исчисление высказываний — очень узкая логическая система. Есть такие типы логических рассуждений, которые не могут быть осуществлены в рамках этой теории, например: «всякий друг Ивана есть друг Петра. Сидор не есть друг Петра. Следовательно, Сидор не есть друг Ивана». Корректность этих умозаключений основана на внутренней структуре самих предложений и на смысле слов «всякий» и «существуют».
Исчисление предикатов — исчисление функций нескольких переменных, которые в области задания этих переменных могут принимать лишь два значения 1 или 0 (которые мы, как всегда, можем рассматривать как истину или ложь).
1)Алфавит: латинские буквы (возможно с индексами): заглавные для обозначения предикатов, строчные — для обозначения переменных в предикатах.
2)Формулы:
1)Первичные (атомарные) формулы — предикаты. Связки 1-го порядка: ¬, и. Связки 2-го порядка: , , и ≡.
2)Если формула, то ¬ — тоже формула (причём все не связанные кванторами переменные остаются свободными, все связанные — связанными). Кроме того, если формула и — свободная переменная, входящая в , то выражения ( ) и ( ) — тоже формулы, причем становится связанной.
3)Если и — две формулы, то ( ), ( ), ( ) и ( ≡ ) — также являются формулами, причём все связанные переменные остаются связанными, а свободные — свободными.
4)Любая формула в ИП получается из первичных с помощью применения конечного числа правил 2 и 3.
Формулы и называются равносильными в данной интерпретации, если при любых возможных значениях свободных переменных (из данной интерпретации) обе формулы принимают одинаковые значения.
Если — интерпретация всех предикатов, входящих в формулы и , то равносильность этих формул в обозначается = ( ).
Формулы и называются равносильными (в ИП), если они равносильны в любой возможной интерпретации. Тогда равносильность обозначается так: ≡ .
Длина формулы в ИП — общее число входящих в неё символов предикатов, логических символов и символов кванторов. Так формула: ( )( , ) ( )( , ) — имеет длину 5 (пять знаков: ).