Для функции 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
Ответ
МДНФ: x1x2x3˅x1x3x4˅x1x3x4˅x1x2
МКНФ: (x1˅x3)∙(x2˅x3˅x4)∙(x1˅x2)∙(x1˅x2˅x3˅x4)
Решение
Т.к. таблица истинности совпадает с таблице истинности в предыдущем номере, следовательно, можно воспользоваться полученными для нее СДНФ и СКНФ.
1) Построение МДНФ методом Квайна
Из предыдущего номера СДНФ:
x1x2x3x4˅x1x2x3x4˅x1x2x3x4˅x1x2x3x4˅x1x2x3x4˅x1x2x3x4˅x1x2x3x4˅x1x2x3x4
Выполним операцию склеивания:Первый этап склейки:
№ Элементарная конъюнкция Возможные склейки
1 x1x2x3x4
1-2=>x1x2x3
-
2 x1x2x3x4
2-3=>x2x3x4
-
3 x1x2x3x4
3-6=>x1x3x4
-
4 x1x2x3x4
4-7=>x1x3x4
-
5 x1x2x3x4
5-6=>x1x2x3
5-7=>x1x2x4
6 x1x2x3x4
6-8=>x1x2x4
-
7 x1x2x3x4
7-8=>x1x2x3
-
8 x1x2x3x4
8-7 -
Второй этап склейки:
№ Элементарная конъюнкция Возможные склейки
1 x1x2x3
- -
2 x2x3x4
- -
3 x1x3x4
- -
4 x1x3x4
- -
5 x1x2x3
5-8=>x1x2
-
6 x1x2x4
6-7=>x1x2
-
7 x1x2x4
7-6 -
8 x1x2x3
8-5 -
Итого получено 5 склеек: x1x2x3, x2x3x4, x1x3x4, x1x3x4, x1x2
Выполним операцию поглощения:
x1x2x3x4
x1x2x3x4
x1x2x3x4
x1x2x3x4
x1x2x3x4
x1x2x3x4
x1x2x3x4
x1x2x3x4
x1x2x3
+ +
x2x3x4
+ +
x1x3x4
+
+
x1x3x4
+
+
x1x2
+ + + +
Полученная МДНФ: x1x2x3˅x1x3x4˅x1x3x4˅x1x2
2) Получение МКНФ:
Из предыдущего номера СКНФ:
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
Выполним операцию склеивания:Первый этап склейки:
№ Элементарная конъюнкция Возможные склейки
1 x1˅x2˅x3˅x4
1-2=>x1˅x2˅x3
1-5=>x1˅x3˅x4
2 x1˅x2˅x3˅x4
2-6=>x1˅x3˅x4
2-8=>x2˅x3˅x4
3 x1˅x2˅x3˅x4
3-4=>x1˅x2˅x3
3-5=>x1˅x2˅x4
4 x1˅x2˅x3˅x4
4-6=>x1˅x2˅x4
-
5 x1˅x2˅x3˅x4
5-6=>x1˅x2˅x3
-
6 x1˅x2˅x3˅x4
- -
7 x1˅x2˅x3˅x4
- -
8 x1˅x2˅x3˅x4
- -
Второй этап склейки:
№ Элементарная конъюнкция Возможные склейки
1 x1˅x2˅x3
1-8=>x1˅x3
-
2 x1˅x3˅x4
2-3=>x1˅x3
-
3 x1˅x3˅x4
- -
4 x2˅x3˅x4
- -
5 x1˅x2˅x3
5-8=>x1˅x2
-
6 x1˅x2˅x4
6-7=>x1˅x2
-
7 x1˅x2˅x4
7-6 -
8 x1˅x2˅x3
8-5 -
9 x1˅x2˅x3˅x4
- -
Итого получено 5 склеек: x1˅x3, x1˅x3˅x4, x2˅x3˅x4, x1˅x2, 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
x1˅x3
+ +
+ +
x1˅x3˅x4
+
+
x2˅x3˅x4
+
+
x1˅x2
+ + + +
x1˅x2˅x3˅x4
+
Полученная МКНФ: (x1˅x3)∙(x2˅x3˅x4)∙(x1˅x2)∙(x1˅x2˅x3˅x4)
Ответ: МДНФ: x1x2x3˅x1x3x4˅x1x3x4˅x1x2
МКНФ: (x1˅x3)∙(x2˅x3˅x4)∙(x1˅x2)∙(x1˅x2˅x3˅x4)