Совершенная дизъюнктивная нормальная форма

Введем обозначения: если во входном наборе а = 1, то будем писать «а», если в наборе а = 0, то пишем « ». Для других переменных аналогично.

Рассмотрим строки табл. 12, в которых функция y = 1.

Строка №3: y = 1, если a = 1 и b = 1, и c = 0.

Используя введенные обозначения переменных и заменив союз И символом конъюнкции, это условие для строки №3 можно записать так:

y = 1, если входной набор равен b a или просто ba.

В строке №5 y = 1 при входном наборе c a.

В строке №6 y = 1 при входном наборе cb .

В строке №7 y = 1 при входном наборе cba.

Итак, y = 1 при наборе ba, или при наборе c a, или при наборе cb , или при наборе cba, что можно записать, заменив союз ИЛИ символом дизъюнкции, так

y = ba c a cb cba = 1.

Единицу обычно не пишут (но всегда подразумевают), поэтому окончательно получаем:

y = ba c a cb cba .

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

СДНФ для каждой логической функции единственна.

Понятия «минтерм» и «конституента единицы» будут пояснены в п. 2.3.4.

Полученная форма называется

совершенной, так как все конъюнкции содержат все переменные (с отрицанием или без отрицания), т.е. имеют максимальный ранг;

дизъюнктивной, потому что формула представляет собой дизъюнкцию конъюнкций;

нормальной, так как все конъюнкции являются элементарными.

Если в конъюнкцию входят только переменные или их отрицания, то конъюнкция называется элементарной. Число переменных в конъюнкции называется ее рангом. В нашем случае ранг конъюнкций равен 3.

Выводы:

Никаких ограничений на число «1» и число «0» в описанной процедуре не накладывается, поэтому подход можно применить для любой функции, с любым числом переменных;

При составлении формул мы использовали символы логических операций НЕ, И, ИЛИ, и, следовательно, с помощью этих операций можно составить формулу для любой логической функции;

Совокупность логических операций, позволяющая составить формулу для любой логической функции, называется функционально полной системой операций (функций) или базисом.