Таран Т.А. Основы дискретной математики

Подождите немного. Документ загружается.

140 141Ãëàâà 8 Ãðàôû

Äåéñòâèòåëüíî, â àöèêëè÷åñêîì ãðàôå ëþáîé ïóòü ïðèâîäèò â

âåðøèíó, èç êîòîðîé îí íå ìîæåò ïðîäîëæèòüñÿ (ñì. ðèñ. 8.23).

Òàêàÿ âåðøèíà è åñòü ñòîê. Åñëè æå ïðîäîëæèòü ýòîò ïóòü îò åãî

íà÷àëà ïðîòèâ îðèåíòàöèè, ïðèäåì â âåðøèíó, èç êîòîðîé íåëüçÿ

âûéòè ïðîòèâ îðèåíòàöèè èíöèäåíòíûõ åé ðåáåð, ò.å.â âåðøèíó,

íå èìåþùóþ âõîäÿùèõ ðåáåð. Òàêàÿ âåðøèíà ÿâëÿåòñÿ èñòî÷íèêîì.

Ðèñ. 8.23. Àöèêëè÷åñêèå ãðàôû.

Ïðèìåðû.

Àöèêëè÷åñêèé îðãðàô ñ îäíèì èñòî÷íèêîì è îäíèì ñòîêîì íàçûâà-

åòñÿ äâóõïîëþñíûì. Äâóõïîëþñíûé ãðàô èçîáðàæåí íà ðèñ.8.23,à.

Àöèêëè÷åñêèé ãðàô íà ðèñ. 8.23, á èìååò òðè èñòîêà è îäèí ñòîê.

Ãðàô êîíäåíñàöèè íåêîòîðîãî îðãðàôà ÿâëÿåòñÿ àöèêëè÷åñêèì

ãðàôîì, òàê êàê îí íèêîãäà íå ñîäåðæèò öèêëîâ. Äðóãèì ïðèìåðîì

àöèêëè÷åñêîãî ãðàôà ÿâëÿåòñÿ ïðåäñòàâëåíèå ïîëóðåøåòîê â âèäå

äèàãðàìì Õàññå. Äèàãðàììà ïîëíîé ðåøåòêè ïðåäñòàâëÿåò ñîáîé

äâóõïîëþñíûé àöèêëè÷åñêèé îðãðàô.

Îïðåäåëåíèå 8.24. Òîïîëîãè÷åñêîé ñîðòèðîâêîé îðãðàôà

íàçûâàåòñÿ òàêàÿ íóìåðàöèÿ âåðøèí, ÷òî äëÿ ëþáîé äóãè (v

,v

)

íîìåð åå íà÷àëà ìåíüøå íîìåðà åå êîíöà: i<j.

Òåîðåìà 8.18. Äëÿ îðãðàôà òîïîëîãè÷åñêàÿ ñîðòèðîâêà

ñóùåñòâóåò òîãäà è òîëüêî òîãäà, êîãäà îí àöèêëè÷åñêèé.

Äîêàçàòåëüñòâî. Ïðåäïîëîæèì, ÷òî äëÿ öèêëà òîïîëîãè÷åñêàÿ

ñîðòèðîâêà âîçìîæíà. Âûáåðåì â öèêëå ïðîèçâîëüíóþ âåðøèíó

. Öèêë ñîäåðæèò ðåáðà (v

, v

) è (v

, v

), ïðè÷åì ïî îïðåäåëå-

íèþ8.24äîëæíî áûòü i<j è k<i. Ïðè ïðîõîæäåíèè âäîëü öèêëà

íîìåðà âåðøèí äîëæíû òîëüêî âîçðàñòàòü è, çíà÷èò, âñå îíè áóäóò

áîëüøå i. Ïîýòîìó, êîãäà ìû ïðèäåì â v

, ïîëó÷èì k>i, ÷òî

ïðîòèâîðå÷èò ïðåäïîëîæåíèþ.

Äëÿ àöèêëè÷åñêîãî îðãðàôà D ñ n âåðøèíàìè òîïîëîãè÷åñêàÿ ñîð-

òèðîâêà îñóùåñòâëÿåòñÿ ñ ïîìîùüþ ñëåäóþùåãî àëãîðèòìà. Âûáå-

ðåì â D êàêîé-ëèáî ñòîê è ïðèñâîèì åìó íîìåð n. Âñå èíöèäåíòíûå

åìó ðåáðà  âõîäÿùèå, ïîýòîìó èõ íà÷àëà áóäóò èìåòü íîìåðà, ìåíüøèå

n, è, ñëåäîâàòåëüíî, äëÿ íèõ óñëîâèå îïðåäåëåíèÿ8.24âûïîëíåíî.

Óäàëèì âûáðàííûé ñòîê âìåñòå ñî âñåìè èíöèäåíòíûìè åìó äóãàìè.

Ïîëó÷èì àöèêëè÷åñêèé ãðàô ñ n1âåðøèíîé. Âûáåðåì â íåì êàêîé-

ëèáî ñòîê è ïðèñâîèì åìó íîìåð n1. Áóäåì ïîâòîðÿòü ïðîöåäóðó

óäàëåíèÿ ñòîêîâ è èíöèäåíòíûõ èì äóã äî òåõ ïîð, ïîêà íå ïðîíó-

ìåðóåì âñå âåðøèíû. Ïîñêîëüêó âñÿêèé ðàç óäàëÿåìûå äóãè áóäóò

óäîâëåòâîðÿòü óñëîâèþ îïðåäåëåíèÿ 8.24, ïîëó÷èì òîïîëîãè÷åñêóþ

ñîðòèðîâêó èñõîäíîãî îðãðàôà. Ïðèìåð òîïîëîãè÷åñêîé ñîðòèðîâêè

ãðàôà ïðèâåäåí íà ðèñ. 8.23.

8.10. Äåðåâüÿ

Åñëè â àöèêëè÷åñêîì îðãðàôå «îòìåíèòü» îðèåíòàöèþ ðåáåð,

òî â ïîëó÷åííîì íåîðèåíòèðîâàííîì ãðàôå ìîãóò âîçíèêíóòü

öèêëû. Ïîýòîìó íåîðèåíòèðîâàííûé àöèêëè÷åñêèé ãðàô èìååò

áîëåå ñïåöèôè÷åñêèé âèä.

Îïðåäåëåíèå 8.25. Ñâÿçíûé íåîðèåíòèðîâàííûé ãðàô áåç

öèêëîâ íàçûâàåòñÿ íåîðèåíòèðîâàííûì äåðåâîì. Íåñâÿçíûé

ãðàô, ñîñòîÿùèé èç íåñêîëüêèõ äåðåâüåâ, íàçûâàåòñÿ ëåñîì.

Òàêîå äåðåâî ÿâëÿåòñÿ íåîðèåíòèðîâàííûì àöèêëè÷åñêèì ãðà-

ôîì, ïîýòîìó â íåì âñå ïóòè  ïðîñòûå.

Ïîíÿòèå îðèåíòèðîâàííîãî äåðåâà îòëè÷àåòñÿ îò àöèêëè÷åñêîãî

ãðàôà.

Îïðåäåëåíèå 8.26. Íå ñîäåðæàùèé öèêëîâ ñâÿçíûé îðãðàô, â

êîòîðîì òîëüêî îäíà âåðøèíà íå èìååò âõîäÿùèõ äóã, à âñå

îñòàëüíûå âåðøèíû èìåþò ïî îäíîé âõîäÿùåé äóãå, íàçûâàåòñÿ

îðèåíòèðîâàííûì, èëè íàïðàâëåííûì äåðåâîì.

Îïðåäåëåíèå 8.27. Âåðøèíà, íå èìåþùàÿ âõîäÿùèõ äóã,

íàçûâàåòñÿ êîðíåì äåðåâà. Âåðøèíû, íå èìåþùèå âûõîäÿùèõ

äóã, íàçûâàþòñÿ êîíöåâûìè, èëè òåðìèíàëüíûìè, èëè ëèñòüÿìè.

Ïðîìåæóòî÷íûå âåðøèíû, ëåæàùèå ìåæäó êîðíåì è ëèñòüÿìè,

íàçûâàþòñÿ òðàíçèòíûìè.

Îðèåíòèðîâàííûå äåðåâüÿ ÷àñ-

òî èçîáðàæàþò áåç ñòðåëîê, ïðåä-

âàðèòåëüíî îãîâîðèâ, ÷òî ýòî ðàñ-

òóùåå âíèç (èëè ââåðõ) äåðåâî. Íà

ðèñ.8.24,a èçîáðàæåíî ðàñòóùåå

âíèç äåðåâî, íà ðèñ.8.24,á íåîðè-

åíòèðîâàííîå äåðåâî.

Ñëåäóþùàÿ òåîðåìà îïèñûâàåò

îñíîâíûå ñâîéñòâà äåðåâüåâ.

Ðèñ. 8.24. Ïðèìåðû äåðåâüåâ.

142 143Ãëàâà 8 Ãðàôû

Òåîðåìà 8.19.

1.Â ëþáîì äåðåâå èìåþòñÿ, ïî êðàéíåé ìåðå, äâå êîíöåâûå âåð-

øèíû (âåðøèíû ñòåïåíè 1).

2.Ìåæäó ëþáûìè äâóìÿ âåðøèíàìè äåðåâà èìååòñÿ ðîâíî îäèí

ïóòü.

3.×èñëî ðåáåð â äåðåâå ñ n âåðøèíàìè ðàâíî n1.

Äîêàçàòåëüñòâî. 1). Ïîñêîëüêó â äåðåâå âñå ïóòè  ïðîñòûå, òî

â íåì åñòü ïî êðàéíåé ìåðå îäèí ìàêñèìàëüíûé ïóòü, ò.å.ïóòü,

êîòîðûé íåëüçÿ ïðîäîëæèòü. Êîíöû ýòîãî ïóòè è ÿâëÿþòñÿ êîíöå-

âûìè âåðøèíàìè. (Çàìåòèì, ÷òî â ïðîèçâîëüíîì àöèêëè÷åñêîì

îðãðàôå òîæå åñòü ìàêñèìàëüíûå ïóòè; èõ êîíöàìè ÿâëÿþòñÿ ñòîêè.

Îäíàêî ñòîê ìîæåò èìåòü ñòåïåíü, áîëüøóþ åäèíèöû. Â ýòîì ñëó÷àå

ïðîäîëæèòü èç íåãî ïóòü íåëüçÿ íå ïîòîìó, ÷òî íåò äðóãîãî èíöè-

äåíòíîãî åìó ðåáðà, à ïîòîìó, ÷òî äðóãèå ðåáðà òîæå âõîäÿùèå, è

âûéòè ïî íèì èç ñòîêà íåëüçÿ.)

2).Íàëè÷èå ïóòè ìåæäó ëþáîé ïàðîé âåðøèí ñëåäóåò èç ñâÿç-

íîñòè äåðåâà, à åäèíñòâåííîñòü ýòîãî ïóòè  èç òîãî, ÷òî

ñóùåñòâîâàíèå äâóõ ïóòåé ìåæäó ïàðîé âåðøèí âñåãäà ñîçäàåò öèêë.

3). Òðåòèé ïóíêò òåîðåìû ïðîùå âñåãî äîêàçàòü, ââåäÿ ïðîöåäóðó

ïðåîáðàçîâàíèÿ íåîðèåíòèðîâàííîãî äåðåâà â îðèåíòèðîâàííîå.

Âûáåðåì â äåðåâå ïðîèçâîëüíóþ âåðøèíó. Íàçîâåì åå êîðíåì. Ðåáðà,

èíöèäåíòíûå êîðíþ, îðèåíòèðóåì â íàïðàâëåíèè îò êîðíÿ. Äëÿ

êàæäîé âåðøèíû v

, ÿâëÿþùåéñÿ êîíöîì îäíîãî èç ýòèõ ðåáåð,

îðèåíòèðóåì îñòàëüíûå èíöèäåíòíûå åé ðåáðà â íàïðàâëåíèè îò

. Ïðîäîëæàåì ýòó ïðîöåäóðó äî òåõ ïîð, ïîêà íå áóäóò äîñòèãíóòû

êîíöåâûå âåðøèíû. Â ñèëó åäèíñòâåííîñòè ïóòè ìåæäó âåðøèíàìè

íè îäíà âåðøèíà íå áóäåò äîñòèãíóòà äâàæäû (ò.å.íå ïðèäåòñÿ

îðèåíòèðîâàòü óæå îðèåíòèðîâàííûå ðåáðà), à â ñèëó ñâÿçíîñòè

äåðåâà âñå âåðøèíû áóäóò äîñòèãíóòû. Èç ýòîé ïðîöåäóðû âèäíî,

÷òî êîðåíü íå èìååò âõîäÿùèõ ðåáåð (åãî ïîëóñòåïåíü çàõîäà ðàâ-

íà0), à êàæäàÿ èç îñòàëüíûõ n1âåðøèí èìååò îäíî âõîäÿùåå

ðåáðî. Ïîñêîëüêó âñå ðåáðà ÿâëÿþòñÿ âõîäÿùèìè äëÿ êàêîéòî

âåðøèíû, òî îòñþäà è ñëåäóåò ï.3òåîðåìû.

Èç îäíîãî íåîðèåíòèðîâàííîãî äåðåâà ñ n âåðøèíàìè ìîæíî

ïîëó÷èòü ðîâíî n ðàçëè÷íûõ îðèåíòèðîâàííûõ äåðåâüåâ, òàê êàê

âûáîð ðàçíûõ êîðíåé âñåãäà äàåò ðàçíûå îðäåðåâüÿ. Ýòî ñëåäóåò

èç òîãî, ÷òî èç êîðíÿ äîñòèæèìû âñå îñòàëüíûå âåðøèíû, ñàì æå

êîðåíü íåäîñòèæèì íè èç êàêîé äðóãîé âåðøèíû. Äðóãèìè ñëîâàìè,

îðèåíòèðîâàííîå äåðåâî âñåãäà îäíîñòîðîííå ñâÿçíî. Îäíàêî

ðàçëè÷íûå îðäåðåâüÿ, ïîëó÷åííûå èç îäíîãî è òîãî æå äåðåâà, ìîãóò

îêàçàòüñÿ èçîìîðôíûìè.

Ïðèìåð. Åñëè èñõîäíîå äåðåâî  ïðîñòàÿ öåïü, òî âûáîð â êà÷å-

ñòâå êîðíÿ êîíöîâ ýòîé öåïè äàñò äâå èçîìîðôíûå îðèåíòèðîâàííûå

öåïè, à åñëè ýòà öåïü ñîäåðæèò ÷åòíîå ÷èñëî âåðøèí è, ñëåäîâà-

òåëüíî, äâà öåíòðà, òî âûáîð ýòèõ öåíòðîâ äàñò äâà èçîìîðôíûõ

îðäåðåâà ñ äâóìÿ ïóòÿìè, âåäóùèìè èç êîðíÿ.

Îïðåäåëåíèå 8.28. Äåðåâî, â êîòîðîì êàæäàÿ âåðøèíà èìååò

ïî äâå èñõîäÿùèõ äóãè èëè íå èìååò âîâñå, íàçûâàåòñÿ äâîè÷íûì,

èëè áèíàðíûì äåðåâîì.

Îïðåäåëåíèå 8.29. Ïóñòü n  êîëè÷åñòâî êîíöåâûõ âåðøèí â

äâîè÷íîì äåðåâå, d  äëèíà ïóòè îò êîðíÿ äåðåâà ê êîíöåâîé

âåðøèíå è m  öåëîå ïîëîæèòåëüíîå ÷èñëî, òîãäà äåðåâî

íàçûâàåòñÿ ñáàëàíñèðîâàííûì, åñëè:

1) ëèáî n = 2

è òîãäà d = m,

2) ëèáî 2

< n < 2

m+1

, è òîãäà d = m èëè d = m+1.

Íà ðèñ. 8.25, a, á äåðåâüÿ ñáàëàíñèðîâàííûå, â  íåñáàëàíñè-

ðîâàííîå äåðåâî.

Ðèñ. 8.25. Ïðèìåðû äåðåâüåâ.

Äåðåâüÿ îòîáðàæàþò èåðàðõè÷åñêèå ñòðóêòóðû, íàïðèìåð, ñ ïî-

ìîùüþ äåðåâà ìîæíî ïðåäñòàâèòü èåðàðõèþ ñëóæåáíûõ ïîëîæåíèé

â íåêîòîðîé îðãàíèçàöèè, èåðàðõèþ ïîíÿòèé íåêîòîðîé ïðåäìåòíîé

îáëàñòè, ðîäñòâåííûå îòíîøåíèÿ (ãåíåàëîãè÷åñêîå äåðåâî) èò.ï.

Áèíàðíûå îðèåíòèðîâàííûå äåðåâüÿ èìåþò áîëüøîå çíà÷åíèå

â ïðîãðàììèðîâàíèè äëÿ ïðåäñòàâëåíèÿ ñëîæíûõ ñòðóêòóð äàííûõ

è ïîñòðîåíèÿ àëãîðèòìîâ èõ îáðàáîòêè. Óäîáíûì ñïîñîáîì ïðåä-

ñòàâëåíèÿ àðèôìåòè÷åñêîãî âûðàæåíèÿ ÿâëÿåòñÿ ïîëüñêàÿ îáðàòíàÿ

çàïèñü, ãäå îïåðàöèè ïðåäøåñòâóþò îïåðàíäàì, â îòëè÷èå îò îáû÷íî

èñïîëüçóåìîé ôóíêöèîíàëüíîé çàïèñè. Íàïðèìåð, ôóíêöèÿ

f(x,y)= x+y â îáðàòíîé çàïèñè èìååò âèä: +(x,y) èëè ïðîñòî

+xy. Íà ðèñ.8.26ïîêàçàíî äåðåâî àðèôìåòè÷åñêîãî âûðàæåíèÿ

144 145Ãëàâà 8 Ãðàôû

(a+b)×(ab). Äëÿ ïðåîáðàçîâàíèÿ åãî â ïîëüñêóþ îáðàòíóþ

çàïèñü ×+abab èñïîëüçóåòñÿ àëãîðèòì îáõîäà äåðåâà ñâåðõó âíèç

è ñëåâà íàïðàâî, êîòîðûé ïîêàçàí íà ðèñ.8.26.

Ñíà÷àëà âûáèðàåòñÿ çíà÷åíèå, õðàíÿùååñÿ

â êîðíå äåðåâà (îíî çàãðóæàåòñÿ â ñòåê). Çàòåì

ïðîèñõîäèò ñïóñê ïî ëåâîé âåòâè äî òåðìèíàëü-

íîé âåðøèíû. Âñå çíà÷åíèÿ, ëåæàùèå íà ýòîì

ïóòè, çàïèñûâàþòñÿ ïîñëå êîðíåâîãî: ×+a. Äîé-

äÿ äî òåðìèíàëüíîé âåðøèíû, ìû ïîäíèìàåìñÿ

äî ïåðâîé ñíèçó òðàíçèòíîé âåðøèíû, è ñïóñêà-

åìñÿ ïî ïðàâîìó ïîääåðåâó; ïîëó÷àåì ×+ab. Ïî-

ñëåäîâàòåëüíî ïîâòîðÿÿ ýòîò ïðîöåññ, ìû äîé-

äåì îïÿòü äî êîðíÿ äåðåâà, ïîñëå ÷åãî ñïóñêàåì-

ñÿ ïî ïðàâîìó ïîääåðåâó ïî òîìó æå àëãîðèòìó.

Â ðåçóëüòàòå ïîëó÷àåì âûðàæåíèå: ×+abab.

8.11. Ïëàíàðíûå ãðàôû

Îïðåäåëåíèå 8.30. Ãðàô íàçûâàåòñÿ ïëàíàðíûì, åñëè îí ìîæåò

áûòü íàðèñîâàí íà ïëîñêîñòè òàê, ÷òî åãî ðåáðà ïåðåñåêàþòñÿ

òîëüêî â âåðøèíàõ ãðàôà. Ãðàô íàçûâàåòñÿ ïëîñêèì, åñëè îí

óæå óëîæåí íà ïëîñêîñòè òàê, ÷òî íèêàêèå åãî äâà ðåáðà íå

ïåðåñåêàþòñÿ â òî÷êàõ, îòëè÷íûõ îò âåðøèí ãðàôà.

Íà ðèñ. 8.27, a ïîêàçàí ïëàíàðíûé ãðàô, èçîáðàæåííûé òàê,

÷òî åãî ðåáðà ïåðåñåêàþòñÿ, à íà ðèñ. 8.27, á  òîò æå ãðàô áåç

ïåðåñå÷åíèé ðåáåð, ò.å.ïëîñêèé ãðàô.

Ðèñ. 8.27. Ïëîñêèé ãðàô.

Ðàññìîòðèì óñëîâèÿ, ïðè êîòîðûõ ãðàô ÿâëÿåòñÿ ïëîñêèì.

Îïðåäåëåíèå 8.31. ×àñòü ïëîñêîãî ãðàôà, êîòîðàÿ îãðàíè÷åíà

öèêëîì è íå âêëþ÷àåò â ñåáÿ íèêàêîé äðóãîé öèêë, íàçûâàåòñÿ

ãðàíüþ. Íåîãðàíè÷åííàÿ áåñêîíå÷íàÿ îáëàñòü, âíåøíÿÿ ïî îòíî-

øåíèþ ê êîíå÷íûì ãðàíÿì, òàêæå ñ÷èòàåòñÿ ãðàíüþ.

Ãðàíè ïëîñêîãî ãðàôà îáðàçóþò ðàçáèåíèå ïëîñêîñòè, íà êîòîðîé

îí èçîáðàæåí. Íà ðèñ. 8.27, á â ãðàôå G z

 áåñêîíå÷íàÿ ãðàíü, z

, z

 êîíå÷íûå. Åñëè ãðàô íåïëàíàðåí, òî îí íå ìîæåò áûòü èçîáðàæåí

â âèäå ïëîñêîãî ãðàôà, è ïîíÿòèå ãðàíè äëÿ íåãî òåðÿåò ñìûñë.

Òåîðåìà 8.20 (Ýéëåðà). Ïëîñêîå ïðåäñòàâëåíèå ñâÿçíîãî ïëà-

íàðíîãî ãðàôà (ìóëüòèãðàôà) ñ n âåðøèíàìè, m ðåáðàìè è r

ãðàíÿìè óäîâëåòâîðÿåò ñëåäóþùåé ôîðìóëå:

n  m + r = 2.

Äîêàçàòåëüñòâî. Äîêàæåì òåîðåìó èíäóêöèåé ïî ÷èñëó ãðàíåé.

Åñëè åäèíñòâåííîé ãðàíüþ ãðàôà G ÿâëÿåòñÿ âíåøíÿÿ ãðàíü, òî

ãðàô íå èìååò öèêëîâ, ñëåäîâàòåëüíî, ýòî äåðåâî, òàê êàê G ñâÿçåí.

Òîãäà m=n  1è r=1, ñëåäîâàòåëüíî, n  m + r = 2.

Ïðåäïîëîæèì, ÷òî G èìååò ïî êðàéíåé ìåðå äâå ãðàíè è (x, y) ðåáðî,

ëåæàùåå íà ãðàíèöå ýòèõ ãðàíåé. Ïðè óäàëåíèè ðåáðà (áåç óäàëåíèÿ

âåðøèí x, y) ãðàô îñòàåòñÿ ñâÿçíûì, íî ÷èñëî åãî ðåáåð òåïåðü

ðàâíîm 1, à ÷èñëî ãðàíåé  r  1, òàê êàê äâå ãðàíè òåïåðü ñëèâàþòñÿ

â îäíó. Òîãäà n  (m1) + (r 1) = n  m + r = 2. Ïðîäîëæàÿ ýòîò

ïðîöåññ, ïî ïðèíöèïó ìàòåìàòè÷åñêîé èíäóêöèè, ïîëó÷èì, ÷òî ôîðìóëà

îñòàåòñÿ ñïðàâåäëèâîé äëÿ ëþáîãî ñâÿçíîãî ïëàíàðíîãî ãðàôà.

Òåîðåìà 8.21. Â ïðîñòîì ïëàíàðíîì ãðàôå ñ n âåðøèíàìè, m

ðåáðàìè è r ãðàíÿìè 3r≤2m.

Äîêàçàòåëüñòâî îñíîâûâàåòñÿ íà òîì ôàêòå, ÷òî êàæäàÿ ãðàíü

èìååò ïî êðàéíåé ìåðå òðè îãðàíè÷èâàþùèõ åå ðåáðà, è êàæäîå

ðåáðî íàõîäèòñÿ íà ãðàíèöå ïî êðàéíåé ìåðå äâóõ ãðàíåé.

Ñëåäóþùàÿ òåîðåìà óñòàíàâëèâàåò òàê íàçûâàåìîå íåðàâåíñòâî

Ýéëåðà.

Òåîðåìà 8.22. Â ïðîñòîì ïëàíàðíîì ãðàôå ñ n âåðøèíàìè, m

ðåáðàìè è r ãðàíÿìè

m≤3n 6.

Äîêàçàòåëüñòâî. Èç ôîðìóëû n  m + r = 2ïîëó÷àåì: r = 2 + m  n.

Ïîäñòàâëÿÿ çíà÷åíèå r â íåðàâåíñòâî 3r≤2m, ïîëó÷èì: 6 + 3m  3n ≤2m,

ò.å.m≤3n 6.

Òåîðåìà 8.22äàåò íåîáõîäèìîå óñëîâèå ïëàíàðíîñòè ãðàôà.

Íà ðèñ. 8.28èçîáðàæåíû äâà íåïëîñêèõ ãðàôà, êîòîðûå èìåþò

íàèìåíüøåå ÷èñëî âåðøèí è íå ÿâëÿþòñÿ ïëàíàðíûìè. Äîêàæåì ýòî.

Ãðàô Ê

 ýòî ïðîñòîé ïîëíûé

ãðàô, ïðåäñòàâëÿþùèé ñîáîé

çâåçäó, âïèñàííóþ â ïÿòèóãîëü-

íèê. Îí

èìååò 5âåðøèí è

10ðåáåð, ò.å.3n 6 = 9, ïîýòîìó

íåðàâåíñòâî Ýéëåðà 10≤3n6

íåâûïîëíåíî. Ïî òåîðåìå 8.22,

ãðàô K

5

íåïëàíàðåí.

Ðèñ.8.26.

Îáõîä äåðåâà.

Ðèñ. 8.28. Íåïëîñêèå ãðàôû.

146 147Ãëàâà 8 Ãðàôû

Î÷åâèäíî, ÷òî ëþáîé ãðàô, ñîäåðæàùèé â êà÷åñòâå ïîäãðàôà

ãðàô Ê

, îáÿçàòåëüíî áóäåò íåïëîñêèì.

Äðóãîé ãðàô, êîòîðûé íå ñîäåðæèò ãðàôà Ê

5

è ÿâëÿåòñÿ íåïëà-

íàðíûì,  ýòî ïîëíûé äâóäîëüíûé ãðàô Ê

3,3

. Â äâóäîëüíûõ ãðàôàõ

ìíîæåñòâî âåðøèí ðàçáèòî íà äâà íåïåðåñåêàþùèõñÿ ïîäìíîæåñòâà,

êîòîðûå íàçûâàþò äîëÿìè. Òàêèå ãðàôû âîçíèêàþò â çàäà÷àõ î

ñîåäèíåíèè n äîìîâ è m ïóíêòîâ îáñëóæèâàíèÿ ñ ïîìîùüþ êîììó-

íèêàöèé (ñì. ðèñ. 8.29). Íàïðèìåð, èññëåäîâàíèå ïëàíàðíîñòè ãðàôà

3,3

íåîáõîäèìî â çàäà÷å «î òðåõ äîìàõ è òðåõ êîëîäöàõ», â êîòîðîé

æèòåëè äîìîâ õîòåëè áû õîäèòü çà âîäîé ê êîëîäöàì òàê, ÷òîáû

íèêîãäà íå âñòðå÷àòü íèêîãî èç ñâîèõ ñîñåäåé. Î÷åâèäíî, äëÿ òîãî,

÷òîáû èõ æåëàíèå áûëî âûïîëíåíî, íóæíî, ÷òîáû èõ ïóòè íèêîãäà

íå ïåðåñåêàëèñü. Äëÿ ýòîãî ãðàô, ñîåäèíÿþùèé «äîìà» è «êîëîä-

öû», äîëæåí áûòü ïëîñêèì. Îäíàêî ãðàô Ê

3,3

 íåïëàíàðíûé, òàê

÷òî æåëàíèå æèòåëåé íåâûïîëíèìî (ñì. ðèñ. 8.29).

Ðèñ. 8.29. Çàäà÷à î äîìàõ èêîëîäöàõ.

Äëÿ ãðàôà K

3,3

m = 9, n = 6, ò.å.íåðàâåíñòâî Ýéëåðà âûïîëíÿåòñÿ.

Òåì íå ìåíåå, îí íåïëàíàðåí. Äîêàæåì ýòî.

Ïðåäïîëîæèì, ÷òî ãðàô K

3,3

ïëàíàðåí. Òîãäà, ïî òåîðåìå Ýéëåðà,

÷èñëî åãî ãðàíåé r=96+2=5. Â ñèëó äâóäîëüíîñòè K

3,3

, â íåì

íåò öèêëîâ äëèíîé ìåíüøå 4, ïîýòîìó, ñóììèðóÿ äëèíû ãðàíèö

âñåõ ãðàíåé è ó÷èòûâàÿ, ÷òî â ýòîé ñóììå êàæäîå ðåáðî ãðàôà

3,3

âñòðåòèòñÿ äâàæäû, ïîëó÷èì: 2m ≥ 4r, ò.å.4r ≤ 18, è, ñëåäîâà-

òåëüíî, r < 5, ÷òî ïðîòèâîðå÷èò òåîðåìå Ýéëåðà. Òàêèì îáðàçîì,

3,3

íåïëàíàðåí. Ýòî ïðèìåð òîãî, ÷òî óñëîâèå m≤3n 6íå ÿâëÿåòñÿ

äîñòàòî÷íûì óñëîâèåì ïëàíàðíîñòè.

Ãðàôû Ê

5

è Ê

3,3

ïîçâîëÿþò îïðåäåëèòü íàèáîëåå îáùèé êðèòåðèé

ïëàíàðíîñòè, êîòîðûé ìû ïðèâîäèì çäåñü áåç äîêàçàòåëüñòâà ââèäó

åãî ñëîæíîñòè. Ïðåäâàðèòåëüíî ââåäåì íîâûå îïðåäåëåíèÿ.

Îïðåäåëåíèå 8.32. Îïåðàöèÿ ïîäðàçáèåíèÿ ðåáðà (u, v) â ãðàôå

G={V, E} ñîñòîèò â óäàëåíèè èç E ðåáðà (u, v), äîáàâëåíèè ê V

íîâîé âåðøèíû w è äîáàâëåíèè ê E\{(u, v)} äâóõ ðåáåð (u, w) è

(w, v). Ãðàô H íàçûâàåòñÿ ïîäðàçáèåíèåì ãðàôà G, åñëè H ìîæåò

áûòü ïîëó÷åí èç G ïóòåì ïîñëåäîâàòåëüíîãî ïðèìåíåíèÿ îïåðà-

öèè ïîäðàçáèåíèÿ ðåáåð.

Íåòðóäíî óáåäèòüñÿ â òîì, ÷òî îïåðàöèÿ ïîäðàçáèåíèÿ ðåáðà

íå èçìåíÿåò ñîîòíîøåíèÿ Ýéëåðà. Äåéñòâèòåëüíî, â ðåçóëüòàòå ïîä-

ðàçáèåíèÿ êàê êîëè÷åñòâî ðåáåð, òàê è êîëè÷åñòâî âåðøèí, óâåëè-

÷èòñÿ íà åäèíèöó, à êîëè÷åñòâî ãðàíåé íå èçìåíèòñÿ (ñì. ðèñ.8.30),

òàê êàê ïðè óäàëåíèè ðåáðà â ïëîñêîì ãðàôå èñ÷åçíåò îäíà ãðàíü,

à ïðè äîáàâëåíèè äâóõ ðåáåð ïîÿâèòñÿ íîâàÿ. Òàêèì îáðàçîì,

(n+1)(m +1) + (r1+1) = n  m + r.

Ðèñ. 8.30. Ïîäðàçáèåíèå ðåáðà (u, v).

Îïðåäåëåíèå 8.33. Ãðàôû G è H ãîìåîìîðôíû, åñëè ñóùåñòâóþò

òàêèå èõ ïîäðàçáèåíèÿ, êîòîðûå èçîìîðôíû.

Òåîðåìà 8.22 (Ïîíòðÿãèíà  Êóðàòîâñêîãî). Ãðàô ïëàíàðåí òîã-

äà è òîëüêî òîãäà, êîãäà îí íå ñîäåðæèò ïîäãðàôîâ, ãîìåîìîðô-

íûõ ãðàôàì Ê

5

è Ê

3,3

149

Ãëàâà 9. ÁÓËÅÂÀ ÀËÃÅÁÐÀ

Äæîðäæ Áóëü (18151864) ðîäèëñÿ â Àíãëèè, â Ëèíêîëüíå, â ñåìüå

ìåëêîãî òîðãîâöà. Åãî ðîäèòåëè èñïûòûâàëè ìàòåðèàëüíûå

çàòðóäíåíèÿ, ïîýòîìó îí íå ñìîã ïîëó÷èòü ñèñòåìàòè÷åñêîãî

îáðàçîâàíèÿ,  êðîìå íà÷àëüíûõ êëàññîâ øêîëû äëÿ äåòåé áåäíÿêîâ

Äæîðäæ Áóëü íå ó÷èëñÿ íè â îäíîì ó÷åáíîì çàâåäåíèè. Îäíàêî ñ äåòñêèõ

ëåò Áóëü ñòðåìèëñÿ ê çíàíèÿì, ñàìîñòîÿòåëüíî èçó÷àÿ ìíîãèå

ïðåäìåòû, â òîì ÷èñëå ëàòûíü è ãðå÷åñêèé, êîòîðûå èçó÷àëèñü â òå

ãîäû âî âñåõ àðèñòîêðàòè÷åñêèõ øêîëàõ. Â 12 ëåò îí óæå ïå÷àòàë â

ìåñòíûõ èçäàíèÿõ ñâîè ïåðåâîäû èç Ãîðàöèÿ, íî ýòî íå ïðèíîñèëî äåíåã,

à ñåìüÿ ñèëüíî íóæäàëàñü. Ñ ðàííèõ ëåò íà÷àëñÿ òðóäîâîé ïóòü Áóëÿ,

ïîõîæèé íà ïóòü ìíîãèõ ãåðîåâ Äèêêåíñà: Áóëü äîëãî èñêàë ðàáîòó,

äàþùóþ êàêîé-òî çàðàáîòîê è, â òî æå âðåìÿ, îñòàâëÿþùóþ

âîçìîæíîñòè äëÿ äàëüíåéøåãî ñàìîîáðàçîâàíèÿ. Ëèøü ïîñëå äîëãèõ

ìó÷èòåëüíûõ ïîèñêîâ è ìíîãèõ íåóäà÷íûõ ïîïûòîê óñòðîèòüñÿ Áóëþ

óäàëîñü îòêðûòü ìàëåíüêóþ ýëåìåíòàðíóþ øêîëó, â êîòîðîé îí

ïðåïîäàâàë ñàì. Äåíåã ýòî äàâàëî ìàëî, íî îñòàâëÿëî íåêîòîðûé äîñóã.

Â ïðîöåññå çàíÿòèé ñ ó÷åíèêàìè Áóëü âïåðâûå îáðàòèëñÿ ê ìàòåìàòèêå,

è øêîëüíûå ó÷åáíèêè ïðèâåëè åãî â óæàñ ñâîåé íåñòðîãîñòüþ è

íåëîãè÷íîñòüþ èçëîæåíèÿ. Ñòðåìÿñü ïîíÿòü, ÷òî æå íà ñàìîì äåëå

ïðåäñòàâëÿåò ñîáîé ìàòåìàòèêà, Áóëü îáðàòèëñÿ ê ïðîèçâåäåíèÿì

êëàññèêîâ è ñàìîñòîÿòåëüíî èçó÷èë îáøèðíûå òðóäû Ëàïëàñà è

Ëàãðàíæà. Â ñâÿçè ñ ýòèìè çàíÿòèÿìè ó íåãî ïîÿâèëèñü ïåðâûå ñàìîñòî-

ÿòåëüíûå èäåè. Ê åãî ñ÷àñòüþ, Ä.Ãðåãîðè, îñíîâàâøèé íåçàäîëãî äî òîãî

«Êåìáðèäæñêèé ìàòåìàòè÷åñêèé æóðíàë», ñðàçó æå îöåíèë ãëóáèíó

ìûñëè è îðèãèíàëüíîñòü ñòèëÿ ïðîâèíöèàëüíîãî ó÷èòåëÿ, ïðèñûëàâøåãî

åìó ñâîè ñòàòüè. Âòîðûì ÷åëîâåêîì, àêòèâíî ïîääåðæàâøèì Áóëÿ,

áûë êåìáðèäæñêèé ìàòåìàòèê, ïðîôåññîð óíèâåðñèòåòà Àóãóñòóñ äå

Ìîðãàí. Äå Ìîðãàí ñàì èíòåðåñîâàëñÿ âîïðîñàìè ëîãè÷åñêîãî îáîñíî-

âàíèÿ ìàòåìàòèêè, êîòîðûå âñêîðå ñòàëè êðàåóãîëüíûì êàìíåì âñåõ

ðàçìûøëåíèé Áóëÿ. Ïåðâûå ïóáëèêàöèè Áóëÿ çàèíòåðåñîâàëè äå Ìîðãà-

íà, à êðàòêàÿ áðîøþðà «Ìàòåìàòè÷åñêèé àíàëèç ëîãèêè, ñîïðîâîæ-

äàåìûé íàáðîñêîì èñ÷èñëåíèÿ äåäóêòèâíûõ ðàññóæäåíèé» (1847),

ïðèâåëà åãî â âîñòîðã. (Çàìåòèì, ÷òî â òîì æå 1847 ã., íåñêîëüêèìè

ìåñÿöàìè ïîçæå, âûøëî â ñâåò ñî÷èíåíèå ñàìîãî äå Ìîðãàíà íà òó æå

òåìó: «Ôîðìàëüíàÿ ëîãèêà èëè èñ÷èñëåíèå âûâîäîâ, íåîáõîäèìûõ è

âîçìîæíûõ», ãäå, â ÷àñòíîñòè, ñîäåðæàëèñü òå ëîãè÷åñêèå çàêîíû,

êîòîðûå ñåé÷àñ íàçûâàþò «çàêîíàìè äå Ìîðãàíà»; ýòî îáñòîÿòåëüñòâî

äåëàëî åãî îöåíêó ðàáîòû Áóëÿ îñîáåííî âåñîìîé). Óñèëèÿìè äå Ìîðãàíà,

Ãðåãîðè è äðóãèõ äðóçåé ñàìîó÷êà Áóëü ñòàë â 1849 ãîäó ïðîôåññîðîì

ìàòåìàòèêè êàòîëè÷åñêîãî êîëëåäæà â ã.Êîðê (Èðëàíäèÿ); çäåñü îí

ïðîâåë ïîñëåäíèå 15 ëåò ñâîåé æèçíè, íàêîíåö-òî ïîëó÷èâ âîçìîæíîñòü

íå òîëüêî îáåñïå÷èòü ñòàðîñòü ðîäèòåëåé, íî è ñïîêîéíî çàíèìàòüñÿ

íàóêîé. Çäåñü æå îí æåíèëñÿ íà Ìýðè Ýâåðåñò äî÷åðè ïðîôåññîðà

ãðå÷åñêîãî ÿçûêà â òîì æå êîëëåäæå è ðîäñòâåííèöå áûâøåãî ãåíåðàë-

ãóáåðíàòîðà Èíäèè, èìåíåì êîòîðîãî íàçâàíà âûñî÷àéøàÿ âåðøèíà

ìèðà Ýâåðåñò. Ìýðè Áóëü-Ýâåðåñò ìíîãî ïîìîãàëà Áóëþ â ðàáîòå, à

ïîñëå åãî ñìåðòè îñòàâèëà èíòåðåñíûå âîñïîìèíàíèÿ î ñâîåì ìóæå è î

åãî íàó÷íîì òâîð÷åñòâå. Îíà ñòàëà ìàòåðüþ ÷åòûðåõ äî÷åðåé Áóëÿ,

êîòîðûå âñå îêàçàëèñü çàìå÷àòåëüíûìè ëþäüìè (ó íàñ íàèáîëåå èçâåñò-

íà Ýòåëü Ëèëèàí Áóëü, â çàìóæåñòâå Âîéíè÷, àâòîð ðîìàíà «Îâîä»).

Â 1854 ã. âûøëî â ñâåò îñíîâíîå ïðîèçâåäåíèå Áóëÿ «Èññëåäîâàíèå

çàêîíîâ ìûñëè, íà êîòîðûõ îñíîâàíû ìàòåìàòè÷åñêèå òåîðèè ëîãèêè

è âåðîÿòíîñòåé». Â ýòîé, ñòàâøåé êëàññè÷åñêîé, ðàáîòå ïîäðîáíî èññëå-

äóåòñÿ àëãåáðàè÷åñêàÿ ñèñòåìà, êîòîðóþ ñåãîäíÿ íàçûâàþò «àëãåá-

ðîé âûñêàçûâàíèé». Ãëóáîêîå ïîíèìàíèå Áóëåì ïðèðîäû ìàòåìàòèêè

è ñìûñëà àáñòðàêòíûõ ìàòåìàòè÷åñêèõ ñòðóêòóð, êîòîðîå ïðîÿâèëîñü

â ýòîé êíèãå, îòìå÷àë Á. Ðàññåë: «×èñòóþ ìàòåìàòèêó îòêðûë Áóëü â

ñî÷èíåíèè, êîòîðîå íàçûâàëîñü «Çàêîíû ìûñëè». Ðàçóìååòñÿ, ôðàçó

Ðàññåëà íèêàê íå ñëåäóåò ïîíèìàòü áóêâàëüíî: òàê, íå ãîâîðÿ óæå î

ãåíèàëüíîì Ãîòôðèäå Âèëüãåëüìå Ëåéáíèöå (16461716) èëè î äðåâíèõ

ãðåêàõ, íà åâðîïåéñêîì êîíòèíåíòå íå óñòóïàþùóþ Áóëþ ãëóáèíó

ïîíèìàíèÿ àáñòðàêòíîé ïðèðîäû «÷èñòîé» ìàòåìàòèêè

äåìîíñòðèðîâàë â òå æå ãîäû åùå îäèí ñàìîó÷êà (åùå îäèí øêîëüíûé

ó÷èòåëü, òàê æå, êàê è Áóëü, ïî äîñòîèíñòâó îöåíåííûé ëèøü ïîñëå

ñìåðòè),  íåìåö Ãåðìàí Ãðàññìàí (18091877). Îäíàêî áåññïîðíî,

÷òî äàííàÿ Äæ. Áóëåì â «Çàêîíàõ ìûñëè» õàðàêòåðèñòèêà (ëþáîãî!)

ìàòåìàòè÷åñêîãî èñ÷èñëåíèÿ êàê «ìåòîäà, áàçèðóþùåãîñÿ íà óïîòðåá-

ëåíèè ñèìâîëîâ, çàêîíû êîìáèíàöèè êîòîðûõ íàì èçâåñòíû» èëè ôðàçà

«äåéñòâåííîñòü àíàëèçà çàâèñèò íå îò èñòîëêîâàíèÿ ñèìâîëîâ, à èñêëþ-

÷èòåëüíî îò çàêîíîâ èõ êîìáèíàöèè» ñâèäåòåëüñòâóþò îá èñêëþ÷è-

òåëüíîé ãëóáèíå ïðîíèêíîâåíèÿ â ñóòü ìàòåìàòèêè. Ïåðâàÿ ñåðüåçíàÿ

ïîïûòêà ôîðìàëèçîâàííîãî èçëîæåíèÿ òîé ëîãè÷åñêîé ñèñòåìû,

êîòîðàÿ ëåæèò â îñíîâå âñåõ ìàòåìàòè÷åñêèõ óìîçàêëþ÷åíèé, ïîïûòêà

ñòðîãîãî îïèñàíèÿ òåõ «ïðàâèë èãðû», êîòîðûì ïîä÷èíÿåòñÿ ìàòåìà-

òèêà, ïðèíàäëåæèò èìåííî Äæîðäæó Áóëþ.

9.1. Àáñòðàêòíàÿ áóëåâà àëãåáðà

Îïðåäåëåíèå áóëåâîé àëãåáðû äàíî â ãëàâå 6 (ñì. îïðåäåëåíèå

6.13). Ïîñêîëüêó ëþáóþ ðåøåòêó ìîæíî ðàññìàòðèâàòü êàê àëãåáðó

ñ äâóìÿ îïåðàöèÿìè, áóëåâó ðåøåòêó, â êîòîðîé êàæäûé ýëåìåíò

èìååò åäèíñòâåííîå äîïîëíåíèå, ìîæíî ðàññìàòðèâàòü êàê áóëåâó àë-

ãåáðó ñ òðåìÿ îïåðàöèÿìè. Â äàííîé ãëàâå ìû ðàññìîòðèì â íåêî-

òîðîì ñìûñëå «ìèíèìàëüíóþ» áóëåâó àëãåáðó, êîòîðàÿ ñòðîèòñÿ

íà ðåøåòêå 2, ñîñòîÿùåé èç äâóõ ýëåìåíòîâ. Ýòè ýëåìåíòû îáîçíà-

÷àþòñÿ ñèìâîëàìè 0 è 1, õîòÿ ïðèðîäà èõ ìîæåò áûòü ðàçëè÷íà,

íàïðèìåð, «ëîæü» è «èñòèíà» â àëãåáðå âûñêàçûâàíèé, ïîëîæåíèå

âûêëþ÷àòåëÿ «ðàçîìêíóòî»/«çàìêíóòî»  â òåîðèè ðåëåéíî-êîíòàêò-

íûõ ñõåì. Â àáñòðàêòíîé áóëåâîé àëãåáðå ïðèðîäà ìíîæåñòâà {0, 1}

íå ðàññìàòðèâàåòñÿ. Ðåøåòî÷íûå îïåðàöèè îáúåäèíåíèÿ (∨),

150 151

ïåðåñå÷åíèÿ (∧) è äîïîëíåíèÿ (') èìåþò äðóãèå íàèìåíîâàíèÿ è

ðàññìàòðèâàþòñÿ êàê àëãåáðàè÷åñêèå îïåðàöèè. Âñå ñâîéñòâà

áóëåâûõ ðåøåòîê, ðàçóìååòñÿ, âûïîëíåíû â áóëåâîé àëãåáðå è îïðå-

äåëÿþòñÿ â íåé êàê àêñèîìû è òåîðåìû. Ðàññìîòðèì îïðåäåëåíèå

áóëåâîé àëãåáðû òàê, êàê ýòî ïðèíÿòî â îáùåèçâåñòíîé ëèòåðàòóðå.

Îïðåäåëåíèå 9.1. Âñÿêóþ ïåðåìåííóþ, êîòîðàÿ ìîæåò ïðèíè-

ìàòü îäíî èç äâóõ âîçìîæíûõ çíà÷åíèé, îáîçíà÷àåìûõ 0 è 1,

íàçîâåì áóëåâîé ïåðåìåííîé.

Îïðåäåëåíèå 9.2. Ôóíêöèÿ f(x

, ..., x

), ïðèíèìàþùàÿ çíà÷åíèÿ

íà ìíîæåñòâå {0, 1} âìåñòå ñî ñâîèìè ïåðåìåííûìè, íàçûâàåòñÿ

áóëåâîé ôóíêöèåé.

Ñîâîêóïíîñòü çíà÷åíèé ïåðåìåííûõ áóëåâîé ôóíêöèè áóäåì

íàçûâàòü íàáîðîì. Íàïðèìåð, äëÿ áóëåâîé ôóíêöèè f(x, y, z)

ñîâîêóïíîñòü çíà÷åíèé x = 1, y = 0, z = 1 çàïèñûâàåòñÿ êàê íàáîð

101. Áóëåâà ôóíêöèÿ ìîæåò áûòü çàäàíà ñ ïîìîùüþ òàáëèöû 

ïåðå÷èñëåíèåì åå çíà÷åíèé íà âñåõ íàáîðàõ. Ìíîæåñòâî íàáîðîâ

ïðèíÿòî çàïèñûâàòü â ëåêñèêîãðàôè÷åñêîì ïîðÿäêå, òàê ÷òî êàæäûé

íàáîð ïðåäñòàâëÿåò ñîáîé êîä äâîè÷íîãî ÷èñëà. Ñîîòâåòñòâóþùåå

åìó äåñÿòè÷íîå ÷èñëî áóäåì íàçûâàòü íîìåðîì íàáîðà. Íàïðèìåð,

íîìåð íàáîðà 101 ðàâåí 5, íîìåð íàáîðà 110  6.

Óòâåðæäåíèå 9.1. Êîëè÷åñòâî íàáîðîâ áóëåâîé ôóíêöèè f(x

, x

) îò n ïåðåìåííûõ ðàâíî 2

. Êîëè÷åñòâî áóëåâûõ ôóíêöèé

îò n ïåðåìåííûõ ðàâíî 2 â ñòåïåíè 2

Äîêàçàòåëüñòâî ýòîãî óòâåðæäåíèÿ íåïîñðåäñòâåííî ñëåäóåò èç

îñíîâíûõ ñîîòíîøåíèé êàðäèíàëüíîé àðèôìåòèêè. Äåéñòâèòåëüíî,

ìíîæåñòâî âñåõ íàáîðîâ áóëåâîé ôóíêöèè îò n ïåðåìåííûõ îáðàçî-

âàíî äåêàðòîâûì ïðîèçâåäåíèåì {0,1}

, ìîùíîñòü êîòîðîãî ðàâíà 2

Ìíîæåñòâî âñåõ áóëåâûõ ôóíêöèé îò n ïåðåìåííûõ åñòü ìíîæåñòâî

îòîáðàæåíèé {0,1}

→{0,1), ìîùíîñòü êîòîðîãî ðàâíà

Ñóùåñòâóåò 4 áóëåâûõ ôóíêöèè îò îäíîé ïåðåìåííîé è 16áó-

ëåâûõ ôóíêöèé îò äâóõ ïåðåìåííûõ. Â òàáëèöå 9.1 ïðèâåäåíû

áóëåâû ôóíêöèè îò îäíîé ïåðåìåííîé:

 êîíñòàíòà 0,

 òîæäåñòâåííàÿ ôóíêöèÿ f(x) = x,

 îòðèöàíèå f(x) = ¬x,

 êîíñòàíòà 1.

Òàáëèöà 9.1.

Â òàáë. 9.2 ïðèâåäåíû îñíîâíûå ôóíêöèè îò äâóõ ïåðåìåííûõ.

Òàáëèöà.9.2.

Ýòî ôóíêöèè:

x ∧ y (èëè x&y)  êîíúþíêöèÿ,

x ∨ y  äèçúþíêöèÿ,

x → y (èëè x⊃y)  èìïëèêàöèÿ,

x≡y (èëè x ~ y)  ýêâèâàëåíòíîñòü (ýêâèâàëåíöèÿ),

x ⊕ y  ñëîæåíèå ïî mod 2 (îïåðàöèÿ Æåãàëêèíà).

Óòâåðæäåíèå 9.2. Ìíîæåñòâî, ñîñòîÿùåå èç äâóõ çíà÷åíèé 0è1,

íà êîòîðîì îïðåäåëåíû óíàðíàÿ îïåðàöèÿ îòðèöàíèÿ ¬ ñîãëàñíî

òàáë. 9.1, è áèíàðíûå îïåðàöèè äèçúþíêöèè ∨ è êîíúþíêöèè ∧

ñîãëàñíî òàáë. 9.2, ÿâëÿåòñÿ áóëåâîé àëãåáðîé.

Èñòèííîñòü óòâåðæäåíèÿ 9.2. ñëåäóåò èç òåîðèè ðåøåòîê:

îïåðàöèÿ îòðèöàíèÿ áóëåâîé àëãåáðû îïðåäåëÿåòñÿ êàê äîïîëíåíèå

â ðåøåòêå 2, äèçúþíêöèè ∨ è êîíúþíêöèè ∧  êàê îáúåäèíåíèå è

ïåðåñå÷åíèå ñîîòâåòñòâåííî.

Îïåðàöèÿ îòðèöàíèÿ ïðè ðóêîïèñíîì íàïèñàíèè îáû÷íî çàïè-

ñûâàåòñÿ êàê ÷åðòà íàä ñèìâîëîì ïåðåìåííîé, íàïðèìåð:

∨

()

îäíàêî, ìû áóäåì èñïîëüçîâàòü ñèìâîë ¬, íàïðèìåð: ¬x, ¬(x∨y).

Èíîãäà îòðèöàíèå îáîçíà÷àåòñÿ ñèìâîëîì ~, íàïðèìåð: ~x. Îïåðà-

öèÿ êîíúþíêöèè â áóëåâîé àëãåáðå îáû÷íî îáîçíà÷àåòñÿ ñèìâîëîì

∧, â àëãåáðå âûñêàçûâàíèé  ñèìâîëîì &. Â âûðàæåíèÿõ áóëåâîé

àëãåáðû ýòîò ñèìâîë ÷àñòî îïóñêàåòñÿ, êàê ñèìâîë óìíîæåíèÿ

âàðèôìåòè÷åñêèõ âûðàæåíèÿõ, íàïðèìåð, âûðàæåíèå x∧y çàïè-

ñûâàåòñÿ êàê xy.

9.2. Îñíîâíûå àêñèîìû è òåîðåìû áóëåâîé àëãåáðû

Àêñèîìû è òåîðåìû áóëåâîé àëãåáðû íåïîñðåäñòâåííî ñëåäóþò

èç ñâîéñòâ áóëåâûõ ðåøåòîê. Ïðèâåäåì ñïèñîê àêñèîì è îñíîâíûõ

òåîðåì áóëåâîé àëãåáðû.

Àêñèîìû áóëåâîé àëãåáðû:

(9.1) êîììóòàòèâíûå çàêîíû:

a ∨ b = b ∨ a;

a ∧ b = b ∧ a;

Áóëåâà àëãåáðàÃëàâà 9

00011

10101

xyx ∧ yx ∨ yx → yx ≡ yx ⊕ y

0000110

0101101

1001001

1111110

152 153Áóëåâà àëãåáðàÃëàâà 9

(9.2) äèñòðèáóòèâíûå çàêîíû:

a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c);

a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c);

(9.3) ñâîéñòâà 0 è 1:

a ∨ 0 = a, a ∧ 1 = a;

(9.4) çàêîí èñêëþ÷åííîãî òðåòüåãî:

a ∨ ¬a = 1;

çàêîí ïðîòèâîðå÷èÿ:

a ∧ ¬a = 0.

Òåîðåìû:

(9.5) àññîöèàòèâíûå çàêîíû:

a ∨ (b ∨ c)=(a ∨ b) ∨ c;

a ∧ (b ∧ c)=(a ∧ b) ∧ c;

(9.6) åñëè äëÿ âñåõ a a ∨ b = a, òî b = 0;

åñëè äëÿ âñåõ a a ∧ b = a, òî b = 1;

(9.7) åñëè a ∨ b = 1 è a ∧ b = 0, òî b = ¬a;

(9.8) ¬¬a = a;

(9.9) ¬0 = 1, ¬1 = 0;

(9.10) çàêîíû èäåìïîòåíòíîñòè:

a ∨ a = a;

a ∧ a = a;

(9.11) a ∨ 1 = 1, a ∧ 0 = 0;

(9.12) çàêîíû ïîãëîùåíèÿ:

a ∨ (a ∧ b) = a;

a ∧ (a ∨ b) = a;

(9.13) çàêîíû äå Ìîðãàíà:

¬(a ∨ b) = ¬a ∧ ¬b;

¬(a ∧ b) = ¬a ∨ ¬b;

(9.14) çàêîíû ñêëåèâàíèÿ:

(a ∨ b) ∧ (a ∨ ¬b) = a;

(a ∧ b) ∨ (a ∧ ¬b) = a.

9.3. Áóëåâû ôîðìóëû

Îïðåäåëåíèå 9.3.

•Êàæäàÿ ïåðåìåííàÿ åñòü ôîðìóëà.

•Åñëè x, y  ôîðìóëû, òî ôîðìóëàìè ÿâëÿþòñÿ (¬x), (x∨y), (x&y).

•Äðóãèõ ôîðìóë íåò.

Â èçîáðàæåíèè ôîðìóë ïðèíÿòû ñëåäóþùèå äîïóùåíèÿ:

âíåøíèå ñêîáêè îïóñêàþò; óñòàíàâëèâàþò ïðèîðèòåòû âûïîëíåíèÿ

îïåðàöèé â ñëåäóþùåì ïîðÿäêå:

¬  îòðèöàíèå (íàèâûñøèé ïðèîðèòåò),

∧  êîíúþíêöèÿ,

∨  äèçúþíêöèÿ,

→, ≡  èìïëèêàöèÿ è ýêâèâàëåíòíîñòü (èìåþò îäèíàêîâûé

ïðèîðèòåò).

Ñ ó÷åòîì ýòèõ ïðèîðèòåòîâ èçáûòî÷íûå ñêîáêè òàêæå

îïóñêàþòñÿ.

Äëÿ êàæäîé áóëåâîé ôîðìóëû ìîæíî ïîñòðîèòü òàáëèöó åå

çíà÷åíèé, ïîëüçóÿñü îïðåäåëåíèåì îñíîâíûõ îïåðàöèé. Áóëåâû

ôîðìóëû íàçûâàþòñÿ ýêâèâàëåíòíûìè, èëè ðàâíîñèëüíûìè, åñëè

èõ òàáëèöû ñîâïàäàþò. (Äëÿ îáîçíà÷åíèÿ ðàâíîñèëüíîñòè ôîðìóë

ìû èñïîëüçóåì ñèìâîë =). Òàêèå ôîðìóëû, êîòîðûå íà îäíèõ è

òåõ æå íàáîðàõ ïðèíèìàþò îäèíàêîâûå çíà÷åíèÿ, ïðåäñòàâëÿþò

îäíó è òó æå áóëåâó ôóíêöèþ. Òàêèì îáðàçîì, îäíà è òà æå áóëåâà

ôóíêöèÿ ìîæåò áûòü ïðåäñòàâëåíà ðàçëè÷íûìè ôîðìóëàìè, à

ïîñêîëüêó äëÿ êàæäîé áóëåâîé ôîðìóëû ìîæíî ïîñòðîèòü

åäèíñòâåííóþ òàáëèöó çíà÷åíèé, òî êàæäîé áóëåâîé ôîðìóëå

ñîîòâåòñòâóåò åäèíñòâåííàÿ áóëåâà ôóíêöèÿ.

Åñëè äâå ðàâíîñèëüíûå ôîðìóëû ñîåäèíèòü ñ ïîìîùüþ îïåðà-

öèè ýêâèâàëåíòíîñòè, òî âíîâü ïîëó÷åííàÿ ôîðìóëà áóäåò òîæäå-

ñòâåííî ðàâíà åäèíèöå. Àêñèîìû è òåîðåìû áóëåâîé àëãåáðû çàäàþò

ðàâíîñèëüíûå ôîðìóëû.

Ðàññìîòðèì íåêîòîðûå ðàâíîñèëüíûå ôîðìóëû (ñì. òàáë. 9.3).

Òàáëèöà 9.3.

Ìû âèäèì, ÷òî òàáëèöû çíà÷åíèé ôîðìóë x → y è ¬x ∨ y

ñîâïàäàþò, ñëåäîâàòåëüíî, ýòè ôîðìóëû ýêâèâàëåíòíû:

(9.15) x → y = ¬x ∨ y.

Ýêâèâàëåíòíû òàêæå ôîðìóëû:

(9.16) x ≡ y = ¬(x ⊕ y),

(9.17) x ≡ y = (x → y)(y → x).

xyx → y ¬x ∨ yy → x (x → y)(y → x) x ≡ yx ⊕ y ¬(x ⊕ y)

00 1 1 1 1 1 0 1

01 1 1 0 0 0 1 0

10 0 0 1 0 0 1 0

11 1 1 1 1 1 0 1

154 155Áóëåâà àëãåáðàÃëàâà 9

Â (9.17) ìû ìîæåì çàìåíèòü èìïëèêàöèþ íà ðàâíîñèëüíóþ åé

ôîðìóëó (9.15). Â ðåçóëüòàòå ïîëó÷èì:

x ≡ y = (x → y)(y → x) = (¬x ∨ y)(¬y ∨ x).

Ýòè ðàâíîñèëüíîñòè îáúÿñíÿþò, ïî÷åìó ïðè îïðåäåëåíèè áóëå-

âîé ôîðìóëû èñïîëüçóþòñÿ òîëüêî îïåðàöèè ¬, ∨, ∧,  îïåðàöèè

èìïëèêàöèè, ýêâèâàëåíòíîñòè è ñëîæåíèÿ ïî ìîäóëþ 2 ìîãóò áûòü

ââåäåíû ñ ïîìîùüþ ðàâíîñèëüíûõ ôîðìóë (9.15)  (9.17).

Ñ ïîìîùüþ ðàâíîñèëüíûõ ôîðìóë ìîæíî ïðîâîäèòü

ýêâèâàëåíòíûå ïðåîáðàçîâàíèÿ áóëåâûõ ôîðìóë. Íàïðèìåð,

ïðåîáðàçóåì áóëåâó ôîðìóëó ¬x ⊕ (z → y).

¬x ⊕ (z → y) = z → y = ¬z ∨ y,

= ¬x ⊕ (¬z ∨ y) = x ⊕ y = ¬(x ≡ y),

= ¬(¬x ≡ (¬z ∨ y)) = x ≡ y = (¬x ∨ y)(¬y ∨ x),

= ¬((¬¬x ∨ (¬z ∨ y))(¬(¬z ∨ y) ∨ ¬x)) = ¬¬x = x

= ¬((x ∨ ¬z ∨ y)(¬(¬z ∨ y) ∨ ¬x)) = çàêîí äå Ìîðãàíà

= ¬((x ∨ ¬z ∨ y)( z ¬y ∨ ¬x)) = çàêîí äå Ìîðãàíà

= (¬xz¬y) ∨ ((¬z ∨ y)x) = äèñòðèáóòèâíûé

= ¬xz¬y ∨ ¬zx ∨ yx = çàêîí

= ¬x¬yz ∨ x¬z ∨ xy. àññîöèàòèâíûé

çàêîí

9.4. Äèçúþíêòèâíûå è êîíúþíêòèâíûå

íîðìàëüíûå ôîðìû

Ïîñêîëüêó îäíà è òà æå áóëåâà ôóíêöèÿ ìîæåò áûòü ïðåäñòàâ-

ëåíà ðàçëè÷íûìè ôîðìóëàìè, âîçíèêàåò âîïðîñ î åäèíñòâåííîñòè

ïðåäñòàâëåíèÿ áóëåâûõ ôóíêöèé, ò.å. íàõîæäåíèÿ òàêîé

óíèâåðñàëüíîé ôîðìû, ÷òîáû êàæäàÿ áóëåâà ôóíêöèÿ ìîãëà áûòü

ïðåäñòàâëåíà â íåé. Òàêèìè ôîðìàìè â áóëåâîé àëãåáðå ÿâëÿþòñÿ

ñîâåðøåííûå äèçúþíêòèâíàÿ è êîíúþíêòèâíàÿ íîðìàëüíûå ôîðìû.

Îïðåäåëåíèå 9.4. Âñÿêàÿ áóëåâà ôîðìóëà, ïîñòðîåííàÿ ñ ïîìî-

ùüþ îäíîé òîëüêî îïåðàöèè äèçúþíêöèè íàä áóëåâûìè ïåðå-

ìåííûìè èëè èõ îòðèöàíèÿìè, íàçûâàåòñÿ ýëåìåíòàðíîé

äèçúþíêöèåé, èëè äèçúþíêòîì. Íàïðèìåð, x

∨x

∨¬x

∨x



ýëåìåíòàðíàÿ äèçúþíêöèÿ.

Îïðåäåëåíèå 9.5. Âñÿêàÿ áóëåâà ôîðìóëà, ïîñòðîåííàÿ ñ ïîìî-

ùüþ îäíîé òîëüêî îïåðàöèè êîíúþíêöèè íàä ïåðåìåííûìè èëè

èõ îòðèöàíèÿìè, íàçûâàåòñÿ ýëåìåíòàðíîé êîíúþíêöèåé, èëè

êîíúþíêòîì. Íàïðèìåð, x

¬x

 ýëåìåíòàðíàÿ êîíúþíêöèÿ.

Òåîðåìà 9.1. Äëÿ òîãî ÷òîáû ýëåìåíòàðíàÿ äèçúþíêöèÿ òîæäå-

ñòâåííî ðàâíÿëàñü åäèíèöå, íåîáõîäèìî è äîñòàòî÷íî, ÷òîáû â

íåå âõîäèëà íåêîòîðàÿ ïåðåìåííàÿ âìåñòå ñî ñâîèì îòðèöàíèåì.

Òåîðåìà 9.2. Äëÿ òîãî, ÷òîáû ýëåìåíòàðíàÿ êîíúþíêöèÿ òîæäå-

ñòâåííî ðàâíÿëàñü íóëþ, íåîáõîäèìî è äîñòàòî÷íî, ÷òîáû â íåå

âõîäèëà íåêîòîðàÿ ïåðåìåííàÿ âìåñòå ñî ñâîèì îòðèöàíèåì.

Ñïðàâåäëèâîñòü òåîðåì 9.1, 9.2 ñëåäóåò èç àêñèîìû (9.4) è

îïðåäåëåíèÿ îïåðàöèé äèçúþíêöèè è êîíúþíêöèè.

Îïðåäåëåíèå 9.6. Áóëåâà ôóíêöèÿ íàçûâàåòñÿ êîíñòèòóåíòîé

åäèíèöû (èëè ìèíòåðìîì), åñëè îíà ðàâíà åäèíèöå òîëüêî íà

îäíîì íàáîðå ñâîèõ àðãóìåíòîâ.

Îïðåäåëåíèå 9.7. Áóëåâà ôóíêöèÿ íàçûâàåòñÿ êîíñòèòóåíòîé

íóëÿ (èëè ìàêñòåðìîì), åñëè îíà ðàâíà íóëþ òîëüêî íà îäíîì

íàáîðå ñâîèõ àðãóìåíòîâ.

Ïðèìåð. Ñðåäè áóëåâûõ ôóíêöèé äâóõ àðãóìåíòîâ êîíúþíêöèÿ

è ñòðåëêà Ïèðñà (x↑y = ¬(x ∨ y)) ÿâëÿþòñÿ êîíñòèòóåíòàìè

åäèíèöû, à äèçúþíêöèÿ, èìïëèêàöèÿ, øòðèõ Øåôôåðà (x|y=

=¬(x∧y)) ÿâëÿþòñÿ êîíñòèòóåíòàìè íóëÿ.

Òåîðåìà 9.3. Íå òîæäåñòâåííî ëîæíàÿ ýëåìåíòàðíàÿ êîíúþíê-

öèÿ îò n ïåðåìåííûõ ÿâëÿåòñÿ êîíñòèòóåíòîé åäèíèöû îò nïå-

ðåìåííûõ.

Äîêàçàòåëüñòâî. Ââåäåì îáîçíà÷åíèå: x

= ¬x, x

= x. Îáîçíà÷èì

ïàðàìåòð 0 èëè 1 ÷åðåç α. Òîãäà õ

= 1, åñëè x = α, è x

= 0, åñëè

x≠α. Êðîìå òîãî, 1

= α, 0

= ¬α.

Ðàññìîòðèì ýëåìåíòàðíóþ êîíúþíêöèþ âèäà x

α1

α2

x

αn

îêîòîðîé èçâåñòíî, ÷òî îíà íå ðàâíà íóëþ òîæäåñòâåííî. Èç

òåîðåìû 9.2 ñëåäóåò, ÷òî âñå âõîäÿùèå â íåå ïåðåìåííûå ðàçëè÷íû

è èì ìîæíî ïðèäàâàòü íåçàâèñèìûå çíà÷åíèÿ. Ïðèäàäèì

ïåðåìåííîé x

çíà÷åíèå α

, x

= α

è ò.ä. äî x

=α

. Òîãäà ýëåìåíòàð-

íàÿ êîíúþíêöèÿ x

α1

α2

x

αn

ðàâíà åäèíèöå ïî ñàìîìó âûáîðó

çíà÷åíèé x

, x

, ..., x

. Âûáîð ýòèõ çíà÷åíèé òàêîâ, ÷òî åñëè

ïåðåìåííàÿ x

âõîäèò â ýëåìåíòàðíóþ êîíúþíêöèþ ñ îòðèöàíèåì,

òî α

= 0 è ïåðåìåííîé x

òîæå ïðèäàåì çíà÷åíèå, ðàâíîå íóëþ.

Òîãäà, ïî îïðåäåëåíèþ, çíà÷åíèå õ

αi

=¬x =¬0 = 1. Åñëè æå

ïåðåìåííàÿ x

âõîäèò â ýëåìåíòàðíóþ êîíúþíêöèþ áåç îòðèöàíèÿ,

òî α

= 1 è x

= x = 1. Òàêèì îáðàçîì, áóäåò íàéäåí íàáîð, íà

êîòîðîì äàííàÿ êîíúþíêöèÿ áóäåò ðàâíà åäèíèöå. Åäèíñòâåííîñòü

òàêîãî íàáîðà ñëåäóåò èç îïðåäåëåíèÿ îïåðàöèè êîíúþíêöèè.

Èç òåîðåìû 9.3 ñëåäóåò, ÷òî âñÿêóþ êîíñòèòóåíòó åäèíèöû ìîæ-

íî ïðåäñòàâèòü â âèäå ýëåìåíòàðíîé êîíúþíêöèè. Äëÿ ýòîãî íåîáõî-

äèìî îáðàçîâàòü êîíúþíêöèþ âñåõ åå àðãóìåíòîâ è ðàññòàâèòü îòðè-

öàíèÿ íàä òåìè ïåðåìåííûìè, êîòîðûå ðàâíû íóëþ íà íàáîðå,

îáðàùàþùåì ôóíêöèþ â åäèíèöó.

Àíàëîãè÷íóþ òåîðåìó ìîæíî äîêàçàòü äëÿ ýëåìåíòàðíîé äèçúþíêöèè.

156 157Áóëåâà àëãåáðàÃëàâà 9

Òåîðåìà 9.4. Íå òîæäåñòâåííî èñòèííàÿ ýëåìåíòàðíàÿ äèçú-

þíêöèÿ îò n ïåðåìåííûõ ÿâëÿåòñÿ êîíñòèòóåíòîé íóëÿ îò nïå-

ðåìåííûõ.

Äîêàçàòåëüñòâî ïðåäîñòàâëÿåòñÿ ÷èòàòåëþ.

Èç ýòîé òåîðåìû ñëåäóåò, ÷òî ëþáóþ êîíñòèòóåíòó íóëÿ ìîæíî

ïðåäñòàâèòü â âèäå ýëåìåíòàðíîé äèçúþíêöèè. Äëÿ ýòîãî íåîá-

õîäèìî îáðàçîâàòü äèçúþíêöèþ âñåõ ïåðåìåííûõ è ðàññòàâèòü

îòðèöàíèÿ íàä òåìè ïåðåìåííûìè, êîòîðûå ðàâíû åäèíèöå íà

íàáîðå, îáðàùàþùåì ôóíêöèþ â íóëü.

Ïðèìåð. Ïóñòü ôóíêöèÿ f(x, y, z, v) ðàâíà åäèíèöå íà åäèí-

ñòâåííîì íàáîðå 0110. Òîãäà îíà ÿâëÿåòñÿ êîíñòèòóåíòîé åäèíèöû

è åå ìîæíî çàïèñàòü â âèäå: f(x, y, z, v) = ¬xyz¬v.

Îïðåäåëåíèå 9.8. Äèçúþíêöèÿ ýëåìåíòàðíûõ êîíúþíêöèé, íå

ñîäåðæàùàÿ äâóõ îäèíàêîâûõ êîíúþíêöèé, íàçûâàåòñÿ äèçúþíê-

òèâíîé íîðìàëüíîé ôîðìîé (ÄÍÔ).

Îïðåäåëåíèå 9.9. Äèçúþíêòèâíàÿ íîðìàëüíàÿ ôîðìà, âñå

êîíúþíêöèè êîòîðîé åñòü êîíñòèòóåíòû åäèíèöû, íàçûâàåòñÿ

ñîâåðøåííîé äèçúþíêòèâíîé íîðìàëüíîé ôîðìîé (ÑÄÍÔ).

Îïðåäåëåíèå 9.10. Êîíúþíêöèÿ ýëåìåíòàðíûõ äèçúþíêöèé, íå

ñîäåðæàùàÿ äâóõ îäèíàêîâûõ äèçúþíêöèé, íàçûâàåòñÿ

êîíúþíêòèâíîé íîðìàëüíîé ôîðìîé (ÊÍÔ).

Îïðåäåëåíèå 9.11. Êîíúþíêòèâíàÿ íîðìàëüíàÿ ôîðìà, âñå

äèçúþíêöèè êîòîðîé åñòü êîíñòèòóåíòû íóëÿ, íàçûâàåòñÿ

ñîâåðøåííîé êîíúþíêòèâíîé íîðìàëüíîé ôîðìîé (ÑÊÍÔ).

Òåîðåìà 9.5. Ëþáóþ áóëåâó ôóíêöèþ ìîæíî ïðåäñòàâèòü â âèäå

ÑÄÍÔ è ÑÊÍÔ.

Äîêàçàòåëüñòâî. Ðàññìîòðèì ïðîèçâîëüíóþ áóëåâó ôóíêöèþ

f(x

, x

, ..., x

), íå ÿâëÿþùóþñÿ êîíñòàíòîé. Ïóñòü α

, α

, ..., α



íàáîðû, íà êîòîðûõ ôóíêöèÿ ïðèíèìàåò çíà÷åíèå, ðàâíîå åäèíèöå,

à β

, β

, ..., β

 íàáîðû, íà êîòîðûõ ôóíêöèÿ ðàâíà íóëþ (l=2

k).

Ïîñòðîèì ýëåìåíòàðíûå êîíúþíêöèè K

α1

, ..., x

), K

α2

, ..., x

),,

αk

, ..., x

), êàæäàÿ èç êîòîðûõ ñîäåðæèò âñå n ïåðåìåííûõ è íå

ÿâëÿåòñÿ òîæäåñòâåííî ëîæíîé. Ïîñòðîèì ýòè ýëåìåíòàðíûå

êîíúþíêöèè òàêèì îáðàçîì, ÷òîáû K

α1

ïðèíèìàëà çíà÷åíèå, ðàâíîå

åäèíèöå, íà íàáîðå α

, K

α2

 íà íàáîðå α

è ò. ä. Ñîãëàñíî òåîðåìå

9.3, êàæäàÿ èç ýòèõ êîíúþíêöèé ÿâëÿåòñÿ êîíñòèòóåíòîé åäèíèöû

è íà îñòàëüíûõ íàáîðàõ ïðèíèìàåò çíà÷åíèå, ðàâíîå íóëþ. Ïî

ñâîåìó ïîñòðîåíèþ ñîâîêóïíîñòü âñåõ ýòèõ êîíñòèòóåíò åäèíèöû

îïèñûâàåò âñå åäèíèöû äàííîé ôóíêöèè. Ïîýòîìó èõ äèçúþíêöèÿ

ðàâíîñèëüíà äàííîé ôóíêöèè: f(x

,..., x

)=K

α1

, ..., x

) ∨

∨K

α2

,...,x

) ∨...∨ K

αk

, ..., x

). Ïî îïðåäåëåíèþ 9.9 ïîëó÷åííàÿ

ôîðìóëà ÿâëÿåòñÿ ñîâåðøåííîé äèçúþíêòèâíîé íîðìàëüíîé

ôîðìîé äàííîé ôóíêöèè.

Àíàëîãè÷íî ìîæíî ïîêàçàòü, ÷òî ôîðìóëà A = K

β1

∧ K

β2

∧ ∧K

βl

ÿâëÿþùàÿñÿ êîíúþíêöèåé âñåõ êîíñòèòóåíò íóëÿ, ñîîòâåòñòâóþùèõ

íàáîðàì, íà êîòîðûõ ôóíêöèÿ ðàâíà íóëþ, ðàâíîñèëüíà äàííîé

ôóíêöèè, è ÿâëÿåòñÿ ÑÊÍÔ ôóíêöèè.

Ïðèìåð. Ïóñòü áóëåâà ôóíêöèÿ f(x, y, z) çàäàíà òàáë.9.4. Ïî-

ñòðîèì ÑÄÍÔ è ÑÊÍÔ äàííîé ôóíêöèè.

Òàáëèöà 9.4.

Äëÿ ïîñòðîåíèÿ ÑÄÍÔ áóëåâîé ôóíêöèè íåîáõîäèìî ðàññìîò-

ðåòü âñå íàáîðû, íà êîòîðûõ ôóíêöèÿ ðàâíà åäèíèöå, è îáðàçîâàòü

êîíñòèòóåíòû åäèíèöû, ñîîòâåòñòâóþùèå ýòèì íàáîðàì. Ïîëó-

÷åííûå êîíñòèòóåíòû îáúåäèíèòü çíàêàìè äèçúþíêöèè. Ïîëó÷èì

ÑÄÍÔ: f(x, y, z) = ¬x¬y¬z ∨ ¬xyz ∨ x¬y¬z ∨ x¬yz. Äâîéñòâåííîå

ïðàâèëî ñóùåñòâóåò äëÿ ïîñòðîåíèÿ ÑÊÍÔ. Ðàññìîòðèì âñå

íàáîðû, íà êîòîðûõ áóëåâà ôóíêöèÿ ðàâíà íóëþ. Îáðàçóåì âñå

êîíñòèòóåíòû íóëÿ êàê ýëåìåíòàðíûå äèçúþíêöèè, â êîòîðûõ

êàæäàÿ ïåðåìåííàÿ áåðåòñÿ áåç îòðèöàíèÿ, åñëè îíà ðàâíà íóëþ, è

ñ îòðèöàíèåì, åñëè îíà ðàâíà åäèíèöå â äàííîì íàáîðå. Ñîåäèíèâ

âñå êîíñòèòóåíòû íóëÿ ñèìâîëàìè êîíúþíêöèè, ïîëó÷èì ÑÊÍÔ:

f(x, y, z) = (x∨ y ∨ ¬z)(x ∨ ¬y ∨ z)(¬x ∨ ¬y ∨ z)(¬x ∨¬y∨¬z).

Äðóãîé ñïîñîá çàêëþ÷àåòñÿ â òîì, ÷òî ëþáóþ áóëåâó ôîðìóëó

ìîæíî ïðèâåñòè ê âèäó ÄÍÔ (ÊÍÔ) è ÑÄÍÔ (ÑÊÍÔ) ñ

ïîìîùüþ ýêâèâàëåíòíûõ ïðåîáðàçîâàíèé, èñïîëüçóÿ ñîîòíîøåíèÿ

(9.1)  (9.17).

Ïðèìåð. Ïðèâåäåì ê ÑÄÍÔ ôîðìóëó (x→ y)→xz. Â ñèëó

òîãî, ÷òî x→y = ¬x ∨ y, ïîëó÷èì: (x→y)→xz = ¬(¬x∨y)∨xz=

= x¬y∨ xz. Ïîëó÷åííàÿ ôîðìóëà ïðåäñòàâëåíà â ÄÍÔ, è äëÿ òîãî,

÷òîáû ïîëó÷èòü åå ïðåäñòàâëåíèå â ÑÄÍÔ, «äîìíîæèì» x¬y íà

z∨¬z, è xz  íà y∨¬y. Òîãäà x¬y(z∨¬z)∨xz(y∨¬y)=

=x¬yz∨x¬y¬z∨xyz∨x¬yz. Â ñèëó èäåìïîòåíòíîñòè, x¬yz∨x¬yz=

= x¬yz, ïîýòîìó ÑÄÍÔ åñòü x¬yz∨x¬y¬z∨ xyz.

x 00001111

y 00110011

z 01010101

f(x, y, z)10011100

158 159Áóëåâà àëãåáðàÃëàâà 9

9.5. Àëãåáðà Æåãàëêèíà

Îïðåäåëåíèå 9.12. Ñèñòåìà ýëåìåíòîâ {0,1}, íà êîòîðîé îïðåäå-

ëåíû îïåðàöèè ∧ (êîíúþíêöèÿ) è ⊕ (ñëîæåíèå ïî mod 2), äëÿ

êîòîðûõ âûïîëíÿþòñÿ ñîîòíîøåíèÿ

(9.18) x ⊕ y = y ⊕ x,

(9.19) x (y ⊕ z) = xy ⊕ xz,

(9.20) x ⊕ x = 0,

(9.21) x ⊕ 0 = x,

à òàêæå ñîîòíîøåíèÿ áóëåâîé àëãåáðû (9.3, 9.4, 9.6, 9.7, 9.10,

9.11), îòíîñÿùèåñÿ ê êîíúþíêöèè è êîíñòàíòàì, íàçûâàåòñÿ

àëãåáðîé Æåãàëêèíà.

Èç òàáëèöû èñòèííîñòè îïåðàöèè ñëîæåíèÿ ïî mod 2 ñëåäóåò, ÷òî

(9.22) ¬x = x ⊕ 1.

Îïåðàöèþ äèçúþíêöèè ìîæíî âûðàçèòü ÷åðåç ⊕ è ∧ òàê:

(9.23) x ∨ y = ¬(¬x ¬y) = (x ⊕ 1)(y ⊕ 1) ⊕ 1 = xy ⊕ x ⊕ y.

Îïðåäåëåíèå 9.13. Âñÿêàÿ ôîðìóëà àëãåáðû Æåãàëêèíà, èìåþ-

ùàÿ âèä ñóììû (ïî mod 2) êîíúþíêöèé áóëåâûõ ïåðåìåííûõ,

íàçûâàåòñÿ ïîëèíîìîì Æåãàëêèíà.

Åñëè â êàæäûé ÷ëåí ïîëèíîìà Æåãàëêèíà êàæäàÿ ïåðåìåííàÿ

âõîäèò îäèí ðàç è ïîëèíîì íå ñîäåðæèò îäèíàêîâûõ ÷ëåíîâ, òî

òàêîé ïîëèíîì Æåãàëêèíà íàçûâàåòñÿ êàíîíè÷åñêèì.

Òåîðåìà 9.6. Âñÿêàÿ áóëåâà ôóíêöèÿ åäèíñòâåííûì îáðàçîì

ïðåäñòàâèìà â âèäå êàíîíè÷åñêîãî ïîëèíîìà Æåãàëêèíà.

Äîêàçàòåëüñòâî. Âñÿêóþ áóëåâó ôîðìóëó ìîæíî ïðåäñòàâèòü

â âèäå ïîëèíîìà Æåãàëêèíà, èñïîëüçóÿ ñîîòíîøåíèÿ (9.22), (9.23).

Èç (9.23) ñëåäóåò, ÷òî åñëè äâå ôóíêöèè f

è f

òàêîâû, ÷òî

∧f

=0, òî f

∨f

=f

⊕f

. Îòñþäà ñëåäóåò ïðàâèëî äëÿ ïðåäñòàâ-

ëåíèÿ áóëåâîé ôóíêöèè â âèäå ïîëèíîìà Æåãàëêèíà: äëÿ áóëåâîé

ôîðìóëû, çàäàííîé â âèäå ÑÄÍÔ, äîñòàòî÷íî çàìåíèòü çíàê ∨ íà

çíàê ⊕, ïðåäñòàâèòü îòðèöàíèÿ ïåðåìåííûõ êàê ¬x=x⊕1, ðàñ-

êðûòü ñêîáêè ïî çàêîíó äèñòðèáóòèâíîñòè (9.19) è ïðèâåñòè ïîäîá-

íûå ÷ëåíû ñîãëàñíî (9.20, 9.21).

Ïðèìåð. Ïðèâåäåì ê êàíîíè÷åñêîìó ïîëèíîìó Æåãàëêèíà áóëå-

âó ôóíêöèþ èç ïðåäûäóùåãî ïðèìåðà: f(x, y, z)=x¬yz∨x¬y¬z∨xyz.

Ïîñêîëüêó ôóíêöèÿ íàõîäèòñÿ â ÑÄÍÔ, çàìåíèì ñèìâîëû ∨ íà

⊕, ïîëó÷èì: f(x, y, z)=x¬yz⊕x¬y¬z⊕xyz =x(y⊕1)z⊕x(y⊕

⊕1)(z⊕1)⊕xyz=xyz⊕xz⊕xyz⊕xz⊕xy⊕x⊕xyz=

=xyz⊕xy⊕x.

9.6. Ñâîéñòâà áóëåâûõ ôóíêöèé

Îïðåäåëåíèå 9.14. Ôóíêöèÿ, êîòîðàÿ âûðàçèìà ïîëèíîìîì Æå-

ãàëêèíà âèäà ∑α

⊕ γ, ãäå α

, γ åñòü 0 èëè 1, íàçûâàåòñÿ ëèíåéíîé.

Âñå ôóíêöèè îäíîé ïåðåìåííîé ëèíåéíû. Ëèíåéíûìè ôóíê-

öèÿìè äâóõ ïåðåìåííûõ ÿâëÿþòñÿ x⊕y è x ≡ y: x ≡ y = ¬x¬y∨xy=

= (x⊕1)(y ⊕1)⊕xy = xy ⊕ x⊕ y ⊕1⊕ xy = x⊕y⊕1.

Îïðåäåëåíèå 9.15. Ïóñòü äàíà íåêîòîðàÿ áóëåâà ôîðìóëà A.

Ôîðìóëà A* íàçûâàåòñÿ äâîéñòâåííîé ôîðìóëå A, åñëè îíà ïîëó-

÷àåòñÿ èç A ïóòåì çàìåíû îïåðàöèé êîíúþíêöèè íà äèçú-

þíêöèþ, äèçúþíêöèè íà êîíúþíêöèþ, 1 íà 0, 0 íà 1 âñþäó, ãäå

îíè âõîäÿò.

Íàïðèìåð: A = xy ∨ ¬x¬y; A* = (x ∨ y)(¬x ∨ ¬y).

Òåîðåìà 9.7. Åñëè A(x

,...,x

) è A*(x

,...,x

) - äâå âçàèìíî

äâîéñòâåííûå ôîðìóëû, òî ¬A(x

, ..., x

) = A*(¬x

, ..., ¬x

Äîêàçàòåëüñòâî ñëåäóåò èç çàêîíîâ äå Ìîðãàíà.

Îïðåäåëåíèå 9.16. Ôóíêöèÿ íàçûâàåòñÿ ñàìîäâîéñòâåííîé, åñëè

îíà äâîéñòâåííà ñàìîé ñåáå, ò.å. A(x

, x

,...,x

) = ¬A(¬x

, ¬x

,...,¬x

èëè ¬A(x

, x

, ..., x

) = A(¬x

, ¬x

, ..., ¬x

Äëÿ ñàìîäâîéñòâåííûõ ôóíêöèé îòðèöàíèå åå àðãóìåíòîâ ïðè-

âîäèò ê îòðèöàíèþ ñàìîé ôóíêöèè, ñëåäîâàòåëüíî, ñàìîäâîéñòâåí-

íàÿ ôóíêöèÿ íà ïðîòèâîïîëîæíûõ íàáîðàõ ïðèíèìàåò ïðîòèâî-

ïîëîæíûå çíà÷åíèÿ. Íàïðèìåð, ôóíêöèÿ xy∨xz∨yz ñàìîäâîé-

ñòâåííà. ×òîáû ïîêàçàòü ýòî, âîçüìåì îòðèöàíèÿ îò êàæäîé ïåðå-

ìåííîé è îò âñåé ôóíêöèè:

¬(¬x¬y ∨ ¬x¬z ∨ ¬y¬z) = (x ∨ y)(x ∨ z)(y ∨ z) =

= (x ∨ xy ∨ xz ∨ yz)(y ∨ z) =

= xy ∨ xy ∨ xyz ∨ yz ∨ xz ∨ xyz ∨ xz ∨ yz =

= xy ∨ xz ∨yz.

Ìíîæåñòâî íàáîðîâ áóëåâîé ôóíêöèè

îò n ïåðåìåííûõ ÷àñòè÷íî óïîðÿäî÷åíî è

îáðàçóåò áóëåâó ðåøåòêó 2

. Áóëåâó ôóíê-

öèþ ìîæíî çàäàòü íà ýòîé ðåøåòêå, êàê

ïîêàçàíî íà ðèñ. 9.1, ïðè÷åì ñðåäè áóëå-

âûõ ôóíêöèé ìîæíî âûäåëèòü òàêèå,

êîòîðûå íå óáûâàþò ñ âîçðàñòàíèåì çíà÷å-

íèé íàáîðîâ íà áóëåâîé ðåøåòêå. Òàêèå

ôóíêöèè íàçûâàþòñÿ ìîíîòîííûìè.

Íàïðèìåð, íà ðèñ. 9.1. ïîêàçàíà ìîíî-

òîííàÿ ôóíêöèÿ.

Ðèñ. 9.1.

Ìîíîòîííàÿ ôóíêöèÿ.