Автор Моряков Сергей задал вопрос в разделе Домашние задания
подскажите ход решения Найти КНФ для булевой функции: [ссылка появится после проверки модератором] и получил лучший ответ
Ответ от Дарья Чарикова[гуру]
все ДНФ и КНФ строятся по одному принципу.
шаг 1
Считаем, сколько переменных в нашей булевой функции (допустим их 3, х1,х2 и х3). Рисуем таблицу с числом строк 2 в третьей степени (или 2 в другой степени, если переменных не 3). В строках в первых трех столбцах перечисляем все возможные сочетания переменных, например:
000 - х1-ложь, х2-ложь, х3-ложь
001- х1-ложь, х2-ложь, х3 - истина
010 - х1-ложь, х2-ложь, х3 - истина
100 - и т. д. , принцип, думаю, ясен.
В последней строке пишем значение булевой функции на данном наборе переменных. Допустим при подстановке х1-ложь, х2-ложь, х3 - ложь булева функция истинна, при х1-ложь, х2 -ложь, х3 - истина функция ложна и т. д. (поясняю на примере "от балды", который придумываю на ходу)
000 -1
001 -1
010 -0
011 -1
100 -0
101 -0
110 -1
111 -0
шаг 2
"Сворачиваем" нашу таблицу. Получаем так называемую "Карту Карно".
Дальше применяем стандартную процедуру "склейки", знакомую вам по поиску ДНФ. Только в ДНФ склеивают единички, а при поиске КНФ склеивают нули. У нас получается 3 разные области (две склеенные и одиночный нолик). Если возможны несколько вариантов склейки, можно выбрать любой на свое усмотрение.
КНФ составляем по подобию ДНФ, только по склеенным нулям, а не единичкам и инвертируем каждую из переменных.
Допустим, в нашем случае:
КНФ = (!х1 + х2)*(!х3+!х1)*(х1+!х2+х3)
(первая скобка соответствует вертикальной склейке, вторая - горизонтальной склейке, третья - одиночному нолику)