y9=x4/y6 =ùx4+x1x2
y10=x4ù→y7=x4(ùx1+ùx2+ùx3+ùx4)= ùx1x4+ùx2x4+ùx3x4
y11=x1~y8~y10=( ùx1(ùx1+x2)( ùx1+x3)( ùx1+x4)(x1+ùx2)( ùx2+x3)( ùx2+x4)+
+x1(x1ùx2+x1ùx3+x1ùx4+ùx1x2+x2ùx3+x2ùx4)) ~y10=((ùx1+ùx1x2) (ùx1+x3) (ùx1+x4)(x1+ùx2)( ùx2+x3)( ùx2+x4)+(x1ùx2+x1ùx3+x1ùx4+x1x2ùx3+x1x2ùx4)) ~y10=(ùx1ùx2(ùx1+x3)( ùx2+x3)( ùx2+x4)( ùx1+x4)+ (x1ùx2+x1ùx3+x1ùx4+ +x1x2ùx3+x1x2ùx4)) ~y10=((ùx1ùx2+ùx1ùx2x3) (ùx2+x3)( ùx2+x4)( ùx1+x4)+
+(x1ùx2+x1ùx3+x1ùx4+ +x1x2ùx3+x1x2ùx4)) ~y10=((ùx1ùx2+ùx1ùx2x3)
( ùx2+x4)( ùx1+x4)+ (x1ùx2+x1ùx3+x1ùx4+ x1x2ùx3+x1x2ùx4)) ~y10=
=((ùx1ùx2+ùx1ùx2x4+ùx1ùx2x3+ùx1ùx2x3x4)( ùx1+x4)+( x1ùx2+x1ùx3+
+ x1ùx4+ x1x2ùx3+x1x2ùx4)) ~y10=(ùx1ùx2+ùx1ùx2x4+ùx1ùx2x3x4+
+ x1ùx2+x1ùx3+ x1ùx4+ x1x2ùx3+x1x2ùx4)~y10=(ùx1ùx2+x1ùx2+x1ùx3+
+x1ùx4+x1x2ùx3+x1x2ùx4) ~y10=(ùx2+x1ùx3+x1ùx4+x1x2ùx3+x1x2ùx4) ~y10=
=(ùx2+x1ùx3+x1ùx4)~y10=x2(ùx1+x3)( ùx1+x4)(x1+ùx4)(x2+ùx4)(x3+ùx4)+
+(ùx2+x1ùx3+x1ùx4)( ùx1x4+ùx2x4+ùx3x4)=x2(ùx1+x3)( ùx1ùx4+x1x4)
(x2+ùx4)(x3+ùx4) +(ùx2+x1ùx3+x1ùx4)( ùx1x4+ùx2x4+ùx3x4)=
=x2(ùx1+x3)( ùx1x2ùx4+x1x2x4+ùx1ùx4)(x3+ùx4) +(ùx2+x1ùx3+x1ùx4)
( ùx1x4+ùx2x4+ùx3x4)=x2(ùx1+x3)( ùx1x2x3ùx4+x1x2x3x4+ùx1x2x4+
+ùx1x2ùx4) +(ùx2+x1ùx3+x1ùx4)( ùx1x4+ùx2x4+ùx3x4)=( ùx1+x3)( ùx1x2x4+
+x1x2x3x4+ùx1x2x3x4) +(ùx2+x1ùx3+x1ùx4)( ùx1x4+ùx2x4+ùx3x4)=
=(ùx1+x3) (ùx1x2x4+x1x2x3x4) +(ùx2+x1ùx3+x1ùx4)( ùx1x4+ùx2x4+ùx3x4)=
=ùx1x2x4+ùx1x2x3x4+x1x2x3x4+ùx1ùx2x4+ùx2x4+ùx2ùx3x4+x1ùx2ùx3x4+
+x1ùx3x4=ùx1x2x3+x1x2x3x4+ùx2x4+x1ùx3x4
y12=x1/y9 =ùx1+x4(ùx1+ùx2)= ùx1+ùx1x4+ùx2x4=x1+ùx2x4
y13= y9ù→y10=(ùx4+x1x2)(x1+ùx4)(x2+ùx4)(x3+ùx4)=(x1ùx4+ùx4+x1x2+
+x1x2ùx4)(x2+ùx4)(x3+ùx4)=( ùx4+x1x2)(x2+ùx4)(x3+ùx4)=(x2ùx4+ùx4+
+x1x2+x1x2ùx4)(x3+ùx4)=( ùx4+x1x2)(x3+ùx4)=x3ùx4+ùx4+x1x2x3+
+x1x2ùx4=ùx4+x1x2x3
y14=y9~y11 =x4(ùx1+ùx2)(x1+ùx2+ùx4)( ùx1+ùx2+ùx3+ùx4)(x2+ùx4)
(ùx1+x3+ùx4)+( ùx4+x1x2)( ùx1x2x4+x1x2x3x4+ùx2x4+x1ùx3x4)=
=x4(ùx1ùx2+ùx1ùx4+x1ùx2+ùx2)( ùx1+ùx2+ùx3+ùx4)(x2+ùx4)( ùx1+x3+ùx4)+
+( ùx4+x1x2)( ùx1x2x4+x1x2x3x4+ùx2x4+x1ùx3x4)=x4(ùx2+ùx1ùx4)( ùx1+ùx2+
+ùx3+ùx4)( ùx1x2+x2x3+x2ùx4+ùx1ùx4+ùx3ùx4+ùx4) +( ùx4+x1x2)( ùx1x2x4+
+ x1x2x3x4+ùx2x4+x1ùx3x4)= ùx2x4(ùx1+ùx2+ùx3+ùx4)( ùx1x2+x2x3+ùx4)+
+( ùx4+x1x2)( ùx1x2x4+x1x2x3x4+ùx2x4+x1ùx3x4)=( ùx1ùx2x4+ùx2x4+
+ùx2ùx3x4)( ùx1x2+x2x3+ùx4)+ ( ùx4+x1x2) (ùx1x2x4+x1x2x3x4+ùx2x4+
+x1ùx3x4)= ùx2x4(ùx1x2+x2x3+ùx4) +( ùx4+x1x2)( ùx1x2x4 +x1x2x3x4+ùx2x4+
x1ùx3x4)=( ùx4+x1x2)( ùx1x2x4+x1x2x3x4+ùx2x4+x1ùx3x4)=x1x2x3x4+
+x1x2ùx3x4=x1x2x4
y15=y10/y12/y14=((x1+ùx4)(x2+ùx4)(x3+ùx4)+x1(x2+ùx4))/y14=
=((x1x2+x1ùx4+x2ùx4+ùx4)+x1x2+x1ùx4)/y14=((x1x2x3+x1x2ùx4+x3ùx4+ùx4)+
+x1x2+x1ùx4)/y14=(x1x2+ùx4)/y14=(ùx1+ùx2)x4+(ùx1+ùx2+ùx4)=
=ùx1x4+ùx2x4+ùx1+ùx2+ùx4=ùx1+ùx2+ùx4
y16=y10ù→y13=(ùx1x4+ùx2x4+ùx3x4)x4(ùx1+ùx2+ùx3)= ùx1x4+ùx1ùx2x4+
+ùx1ùx3x4+ùx2x4+ùx1ùx2x4+ùx1ùx3x4+ùx3x4+ùx1ùx3x4+ùx2ùx3x4=
=ùx1x4+ùx2x4+ùx3x4
y17=y11~y14=(x1+ùx2+x4)( ùx1+ùx2+ùx3+ùx4)(x2+ùx4)( ùx1+x3+ùx4)
(ùx1+ùx2+ùx4)+( ùx1x2x4+x1x2x3x4+ùx2x4+x1ùx3x4)x1x2x4=
=(x1ùx2+x1ùx3+x1ùx4+ùx1ùx2+ùx2+ùx2ùx3+ùx2ùx4+ùx1x4+ùx2x4+ùx3x4)
(ùx1x2+x2x3+x2ùx4+ùx1ùx4+x3ùx4+ùx4)+x1x2x3x4+x1x2ùx3x4=
=ùx2ùx4+x1ùx3ùx4+x1x2x3ùx4+x1ùx4+ùx1x2x4+ùx1x2x3x4+ùx1x2ùx3x4+
+x1x2x3x4+x1x2ùx3x4=ùx2ùx4+x1ùx4+ùx1x2x4+ùx1x2x3x4+ùx1x2ùx3x4+
+x2x4=ùx2ùx4+x1ùx4+x2x4
y18=y15/y17=x1x2x4+(x2+x4)( ùx1+x4)( ùx2+ùx4)=x1x2x4+(ùx1x2+x2x4+
+ùx1x4+x4)( ùx2+ùx4)=x1x2x4+(ùx1x2+x4)( ùx2+ùx4)=x1x2x4+ùx1x2ùx4+
+ùx2x4=ùx1x2ùx4+x1x4+ùx2x4
y19=y16ù→y18 =(ùx1x4+ùx2x4+ùx3x4)( ùx1+ùx2+ùx4)(x1+ùx2+x4)(x2+ùx4)=
=(ùx1x4+ùx2x4+ùx3x4)( ùx1+ùx2+ùx4)(x1x2+x1ùx4+ùx2ùx4+x2x4)=
=(ùx1x4+ùx2x4+ùx3x4)( ùx1ùx2ùx4+ùx1x2x4+x1ùx2ùx4+ùx2ùx4+x1x2ùx4+
+x1ùx4+ùx2ùx4)= (ùx1x4+ùx2x4+ùx3x4)( ùx1x2x4+ùx2ùx4+x1ùx4)=
=ùx1x2x4+ùx1x2ùx3x4=ùx1x2x4
y20=y18=ùx1x2ùx4+x1x4+ùx2x4
Теперь выполним построение сводной таблицы. В левой части таблицы приводятся все возможные наборы из четырех аргументов – от нулевого до пятнадцатого, а в правой – значения функции для каждого элемента логической схемы.
| x1 | x2 | x3 | x4 | y5 | y6 | y7 | y8 | y9 | y10 | y11 | y12 | y13 | y14 | y15 | y16 | y17 | y18 | y19 | y20 |
| 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 |
Формула ùx1x2ùx4+x1x4+ùx2x4 , полученная для всей таблицы, записана в виде ДНФ. Для перевода ее в СДНФ, введем единицы для недостающих элементов в каждый минитерм:
СДНФ=(x3+ùx3)(x2+ùx2) x1x4+(x3+ùx3) ùx1x2ùx4+(x3+ùx3)(x1+ùx1)ùx2x4=
=x1x2x3x4+x1x2ùx3x4+ùx1x2x3ùx4+ùx1x2ùx3ùx4+x1ùx2x3x4+x1ùx2ùx3x4+
+ùx1ùx2x3x4+ùx1ùx2ùx3x4
Выполним перевод из CДНФ в CКНФ:
CКНФ=(ù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)
Задание № 4
Рассмотрим функцию четырех переменных Q=f(x1,x2,x3,x4) заданную таблицей 2.
Ей соответствует дизъюнктивная совершенная нормальная форма
x1x2x3x4+x1x2ùx3x4+ùx1x2x3ùx4+ùx1x2ùx3ùx4+x1ùx2x3x4+x1ùx2ùx3x4+
+ùx1ùx2x3x4+ùx1ùx2ùx3x4
Множество 0-Кубов после разбиения и упорядочивания записывается следующим образом:
| 00010100 |
| 011010010011 |
| 11011011 |
| 1111 |
K0=
Будем попарно сравнивать S-кубы из соседних поясов, склеивая таковые, отличающиеся только по одной координате. Такая операция склеивания соответствует объединению двух S-кубов. Получим (S+1)-куб, в котором склеиваемую координату заместим символом «~». Склеиваемые кубы будем отмечать знаком «-».
| 0001-0100- |
| 0110-1001-0011- |
| 1101-1011- |
| 1111- |
K’0=
| ~001-00~1-01~0 |
| 1~01-10~1-~011- |
| 11~1-1~11- |
K1 =
K
| ~0~1 |
| 1~~1 |
K2 =
K3=Æ
Очевидно, во множестве K2 склеивание S-кубов невозможно. Поэтому следующее множество K3 – пустое. Полученная сокращенная форма содержит четыре простые импликанты (неотмеченные кубы, то есть те, которые не склеились в процессе сравнения).
Теперь построим таблицу Квайна. Ее строкам соответствуют простые импликанты из сокращенной формы, столбцам – конституэнты булевой функции.
| 0001 | 0100 | 0110 | 1001 | 0011 | 1101 | 1011 | 1111 |
| 01~0 | a | - | - | ||||
| ~0~1 | b | - | - | - | - | ||
| 1~~1 | c | - | - | - | - |
Очевидно, каждая импликанта является существенной. В этом случае тупиковая форма единственна. Она же будет являться и минимальной формой.
МДНФ=ùx1x2ùx4+x1x4+ùx2x4
Полученная формула в точности равна полученной еще на этапе анализа логической схемы. Действительно, при анализе мы пользовались аналитической минимизацией, применяя те ли иные свойства. Универсальный метод Квайна-Мак-Класки показал, что полученная ДНФ действительно является минимальной.
Полученный вывод можно подтвердить также с помощью метода Петрика. Логическое условие покрытия всей таблицы Квайна имеет вид:
bÙaÙaÙ(bÚc)ÙbÙcÙ(bÚc)Ùc
Производя простые преобразования, получаем:
aÚbÚc
Таким образом, с помощью метода Петрика получаем следующее выражение для МДНФ: