Дискретная математика. Элементы теории, задачи и упражнения. Часть 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
Дизъюнкции двух высказываний P � Q соответствует схема с парал-
лельным соединением контактов:

                                          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 ) � ( xy � xz ) � xy � xy � xz
(ДНФ).
         Итак, имеем РКС:

                                                 Y
                                  X



                                                 Y
                                  X



                                  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




                                          37

Страницы