Алгоритм приведения формулы к ДНФ и КНФ

Основные понятия и теоремы

Вопросы и упражнения

1. Докажите законы алгебры логики с помощью таблиц истинности.

2. Выразите через штрих Шеффера, стрелку Пирса через конъюнкцию, дизъюнкцию; импликацию; эквивалентность.

3. Упростите формулы.

a.

b.

c.

d.

e.

f.

5. Используя основные законы и соотношения алгебры логики, необходимо установить справедливость формул.

1.

2.

3.

4.

5.

6.

Тема 3. Нормальные формы алгебры высказываний. Теорема о функциональной полноте

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

Переменные структурной формулы соответствуют входам функциональной схемы. Значения переменных в таблице истинности соответствуют значениям входов функциональной схемы.

Введём определения.

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

Элементарная конъюнкция – это конъюнкция конечного множества переменных и их инверсий.

Элементарная дизъюнкция - это дизъюнкция конечного множества переменных и их инверсий.

Число аргументов, образующих элементарную дизъюнкцию или конъюнкцию, называется рангом.

Пример 3.1. Формула - элементарная конъюнкция третьего ранга; - элементарная дизъюнкция второго ранга.

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

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

Пример 3.2. Формула - ДНФ; формула - КНФ; формула является одновременно КНФ и ДНФ.

Теорема 3.1.

1) Любая формула эквивалентна некоторой ДНФ. 2) Любая формула эквивалентна некоторой КНФ.

1. Выражаем все логические операции, участвующие в построении формулы, через дизъюнкции, конъюнкции, отрицания.

2. Используя законы де Моргана, переносим все отрицания к переменным и сокращаем двойные отрицания.

3. Используя закон дистрибутивности, преобразуем формулу так, чтобы все конъюнкции выполнялись раньше дизъюнкций.

Пример 3.3. Привести формулу к ДНФ.

Выразим логические операции и через :

В полученной формуле перенесём отрицание к переменным и сократим двойные отрицания:

.

Используя закон дистрибутивности, приводим формулу к ДНФ:

.

Приведение формулы к КНФ производится аналогично приведению её к ДНФ, только п.3 формулируется так:

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

Пример 3.4. Привести формулу к КНФ.

Выразим логические операции и через :

В полученной формуле перенесём отрицание к переменным и сократим двойные отрицания:

.

Используя закон дистрибутивности, приводим формулу к КНФ:

.

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

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

Пример 3.5. .

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

Пример 3.6. .