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

UptoLike

ВУЗ: 

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

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

Рубрика: 

{
}
x
xy∉∧
⎡
⎤
⎣
⎦
.
{
}
,,
n
x
xyxy P∨∧=⎡⎤
⎣⎦
. Пример 17. Это следуе теоремы 4.
Пример 18.
т из
{
}
,
n
x
xy P∧=⎡⎤
⎣⎦
, так как
{
}
,
x
yxy xxy∨=∧∈ ∧
⎡
⎤
⎣
⎦
.
ыкания:
1.
Свойства зам
[
]
FF⊂
, то есть система содержится в своем замыкании; F
2.
[
]
[
]
FF
⎡⎤
=
⎣⎦
;
3.
[
]
[
]
12 1 2
FF F F⊂
;
⊂⇒
4.
[
]
[
]
]
121
FFFF
2
UU
.
имер 19. Покажем
⊂
Пр , что
[
]
]
]
121
FFFF≠
UU
.
2
В самом деле, если
{
}
1
Fx=
и
{
}
2
Fxy=∧
, то
[
]
{
}
{
}
{
}
{
}
[
]
[
]
12 1
,
nk
F F xx y P x y F F=∧= ∧=⎡⎤ ⎡⎤
⎣⎦ ⎣⎦
UUU
≠
1 2
, ... xx x x∧∧=⎡⎤
⎣⎦
.
Определение. Класс функций называется замкнутым, если он совпадает своим
:
F со
замыканием
]
FF
=
.
{
}
{
}
,,
x
xx=⎡⎤
⎣⎦
.
x
Действительно, если
{
}
Fx=
, то
]
{
}
,Fxx=
Пример 20. (см. пример
5). В силу свойства 2 замыкания, получаем
1
]
]
{
}
{
}
,,
x
x
=⎡⎤
⎣⎦
FFxx
⎡⎤
==
⎣⎦
.
Итак, класс
{
}
,
x
x
— замкнут.
Приведем другие простые примеры замкнутых классов.
ер 21Прим .
[
]
nn
PP
=
;
{
}
{
}
=⎡
⎣
⎤
⎦
00
;
{
}
{
}
,,, ,,,
x
xx=⎡⎤
⎣⎦
01 01
.
x
классов. Пусть и — замкну е классы. Тогда
1.
Свойства замкнутых ты
1
F
2
F
[
]
12 12
FF FF⊂
UU
;
2.
[
]
1212
= FF FF
II
.
Основные замкнутые классы
1 их 0:
. Класс
0
T
функций, сохраняющ
{
}
0
: (0,...,0) 0
n
TfPf=∈ =
.
Пример 22.
0
T∈0
;
0
x
T∈
;
0
x
yT∧∈
;
0
x
yT∨∈
;
0
x
yT⊕
.
∈
                                                        x ∉ ⎡⎣{ x ∧ y}⎤⎦ .

        Пример 17. ⎡⎣{ x , x ∨ y, x ∧ y}⎤⎦ = Pn . Это следует из теоремы 4.
        Пример 18. ⎡⎣{ x , x ∧ y}⎤⎦ = Pn , так как x ∨ y = x ∧ y ∈ ⎡⎣{ x , x ∧ y}⎤⎦ .

        Свойства замыкания:
        1. F ⊂ [ F ] , то есть система F содержится в своем замыкании;
        2. ⎡⎣[ F ]⎤⎦ = [ F ] ;
        3. F1 ⊂ F2 ⇒ [ F1 ] ⊂ [ F2 ] ;
        4. [ F1 ] U   [ F2 ] ⊂ [ F1 U   F2 ] .
        Пример 19. Покажем, что [ F1 ] U                     [ F2 ] ≠ [ F1 U    F2 ] . В самом деле, если F1 = { x } и
F2 = { x ∧ y} , то
         [ F1 U   F2 ] = ⎡⎣{ x , x ∧ y}⎤⎦ = Pn ≠ { x , x1 ∧ ... ∧ xk } = ⎡⎣{ x }⎤⎦ U ⎡⎣{ x ∧ y}⎤⎦ = [ F1 ] U   [ F2 ] .
      Определение. Класс функций F называется замкнутым, если он совпадает со своим
замыканием:
                                       [F ] = F .

       Пример 20. ⎡⎣{ x, x }⎤⎦ = { x, x } . Действительно, если F = { x } , то [ F ] = { x, x } (см. пример
15). В силу свойства 2 замыкания, получаем

                                                 ⎡⎣{ x, x }⎤⎦ = ⎡⎣[ F ]⎤⎦ = [ F ] = { x, x } .

Итак, класс { x, x } — замкнут.
       Приведем другие простые примеры замкнутых классов.
       Пример 21. [ Pn ] = Pn ; ⎡⎣{0}⎤⎦ = {0} ; ⎡⎣{0, 1, x, x }⎤⎦ = {0, 1, x, x } .

        Свойства замкнутых классов. Пусть F1 и F2 — замкнутые классы. Тогда
        1. F1 U F2 ⊂ [ F1 U F2 ] ;
        2. F1 I F2 = [ F1 I F2 ] .


                                          Основные замкнутые классы


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

                                             T0 = { f ∈ Pn : f (0,..., 0) = 0} .

        Пример 22. 0 ∈ T0 ; x ∈ T0 ; x ∧ y ∈ T0 ; x ∨ y ∈ T0 ; x ⊕ y ∈ T0 .

Страницы