ВУЗ:
Составители:
Рубрика:
индекс i — один из пяти индексов 0, 1,
∗
,
≤
или
L
. Тогда существует такая функция
f
, что
i
f
T∈
,
f
T∉ ,
{
}
i
Tf⊂
U
T
и
{
}
[
]
ii
TfTT⊂=≠⎡⎤
⎣⎦
U
n
P
.
Следствие 3. Из любой полной в системы можно выделить полную подсистему,
состоящую не более чем из
4 функций.
n
P
Доказательство. В доказательстве теоремы Поста о функциональной полноте использова-
лось не более
5 функций
0
f
,
1
f
,
f
∗
,
f
≤
и
L
f
, которые тем самым составляли полную подсис-
тему. Из них либо не использовалась функция
f
∗
, либо не использовались функции
1
f
и
f
≤
.
Замечание. Улучшить оценку 4 в общем случае нельзя: утверждение, что из любой полной в
системы можно выделить полную подсистему, состоящую не более чем из 3 функций, во-
обще говоря, неверно.
n
P
Пример 38. Построим таблицу принадлежности к предполным классам для системы
{
}
,, ,Fxyxy⊕⊕=∧01 z
:
Функция
Класс
0
x
∧
y
x
⊕
y
⊕
z
1
0
T
+
+
+
−
1
T
−
+
+
+
T
∗
−
−
+
−
T
≤
+
+
−
+
L
T
+
−
+
+
Из этой таблицы видно, что система
{
}
,, ,Fxyxy⊕⊕=∧01 z
полна, однако удаление из нее
любой функции делает систему неполной: все функции без
0 лежат в , все функции без 1
лежат в
, все функции без
1
T
0
T
xy
∧
лежат в , все функции без
L
T
x
yz
⊕
⊕ лежат в
T
.
≤
индекс i — один из пяти индексов 0, 1, ∗ , ≤ или L . Тогда существует такая функция f , что
f ∈ Ti , f ∉ T , T U { f } ⊂ Ti и
⎡⎣T U { f }⎤⎦ ⊂ [Ti ] = Ti ≠ Pn .
Следствие 3. Из любой полной в Pn системы можно выделить полную подсистему,
состоящую не более чем из 4 функций.
Доказательство. В доказательстве теоремы Поста о функциональной полноте использова-
лось не более 5 функций f 0 , f1 , f∗ , f ≤ и f L , которые тем самым составляли полную подсис-
тему. Из них либо не использовалась функция f∗ , либо не использовались функции f1 и f ≤ .
Замечание. Улучшить оценку 4 в общем случае нельзя: утверждение, что из любой полной в
Pn системы можно выделить полную подсистему, состоящую не более чем из 3 функций, во-
обще говоря, неверно.
Пример 38. Построим таблицу принадлежности к предполным классам для системы
F = {0, 1, x ∧ y , x ⊕ y ⊕ z} :
Функция
0 x ∧y x ⊕ y ⊕ z 1
Класс
T0 + + + −
T1 − + + +
T∗ − − + −
T≤ + + − +
TL + − + +
Из этой таблицы видно, что система F = {0, 1, x ∧ y , x ⊕ y ⊕ z} полна, однако удаление из нее
любой функции делает систему неполной: все функции без 0 лежат в T1 , все функции без 1
лежат в T0 , все функции без x ∧ y лежат в TL , все функции без x ⊕ y ⊕ z лежат в T≤ .
