Найти минимальные формы методом Квайна и построить для них таблицу истинности.
Решение
Для удобства, каждую единицу булевой функции представим в виде двоичного набора длины n. Все такие наборы группируем по числу единичных компонент в наборе. Все наборы, содержащие k единиц, образуют одну группу. Наборы размещаются в порядке возрастания единиц в наборе. Ясно, что склеиваться будут только наборы из соседних групп.
В результате склеивания получают конъюнкцию, в которой отсутствует одна из переменных
. На месте отсутствующей переменной будем ставить прочерк. В процессе склеивания помечаем звездочкой соответствующие наборы. Повторно склеенные конъюнкции не записываем.
Составим таблицу склеиваний:
0010* 001-*
0-10*
-010* 0-1-
-01-
--11
1--1
0011*
0110*
1001*
1010* 0-11*
-011*
011-*
10-1*
1-01*
101-*
0111*
1011*
1101* -111*
1-11*
11-1*
1111*
Получены следующие простые импликанты: xz, yz, zp, xp.
Строим матрицу покрытий единиц заданной булевой функции простыми ипликантами.
0010 0011 0110 0111 1001 1010 1011 1101 1111
xz