Теорема 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) написать логическое произведение составленных логических сумм. Полученное произведение и является СКНФ. В общем виде:
где Fi – сложные дизъюнкции.
Это правило также называют правилом построения переключательной функции по нулям.
Кроме представления функций в виде СДНФ и СКНФ используют и совершенную полиномиальную нормальную форму СПНФ. Вместо дизъюнкции может быть записана функция сложения по модулю два (сумма Жегалкина):
, (6)где Fi – сложные конъюнкции.
Существует специальная таблица, в которой все элементарные логические операции от двух аргументов представлены в двух совершенных нормальных формах.
Нормальные формы представления переключательной функции иногда называют стандартными (табл. 5).
Таблица 5
f | A0011B0101 | Название функции | Обозначение функции | СДНФ | СКНФ |
f0 | 0000 | Константа нуль | 0 | Не имеет | |
f1 | 0001 | Логическое произведение, конъюнкция | |||
f2 | 0010 | Функция запрета по В | |||
f3 | 0011 | Переменная А | |||
f4 | 0100 | Функция запрета по А | |||
f5 | 0101 | Переменная В | |||
f6 | 0110 | Сумма по мо дулю 2, логическая неравнозначность | |||
f7 | 0111 | Логическое сложение, дизъюнкция | |||
f8 | 1000 | Операция (стрелка) Пирса, операция Вебба | |||
f9 | 1001 | Эквивалентность, логическая равнозначность | |||
f10 | 1010 | Инверсия В | |||
f11 | 1011 | Импликация от В к А | |||
f12 | 1100 | Инверсия А | |||
f13 | 1101 | Импликация от А к В | |||
f14 | 1110 | Операция (штрих) Шеффера | |||
f15 | 1111 | Константа единица | 1 | Не имеет |
Многочленом Жегалкина называется многочлен, являющийся суммой константы 0 или 1 и различных одночленов, в которые все переменные входят не выше, чем в первой степени.
Теорема. Любая функция булевой алгебры может быть представлена, и притом единственным образом, с помощью полинома Жегалкина вида