Дискретная математика. Элементы теории задачи и упражнения. Часть 2. Булгакова И.Н - 33 стр.

UptoLike

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
79
Определение 5. Сокращенной ДНФ функции
f
называется дизъ -
юнкция всех простых импликантов функции
f
.
Сокращенная ДНФ определяется однозначно для функции
f
.
Метод построения сокращенной ДНФ функции
f
Шаг 1. Построить ДНФ для функции
f
.
Шаг 2. Производить операцию обобщенного склеивания
212121
KKKXXKKXXK =∨
до тех пор, пока это возможно.
Шаг 3. Производить операцию поглощения
1211
KKKK
=
.
В результате приходим к сокращенной ДНФ , учитывая, что 0
11
=KK
и
111
KKK
=
.
Пример 2. Построить сокращенную ДНФ для функции
(
)
(
)
zyxyxf
=
.
Решение. Раскрывая скобки по 1-му дистрибутивному закону, полу -
чаем ДНФ ; затем применяем операцию поглощения:
(
)
(
)
() ()
()
xzyxzyzy
xzyzyyxyzxzyxyyx
yzxzyyxyyxxxzyxyxf
=∨=
==∨=
=
=
=
сокращенная ДНФ .
Определение 6. ДНФ функции
(
)
n
x,...,x,xf
21
называется совершен-
ной, если она составлена из попарно различных э. к . ранга
n
, т.е. формула
вида:
(
)
()
(
)
n
n
n
,...,,f
n
x&...&x&xx,...,x,xf
σσσ
σσσ
21
21
21
1
21
=
∨=
,
где дизъюнктивная сумма берется по всем наборам
(
)
n
,...,,
σ
σ
σ
21
, на кото-
рых
(
)
1
21
=
n
,...,,f
σ
σ
σ
. Ясно, что функция
(
)
n
x,...,x,xf
21
отлична от тож -
дественного нуля.
В следующем параграфе подробно рассматриваются совершенные
нормальные формы и их нахождение, имеющие важное значение в
приложениях .
ЗАДАЧИ И УПРАЖНЕНИЯ
1. Для функции
(
)
11110100
=
f построить несколько ДНФ . Указать крат-
чайшую, минимальную. Среди э.к. определить, какие являются