Всякая пропозициональная форма, содержащая n пропозициональных букв, порождает истинностную функцию n аргументов

Полные системы связок

Логически эквивалентные формы порождают одну и ту же истинностную функцию (Доказать!)

Утверждение: Всякая истинностная функция порождается некоторой пропозициональной формой, содержащей лишь связки .

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

Функция представлена истинностной таблицей с строками.

Введем n штук пропозициональных букв .

Для каждой строки составим конъюнкцию следующим образом: , где есть , если в i-й строке истинностной таблицы принимает значение «и», и есть , если принимает значение «л».

Обозначим через D дизъюнкцию всех таких, что функция f в строке i истинностной таблицы получает значение «и». Истинностная форма D совпадает с f.

D называется (совершенной) дизъюнктивной нормальной формой (ДНФ).

Пример:

х1	х2	f(x1,x2)
и	и	л
л	и	и
и	л	и
л	л	и

Искомая форма

Утверждение: Для порождения истинностной функции f достаточно любой пары пропозициональных связок из следующих: .

Доказательство следует из тавтологий (проверить!):

; ; ;

Одного отрицания недостаточно для порождения любой истинностной функции.

А	В	Конъюнкция отрицаний	Штрих Шеффера
и	и	л	л
л	и	л	и
и	л	л	и
л	л	и	и

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

.

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

Определение: Пусть содержит лишь связки . Тогда называется двойственной к , если получается из заменой на , а на .

Утверждения:

1). ;

2).

3). Если , то - закон двойственности.

ДНФ - дизъюнкция элементарных конъюнкций (конъюнкций переменных, возможно с отрицанием). ДНФ может быть получена раскрытием скобок по первому дистрибутивному закону, когда формула содержит только конъюнкцию, дизъюнкцию и тесное отрицание.

КНФ - конъюнктивная нормальная форма - конъюнкция элементарных дизъюнкций.

Для получения КНФ для формула следует построить двойственную, привести ее к ДНФ и вновь перейти к двойственной:

Теорема 1: Для того, чтобы формула была тождественно истинной необходимо и достаточно, чтобы каждая элементарная сумма ее конъюнктивной нормальной формы содержала по крайней мере два слагаемых, одно из которых является отрицанием другого.

Теорема 2: Для того, чтобы формула была тождественно ложной необходимо и достаточно, чтобы каждое элементарное произведение ее дизъюнктивной нормальной формы содержало по крайней мере два сомножителя, одно из которых является отрицанием другого.

Формула называется выполнимой, если существует набор значений, входящих в нее переменных, при которых она принимает значение «истина» (то есть формула не является тождественно ложной).

Разрешимость - является ли заданная формула выполнимой?

Способ 1. - построить истинностную таблицу и проверить.

Способ 2 - по теореме 2 убедиться, что формула не является тождественно ложной.

Дата добавления: 2013-12-13