Для функции f, заданной таблицей истинности построить СДНФ и СКНФ:
x1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
x2 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
x3 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
x4 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
f 1 1 0 0 0 0 0 0 0 1 1 0 1 1 1 1
Ответ
СДНФ: x1x2x3x4˅x1x2x3x4˅x1x2x3x4˅x1x2x3x4˅x1x2x3x4˅x1x2x3x4˅x1x2x3x4˅x1x2x3x4
СКНФ: x1˅x2˅x3˅x4∙x1˅x2˅x3˅x4∙x1˅x2˅x3˅x4∙x1˅x2˅x3˅x4∙x1˅x2˅x3˅x4∙x1˅x2˅x3˅x4∙∙x1˅x2˅x3˅x4∙x1˅x2˅x3˅x4
Решение
Построение СДНФ:
Наборы аргументов, для которых искомая функция принимает истинное значение:
0,0,0,0, 0,0,0,1, 1,0,0,1, 1,0,1,0, 1,1,0,0, 1,1,0,1,1,1,1,0, 1,1,1,1
Сопоставим этим наборам элементарные конъюнкции (если элемент в наборе равен 0, то соответствующий аргумент берется с отрицанием):
0,0,0,0=>x1x2x3x4
0,0,0,1=>x1x2x3x4
1,0,0,1=>x1x2x3x4
1,0,1,0=>x1x2x3x4
1,1,0,0=>x1x2x3x4
1,1,0,1=>x1x2x3x4
1,1,1,0=>x1x2x3x4
1,1,1,1=>x1x2x3x4
Объединим полученные элементарные конъюнкции с помощью дизъюнкций и получим СДНФ:
x1x2x3x4˅x1x2x3x4˅x1x2x3x4˅x1x2x3x4˅x1x2x3x4˅x1x2x3x4˅x1x2x3x4˅x1x2x3x4
2) Построение СКНФ:
Наборы аргументов, для которых искомая функция принимает ложное значение:
0,0,1,0, 0,0,1,1, 0,1,0,0, 0,1,0,1, 0,1,1,0, 0,1,1,1,1,0,0,0, 1,0,1,1
Сопоставим этим наборам элементарные дизъюнкции (если элемент в наборе равен 1, то соответствующий аргумент берется с отрицанием):
0,0,1,0=>x1˅x2˅x3˅x4
0,0,1,1=>x1˅x2˅x3˅x4
0,1,0,0=>x1˅x2˅x3˅x4
0,1,0,1=>x1˅x2˅x3˅x4
0,1,1,0=>x1˅x2˅x3˅x4
0,1,1,1=>x1˅x2˅x3˅x4
1,0,0,0=>x1˅x2˅x3˅x4
1,0,1,1=>x1˅x2˅x3˅x4
Объединим полученные элементарные дизъюнкции с помощью конъюнкций и получим СКНФ:
x1˅x2˅x3˅x4∙x1˅x2˅x3˅x4∙x1˅x2˅x3˅x4∙x1˅x2˅x3˅x4∙x1˅x2˅x3˅x4∙x1˅x2˅x3˅x4∙∙x1˅x2˅x3˅x4∙x1˅x2˅x3˅x4
Ответ: СДНФ: x1x2x3x4˅x1x2x3x4˅x1x2x3x4˅x1x2x3x4˅x1x2x3x4˅x1x2x3x4˅x1x2x3x4˅x1x2x3x4
СКНФ: x1˅x2˅x3˅x4∙x1˅x2˅x3˅x4∙x1˅x2˅x3˅x4∙x1˅x2˅x3˅x4∙x1˅x2˅x3˅x4∙x1˅x2˅x3˅x4∙∙x1˅x2˅x3˅x4∙x1˅x2˅x3˅x4