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

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

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

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

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

Выполнил

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

Ф.И.О.

Проверил

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

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

Одесса 2008

Введение

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

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

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

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

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

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

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

Задание № 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 )) ( 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

№операц 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, т.е. ............