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

UptoLike

ВУЗ: 

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

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

Рубрика: 

Таблица 5
Класс
Функция
⊕
x
x
0
∧
∨
↓
≡
→
/
1
0
T
+
+
+
+
+
−
−
−
−
−
−
1
T
−
+
+
−
+
−
+
−
+
−
+
T
∗
−
−
+
−
−
−
−
+
−
−
−
T
≤
+
+
+
−
+
−
−
−
−
−
+
L
T
+
−
+
+
−
−
+
+
−
−
+
з таблицы 5 видно, что рассмотренные классы попарно различны, не пусты и не совпадают
Полнота
Определение. Класс булевых функций называется полным, если его замыкание
совпад
И
с множеством всех булевых функций
n
P
.
F
ает с
n
P
:
[
]
n
FP
.
ругими словами, множество функций
образует полную систему, если любая функция
Д
F
реализуема формулой над
F
.
Пример 31.
{
}
,,
n
x
x x∨⎡
⎣
y y P∧=
⎦
;
⎤
{
}
,
n
x
xy P
∧
=⎡⎤
⎣⎦
(см. примеры 17, 18).
практическом план нас будут инте большие ко-
нечные
Теорема 14 (Критерий полноты). Пусть заданы две системы функций
Замечание. В е ресовать в основном не
системы, обладающие свойством полноты. Однако замыкание конечной системы
может быть бесконечным и не совпадать с множеством всех булевых функций
n
P
(см. заме-
чание к примеру 16).
{
}
1
,...,
m
Ff f=
и
{
}
1
,...,
k
Gg g=
.
огда, если система
полна и все функции из реализуемы формулами над то система
оказательство. Пусть
Т
F F G ,
функций
G
также полна.
Д
n
f
P∈
— произвольная булева функция. Тогда
[
]
{
}
1
,...,
FF
ffunc F func f f=Φ =Φ
m
=
⎡
⎤
⎣
⎦
[
]
[
]
{
}
[
]
1
,...,
FmG
f
unc func G func G func G
⎡⎤
=Φ Φ Φ =Φ
⎣⎦
.
Пример 32.
{
}
/
n
x
yP=⎡⎤
⎣⎦
, так как
{
}
,
n
x
xy P
∧
=⎡⎤
⎣⎦
и
/
x
xx
=
,
(
)
(
)
////
x
yxy xy xy∧= = .
Пример 33.
{
}
,,
n
x
yx y P⊕∧=⎡⎤
⎣⎦
1
, так как
{
}
,
n
x
xy P
∧
=⎡⎤
⎣⎦
и 1
x
x⊕
=
. 
                                                                                         Таблица 5
                       Функция
                                    0     ∧     x     ⊕      ∨       ↓   ≡       x   →     /   1
               Класс
                       T0           +     +     +     +      +       −   −       −   −     −   −
                       T1           −     +     +     −      +       −   +       −   +     −   +
                       T∗           −     −     +     −      −       −   −       +   −     −   −
                       T≤           +     +     +     −      +       −   −       −   −     −   +
                       TL           +     −     +     +      −       −   +       +   −     −   +

Из таблицы 5 видно, что рассмотренные классы попарно различны, не пусты и не совпадают
с множеством всех булевых функций Pn .


                                                Полнота
      Определение. Класс булевых функций F называется полным, если его замыкание
совпадает с Pn :
                                                      [ F ] = Pn .
Другими словами, множество функций F образует полную систему, если любая функция
реализуема формулой над F .
      Пример 31. ⎡⎣{ x , x ∨ y, x ∧ y}⎤⎦ = Pn ; ⎡⎣{ x , x ∧ y}⎤⎦ = Pn (см. примеры 17, 18).
      Замечание. В практическом плане нас будут интересовать в основном небольшие ко-
нечные системы, обладающие свойством полноты. Однако замыкание конечной системы
может быть бесконечным и не совпадать с множеством всех булевых функций Pn (см. заме-
чание к примеру 16).

      Теорема 14 (Критерий полноты). Пусть заданы две системы функций

                                 F = { f1 ,..., f m } и G = { g1 ,..., g k } .

Тогда, если система F полна и все функции из F реализуемы формулами над G , то система
функций G также полна.

Доказательство. Пусть f ∈ Pn — произвольная булева функция. Тогда

                             f = funcΦ F [ F ] = funcΦ F ⎡⎣{ f1 ,..., f m }⎤⎦ =
                      = funcΦ F ⎡⎣{ funcΦ1 [G ] ,..., funcΦ m [G ]}⎤⎦ = funcΦ G [G ] .


      Пример 32. ⎡⎣{ x / y}⎤⎦ = Pn , так как ⎡⎣{ x , x ∧ y}⎤⎦ = Pn и

                                                x = x/ x,
                                     x ∧ y = x / y = ( x / y) / ( x / y) .
      Пример 33. ⎡⎣{1, x ∧ y, x ⊕ y}⎤⎦ = Pn , так как ⎡⎣{ x , x ∧ y}⎤⎦ = Pn и x = 1 ⊕ x .

Страницы