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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

23
(
)
( )( )
( )( )( )
.zxzyyxzxK
,zyyxzxK
,yxzxK
ÚÚÚ=
ÚÚ=
Ú
=
3
2
1
Рассмотрим два способа построения ДНФ и КНФ.
Способ 1. (Метод эквивалентных преобразований). Пусть булева
функция
(
)
n
x,...,x,xf
21
задана формулой. Алгоритм построения ДНФ и
КНФ состоит в следующем:
Шаг 1. Формулу преобразовать так, чтобы в ней были только опера-
ции
Ú
, & и ù.
Шаг 2. Добиться с помощью законов де Моргана, чтобы знак отри-
цания стоял лишь над отдельными переменными.
Шаг 3. Раскрыть скобки по 1-му дистрибутивному закону
ABC

при построении ДНФ и по 2-му дистрибутивному
закону
(
)
(
)
CABABCA
Ú
Ú
=
Ú
при построении КНФ.
Способ 2. (С использованием таблицы истинности).
Шаг 1. Пусть функция
(
)
n
x,...,x,xf
21
задана таблицей или набором
своих значений. Воспользоваться разложением функции по переменным
n
x,...,x,x
21
:
(
)
( )
(
)
(
)
nn
,...,,
n
,...,f&x&...&x&xx,...,x,xf
n
n
ss
s
ss
sss
12121
21
21
Ú= (*)
при построении ДНФ и
(
)
( )
(
)
(
)
n
n
n
n
n
fxxxxxxf
s
s
sss
sss
,...,...&,...,,
1
2
2
1
1
,...,
2
,
1
21
Ú
Ú
Ú
Ú
=
(**)
при построении КНФ.
Шаг 2. Полученные формулы по возможности упростить с помощью
основных равносильностей алгебры логики высказываний.
( )( ) ( )
( )
( )
( ) ( )
( )
.д.ти;baabba;bababa
;a;bababa
;babab&ab&ababa
;abbaabbaabbaba
;aa,a&a
;
b
a
b
a
Ú==½=Ú=¯
=ÚÚ=Å
ÚÚ=Ú=«=Å
Ú=ÚÚ=®®=«
=Ú=
Ú
=
®
11
10
Пример 1. Методом эквивалентных преобразований для функции
(
)
(
)
yzyxz,y,xf
®
Å
=
построить ДНФ и КНФ. 
                                  K 1 � x z � x � y �,
                                  K 2 � x z � x � y �� y � z �,
                                  K 3 � x z � x � y �� y � z �� x � z �.

      Рассмотрим два способа построения ДНФ и КНФ.
      Способ 1. (Метод эквивалентных преобразований). Пусть булева
функция f � x1 , x 2 , ... , x n � задана формулой. Алгоритм построения ДНФ и
КНФ состоит в следующем:
      Шаг 1. Формулу преобразовать так, чтобы в ней были только опера-
ции � , & и �.
      Шаг 2. Добиться с помощью законов де Моргана, чтобы знак отри-
цания стоял лишь над отдельными переменными.
      Шаг 3. Раскрыть скобки по 1-му дистрибутивному закону
A B  C   AB  AC при построении ДНФ и по 2-му дистрибутивному
закону A � BC � � A � B �� A � C � при построении КНФ.

         Способ 2. (С использованием таблицы истинности).
         Шаг 1. Пусть функция f � x1 , x 2 , ... , x n � задана таблицей или набором
своих значений. Воспользоваться разложением функции по переменным
x1 , x 2 , ... , x n :
             f � x1 , x 2 , ... , x n � � � � �� x1� 1 & x 2� 2 & ... & x n� n & f �� 1 ,...,� n �� (�)
                                        � 1 ,� 2 ,...,� n

при построении ДНФ и
       f � x1 , x 2 , ... , x n � �         &
                                      ��1 ,� 2 ,...,� n   �
                                                           �x   �1
                                                                1
                                                                     � x 2� 2 � ... � x n� n � f �� 1 ,..., � n ��   (��)
при построении КНФ.
     Шаг 2. Полученные формулы по возможности упростить с помощью
основных равносильностей алгебры логики высказываний.
               a � b � a � b;
               a & a � 0 , a � a � 1;
                        a � b � �a � b ��b � a � � �a � b ��b � a � � a b � ab ;
                                                            �
                        a � b � a � b � a & b � �a & b � � �a � b � a � b ;�                        �        �
                        a � b � a b � ab ;                           a � 1 � 1;
                        a � b � a � b � a b ; a�b � ab � a � b ; и т .д .

     Пример 1. Методом эквивалентных преобразований для функции
                      f � x , y , z � � � x � y � � yz
построить ДНФ и КНФ.


                                                                      23

Страницы