Дискретная математика. Элементы теории задачи и упражнения. Часть 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
                                           88
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________


     Так как любая функция алгебры логики представима в виде ДНФ
(или КНФ), то для любой булевой функции можно составить соответст-
вующую схему, а каждой схеме соответствует некоторая формула алгебры
логики, задающая некую булеву функцию.

                                       P
       T1                                                         T2
                                       Q
      Две схемы считаются эквивалентными, если через одну их них
проходит ток тогда и только тогда, когда он проходит через другую. Из
двух эквивалентных схем более простой считается та, которая содержит
меньшее число контактов.

        Пример 1. Составит РКС для следующей функции:
                          f ( x , y , z ) =( x → y ) → ( x ( y ∨ z )).
        Решение. С помощью равносильных преобразований найдем
нормальную форму (ДНФ или КНФ):
 f ( x, y, z ) =( x → y ) → x ( y → z ) =( x ∨ y ) ∨ ( x y ∨ x z ) = xy ∨ x y ∨ x z
(ДНФ).
        Итак, имеем РКС:
                                   X
                                                  Y

                                   X
                                                  Y


                                   X              Z



       Пример 2. Построить РКС для функции f ( x , y , z ) , если
                      f ( 1,1,1 ) = f ( 1,1,0 ) = f ( 0 ,1,1 ) = f ( 0 ,0 ,1 ) =1 ,
а остальные значения функции равны нулю.
       Решение. Составим СДНФ для данной функции и затем упростим:
    f ( x , y , z ) = xyz ∨ xyz ∨ xyz ∨ xyz = xy( z ∨ z ) ∨ xz ( y ∨ y ) = xy ∨ xz
       Тогда имеем следующую РКС:

                                       X                 Y



                                       X
                                                         Z

Страницы