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

Страницы работы

Фрагмент текста работы

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

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

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

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

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

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

e0(G)=2       

e1(G)=3        

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

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

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

p0(G)=4         

p1(G)=5        

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

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

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

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

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

b0(G)= 2       

b1(G)= 2       

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

Синтез логических схем осуществляется на основе заданной функции алгебры логики. Функция, определенная на наборах <xn-1, …, xi, …, x2, x1, x0> и принимающая на этих наборах значение 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ÏK0

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

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

fл=CÅC0x0ÅC1x1ÅC2x2ÅC3x3ÅC4x4

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

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

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

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

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

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

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

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

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

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

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

f(10000)= 1ÅC0*1Å0Å0Å0Å0=0, тогда C0=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 Минимизация с помощью карт Карно

х0

0

х4

4

х4

4

х3

11001

25   0

11101

29  0

01101

13   0

01001

9   0

11000

24   0

11100

28   1

01100

12   1

01000

8   0

1

11011

27   0

11111

31  1

01111

15   1

01011

11   1

11010

26   0

11110

30   1

01110

14   1

01010

10   1

х1

3

10011

19   0

10111

23  0

00111

7   1

00011

3   1

10010

18   1

10110

22   1

00110

6   1

00010

2   1

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

10001

17   0

10101

21   0

00101

5   0

00001

1   0

10000

16   1

10100

20   1

00100

4   1

00000

0   1

1

2

х2

2

2

х2

2

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

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

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

Похожие материалы

Информация о работе