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

UptoLike

ВУЗ: 

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

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

Рубрика: 

0, если 0,
1, если 1,
, если 0, 1.
ii
ii
ii
x
αβ
χαβ
αβ
==
⎧
⎪
==
⎨
⎪
i
=
=
=
⎩
Тогда
()
(
)
11
(0) ,..., ,..., (1)
nn
ff
ϕ
αα ββϕ
=>=
.
Таким образом,
(0) (1)
ϕ
ϕ
> , откуда (0) 1
ϕ
=
и (1) 0
ϕ
=
, то есть ()
x
x
=
.
Пример 28. Пусть (, ) /
f
xy x y= . Тогда ( , ) ( 1110 )fxy
=
и
(0,0) 1 0 (1,1)ff
=
>= .
Рассмотрим функцию
(
)
() , /
x
fxx xx
ϕ
==
.
Находим,
(0) 0 / 0 1
ϕ
==
и
(1) 1 / 1 0
ϕ
=
=
,
то есть
()
x
x
=
. Итак, получаем
(, ) /
x
fxx xx==
.
5. Класс линейных функций:
L
T
{
}
011
: ...
L
nn
TfPf x x
αα α
⊕⊕⊕=∈ =
n
,
где
{
}
0,1
i
α
∈
для всех 0,1...,in
=
.
Пример 29. ; ;
L
T∈0
L
T∈1 1
L
x
yxyT⊕⊕≡= ∈
;
1
L
x
xT⊕
=
∈
.
Теорема 13. Класс замкнут.
L
T
Доказательство. Пусть функция
1
( ,..., )
n
f
xx
реализована формулой
()
11 1
( ,..., ),..., ( ,..., )
nn n
x
xx
ϕϕ ϕ
x
над
. Если
L
T
00 0
011
...
nn
x
x
ϕα α α
⊕⊕⊕= ,
(
)
(
)
(
)
011
...
kk k
knn
x
x
ϕα α α
⊕⊕⊕=
1,...,= при kn, то
() () ()
(
)
() () ()
(
)
11 1
00 0
101011 011
( ,..., ) ... ... ...
nn n
nnnn
fx x x x x x
ααα α α αα α α
⊕ ⊕ ⊕⊕ ⊕⊕ ⊕ ⊕⊕==
nn
011
...
nn
x
x
α
αα
⊕⊕⊕
=
.
Это означает, что
1
( ,..., )
nL
f
xxT∈
.
Пример 30.
{
}
,
L
Txy⊕=
⎡
⎤
⎣
⎦
1
. Отсюда, в частности, следует, что класс — замкну-
тый.
L
T
Другие свойства класса рассмотрим в следующем разделе.
L
T
Наконец, приведем таблицу принадлежности элементарных булевых функций основ-
ным замкнутым классам: 
                                                  ⎧0, если α i = β i = 0,
                                                  ⎪
                                            χ i = ⎨1, если α i = βi = 1,
                                                  ⎪
                                                  ⎩ x, если α i = 0, βi = 1.
Тогда
                                    ϕ (0) = f (α1 ,..., α n ) > f ( β1 ,..., β n ) = ϕ (1) .

Таким образом, ϕ (0) > ϕ (1) , откуда ϕ (0) = 1 и ϕ (1) = 0 , то есть ϕ ( x) = x .
      Пример 28. Пусть f ( x, y ) = x / y . Тогда f ( x, y ) = ( 1110 ) и

                                                  f (0, 0) = 1 > 0 = f (1,1) .
Рассмотрим функцию
                                                  ϕ ( x ) = f ( x, x ) = x / x .
Находим,
                                        ϕ (0) = 0 / 0 = 1 и ϕ (1) = 1/1 = 0 ,

то есть ϕ ( x) = x . Итак, получаем x = f ( x, x) = x / x .


                                             5. Класс TL линейных функций:

                                    TL = { f ∈ Pn : f = α 0 ⊕ α1 x1 ⊕ ... ⊕ α n xn } ,

где α i ∈ {0,1} для всех i = 0,1..., n .
         Пример 29. 0 ∈ TL ; 1 ∈ TL ; x ≡ y = 1 ⊕ x ⊕ y ∈ TL ; x = 1 ⊕ x ∈ TL .

         Теорема 13. Класс TL замкнут.

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

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

над TL . Если ϕ = α 00 ⊕ α10 x1 ⊕ ... ⊕ α n0 xn , ϕ k = α 0( k ) ⊕ α1( k ) x1 ⊕ ... ⊕ α n( k ) xn при k = 1,..., n , то


                                (   1       1                     1
                                                                        )                     (   n   n         n
                                                                                                                     )
    f ( x1 ,..., xn ) = α 00 ⊕ α10 α 0( ) ⊕ α1( ) x1 ⊕ ... ⊕ α n( ) xn ⊕ ... ⊕ α n0 α 0( ) ⊕ α1( ) x1 ⊕ ... ⊕ α n( ) xn =
                                                     = α 0 ⊕ α1 x1 ⊕ ... ⊕ α n xn .

Это означает, что f ( x1 ,..., xn ) ∈ TL .
         Пример 30. TL = ⎡⎣{1, x ⊕ y}⎤⎦ . Отсюда, в частности, следует, что класс TL — замкну-
тый.
Другие свойства класса TL рассмотрим в следующем разделе.
      Наконец, приведем таблицу принадлежности элементарных булевых функций основ-
ным замкнутым классам:

Страницы