ВУЗ:
Составители:
Рубрика:
класс
функция
0
T
1
T
T
∗
T
≤
L
T
(, ,)
f
xyz
+
+
−
−
−
(, ,)gxyz
−
−
+
−
−
Итак, поскольку данная система функций не лежит целиком ни в одном из указанных
классо
ф кций полна в
то формулами над заданной системой
можно
бую немонотонную функцию, например
1gxy
в функций, то она полна в
n
P
.
2. Так как данная система ун
n
P
,
реализовать и отрицание и конъюнкцию.
Для построения отрицания возьмем лю
( , , ) ( 101 0100)z =
. Так как
(0, 0, 0) 1 (1, 1, 1)gg0
=
>=
, то положим
() (,,)
x
gx xx
ϕ
=
. Сле-
о немон нкция
()
дуя условиям леммы отонной функции, фу
x
ϕ
реализ цание ует отри
()
x
x
ϕ
=
. Действительно,
(0) (0,0,0) 1g
ϕ
==
и
(1) (1,1 0g ,1)
ϕ
=
=
роения конъюнкции возьмем люб нелинейную функцию, например
fxy
.
Для пост ую
( , , ) (0100 1011)z=
. Так как
(, ,) 0
f
xyz yz x z yz z x
=
⊕⊕= ⊕⊕⊕
, то рассмотрим функ-
(,)yz yz
цию двух переменных
z f yz
0 0 (0,,)
ϕ
=
Наконец, введем
⊕⊕⊕=
.
новую функцию
(,) ( 1, 0) (01 0) (, ) (0, ,)yz y z y z f yz
ψ
ϕϕ
=⊕⊕⊕⋅⊕= =
.
ледуя условиям леммы о нелинейной функции, функция С
(,)yz
ψ
реализует конъюнкцию
(,)yz yz
ψ
=
. Действительно,
(
)
(,) (0, ,)y z f y z yz z y yz yz1z
ψ
=
=⊕=⊕ =
. Здесь отрицание
=
(,, ), а y gyyy= (,,)
f
yyy=0 .
Итак,
(,, )y= gyyy и (0, , )yz f y z= , где (,,)
f
yyy=0 .
Из тео оста о функциональной полн текает ряд важных следствий.
Следствие 1. Всякая неполная в система функций содержится по крайней мере в
одном
В
едполным в если
ремы П оте вы
n
P
из классов
0
T
,
1
T
,
T
∗
,
T
≤
или
L
T
. частности, всякий замкнутый класс, отличный от
n
P
, содержится в о ом из перечисленных классов.
Определение. Замкнутый класс
F
называется пр
дн пяти
n
P
,
n
F
P≠
и для
любой функции
f
F∉
{
}
n
FfP
=
⎡⎤
⎣⎦
U
.
Следствие 2. В существует только пять предполных классов и .
оказательство. Согласно таблице 5 все эти классы попарно различны, не пусты и не сов-
n
P
0
T
,
1
T
,
T
∗
,
T
≤
L
T
Д
падают с множеством всех булевых функций
n
P
. Покажем, что каждый из них предполный.
Класс
0
T
содержит
1
T∉0
,
T
∗
∉
0
,
x
yT
≤
⊕
∉
,
L
x
yT
∧
∉
. Поэтому добавление любой
функции
0
f
T∉
даст систем со ащ в пяти классов, то есть полную
систему. Доказательство предполноты остальных классов проводится аналогично.
Теперь покажем, что других предполных классов в
n
P
нет. Предположим противн
у, не держ уюся ни
ое. Пусть
одном из
T — предполный в
n
P
класс, отличный от пяти перечисленных. Класс T замкнут, отличен
n
P
и по следствию должен содержаться в одном из пяти основных ассов:
i
TT⊂
, где
от
1 кл
класс T0 T1 T∗ T≤ TL
функция
f ( x, y , z ) + + − − −
g ( x, y , z ) − − + − −
Итак, поскольку данная система функций не лежит целиком ни в одном из указанных
классов функций, то она полна в Pn .
2. Так как данная система функций полна в Pn , то формулами над заданной системой
можно реализовать и отрицание и конъюнкцию.
Для построения отрицания возьмем любую немонотонную функцию, например
g ( x, y, z ) = (1101 0100) . Так как g (0, 0, 0) = 1 > 0 = g (1,1,1) , то положим ϕ ( x) = g ( x, x, x) . Сле-
дуя условиям леммы о немонотонной функции, функция ϕ ( x) реализует отрицание
ϕ ( x) = x . Действительно, ϕ (0) = g (0, 0, 0) = 1 и ϕ (1) = g (1,1,1) = 0 .
Для построения конъюнкции возьмем любую нелинейную функцию, например
f ( x, y, z ) = (0100 1011) . Так как f ( x, y, z ) = yz ⊕ x ⊕ z = yz ⊕ 0 ⊕ z ⊕ x , то рассмотрим функ-
цию двух переменных ϕ ( y, z ) = yz ⊕ 0 ⊕ z ⊕ 0 = f (0, y, z ) .
Наконец, введем новую функцию
ψ ( y, z ) = ϕ ( y ⊕ 1, z ⊕ 0) ⊕ (0 ⋅1 ⊕ 0) = ϕ ( y , z ) = f (0, y , z ) .
Следуя условиям леммы о нелинейной функции, функция ψ ( y, z ) реализует конъюнкцию
ψ ( y, z ) = yz . Действительно, ψ ( y, z ) = f (0, y , z ) = yz ⊕ z = ( y ⊕ 1) z = yz = yz . Здесь отрицание
y = g ( y, y, y ) , а 0 = f ( y , y , y ) .
Итак, y = g ( y, y, y ) и yz = f (0, y , z ) , где 0 = f ( y , y , y ) .
Из теоремы Поста о функциональной полноте вытекает ряд важных следствий.
Следствие 1. Всякая неполная в Pn система функций содержится по крайней мере в
одном из классов T0 , T1 , T∗ , T≤ или TL . В частности, всякий замкнутый класс, отличный от
Pn , содержится в одном из пяти перечисленных классов.
Определение. Замкнутый класс F называется предполным в Pn , если F ≠ Pn и для
любой функции f ∉ F
⎡⎣ F U { f }⎤⎦ = Pn .
Следствие 2. В Pn существует только пять предполных классов T0 , T1 , T∗ , T≤ и TL .
Доказательство. Согласно таблице 5 все эти классы попарно различны, не пусты и не сов-
падают с множеством всех булевых функций Pn . Покажем, что каждый из них предполный.
Класс T0 содержит 0 ∉ T1 , 0 ∉ T∗ , x ⊕ y ∉ T≤ , x ∧ y ∉ TL . Поэтому добавление любой
функции f ∉ T0 даст систему, не содержащуюся ни в одном из пяти классов, то есть полную
систему. Доказательство предполноты остальных классов проводится аналогично.
Теперь покажем, что других предполных классов в Pn нет. Предположим противное. Пусть
T — предполный в Pn класс, отличный от пяти перечисленных. Класс T замкнут, отличен
от Pn и по следствию 1 должен содержаться в одном из пяти основных классов: T ⊂ Ti , где
