Дизъюнктивная нормальная форма. Совершенная дизъюнктивная нормальная форма.

Определение 2. Конъюнкция

(4.1)

называется элементарной конъюнкцией или конъюнктом.

Так как существует всего 2ⁿ различных наборов значений переменной sÎ{0, 1}, то существует соответственно 2ⁿ различных элементарных конъюнкций от n переменных. При этом значение элементарной конъюнкции вида (4.1) равно 1 тогда и только тогда, когда x_i=s_i для всех i=1, 2, …, n.

Конъюнкция вида (4.1) называется также конституентой единицы.

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

Пример 4.1. Для формулы А= ®( у) имеем, например, ДНФА~хÚ( у), ДНФА~хÚу или ДНФА~хуÚх Ú у (проверьте!).

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

I шаг: Приведение операций |, ¯, ®, «, Å к операциям &, Ú или их отрицаниям:

1. Если в формуле участвуют операции |, ¯, и Å, то от них с помощью операции отрицания переходим к отрицанию соответственно конъюнкций, дизъюнкций или эквиваленций.

2. Если в формуле участвует операция «, то от неё с помощью закона т) упражнения 3.2 переходим к операции ®.

3. Если в формуле участвует операция ®, то от неё с помощью закона п) упражнения 3.2 преходим к операции Ú.

II шаг. Отнесение отрицаний к пропозициональным переменным.

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

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

III шаг. Получение ДНФ.

С помощью свойства дистрибутивности & относительно Ú все подформулы вида A(B₁ÚB₂Ú…ÚB_k) приводим к подформулам вида AB₁ÚAB₂Ú…ÚAB_k до тех пор, пока не получим дизъюнкцию элементарных конъюнкций.

Таким образом, мы доказали, что любая формула эквивалентна некоторой ДНФ.

Что касается того, что ДНФ формулы можно построить сколько угодно, то это становится очевидным, если увидеть, что АÚАÚ…ÚА~А, и поэтому в ДНФ элементарная конъюнкция может повторяться сколько угодно раз.

В приведённом примере третья ДНФ отличается от первой и второй тем, что она удовлетворяет следующим четырём свойствам совершенства:

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

2. Все конъюнкты, входящие в ДНФ, различны.

3. Ни один конъюнкт, из которых состоит ДНФ, не содержит одновременно переменную и её отрицание.

4. Ни один конъюнкт не содержит одну же литеру два и более раз.

Определение 4. ДНФ формулы, удовлетворяющей всем условиям совершенства, называется совершенной дизъюнктивной нормальной формой данной формулы (СДНФ).

Для того, чтобы получить СДНФ формулы А, достаточно сначала формулу привести к ДНФА, а затем применить к полученной ДНФ эквивалентные преобразования следующих видов, позволяющие последовательно получать эквивалентную ДНФА, удовлетворяющие всем условиям совершенства:

1. Если в ДНФА какой-либо конъюнкт В не содержит переменную х_i или её отрицание, то используя равносильности B~В&(х_iÚ )~ ~(В&х_i)Ú(B& ), конъюнкт В заменяем на два конъюнкта (В&х_i) и (B& ), каждая из которых содержит х_i или её отрицание .

2. Если в ДНФА входят два или более одинаковых конъюнкта B, то лишние отбрасываем, пользуясь равносильностью BÚBÚ…ÚB~B.

3. Если некоторый конъюнкт В, входящий в ДНФА, содержит переменную х_i и её отрицание , то В~0, и в силу эквивалентности CÚ0~C, В исключаем из ДНФА.

4. Если некоторый конъюнкт, входящий в ДНФА, содержит одну и ту же литеру дважды или более, то, пользуясь равносильностью & &…& ~ , лишние отбрасываем.

Упражнение 4.1. С помощью эквивалентных преобразований привести формулы упражнения 3.4 к СДНФ.

Решение. з) Приведём формулу к ДНФ:

(x| )®(zÅ ) ( )Ú(zÅ ) (x& )Ú

(x& )Ú (x& )Ú

(x& )Ú( (x& )Ú

Получили ДНФ формулы. Теперь преобразуем ДНФ по алгоритму получения всех условий совершенства:

(x& &z)Ú(x& & )Ú( &y&z)Ú( & &z)Ú(x& &z)Ú( & &z)Ú(x& & )

(x& &z)Ú(x& & )Ú( &y&z)Ú( & &z)Ú(x& & ).

á(1) Одновременно заменили | на отрицание операции &, и ® - на отрицание Ú.

(2) Одновременно применили закон двойного отрицания и Å заменили на « и его отрицание.

(3) Операцию « заменили на ®.

(4) Применили закон де Моргана.

(5) Заменили ® на Ú.

(6), (7) Одновременно применили законы де Моргана и снятия двойного отрицания.

(8) Воспользовались дистрибутивностью & относительно Ú.

(9) 1-й, 2-й и 3-й конъюнкты преобразовали, добавив недостающие переменные и их отрицания заменив каждый из них на два (шаг 1-й алгоритма приведения к СДНФ).

(10) 5-й и 6-й конъюнкты опустили, так как они уже участвуют в полученной ДНФ (шаг 2-го алгоритма).

СДНФ формулы существует и единственна.

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

Другой способ построения СДНФА основывается на следующей эквиваленции:

A(х₁, х₂, …, х_n)~ .

Другими словами, формула A(х₁, х₂, …, х_n) в своей СДНФ содержит те и только те конъюнкты вида (4.1), значения которых равны 1 при x_i=s_i для всех i=1, 2, …, n. Например, для формулы А= ®( у), состоящей из двух переменных, можно составить всевозможные конъюнкты ху, х , у и . Из них значение 1 принимают только ху, х , у соответственно при наборах (х, у)=(1, 1), (х, у)=(1, 0), (х, у)=(0, 1) (что можно проверить, непосредственно составив таблицу истинности). Поэтому, СДНФА~хуÚх Ú у.

Таким образом, СДНФA(х₁, х₂, …, х_n)= . Поэтому для нахождения СДНФ формулы достаточно: 1) построить её таблицу истинности; 2) выбрать те наборы значений переменных (которые входят в формулу), при которых формула принимает значение 1; 3) составить соответствующие им конъюнкты и 4) составить из них ДНФ.

Упражнение 4.2. С помощью таблиц истинности привести формулы упражнения 3.4 к СДНФ.

Решение. д). 1. Составим таблицу истинности формулы:

x	y	z	х®у	у®z	(х®у)&(у®z)	z®x	A(x, y, z)

2. Выберем те наборы значений переменных, при которых формула принимает значение 1: (0, 0, 0), (0, 1, 0), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1).

3. Составим соответствующие им конъюнкты: , y , x , x z, xy , xyz.

4. Составим из них ДНФ: Ú y Úx Úx zÚxy Úxyz.

Ответ: д) СДНФ A= Ú y Úx Úx zÚxy Úxyz.

Предыдущая 1 2 345 6 7 8 Следующая

Не нашли, что искали? Воспользуйтесь поиском по сайту:

©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.