курсовые,контрольные,дипломы,рефераты
ОДЕССКИЙ НАЦИОНАЛЬНЫЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
РАСЧЕТНО-ГРАФИЧЕСКАЯ РАБОТА
по дисциплине
«Основы дискретной математики»
Выполнил
студент группы АЕ-074
Ф.И.О.
Проверил
доцент кафедры КИСС
Мартынюк А. Н.
Введение
Данная расчетно-графическая работа по дисциплине «Основы дискретной математики» включает в себя:
· задачу минимизации заданного выражения алгебры множеств на основании известных свойств;
· анализ заданного бинарного отношения в общем виде, построение его графика и полное определение свойств отношения, включая свойства, унаследованных им от соответствий;
· анализ заданной в определенном функциональном базисе логической схемы: вывод формул булевых функций для каждого элемента и схемы в целом, с одновременной их минимизацией на основании известных свойств и тождеств, а также построение таблиц истинности;
· преобразование формулы булевой функции заданной логической схемы в КНФ, ДНФ, СКНФ и СДНФ, а также ее минимизацию методами Квайна-МакКласки, Петрика, и с помощью карт Карно;
· пополнение булевой функции заданными безразличными входными наборами и минимизацию пополненной функции с помощью карт Карно, а также методов Квайна-МакКласки и Петрика;
· перевод полученных минимизированных формул из булева базиса в заданный функциональный базис и синтез соответствующих логических схем.
Задание № 1
Упрощение заданного выражения алгебры множеств
1.1 Выбор варианта задания
Варианты РГР образуются заданием индивидуальных:
· выражения алгебры множеств;
· бинарного отношения;
· исходной логической схемы;
· безразличных входных наборов.
В основе выбора варианта лежит процедура определения целочисленного остатка от деления выражения, в котором присутствует число. (Вариант 9)
Таблицы – см. литература 1.
Выбор варианта выражения алгебры множеств.
«№ операций» = 9mod7+1=3
| № операции | a | b | g | d | l |
| Вариант 3 | Ø | \ | Ç | - | È |
«№ операндов»=9mod5+1=5
| № операнда | оп-д1 | оп-д2 | оп-д3 | оп-д4 | оп-д5 |
| Вариант 5 | AdF | BbA | EdB | aE | AgB |
Результаты подставляются в шаблонную формулу:
(a (Оп-д1 b (a Оп-д2))) g (ùa ((Оп-д3 d Оп-д4) l (ùa Оп-д5)))
1.2 Минимизация заданного выражения
Заданное выражение выглядит следующим образом:
( ( A – F) \ ( B \ A ) ) Ç ( E A ÇB ) )
Минимизация проводится с использованием восемнадцати законов. (см. литературы 2)
1) (( A – F) \ ( B \ A )) =
(( A \ F) ( F \ A) \ ( B A )) =
(( A F) ( F A ) ( ( B A ))) =
( A F) ( F A ) ( B A ) =
( A F) B =
A F B
2) ( ( E – B – E )) ( AB))
( B (A B))) =
( B A B)) =
A B
3) ( A F B ) A B
( A F B A) A F B B
Ø ( A F B ) =
A F B
F B – так выглядит выражение после минимизации.
Задание № 2
Анализ заданного бинарного отношения
2.1 Выбор варианта задания
Вариант требующего минимизации выражения бинарного отношения образуется заданием и подстановкой для шаблонной формулы: набора операций над действительными числами; набора нетривиальных операндов; бинарного отношения.
«№операций» =9mod4+1=2
| №операц | a | b | g | d |
| Вариант2 | abs | - | Æ | * |
«№операндов»=9mod7+1=3
| №операн | оп-д1 | оп-д2 | оп-д3 | оп-д4 |
| Вариант3 | b-a | 5*a | 2*a+b | a/2 |
«№отношения»=24mod5+1=5
| №варианта | отношение |
| Варіант 5 | = |
2.2 Бинарное отношение
В шаблонную формулу
( (Оп1 Оп2)) Relation ( (Оп3 Оп4))
подставляются результаты, и получается:
(abs((b-a-5*a)) = (Æ((2*a+b)*a/2)
упрощение формулы :
| b – a – 5a | = ( 2a + b ) a/2
2.3 Построение графика
По данному отношению с помощью программ MathCad или MathLab, или же от руки, можно построить график:
2.4 Исследование свойств отношения
Свойства отношений доказываются путём приведения примеров на графике:
1. Функционален, так как не содержит пары с одинаковыми первыми коэфициентами
2. Инъективен, так как не содержит пары с одинаковыми вторыми компонентами «b» и разными первыми компонентами «a».
3. Не всюду определен, так как область определения не совпадает с областью отправления
4. Сюрьективен так как его область значений равна области прибытия.
5. Биективен, так как функционален, инъективен и сюрьективен.
6. Не рефлексивен так как график не содержит прямую в = а.
7. Актирефлексивен так как график содержит точки , лежащие на прямой и = а.
8. Не иррефлексивен, так как найдутся точки, принадлежащие графику и лежащие на прямой в = а .
9. Не симметричен, так как найдутся точки, не принадлежащие графику и симметричные относительно прямой в = а.
10. Не анттисимметричен, так как найдутся точки, принадлежащие графику и не симметричные относительно прямой в = а.
11. Не ассиметричен, так как найдутся точки, принадлежащие графику и симметричные относительно прямой в = а, и одновременно найдутся точки, не принадлежащие графику и симметричные относительно прямой в = а.
12. Не транзитивен.
Свойства отношения внесены в таблицу
| Функциональность | + |
| Инъективность | + |
| Всюду определенность | – |
| Сюръективность | + |
| Биективность | + |
| Рефлексивность | – |
| Не рефлексивность | – |
| Антирефлексивность | + |
| Симметричность | – |
| Асимметричность | – |
| Антисимметричность | – |
| Транзитивность | – |
Задание № 3
Вариант исходной логической схемы образуется заданием функционального базиса логических функций, размещением логических элементов в сетке мест графического изображения логической схемы, списком связей входов и выходов логических элементов.
Номер варианта заданного функционального базиса логических функций {№Ф-ции1,№Ф-ции2,№Ф-ции3} из таблицы 6, обозначаемый как «№Базиса», получается следующим образом:
«№Базиса»=(«№Зачетки»%8)+1
где % - операция получения целочисленного остатка от деления.
«№Базиса»=(9%8)+1=2, т.е. из таблицы 6 следует, что
{№Ф-ции1,№Ф-ции2,№Ф-ции3}={2,9,14}
Графическое изображение логической схемы содержит пятнадцать мест для размещения (три ряда по пять элементов) логических элементов, реализующих логические функции базиса. Элементы пронумерованы с 5 по 19 включительно, номера с 1 по 4 принадлежат входам логической схемы, а номер 20 приписан выходу всей схемы.
Номер варианта размещения логических элементов в сетке мест графического изображения логической схемы из таблицы 7, обозначаемый как «№Размещения» получается следующим образом:
«№Размещения»= («№Зачетки»%3)+1
где % - операция получения целочисленного остатка от деления.
«№Размещения»=(9%3)+1=1, т.е из таблицы 7 получаем следующее расположение для базиса {№Ф-ции1,№Ф-ции2,№Ф-ции3}={4,6,8 }:
|
№элем №вар |
5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| ф-я1 | x | x | x | x | x | ||||||||||
| ф-я2 | x | x | x | x | x | ||||||||||
| ф-я3 | x | x | x | x | x |
Номер варианта списка связей входов и выходов логических элементов логической схемы обозначаемый как «№Связей» получается следующим образом:
«№Связей»=(«№Зачетки»%13)+1
где % - операция получения целочисленного остатка от деления.
«№Связей»=(9%13)+1=10
В списке связей для каждого логического элемента указаны номера логических элементов, выходы которых соединены с его входами.
Для данного варианта список связей выглядит следующим образом:
5(1,2); 6(1,2); 7(3,4,6); 8(5,6,7); 9(4,6); 10(4,7); 11(1,8,10); 12(1,9); 13(9,10); 14(9,11); 15(10,12,14); 16(10,13); 17(11,14); 18(15,17); 19(16,18); 20(18).
Полученная схема приведена ниже:
Анализ схемы.
Анализ схемы выполняется путем поэтапной подстановки выражений для реализации y
y5=x1~ x2=ùx1ùx2+x1x2
y6=x1/x2=ùx1+ùx2
y7=x3ù→x4ù→y6=(x3ùx4) ù→y6=x3x4x1x2=x1x2x3x4
y8=y5~y6~y7=((x1+x2)( ùx1+ùx2)x1x2+(ùx1ùx2+x1x2)( ùx1+ùx2)) ~y7=
=(ùx1ùx2) ~y7=(x1+x2)( ùx1+ùx2+ùx3+ùx4)+( ùx1ùx2)x1x2x3x4=x1ùx2+x1ùx3+
+x1ùx4+ùx1x2+x2ùx3+x2ùx4
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-Кубов после разбиения и упорядочивания записывается следующим образом:
|
0001 0100 |
|
0110 1001 0011 |
|
1101 1011 |
| 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
Таким образом, с помощью метода Петрика получаем следующее выражение для МДНФ:
МДНФ=ùx1x2ùx4+x1x4+ùx2x4
Видим, что оно совпадает с выражением, полученным с помощью метода Квайна-Мак-Класки.
Теперь рассмотрим минимизацию методом карты Карно:
МДНФ=ùx1x2ùx4+x1x4+ùx2x4
Мы получили результат, который совпадает с двумя результатами, полученными раннее. Это говорит о правильности произведенных вычислений.
Выбор безразличных наборов
По построенной таблице истинности булевой функции заданной логической схемы строится таблица истинности частично определенной булевой функции выбором четырех случайно выбранных безразличных входных двоичных наборов, на которых частичная булева функция не определена (безразлична). В случае наложения безразличного набора на единичный набор (на котором функция принимает значение «1») для данного набора значений аргументов сохраняется значение функции, равное «1».
Номер варианта безразличных входных наборов частичной булевой функции {№Наб1, №Наб2, №Наб3, №Наб4} из таблицы 8, обозначаемый как «№Наборов», получается определением смещенного на «1» целочисленного остатка от деления «№Зачетки» на число «11»- число вариантов таблицы 8 по следующей формуле:
«№Наборов»= «№Зачетки»%9+1
где %- операция получения целочисленного остатка от деления.
«№Наборов»=(9 %11)+1=3, т.е. из таблицы 8 следует, что выбраны безразличные наборы {№Наб1, №Наб2, №Наб3, №Наб4}={8,10,11,12}=
={0111, 1001, 1010, 1011}.
Таким образом, понятно, что изменений не произойдет, так как все безразличные наборы уже присутствуют в наборах булевой функции, полученной из сводной таблицы. Значит вычисление минимизации для функции, пополненной безразличными наборами, даст результат, полученный раннее, т.е.
МДНФ= ùx1x2ùx4+x1x4+ùx2x4
Перевод полученных в пунктах 5 и 6 минимальных формул из булевого базиса в заданный функциональный базис.
Построим логическую схему для МДНФ:
МДНФ=ùx1x2ùx4+x1x4+ùx2x4
Преобразуем МДНФ из булевого базиса {Ú, Ù, ù} в заданный функциональный базис:
МДНФ=(((((x2ù→x4) ù→x1)/(x2ù→x4) ù→x1))/((x4ù→x2)/(x4ù→x2)))/
/(((x2ù→x4) ù→x1)/(x2ù→x4) ù→x1))/((x4ù→x2)/(x4ù→x2))))/(x1/x4)
Логическая схема для полученной формулы булевой функции выглядит следующим образом:
Выводы
В ходе выполнения расчетно-графической работы по дисциплине «Основы дискретной математики» были закреплены основные теоретические знания и практические навыки.
В процессе расчетно-графической работы для построенных в соответствии с индивидуальным вариантом множественной формулы, бинарного отношения и логической схемы выполнен анализ, минимизация множественных и булевых формул, перевод булевых формул в заданный базис и синтез схем в заданном базисе.
Литература:
1. Методические указания выполнения расчетно-графической работы по дисциплине «Основы дискретной математики» для студентов специальностей 6.0804 и 6.0915. / Сост. А. Н. Мартынюк. – Одесса: ОНПУ, 2002.
2. Конспект лекций по дисциплине «Основы дискретной математики» для студентов специальностей 6.0804 и 6.0915. / Сост. А. Н. Мартынюк. – Одесса: ОНПУ, 2002.
ОДЕССКИЙ НАЦИОНАЛЬНЫЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ Кафедра компьютерных интеллектуальных систем и сетей РАСЧЕТНО-ГРАФИЧЕСКАЯ РАБОТА по дисциплине «Основы дискретной математики» Вып
Распределение случайной величины. Эмпирические линии регрессии
Расчет вероятностей событий
Основы научного исследования и планирование экспериментов на транспорте
Основы теории вероятностей
Основы теории вероятности
Основы черчения
Особливі точки рівняння
Отрицания и антитезы в E-структурах
Парадоксы в математике
10 способов решения квадратных уравнений
Copyright (c) 2024 Stud-Baza.ru Рефераты, контрольные, курсовые, дипломные работы.