Умножитель по модулю 9. Оптимизация

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

12 страниц (Word-файл)

Содержание работы

Оптимизация функции .

1.  Оптимизация

Рассмотрим нулевое подмножество функции . Оно содержит следующие конъюнкции: 12346 и 13456. Очевидно, что конъюнкция меньшего ранга, которая не будет покрывать нулевое подмножество функции, - 25. Получаем .

2.  Оптимизация

Так как функция содержит элементарные конъюнкции только пятого ранга, ее оптимизация возможна за счет элементарных конъюнкций четвертого и меньших рангов. Рассмотрим элементарные конъюнкции четвертого ранга:

Конъюнкция

Покрываемый набор из

Количество покрываемых импликант

Множество импликант

1

1245

-

0

-

2

1256

-

0

-

3

2345

-

0

-

4

2356

-

0

-

5

2456

-

0

-

Следовательно, оптимизация невозможна. Получаем .

3.  Оптимизация

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

Конъюнкция

Покрываемый набор из

Количество покрываемых импликант

Множество импликант

1

12

-

2

+

2

13

-

1

+

3

14

-

2

+

4

16

-

1

+

5

23

-

1

+

6

25

-

2

+

7

26

-

1

+

8

34

-

1

+

9

35

-

1

+

10

36

-

0

-

11

45

-

2

+

12

46

-

1

+

13

56

-

1

+

Рассмотрим элементарные конъюнкции первого ранга:

Конъюнкция

Покрываемый набор из

Количество покрываемых импликант

Множество импликант

1

1

15

*

-

2

2

24

*

-

3

3

-

2

+

4

4

24

*

-

5

5

15

*

-

6

6

-

2

+

Построим таблицу покрытия:

1

2

4

1

2

5

1

3

5

1

4

5

1

5

6

2

3

4

2

4

5

2

4

6

3

6

12

14

25

45

Конъюнкции 3 и 6 существенны. Включаем их в окончательное решение. Сокращаем таблицу покрытия.

1

2

4

1

2

5

1

4

5

2

4

5

12

A

14

B

25

C

45

D

Получаем две минимальных ДНФ, любая из которых может быть выбрана в качестве оптимальной. Произвольно выбираем . Получаем .

4.  Оптимизация

Так как функция содержит только конъюнкции второго ранга, то ее оптимизация возможна конъюнкциями первого ранга. Но оптимизация невозможна, так как конъюнкции первого ранга входят в нулевое подмножество функции. Получаем .

Оптимизация функции .

1.  Оптимизация

Так как функция содержит только элементарную конъюнкцию шестого ранга, то ее оптимизация возможна за счет элементарных конъюнкций пятого и меньших рангов. Рассмотрим элементарные конъюнкции пятого ранга:

Конъюнкция

Покрываемый набор из

Количество покрываемых импликант

Множество импликант

1

12345

-

1

+

2

12346

-

1

+

3

12456

-

1

+

4

13456

-

1

+

Рассмотрим элементарные конъюнкции четвертого ранга:

Конъюнкция

Покрываемый набор из

Количество покрываемых импликант

Множество импликант

1

1235

12356

*

-

2

1236

12356

*

-

3

1346

-

1

+

4

1456

1456

*

-

5

2346

23456

*

-

6

2456

23456

*

-

7

3456

23456

*

-

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

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