ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.03.2021
Просмотров: 878
Скачиваний: 9
2.5. ÔÓÍÊÖÈÎÍÀËÜÍÀß ÏÎËÍÎÒÀ ÑÈÑÒÅÌ ÔÓÍÊÖÈÉ
71
Äîêàçàòåëüñòâî.
ϕ
∗
(
x
1
, . . . , x
n
) = ¯
f
(¯
x
1
, . . . ,
¯
x
n
) =
ϕ
∗
(
x
1
, . . . , x
n
) = ¯
ϕ
(¯
x
1
, . . . ,
¯
x
n
) =
= ¯
f
(
f
1
(¯
x
11
, . . . ,
¯
x
1
p
1
)
, . . . , f
m
(¯
x
m
1
, . . . ,
¯
x
mp
m
)) =
= ¯
f
( ¯
¯
f
1
(¯
x
11
, . . . ,
¯
x
1
p
1
)
, . . . ,
¯
¯
f
m
(¯
x
m
1
, . . . ,
¯
x
mp
m
)) =
= ¯
f
( ¯
f
∗
1
(
x
11
, . . . , x
1
p
1
)
, . . . ,
¯
f
∗
m
(
x
m
1
, . . . , x
mp
m
)) =
=
f
∗
(
f
∗
1
(
x
11
, . . . , x
1
p
1
)
, . . . , f
∗
m
(
x
m
1
, . . . , x
mp
m
))
.
Òåîðåìà äîêàçàíà.
Èç òåîðåìû âûòåêàåò ïðèíöèï äâîéñòâåííîñòè: åñëè ôîðìóëà
A
ðåà-
ëèçóåò ôóíêöèþ
f
(
x
1
, . . . , x
n
)
, òî ôîðìóëà, ïîëó÷åííàÿ èç
A
çàìåíîé
âõîäÿùèõ â íåå ôóíêöèé íà äâîéñòâåííûå èì, ðåàëèçóåò äâîéñòâåí-
íóþ ôóíêöèþ
f
∗
(
x
1
, . . . , x
n
)
.
Îáîçíà÷èì ÷åðåç
S
êëàññ âñåõ ñàìîäâîéñòâåííûõ ôóíêöèé èç
P
2
:
S
=
{
f
|
f
∗
=
f
}
Ëåãêî âèäåòü, ÷òî åñòü ôóíêöèè, ïðèíàäëåæàùèå
S
, è ôóíêöèè, ýòî-
ìó êëàññó íå ïðèíàäëåæàùèå:
x,
¯
x
∈
L
;
0
,
1
, xy, x
∨
y /
∈
L.
Ìåíåå òðèâèàëüíûì ïðèìåðîì ñàìîäâîéñòâåííîé ôóíêöèè ÿâëÿåòñÿ
ôóíêöèÿ
h
(
x, y, z
) =
xy
∨
xz
∨
yz
;
èñïîëüçóÿ òåîðåìó î ôóíêöèè, äâîéñòâåííîé ê ñóïåðïîçèöèè, èìååì
h
∗
(
x, y, z
) = (
x
∨
y
)
∧
(
x
∨
z
)
∧
(
y
∨
z
) =
xy
∨
xz
∨
yz
=
h
∗
;
h
∈
S.
Äëÿ ñàìîäâîéñòâåííîé ôóíêöèè èìååò ìåñòî òîæäåñòâî:
f
(
x
1
, . . . , x
n
) = ¯
f
(¯
x
1
, . . . ,
¯
x
n
)
,
òàê ÷òî íà íàáîðàõ
(
α
1
, . . . , α
n
)
è
( ¯
α
1
, . . . ,
¯
α
n
)
, êîòîðûå ìû áóäåì
íàçûâàòü ïðîòèâîïîëîæíûìè, ñàìîäâîéñòâåííàÿ ôóíêöèÿ ïðèíèìà-
åò ïðîòèâîïîëîæíûå çíà÷åíèÿ. Îòñþäà ñëåäóåò, ÷òî ñàìîäâîéñòâåí-
íàÿ ôóíêöèÿ ïîëíîñòüþ îïðåäåëÿåòñÿ ñâîèìè çíà÷åíèÿìè íà ïåðâîé
72
ÃËÀÂÀ 2. ÔÓÍÊÖÈÈ ÀËÃÅÁÐÛ ËÎÃÈÊÈ
ïîëîâèíå ñòðîê ñòàíäàðòíîé òàáëèöû. Ïîýòîìó ÷èñëî ñàìîäâîéñòâåí-
íûõ ôóíêöèé â êëàññå
S
(
n
)
ôóíêöèé, çàâèñÿùèõ îò n ïåðåìåííûõ,
ðàâíî:
|
S
(
n
)
|
= 2
2
n
−
1
.
Äîêàæåì òåïåðü, ÷òî êëàññ
S
çàìêíóò. Òàê êàê
x
∈
S
, òî äëÿ îáîñ-
íîâàíèÿ çàìêíóòîñòè äîñòàòî÷íî ïîêàçàòü çàìêíóòîñòü îòíîñèòåëü-
íî îïåðàöèè ñóïåðïîçèöèè, ïîñêîëüêó îïåðàöèÿ çàìåíû ïåðåìåííûõ
åñòü ÷àñòíûé ñëó÷àé ñóïåðïîçèöèè ñ ôóíêöèåé
x
. Ïóñòü
f
(˜
x
m
)
,
f
1
(
x
k
1
)
, . . . , f
m
(˜
x
k
m
)
∈
S
. Òîãäà äîñòàòî÷íî ïîêàçàòü, ÷òî
ϕ
=
f
(
f
1
, . . . , f
m
)
∈
S.
Ïîñëåäíåå óñòàíàâëèâàåòñÿ íåïîñðåäñòâåííî:
ϕ
∗
=
f
∗
(
f
∗
1
, . . . , f
∗
m
) =
f
(
f
1
, . . . , f
m
)
.
5. Ì êëàññ ìîíîòîííûõ ôóíêöèé.
Ïðåæäå ÷åì îïðåäåëÿòü ïîíÿòèå ìîíîòîííîé ôóíêöèè àëãåáðû ëî-
ãèêè, íåîáõîäèìî ââåñòè îòíîøåíèå óïîðÿäî÷åííîñòè íà ìíîæåñòâå
íàáîðîâ åå ïåðåìåííûõ.
Ãîâîðÿò, ÷òî íàáîð
˜
α
= ˜
α
n
= (
α
1
, . . . , α
n
)
ïðåäøåñòâóåò íàáîðó
˜
β
= ˜
β
n
= (
β
1
, . . . , β
n
)
(èëè ¾íå áîëüøå
˜
β
¿, èëè ¾ìåíüøå èëè ðà-
âåí
˜
β
¿), è ïðèìåíÿþò îáîçíà÷åíèå
˜
α
≤
˜
β
, åñëè
α
i
≤
β
i
äëÿ âñåõ
i
= 1
, . . . , n
. Åñëè
˜
α
≤
˜
β
è
˜
α
6
= ˜
β
, òî áóäåì ãîâîðèòü, ÷òî íàáîð
˜
α
ñòðîãî ïðåäøåñòâóåò íàáîðó
˜
β
(èëè ¾ñòðîãî ìåíüøå¿, èëè ¾ìåíüøå¿
íàáîðà
˜
β
), è èñïîëüçîâàòü îáîçíà÷åíèå
˜
α <
˜
β
. Íàáîðû
˜
α
è
˜
β
íàçûâà-
þòñÿ ñðàâíèìûìè, åñëè ëèáî
˜
α
≤
˜
β
, ëèáî
˜
β
≤
˜
α
.  ñëó÷àå, êîãäà íè
îäíî èç ýòèõ ñîîòíîøåíèé íå âûïîëíÿåòñÿ, íàáîðû
˜
α
è
˜
β
íàçûâàþòñÿ
íåñðàâíèìûìè. Íàïðèìåð,
(0
,
1
,
0
,
1)
≤
(1
,
1
,
0
,
1)
, íî íàáîðû
(0
,
1
,
1
,
0)
è
(1
,
0
,
1
,
0)
íåñðàâíèìû. Òåì ñàìûì îòíîøåíèå
≤
(åãî ÷àñòî íàçû-
âàþò îòíîøåíèåì ïðåäøåñòâîâàíèÿ) ÿâëÿåòñÿ ÷àñòè÷íûì ïîðÿäêîì
íà ìíîæåñòâå
B
n
. Íèæå ïðèâåäåíû äèàãðàììû ÷àñòè÷íî óïîðÿäî÷åí-
íûõ ìíîæåñòâ
B
2
, B
3
è
B
4
.
2.5. ÔÓÍÊÖÈÎÍÀËÜÍÀß ÏÎËÍÎÒÀ ÑÈÑÒÅÌ ÔÓÍÊÖÈÉ
73
Ââåäåííîå îòíîøåíèå ÷àñòè÷íîãî ïîðÿäêà èñêëþ÷èòåëüíî âàæíîå
ïîíÿòèå, äàëåêî âûõîäÿùåå çà ðàìêè íàøåãî êóðñà.
Òåïåðü ìû èìååì âîçìîæíîñòü îïðåäåëèòü ïîíÿòèå ìîíîòîííîé ôóíê-
öèè.
Ôóíêöèÿ àëãåáðû ëîãèêè
f
(˜
x
n
)
íàçûâàåòñÿ ìîíîòîííîé, åñëè äëÿ
ëþáûõ äâóõ íàáîðîâ
˜
α
n
è
˜
β
n
, òàêèõ, ÷òî
˜
α
n
≤
˜
β
n
, èìååò ìåñòî íåðà-
âåíñòâî
f
( ˜
α
n
)
≤
f
( ˜
β
n
)
. Ìíîæåñòâî âñåõ ìîíîòîííûõ ôóíêöèé àë-
ãåáðû ëîãèêè îáîçíà÷àåòñÿ ÷åðåç
M
, à ìíîæåñòâî âñåõ ìîíîòîííûõ
ôóíêöèé, çàâèñÿùèõ îò
n
ïåðåìåííûõ ÷åðåç
M
(
n
)
.
Ëåãêî âèäåòü, ÷òî åñòü ôóíêöèè, ïðèíàäëåæàùèå
M
, è ôóíêöèè, ýòî-
ìó êëàññó íå ïðèíàäëåæàùèå:
0
,
1
, x, xy, x
∨
y
∈
M
;
x
+
y, x
→
y, x
≡
y /
∈
M.
Ïîêàæåì, ÷òî êëàññ ìîíîòîííûõ ôóíêöèé
M
çàìêíóòûé êëàññ.
Òàê êàê
x
∈
M
, òî äëÿ îáîñíîâàíèÿ çàìêíóòîñòè äîñòàòî÷íî ïîêà-
çàòü çàìêíóòîñòü îòíîñèòåëüíî îïåðàöèè ñóïåðïîçèöèè, ïîñêîëüêó
îïåðàöèÿ çàìåíû ïåðåìåííûõ åñòü ÷àñòíûé ñëó÷àé ñóïåðïîçèöèè ñ
ôóíêöèåé
x
.
Ïóñòü
f
(˜
x
m
)
, f
1
(˜
x
k
1
)
, . . . , f
m
(˜
x
k
m
)
∈
M
. Òîãäà äîñòàòî÷íî ïîêàçàòü,
÷òî
ϕ
=
f
(
f
1
, . . . , f
m
)
∈
M
.
Ïóñòü
˜
x
= ˜
x
n
= (
x
1
, . . . , x
n
)
,
˜
x
k
1
= (
x
11
, . . . , x
1
k
1
)
, . . . ,
˜
x
k
m
= (
x
m
1
, . . . , x
mk
m
)
íàáîðû ïåðåìåííûõ, ñîîòâåòñòâåííî, ôóíê-
öèé
ϕ, f
1
, . . . , f
m
, ïðè÷åì ìíîæåñòâî ïåðåìåííûõ ôóíêöèè
ϕ
ñîñòî-
èò èç òåõ è òîëüêî òåõ ïåðåìåííûõ, êîòîðûå âñòðå÷àþòñÿ ó ôóíêöèé
74
ÃËÀÂÀ 2. ÔÓÍÊÖÈÈ ÀËÃÅÁÐÛ ËÎÃÈÊÈ
f
1
, . . . , f
m
. Ïóñòü
˜
α
è
˜
β
äâà íàáîðà çíà÷åíèé ïåðåìåííîé
˜
x
, ïðè÷åì
˜
α
≤
˜
β
. Ýòè íàáîðû îïðåäåëÿþò íàáîðû
˜
α
k
1
,
˜
β
k
1
, . . . ,
˜
α
k
m
,
˜
β
k
m
çíà÷å-
íèé ïåðåìåííûõ
˜
x
k
1
, . . . ,
˜
x
k
m
, òàêèå, ÷òî
˜
α
k
1
≤
˜
β
k
1
, . . . ,
˜
α
k
m
≤
˜
β
k
m
.
 ñèëó ìîíîòîííîñòè ôóíêöèé
f
1
, . . . , f
m
f
1
( ˜
α
k
1
)
≤
f
1
( ˜
β
k
1
)
, . . . , f
m
( ˜
α
k
m
)
≤
f
m
( ˜
β
k
m
)
,
ïîýòîìó
(
f
1
( ˜
α
k
1
)
, . . . , f
m
( ˜
α
k
m
))
≤
(
f
1
( ˜
β
k
1
)
, . . . , f
m
( ˜
β
k
m
))
,
è â ñèëó ìîíîòîííîñòè ôóíêöèè
f
f
(
f
1
( ˜
α
k
1
)
, . . . , f
m
( ˜
α
k
m
))
≤
f
(
f
1
( ˜
β
k
1
)
, . . . , f
m
( ˜
β
k
m
))
.
Îòñþäà ïîëó÷àåì
ϕ
( ˜
α
) =
f
(
f
1
( ˜
α
k
1
)
, . . . , f
m
( ˜
α
k
m
))
≤
f
(
f
1
( ˜
β
k
1
)
, . . . , f
m
( ˜
β
k
m
)) =
ϕ
( ˜
β
)
×èñëî ìîíîòîííûõ ôóíêöèé, çàâèñÿùèõ îò n ïåðåìåííûõ, òî÷íî íåèç-
âåñòíî. Ëåãêî ìîæåò áûòü ïîëó÷åíà îöåíêà ñíèçó:
|
M
(
n
)
| ≥
2(
n
[
n/
2]
)
,
ãäå
[
n/
2]
åñòü öåëàÿ ÷àñòü îò
n/
2
.
Òàê æå ïðîñòî ïîëó÷àåòñÿ ñëèøêîì çàâûøåííàÿ îöåíêà ñâåðõó:
|
M
(
n
)
| ≤
2 +
n
(
n
[
n/
2]
)
.
Óòî÷íåíèå ýòèõ îöåíîê âàæíàÿ è èíòåðåñíàÿ çàäà÷à ñîâðåìåííûõ
èññëåäîâàíèé.
2.5.2 Êðèòåðèé ïîëíîòû
Òåïåðü ìû â ñîñòîÿíèè ñôîðìóëèðîâàòü è äîêàçàòü êðèòåðèé ïîëíîòû (òåî-
ðåìó Ïîñòà), îïðåäåëÿþùèé íåîáõîäèìûå è äîñòàòî÷íûå óñëîâèÿ ïîëíîòû
ñèñòåìû ôóíêöèé. Ïðåäâàðèì ôîðìóëèðîâêó è äîêàçàòåëüñòâî êðèòåðèÿ
ïîëíîòû íåñêîëüêèìè íåîáõîäèìûìè ëåììàìè, èìåþùèìè è ñàìîñòîÿòåëü-
íûé èíòåðåñ.
Ëåììà 2.7 (Ëåììà î íåñàìîäâîéñòâåííîé ôóíêöèè.). Åñëè
f
(
x
1
, . . . , x
n
)
/
∈
S
, òî èç íåå ïóòåì ïîäñòàíîâêè ôóíêöèé
x
è
¯
x
ìîæíî
ïîëó÷èòü êîíñòàíòó.
2.5. ÔÓÍÊÖÈÎÍÀËÜÍÀß ÏÎËÍÎÒÀ ÑÈÑÒÅÌ ÔÓÍÊÖÈÉ
75
Äîêàçàòåëüñòâî. Òàê êàê
f /
∈
S
, òî íàéäåòñÿ íàáîð çíà÷åíèé ïåðåìåííûõ
α
= (
α
1
, . . . , α
n
)
òàêîé, ÷òî
f
( ¯
α
1
, . . . ,
¯
α
n
) =
f
(
α
1
, . . . , α
n
)
Çàìåíèì àðãóìåíòû â ôóíêöèè
f
:
x
i
çàìåíÿåòñÿ íà
(
x,
åñëè
α
i
= 1
â íàáîðå
α
;
¯
x,
åñëè
α
i
= 0
â íàáîðå
α,
òî åñòü ïîëîæèì
x
i
=
x
α
i
, è ðàññìîòðèì ôóíêöèþ
ϕ
(
x
) =
f
(
x
α
1
, x
α
2
, . . . , x
α
n
)
.
Ìû èìååì
ϕ
(0) =
f
(0
α
1
,
. . . ,
0
α
n
) =
f
( ¯
α
1
,
. . . ,
¯
α
n
) =
f
(
α
1
,
. . . ,
α
n
) =
=
f
(1
α
1
, . . . ,
1
α
n
) =
ϕ
(1)
.
Òåì ñàìûì ìû ïîëó÷èëè êîíñòàíòó (ïðàâäà, íåèçâåñòíî, êàêàÿ ýòî êîí-
ñòàíòà: 0 èëè 1).
Ëåììà 2.8 (Ëåììà î íåìîíîòîííîé ôóíêöèè.). Åñëè ôóíêöèÿ
f
(
x
1
, . . . , x
n
)
íåìîíîòîííà,
f
(
x
1
, . . . , x
n
)
/
∈
M
, òî èç íåå ïóòåì çàìåíû
ïåðåìåííûõ è ïîäñòàíîâêè êîíñòàíò 0 è 1 ìîæíî ïîëó÷èòü îòðèöàíèå.
Äîêàçàòåëüñòâî. Òàê êàê
f
(
x
1
, . . . , x
n
)
/
∈
M
, òî íàéäóòñÿ íàáîðû
˜
α
è
˜
β
çíà÷åíèé åå ïåðåìåííûõ,
˜
α
= (
α
1
, . . . , α
n
)
,
˜
β
= (
β
1
, . . . , β
n
)
, òàêèå ÷òî
˜
α
≤
˜
β
è
f
( ˜
α
)
> f
( ˜
β
)
, ïðè÷åì õîòÿ áû äëÿ îäíîãî çíà÷åíèÿ
i
èìååò ìåñòî
α
i
< β
i
. Âûïîëíèì ñëåäóþùóþ çàìåíó ïåðåìåííûõ ôóíêöèè
f
:
x
i
çàìåíèì íà
0
,
åñëè
α
i
=
β
i
= 0;
1
,
åñëè
α
i
=
β
i
= 1;
x,
åñëè
α
i
< β
i
.
Ïîñëå òàêîé ïîäñòàíîâêè ïîëó÷èì ôóíêöèþ îäíîé ïåðåìåííîé
ϕ
(
x
)
, äëÿ
êîòîðîé èìååì:
ϕ
(0) =
f
( ¯
α
) = 1;
ϕ
(1) =
f
( ¯
β
) = 0
.
Ýòî îçíà÷àåò, ÷òî
ϕ
(
x
) = ¯
x
. Ëåììà äîêàçàíà.