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

UptoLike

ВУЗ: 

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

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

Рубрика: 

(
)
(
)
0
() ,
11
, ,,
x
fxx
ϕ
=x fxxx=
.
Находим,
(
)
(
)
(0) 0,0,0 1,0,0 0ff
ϕ
===
,
(
)
(
)
(1) 1,1,1 0,1,1 0ff
ϕ
=
==
.
Итак, получаем
()
,,
f
xxx0=
. Отметим, что в данном примере функцию 1 получить нельзя.
Замечание. Лемма о несамодвойственной функции ничего не говорит о том, какую
у можно пол
4. Класс
именно констант учить и можно ли получить обе константы.
T
≤
монотонных функций:
{
}
:()()
n
fP f fT
α
βαβ
=∈ ≤⇒ ≤
,
≤
где
1
( ,..., )
n
α
αα
=
,
1
( ,..., )
n
ββ
=
и
ii
α
βαβ
≤
⇔≤
для всех ...,in 1,
=
.
Пример 27.
T
≤
∈0
;
T
≤
∈1
;
x
T
≤
∈
;
x
yT
≤
∧
∈
;
x
yT
≤
∨∈
.
Теорема 12. с
T
Клас замкнут.
Доказа н
≤
тельство. Пусть фу кция
1
( ,..., )
n
f
xx
реализована формулой
( ,...,
n
()
11 1
),..., ( ,..., )
n n
x
x
ϕ
над
Если
xx
ϕ ϕ
T
≤
.
11
( ,..., ) ( ,..., )
nn
α
αββ
≤
, то
(
)
111 1
( ,..., ) ( ,..., ),..., ( ,..., )
nnn
f
αα
n
ϕαα ϕαα
≤
ϕ
=
()
(
)
()
(
)
11 1 1
,..., ,..., ,..., ,...,
nn n
f
n
ϕ
ϕββ ϕββ ββ
≤=
.
Это означает, что
1
( ,..., )
n
f
xxT
≤
∈
.
Лемма 2 (О й немонотонно функции). Если функция
1
( ,..., )
n
f
xxT
≤
∉
, то из неё подста-
овкой
0, 1 и
н
x
можно получить
x
.
Доказательство. Если
1
( ,...,
n
1
( ,..., )
n
α
α
и
()
1
,...,
n
β
β
)
f
xxT
≤
∉
, то существуют наборы значе-
ий аргументов такие, что
1
) ,...,
nn
н
1
( ,...,
()
(
)
11
( ,..., ) ,...,
nn
ff
α
αβ
>
αββ
≤
и
α
β
.
этом случае
n
f
В
и
(
)
1
,..., 0
n
f
ββ
=
1
( ,..., ) 1
α
α
=
.
Пусть теперь
()
1
( ) ,...,
n
xf
ϕ
χχ
=
, где 
                                           ϕ ( x) = f ( x 0 , x1 , x1 ) = f ( x , x, x ) .
Находим,
                                           ϕ (0) = f ( 0, 0, 0 ) = f (1, 0, 0 ) = 0 ,
                                             ϕ (1) = f ( 1,1,1) = f ( 0,1,1) = 0 .

Итак, получаем 0 = f ( x , x, x ) . Отметим, что в данном примере функцию 1 получить нельзя.
       Замечание. Лемма о несамодвойственной функции ничего не говорит о том, какую
именно константу можно получить и можно ли получить обе константы.


                                            4. Класс T≤ монотонных функций:

                                        T≤ = { f ∈ Pn : α ≤ β ⇒ f (α ) ≤ f ( β )} ,

где α = (α1 ,..., α n ) , β = ( β1 ,..., β n ) и α ≤ β ⇔ α i ≤ β i для всех i = 1, ..., n .
         Пример 27. 0 ∈ T≤ ; 1 ∈ T≤ ; x ∈ T≤ ; x ∧ y ∈ T≤ ; x ∨ y ∈ T≤ .

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

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

                                            ϕ (ϕ1 ( x1 ,..., xn ),..., ϕ n ( x1 ,..., xn ) )

над T≤ . Если (α1 ,..., α n ) ≤ ( β1 ,..., β n ) , то

                                 f (α1 ,..., α n ) = ϕ (ϕ1 (α1 ,..., α n ),..., ϕ n (α1 ,..., α n ) ) ≤
                                    ≤ ϕ (ϕ1 ( β1 ,..., β n ) ,..., ϕ n ( β1 ,..., β n ) ) = f ( β1 ,..., β n ) .

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

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

Доказательство. Если f ( x1 ,..., xn ) ∉ T≤ , то существуют наборы (α1 ,..., α n ) и ( β1 ,..., β n ) значе-
ний аргументов такие, что

                            (α1 ,..., α n ) ≤ ( β1 ,..., β n ) и      f (α1 ,..., α n ) > f ( β1 ,..., β n ) .
В этом случае
                                         f (α1 ,..., α n ) = 1 и        f ( β1 ,..., β n ) = 0 .

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

Страницы