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

Минимизация заданного выражения алгебры множеств на основании известных свойств. Анализ заданного бинарного отношения в общем виде. Вывод формул булевых функций для каждого элемента и схемы в целом. Преобразование формулы булевой функции логической схемы.

Рубрика Математика
Вид контрольная работа
Язык русский
Дата добавления 28.02.2009
Размер файла 286,7 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

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

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

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

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

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

Выполнил

студент группы АЕ-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

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

№операц

Вариант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=

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

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

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

Формула 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-Кубов после разбиения и упорядочивания записывается следующим образом:

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

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

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


Подобные документы

  • Решения задач дискретной математики: диаграммы Эйлера-Венна; высказывание в виде формулы логики высказываний и формулы логики предикатов; СДНФ и СКНФ булевой функции. При помощи алгоритма Вонга и метода резолюции выяснить является ли клауза теоремой.

    контрольная работа [133,5 K], добавлен 08.06.2010

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

    контрольная работа [375,6 K], добавлен 17.01.2011

  • Логика - наука о законах и формах мышления, а основное понятие алгебры логики - высказывание. Основные понятия и тождества булевой алгебры. Изучение методов минимизации булевых функций. Метод Квайна, основанный на применении двух основных соотношений.

    контрольная работа [178,2 K], добавлен 20.01.2011

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

    курсовая работа [278,1 K], добавлен 21.02.2009

  • Построение графа и таблицы поведения автомата. Нахождение системы булевых функций для возбуждения JK-триггеров, реализующих функции y. Определение булевой функции для реализации функции j. Составление логической схемы автомата, кодирование данных.

    курсовая работа [200,4 K], добавлен 27.04.2011

  • Построение таблицы поведения автомата и соответствующего графа. Нахождение системы булевых функций для возбуждения T-триггеров, реализующих функции "пси". Определение булевой функции для реализации функции "фи". Составление логической схемы автомата.

    курсовая работа [96,7 K], добавлен 27.04.2011

  • Графическая интерпретация множеств и операций над ними. Математическая логика, булева алгебра. Совершенная конъюнктивная нормальная форма. Равносильные формулы и их доказательство. Полнота системы булевых функций. Логика предикатов, теория графов.

    лекция [253,7 K], добавлен 01.12.2009

  • Синтез схемы, реализующей функцию, заданную кубическим комплексом в универсальном базисе логических элементов ИЛИ-НЕ. Нахождение минимального и построение факторизованного покрытий. Составление логической схемы и ее проверка контролирующим тестом.

    курсовая работа [261,7 K], добавлен 16.06.2011

  • Изучение булевых функций. Алгоритм представления булевых функций в виде полинома Жегалкина. Система функций множества. Алгебраические преобразования, метод неопределенных коэффициентов. Таблица истинности для определенного количества переменных.

    курсовая работа [701,9 K], добавлен 27.04.2011

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

    контрольная работа [225,5 K], добавлен 18.02.2015

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.