Нормальные формы

Для произвольной пропозициональной переменной А и булевой константы введем обозначение

в силу этого определения .

Элементарной дизъюнкцией и элементарной конъюнкцией называются соответственно формулы , где - пропозициональные переменные.

В силу определения дизъюнкции элементарная дизъюнкция ложна (равна 0) тогда и только тогда, когда переменные одновременно примут значения . Из определения конъюнкции получаем, что элементарная конъюнкция истинна (равна 1) тогда и только тогда, если .

Пусть - фиксированные булевы векторы. Формула вида

имеет совершенную дизъюнктивную форму (СДНФ). Она принимает значение И только в случаях, когда .

Формула вида

имеет совершенную конъюнктивную форму (СКНФ). Она принимает значение Л только в случаях, когда .

Указанные в предыдущем пункте логические законы и тавтологии позволяют упрощать формулы, а также, приводить формулы к ДНФ, к СДНФ.

Пример 1. Упростим формулу . Используя законы де Моргана и выражение импликации через дизъюнкцию получаем: . Закон двойного отрицания позволяет полученную формулу записать в виде . Операция конъюнкция коммутативна, т.е. окончательно получим СДНФ для исходной формулы: .

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

Пример 2. Приведем формулу равносильными преобразованиями к ДНФ и, если возможно, к СДНФ. Выразим эквиваленцию через импликацию и конъюнкцию:

.

Благодаря свойству ассоциативности конъюнкции внешние скобки можем сдвинуть; после чего выразим импликацию через дизъюнкцию и отрицание: . По закону поглощения , тогда . Теперь воспользуемся законами дистрибутивности и ассоциативности конъюнкции и получим ДНФ для формулы . Легко заметить, что формула Ф тождественно ложна, т.е. не имеет СДНФ.

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

;

Разъяснение. Для построения СДНФ в таблице выделяем строки, в которых принимает значение 1, и получаем 3 булевых вектора , , , и т.д. Для построения СКНФ в таблице выделяются строки, в которых принимает значение 0, и получаем 5 булевых векторов , , , , , по которым находим и т.д.

Обращаем внимание студентов, что СДНФ существует только для тех булевых функций, которые принимают хотя бы один раз значение 1, а СКНФ существует только для тех функций, которые хотя бы один раз принимают значение 0.

Пример 3. Продемонстрируем на примере один из способов построения формул по таблицам значений (с точностью до равносильности).

Выделяем строчки, в которых Ф принимает значение 1. Для каждой выделенной строчки строим конъюнкцию букв , причем, если буква имеет значение 0, то перед ней ставится знак . В нашем случае мы строим элементарные дизъюнкции для 2-й, 5-й, 7-й строчек: , , . Тогда , т.е. является дизъюнкцией построенных элементарных конъюнкций.

Обратите внимание на то, что нами получена СДНФ.

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

Контрольные вопросы и упражнения

1. Сформулировать высказывание, заданное формулой . Является ли оно истинным, если А означает «число а делится на число b»; В – «число а делится на число с»; С – «число а делится на произведение b и с» (а, b, с – заданные целые числа)?

2. Выяснить, какие из данных формул являются тавтологиями:

а) ;

б) ;

в) .

3. Найти СДНФ и СКНФ для формул:

а) ;

б) .

4. Указать алгоритм нахождения ДНФ, СДНФ равносильными преобразованиями.

5. Что можно сказать об однозначности ДНФ (привести примеры), об однозначности СДНФ?

6. Указать тавтологии, позволяющие выражать одни операции через другие.

7. Указать, по крайней мере, 3 различные полные системы логических связок, т.е. такие, через которые выражаются все логические операции.

8. Данные формулы упростить путем равносильных преобразований (сделать их менее громоздкими):

а) ;

б) ;

в) ;

г) .

9. Следующие формулы равносильными преобразованиями привести к ДНФ, СДНФ:

а) ;

б) ;

в) ;

г) .

10. Следующие формулы равносильными преобразованиями привести к КНФ, СКНФ:

а) ;

б) ;

в) ;

г) .

11. Построить формулы по таблицам значений:

а) б)

12. Построить формулу Ф такую, чтобы данная формула была тавтологей:

а) ;

б) .

13. Построить формулу от трех переменных, которая истинна в том и только том случае, когда ровно две переменные ложны.

14. По СДНФ формул Ф и построить СДНФ формул , , .

ТЕМА III

Дата добавления: 2015-11-14