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

Посмотреть архив целиком

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

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








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

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

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







Выполнил

студент группы АЕ-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, обозначаемый как «№Размещения» получается следующим образом:


Случайные файлы

Файл
14723.rtf
174052.rtf
21428-1.rtf
5205-1.rtf
97285.rtf




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.