Контрольная работа: Основы дискретной математики
=(ù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
Минимизация методами Квайна-МакКласки и Петрика, а также с помощью карт Карно булевой функции по исходной таблице истинности, полученной в п.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-Кубов после разбиения и упорядочивания записывается следующим образом:
|
0001 0100 |
|
0110 1001 0011 |
|
1101 1011 |
| 1111 |
K0 =
Будем попарно сравнивать S-кубы из соседних поясов, склеивая таковые, отличающиеся только по одной координате. Такая операция склеивания соответствует объединению двух S-кубов. Получим (S+1)-куб, в котором склеиваемую координату заместим символом «~». Склеиваемые кубы будем отмечать знаком «-».
|
0001- К-во Просмотров: 325
Бесплатно скачать Контрольная работа: Основы дискретной математики
|