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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

24
Решение. Применяя основные равносильности и 1-й дистрибутив-
ный закон, строим ДНФ:
( ) ( ) ( ) ( )( )
( )( )
.yzyxxy
yzxyyyxxyxyzxyyx
yzxyyxyzyxyzyxz,y,xf
ÚÚ=
=ÚÚÚÚ=ÚÚÚ=
=Ú®®=Ú«=®Å=
Применяя 2-й дистрибутивный закон в
полученной ДНФ, построим КНФ для данной
функции.
(
)
(
)
(
)
(
)
( )( )( )( )
( )( ) ( )( )
( )( )( )( )
.
,,
yyxzyxyzxxy
yzyxyzxyyzyxxy
yzyyyxxyxx
yzyxyxxyyzyxxyzyxf
ÚÚÚÚÚÚÚ=
=ÚÚÚÚ=ÚÚÚ=
=ÚÚÚÚÚ=
=
Ú
Ú
Ú
=
Ú
Ú
=
Учитывая, что
1
1
=
Ú
=
Ú
Ú
x
y
y
x
, полу-
чим другую КНФ, равносильную построенной:
fx,y,z=xyxyzxyz
∨ ∨ ∨ ∨ ∨
.
Пример 2. Построить ДНФ и КНФ для функции
(
)
11001011
=
f .
Решение. Строим таблицу истинности для функции, зависящей от
трех переменных, т.к. длина ее двоичного набора равна
(
)
.n 328
3
=
=
По формуле (*) с учетом, что
K
1
K&
=
,
0
0
K&
=
, имеем
(
)
.1&
1&0&0&1&
0&1&1&,,
1
111
011101001110
010100000
ДНФzyxzxyzyxzyxzyxzyx
zyxzyxzyxzyx
zyxzyxzyxzyxf
-ÚÚÚÚ=Ú
ÚÚÚÚÚ
ÚÚÚ=
Учитывая, что
(
)
cbacaba
Ú
=
Ú
, можно получить другие ДНФ для
данной функции:
(
)
(
)
( ) ( )
.ДНФyxzyxyx
zzxyzyxzzyx
zyxzyxyzxzyxzyxf
2
-ÚÚ=
=ÚÚÚÚ=
=
Ú
Ú
Ú
Ú
=
(
)
( )
( )( )
( )
.
3
ДНФyxzxyx
yxzyx
yxzyyyx
xyzyyx
yxzyxyxf
-ÚÚ=
ÚÚ=
ÚÚÚ=
=ÚÚ=
=
Ú
Ú
=
x y z f
0 0 0 1
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 1 
     Решение. Применяя основные равносильности и 1-й дистрибутив-
ный закон, строим ДНФ:
      f � x , y , z � � � x � y � � yz � � x � y � � yz � � x � y �� y � x � � yz �
                      � � x � y �� y � x � � yz � x y � xx � yy � xy � yz �
                      � xy � x y � yz .
                                                 Применяя 2-й дистрибутивный закон в
  x       y          z       f         полученной ДНФ, построим КНФ для данной
  0       0          0       1         функции.
  0       0          1       1          f � x , y, z � � � xy � x y � � yz � � xy � x �� xy � y � � yz �
  0       1          0       0
                                       � � x � x �� y � x �� x � y �� y � y � � yz �
  0       1          1       1
  1       0          0       0         � � y � x �� x � y � � yz � � y � x � yz �� x � y � yz � �
  1       0          1       0         � � y � x �� x � z � y �� x � y � z �� x � y � y �.
  1       1          0       1
  1       1          1       1                   Учитывая, что x � y � y � x � 1 � 1 , полу-
                                       чим другую КНФ, равносильную построенной:
                          f ( x, y,z ) = ( x ∨ y )( x∨ y ∨ z )( x ∨ y∨ z ) .

      Пример 2. Построить ДНФ и КНФ для функции f � �11 01 0 011� .
      Решение. Строим таблицу истинности для функции, зависящей от
трех переменных, т.к. длина ее двоичного набора равна 8 � 2 3 �n � 3�.
      По формуле (�) с учетом, что K& 1 � K , K& 0 � 0 , имеем
          f � x, y, z � � x 0 y 0 z 0 & 1 � x 0 y 0 z 1 & 1 � x 0 y 1 z 0 & 0 �
           � x 0 y1 z1 & 1 � x1 y 0 z 0 & 0 � x1 y 0 z1 & 0 � x1 y1 z 0 & 1 �
         � x 1 y 1 z 1 & 1 � x y z � x y z � x y z � xy z � x y z � ДНФ1 .
     Учитывая, что a b � a c � a �b � c � , можно получить другие ДНФ для
данной функции:
                       f � � x y z � x y z � � x yz � � x y z � x y z � �
                         � x y � z � z � � x y z � xy� z � z � �
                         � x y � x y z � x y � ДНФ2 .

                               f � � x y� x y z � � x y �
                                 � x � y � y z � � xy �
                                 � x � y � y �� y � z � � x y
                                 � x� y � z� � x y
                                 � x y � x z � x y � ДНФ3 .


                                                24

Страницы