Дискретная математика. Кулаков Ю.В - 27 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

– – 0 – –,
I
макс 4
= – – – – – 1 – и простые импликанты
51
xx ,
6
x .
Дизъюнкция простых импликант дает сокращенную ДНФ булевой функции, являющуюся уже пол-
ностью определенной:
f
с
(x
1
, x
2
, ... , x
7
) =
6514251
xxxxxxx ∨∨∨ =
6425151
xxxxxxx ∨∨∨ =
=
64251
xxxxx ∨∨ .
Единичная область функции f
с
содержит единичную область функции f, нулевая область функции f
с
содержит нулевую область функции f.
Выделение максимальных единичных интервалов и построение сокращенной ДНФ слабоопреде-
ленной булевой функции является первым этапом минимизации. Второй этап заключается в получении
тупиковых ДНФ этой функции и выборе среди них минимальной ДНФ.
Тупиковой ДНФ слабоопределенной булевой функции называется ДНФ, не определяющая эту функ-
цию с точностью до неопределенной области при вычеркивании хотя бы одного первичного терма. Ту-
пиковые ДНФ булевой функции получаются в результате покрытия столбцов строками импликантной
таблицы (таблицы Квайна) – двумерной таблицы, каждой строке которой соответствует максимальный
единичный интервал, столбцу – единичный интервал, а на пересечении i-й строки с j-м столбцом нахо-
дится единица, если j-й единичный интервал входит в i-й максимальный интервал, в противном случае –
ноль.
Для рассматриваемого примера импликантная таблица имеет следующий
вид.
Таблица 10
Единичный интервал
Максимальные
интервалы
0 – 0 – 0 –
0
11 – 0 –
01
0 – – 001
–
a
0 – – – 0 – – 1 0 1
b
– 1 – 0 – – – 0 1 0
c
– – – – – 1 – 0 0 1
Таблица имеет одно покрытие: ab (a ∨ c) = a (a ∨ c) b = ab. Этому покрытию соответствует множе-
ство максимальных единичных интервалов {I
макс
} = {0 – – – 0 – –, – 1 – 0 – – –} и единственная тупико-
вая ДНФ
f
т
(x
1
, x
2
, ..., x
7
) =
4251
xxxx ∨ ,
которая и является минимальной
f
мин
(x
1
, x
2
, ..., x
7
) =
4251
xxxx ∨ .
Задачи и упражнения
1 Получить совершенную, сокращенную и минимальную ДНФ булевой функции, заданной пере-
числением десятичных эквивалентов:
а) f (x
1
, x
2
, x
3
)|
1
= ∨(0, 4, 5, 7);
б) f (x
1
, x
2
, x
3
)|
1
= ∨(0, 1, 3, 5, 7);
в) f (x
1
, x
2
, x
3
)|
1
= ∨(0, 2, 3, 4, 5);
г) f (x
1
, x
2
, x
3
)|
1
= ∨(0, 1, 4, 5, 6, 7);
д) f (x
1
, x
2
, x
3
, x
4
)|
1
= ∨(6, 7, 8, 10, 14);
е) f (x
1
, x
2
, x
3
, x
4
)|
1
= ∨(0, 1, 4, 5, 9, 11, 13, 15);
ж) f (x
1
, x
2
, x
3
, x
4
)|
1
= ∨(5, 7, 8, 10, 11, 13, 15);
з) f (x
1
, x
2
, x
3
, x
4
)|
1
= ∨(0, 4, 5, 6, 7, 12, 13, 14, 15).
2 Получить сокращенную и минимальную ДНФ слабоопределенной булевой функции, заданной
перечислением единичных и нулевых интервалов:

Страницы