15. Дизъюнктивные и конъюнктивные нормальные формы. Алгоритм приведения формулы к днф и кнф.

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

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

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

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

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

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

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

1) Выразить все логические операции, через дизъюнкции, конъюнкции и отрицания: , .

2) закон де Моргана, сокращаем двойные отрицания.

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

Способы построения СДНФ и СКНФ.

СДНФ – дизъюнкция некоторых конституент единицы, среди которых нет одинаковых. СКНФ – конъюнкция некоторых коституент нуля, среди которых нет одинаковых.

Первая теорема Шеннона: Любая булева функция f(x₁,…,x_n) представима в виде разложения Шеннона:

Вторая теорема Шеннона: Любая булева функция f(x₁,…,x_n) представима в виде разложения Шеннона:

Теорема о функциональной полноте: Для любой булевой функции f найдется формула φ, представляющая функцию f. Если f≠0, то φ однозначно представима в виде СДНФ: . Если f≠1, то φ однозначно представима в виде СКНФ: .

Приведение КНФ к СКНФ:

1. Данную формулу приводим к КНФ

2. Если в дизъюнкт одна и та же литера x^δ входит несколько раз, то мы удаляем их все кроме одной

3. Если в некоторый дизъюнкт не входит переменная y, то заменяем его на эквивалентную формулу и применяем закон дистрибутивности

4. Если в полученном КНФ имеется несколько одинаковых конституент нуля, то оставляем только одну из них. В результате получается СКНФ.

16. Минимизация днф. Сокращенная, тупиковая, минимальная днф.

Элементарным произведением называется конъюнкт, в который любая переменная входит не более одного раза.

Формула φ(x₁,…,x_n) называется импликантой формулы ψ(x₁,…,x_n), если φ – элементарное произведение и , т.е для соответствующих формулам φ и ψ функций f_φ и f_ψ справедливо неравенство f_φ ≤f_ψ. Формула φ(x₁,…,x_n) называется импликантой функции f, если φ – импликанта СДНФ, представляющей f. Импликанта формулы ψ называется простой, если после отбрасывания любой литеры из φ не получается формула, являющаяся импликантой формулы ψ.

Дизъюнкция всех простых импликант данной формулы называется Сокращенной ДНФ.

Если из СкДНФ удалить все лишние импликанты, то получается Тупиковая ДНФ. Выбор из всех тупиковых форм формы с наименьшим числом вхождений переменных дает МинимальнуюДНФ

Способы построения СДНФ и СКНФ.

СДНФ – дизъюнкция некоторых конституент единицы, среди которых нет одинаковых. СКНФ – конъюнкция некоторых коституент нуля, среди которых нет одинаковых.

Метод Квайна для нахождения МДНФ,представляющей данную булеву функцию. Определим следующие три операции:

• Операцию полного склеивания

• Операцию неполного склеивания

• Операция элементарного поглащения

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

Приведение КНФ к СКНФ:

5. Данную формулу приводим к КНФ

6. Если в дизъюнкт одна и та же литера x^δ входит несколько раз, то мы удаляем их все кроме одной

7. Если в некоторый дизъюнкт не входит переменная y, то заменяем его на эквивалентную формулу и применяем закон дистрибутивности

8. Если в полученном КНФ имеется несколько одинаковых конституент нуля, то оставляем только одну из них. В результате получается СКНФ.