Критерий условной выводимости

Теорема 1.37. Г Ь А в ИВ тогда и только тогда, когда (формула, А истинна на любом наборе значений переменных, на котором, истинны все формулы из множества Г.

Доказательство. В одну сторону доказательство повторяет доказательство корректности ИВ: аксиомы и гипотезы истинны на любом наборе значений переменных, на котором истинны все формулы из Г, применение правила modus ponens сохраняет это свойство.

Чтобы доказать утверждение теоремы в обратную сторону, рассмотрим вначале случай конечного множества.

Пусть формула А истинна на любом наборе значений, на котором истинны все Д. Многократным применением теоремы дедукции устанавливаем, что Г Ь А равносильно Ь С, где С = f Д—>(Д—? … —"(2?_т—"Л)) V Формула С является тавтологией: она истинна., если хотя бы одна из формул Д ложна, а если все Д истинны, то А также истинна по условию теоремы, так что формула С также истинна. Из теоремы полноты заключаем, что формула С выводима.

Случай бесконечного множества формул сведём к случаю конечного множества. Если формула А истинна на любом наборе значений, на котором истинны все формулы из множества Г, то для каждого набора а значений входящих в формулу А переменных, на котором А ложна, можно указать формулу В_а? Г, которая также ложна на а. Переменные, входящие в формулу Л, могут принимать лишь конечное число различных значений, поэтом}' множество формул {Да} конечно и по его построению формула А истинна на любом наборе значений, на котором истинны все формулы из множества { В_а }. Значит, { В_а } I-А. ?

Задачи.

1.15. Проверьте выполнение следующих утверждений о выводимости в исчислении высказываний.

1.16. Пусть Г — множество всех формул исчисления высказываний, в которые не входят отрицания. Докажите, что.

• 1.17. Формулы F1 и F2 невыводимы в исчислении высказываний. Верно ли, что невыводима формула ~(F —> IF2)?
• 1.18. Формулы А, В выводимы в исчислении высказываний. Докажите, что любая формула вида ((С—>~В)—>С также выводима в исчислении высказываний.
• 1.19. Множество формул Г состоит из всех формул вида

Х—Ъ~х_П) п = 2,3,——Верно ли, что.

• а) формула а>2—>~х выводима из Г?
• б) формула 1х2—*~х выводима из Г?
• 1.20. Противоречиво ли множество формул Г, которые имеют вид ~А —" В, где А, В — произвольные формулы?
• 1.21. Для каких п существует такое противоречивое множество из п формул, что любое его подмножество из п — 1 формулы ней роти вореч и во ?
• 1.22. Проверьте полноту множества формул Г, если
• а) Г включает в себя формулы Х{ —> yi, у —> Zi, zt —у 1 хи 1 Xi -> Zi, Zi -? 1 yi, 1 Ui Xi? (Xi, Уг, Zi — переменные);
• б) Г включает в себя формулы вида А —> ~|Л, где А — 11роизвольная формула;
• в) Г включает в себя формулы вида А —" В, где А, В — произвольные формулы.
• г) Г включает в себя формулы вида х —> Л, где х — некоторая переменная, а А — произвольная формула.
• 1.23. Верно ли, что существует полное и непротиворечивое множество формул, в каждую формулу которого входит более 2 переменных?