Функции алгебры логики. Стасюк В.В. - 11 стр.

UptoLike

ВУЗ: 

ДВФУ | Владивосток

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

Рубрика: 

булевой функции по нескольким переменным). Теорема 2. (О разложении
()
()
(
)
1
11 1 1 1
,..., , ,..., ... ,..., , ,...,
i
ii n i ii n
,...,
i
1
f
xxx x x xf x x
σ
σ
σσ
++
=∧∧∧∨
,
σσ
где дизъюнкция берется по всем возможным наборам
(
)
1
,...,
i
σ
σ
.
Доказательство. Докажем, что формула
()
(
)
()
1
11
,...,
,...,
n
1
11
... ,..., , ,...,
i
i
iiin
x
xx
σ
σσ
Φ=∨ xfxx
σ
σσ
+
∧∧∧
реализует функцию
(
)
1
,...,
n
fx x
. Для этого достаточно на произвольном наборе
()
1
,...,
n
α
α
значений аргументов функции
f
вычислить на этом наборе значение формулы
оно окажется равным функции
Φ
, и если
значению
f
на этом наборе, то из этого следует доказывае
мое утверждение. Действительн
()
()
-
о,
(
)
1
1
1
,.
,...,
n
σσ
αα
Φ=∨
1 11
..,
... ,..., , ,...,
i
i
iiin
f
σ
σ
α α σσα α
+
∧∧∧ =
(
)
(
)
1
111
... ,..., , ,..., ,...,
i
iiin
ff
α
α
1n
α
ααααααα
+
=∧∧∧ =
.
ледствие.
С
()
()
(
)
1
1
11
,..., 1
,..., ... ,...,
n
n
nn
f
fx x x x f
σ
σ
σσ
1n
σ
σ
=
=∧∧∨
,
где дизъюнкция берется по всем наборам
(
)
1
,...,
n
σ
, для которых
(
)
1
,..., 1
n
f
σσ
=
.
Пример 11. Разложим функцию
(, ,) ( )
f
xyz =
переменной
y z xz↓
по
x
.
сначала построим таблицу функции
Для этого
f
:
х у z
y
z
z х
z
↓ х z
()zxz↓
(, ,)
f
xyz
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
1
1
1
0
0
1
1
0
1
0
0
0
1
1
0
0
1
0
1
0
1
0
0
0
0
0
0
1
0
1
0
1
0
0
0
0
1
0
1
1
1
1
0
0
1
1
0
0
Из таблицы видно
) ( 1000 )
, что
(0, ,
f
yz z= и y↓= (1, , ) ( 11 )00
f
yz y
=
= . Используя фор-
улу разложения по переменнойм
x
, находим
(
)
(,,) (0,,) (1,,)
f
xyz xf yz x=∨f yz x y z xy=↓∨
.
Итак,
()
() yz xz x y z xy↓= ↓∨. 
       Теорема 2. (О разложении булевой функции по нескольким переменным).

                 f ( x1 ,..., xi , xi +1 ,..., xn ) =           ∨
                                                         (σ1 ,...,σ i )
                                                                          x1σ1 ∧ ... ∧ xiσ i ∧ f (σ 1 ,..., σ i , xi +1 ,..., xn ) ,


где дизъюнкция берется по всем возможным наборам (σ 1 ,..., σ i ) .
Доказательство. Докажем, что формула

                         Φ ( x1 ,..., xn ) =       ∨
                                               (σ1 ,...,σ i )
                                                                x1σ1 ∧ ... ∧ xiσ i ∧ f (σ 1 ,..., σ i , xi +1 ,..., xn )


реализует функцию f ( x1 ,..., xn ) . Для этого достаточно на произвольном наборе (α1 ,..., α n )
значений аргументов функции f вычислить на этом наборе значение формулы Φ , и если
оно окажется равным значению функции f на этом наборе, то из этого следует доказывае-
мое утверждение. Действительно,

                     Φ (α1 ,..., α n ) =       ∨
                                            (σ1 ,...,σ i )
                                                             α1σ ∧ ... ∧ α iσ i ∧ f (σ 1 ,..., σ i , α i +1 ,..., α n ) =
                                                                  1




                          = α1α1 ∧ ... ∧ α iαi ∧ f (α1 ,..., α i , α i +1 ,..., α n ) = f (α1 ,..., α n ) .
Следствие.

                               f ( x1 ,..., xn ) =               ∨)
                                                       f (σ 1 ,...,σ n = 1
                                                                               x1σ1 ∧ ... ∧ xnσ n f (σ 1 ,..., σ n ) ,


где дизъюнкция берется по всем наборам (σ 1 ,..., σ n ) , для которых f (σ 1 ,..., σ n ) = 1 .
      Пример 11. Разложим функцию f ( x, y , z ) = y (z ↓ xz ) по переменной x . Для этого
сначала построим таблицу функции f :

                     х     у     z     y       z             хz           z ↓ хz          (z ↓ xz )           f ( x, y , z )
                     0     0     0     1       1             0                0              1                     1
                     0     0     1     1       0             0                1              0                     0
                     0     1     0     0       1             0                0              1                     0
                     0     1     1     0       0             0                1              0                     0

                     1     0     0     1       1             0                0                1                   1
                     1     0     1     1       0             1                0                1                   1
                     1     1     0     0       1             0                0                1                   0
                     1     1     1     0       0             1                0                1                   0

Из таблицы видно, что f (0, y, z ) = ( 1000 ) = y ↓ z и f (1, y, z ) = ( 1100 ) = y . Используя фор-
мулу разложения по переменной x , находим

                            f ( x, y, z ) = x f (0, y, z ) ∨ x f (1, y, z ) = x                     ( y ↓ z) ∨ x y .
Итак, y (z ↓ xz ) = x    ( y ↓ z) ∨ x y .

Страницы