Основы дискретной математики

ОДЕССКИЙ НАЦИОНАЛЬНЫЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Кафедра компьютерных интеллектуальных систем и сетей

РАСЧЕТНО-ГРАФИЧЕСКАЯ РАБОТА

по дисциплине

«Основы дискретной математики»

Выполнил

студент группы АЕ-074

Ф.И.О.

Проверил

доцент кафедры КИСС

Мартынюк А. Н.

Одесса 2008

Данная расчетно-графическая работа по дисциплине «Основы дискретной математики» включает в себя:

· задачу минимизации заданного выражения алгебры множеств на основании известных свойств;

· анализ заданного бинарного отношения в общем виде, построение его графика и полное определение свойств отношения, включая свойства, унаследованных им от соответствий;

· анализ заданной в определенном функциональном базисе логической схемы: вывод формул булевых функций для каждого элемента и схемы в целом, с одновременной их минимизацией на основании известных свойств и тождеств, а также построение таблиц истинности;

· преобразование формулы булевой функции заданной логической схемы в КНФ, ДНФ, СКНФ и СДНФ, а также ее минимизацию методами Квайна-МакКласки, Петрика, и с помощью карт Карно;

· пополнение булевой функции заданными безразличными входными наборами и минимизацию пополненной функции с помощью карт Карно, а также методов Квайна-МакКласки и Петрика;

· перевод полученных минимизированных формул из булева базиса в заданный функциональный базис и синтез соответствующих логических схем.

Задание № 1

Упрощение заданного выражения алгебры множеств

1.1 Выбор варианта задания

Варианты РГР образуются заданием индивидуальных:

· выражения алгебры множеств;

· бинарного отношения;

· исходной логической схемы;

· безразличных входных наборов.

В основе выбора варианта лежит процедура определения целочисленного остатка от деления выражения, в котором присутствует число. (Вариант 9)

Таблицы — см.

литература

1.

Выбор варианта выражения алгебры множеств.

«№ операций» = 9mod7+1=3

«№ операндов"=9mod5+1=5

Результаты подставляются в шаблонную формулу:

((Оп-д1 (Оп-д2))) (((Оп-д3 Оп-д4) (Оп-д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)) ??(???A???B??))??

???(?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

«№операндов"=9mod7+1=3

«№отношения"=24mod5+1=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 }:

Номер варианта списка связей входов и выходов логических элементов логической схемы обозначаемый как «№Связей» получается следующим образом:

«№Связей"=("№Зачетки"%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=x1x2+x1x2

y6=x1/x2=x1+x2

y7=x3>x4>y6=(x3x4) >y6=x3x4x1x2=x1x2x3x4

y8=y5~y6~y7=((x1+x2)(x1+x2)x1x2+(x1x2+x1x2)(x1+x2)) ~y7=

=(x1x2) ~y7=(x1+x2)(x1+x2+x3+x4)+(x1x2)x1x2x3x4=x1x2+x1x3+

+x1x4+x1x2+x2x3+x2x4

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(x1x2+x1x3+x1x4+x1x2+x2x3+x2x4)) ~y10=((x1+x1x2) (x1+x3) (x1+x4)(x1+x2)(x2+x3)(x2+x4)+(x1x2+x1x3+x1x4+x1x2x3+x1x2x4)) ~y10=(x1x2(x1+x3)(x2+x3)(x2+x4)(x1+x4)+ (x1x2+x1x3+x1x4+ +x1x2x3+x1x2x4)) ~y10=((x1x2+x1x2x3) (x2+x3)(x2+x4)(x1+x4)+

+(x1x2+x1x3+x1x4+ +x1x2x3+x1x2x4)) ~y10=((x1x2+x1x2x3)

(x2+x4)(x1+x4)+ (x1x2+x1x3+x1x4+ x1x2x3+x1x2x4)) ~y10=

=((x1x2+x1x2x4+x1x2x3+x1x2x3x4)(x1+x4)+(x1x2+x1x3+

+ x1x4+ x1x2x3+x1x2x4)) ~y10=(x1x2+x1x2x4+x1x2x3x4+

+ x1x2+x1x3+ x1x4+ x1x2x3+x1x2x4)~y10=(x1x2+x1x2+x1x3+

+x1x4+x1x2x3+x1x2x4) ~y10=(x2+x1x3+x1x4+x1x2x3+x1x2x4) ~y10=

=(x2+x1x3+x1x4)~y10=x2(x1+x3)(x1+x4)(x1+x4)(x2+x4)(x3+x4)+

+(x2+x1x3+x1x4)(x1x4+x2x4+x3x4)=x2(x1+x3)(x1x4+x1x4)

(x2+x4)(x3+x4) +(x2+x1x3+x1x4)(x1x4+x2x4+x3x4)=

=x2(x1+x3)(x1x2x4+x1x2x4+x1x4)(x3+x4) +(x2+x1x3+x1x4)

(x1x4+x2x4+x3x4)=x2(x1+x3)(x1x2x3x4+x1x2x3x4+x1x2x4+

+x1x2x4) +(x2+x1x3+x1x4)(x1x4+x2x4+x3x4)=(x1+x3)(x1x2x4+

+x1x2x3x4+x1x2x3x4) +(x2+x1x3+x1x4)(x1x4+x2x4+x3x4)=

=(x1+x3) (x1x2x4+x1x2x3x4) +(x2+x1x3+x1x4)(x1x4+x2x4+x3x4)=

=x1x2x4+x1x2x3x4+x1x2x3x4+x1x2x4+x2x4+x2x3x4+x1x2x3x4+

+x1x3x4=x1x2x3+x1x2x3x4+x2x4+x1x3x4

y12=x1/y9 =x1+x4(x1+x2)= x1+x1x4+x2x4=x1+x2x4

y13= y9>y10=(x4+x1x2)(x1+x4)(x2+x4)(x3+x4)=(x1x4+x4+x1x2+

+x1x2x4)(x2+x4)(x3+x4)=(x4+x1x2)(x2+x4)(x3+x4)=(x2x4+x4+

+x1x2+x1x2x4)(x3+x4)=(x4+x1x2)(x3+x4)=x3x4+x4+x1x2x3+

+x1x2x4=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+x1x3x4)=

=x4(x1x2+x1x4+x1x2+x2)(x1+x2+x3+x4)(x2+x4)(x1+x3+x4)+

+(x4+x1x2)(x1x2x4+x1x2x3x4+x2x4+x1x3x4)=x4(x2+x1x4)(x1+x2+

+x3+x4)(x1x2+x2x3+x2x4+x1x4+x3x4+x4) +(x4+x1x2)(x1x2x4+

+ x1x2x3x4+x2x4+x1x3x4)= x2x4(x1+x2+x3+x4)(x1x2+x2x3+x4)+

+(x4+x1x2)(x1x2x4+x1x2x3x4+x2x4+x1x3x4)=(x1x2x4+x2x4+

+x2x3x4)(x1x2+x2x3+x4)+ (x4+x1x2) (x1x2x4+x1x2x3x4+x2x4+

+x1x3x4)= x2x4(x1x2+x2x3+x4) +(x4+x1x2)(x1x2x4 +x1x2x3x4+x2x4+

x1x3x4)=(x4+x1x2)(x1x2x4+x1x2x3x4+x2x4+x1x3x4)=x1x2x3x4+

+x1x2x3x4=x1x2x4

y15=y10/y12/y14=((x1+x4)(x2+x4)(x3+x4)+x1(x2+x4))/y14=

=((x1x2+x1x4+x2x4+x4)+x1x2+x1x4)/y14=((x1x2x3+x1x2x4+x3x4+x4)+

+x1x2+x1x4)/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+x1x2x4+

+x1x3x4+x2x4+x1x2x4+x1x3x4+x3x4+x1x3x4+x2x3x4=

=x1x4+x2x4+x3x4

y17=y11~y14=(x1+x2+x4)(x1+x2+x3+x4)(x2+x4)(x1+x3+x4)

(x1+x2+x4)+(x1x2x4+x1x2x3x4+x2x4+x1x3x4)x1x2x4=

=(x1x2+x1x3+x1x4+x1x2+x2+x2x3+x2x4+x1x4+x2x4+x3x4)

(x1x2+x2x3+x2x4+x1x4+x3x4+x4)+x1x2x3x4+x1x2x3x4=

=x2x4+x1x3x4+x1x2x3x4+x1x4+x1x2x4+x1x2x3x4+x1x2x3x4+

+x1x2x3x4+x1x2x3x4=x2x4+x1x4+x1x2x4+x1x2x3x4+x1x2x3x4+

+x2x4=x2x4+x1x4+x2x4

y18=y15/y17=x1x2x4+(x2+x4)(x1+x4)(x2+x4)=x1x2x4+(x1x2+x2x4+

+x1x4+x4)(x2+x4)=x1x2x4+(x1x2+x4)(x2+x4)=x1x2x4+x1x2x4+

+x2x4=x1x2x4+x1x4+x2x4

y19=y16>y18 =(x1x4+x2x4+x3x4)(x1+x2+x4)(x1+x2+x4)(x2+x4)=

=(x1x4+x2x4+x3x4)(x1+x2+x4)(x1x2+x1x4+x2x4+x2x4)=

=(x1x4+x2x4+x3x4)(x1x2x4+x1x2x4+x1x2x4+x2x4+x1x2x4+

+x1x4+x2x4)= (x1x4+x2x4+x3x4)(x1x2x4+x2x4+x1x4)=

=x1x2x4+x1x2x3x4=x1x2x4

y20=y18=x1x2x4+x1x4+x2x4

Теперь выполним построение сводной таблицы. В левой части таблицы приводятся все возможные наборы из четырех аргументов — от нулевого до пятнадцатого, а в правой — значения функции для каждого элемента логической схемы.

Формула x1x2x4+x1x4+x2x4, полученная для всей таблицы, записана в виде ДНФ. Для перевода ее в СДНФ, введем единицы для недостающих элементов в каждый минитерм:

СДНФ=(x3+x3)(x2+x2) x1x4+(x3+x3) x1x2x4+(x3+x3)(x1+x1)x2x4=

=x1x2x3x4+x1x2x3x4+x1x2x3x4+x1x2x3x4+x1x2x3x4+x1x2x3x4+

+x1x2x3x4+x1x2x3x4

Выполним перевод из 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+x1x2x3x4+x1x2x3x4+x1x2x3x4+x1x2x3x4+x1x2x3x4+

+x1x2x3x4+x1x2x3x4

Множество 0-Кубов после разбиения и упорядочивания записывается следующим образом:

K₀=

Будем попарно сравнивать S-кубы из соседних поясов, склеивая таковые, отличающиеся только по одной координате. Такая операция склеивания соответствует объединению двух S-кубов. Получим (S+1)-куб, в котором склеиваемую координату заместим символом «~». Склеиваемые кубы будем отмечать знаком ««.

K'₀ =

K₁ =

K

K₂ =

K₃ =

Очевидно, во множестве K₂ склеивание S-кубов невозможно. Поэтому следующее множество K₃ — пустое. Полученная сокращенная форма содержит четыре простые импликанты (неотмеченные кубы, то есть те, которые не склеились в процессе сравнения).

Теперь построим таблицу Квайна. Ее строкам соответствуют простые импликанты из сокращенной формы, столбцам — конституэнты булевой функции.

Очевидно, каждая импликанта является существенной. В этом случае тупиковая форма единственна. Она же будет являться и минимальной формой.

МДНФ=x1x2x4+x1x4+x2x4

Полученная формула в точности равна полученной еще на этапе анализа логической схемы. Действительно, при анализе мы пользовались аналитической минимизацией, применяя те ли иные свойства. Универсальный метод Квайна-Мак-Класки показал, что полученная ДНФ действительно является минимальной.

Полученный вывод можно подтвердить также с помощью метода Петрика. Логическое условие покрытия всей таблицы Квайна имеет вид:

baa (bc)bc (bc)c

Производя простые преобразования, получаем:

abc

Таким образом, с помощью метода Петрика получаем следующее выражение для МДНФ:

МДНФ=x1x2x4+x1x4+x2x4

Видим, что оно совпадает с выражением, полученным с помощью метода Квайна-Мак-Класки.

Теперь рассмотрим минимизацию методом карты Карно:

МДНФ=x1x2x4+x1x4+x2x4

Мы получили результат, который совпадает с двумя результатами, полученными раннее. Это говорит о правильности произведенных вычислений.

Минимизация методами Квайна-Мак-Класки и Петрика, а также с помощью карт Карно формулы частично определенной булевой функции, полученной из таблицы истинности п. 4, пополненной заданными безразличными входными наборами.

Выбор безразличных наборов

По построенной таблице истинности булевой функции заданной логической схемы строится таблица истинности частично определенной булевой функции выбором четырех случайно выбранных безразличных входных двоичных наборов, на которых частичная булева функция не определена (безразлична). В случае наложения безразличного набора на единичный набор (на котором функция принимает значение «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}.

Таким образом, понятно, что изменений не произойдет, так как все безразличные наборы уже присутствуют в наборах булевой функции, полученной из сводной таблицы. Значит вычисление минимизации для функции, пополненной безразличными наборами, даст результат, полученный раннее, т. е.

МДНФ= x1x2x4+x1x4+x2x4

Перевод полученных в пунктах 5 и 6 минимальных формул из булевого базиса в заданный функциональный базис.

Построим логическую схему для МДНФ:

МДНФ=x1x2x4+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.