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

UptoLike

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
74
Шаг 1.Формулу преобразовать так, чтобы в ней были только опера -
ции
, & и ;
Шаг 2. Добиться с помощью законов де Моргана, чтобы знак отри -
цания стоял лишь над отдельными переменными;
Шаг 3. Раскрыть скобки по 1-му дистрибутивному закону
(
)
ACABCBA
=
при построении ДНФ и по 2-му дистрибутивному за -
кону
(
)
(
)
CABABCA
=
при построении КНФ .
Способ 2. (С использованием таблицы истинности ).
Шаг 1. Пусть функция
(
)
n
x,...,x,xf
21
задана таблицей или набором
своих значений. Воспользоваться разложением функции по переменным
n
x,...,x,x
21
:
(
)
()
(
)
(
)
nn
,...,,
n
,...,f&x&...&x&xx,...,x,xf
n
n
σσ
σσσ
σσσ
12121
21
21
∨= ()
при построении ДНФ и
(
)
()
(
)
(
)
nnn
fxxxxxxf
n
n
σσ
σσσ
σσσ
,...,...&,...,,
,...,,
12121
21
21
∨= (∗∗)
при построении КНФ .
Шаг 2. Полученные формулы по возможности упростить с помощью
основных равносильностей алгебры логики высказываний.
()()()
()
()
()()
()
.д.ти;baabba;bababa
;a;bababa
;babab&ab&ababa
;abbaabbaabbaba
;aa,a&a
;
b
a
b
a
====↓
==⊕
===⊕
===↔
=∨=
=
11
10
Пример 1. Методом эквивалентных преобразований для
функции
(
)
(
)
yzyxz,y,xf
=
построить ДНФ и КНФ .
Решение. Применяя основные равносильности и 1-ый дистрибутив-
ный закон , строим ДНФ :
()()() ()()
()()
.yzyxxy
yzxyyyxxyxyzxyyx
yzxyyxyzyxyzyxz,y,xf
∨=
==∨=
==∨↔=⊕=
                                                                        74
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________
     Шаг 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 ) =          ∨          (x
                                         (σ1 ,σ 2 ,...,σ n )
                                                                   σ1
                                                                   1
                                                                        & x 2σ 2 & ... & x σn n & f (σ 1 ,...,σ n ))     (∗)
при построении ДНФ и
       f ( x1 , x 2 , ..., x n ) =           &
                                    (σ 1 ,σ 2 ,...,σ n   )
                                                          (x   σ1
                                                               1    ∨ x σ2 ∨ ... ∨ x nσ ∨ f (σ 1 ,..., σ n ))
                                                                                 2       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
построить ДНФ и КНФ.
      Решение. Применяя основные равносильности и 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 .