ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.03.2021
Просмотров: 881
Скачиваний: 9
66
ÃËÀÂÀ 2. ÔÓÍÊÖÈÈ ÀËÃÅÁÐÛ ËÎÃÈÊÈ
ïðè
i
6
=
k
. Î÷åâèäíî, ÷òî çàìåíà ïåðåìåííûõ âêëþ÷àåò â ñåáÿ ïåðå-
èìåíîâàíèå ïåðåìåííûõ, ïåðåñòàíîâêó ïåðåìåííûõ è îòîæäåñòâëåíèå
ïåðåìåííûõ.
Ïðèìåð Ïóñòü èìååòñÿ ôóíêöèÿ
f
(
x
1
, x
2
) =
x
1
|
x
2
. Òîãäà ïðè çà-
ìåíå ïåðåìåííûõ
x
1
x
2
y
y
èç ôóíêöèè
f
(
x
1
, x
2
)
ìîæíî ïîëó÷èòü
ôóíêöèþ
ϕ
(
y
) =
f
(
y, y
) =
y
|
y
= ¯
y
.
2. Ñóïåðïîçèöèÿ ôóíêöèé àëãåáðû ëîãèêè.
Îïðåäåëåíèå. Ïóñòü èìååòñÿ ôóíêöèÿ
f
(
x
1
, x
2
, . . . , x
n
)
è ôóíêöèè
f
1
(
x
i
1
, . . . , x
m
i
)
, i
= 1
, . . . , n,
òîãäà ôóíêöèþ
ϕ
=
f
(
f
1
(
x
1
1
, . . . , x
1
m
1
)
, . . . , f
n
(
x
n
1
, . . . , x
n
mn
))
áóäåì íàçûâàòü ñóïåðïîçèöèåé ôóíêöèè
f
(
x
1
, x
2
, . . . , x
n
)
è ôóíêöèé
f
i
(
x
i
1
, . . . , x
i
mi
)
, i
= 1
, . . . , n.
Äðóãèìè ñëîâàìè: ïóñòü
F
=
{
f
j
}
íàáîð ôóíêöèé àëãåáðû ëîãèêè, íå
îáÿçàòåëüíî êîíå÷íûé. Ôóíêöèÿ
f
íàçûâàåòñÿ ñóïåðïîçèöèåé ôóíêöèé èç
ìíîæåñòâà
F
èëè ôóíêöèåé íàä
F
, åñëè îíà ïîëó÷åíà èç ôóíêöèè
f
j
∈
F
ïóòåì çàìåíû îäíîé èëè íåñêîëüêèõ åå ïåðåìåííûõ ôóíêöèÿìè èç ìíîæå-
ñòâà
F
.
Ïðèìåð.
Ïóñòü çàäàíî ìíîæåñòâî ôóíêöèé
F
=
{
f
1
(
x
1
)
, f
2
(
x
1
, x
2
, x
3
)
, f
3
(
x
1
, x
2
)
}
.
Òîãäà ñóïåðïîçèöèÿìè ôóíêöèé èç F áóäóò, íàïðèìåð, ôóíêöèè:
ϕ
1
(
x
2
, x
3
) =
f
3
(
f
1
(
x
2
)
, f
1
(
x
3
));
ϕ
2
(
x
1
, x
2
) =
f
2
(
x
1
, f
1
(
x
1
)
, f
3
(
x
1
, x
2
))
.
Ñîâåðøåííàÿ ÄÍÔ ñóïåðïîçèöèÿ ôóíêöèé èç ìíîæåñòâà
{
x
1
∨
x
2
, x
1
∧
x
2
,
¯
x
}
Îïðåäåëåíèå. Ñèñòåìà ôóíêöèé íàçûâàåòñÿ ïîëíîé, åñëè ïðè ïîìîùè
îïåðàöèé ñóïåðïîçèöèè è çàìåíû ïåðåìåííûõ èç ôóíêöèé ýòîé ñèñòåìû
ìîæåò áûòü ïîëó÷åíà ëþáàÿ ôóíêöèÿ àëãåáðû ëîãèêè.
2.5. ÔÓÍÊÖÈÎÍÀËÜÍÀß ÏÎËÍÎÒÀ ÑÈÑÒÅÌ ÔÓÍÊÖÈÉ
67
Ìû óæå èìååì íåêîòîðûé íàáîð ïîëíûõ ñèñòåì:
{
x
∨
y, xy,
¯
x
}
;
{
xy,
¯
x
}
, òàê êàê
x
∨
y
= ¯
x
∧
¯
y
;
{
x
∨
y,
¯
x
}
, òàê êàê
xy
= ¯
x
∨
¯
y
{
x
+
y, xy,
1
}
.
Êàê æå îïðåäåëèòü óñëîâèÿ, ïðè êîòîðûõ ñèñòåìà ïîëíà. Ñ ïîíÿòèåì
ïîëíîòû òåñíî ñâÿçàíî ïîíÿòèå çàìêíóòîãî êëàññà.
2.5.1 Çàìêíóòûå êëàññû
Ìíîæåñòâî (êëàññ)
K
ôóíêöèé àëãåáðû ëîãèêè íàçûâàåòñÿ çàìêíóòûì
êëàññîì, åñëè îíî ñîäåðæèò âñå ôóíêöèè, ïîëó÷àþùèåñÿ èç
K
îïåðàöè-
ÿìè ñóïåðïîçèöèè è çàìåíû ïåðåìåííûõ, è íå ñîäåðæèò íèêàêèõ äðóãèõ
ôóíêöèé.
Ïóñòü
K
íåêîòîðîå ïîäìíîæåñòâî ôóíêöèé èç
P
2
. Çàìûêàíèåì
K
íàçûâàåòñÿ ìíîæåñòâî âñåõ áóëåâûõ ôóíêöèé, ïðåäñòàâèìûõ ñ ïîìîùüþ
îïåðàöèé ñóïåðïîçèöèè è çàìåíû ïåðåìåííûõ ôóíêöèé èç ìíîæåñòâà
K
.
Çàìûêàíèå ìíîæåñòâà
K
îáîçíà÷àåòñÿ ÷åðåç
[
K
]
.
 òåðìèíàõ çàìûêàíèÿ ìîæíî äàòü äðóãèå îïðåäåëåíèÿ çàìêíóòîñòè è
ïîëíîòû (ýêâèâàëåíòíûå èñõîäíûì):
K
çàìêíóòûé êëàññ, åñëè
K
= [
K
]
;
K
ïîëíàÿ ñèñòåìà, åñëè
[
K
] =
P
2
.
Ïðèìåðû.
• {
0
}
,
{
1
}
çàìêíóòûå êëàññû.
•
Ìíîæåñòâî ôóíêöèè îäíîé ïåðåìåííîé çàìêíóòûé êëàññ.
• {
x,
¯
x
}
çàìêíóòûé êëàññ.
•
Êëàññ
{
1
, x
+
y
}
íå ÿâëÿåòñÿ çàìêíóòûì êëàññîì.
Ðàññìîòðèì íåêîòîðûå âàæíåéøèå çàìêíóòûå êëàññû.
1.
T
0
êëàññ ôóíêöèé, ñîõðàíÿþùèõ 0.
Îáîçíà÷èì ÷åðåç
T
0
êëàññ âñåõ ôóíêöèé àëãåáðû ëîãèêè
f
(
x
1
, x
2
, . . . , x
n
)
, ñîõðàíÿþùèõ êîíñòàíòó 0, òî åñòü ôóíêöèé, äëÿ
êîòîðûõ
f
(0
, . . . ,
0) = 0
.
T
0
=
{
f
(
x
1
, x
2
, . . . , x
n
)
|
f
(0
, . . . ,
0) = 0
}
.
68
ÃËÀÂÀ 2. ÔÓÍÊÖÈÈ ÀËÃÅÁÐÛ ËÎÃÈÊÈ
Ëåãêî âèäåòü, ÷òî åñòü ôóíêöèè, ïðèíàäëåæàùèå
T
0
, è ôóíêöèè, ýòî-
ìó êëàññó íå ïðèíàäëåæàùèå:
0
, x, xy, x
∨
y, x
+
y
∈
T
0
1
,
¯
x /
∈
T
0
Èç òîãî, ÷òî
¯
x /
∈
T
0
ñëåäóåò, íàïðèìåð, ÷òî
¯
x
íåëüçÿ âûðàçèòü ÷åðåç
äèçúþíêöèþ è êîíúþíêöèþ.
Ïîñêîëüêó òàáëèöà äëÿ ôóíêöèè
f
èç êëàññà
T
0
â ïåðâîé ñòðîêå ñî-
äåðæèò çíà÷åíèå 0, òî äëÿ ôóíêöèé èç
T
0
ìîæíî çàäàâàòü ïðîèç-
âîëüíûå çíà÷åíèÿ òîëüêî íà
2
n
−
1
íàáîðå çíà÷åíèé ïåðåìåííûõ, òî
åñòü
|
T
(
n
)
0
|
= 2
2
n
−
1
=
1
2
|
P
2
|
,
ãäå
T
(
n
)
0
ìíîæåñòâî ôóíêöèé, ñîõðàíÿþùèõ 0 è çàâèñÿùèõ îò
n
ïåðåìåííûõ.
Ïîêàæåì, ÷òî
T
0
çàìêíóòûé êëàññ. Òàê êàê
x
∈
T
0
, òî äëÿ îáîñ-
íîâàíèÿ çàìêíóòîñòè äîñòàòî÷íî ïîêàçàòü çàìêíóòîñòü îòíîñèòåëü-
íî îïåðàöèè ñóïåðïîçèöèè, ïîñêîëüêó îïåðàöèÿ çàìåíû ïåðåìåííûõ
åñòü ÷àñòíûé ñëó÷àé ñóïåðïîçèöèè ñ ôóíêöèåé
x
.
Ïóñòü
f
(˜
x
m
)
, f
1
(˜
x
k
1
)
, . . . , f
m
(˜
x
k
m
)
∈
T
0
. Òîãäà äîñòàòî÷íî ïîêàçàòü,
÷òî
ϕ
=
f
(
f
1
, . . . , f
m
)
∈
T
0
. Ïîñëåäíåå âûòåêàåò èç öåïî÷êè ðàâåíñòâ
ϕ
(0
, . . . ,
0) =
f
(
f
1
(0
, . . . ,
0)
, . . . , f
m
(0
, . . . ,
0)) =
f
(0
, . . . ,
0) = 0
.
2.
T
1
êëàññ ôóíêöèé, ñîõðàíÿþùèõ 1.
Îáîçíà÷èì ÷åðåç
T
1
êëàññ âñåõ ôóíêöèé àëãåáðû ëîãèêè
f
(
x
1
, x
2
, . . . , x
n
)
, ñîõðàíÿþùèõ êîíñòàíòó 1, òî åñòü ôóíêöèé, äëÿ
êîòîðûõ
f
(1
, . . . ,
1) = 1
.
T
1
=
{
f
(
x
1
, x
2
, . . . , x
n
)
|
f
(1
, . . . ,
1) = 1
}
Ëåãêî âèäåòü, ÷òî åñòü ôóíêöèè, ïðèíàäëåæàùèå
T
1
, è ôóíêöèè, ýòî-
ìó êëàññó íå ïðèíàäëåæàùèå:
1
, x, xy, x
∨
y, x
≡
y
∈
T
1
0
,
¯
x, x
+
y /
∈
T
1
Èç òîãî, ÷òî
x
+
y /
∈
T
0
ñëåäóåò, íàïðèìåð, ÷òî
x
+
y
íåëüçÿ âûðàçèòü
÷åðåç äèçúþíêöèþ è êîíúþíêöèþ.
2.5. ÔÓÍÊÖÈÎÍÀËÜÍÀß ÏÎËÍÎÒÀ ÑÈÑÒÅÌ ÔÓÍÊÖÈÉ
69
Ðåçóëüòàòû î êëàññå
T
0
òðèâèàëüíî ïåðåíîñÿòñÿ íà êëàññ
T
1
. Òàêèì
îáðàçîì, èìååì:
T
1
çàìêíóòûé êëàññ;
|
T
(
n
)
1
|
= 2
2
n
−
1
=
1
2
|
P
2
|
.
3.
L
êëàññ ëèíåéíûõ ôóíêöèé.
Îáîçíà÷èì ÷åðåç
L
êëàññ âñåõ ôóíêöèé àëãåáðû ëîãèêè
f
(
x
1
, x
2
, . . . , x
n
)
, ÿâëÿþùèõñÿ ëèíåéíûìè:
L
=
f
(
x
1
, x
2
, . . . , x
n
)
:
f
(
x
1
, x
2
, . . . , x
n
) =
α
0
+
α
1
x
1
+
. . .
. . .
+
α
n
x
n
;
α
i
∈ {
0
,
1
}
, i
= 1
, . . . , n
Ëåãêî âèäåòü, ÷òî åñòü ôóíêöèè, ïðèíàäëåæàùèå
L
, è ôóíêöèè, ýòî-
ìó êëàññó íå ïðèíàäëåæàùèå:
0
,
1
, x, x
+
y, x
1
≡
x
2
=
x
1
+
x
2
+ 1
,
¯
x
=
x
+ 1
∈
L
;
xy, x
∨
y /
∈
L.
Äîêàæåì, íàïðèìåð, ÷òî
x
∨
y /
∈
L
.
Ïðåäïîëîæèì ïðîòèâíîå. Áóäåì èñêàòü âûðàæåíèå äëÿ
x
∨
y
â âèäå
ëèíåéíîé ôóíêöèè ñ íåîïðåäåëåííûìè êîýôôèöèåíòàìè:
x
∨
y
=
α
+
βx
+
γy
Ïðè
x
=
y
= 0
èìååì
α
= 0
,
ïðè
x
= 1
,
y
= 0
èìååì
β
= 1
,
ïðè
x
= 0
,
y
= 1
èìååì
γ
= 1
,
íî òîãäà ïðè
x
= 1
,
y
= 1
èìååì
1
∨
1
6
= 1 + 1
, ÷òî äîêàçûâàåò
íåëèíåéíîñòü ôóíêöèè
x
∨
y
.
Äîêàçàòåëüñòâî çàìêíóòîñòè êëàññà ëèíåéíûõ ôóíêöèé ñîâåðøåííî
î÷åâèäíî.
Ïîñêîëüêó ëèíåéíàÿ ôóíêöèÿ îäíîçíà÷íî îïðåäåëÿåòñÿ çàäàíèåì çíà-
÷åíèé
n
+ 1
êîýôôèöèåíòà
α
0
, . . . , α
n
, ÷èñëî ëèíåéíûõ ôóíêöèé â
êëàññå
L
(
n
)
ôóíêöèé, çàâèñÿùèõ îò
n
ïåðåìåííûõ ðàâíî
2
n
+1
.
|
L
(
n
)
|
= 2
n
+1
.
70
ÃËÀÂÀ 2. ÔÓÍÊÖÈÈ ÀËÃÅÁÐÛ ËÎÃÈÊÈ
4.
S
êëàññ ñàìîäâîéñòâåííûõ ôóíêöèé.
Îïðåäåëåíèå êëàññà ñàìîäâîéñòâåííûõ ôóíêöèé îñíîâàíî íà èñïîëü-
çîâàíèè òàê íàçûâàåìîãî ïðèíöèïà äâîéñòâåííîñòè è äâîéñòâåííûõ
ôóíêöèé.
Îïðåäåëåíèå. Ôóíêöèÿ
f
∗
(˜
x
n
)
, îïðåäåëÿåìàÿ ðàâåíñòâîì
f
∗
(˜
x
n
) =
¯
f
(¯
x
1
, . . . ,
¯
x
n
)
íàçûâàåòñÿ äâîéñòâåííîé ê ôóíêöèè
f
(˜
x
n
)
.
Î÷åâèäíî, ÷òî òàáëèöà äëÿ äâîéñòâåííîé ôóíêöèè (ïðè ñòàíäàðòíîé
óïîðÿäî÷åííîñòè íàáîðîâ çíà÷åíèé ïåðåìåííûõ) ïîëó÷àåòñÿ èç òàá-
ëèöû äëÿ èñõîäíîé ôóíêöèè èíâåðòèðîâàíèåì (òî åñòü çàìåíîé 0 íà
1 è 1 íà 0) ñòîëáöà çíà÷åíèé ôóíêöèè è åãî ïåðåâîðà÷èâàíèåì.
Ëåãêî âèäåòü, ÷òî:
0
∗
= 1
,
1
∗
= 0
,
x
∗
=
x,
¯
x
∗
= ¯
x,
(
x
1
∨
x
2
)
∗
=
x
1
∧
x
2
,
(
x
1
∧
x
2
)
∗
=
x
1
∨
x
2
.
Èç îïðåäåëåíèÿ âûòåêàåò, ÷òî
(
f
∗
)
∗
=
f
, òî åñòü ôóíêöèÿ f ÿâëÿåòñÿ
äâîéñòâåííîé ê
f
∗
.
Ïóñòü ôóíêöèÿ âûðàæåíà ñ ïîìîùüþ ñóïåðïîçèöèè ÷åðåç äðóãèå
ôóíêöèè. Ñïðàøèâàåòñÿ, êàê ïîñòðîèòü ôîðìóëó, ðåàëèçóþùóþ
f
∗
(˜
x
n
)
?
Îáîçíà÷èì ÷åðåç
˜
x
n
= (
x
1
, . . . , x
n
)
âñå ðàçëè÷íûå ñèìâîëû ïåðåìåí-
íûõ, âñòðå÷àþùèåñÿ â íàáîðàõ
(
x
11
, . . . , x
1
p
1
)
, . . . ,
(
x
m
1
, . . . , x
mp
m
)
.
Òåîðåìà 2.6. Åñëè ôóíêöèÿ
ϕ
ïîëó÷åíà êàê ñóïåðïîçèöèÿ ôóíêöèé
f, f
1
, f
2
, . . . , f
m
, òî åñòü
ϕ
(
x
1
, . . . , x
n
) =
f
(
f
1
(
x
11
, . . . , x
1
p
1
)
, . . . , f
m
(
x
m
1
, . . . , x
mp
m
))
,
òî
ϕ
∗
(
x
1
, . . . , x
n
) =
f
∗
(
f
∗
1
(
x
11
, . . . , x
1
p
1
)
, . . . , f
∗
m
(
x
m
1
, . . . , x
mp
m
))
−
ôóíêöèÿ, äâîéñòâåííàÿ ê ñóïåðïîçèöèè, åñòü ñóïåðïîçèöèÿ äâîé-
ñòâåííûõ ôóíêöèé.