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

UptoLike

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

37
Дизъюнкции двух высказываний QP
Ú
соответствует схема с парал-
лельным соединением контактов:
Так как любая функция алгебры логики представима в виде ДНФ
(или КНФ), то для любой булевой функции можно составить соответ-
ствующую схему, а каждой схеме соответствует некоторая формула алгеб-
ры логики, задающая некую булеву функцию.
Две схемы считаются эквивалентными, если через одну их них
проходит ток тогда и только тогда, когда он проходит через другую. Из
двух эквивалентных схем более простой считается та, которая содержит
меньшее число контактов.
Пример 1. Составит РКС для следующей функции:
)).
z
y
(
x
(
)
y
x
(
)
z
y
x
(
f
Ú
®
®
=
Решение. С помощью равносильных преобразований найдем нор-
мальную форму (ДНФ или КНФ):
zxyxyxzxyxyxzyxyxzyxf
Ú
Ú
=
Ú
Ú
Ú
=
®
®
®
=
)()()()(),,(
(ДНФ).
Итак, имеем РКС:
Пример 2. Построить РКС для функции
)
z
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
X
X
Y
Z
Y