Дискретная математика. Громов Ю.Ю - 31 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

31
Поэтому в качестве минимальной ДНФ можно выбрать любую из них.
Выберем, например, первую:
f
min
(x
1
, x
2
, x
3
) =
323132
xxxxxx ∨∨
.
Получением минимальной ДНФ булевой функции заканчивается
второй этап метода Квайна, на нём сложность ДНФ взятой в качестве
примера булевой функции уменьшилась от 8 до 6.
Таким образом, в результате минимизации булевой функции f (x
1
, x
2
,
x
3
) |
1
= ∨ (0, 3, 4, 6, 7) в классе ДНФ сложность L(f) уменьшилась с 15 до 6.
Дальнейшее уменьшение сложности выражения, определяющего за-
данную функцию, возможно при переходе из класса ДНФ в класс ско-
бочных форм. Выражение, определяющее булеву функцию, называется
скобочной формой, если кроме первичных термов и знаков операций
конъюнкции и дизъюнкции в него входят скобки (, ).
Для рассматриваемой функции сложность её минимальной ДНФ,
равная 6, может быть уменьшена до 5 в результате перехода в скобочную
форму с применением закона дистрибутивности конъюнкции относи-
тельно дизъюнкции:
f
b
(x
1
, x
2
, x
3
) =
32123
)( xxxxx ∨∨
.
Задачи и упражнения
1. Представить таблицей, совершенной ДНФ и гиперкубом булеву
функцию, заданную перечислением десятичных эквивалентов:
а) f (x
1
, x
2
) |
1
= ∨ (0, 2, 3);
б) f (x
1
, x
2
, x
3
) |
1
= ∨ (1, 4, 5, 7);
в) f (x
1
, x
2
, x
3
, x
4
) |
1
= ∨ (0, 2, 6, 9, 10, 11, 14).
2. Минимизировать методом Квайна трёхместную булеву функцию:
а) f (x
1
, x
2
, x
3
) |
1
= ∨ (0, 1, 7);
б) f (x
1
, x
2
, x
3
) |
1
= ∨ (0, 4, 5, 7);
в) f (x
1
, x
2
, x
3
) |
1
= ∨ (0, 4, 5, 6, 7);
г) f (x
1
, x
2
, x
3
) |
1
= ∨ (0, 1, 2, 4, 5, 7);
д) f (x
1
, x
2
, x
3
) |
1
= ∨ (0, 1, 2, 3, 6, 7);
е) f (x
1
, x
2
, x
3
) |
1
= ∨ (0, 1, 2, 3, 4, 6, 7).
3. Минимизировать методом Квайна четырёхместную булеву
функцию:
а) f (x
1
, x
2
, x
3
, x
4
) |
1
= ∨ (4, 5, 9, 11, 13, 15);
б) f (x
1
, x
2
, x
3
, x
4
) |
1
= ∨ (0, 1, 4, 5, 6, 7, 14, 15);
в) f (x
1
, x
2
, x
3
, x
4
) |
1
= ∨ (0, 2, 4, 6, 8, 10, 11, 12, 14);
г) f (x
1
, x
2
, x
3
, x
4
) |
1
= ∨ (0, 4, 8, 9, 10, 11, 12, 13, 14, 15).

Страницы