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

UptoLike

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
88
Так как любая функция алгебры логики представима в виде ДНФ
(или КНФ ), то для любой булевой функции можно составить соответст -
вующую схему, а каждой схеме соответствует некоторая формула алгебры
логики, задающая некую булеву функцию .
Две схемы считаются эквивалентными, если через одну их них
проходит ток тогда и только тогда, когда он проходит через другую. Из
двух эквивалентных схем более простой считается та, которая содержит
меньшее число контактов.
Пример 1. Составит РКС для следующей функции:
)).
z
y
(
x
(
)
y
x
(
)
z
,
y
,
x
(
f
=
Решение. С помощью равносильных преобразований найдем
нормальную форму (ДНФ или КНФ ):
zxyxyxzxyxyxzyxyxzyxf ==→= )()()()(),,(
( ДНФ ).
Итак, имеем РКС:
Пример 2. Построить РКС для функции
)
,
y
,
x
f
, если
1
1
0
0
1
1
0
0
1
1
1
1
1
=
=
=
=
)
,
,
(
f
)
,
,
(
f
)
,
,
(
f
)
,
,
(
f
,
а остальные значения функции равны нулю .
Решение. Составим СДНФ для данной функции и затем упростим :
z
x
xy
)
y
y
(
z
x
)
z
z
(
xy
z
y
x
yz
x
z
xy
xyz
)
z
,
y
,
x
(
f
=
=
=
Тогда имеем следующую РКС:
P
T
1
T
2
Q
X
Z
X Y
X
X
X
Y
Z
Y