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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
68
1
x
2
x
3
x
)x,x,x(f
321
1
x
2
x
…
1−n
x
n
x )x,...,x,x(f
n21
0 0 0 1 0 0 …
0 0
),,...,,(f 0000
0 0 1 1 0 0 …
0 1
),,...,,(f 1000
0 1 0 1 0 0 …
1 0
),,...,,(f 0100
0 1 1 0 0 0 …
1 1
),,...,,(f 1100
1 0 0 1 …
…
…
… … …
1 0 1 0 1 1 …
0 1
),,...,,(f 1011
1 1 0 0 1 1 …
1 0
),,...,,(f 0111
1 1 1 0 1 1 …
1 1
),,...,,(f 1111
Рис. 1
Рис. 2
При фиксированном порядке расположения наборов )...,,,(
n
α
α
α
21
в
таблице истинности всякая булева функция однозначно задается набором
своих значений. В нашем примере этот набор имеет вид
).
(
f
=
Заметим, что множество истинности
f
E , задающее функцию
)x,...,x,x(f
n21
, представляет собой
n
-местное отношение
ϕ
на множе-
стве
E
. Оно задает булеву функцию по правилу :
()
(
)
()
∉
∈
=
.,...,,åñëè,
,...,,åñëè,
,...,,f
n
n
n
ϕααα
ϕααα
ααα
21
21
21
0
1
И наоборот, булева функция )x,...,x,x(f
n21
однозначно определяет
множество истинности
(
)
(
)
}
1
2121
==
nnf
,...,,f,...,,fE αααααα .
В случае описанного выше примера
(
)
(
)
(
)
(
)
.,,,E
f
001010100000
=
Имеет место
Теорема. Всякая булева функция представима в виде формулы алгебры
логики через операции
&
,
∨
и , и это представление таково:
(
)
()
(
)
(
)
nmmm
,...,
n
x...,,x,,...,,f&x&...&x&xx...,,xf
m
m
121211
21
1
+∨
= σσσ
σσσ
σσ
,
где
(
)
m
,...,,
σ
σ
σ
21
— различные двоичные наборы значений пе -
ременных
iin
xx,nm,x...,,x
i
=≤≤
σ
1
1
, если 1
=
i
σ
,
ii
xx
i
=
σ
, если 0
=
i
σ
,
m
...,
,
i
=
.
Приведенная выше в примере функция
(
)
321
x,x,xf представима
формулой: 
                                                            68
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________


x1    x2    x3        f ( x1 , x 2 , x 3 )             x1   x2    …      x n−1       xn     f ( x1 , x 2 ,..., x n )
 0    0     0                 1                    0 0            …       0         0          f ( 0 ,0 ,...,0 ,0 )
 0    0     1                 1                    0 0            …       0         1          f ( 0 ,0 ,...,0 ,1 )
 0    1     0                 1                    0 0            …       1         0          f ( 0 ,0 ,...,1,0 )
 0    1     1                 0                    0 0            …       1         1           f ( 0 ,0 ,...,1,1 )
 1    0     0                 1                    … …            …       …        …                 …
 1    0     1                 0                    1 1            …       0         1          f ( 1,1,...,0 ,1 )
 1    1     0                 0                    1 1            …       1         0          f ( 1,1,...,1,0 )
 1    1     1                 0                    1 1            …       1         1          f ( 1,1,...,1,1 )
                Рис. 1                                                           Рис. 2

         При фиксированном порядке расположения наборов ( α 1 ,α 2 ,...,α n ) в
таблице истинности всякая булева функция однозначно задается набором
своих значений. В нашем примере этот набор имеет вид f =( 111 01 0 0 0 ).
         Заметим, что множество истинности E f , задающее функцию
 f ( x1 , x 2 ,..., x n ) , представляет собой n -местное отношение ϕ на множе-
стве E . Оно задает булеву функцию по правилу:
                                                    �1, åñëè (α 1 ,α 2 , ... ,α n ) ∈ϕ
                          f (α 1 ,α 2 , ... ,α n ) =�
                                                    �0 , åñëè (α 1 ,α 2 , ... ,α n )∉ϕ .
         И наоборот, булева функция f ( x1 , x 2 ,..., x n ) однозначно определяет
множество истинности E f ={ f (α 1 ,α 2 , ... ,α n ) f (α 1 ,α 2 , ... ,α n ) =1}.
       В случае описанного выше примера
                     E f ={(0 0 0), (0 0 1), (0 1 0 ), (1 0 0)}.
       Имеет место

Теорема. Всякая булева функция представима в виде формулы алгебры
         логики через операции ∨, & и �, и это представление таково:
           f ( x1 , ..., x n ) =       ∨ ) (x          & x 2σ & ... & x mσ & f (σ 1 ,σ 2 ,...,σ m , x m +1 , ..., x n ))
                                                  σ1         2             m
                                                  1
                                   (σ1 ,...,σ m
                                                    ,
             где (σ 1 ,σ 2 ,...,σ m ) — различные двоичные наборы значений пе-
             ременных           x1 , ..., x n , 1 ≤ m ≤n , x iσ = x i , если σ i =1 ,
                                                                                 i




              x iσ = x i , если σ i =0 , i =1, ..., m .
                  i




     Приведенная выше в примере функция f (x1 , x 2 , x 3 ) представима
формулой:

Страницы