Исчисление высказываний и булевы функции

Для ИВ есть естественная семантика — формулы ИВ реализуют булевы функции.

Напомним, что аргументы и значение булевой функции f (x принадлежат множеству {0,1}. Посколь ку область определения булевой функции конечна, её можно задать таблицей значений. Приведём таблицы значений некоторых булевых функций:

Если понимать под символом 0 ложь, а под символом 1 истину, то приведённые выше функции правильно отражают смысл пропозициональных связок (соответственно, отрицания, конъюнкции, дизъюнкции, импликации, эквивалентности; последняя функция часто обозначается XOR и имеет смысл исключающего ИЛИ — истинно ровно одно из двух высказываний).

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

• 1: Значение формулы, которая является переменной, совпадает со значением этой переменной.
• 2: Значение формулы (1J5) является отрицанием значения формулы В.
• 3: Значение формулы (А—>В) является импликацией значений формул Л, В.

Таким образом, каждая формула А в ИВ реализует. булеву функцию А (х). При этом тавтологии реализуют тождественно равные 1 функции.

Имея некоторый набор булевых функций Т {систему (функций), можно строить новые функции с помощью операций замены переменных и суперпозиции (подстановки одной функции в аргумент другой функции).

Напомним, что система функций Т называется полной, если любую булеву функцию можно представить с помощью замены переменных и суперпозиций функций из системы Т. Критерий полноты системы булевых функций даёт теорема Поста.

Теорема 1.17 (теорема Поста). Система функций полна тогда и только тогда, когда она не содержится целиком в одном из классов То, Т, L, М, S, т. е. когда она содержит.

• 1: функцию, не сохраняющую 0 (/(б) = 1);
• 2: функцию, не сохраняющую 1 (/(1) = 0);
• 3: нелинейную функцию (т. е. функцию, которая не представима в виде

при каких-то значениях а-* € {(), 1});

• 4: немонотонную функцию (т. е. для некоторых наборов аргументов о, выполнено d < /?, /(d) = 1, /(,#) = 0, сравнение наборов значений покомпонентное);
• 5: несамодвойственную функцию (неравенство

выполнимо на некотором наборе значений аргументов (а?1 ,…, х_п)).

Применим теорему Поста к систему функций {!,—"}. Эта система содержит функцию 1, которая не сохраняет 0, не сохраняет 1 и не является монотонной. Также в ней есть функция —>•, которая не является самодвойственной и не является линейной. Таким образом, по теореме Поста эта система функций полна, т. е. любую булеву функцию можно выразить через отрицание и импликацию. Например, можно проверить по таблице значений, что.

Из полноты системы функций {1, —"} следует, что для любой булевой функции /, найдётся формула ИВ, которая реализует функцию /.

Задачи.

• 1.4. Формулы 1F и F2 выводимы в исчислении высказываний. Верно ли, что выводима формула F —> F2?
• 1.5. Множество формул Г состоит из формул, в которые входят лишь переменные ж, у. Верно ли, что для переменной z выполнено Г Ь z?