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