Учебное пособие: Дискретная математика
Дизъюнктивной нормальной формой (ДНФ) данной формулы называется формула, равносильная данной и представленная в виде дизъюнкции основных конъюнкций. Например, AB + C + AC .
Теорема 1. Для того чтобы формула алгебры высказываний была тождественно истинной, необходимо и достаточно, чтобы ее КНФ содержала в каждой элементарной дизъюнкции некоторое высказывание и его отрицание.
Теорема 2. Для того чтобы формула алгебры высказываний была тождественно ложной, необходимо и достаточно, чтобы ее ДНФ содержала в каждой элементарной конъюнкции некоторое высказывание и его отрицание.
Совершенные дизъюнктивные, конъюнктивные и полиномиальные нормальные формы представления переключательных (логических) функций. Многообразие формул, посредством которых может быть выражена любая логическая функция, определяет многообразие форм логических функций, т. е. способов их записи путем применения к переменным и их группам элементарных логических операций. Наиболее удобными для практического использования оказываются совершенные нормальные формы представления сложных логических функций. В алгебре логики доказывают, что любая логическая функция F ( A , B , C ,…, N ) может быть представлена только одной совершенной дизъюнктивной нормальной формой (кроме константы нуль) или только одной совершенной конъюнктивной нормальной формой (кроме константы единица).
Пусть функция X = F ( A , B , C ) задана таблицей 4. Запись функции Х в виде логической суммы (дизъюнкции) логических произведений (конъюнкций) переменных, для которых значение функции Х равно 1, и является совершенной дизъюнктивной нормальной формой (СДНФ) представления логической функции.
Таблица 4
| A | B | C | X |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
СДНФ логической функции следует находить в такой последовательности:
1) составить произведения переменных для строк таблицы истинности, в которых Х равна 1. Если значение переменной (А, В или С ) в строке равно 0, то в произведении записывается отрицание этой переменной;
2) написать сумму произведений, для которых функция Х равна 1. Полученная сумма и является СДНФ. В общем виде
, (1)
Это правило называют правилом записи переключательной функции по единицам. Согласно этому правилу, данные табл. 4 описываются аналитическим выражением, связывающим все наборы переменных, для которых Х =1, в виде:
. (2)
Запись функции Х в виде логического произведения (конъюнкции) логических сумм (дизъюнкций) переменных, для которых функция Х равна 0, является совершенной конъюнктивной нормальной формой (СКНФ) представления логической функции.
Для табл. 4 аналитическое выражение в СДНФ, связывающее все наборы переменных, для которых Х =0, имеет вид:
. (3)
Для представления логической функции Х в СКНФ произведем операцию отрицания левой и правой частей равенства (3)
и на основании законов двойного отрицания и инверсии
. (4)
СКНФ логической функции, согласно (4), следует находить в такой последовательности:
1) составить логические суммы переменных для строк таблицы истинности, в которых функция Х равна 0. Если значение переменной (А, В или С ) в строке равно 1, то в сумме записывается отрицание этой переменной;
2) написать логическое произведение составленных логических сумм. Полученное произведение и является СКНФ. В общем виде:
, (5)
где Fi – сложные дизъюнкции.
Это правило также называют правилом построения переключательной функции по нулям.
Кроме представления функций в виде СДНФ и СКНФ используют и совершенную полиномиальную нормальную форму СПНФ. Вместо дизъюнкции может быть записана функция сложения по модулю два (сумма Жегалкина):
, (6)
где Fi – сложные конъюнкции.