ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.03.2021
Просмотров: 882
Скачиваний: 9
2.4. ÐÀÇËÎÆÅÍÈÅ ÔÓÍÊÖÈÉ ÀËÃÅÁÐÛ ËÎÃÈÊÈ ÏÎ ÏÅÐÅÌÅÍÍÛÌ61
Ëåãêî âèäåòü, ÷òî
x
σ
= 1
òîãäà è òîëüêî òîãäà, êîãäà
x
=
σ
, òî åñòü
çíà÷åíèå ¾îñíîâàíèÿ¿ ðàâíî çíà÷åíèþ ¾ïîêàçàòåëÿ¿.
Ëåììà 2.2 (Î ðàçëîæåíèè ôóíêöèè ïî îäíîé ïåðåìåííîé). Ïóñòü
f
(
x
1
, . . . , x
n
)
ïðîèçâîëüíàÿ ôóíêöèÿ àëãåáðû ëîãèêè, òîãäà ñïðàâåäëèâî
ñëåäóþùåå ïðåäñòàâëåíèå
f
â ôîðìå ðàçëîæåíèÿ ïî ïåðåìåííîé
x
1
:
(2
.
1)
f
(
x
1
, . . . , x
n
) =
x
1
·
f
(1
, x
2
, . . . , x
n
)
∨
¯
x
1
·
f
(0
, x
2
, . . . , x
n
)
Äîêàçàòåëüñòâî. Îòìåòèì ïðåæäå âñåãî, ÷òî ïðåäñòàâëåíèå (2.1), åñòå-
ñòâåííî, ñïðàâåäëèâî äëÿ ïðîèçâîëüíîé ïåðåìåííîé
x
i
èç ìíîæåñòâà ïåðå-
ìåííûõ ôóíêöèè
f
. Äëÿ äîêàçàòåëüñòâà ðàññìîòðèì ïðîèçâîëüíûé íàáîð
çíà÷åíèé ïåðåìåííûõ
(
α
1
, . . . , α
n
)
è ïîêàæåì, ÷òî ëåâàÿ è ïðàâàÿ ÷àñòè
ñîîòíîøåíèÿ (2.1) ïðèíèìàþò íà í¼ì îäíî è òî æå çíà÷åíèå.
Ðàññìîòðèì íàáîð çíà÷åíèé ïåðåìåííûõ
(1
, α
2
, . . . , α
n
)
. Ëåâàÿ ÷àñòü
(2.1) ïðèíèìàåò íà ýòîì íàáîðå çíà÷åíèå
f
(1
, α
2
, . . . , α
n
)
, à ïðàâàÿ ÷àñòü
çíà÷åíèå
1
·
f
(1
, α
2
, . . . , α
n
)
∨
0
·
f
(0
, α
2
, . . . , α
n
) =
f
(1
, α
2
, . . . , α
n
)
.
Òàêèì îáðàçîì, íà íàáîðàõ
(1
, α
2
, . . . , α
n
)
ëåâàÿ è ïðàâàÿ ÷àñòè (2.1)
ïðèíèìàþò îäèíàêîâûå çíà÷åíèÿ.
Ðàññìîòðèì íàáîð çíà÷åíèé ïåðåìåííûõ
(0
, α
2
, . . . , α
n
)
. Ëåâàÿ ÷àñòü
(2.1) ïðèíèìàåò íà ýòîì íàáîðå çíà÷åíèå
f
(0
, α
2
, . . . , α
n
)
, à ïðàâàÿ ÷àñòü
çíà÷åíèå
0
·
f
(1
, α
2
, . . . , α
n
)
∨
1
·
f
(0
, α
2
, . . . , α
n
) =
f
(0
, α
2
, . . . , α
n
)
.
Òàêèì îáðàçîì, íà íàáîðàõ
(0
, α
2
, . . . , α
n
)
ëåâàÿ è ïðàâàÿ ÷àñòè (2.1)
ïðèíèìàþò îäèíàêîâûå çíà÷åíèÿ.
Òåì ñàìûì ìû äîêàçàëè, ÷òî ëåâàÿ è ïðàâàÿ ÷àñòè ñîîòíîøåíèÿ (2.1)
ïðèíèìàþò îäèíàêîâûå çíà÷åíèÿ íà âñåõ íàáîðàõ
(
α
1
, . . . , α
n
)
.
Ëåììà 2.3. Êîíúþíêöèÿ (ïðîèçâåäåíèå)
x
σ
1
1
Kx
σ
n
n
= 1
òîãäà è òîëüêî
òîãäà, êîãäà
(
x
1
, K, x
n
) = (
σ
1
, K, σ
n
)
.
Äîêàçàòåëüñòâî. Ïðîèçâåäåíèå (êîíúþíêöèÿ) ðàâíî 1 òîãäà è òîëüêî òî-
ãäà, êîãäà êàæäûé ñîìíîæèòåëü ðàâåí 1, íî
x
σ
= 1
òîãäà è òîëüêî òîãäà,
êîãäà
x
=
σ
.
 äàëüíåéøåì áóäåì óïîòðåáëÿòü ñëåäóþùèå îáîçíà÷åíèÿ:
k
^
i
=1
=
x
1
∧
x
2
∧
. . .
∧
x
k
=
x
1
x
2
. . . x
k
,
k
_
i
=1
=
x
1
∨
x
2
∨
. . .
∨
x
k
Ýòè çàïèñè èìåþò ñìûñë è ïðè
k
= 1
.
62
ÃËÀÂÀ 2. ÔÓÍÊÖÈÈ ÀËÃÅÁÐÛ ËÎÃÈÊÈ
Òåîðåìà 2.4 (Î ðàçëîæåíèè ôóíêöèè ïî íåñêîëüêèì ïåðåìåííûì). Ïóñòü
f
(
x
1
, . . . , x
n
)
ïðîèçâîëüíàÿ ôóíêöèÿ àëãåáðû ëîãèêè. Òîãäà åå ìîæíî
ïðåäñòàâèòü â ñëåäóþùåé ôîðìå:
f
(
x
1
, . . . , x
k
, x
k
+1
, . . . , x
n
) =
_
(
σ
1
, ..., σ
k
)
x
σ
1
1
. . . x
σ
k
k
·
f
(
σ
1
, . . . , σ
k
, x
k
+1
, . . . , x
n
)
(2
.
2)
Äîêàçàòåëüñòâî. Ðàññìîòðèì ïðîèçâîëüíûé íàáîð çíà÷åíèé ïåðåìåííûõ
(
α
1
, . . . , α
n
)
è ïîêàæåì, ÷òî ëåâàÿ è ïðàâàÿ ÷àñòè ñîîòíîøåíèÿ (2.2) ïðè-
íèìàþò íà íåì îäíî è òî æå çíà÷åíèå. Ëåâàÿ ÷àñòü äàåò
f
(
α
1
, . . . , α
k
, α
k
+1
,
. . . , α
n
)
. Ïðàâàÿ ÷àñòü äàåò
_
(
σ
1
, ..., σ
k
)
x
σ
1
1
Kx
σ
k
k
·
f
(
σ
1
, K, σ
k
, x
k
+1
, K, x
n
) =
=
α
σ
1
1
Kα
σ
k
k
·
f
(
α
1
, K, α
k
, α
k
+1
, K, α
n
) =
f
(
α
1
, K, α
n
)
.
Ïðåäñòàâëåíèå (2.2) íàçûâàåòñÿ äèçúþíêòèâíûì ðàçëîæåíèåì ôóíê-
öèè ïî
k
ïåðåìåííûì.
Ïðèìåð. Äëÿ
k
= 2
ðàçëîæåíèå â äèçúþíêòèâíóþ ôîðìó èìååò âèä:
f
(
x
1
, . . . , x
n
) = ¯
x
1
¯
x
2
·
f
(0
,
0
, x
3
, . . . , x
n
)
∨
∨
¯
x
1
x
2
·
f
(0
,
1
, x
3
, . . . , x
n
)
∨
∨
x
1
¯
x
2
·
f
(1
,
0
, x
3
, . . . , x
n
)
∨
∨
x
1
x
2
·
f
(1
,
1
, x
3
, . . . , x
n
)
.
Âûïèøåì òàêîå ðàçëîæåíèå äëÿ êîíêðåòíîé ôóíêöèè òðåõ ïåðåìåííûõ ïî
ïåðåìåííûì
x
2
è
x
3
:
(
x
1
→
x
2
)
≡
(
x
2
→
x
3
) = ¯
x
2
¯
x
3
·
((
x
1
→
0)
≡
(0
→
0))
∨
∨
¯
x
2
x
3
·
((
x
1
→
0)
≡
(0
→
1))
∨
∨
x
2
¯
x
3
·
((
x
1
→
1)
≡
(1
→
0))
∨
∨
x
2
x
3
·
((
x
1
→
1)
≡
(1
→
1))
.
 êà÷åñòâå ñëåäñòâèé ïîëó÷àåì äâà ñïåöèàëüíûõ ðàçëîæåíèÿ.
1. Ðàçëîæåíèå ïî îäíîé ïåðåìåííîé, âûïèñàííîå ðàíåå.
2. Ðàçëîæåíèå ïî âñåì
n
ïåðåìåííûì.
2.4. ÐÀÇËÎÆÅÍÈÅ ÔÓÍÊÖÈÉ ÀËÃÅÁÐÛ ËÎÃÈÊÈ ÏÎ ÏÅÐÅÌÅÍÍÛÌ63
Åñëè
k
=
n
, òî ïîëó÷àåì ðàçëîæåíèå
f
(
x
1
, . . . , x
n
) =
_
(
σ
1
, ..., σ
n
)
x
σ
1
1
. . . x
σ
n
n
·
f
(
σ
1
, . . . , σ
n
)
Îíî ìîæåò áûòü ïðåîáðàçîâàíî ïðè
f
(
x
1
, . . . , x
n
)
6
= 0
ñëåäóþùèì îáðà-
çîì:
_
(
σ
1
, ..., σ
n
)
x
σ
1
1
. . . x
σ
n
n
·
f
(
σ
1
, . . . , σ
n
) =
_
(
σ
1
,...,σ
n
)
f
(
σ
1
,...,σ
n
)=1
x
σ
1
1
. . . x
σ
n
n
Èòàê, â ýòîì ñëó÷àå ðàçëîæåíèå èìååò âèä:
f
(
x
1
, . . . , x
n
) =
_
(
σ
1
,...,σ
n
)
f
(
σ
1
,...,σ
n
)=1
x
σ
1
1
. . . x
σ
n
n
Ýòî ðàçëîæåíèå íàçûâàåòñÿ ñîâåðøåííîé äèçúþíêòèâíîé íîðìàëüíîé ôîð-
ìîé (ñîâåðøåííàÿ ÄÍÔ.). Îíî îïðåäåëåíî äëÿ ëþáîé ôóíêöèè
f
, íå ðàâíîé
êîíñòàíòå 0.
Òåîðåìà 2.5. Ïðîèçâîëüíóþ ôóíêöèþ àëãåáðû ëîãèêè ìîæíî âûðàçèòü
ôîðìóëîé ïðè ïîìîùè îïåðàöèé
∧
,
∨
,
e
, ïðè÷åì îïåðàöèÿ
e
ïðèìåíÿåòñÿ
òîëüêî ê ïåðåìåííûì.
Äîêàçàòåëüñòâî.
1. Ïóñòü
f
(
x
1
, . . . , x
n
) = 0
. Òîãäà, î÷åâèäíî,
f
(
x
1
, . . . , x
n
) =
x
1
∧e
x
1
2. Ïóñòü
f
(
x
1
, . . . , x
n
)
6
= 0
. Ïðåäñòàâèì åå â ôîðìå ñîâåðøåííîé ÄÍÔ:
f
(
x
1
, . . . , x
n
) =
_
(
σ
1
,...,σ
n
)
f
(
σ
1
,...,σ
n
)=1
x
σ
1
1
. . . x
σ
n
n
Òàêèì îáðàçîì, â îáîèõ ñëó÷àÿõ ôóíêöèÿ
f
âûðàæàåòñÿ â âèäå ôîðìó-
ëû ÷åðåç êîíúþíêöèþ, äèçúþíêöèþ è îòðèöàíèå, ïðè÷åì îòðèöàíèå ïðè-
ìåíÿåòñÿ òîëüêî ê ñèìâîëàì ïåðåìåííûõ.
Èòàê, îêàçàëîñü, ÷òî ëþáóþ áóëåâó ôóíêöèþ ìîæíî âûðàçèòü ôîðìó-
ëîé íàä ìíîæåñòâîì îïåðàöèé
{∨
,
∧
,
e}
, ñîñòîÿùèì èç òðåõ ôóíêöèé: îòðè-
öàíèÿ, êîíúþíêöèè è äèçúþíêöèè. Äàííàÿ òåîðåìà íîñèò êîíñòðóêòèâíûé
64
ÃËÀÂÀ 2. ÔÓÍÊÖÈÈ ÀËÃÅÁÐÛ ËÎÃÈÊÈ
õàðàêòåð, òàê êàê îíà ïîçâîëÿåò äëÿ êàæäîé ôóíêöèè ïîñòðîèòü ðåàëè-
çóþùóþ åå ôîðìóëó (ñîâåðøåííóþ ÄÍÔ). À èìåííî, áåðåì òàáëèöó äëÿ
ôóíêöèè
f
(
x
1
, . . . , x
n
) (
f
6
= 0)
è îòìå÷àåì â íåé âñå ñòðîêè
(
σ
1
, . . . , σ
n
)
, â
êîòîðûõ
f
(
σ
1
, . . . , σ
n
) = 1
, äëÿ êàæäîé òàêîé ñòðîêè îáðàçóåì ëîãè÷åñêîå
ïðîèçâåäåíèå
x
σ
1
1
∧
. . .
∧
x
σ
n
n
, à çàòåì ñîåäèíÿåì âñå ïîëó÷åííûå êîíúþíêöèè
çíàêîì äèçúþíêöèè.
Ïðèìåð Ïîñòðîèòü ñîâåðøåííóþ ÄÍÔ äëÿ ôóíêöèè, çàäàííîé òàáëè-
öåé:
x
1
x
2
x
3
f
(
x
1
, x
2
, x
3
)
x
1
x
2
x
3
f
(
x
1
, x
2
, x
3
)
0
0
0
1
1
0
0
0
0
0
1
1
1
0
1
1
0
1
0
0
1
1
0
0
0
1
1
0
1
1
1
1
Èìååì:
f
(
x
1
, x
2
, x
3
) = ¯
x
1
¯
x
2
¯
x
3
∨
¯
x
1
¯
x
2
x
3
∨
x
1
¯
x
2
x
3
∨
x
1
x
2
x
3
Åñëè â òàáëèöå çíà÷åíèé ôóíêöèè ìíîãî 1 è ìàëî 0, òî öåëåñîîáðàçíî
ñòðîèòü ôóíêöèþ ïî-äðóãîìó. Ñîâåðøåííàÿ ÄÍÔ åñòü âûðàæåíèå òèïà
¾
∨
&¿, òî åñòü ëîãè÷åñêàÿ ñóììà ïðîèçâåäåíèé
x
σ
i
i
. Ñïðàøèâàåòñÿ íåëüçÿ
ëè äëÿ ôóíêöèè àëãåáðû ëîãèêè ïîëó÷èòü ðàçëîæåíèå òèïà ¾&,
∨
¿?
Àíàëîãè÷íî òîëüêî ÷òî ïðîâåäåííûì äîêàçàòåëüñòâàì ëåãêî ïîëó÷èòü,
÷òî:
•
x
¯
σ
= 0
òîãäà è òîëüêî òîãäà, êîãäà
x
=
σ
;
•
x
¯
σ
1
1
∨
. . .
∨
x
¯
σ
n
n
îáðàùàåòñÿ â 0 òîëüêî íà íàáîðå
(
x
1
, . . . , x
n
) =
(
σ
1
, . . . , σ
n
);
•
èìååò ìåñòî ñëåäóþùåå ðàçëîæåíèå â êîíúþíêòèâíóþ íîðìàëüíóþ
ôîðìó ïî îäíîé ïåðåìåííîé
f
(
x
1
, . . . , x
n
) = (
x
1
∨
f
(0
, x
2
, . . . , x
n
))
·
·
(¯
x
1
∨
f
(1
, x
2
, . . . , x
n
))
•
èìååò ìåñòî ñëåäóþùåå ïðåäñòàâëåíèå ôóíêöèè â âèäå ñîâåðøåííîé
êîíúþíêòèâíîé íîðìàëüíîé ôîðìû (ñîâåðøåííàÿ ÊÍÔ) äëÿ
f
6
= 1
:
f
(
x
1
, K, x
n
) =
^
(
σ
1
, ..., σ
n
)
f
(
σ
1
, ..., σ
n
)=0
x
¯
σ
1
1
∨
x
¯
σ
2
2
∨
K
∨
x
¯
σ
n
n
Èñïîëüçîâàíèå ñîâåðøåííîé ÊÍÔ ïîçâîëÿåò óïðîñòèòü çàïèñü ôîðìóëû
äëÿ ôóíêöèè, òàáëèöà çíà÷åíèé êîòîðîé ñîäåðæèò ìàëî íóëåé.
2.5. ÔÓÍÊÖÈÎÍÀËÜÍÀß ÏÎËÍÎÒÀ ÑÈÑÒÅÌ ÔÓÍÊÖÈÉ
65
Êðîìå îòìå÷åííûõ êîíúþíêòèâíîãî è äèçúþíêòèâíîãî ðàçëîæåíèé ôóíê-
öèè ïî ïåðåìåííîé ÷àñòî èñïîëüçóåòñÿ è ðàçëîæåíèå, îñíîâàííîå íà îïå-
ðàöèè ëîãè÷åñêîé ñóììû:
f
(
x
1
, x
2
, . . . , x
n
) =
x
1
·
f
(1
, x
2
, . . . , x
n
) + ¯
x
1
·
f
(0
, x
2
, . . . , x
n
)
Ïîñëåäîâàòåëüíîå ïðèìåíåíèå òàêîãî ðàçëîæåíèÿ êî âñåì ïåðåìåííûì ïîç-
âîëÿåò âûðàçèòü ïðîèçâîëüíóþ ôóíêöèþ àëãåáðû ëîãèêè ÷åðåç ýëåìåíòàð-
íûå ôóíêöèè
¯
x
,
x
+
y
,
x
∧
y
èëè, èñïîëüçóÿ ñîîòíîøåíèå
¯
x
=
x
+ 1
, ëèøü
÷åðåç ôóíêöèè
x
+
y
,
x
∧
y
, 1.
2.5 Ôóíêöèîíàëüíàÿ ïîëíîòà ñèñòåì ôóíêöèé
àëãåáðû ëîãèêè
Âûøå ìû âèäåëè, ÷òî âñÿêàÿ ôóíêöèÿ àëãåáðû ëîãèêè ìîæåò áûòü âû-
ðàæåíà â âèäå ôîðìóëû ÷åðåç ýëåìåíòàðíûå ôóíêöèè
¯
x
,
x
∧
y
,
x
∨
y
. Â
ñâÿçè ñ ýòèì âîçíèêàåò âîïðîñ, êàêèìè ñâîéñòâàìè äîëæíà îáëàäàòü ñè-
ñòåìà ôóíêöèé, ÷òîáû ÷åðåç ôóíêöèè ýòîé ñèñòåìû ìîæíî áûëî âûðàçèòü
ïðîèçâîëüíóþ ôóíêöèþ àëãåáðû ëîãèêè? Ìû ñîáèðàåìñÿ äàòü äîñòàòî÷-
íî èñ÷åðïûâàþùèé îòâåò íà ýòîò âîïðîñ è ïîêàçàòü, ÷òî òàêèì ñâîéñòâîì
îáëàäàþò è äðóãèå ñèñòåìû ôóíêöèé.
Ïðåæäå âñåãî óòî÷íèì, êàêèìè ñðåäñòâàìè èç èìåþùåéñÿ ñèñòåìû ôóíê-
öèé ìîæíî ïîëó÷àòü íîâûå ôóíêöèè. Íîâûå ôóíêöèè ïîëó÷àþòñÿ èç èìå-
þùèõñÿ â çàäàííîé ñèñòåìå ôóíêöèé ñ ïîìîùüþ îïåðàöèé çàìåíû ïåðå-
ìåííûõ è ñóïåðïîçèöèè. Îïèøåì ýòè äâå îïåðàöèè.
1. Çàìåíà ïåðåìåííûõ.
Ïóñòü
f
(
x
1
, x
2
, . . . , x
n
)
çàäàííàÿ ôóíêöèÿ àëãåáðû ëîãèêè. Áóäåì
ãîâîðèòü, ÷òî ôóíêöèÿ
ϕ
(
y
1
, y
2
, . . . , y
n
)
ïîëó÷åíà îïåðàöèåé çàìå-
íû ïåðåìåííûõ èç ôóíêöèè
f
(
x
1
, x
2
, . . . , x
n
)
, åñëè îñóùåñòâëåíà
ïîäñòàíîâêà ïåðåìåííûõ
s
=
x
1
. . .
x
n
y
1
. . .
y
n
,
òî åñòü âìåñòî êàæäîãî âõîæäåíèÿ ïåðåìåíîé
x
1
ïîäñòàâëÿåòñÿ ïå-
ðåìåííàÿ
y
1
, âìåñòî êàæäîãî âõîæäåíèÿ ïåðåìåíîé
x
2
ïîäñòàâëÿåòñÿ
ïåðåìåííàÿ
y
2
, . . . ,
âìåñòî êàæäîãî âõîæäåíèÿ ïåðåìåíîé
x
n
ïîä-
ñòàâëÿåòñÿ ïåðåìåííàÿ
y
n
, ïðè ýòîì
y
i
íå îáÿçàíà îòëè÷àòüñÿ îò
y
k