Информатика и вычислительная техника
или макстермов. При этом
Конъюнктивная совершенная нормальная форма (КСНФ) образуется
конъюнкцией так называемых конституент 0 или макстермов. При этом макстермы представляют собой элементарные дизъюнкции переменных на тех наборах, на которых функция равна 0. Те переменные, которые в данном наборе равны 1 , записываются в макстерме с отрицанием (инверсией), а равные 0 - без отрицания (инверсии).
Таким образом, для образования КСНФ логической функции, заданной таблично, необходимо выполнить следующую последовательность действий:
1) по каждому набору двоичных переменных, при котором данная функция принимает значение 0, составить элементарные дизъюнкции;
2) в элементарные дизъюнкции записать без инверсии переменные, заданные нулем в соответствующем наборе, а с инверсией - переменные, заданные единицей;
3) элементарные дизъюнкции соединить знаком конъюнкции.
Любая логическая функция, кроме функции, тождественно равной 0 (f ? 0), представима в ДСНФ, а любая функция, кроме f = 1 , представима в КСНФ.
111
Дизъюнкцией минтермов или конъюнкцией макстермов можно компактно представить, соответственно, в ДСНФ или КСНФ все 16 логических функций двух аргументов, как показано в табл. 5.2.
Таблица 5.2
ДСНФ и КСНФ логических функций двух аргументов
Таким образом, с использованием ДСНФ и КСНФ любая логическая функция представляется аналитическим выражением, в котором участвуют аргументы, связанные логическими операциями отрицания, дизъюнкции и конъюнкции.
112
110 :: 111 :: 112 :: Содержание
