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

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

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

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

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

Выполнил

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

Ф.И.О.

Проверил

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

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

Одесса 2008

Введение

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

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

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

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

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

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

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

Задание № 1

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

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

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

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

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

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

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

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

Таблицы – см. литература 1.

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

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

№ операции
Вариант 3	Ø	\

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

№ операнда	оп-д1	оп-д2	оп-д3	оп-д4	оп-д5
Вариант 5	AF	BA	EB	E	AB

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

( (Оп-д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

1. ( ( E – B – E )) ( AB))

( B (A  B))) =

( B A  B)) =

A B

1. ( 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

№операц
Вариант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=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=