Материал: Ответы на экзаменационные вопросы по математической логике

10. Аксиоматическое введение в ИВ и

Функции отрицания и импликации являются базисом, и, значит, через них можно выразить любую булеву функцию и, в частности, конъюнкцию и дизъюнкцию .

Конъюнкция ( ̅̅̅̅̅̅̅ ( )):

≡ ≡ ¬ ¬

1) Если , , , то , (введение конъюнкции слева). 2) Если , , то , , (удаление конъюнкции слева).

3) Если { , то (введение конъюнкции справа).

4) Если , то { (удаление конъюнкции справа).

Дизъюнкция ( ≡ ¬ ):

1)Если (, ¬ ) или (, ) или (, ) , то , (введение дизъюнкции слева).

2)Если , , то (, ¬ ) или (, ) или (, ) (удаление дизъюнкции слева).

3) Если ( ) или ( ) или (, ¬ ) или (, ¬ ) или (, ¬ , ¬ ), то

(введение дизъюнкции справа).

4) Если , то ( ) или ( ) или (, ¬ ) или (, ¬ ) или

(, ¬ , ¬ ) (удаление дизъюнкции справа). Примем без доказательства.

11. Теорема о том, что всякая выводимая в ИВ формула есть тавтология Тавтология — тождественно истинное высказывание.

Теорема. Если формула выводима, то она тождественно истинна / является тавтологией (то есть на любом наборе переменных принимает значение, равное 1).

Доказательство.

[Для доказательства этой теоремы нужна лемма 12-го вопроса!]

Пусть формула выводима (из аксиом). Докажем, что при любых значениях переменных, входящих в неё, формула принимает значение 1. Непосредственно проверяем, что все аксиомы являются тождественно истинными формулами. Так как импликация из истины выводит только истину, то по правилу вывода . . (,) получаем, что тоже истинна. Так как других правил вывода в ИВ нет, то все выводимые (из аксиом) формулы тождественно истинны.

12. Доказательство леммы , , … ,

Исчисление высказываний — чисто логический вывод одних суждений из других. Ранее такая наука называлась схоластикой. То есть из некоторых общепризнанных фактов выводились другие суждения без всяких опытов. Например, если человек идёт в кино, то у него должны быть деньги. Разумеется, этот пример является простым и его легко провести в жизни без всякой дискретной математики. Однако в других случаях формальный логический вывод без применения правил ИВ бывает очень сложным и применение этой теории становится обязательным. Поэтому, для получения логических выводов мы заменяем суждения (которые могут быть либо истинными, либо ложными) латинскими буквами и получаем первичные формулы ИВ (и тем самым отказываемся от смысла этих суждений) и тогда мы можем считать, что эти самые буквы (то есть переменные или первичные формулы) являются числами, которые могут принимать только два значения 0 и 1.

Так как в формулы ИВ кроме переменных (то есть первичных формул) входят связки (отрицание и импликация), то по правилам этих булевых функций любая формула на определенном наборе переменных также принимает значения 0 или 1. Таким образом, если — формула в ИВ, 1, 2, … , — набор её переменных и 1, 2, … , — любой набор возможных значений этих переменных (из нулей и единиц), то (1, 2, … , ) — значение формулы на этом наборе. Тем самым мы получаем одну из возможных интерпретаций теории ИВ, которая переводит схоластические рассуждения на язык чисел (нулей и единиц).

¬ , , ¬ ¬ ( ¬ )

Формула выводима, если она выводится из аксиом (то есть ).

Пусть длина формулы означает количество связок в ней (то есть символов ¬ и ).

Лемма. Пусть — формула в ИВ, 1, 2, … , — набор её переменных и1, 2, … , — любой набор возможных значений этих переменных (из нулей и единиц) и — значение формулы на этом наборе. Тогда верна следующая секвенция:

Доказательство этой леммы проведём индукцией по длине формулы , которую обозначим (к). При = 0 формула не содержит символов отрицания и импликации и состоит из одной переменной . Поэтому в этом случае доказательство леммы сводится к очевидной секвенции .

Пусть > 0 и пусть формула (1) верна для всех формул, длина которых строго меньше . Докажем тогда, что лемма верна для формулы .

СЛУЧАЙ 1. Предположим, что формула совпадает с формулой ¬ ( = ¬). Тогда длина равна − 1, и для лемма верна по индукционному предположению. Кроме того, в формулы и входят одни и те же переменные. Пусть для набора1, 2, … , значение формулы на этом наборе равно , а формулы равно ′ (так как = ¬, то очевидно, что = ¬ ′).

а) Пусть = 1, тогда ′ = 0. По индукционному предположению верна секвенция

СЛУЧАЙ 2. Предположим, что формула имеет вид ( = ( )). Длина формул и меньше , поэтому для обеих формул лемма верна по индукционному предположению (в формулы и может входить меньшее число переменных, но так как лишние формулы не мешают, то лемма будет верна). Пусть для данного набора1, 2, … , значения , ′, ′′ являются значениями формул , и соответственно.

а) Пусть ′ = 0, тогда = 1. По индуктивному предположению верно:

По уже доказанному в 7-ом вопросе утверждению («если , то , ¬ ») и уже доказанному в 9-ом вопросе утверждению (« ≡ ¬¬») — переносим ¬ влево:

По свойству №3 («лишняя формула не мешает») — добавляем ¬:

По уже доказанному в 8-ом вопросе утверждению («если , ¬ , то »):

По теореме дедукции («если , , то »):

. . , !

По уже доказанному в 7-ом вопросе утверждению («если , то , ¬ ») и уже доказанному в 9-ом вопросе утверждению (« ≡ ¬¬») — переносим влево:

, , ¬ !

По свойству №2 («порядок формул не имеет значения») и уже доказанному в 8-ом вопросе утверждению («если , , то ¬») — переносим вправо:

, ¬ ¬( )!

По свойству №3 («лишняя формула не мешает») и по свойству №2 («порядок формул

По свойству №1 («, !» или « !»):

!

По свойству №3 («лишняя формула не мешает») и по свойству №2 («порядок формул не имеет значения») — добавляем в начало:

, !

По теореме дедукции («если , , то »):

!

По свойству №3 («лишняя формула не мешает») и по свойству №2 («порядок формул