162 163Áóëåâà àëãåáðàÃëàâà 9
Òåîðåìà 9.13 (Ïîñòà). Äëÿ òîãî, ÷òîáû ñèñòåìà ôóíêöèé áûëà
ïîëíà, íåîáõîäèìî è äîñòàòî÷íî, ÷òîáû îíà ñîäåðæàëà õîòÿ áû
îäíó íåìîíîòîííóþ, õîòÿ áû îäíó íåëèíåéíóþ, õîòÿ áû îäíó
íåñàìîäâîéñòâåííóþ, õîòÿ áû îäíó, íå ñîõðàíÿþùóþ íóëü, è
õîòÿ áû îäíó, íå ñîõðàíÿþùóþ åäèíèöó, ôóíêöèþ.
Äîêàçàòåëüñòâî. Íåîáõîäèìîñòü óñëîâèé òåîðåìû ñëåäóåò èç
ôóíêöèîíàëüíîé çàìêíóòîñòè è íåïîëíîòû êëàññîâ ìîíîòîííûõ,
ëèíåéíûõ, ñîõðàíÿþùèõ 0, ñîõðàíÿþùèõ 1 è ñàìîäâîéñòâåííûõ
ôóíêöèé. Äîêàçàíî (òåîðåìû 9.9 9.12), ÷òî ôóíêöèÿ, íå ïðèíàä-
ëåæàùàÿ äàííîìó ôóíêöèîíàëüíî çàìêíóòîìó êëàññó, íå ìîæåò
áûòü ïîñòðîåíà ïóòåì ñóïåðïîçèöèè ôóíêöèé ýòîãî êëàññà.
Äëÿ äîêàçàòåëüñòâà äîñòàòî÷íîñòè ïîêàæåì, ÷òî ñ ïîìîùüþ
ôóíêöèé, íå ïðèíàäëåæàùèõ íåêîòîðûì èç êëàññîâ T
0
, T
1
, S, M, L,
ìîæíî ïîñòðîèòü íåêîòîðóþ ïîëíóþ ñèñòåìó ôóíêöèé. Òàêîé
(ïîëíîé) ñèñòåìîé ÿâëÿåòñÿ, íàïðèìåð, îòðèöàíèå è êîíúþíêöèÿ.
Äåéñòâèòåëüíî, ëþáàÿ áóëåâà ôóíêöèÿ ïðåäñòàâèìà â âèäå ÑÄÍÔ,
ò.å. êàê ñóïåðïîçèöèÿ ¬, ∧, ∨. Ñëåäîâàòåëüíî, ñèñòåìà {¬, ∧, ∨}
ôóíêöèîíàëüíî ïîëíà. Ìîæíî èñêëþ÷èòü èç íåå ∨, òàê îíà
ïðåäñòàâèìà êàê ñóïåðïîçèöèÿ ¬ è ∧: x ∨ y = ¬(¬x∧ ¬y).
Ñíà÷àëà ïîñòðîèì êîíñòàíòû. Åñëè ôóíêöèÿ f(x
1
,, x
n
) íåñà-
ìîäâîéñòâåííà, òî ïîäñòàíîâêîé â íåå x è ¬x ìîæíî ïîëó÷èòü êîí-
ñòàíòó. Äåéñòâèòåëüíî, ââèäó íåñàìîäâîéñòâåííîñòè f(x
1
,, x
n
)
ñóùåñòâóåò òàêîé íàáîð (α
1
,..., α
n
), ÷òî f(α
1
,..., α
n
) = f(¬α
1
,..., ¬α
n
).
Òîãäà ôóíêöèÿ ϕ(x) = f(x
α1
,, x
n
αn
) ÿâëÿåòñÿ êîíñòàíòîé, òàê êàê
ϕ(0) = f(0
α1
,, 0
αn
) = f((¬α
1
, ..., ¬α
n
) = f(α
1
, ..., α
n
) = f(1
α1
,, 1
αn
)=ϕ(1).
Êîíñòàíòó 1 ìîæíî ïîñòðîèòü ñ ïîìîùüþ ôóíêöèè, íå ñîõðàíÿ-
þùåé 0 è ñîõðàíÿþùåé 1, ò.å. íåñàìîäâîéñòâåííîé. Äåéñòâèòåëüíî,
ïóñòü f íå ñîõðàíÿåò 0. Òîãäà ϕ(0) = f(0,,0) = 1, à åñëè ïðè ýòîì
f ñîõðàíÿåò 1, òî ϕ(1) = f(1,,1) = 1, ò.å. êîíñòàíòà 1 ïîñòðîåíà.
Äâîéñòâåííî, ïóñòü f
1
íå ñîõðàíÿåò 1. Òîãäà ψ(x)=f
1
(ϕ(x),,ϕ(x))=
= f
1
(1,,1)) = 0, ò.å. ψ(x) åñòü êîíñòàíòà 0.
Åñëè æå f(1,,1)) = 0, òî ϕ(x) = ¬x, òàê êàê ϕ(0) = 1 ïî îïðåäå-
ëåíèþ f, à ϕ(1) = 0. Òîãäà, åñëè âçÿòü íåñàìîäâîéñòâåííóþ ôóíêöèþ
f
2
, òî, ïîäñòàâëÿÿ â íåå x è ¬x, òàêæå ìîæíî ïîëó÷èòü êîíñòàíòó, à
ñ ïîìîùüþ åùå îäíîãî îòðèöàíèÿ, ïîëó÷èòü äðóãóþ êîíñòàíòó.
Òàêèì îáðàçîì, ñ ïîìîùüþ ôóíêöèé, íå ñîõðàíÿþùèõ 0, íå ñîõðàíÿ-
þùèõ 1 è íåñàìîäâîéñòâåííûõ, ìîæíî ïîñòðîèòü êîíñòàíòû 0, 1.
Ñ ïîìîùüþ íåìîíîòîííîé ôóíêöèè ïîäñòàíîâêîé â íåå êîí-
ñòàíò ìîæíî ïîëó÷èòü îòðèöàíèå. Äåéñòâèòåëüíî, ïóñòü f íåìîíî-
òîííà. Òîãäà ñóùåñòâóþò íàáîðû α è β, òàêèå, ÷òî α≤β, f(α) = 1,
f(β) = 0. Ïîñêîëüêó α ≤ β, òî â α åñòü íåñêîëüêî, íàïðèìåð, k
ýëåìåíòîâ, êîòîðûå ðàâíû 0, â òî âðåìÿ êàê â β ýòè æå ýëåìåíòû
ðàâíû 1. Âîçüìåì íàáîð α è çàìåíèì â íåì ïåðâûé òàêîé íóëåâîé
ýëåìåíò íà 1, ïîëó÷èì íàáîð α≤α
1
, êîòîðûé îòëè÷àåòñÿ îò α òîëüêî
îäíèì ýëåìåíòîì (òàêèå íàáîðû íàçûâàþò ñîñåäíèìè). Ïîâòîðÿÿ
ýòó îïåðàöèþ k ðàç, ïîëó÷èì ïîñëåäîâàòåëüíîñòü íàáîðîâ
α≤α
1
≤≤α
k1
≤β
, â êîòîðîé ëþáûå äâà ñîñåäíèõ íàáîðà
îòëè÷àþòñÿ äðóã îò äðóãà òîëüêî îäíèì ýëåìåíòîì.  ýòîé öåïî÷êå
íàéäóòñÿ äâà òàêèå íàáîðà α
i
, α
i+1
, ÷òî f(α
i
) = 1, f(α
i+1
) = 0. Ïóñòü
ýòè íàáîðû îòëè÷àþòñÿ i-ì ýëåìåíòîì (çíà÷åíèåì ïåðåìåííîé x
i
),
îñòàëüíûå ýëåìåíòû îäèíàêîâû. Ïîäñòàâèì â f ýòè çíà÷åíèÿ. Òîãäà
ïîëó÷èì ôóíêöèþ f(α
i
1
,, x
i
, α
i
i+1
, , α
i
n
) = g(x
i
), êîòîðàÿ çàâèñèò
òîëüêî îò x
i
. Òîãäà g(0) = g(α
i
i
) = f(α
i
) = 1, g(1) = g(α
i+1
i
) = f(α
i+1
)=0.
Îòñþäà ñëåäóåò, ÷òî g(x
i
) = ¬x
i
.
Ñ ïîìîùüþ ïîäñòàíîâêè â íåëèíåéíóþ ôóíêöèþ êîíñòàíò è
èñïîëüçîâàíèÿ îòðèöàíèÿ ìîæíî ïîñòðîèòü êîíúþíêöèþ è äèçú-
þíêöèþ. Äåéñòâèòåëüíî, åñëè ôóíêöèÿ f íåëèíåéíàÿ, òî åå ïîëèíîì
Æåãàëêèíà ñîäåðæèò êîíúþíêöèþ ïåðåìåííûõ, íàïðèìåð, K=x
1
x
2
x
k
.
Ïîëîæèì x
3
= = x
k
= 1, à äëÿ âñåõ x
j
, íå ñîäåðæàùèõñÿ â K, x
j
= 0.
Òîãäà êîíúþíêöèÿ K = x
1
x
2
, îñòàëüíûå êîíúþíêöèè îáðàòÿòñÿ â 0,
à ïîëèíîì Æåãàëêèíà ïðèìåò âèä ϕ(x
1
,x
2
)=x
1
x
2
⊕α
1
x
1
⊕ α
2
x
2
⊕γ,
ãäå α
1
, α
2
, γ êîýôôèöèåíòû, ðàâíûå 0 èëè 1. Ïðè ïîäñòàíîâêå
ðàçëè÷íûõ êîíñòàíò âìåñòî α
1
, α
2
, γ áóäóò ïîëó÷åíû ðàçíûå ôóíê-
öèè. Ðàññìîòðèì ôóíêöèþ ψ(x
1
,x
2
), ïîëó÷àåìóþ èç ϕ(x
1
,x
2
) ñëåäó-
þùèì îáðàçîì:
ψ(x
1
,x
2
) = ϕ(x
1
⊕α
2
,x
2
⊕ α
1
) ⊕ α
1
α
2
⊕ γ =
= (x
1
⊕α
2
)(x
2
⊕ α
1
) ⊕ α
1
(x
1
⊕α
2
) ⊕ α
2
(x
2
⊕ α
1
) ⊕ γ ⊕ α
1
α
2
⊕ γ = x
1
x
2
.
Òàêèì îáðàçîì, êîíúþíêöèÿ ïîëó÷åíà.
Äëÿ ïîëó÷åíèÿ äèçúþíêöèè ïî çàêîíàì äå Ìîðãàíà ïîòðåáóåòñÿ
òîëüêî îòðèöàíèå.
Ïðèìåð. Ñèñòåìû ôóíêöèé {∨, ∧, ¬}, {⊕, ∧, 0, 1}, {→, ¬} ÿâëÿþòñÿ
ôóíêöèîíàëüíî ïîëíûìè. Äëÿ ïðèìåðà ïðîâåðèì ïîëíîòó ñèñòåìû
ôóíêöèé {¬, →}. Äëÿ èññëåäóåìîé ñèñòåìû ñîñòàâèì òàáëèöó Ïîñòà
(ñì. òàáë.9.5). Åñëè ôóíêöèÿ âõîäèò â ôóíêöèîíàëüíî çàìêíóòûé
êëàññ, òî â òàáëèöå Ïîñòà â ñîîòâåòñòâóþùåé ÿ÷åéêå ñòàâèòñÿ çíàê
«+», èíà÷å çíàê «».
Ôóíêöèÿ ¬x íå ñîõðàíÿåò 0 è 1, òàê êàê íà íóëåâîì íàáîðå îíà
ïðèíèìàåò çíà÷åíèå 1, à íà åäèíè÷íîì 0. Î÷åâèäíî, ÷òî äàííàÿ
ôóíêöèÿ íåìîíîòîííà. Ôóíêöèÿ ñàìîäâîéñòâåííà, òàê êàê íà
ïðîòèâîïîëîæíûõ íàáîðàõ îíà ïðèíèìàåò ïðîòèâîïîëîæíûå
çíà÷åíèÿ. Ôóíêöèÿ ëèíåéíà åå ïîëèíîì Æåãàëêèíà: ¬õ = õ⊕1.
Ôóíêöèÿ õ→ó íå ñîõðàíÿåò 0 è ñîõðàíÿåò 1. Ýòà ôóíêöèÿ íåìîíî-
òîííà, òàê êàê íàáîð (0,0) ïðåäøåñòâóåò íàáîðó (1,0), íî 0→0=1,
à 1→0 = 0. Íà ïðîòèâîïîëîæíûõ íàáîðàõ (0,0) è (1,1) ôóíêöèÿ
ïðèíèìàåò îäèíàêîâûå çíà÷åíèÿ 1, ñëåäîâàòåëüíî, îíà íåñàìî-
äâîéñòâåííà.