ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.03.2021
Просмотров: 877
Скачиваний: 9
76
ÃËÀÂÀ 2. ÔÓÍÊÖÈÈ ÀËÃÅÁÐÛ ËÎÃÈÊÈ
Ëåììà 2.9 (Ëåììà î íåëèíåéíîé ôóíêöèè.). Åñëè
f
(
x
1
, . . . , x
n
)
/
∈
L
,
òî èç íåå ïóòåì ïîäñòàíîâêè êîíñòàíò 0, 1 è èñïîëüçîâàíèÿ ôóíêöèè
¯
x
ìîæíî ïîëó÷èòü ôóíêöèþ
x
1
&
x
2
.
Äîêàçàòåëüñòâî. Ïðåäñòàâèì
f
â âèäå ÄÍÔ (íàïðèìåð, ñîâåðøåííîé ÄÍÔ)
è âîñïîëüçóåìñÿ ñîîòíîøåíèÿìè:
x
1
∨
x
2
=
x
1
∧
x
2
;
¯
x
=
x
+ 1;
K
∧
K
=
K
;
K
+
K
= 0
.
Ïðèìåð. Ïðèâåäåì äâà ïðèìåðà ïðèìåíåíèÿ óêàçàííûõ ïðåîáðàçîâà-
íèé.
x
1
∨
x
2
= (
x
1
+ 1)(
x
2
+ 1) + 1 =
x
1
x
2
+
x
1
+
x
2
;
x
1
x
2
∨
x
3
x
4
= (
x
1
x
2
+ 1)(
x
3
x
4
+ 1) + 1 =
x
1
x
2
x
3
x
4
+
x
2
x
3
+
x
3
x
4
.
Òàêèì îáðàçîì, ôóíêöèÿ, çàïèñàííàÿ â äèçúþíêòèâíîé íîðìàëüíîé
ôîðìå, ïîñëå ïðèìåíåíèÿ óêàçàííûõ ñîîòíîøåíèé, ðàñêðûòèÿ ñêîáîê è
íåñëîæíûõ àëãåáðàè÷åñêèõ ïðåîáðàçîâàíèé ïåðåõîäèò â ïîëèíîì ïî
mod 2
(ïîëèíîì Æåãàëêèíà):
f
=
X
i
1
, ..., i
s
α
i
1
, ..., i
s
x
i
1
x
i
2
. . . x
i
s
=
=
α
0
+
α
1
x
1
+
α
2
x
2
+
. . .
+
α
n
x
n
+
+
α
1
,
2
x
1
x
2
+
α
1
,
3
x
1
x
3
+
. . .
+
α
n
−
1
,n
x
n
−
1
x
n
+
+
α
1
,
2
,
3
x
1
x
2
x
3
+
. . .
+
α
n
−
2
,n
−
1
,n
x
n
−
2
x
n
−
1
x
n
+
. . .
+
α
1
,
2
,...,n
x
1
x
2
. . . x
n
=
A
0
+
A
1
+
. . .
+
A
r
,
ãäå
A
0
êîíñòàíòà, à
A
i
êîíúþíêöèÿ íåêîòîðûõ ïåðåìåííûõ èç ÷èñëà
x
1
, . . . , x
n
, i
= 1
,
2
, . . . , r
.
Åñëè êàæäàÿ êîíúþíêöèÿ
A
i
ñîñòîèò ëèøü èç îäíîé ïåðåìåííîé, òî
f
ëèíåéíàÿ ôóíêöèÿ, ÷òî ïðîòèâîðå÷èò óñëîâèþ ëåììû.
Ñëåäîâàòåëüíî, â ïîëèíîìå Æåãàëêèíà äëÿ ôóíêöèè
f
íàéäåòñÿ ÷ëåí,
â êîòîðîì ñîäåðæèòñÿ íå ìåíåå äâóõ ñîìíîæèòåëåé. Áåç îãðàíè÷åíèÿ îáù-
íîñòè ìîæíî ñ÷èòàòü, ÷òî ñðåäè ýòèõ ñîìíîæèòåëåé ïðèñóòñòâóþò ïåðå-
ìåííûå
x
1
è
x
2
. Òîãäà ïîëèíîì ìîæíî ïðåîáðàçîâàòü ñëåäóþùèì îáðàçîì:
f
=
x
1
x
2
f
1
(
x
3
, . . . , x
n
)+
x
1
f
2
(
x
3
, . . . , x
n
)+
x
2
f
3
(
x
3
, . . . , x
n
)+
f
4
(
x
3
, . . . , x
n
)
,
2.5. ÔÓÍÊÖÈÎÍÀËÜÍÀß ÏÎËÍÎÒÀ ÑÈÑÒÅÌ ÔÓÍÊÖÈÉ
77
ãäå
f
1
(
x
3
, . . . , x
n
)
6
= 0
(â ïðîòèâíîì ñëó÷àå â ïîëèíîì íå âõîäèò êîíúþíê-
öèÿ, ñîäåðæàùàÿ êîíúþíêöèþ
x
1
x
2
).
Ïóñòü
(
α
3
, . . . , α
n
)
òàêîâû, ÷òî
f
1
(
α
3
, . . . , α
n
) = 1
. Òîãäà
ϕ
(
x
1
, x
2
) =
f
(
x
1
, x
2
, α
3
, . . . , α
n
) =
x
1
x
2
+
αx
1
+
βx
2
+
γ,
ãäå
α, β, γ
êîíñòàíòû, ðàâíûå 0 èëè 1.
Âîñïîëüçóåìñÿ îïåðàöèåé îòðèöàíèÿ, êîòîðàÿ ó íàñ èìååòñÿ, è ðàññìîò-
ðèì ôóíêöèþ
ψ
(
x
1
, x
2
)
, ïîëó÷àþùóþñÿ èç
ϕ
(
x
1
, x
2
)
ñëåäóþùèì îáðàçîì:
ψ
(
x
1
, x
2
) =
ϕ
(
x
1
+
β, x
2
+
α
) +
αβ
+
γ.
Î÷åâèäíî, ÷òî
ψ
(
x
1
, x
2
) = (
x
1
+
β
)(
x
2
+
α
) +
α
(
x
1
+
β
) +
β
(
x
2
+
α
) +
γ
+
αβ
+
γ
=
x
1
x
2
.
Ñëåäîâàòåëüíî,
ψ
(
x
1
, x
2
) =
x
1
x
2
.
Ëåììà äîêàçàíà ïîëíîñòüþ.
Ëåììà 2.10 (Îñíîâíàÿ ëåììà êðèòåðèÿ ïîëíîòû.). Åñëè â êëàññå
F
=
{
f
}
ôóíêöèé àëãåáðû ëîãèêè ñîäåðæàòñÿ ôóíêöèè, íå ñîõðàíÿþùèå
åäèíèöó, íå ñîõðàíÿþùèå 0, íåñàìîäâîéñòâåííûå è íåìîíîòîííûå:
f
¯
0
/
∈
T
0
, f
¯
1
/
∈
T
1
, f
¯
S
/
∈
S, f
¯
M
/
∈
M,
òî èç ôóíêöèé ýòîé ñèñòåìû îïåðàöèÿìè ñóïåðïîçèöèè è çàìåíû ïåðå-
ìåííûõ ìîæíî ïîëó÷èòü êîíñòàíòû 0, 1 è ôóíêöèþ
¯
x
.
Äîêàçàòåëüñòâî. Ðàññìîòðèì ôóíêöèþ
f
¯
0
/
∈
T
0
. Òîãäà
f
¯
0
(0
,
0
, . . . ,
0) = 1
.
Âîçìîæíû äâà ñëó÷àÿ ïîñëåäóþùèõ ðàññìîòðåíèé, â äàëüíåéøåì èçëîæå-
íèè îáîçíà÷åííûå êàê 1) è 2).
1). Ôóíêöèÿ
f
¯
0
íà åäèíè÷íîì íàáîðå ïðèíèìàåò çíà÷åíèå 0:
f
¯
0
(1
,
1
, . . . ,
1) = 0
.
Çàìåíèì âñå ïåðåìåííûå ôóíêöèè
f
¯
0
ïåðåìåííîé
x
.
78
ÃËÀÂÀ 2. ÔÓÍÊÖÈÈ ÀËÃÅÁÐÛ ËÎÃÈÊÈ
Òîãäà ôóíêöèÿ
ϕ
(
x
) =
f
¯
0
(
x, . . . , x
)
åñòü
¯
x
, èáî
ϕ
(0) =
f
¯
0
(0
, . . . ,
0) = 1
è
ϕ
(1) =
f
¯
0
(1
, . . . ,
1) = 0
.
Âîçüìåì íåñàìîäâîéñòâåííóþ ôóíêöèþ
f
¯
S
. Òàê êàê ôóíêöèþ
¯
x
ìû óæå
ïîëó÷èëè, òî ïî ëåììå î íåñàìîäâîéñòâåííîé ôóíêöèè (ëåììà 2.7) èç
f
¯
S
ìîæíî ïîëó÷èòü êîíñòàíòó. Âòîðóþ êîíñòàíòó ìîæíî ïîëó÷èòü èç ïåðâîé,
èñïîëüçóÿ ôóíêöèþ
¯
x
. Èòàê, â ïåðâîì ðàññìîòðåííîì ñëó÷àå ïîëó÷åíû
êîíñòàíòû è îòðèöàíèå.
2). Ôóíêöèÿ
f
¯
0
íà åäèíè÷íîì íàáîðå ïðèíèìàåò çíà÷åíèå 1:
f
¯
0
(1
,
1
, . . . ,
1) = 1
.
Çàìåíèì âñå ïåðåìåííûå ôóíêöèè
f
¯
0
ïåðåìåííîé
x
(îòîæäåñòâèì âñå ïå-
ðåìåííûå). Òîãäà ôóíêöèÿ
ϕ
(
x
) =
f
¯
0
(
x, . . . , x
)
åñòü êîíñòàíòà 1, èáî
ϕ
(0) =
f
¯
0
(0
, . . . ,
0) = 1
è
ϕ
(1) =
f
¯
0
(1
, . . . ,
1) = 1
.
Âòîðàÿ êîíñòàíòà 0 ïîëó÷àåòñÿ èç ôóíêöèè
f
¯
1
, íå ñîõðàíÿþùåé åäèíèöó,
f
¯
1
/
∈
T
1
:
f
¯
1
(1
,
1
, . . . ,
1) =
f
¯
1
(
ϕ
(
x
)
, ϕ
(
x
)
, . . . , ϕ
(
x
)) = 0
Òåïåðü íà
îñíîâàíèè ëåììû î íåìîíîòîííîé ôóíêöèè (ëåììà 2.8) èç èìåþùåéñÿ ó íàñ
íåìîíîòîííîé ôóíêöèè
f
¯
M
è ïîëó÷åííûõ êîíñòàíò 0 è 1 ìîæíî ïîëó÷èòü
îòðèöàíèå
¯
x
. Âòîðîé ñëó÷àé, à âìåñòå ñ íèì è îñíîâíàÿ ëåììà êðèòåðèÿ
ïîëíîòû, ïîëíîñòüþ äîêàçàíû.
Òåîðåìà 2.11 (Êðèòåðèé ïîëíîòû ñèñòåì ôóíêöèé àëãåáðû ëîãèêè (òåî-
ðåìà Ïîñòà)). Äëÿ òîãî, ÷òîáû ñèñòåìà ôóíêöèé
F
=
{
f
i
}
áûëà ïîëíîé,
íåîáõîäèìî è äîñòàòî÷íî, ÷òîáû îíà öåëèêîì íå ñîäåðæàëàñü íè â îä-
íîì èç ïÿòè çàìêíóòûõ êëàññîâ
T
0
, T
1
, L, S, M
, òî åñòü äëÿ êàæäîãî
èç êëàññîâ
T
0
, T
1
, L, S, M
â
F
íàéäåòñÿ õîòÿ áû îäíà ôóíêöèÿ, ýòîìó
êëàññó íå ïðèíàäëåæàùàÿ.
Äîêàçàòåëüñòâî. Íåîáõîäèìîñòü. Ïóñòü
F
ïîëíàÿ ñèñòåìà. Äîïóñòèì,
÷òî
F
ñîäåðæèòñÿ â îäíîì èç óêàçàííûõ êëàññîâ, îáîçíà÷èì åãî ÷åðåç
K
,
ò.å.
F
⊆
K
. Ïîñëåäíåå âêëþ÷åíèå íåâîçìîæíî, òàê êàê
K
çàìêíóòûé
êëàññ, íå ÿâëÿþùèéñÿ ïîëíîé ñèñòåìîé.
Äîñòàòî÷íîñòü. Ïóñòü ñèñòåìà ôóíêöèé
F
=
{
f
i
}
öåëèêîì íå ñîäåð-
æèòñÿ íè â îäíîì èç ïÿòè çàìêíóòûõ êëàññîâ
T
0
, T
1
, L, S, M.
Âîçüìåì â
F
ôóíêöèè:
f
¯
0
/
∈
T
0
, f
¯
1
/
∈
T
1
, f
L
/
∈
L, f
S
/
∈
S, f
M
/
∈
M.
2.5. ÔÓÍÊÖÈÎÍÀËÜÍÀß ÏÎËÍÎÒÀ ÑÈÑÒÅÌ ÔÓÍÊÖÈÉ
79
Òîãäà íà îñíîâàíèè îñíîâíîé ëåììû (ëåììà 2.10.) èç ôóíêöèè íå ñîõðàíÿ-
þùåé 0, ôóíêöèè íå ñîõðàíÿþùåé 1, íåñàìîäâîéñòâåííîé è íåìîíîòîííîé
ôóíêöèé ìîæíî ïîëó÷èòü êîíñòàíòû 0, 1 è ôóíêöèþ îòðèöàíèå
¯
x
:
{
f
¯
0
, f
¯
1
, f
¯
S
, f
¯
M
} ⇒ {
0
,
1
,
¯
x
}
.
Íà îñíîâàíèè ëåììû î íåëèíåéíîé ôóíêöèè (ëåììà ) èç êîíñòàíò, îòðèöà-
íèÿ è íåëèíåéíîé ôóíêöèè ìîæíî ïîëó÷èòü êîíúþíêöèþ:
{
0
,
1
,
¯
x, f
¯
L
} ⇒ {
x
1
∧
x
2
}
.
Ñèñòåìà ôóíêöèé
{
¯
x, x
1
∧
x
2
}
ïîëíàÿ ñèñòåìà ïî òåîðåìå î âîçìîæíîñòè
ïðåäñòàâëåíèÿ ëþáîé ôóíêöèè àëãåáðû ëîãèêè â âèäå ñîâåðøåííîé äèçú-
þíêòèâíîé íîðìàëüíîé ôîðìû (çàìåòèì, ÷òî äèçúþíêöèÿ ìîæåò áûòü âû-
ðàæåíà ÷åðåç êîíúþíêöèþ è îòðèöàíèå â âèäå
x
1
∨
x
2
= ¯
x
1
∧
¯
x
2
).
Òåîðåìà äîêàçàíà ïîëíîñòüþ.
Ïðèìåðû.
1. Ïîêàæåì, ÷òî ôóíêöèÿ
f
(
x, y
) =
x
|
y
îáðàçóåò ïîëíóþ ñèñòåìó. Ïî-
ñòðîèì òàáëèöó çíà÷åíèé ôóíêöèè
x
|
y
:
x
y
x
|
y
0 0
1
0 1
1
1 0
1
1 1
0
f
(0
,
0) = 1
, ñëåäîâàòåëüíî,
x
|
y /
∈
T
0
.
f
(1
,
1) = 0
, ñëåäîâàòåëüíî,
x
|
y /
∈
T
1
.
f
(0
,
0) = 1
, f
(1
,
1) = 0
, ñëåäîâàòåëüíî,
x
|
y /
∈
M
f
(0
,
1) =
f
(1
,
0) = 1
, íà ïðîòèâîïîëîæíûõ íàáîðàõ
x
|
y
ïðèíèìàåò
îäèíàêîâûå çíà÷åíèÿ, ñëåäîâàòåëüíî
x
|
y /
∈
S
.
Íàêîíåö,
x
|
y
=
x
∧
y
=
xy
+ 1
, ÷òî îçíà÷àåò íåëèíåéíîñòü ôóíêöèè
x
|
y
.
Íà îñíîâàíèè êðèòåðèÿ ïîëíîòû ìîæíî óòâåðæäàòü, ÷òî
f
(
x, y
) =
x
|
y
îáðàçóåò ïîëíóþ ñèñòåìó.
2. Ïîêàæåì, ÷òî ñèñòåìà ôóíêöèé
{
¯
x, x
→
y
}
îáðàçóåò ïîëíóþ ñèñòåìó.
Äåéñòâèòåëüíî,
¯
x /
∈
T
0
,
¯
x /
∈
T
1
,
¯
x /
∈
M,
(
x
→
y
)
/
∈
S, x
→
y
= ¯
x
∨
y
= (
xy
+
x
+ 1)
/
∈
L.
Òåì ñàìûì ñðåäè ôóíêöèé íàøåé ñèñòåìû íàéäåíû: ôóíêöèÿ, íå ñîõðàíÿ-
þùàÿ 0, ôóíêöèÿ, íå ñîõðàíÿþùàÿ 1, íåñàìîäâîéñòâåííàÿ, íåìîíîòîííàÿ è
80
ÃËÀÂÀ 2. ÔÓÍÊÖÈÈ ÀËÃÅÁÐÛ ËÎÃÈÊÈ
íåëèíåéíàÿ ôóíêöèè. Íà îñíîâàíèè êðèòåðèÿ ïîëíîòû ìîæíî óòâåðæäàòü,
÷òî ñèñòåìà ôóíêöèé
{
¯
x, x
→
y
}
îáðàçóåò ïîëíóþ ñèñòåìó.
Òàêèì îáðàçîì ìû óáåäèëèñü, ÷òî êðèòåðèé ïîëíîòû äàåò êîíñòðóêòèâ-
íûé è ýôôåêòèâíûé ñïîñîá âûÿñíåíèÿ ïîëíîòû ñèñòåì ôóíêöèé àëãåáðû
ëîãèêè.
Ñôîðìóëèðóåì òåïåðü òðè ñëåäñòâèÿ èç êðèòåðèÿ ïîëíîòû.
Ñëåäñòâèå 1. Âñÿêèé çàìêíóòûé êëàññ
K
ôóíêöèé àëãåáðû ëîãèêè,
íå ñîâïàäàþùèé ñî âñåì ìíîæåñòâîì ôóíêöèé àëãåáðû ëîãèêè
(
K
6
=
P
2
)
,
ñîäåðæèòñÿ ïî êðàéíåé ìåðå â îäíîì èç ïîñòðîåííûõ çàìêíóòûõ êëàññîâ.
Îïðåäåëåíèå. Çàìêíóòûé êëàññ
K
íàçûâàåòñÿ ïðåäïîëíûì, åñëè
K
íåïîëíûé è äëÿ ëþáîé ôóíêöèè
f /
∈
K
êëàññ
K
∪ {
f
}
ïîëíûé.
Èç îïðåäåëåíèÿ ñëåäóåò, ÷òî ïðåäïîëíûé êëàññ ÿâëÿåòñÿ çàìêíóòûì.
Ñëåäñòâèå 2. Â àëãåáðå ëîãèêè ñóùåñòâóåò òîëüêî ïÿòü ïðåäïîëíûõ
êëàññîâ, à èìåííî:
T
0
, T
1
, L, M, S.
Äëÿ äîêàçàòåëüñòâà ñëåäñòâèÿ íóæíî ïðîâåðèòü òîëüêî òî, ÷òî íè îäèí
èç ýòèõ êëàññîâ íå ñîäåðæèòñÿ â äðóãîì, ÷òî ïîäòâåðæäàåòñÿ, íàïðèìåð,
ñëåäóþùåé òàáëèöåé ïðèíàäëåæíîñòè ôóíêöèé ðàçëè÷íûì êëàññàì:
T
0
T
1
L
S
M
0
+
−
+
−
+
1
−
+
+
−
+
¯
x
−
−
+
+
−
Ñëåäñòâèå 3. Èç âñÿêîé ïîëíîé ñèñòåìû ôóíêöèé ìîæíî âûäåëèòü
ïîë-íóþ ïîäñèñòåìó, ñîäåðæàùóþ íå áîëåå ÷åòûðåõ ôóíêöèé.
Èç äîêàçàòåëüñòâà êðèòåðèÿ ïîëíîòû ñëåäóåò, ÷òî ìîæíî âûäåëèòü íå
áîëåå ïÿòè ôóíêöèé. Èç äîêàçàòåëüñòâà îñíîâíîé ëåììû (ëåììà 2.10) ñëå-
äóåò, ÷òî
f
¯
0
(
x, x, . . . , x
)
/
∈
T
0
ëèáî íåñàìîäâîéñòâåííà, ëèáî íå ñîõðàíÿåò
åäèíèöó è íå ìîíîòîííà. Ïîýòîìó íóæíî íå áîëåå ÷åòûðåõ ôóíêöèé.
2.5.3 Ïðåäñòàâëåíèå î ðåçóëüòàòàõ Ïîñòà
Âåñüìà ãëóáîêîå èçó÷åíèå çàìêíóòûõ êëàññîâ â
P
2
áûëî îñóùåñòâëåíî àìå-
ðèêàíñêèì ìàòåìàòèêîì Ý. Ïîñòîì â 1921 1941 ãîäàõ. Èì áûëà îïèñàíà
ñòðóêòóðà âñåõ çàìêíóòûõ êëàññîâ â
P
2
. Ñôîðìóëèðóåì íåêîòîðûå èç âàæ-
íåéøèõ ðåçóëüòàòîâ ýòèõ èññëåäîâàíèé.
Îïðåäåëåíèå. Ñèñòåìà ôóíêöèé
{
f
1
, f
2
, . . . , f
n
, . . .
}
èç çàìêíóòîãî
êëàññà
K
íàçûâàåòñÿ ïîëíîé â
K
, åñëè åå çàìûêàíèå ñîâïàäàåò ñ
K
.
Èíà÷å ãîâîðÿ, ñèñòåìà ïîëíà â
K
, åñëè êàæäàÿ ôóíêöèÿ èç
K
ìîæåò
áûòü âûðàæåíà â âèäå ôîðìóëû ÷åðåç ôóíêöèè äàííîé ñèñòåìû.