Дизъюнктивные нормальныеформы

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

Под элементарным понимается такое произведение, в котором сомножителями являются только отдельные переменные или их отрицания. Например, формула f(x1,

x2, x3)=

х2×х3Úх1×х2

содержит два элементарных произведения, каждое из кото-

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

 

 

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

СДНФ определяется как сумма элементарных произведений, в которых каждая переменная встречается ровно один раз либо с отрицанием, либо без него.

Для преобразования функции (2.2) в СДНФ необходимо дополнить каждое элементарное произведение недостающими переменными так, чтобы тождествен- ность преобразования не была нарушена:

f(xl, x2, x3) =

х2×х3Úх1×х2

= (х1 Ú х1) × х 2 × х 3 Ú х1 × х 2 × (х 3 Ú х 3).

После раскрытия скобок и приведения подобных членов, получим функцию, записанную в СДНФ:

f(xl,x2,x3)=х1×х2×х3Úх1×х2×х3Úх1×х2×х3Úх1×х2×х3)=

= х1 × х 2 × х 3 Ú х1 × х 2 × х 3 Ú х1 × х 2 × х 3.

(2.3)

Здесь каждая переменная (или ее отрицание) содержится по одному разу в каж- дом элементарном произведении. Функция (2.3) обращается в логическую единицу при трех различных комбинациях значений входных переменных:

х1 = 1, х2 = 0, х3 = 1 – первая комбинация; х1 = 0, х2 = 0, х3 = 1 – вторая комбинация; х1 = 1, х2 = 0, х3 = 0 – третья комбинация.

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

Таблица истинности такой функции (таблица 2.3) содержит три строки, в кото- рых функция равна 1.

Таблица 2.3

 

Xl	х2	x3	f(xl, x2, x3)
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	0

 

 

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

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

Применив это правило, мы получим

f(xl, x2, x3) = х1 × х 2 × х 3 Ú х1 × х 2 × х 3 Ú х1 × х 2 × х 3.