Табличное представление логических функций является весьма наглядным. Однако при большом числе n переменных (аргументов) оно становится очень громоздким и практически необозримым. Если для n = 2 число различных логических функций равно 16, то для n = 3 это число возрастает до 256.
Значительно проще выглядит аналитическая запись логических функций в виде формул.
Широкое распространение получили так называемые нормальные формы представления логических функций. В их основе лежат понятия элементарных дизъюнкций и конъюнкций.
Элементарная дизъюнкция представляет собой дизъюнкцию конечного числа переменных и их отрицаний (инверсий), например, х1 ? x2, x1 ? x2, x1 ? x2 и др. Конъюнкция элементарных дизъюнкций называется конъюнктивной нормальной формой (КНФ), например,
FКНФ = (x ? y) & (x ? y).
110
Элементарная конъюнкция представляет собой конъюнкцию конечного числа переменных и их отрицаний (инверсий), например, х1 & х2, х1 & х2, х1 & х2 и др. Дизъюнкция элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ), например,
PДНФ = х & y ? х & y.
Одну и ту же логическую функцию можно представить различными ДНФ и КНФ. Однозначность представления логических функций возможна при записи их в совершенных нормальных формах.
Дизъюнктивная совершенная нормальная форма (ДСНФ) образуется дизъюнкцией так называемых конституент 1 или минтермов. При этом минтермы представляют собой элементарные конъюнкции переменных на тех наборах, на которых функция равна 1. Те переменные, которые в данном наборе равны 0, записываются в минтерме с отрицанием (инверсией), а равные 1 - без отрицания (инверсии).
Таким образом, для образования ДСНФ логической функции, заданной таблично, необходимо выполнить следующую последовательность действий: