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

Сравним наборы:

…

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

1. Класс монотонных функций

Анализируем  функцию к принадлежности к классу К_м. Для этого необходимо построить матрицу (табл.), в которой по строчкам (i) и столбцам (j) записаны наборы функции .

Потом заполняем  звездочками следующие пересечения:

• Все элементы (обозначения переменных на конкретном наборе) строчки равняются всем элементам столбца, т.е i=j
• Хотя бы один элемент строчки больше элемента столбца, т.е i>j.

В клетках, которые остались, ставим плюс «+», если значение функции  на наборе i меньше или равняется значению функции на наборе j, и минус «-», если значение функции на наборе i больше значения функции на наборе j.

Табл. 2.3

i\j

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

00000

00001

00010

00011

00100

00101

00110

00111

01000

01001

01010

01011

01100

01101

01110

01111

10000

10001

10010

10011

10100

10101

10110

10111

11000

11001

11010

11011

11100

11101

11110

11111

1

00000

*

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

2

00001

*

*

*

+

*

+

*

+

*

+

*

+

*

+

*

+

*

+

*

+

*

+

*

+

*

+

*

+

*

+

*

+

3

00010

*

*

*

+

*

*

+

+

*

*

+

+

*

*

+

+

*

*

+

+

*

*

+

+

*

*

+

+

*

*

+

+

4

00011

*

*

*

*

*

*

*

+

*

*

*

+

*

*

*

+

*

*

*

+

*

*

*

+

*

*

*

+

*

*

*

+

5

00100

*

*

*

*

*

*

+

+

*

*

*

*

+

+

+

+

*

*

*

*

+

+

+

+

*

*

*

*

+

+

+

+

6

00101

*

*

*

*

*

*

*

+

*

*

*

*

*

+

*

+

*

*

*

*

*

+

+

+

+

*

*

*

*

*

*

+

7

00110

*

*

*

*

*

*

*

+

*

*

*

*

*

*

+

+

*

*

*

*

*

*

+

+

*

*

*

*

*

*

+

+

8

00111

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

+

*

*

*

*

*

*

*

+

*

*

*

*

*

*

*

+

9

01000

*

*

*

*

*

*

*

*

*

+

+

+

+

+

+

+

*

*

*

*

*

*

*

*

+

+

+

+

+

+

+

+

10

01001

*

*

*

*

*

*

*

*

*

*

+

+

*

+

+

+

*

*

*

*

*

*

*

*

*

+

+

+

+

+

+

+

11

01010

*

*

*

*

*

*

*

*

*

*

*

+

*

*

+

+

*

*

*

*

*

*

*

*

*

*

+

+

*

*

+

+

12

01011

*

*

*

*

*

*

*

*

*

*

*

*

*

+

*

+

*

*

*

*

*

*

*

*

*

*

*

+

*

+

*

+

13

01100

*

*

*

*

*

*

*

*

*

*

*

*

*

+

+

+

*

*

*

*

*

*

*

*

*

*

*

+

+

+

+

+

14

01101

*

*

*

*

*

*

*

*

*

*

*

*

*

*

+

+

*

*

*

*

*

*

*

*

*

*

*

*

*

+

*

+

15

01110

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

+

*

*

*

*

*

*

*

*

*

*

*

*

*

*

+

+

16

01111

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

+

17

10000

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

18

10001

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

+

*

+

*

+

*

+

*

+

*

+

*

+

19

10010

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

+

*

*

+

+

*

*

+

+

*

*

+

+

20

10011

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

+

*

*

*

+

*

*

*

+

21

10100

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

+

+

+

*

*

*

*

+

+

+

+

22

10101

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

+

*

*

*

*

+

*

+

*

+

23

10110

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

+

*

*

*

*

*

*

+

+

24

10111

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

+

25

11000

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

+

+

+

+

+

+

+

26

11001

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

+

*

+

*

+

27

11010

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

+

*

+

+

+

28

11011

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

+

29

11100

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

+

+

30

11101

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

+

31

11110

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

+

32

11111

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

Если в полученной матрице есть хоть один знак «-», то функция не монотонна, т.е.

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

Области, в которых (и только в этих областях!) предполагается возможным знак «-» выделены серым цветом – это области пересечения строк со значением функции 1 и столбцов со значением функции 0. Как мы видим, все эти наборы несравнимы, поэтому ни одна ячейка таблицы не будет иметь знак «-» и, следовательно, функция монотонна)

2. Минимизация функции алгебры логики

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

 

Минимизация функции алгебры логики методом Квайна

Т.к. количество наборов, на которых функция принимает  значение 1 довольно велико (24 из 32), воспользуемся  методом Квайна для минимизации  функции.

Метод Квайна заключается в полном попарном сравнении  каждого из наборов СДНФ, со всеми наборами СДНФ.

При этом используется преобразование СДНФ с помощью операций неполного склеивания и поглощения.

Операция  полного склеивания:

,

два члена и склеиваются по переменной y.

Операция  неполного склеивания:

 

Операция  поглощения:

,

где член xy поглощается x членом.

Теорема Квайна. Если в ДНФ переключательной функции провести все операции неполного склеивания, а затем все операции поглощения, то получим сокращенную ДНФ, т.е. дизъюнкцию простых импликант.

Метод Квайна выполняется в несколько  этапов:

1. Провести в СДНФ функции все возможные операции неполного склеивания конституент единицы. В результате образуются произведения-минтермы (n-1) ранга (конъюнкция (n-1) ранга).

Затем проводят операцию поглощения.

2. Провести возможные склеивания членов  (n-1) ранга, затем поглощения. Получают конъюнкцию (n-2) ранга.
3. Выполнить операции склеивания членов с числом букв (n-2)  ранга. Получаем конъюнкцию (n-) ранга и т. д.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

В итоге мы получили МДНФ, состоящую  всего из 2-х переменных:

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

 

2.5 Синтез  схемы методом каскадов.

Графическое обозначение  логических элементов  Табл.2.5

 

Константа 0
Отрицание
Дизъюнкция
Конъюнкция
Элемент Вебба
Элемент Шеффера
Импликация
Коимпликация
Сложение по модулю 2
Эквивалентность
Константа 1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис. 2.2 Функциональная логическая схема дизъюнкции 2-х переменных

 

 

ЗАКЛЮЧЕНИЕ

Курсовая работа содержит два раздела: задачи теории графов и  синтез логических схем.

В первой части для заданного  графа составлена таблица соответствия вершин и ребер, составлен фактор – множества. Данный граф описан также  матрицами: матрицей инциденций размерностью 6х9, матрицей смежности  размерностью 6х6, матрицей циклов размерностью 10х9, матрицей разрезов  размерностью 15х9, матрицей путей размерностью 7х9.  Найдены числовые характеристики графа: степени всех вершин графа, вершинная  и реберная связность графа, цикломатическое  число графа, вершинное и реберное числа независимости, числа вершинного и реберного покрытия графа, вершинное  и реберное числа внешней устойчивости графа, радиус и диаметр графа. Решена задача на нахождения максимального  потока в графе.

Во второй части составлена таблица истинности для заданной функции алгебры логики, найдены  её совершенные дизъюнктивные и  конъюнктивные нормальные формы, выявлено, что функция не принадлежит к  классу функций сохраняющих ноль и классу функций, сохраняющих единицу  и  не принадлежит к классу линейных, самодвойственных и монотонных функций. Заданная функция минимизирована с  помощью метода Квайна. И минимальная  дизъюнктивная нормальная форма  имеет вид: . Схема синтезирована методом каскадов, реализована при помощи двухвходовых логических элементов и изображена на рис.2.2.

Таким образом, я закрепил полученные знания по дисциплине «Основы дискретной математики», овладел математическим аппаратом  и приобрел навыки самостоятельного синтеза логических схем.

 

СПИСОК   ЛИТЕРАТУРЫ

Основная:

1. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2002. – 304 с.
2. Марасанов В.В. Элементы теории систем. – Кишинев: Штиинца, 1991. – 176с.
3. Горбатов В.А. Фундаментальные основы дискретной математики. – М.: Наука. Физматлит, 2000. – 544с.
4. Капітонова Ю.В. и др. Основи дискретної математики. - К.: Наукова думка, 2002. – 579с.
5. Акимов О.Е. Дискретная математика. Логика, группы, графы. – М.: Лаборатория базовых знаний, 2001. – 376с.
6. Бардачев Ю.Н., Соколова Н.А., Ходаков В.Е. Основы дискретной математики. – Херсон: Изд-во ХГТУ. – 200. – 357 с.
7. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженеров. – М.: Энергоатомиздат, 1988. – 480 с.
8. Дискретная математика и математические вопросы кибернетики. (Под ред. Яблонского С.В., Лупанова А.А.) М.: Наука, 1974.
9. Методичні вказівки до виконання курсової роботи з дисципліни “Спеціальні розділи вищої математики”. / Димов В.С., Димова Г.О. – Херсон: ХДТУ, 2000. – 42с.

Дополнительная: 

1. Оре О. Теория графов. – М. Мир, 1968.
2. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Алгебра. Языки. Программирование. – Киев: Наукова думка, 1989. – 376с.
3. Гильберт Д., Бернайс П. Основания математики. Т.1. Логические исчисления и формализация арифметики. – М.: Наука, 1978. – 556 с., Т.2. Теория доказательств. – М.: Наука, 1982. – 652 с.
4. Клини С.К. Введение в метаматематику. – М.: Изд-во иностр. лит., 1957. – 526 с.
5. Успенский В.А., Семенов Л.А. Теория алгоритмов: основні открітия и приложения. М.: Наука, 1987. – 288 с.
6. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. – М.: Наука, 1975. – 240 с.
7. Мальцев А.И. Алгебраические системы. – М.: Наука, 1970