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

UptoLike

ВУЗ: 

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

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

Рубрика: 

Теорема 6. К
T
ласс замкнут.
Доказа о некоторый класс замкнут, достаточно показать, что
сли функция реализована в виде формулы над
, то она принадлежит Доказать, что
,
0
тельство. Чтобы д казать, что F
е
F F .
произвольная формула обладает указанным свойством можно с помощью индукции по
структуре формулы и глубине вложенности в неё функций класса
F .
Итак, пусть функция
1
( ,..., )
n
f
xx
реализована формулой
(
)
11 1
( ,..., ),..., ( ,..., )
nn n
x
xxx
ϕϕ ϕ
над
0
T
. Тогда
(
)
(0,..., (0,..., 0),..., (0,...,0)
n
f
ϕ ϕ
1
0) (0,..., 0) 0
ϕϕ
===
.
По определению класса
это означает, что
0
T
10
( ,..., )
n
f
xxT
∈
.
Теорема 7. Число улевых функций б
10
( ,..., )
n
21
0
2
n
T
−
=
.
xxT
∈
равно
f
Доказа нных можно р пары функций, значения
оторых различаются только на нулевом наборе. Поскольку из каждой пары толь-
к
тельство. Все функции от
n
переме азбить на
к значением
ко одна функция из класса
0
T
, то та их функций будет ровно половина:
2
21
2
2
n
n
n
P
T
0
22
−
===
.
(При
указанную в доказательстве пару составляю , например, функции и
(см. таблицу 2)).
2. Класс функций, сохраняющих 1:
2n =
т (0000)=0
(1000)xy↓=
1
T
{
}
1
: (1,...,1) 1
n
TfPf=∈ =
.
1
T∈1
;
1
x
T∈
;
1
yT∧∈
;
1
yT∨∈
;
1
x
yT→∈
. Пример 23.
Теорема 8. К
T
ласс замкнут.
Доказа у
,..., )
n
1
тельство. Пусть ф нкция
(
1
f
xx
реализована формулой
( ,...,
n
()
11 1
),..., ( ,..., )
n n
x
x
ϕ
ад
Тогда
xx
ϕ ϕ
1
T
.
н
(
)
1
(1,...,1) (1,...,1),..., (1,...,1) (1,...,1) 1
n
f
ϕϕ ϕ ϕ
===
.
Это означает, что
11
( ,..., )
n
f
xx∈
.
T
Идентично доказательству теоремы 7 доказывается
Теорема 9. Число булевых функций
11
( ,..., )
n
f
xxT
∈
21
1
2
n
T
−
=
. равно
3. Класс
T
∗
самодвойственных функций: 
        Теорема 6. Класс T0 замкнут.

Доказательство. Чтобы доказать, что некоторый класс F замкнут, достаточно показать, что
если функция реализована в виде формулы над F , то она принадлежит F . Доказать, что
произвольная формула обладает указанным свойством, можно с помощью индукции по
структуре формулы и глубине вложенности в неё функций класса F .
      Итак, пусть функция f ( x1 ,..., xn ) реализована формулой ϕ (ϕ1 ( x1 ,..., xn ),..., ϕ n ( x1 ,..., xn ) )
над T0 . Тогда
                             f (0,..., 0) = ϕ (ϕ1 (0,..., 0),..., ϕ n (0,..., 0) ) = ϕ (0,..., 0) = 0 .

По определению класса T0 это означает, что f ( x1 ,..., xn ) ∈ T0 .

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

Доказательство. Все функции от n переменных можно разбить на пары функций, значения
которых различаются только значением на нулевом наборе. Поскольку из каждой пары толь-
ко одна функция из класса T0 , то таких функций будет ровно половина:

                                                                   n
                                                        Pn 22     n
                                               T0 =       =   = 22 −1 .
                                                        2   2

(При n = 2 указанную в доказательстве пару составляют, например, функции 0 = (0000) и
 x ↓ y = (1000) (см. таблицу 2)).


                                     2. Класс T1 функций, сохраняющих 1:

                                           T1 = { f ∈ Pn : f (1,...,1) = 1} .

        Пример 23. 1 ∈ T1 ; x ∈ T1 ; x ∧ y ∈ T1 ; x ∨ y ∈ T1 ; x → y ∈ T1 .

        Теорема 8. Класс T1 замкнут.

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

                                        ϕ (ϕ1 ( x1 ,..., xn ),..., ϕ n ( x1 ,..., xn ) )
над T1 . Тогда
                                f (1,...,1) = ϕ (ϕ1 (1,...,1),..., ϕ n (1,...,1) ) = ϕ (1,...,1) = 1 .

Это означает, что f ( x1 ,..., xn ) ∈ T1 .
      Идентично доказательству теоремы 7 доказывается
                                                                                                  n −1
        Теорема 9. Число булевых функций f ( x1 ,..., xn ) ∈ T1 равно T1 = 22                            .
                                   3. Класс T∗ самодвойственных функций:

Страницы