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

UptoLike

ВУЗ: 

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

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

Рубрика: 

{
}
:
n
TfPff
∗
∗
∈ =
.
=
x
T
∗
∈
;
x
T
∗
∈
;
x
yxzyzT
∗
∨∨∈
. Пример 24.
Теорема 10. с
T
Клас замкнут.
Доказа н
∗
тельство. Пусть фу кция
1
( ,..., )
n
xx
реализована формулой
( ,...,
n
()
11 1
),..., ( ,..., )
n n
x
x
ϕ
ад
В силу теоремы 1
xx
ϕ ϕ
T
∗
.
н
(
)
111 1
( ,..., ) ( ,..., ),..., (x,..., )
nnnn
fx x x x x
ϕϕ ϕ
∗∗∗ ∗
=
=
n
()
11 1 1
( ,..., ),..., ( ,..., ) ( ,..., )
nn n
x
xxxfx
ϕϕ ϕ
==x
.
Это означает, что
1
( ,..., )
n
f
xxT
∗
∈
.
1
( ,..., )
n
f
xxT
∗
∈
равно
2
2
n
T
∗
= . Теорема 11. Число булевых функций
Доказа
,..., )
nn
тельство. Всякая булева функция
(
f
1
xxP
∈
о на число значений, рав-
ым
Если
( ,..., )
пределе м
2
n
.
1 n
f
xxT∈
, то она определяется половиной своих значений, число кото-
н
∗
рых
1
2
n−
. Таким образом,
1
22
22
n n
T
−
==
.
∗
Пример 25. Число самодвойственных булевых нкций от переменных равно фу 3n =
3
28
2 2 256 16== =.
Лемма 1 (О несамодвойственной функции). Если функция
1
( ,..., )
n
f
xxT
∗
∉
, то из неё
одстановкойп
x
и/или
x
можно получить 0 или 1.
Доказательство. Если
1
( ,..., )
n
f
xxT
∗
∉
, то существует набор
1
( ,..., )
n
α
α
значений аргументов
акой, что т
11
( ,..., ) ( ,..., )
nn
ff
α
ααα
≠
или, что то же самое,
11
( ,..., ) ( ,..., )
nn
ff
α
ααα
=
.
Пусть теперь
()
1
( ) ,...,
n
x
fx x
α
α
ϕ
=
. Тогда
()
(
)
1 1
11
(0) 0 ,...,0 ( ,..., ) ( ,..., ) 1 ,...,1 (1)
n n
nn
ffff
αα
αα
ϕ
αα αα ϕ
=====
.
Таким образом,
(0) (1)
ϕ
ϕ
= , откуда ()x
ϕ
=
0 или ()x
ϕ
=
1 .
Пример 26. Пусть Тогда ( , , ) ( 0100 0101)fxyz= . ( , , ) ( 0101 1101) ( , , )
f
xyz f xyz
∗
=≠.
Имеем, например
,1,1) , на котором (0,1 1f
, набор
(0,1,1)f
∗
=≠= .
ю
(0 ,1) 0
Рассмотрим функци
                                                   T∗ = { f ∈ Pn : f = f ∗ } .

        Пример 24. x ∈ T∗ ; x ∈ T∗ ; xy ∨ xz ∨ yz ∈ T∗ .

        Теорема 10. Класс T∗ замкнут.

Доказательство. Пусть функция f ( x1 ,..., xn ) реализована формулой

                                            ϕ (ϕ1 ( x1 ,..., xn ),..., ϕ n ( x1 ,..., xn ) )
над T∗ . В силу теоремы 1
                                     f ∗ ( x1 ,..., xn ) = ϕ ∗ (ϕ1∗ ( x1 ,..., xn ),..., ϕn∗ ( x1 ,..., xn ) ) =
                                      = ϕ (ϕ1 ( x1 ,..., xn ),..., ϕ n ( x1 ,..., xn ) ) = f ( x1 ,..., xn ) .

Это означает, что f ( x1 ,..., xn ) ∈ T∗ .

                                                                                                                   n
        Теорема 11. Число булевых функций f ( x1 ,..., xn ) ∈ T∗ равно T∗ = 22 .

Доказательство. Всякая булева функция f ( x1 ,..., xn ) ∈ Pn определена числом значений, рав-
ным 2n . Если f ( x1 ,..., xn ) ∈ T∗ , то она определяется половиной своих значений, число кото-
рых 2n −1 . Таким образом,
                                                                  n−1         n
                                                       T∗ = 22 = 22 .

        Пример 25. Число самодвойственных булевых функций от n = 3 переменных равно
    3
  22 = 28 = 256 = 16 .

      Лемма 1 (О несамодвойственной функции). Если функция f ( x1 ,..., xn ) ∉ T∗ , то из неё
подстановкой x и/или x можно получить 0 или 1.

Доказательство. Если f ( x1 ,..., xn ) ∉ T∗ , то существует набор (α1 ,..., α n ) значений аргументов
такой, что
                                       f (α1 ,..., α n ) ≠ f (α1 ,..., α n )
или, что то же самое,
                                       f (α1 ,..., α n ) = f (α1 ,..., α n ) .


                             (               )
Пусть теперь ϕ ( x) = f xα1 ,..., xα n . Тогда


                ϕ (0) = f ( 0α1 ,..., 0α n ) = f (α1 ,..., α n ) = f (α1 ,..., α n ) = f (1α1 ,...,1α n ) = ϕ (1) .

Таким образом, ϕ (0) = ϕ (1) , откуда ϕ ( x) = 0 или ϕ ( x) = 1 .
      Пример 26. Пусть f ( x, y, z ) = ( 0100 0101) . Тогда f ∗ ( x, y, z ) = ( 0101 1101) ≠ f ( x, y, z ) .
Имеем, например, набор (0,1,1) , на котором f (0,1,1) = 0 ≠ 1 = f ∗ (0,1,1) .
      Рассмотрим функцию

Страницы