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

Циклическое число определяется только для неориентированных графов. По варианту, дан ориентированный граф, то циклическое число находить не нужно.

1.8 Вершинное и реберное числа независимости

Множество SV графа G = (V, Г) называют внутренне устойчивым, если никакие две вершины из S не смежны, т.е. для любого хS имеет место ГхS¹Æ.

Множество внутренней устойчивости, содержащее наибольшее число элементов, называют наибольшим внутренне устойчивым множеством, а число элементов этого множества – числом внутренней устойчивости e₀(G) графа G (это число называют также вершинным числом независимости графа).

Два ребра графа называют смежными, если они инцидентны одной и той же вершине. Максимальное число попарно несмежных ребер графа называется его реберным числом независимости e₁(G).

Вершинное и реберное числа независимости графа на рисунке 1

e₀(G)=2       

e₁(G)=3        

1.9 Числа вершинного и реберного покрытий графа

Если ребро графа инцидентно его вершине, то говорят, что они покрывают друг друга. Множество вершин, покрывающих все ребра графа, называют вершинным покрытием графа G, а минимальную мощность этого множества - числом вершинного покрытия графа p₀(G). Аналогично, множество ребер, покрывающих все вершины графа, называют реберным покрытием графа G, а минимальную мощность этого множества – числом реберного покрытия графа p₁(G).

Числа вершинного и реберного покрытий графа на рисунке 1:

p₀(G)=4         

p₁(G)=5        

1.10 Вершинное и реберное число внешней устойчивости графа

Множество ТÌV графа G=(V, Г) называют внешне устойчивым, если любая вершина, не принадлежащая Т, соединена ребрами с вершинами из Т, т.е. для любого хÏТ имеет место ГхÇТ¹Æ.

Множество внешней устойчивости, содержащее наименьшее число элементов, называется наименьшим внешне устойчивым множеством, а число элементов этого множества – вершинным числом внешней устойчивости b₀(G) графа G.

Минимальная мощность множества ребер, покрывающих все ребра графа, называется реберным числом внешней устойчивости b₁(G) графа G.

Вершинное и реберное числа внешней устойчивости графа на рис.1.1:

b₀(G)= 2       

b₁(G)= 2       

2 СИНТЕЗ ЛОГИЧЕСКИХ СХЕМ

Синтез логических схем осуществляется на основе заданной функции алгебры логики. Функция, определенная на наборах <x_n-1, …, x_i, …, x₂, x₁, x₀> и принимающая на этих наборах значение 0 или 1, называется функцией алгебры логики.

2.1 Таблица истинности функции алгебры логики          

    - (1)               

								1	2		3	4	f
	x4	x3	x2	x1	x0								(4)->(3)
0	0	0	0	0	0	1	1	0	0	1		1	1
1	0	0	0	0	1	1	1	0	1	0		1	0
2	0	0	0	1	0	0	1	0	0	1		0	1
3	0	0	0	1	1	0	1	0	1	0		0	1
4	0	0	1	0	0	1	0	0	0	1		1	1
5	0	0	1	0	1	1	0	0	1	0		1	0
6	0	0	1	1	0	0	0	0	0	1		0	1
7	0	0	1	1	1	0	0	0	1	0		0	1
8	0	1	0	0	0	1	1	1	1	0		1	0
9	0	1	0	0	1	1	1	1	1	0		1	0
10	0	1	0	1	0	0	1	1	1	0		0	1
11	0	1	0	1	1	0	1	1	1	0		0	1
12	0	1	1	0	0	1	0	0	0	1		1	1
13	0	1	1	0	1	1	0	0	1	0		1	0
14	0	1	1	1	0	0	0	0	0	1		0	1
15	0	1	1	1	1	0	0	0	1	0		0	1
16	1	0	0	0	0	1	1	0	0	1		1	1
17	1	0	0	0	1	1	1	0	1	0		1	0
18	1	0	0	1	0	0	1	0	0	1		1	1
19	1	0	0	1	1	0	1	0	1	0		1	0
20	1	0	1	0	0	1	0	0	0	1		1	1
21	1	0	1	0	1	1	0	0	1	0		1	0
22	1	0	1	1	0	0	0	0	0	1		1	1
23	1	0	1	1	1	0	0	0	1	0		1	0
24	1	1	0	0	0	1	1	1	1	0		1	0
25	1	1	0	0	1	1	1	1	1	0		1	0
26	1	1	0	1	0	0	1	1	1	0		1	0
27	1	1	0	1	1	0	1	1	1	0		1	0
28	1	1	1	0	0	1	0	0	0	1		1	1
29	1	1	1	0	1	1	0	0	1	0		1	0
30	1	1	1	1	0	0	0	0	0	1		1	1
31	1	1	1	1	1	0	0	0	1	0		1	0

2.2 Совершенные дизъюнктивная и конъюнктивная  нормальные формы

СДНФ:

Сложность формулы  a(Y)=5*18=90

СКНФ:

Сложность формулы  a(Y)=5*14=60

2.3 Анализ функции алгебры логики на принадлежность к классам

Так как f(0, 0, 0, 0, 0) = 1, то данная функция алгебры логики не принадлежит к классу функций сохраняющих ноль, т.е. fÏK₀

Так как f(1, 1, 1, 1, 1)=0, то данная функция алгебры логики принадлежит к классу функций сохраняющих единицу, т.е. fÏK₁

Анализ функции алгебры логики на принадлежность к классу линейных функций:

f_л=CÅC₀x₀ÅC₁x₁ÅC₂x₂ÅC₃x₃ÅC₄x₄

Коэффициент С находим на наборе <0,0,0,0,0>

f(00000)= CÅ0Å0Å0Å0Å0=C=1, тогда C=1

Коэффициент С₄ находим на наборе <0,0,0,0,1>

f(00001)= 1Å0 Å0Å0Å0ÅC₄*1=1, тогда C₄=0

Коэффициент С₃ находим на наборе <0,0,0,1,0>

f(00010)= 1Å0Å0Å0ÅC₃*1Å0=0, тогда C₃=1

Коэффициент С₂ находим на наборе <0,0,1,0,0>

f(00100)= 1Å0Å0ÅC₂*1Å0Å0=1, тогда C₂=0

Коэффициент С₁ находим на наборе <0,1,0,0,0>

f(01000)= 1Å0ÅC₁*1Å0Å0Å0=1, тогда C₁=0

Коэффициент С₀ находим на наборе  <1,0,0,0,0>

f(10000)= 1ÅC₀*1Å0Å0Å0Å0=0, тогда C₀=1

f_л=1

Идет несовпадение, значит функция не линейная, т.е. fÏK_л.

Анализ функции алгебры логики на принадлежность к K_с. Выразим обратную функцию (1) и составим таблицу истинности для обратной функции и сравним с исходной :

	x4	x3	x2	x1	x0
0	0	0	0	0	0	1
1	0	0	0	0	1	0
2	0	0	0	1	0	1
3	0	0	0	1	1	0
4	0	0	1	0	0	1
5	0	0	1	0	1	1
6	0	0	1	1	0	1
7	0	0	1	1	1	1
8	0	1	0	0	0	1
9	0	1	0	0	1	0
10	0	1	0	1	0	1
11	0	1	0	1	1	0
12	0	1	1	0	0	1
13	0	1	1	0	1	0
14	0	1	1	1	0	1
15	0	1	1	1	1	0
16	1	0	0	0	0	0
17	1	0	0	0	1	0
18	1	0	0	1	0	1
19	1	0	0	1	1	0
20	1	0	1	0	0	0
21	1	0	1	0	1	0
22	1	0	1	1	0	1
23	1	0	1	1	1	1
24	1	1	0	0	0	0
25	1	1	0	0	1	0
26	1	1	0	1	0	1
27	1	1	0	1	1	0
28	1	1	1	0	0	0
29	1	1	1	0	1	0
30	1	1	1	1	0	1
31	1	1	1	1	1	0

Анализируем полученную таблицу и приходим к выводу что функция не принадлежит к классу fÏ K_с.

Проверим принадлежность функции алгебры логики к классу монотонных функций f_м:

I \ j	00000	00001	00010	00011	00100	00101	00110	00111	01000
00000	*	+	+	+	+	+	+	+	-
00001	*	*
00010	*	*	*
00011	*	*	*	*
00100	*	*	*	*	*
00101	*	*	*	*	*	*
00110	*	*	*	*	*	*	*
00111	*	*	*	*	*	*	*	*
01000	*	*	*	*	*	*	*	*	*

Если в полученной матрице есть хотя бы один знак “-“, то функция не является монотонной, т.е. fÏ K_м

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

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

2.5 Минимизация с помощью карт Карно

Продолжение карты Карно

Записываем МДНФ  в виде логической суммы конъюнкций, соответствующих выполненным накрытиям:

2.6 Минимизация методом Квайна -  Мак-Класски

Этот метод использует перебор конъюнкций, которые могут присутствовать