Лекции по дискретной математике - БУЛЕВЫ ФУНКЦИИ

ÁÓËÅÂÛ ÔÓÍÊÖÈÈ (Ëåêöèè ïî äèñêðåòíîé ìàòåìàòèêå) Ì.È. Äåõòÿðü

Ñîäåðæàíèå 1 Áóëåâû ôóíêöèè è èõ ïðåäñòàâëåíèÿ 1.1 1.2 1.3 1.4 1.5

Áóëåâû ôóíêöèè îò n ïåðåìåííûõ Ãåîìåòðè÷åñêîå ïðåäñòàâëåíèå . . Òàáëè÷íîå ïðåäñòàâëåíèå . . . . . Ôîðìóëû . . . . . . . . . . . . . . . Çàäà÷è . . . . . . . . . . . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

2 Áóëåâû ôóíêöèè è ëîãèêà âûñêàçûâàíèé 2.1

2

2 3 3 6 8

9

Çàäà÷è . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

3 Ýêâèâàëåíòíîñòü ôîðìóë

13

4 Äèçúþíêòèâíûå è êîíúþíêòèâíûå íîðìàëüíûå ôîðìû

16

3.1 3.2 3.3 4.1 4.2 4.3 4.4

Îñíîâíûå ýêâèâàëåíòíîñòè (òîæäåñòâà) . . . . . . . . . . . . . . . . . . 13 Ýêâèâàëåíòíûå ïðåîáðàçîâàíèÿ ôîðìóë . . . . . . . . . . . . . . . . . . 14 Çàäà÷è . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 Îïðåäåëåíèå ÄÍÔ è ÊÍÔ Ñîâåðøåííûå ÄÍÔ è ÊÍÔ Ñîêðàùåííûå ÄÍÔ . . . . Çàäà÷è . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

16 16 20 22

5 Ìíîãî÷ëåíû Æåãàëêèíà

22

6 Ïîëíûå ñèñòåìû ôóíêöèé è òåîðåìà Ïîñòà

25

5.1 6.1

Çàäà÷è . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 Çàäà÷è . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

1 Áóëåâû ôóíêöèè è èõ ïðåäñòàâëåíèÿ

2

1 Áóëåâû ôóíêöèè è èõ ïðåäñòàâëåíèÿ Áóëåâû ôóíêöèè1 íàçâàíû â ÷åñòü àíãëèéñêîãî ìàòåìàòèêà ÕIÕ âåêà Äæ. Áóëÿ, êîòîðûé âïåðâûå ïðèìåíèë àëãåáðàè÷åñêèå ìåòîäû äëÿ ðåøåíèÿ ëîãè÷åñêèõ çàäà÷. Îíè îáðàçóþò ñàìûé ïðîñòîé íåòðèâèàëüíûé êëàññ äèñêðåòíûõ ôóíêöèé  èõ àðãóìåíòû è çíà÷åíèÿ ìîãóò ïðèíèìàòü âñåãî äâà çíà÷åíèÿ (åñëè ìîùíîñòü ìíîæåñòâà çíà÷åíèé ôóíêöèè ðàâíà 1, òî ýòî òðèâèàëüíàÿ ôóíêöèÿ  êîíñòàíòà !). Ñ äðóãîé ñòîðîíû, ýòîò êëàññ äîñòàòî÷íî áîãàò è åãî ôóíêöèè èìåþò ìíîãî èíòåðåñíûõ ñâîéñòâ.. Áóëåâû ôóíêöèè íàõîäÿò ïðèìåíåíèå â ëîãèêå, ýëåêòðîòåõíèêå, ìíîãèõ ðàçäåëàõ èíôîðìàòèêè.

1.1 Áóëåâû ôóíêöèè îò n ïåðåìåííûõ Îáîçíà÷èì ÷åðåç B äâóõýëåìåíòíîå ìíîæåñòâî {0, 1}. Òîãäà B n = |B × B × {z. . . × B} n

 ýòî ìíîæåñòâî âñåõ äâîè÷íûõ ïîñëåäîâàòåëüíîñòåé (íàáîðîâ, âåêòîðîâ) äëèíû n. Áóëåâîé ôóíêöèåé îò n ïåðåìåííûõ (àðãóìåíòîâ) íàçûâàåòñÿ ëþáàÿ ôóíêöèÿ f (x1 , . . . , xn ) : B n → B . Êàæäûé èç åå àðãóìåíòîâ xi , 1 ≤ i ≤ n, ìîæåò ïðèíèìàòü îäíî èç äâóõ çíà÷åíèé 0 èëè 1 è çíà÷åíèåì ôóíêöèè íà ëþáîì íàáîðå èç B n òàêæå ìîæåò áûòü 0 èëè 1. Îáîçíà÷èì ÷åðåç Pn ìíîæåñòâî âñåõ áóëåâûõ ôóíêöèé îò n ïåðåìåííûõ. Íåòðóäíî ïîäñ÷èòàòü èõ ÷èñëî.

Òåîðåìà 1.1. |Pn | = 22 . n

Äîêàçàòåëüñòâî. Äåéñòâèòåëüíî, ïî òåîðåìå 1.1 èç Ââåäåíèÿ ÷èñëî ôóíêöèé èç k -ýëåìåíòíîãî ìíîæåñòâà A â m-ýëåìåíòíîå ìíîæåñòâî B ðàâíî mk .  íàøåì ñëó÷àå B = {0, 1}, à A = B n . Òîãäà m = 2 è k = |B n | = 2n . Îòñþäà ñëåäóåò óòâåðæäåíèå òåîðåìû. 2 Èìååòñÿ íåñêîëüêî ðàçëè÷íûõ ñïîñîáîâ ïðåäñòàâëåíèÿ è èíòåðïðåòàöèè áóëåâûõ ôóíêöèé.  ýòîì ðàçäåëå ìû ðàññìîòðèì ãåîìåòðè÷åñêîå è òàáëè÷íîå ïðåäñòàâëåíèÿ, à òàêæå ïðåäñòàâëåíèå ñ ïîìîùüþ ëîãè÷åñêèõ ôîðìóë.  ðàçäåëå 4 íà ñòð. 16 áóäåò ïîêàçàíî, êàê áóëåâû ôóíêöèè ìîæíî ïðåäñòàâëÿòü ñ ïîìîùüþ ôîðìóë ñïåöèàëüíîãî âèäà  äèçúþíêòèâíûõ è êîíúþíêòèâíûõ íîðìàëüíûõ ôîðì. Åùå îäíîìó ïðåäñòàâëåíèþ áóëåâûõ ôóíêöèé ñ ïîìîùüþ ñïåöèàëüíûõ ôîðìóë  ìíîãî÷ëåíîâ Æåãàëêèíà  ïîñâÿùåí ðàçäåë 5 íà ñòð. 22. Êðîìå òîãî, â ãëàâå 6 áóäåò ðàññìîòðåíî åùå äâà ñïîñîáà ïðåäñòàâëåíèÿ áóëåâûõ ôóíêöèé: ëîãè÷åñêèå ñõåìû è óïîðÿäî÷åííûå áèíàðíûå äèàãðàììû ðåøåíèé 1Â

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

1.2

1.2

Ãåîìåòðè÷åñêîå ïðåäñòàâëåíèå

3

Ãåîìåòðè÷åñêîå ïðåäñòàâëåíèå

B n ìîæíî ðàññìàòðèâàòü êàê åäèíè÷íûé n-ìåðíûé êóá . Êàæäûé íàáîð èç íóëåé è åäèíèö äëèíû n çàäàåò âåðøèíó ýòîãî êóáà. Íà ñëåäóþùåì ðèñóíêå ïðåäñòàâëåíû åäèíè÷íûå êóáû B n ïðè n = 1, 2, 3, 4. 1111 t 
A 
A 
A  111 1110 1011  t f t t
1101At0111   t

A @ A   
A  @ A
A
 
A A

@ A   101 1010  t f
At
A
t 1100 At0110 11 110 @tf011  1001  t t t
1t
t 0011 @ A  At0101  A 
@ @ @ A
A
 @ @ @ A

A  A
  @
A @tf @
t A A
100  10t t t0100 @t01 t 001 @t010 1000
 0010A A
t 0001 @ @ A
 @ @ A
 @ @ A
 @t 0t @t A
t

B1

002 B

000 B3

0000

B4

Ïðè ýòîì ñóùåñòâóåò åñòåñòâåííîå âçèìíîîäíîçíà÷íîå ñîîòâåòñòâèå ìåæäó ïîäìíîæåñòâàìè âåðøèí n-ìåðíûõ åäèíè÷íûõ êóáîâ è áóëåâûìè ôóíêöèÿìè îò n ïåðåìåííûõ: ïîäìíîæåñòâó A ⊆ B n ñîîòâåòñòâóåò åãî õàðàêòåðèñòè÷åñêàÿ ôóíêöèÿ  1 ïðè (x1 , . . . , xn ) ∈ A fA (x1 , . . . , xn ) = 0 â ïðîòèâíîì ñëó÷àå. Íàïðèìåð, âåðõíåé ãðàíè êóáà B 3 (åå âåðøèíû âûäåëåíû íà ðèñóíêå) ñîîòâåòñòâóåò ôóíêöèÿ f : f (0, 0, 1) = f (0, 1, 1) = f (1, 0, 1) = f (1, 1, 1) = 1 è f (0, 0, 0) = f (0, 1, 0) = f (1, 0, 0) = f (1, 1, 0) = 0. Î÷åâèäíî, ÷òî óêàçàííîå ñîîòâåòñòâèå äåéñòâèòåëüíî âçàèìíîîäíîçíà÷íîå: êàæäàÿ áóëåâàÿ ôóíêöèÿ f îò n ïåðåìåííûõ çàäàåò ïîäìíîæåñòâî Af = {(x1 , . . . , xn ) | f (x1 , . . . , xn ) = 1} âåðøèí B n . Íàïðèìåð, ôóíêöèÿ, òîæäåñòâåííî ðàâíàÿ 0, çàäàåò ïóñòîå ìíîæåñòâî ∅ ⊂ B n , à ôóíêöèÿ, òîæäåñòâåííî ðàâíàÿ 1, çàäàåò ìíîæåñòâî âñåõ âåðøèí B n .

1.3

Òàáëè÷íîå ïðåäñòàâëåíèå

Áóëåâû ôóíêöèè îò íåáîëüøîãî ÷èñëà àðãóìåíòîâ óäîáíî ïðåäñòàâëÿòü ñ ïîìîùüþ òàáëèö. Òàáëèöà äëÿ ôóíêöèè f (x1 , . . . , xn ) èìååò n + 1 ñòîëáåö.  ïåðâûõ n ñòîëáöàõ óêàçûâàþòñÿ çíà÷åíèÿ àðãóìåíòîâ x1 , . . . , xn , à â (n+1)-îì ñòîëáöå çíà÷åíèå ôóíêöèè íà ýòèõ àðãóìåíòàõ  f (x1 , . . . , xn ).

1 Áóëåâû ôóíêöèè è èõ ïðåäñòàâëåíèÿ

4

Òàáëèöà 1: Òàáëè÷íîå ïðåäñòàâëåíèå ôóíêöèè f (x1 , . . . , xn )

x1 0 0 0 . 1

. . . . . .

. . . . . .

. . . . . .

xn−1 0 0 1 . 1

xn 0 1 0 . 1

f (x1 , . . . xn−1 , xn ) f (0, . . . , 0, 0) f (0, . . . , 0, 1) f (0, . . . , 1, 0) ... f (1, . . . , 1, 1)

Íàáîðû àðãóìåíòîâ â ñòðîêàõ îáû÷íî ðàñïîëàãàþòñÿ â ëåêñèêîãðàôè÷åñêîì ïîðÿäêå: (α1 , . . . , αn ) ≺ (β1 , . . . , βn ) ⇔ ñóùåñòâóåò òàêîå i ∈ [1, n], ÷òî ïðè j < i αj = βj , à αi < βi . Åñëè ýòè íàáîðû ðàññìàòðèâàòü êàê çàïèñè ÷èñåë â äâîè÷íîé ñèñòåìå ñ÷èñëåíèÿ, òî 1-àÿ ñòðîêà ïðåäñòàâëÿåò ÷èñëî 0, 2-àÿ  1, 3-ÿ  2, ... , à ïîñëåäíÿÿ  2n − 1. Ïðè áîëüøèõ n òàáëè÷íîå ïðåäñòàâëåíèå ñòàíîâèòñÿ ãðîìîçäêèì, íàïðèìåð, äëÿ ôóíêöèè îò 10 ïåðåìåííûõ ïîòðåáóåòñÿ òàáëèöà ñ 1024 ñòðîêàìè. Íî äëÿ ìàëûõ n îíî äîñòàòî÷íî íàãëÿäíî. Ïðåäñòàâèì â òàáëè÷íîì âèäå âñå áóëåâû ôóíêöèè îò 1-îé ïåðåìåííîé. Òàáëèöà 2: Áóëåâû ôóíêöèè îò 1-îé ïåðåìåííîé

x1 0 1

f1 0 0

f2 1 1

f3 0 1

f4 1 0

 ýòîé òàáëèöå ïðåäñòàâëåíû ñëåäóþùèå ôóíêöèè: 1. f1 (x1 ) = 0  êîíñòàíòà 0; 2. f2 (x1 ) = 1  êîíñòàíòà 1; 3. f3 (x1 ) = x1  òîæäåñòâåííàÿ ôóíêöèÿ; 4. f4 (x1 ) = ¬x1  îòðèöàíèå x1 (èñïîëüçóåòñÿ òàêæå îáîçíà÷åíèå x1 , à â ÿçûêàõ ïðîãðàììèðîâàíèÿ ýòà ôóíêöèÿ ÷àñòî îáîçíà÷àåòñÿ êàê N OT x1 ).  ñëåäóþùåé òàáëèöå ïðåäñòàâëåíû âñå 16 ôóíêöèé îò 2-õ ïåðåìåííûõ. Ìíîãèå èç ýòèõ ôóíêöèé ÷àñòî èñïîëüçóþòñÿ â êà÷åñòâå ýëåìåíòàðíûõ è èìåþò ñîáñòâåííûå îáîçíà÷åíèÿ.

1.3

x1 0 0 1 1

Òàáëè÷íîå ïðåäñòàâëåíèå

x2 0 1 0 1

f1 0 0 0 0

f2 1 1 1 1

5

Òàáëèöà 3: Áóëåâû ôóíêöèè îò 2-õ ïåðåìåííîé

f3 0 0 1 1

f4 1 1 0 0

f5 0 1 0 1

f6 1 0 1 0

f7 0 0 0 1

f8 0 1 1 1

f9 1 1 0 1

f10 0 1 1 0

f11 1 0 0 1

f12 1 1 1 0

f13 1 0 0 0

f14 0 1 0 0

f15 0 0 1 0

f16 1 0 1 1

1. f1 (x1 , x2 ) = 0  êîíñòàíòà 0; 2. f2 (x1 , x2 ) = 1  êîíñòàíòà 1; 3. f3 (x1 , x2 ) = x1  ôóíêöèÿ, ðàâíàÿ 1-ìó àðãóìåíòó ; 4. f4 (x1 , x2 ) = ¬x1  îòðèöàíèå x1 ; 5. f5 (x1 , x2 ) = x2  ôóíêöèÿ, ðàâíàÿ 2-ìó àðãóìåíòó ; 6. f6 (x1 , x2 ) = ¬x2  îòðèöàíèå x2 ; 7. f7 (x1 , x2 ) = (x1 ∧ x2 )  êîíúþíêöèÿ, ÷èòàåòñÿ  x1 è x2  (èñïîëüçóþòñÿ òàêæå îáîçíà÷åíèÿ (x1 &x2 ), (x1 x2 ), min(x1 , x2 ) è (x1 AND x2 )); 8. f8 (x1 , x2 ) = (x1 ∨ x2 )  Äèçúþíêöèÿ, ÷èòàåòñÿ  x1 èëè x2  (èñïîëüçóþòñÿ òàêæå îáîçíà÷åíèÿ (x1 + x2 ), max(x1 x2 ) è (x1 OR x2 )); 9. f9 (x1 , x2 ) = (x1 → x2 )  èìïëèêàöèÿ, ÷èòàåòñÿ  x1 âëå÷åò x2  èëè èç x1 ñëåäóåò x2  (èñïîëüçóþòñÿ òàêæå îáîçíà÷åíèÿ (x1 ⊃ x2 ), è ( IF x1 THEN x2 ) ); 10. f10 (x1 , x2 ) = (x1 + x2 )  ñëîæåíèå ïî ìîäóëþ 2, ÷èòàåòñÿ  x1 ïëþñ x2  (èñïîëüçóåòñÿ òàêæå îáîçíà÷åíèå (x1 ⊕ x2 )); 11. f11 (x1 , x2 ) = (x1 ∼ x2 )  ýêâèâàëåíòíîñòü, ÷èòàåòñÿ  x1 ýêâèâàëåíòíî (ðàâíîñèëüíî) x2  (èñïîëüçóåòñÿ òàêæå îáîçíà÷åíèå (x1 ≡ x2 ) ); 12. f12 (x1 , x2 ) = (x1 |x2 )  øòðèõ Øåôôåðà (àíòèêîíúþíêöèÿ), èíîãäà ÷èòàåòñÿ êàê íå x1 è x2 ; 13. f13 (x1 , x2 ) = (x1 ↓ x2 )  ñòðåëêà Ïèðñà (àíòèäèçúþíêöèÿ), èíîãäà ÷èòàåòñÿ êàê íå x1 èëè x2 .  êà÷åñòâå ýëåìåíòàðíûõ ôóíêöèé áóäåì òàêæå ðàññìàòðèâàòü 0-ìåñòíûå ôóíêöèèêîíñòàíòû 0 è 1. Îòìåòèì, ÷òî ôóíêöèè f1 (x1 , x2 ) è f2 (x1 , x2 ) ôàêòè÷åñêè íå çàâèñÿò îò çíà÷åíèé îáîèõ àðãóìåíòîâ, ôóíêöèè f3 (x1 , x2 ) è f4 (x1 , x2 ) íå çàâèñÿò îò çíà÷åíèé àðãóìåíòà x2 , à ôóíêöèè f5 (x1 , x2 ) è f6 (x1 , x2 ) íå çàâèñÿò îò çíà÷åíèé àðãóìåíòà x1 .

6

1 Áóëåâû ôóíêöèè è èõ ïðåäñòàâëåíèÿ

Îïðåäåëåíèå 1.1. Ôóíêöèÿ f (x1 , . . . , xi , . . . , xn ) íå çàâèñèò îò àðãóìåíòà xi , åñëè

äëÿ ëþáîãî íàáîðà çíà÷åíèé σ1 , . . . , σi−1 , σi+1 , . . . , σn îñòàëüíûõ àðãóìåíòîâ f èìååò ìåñòî ðàâåíñòâî f (σ1 , . . . , σi−1 , 0, σi+1 , . . . , σn ) = f (σ1 , . . . , σi−1 , 1, σi+1 , . . . , σn ). Òàêîé àðãóìåíò xi íàçûâàåòñÿ ôèêòèâíûìè. Àðãóìåíòû, íå ÿâëÿþùèåñÿ ôèêòèâíûìè, íàçûâàþòñÿ ñóùåñòâåííûìè. Ôóíêöèè f1 (x1 , . . . , xn ) è f2 (x1 , . . . , xm ) íàçûâàþòñÿ ðàâíûìè, åñëè ôóíêöèþ f2 ìîæíî ïîëó÷èòü èç ôóíêöèè f1 ïóòåì äîáàâëåíèÿ è óäàëåíèÿ ôèêòèâíûõ àðãóìåíòîâ. Íàïðèìåð, ðàâíûìè ÿâëÿþòñÿ îäíîìåñòíàÿ ôóíêöèÿ f3 (x1 ) è äâóõìåñòíàÿ ôóíêöèÿ f3 (x1 , x2 ), òàê êàê âòîðàÿ ïîëó÷àåòñÿ èç ïåðâîé äîáàâëåíèåì ôèêòèâíîãî àðãóìåíòà x2 . Ìû íå áóäåì ðàçëè÷àòü ðàâíûå ôóíêöèè è, êàê ïðàâèëî, áóäåì èñïîëüçîâàòü äëÿ îáîçíà÷åíèÿ ðàâíûõ ôóíêöèé îäíî è òî æå èìÿ ôóíêöèè.  ÷àñòíîñòè, ýòî ïîçâîëÿåò ñ÷èòàòü, ÷òî âî âñÿêîì êîíå÷íîì ìíîæåñòâå ôóíêöèé âñå ôóíêöèè çàâèñÿò îò îäíîãî è òîãî æå ìíîæåñòâà ïåðåìåííûõ.

1.4 Ôîðìóëû Êàê ìû âèäåëè, ãåîìåòðè÷åñêîå è òàáëè÷íîå ïðåäñòàâëåíèÿ áóëåâûõ ôóíêöèé ïîäõîäÿò ëèøü äëÿ ôóíêöèé ñ íåáîëüøèì ÷èñëîì àðãóìåíòîâ. Ôîðìóëû ïîçâîëÿþò, óäîáíî ïðåäñòàâëÿòü ìíîãèå ôóíêöèè îò áîëüøåãî ÷èñëà àðãóìåíòîâ è îïåðèðîâàòü ðàçëè÷íûìè ïðåäñòàâëåíèÿìè îäíîé è òîé æå ôóíêöèè. Ïóñòü B  íåêîòîðîå (êîíå÷íîå èëè áåñêîíå÷íîå) ìíîæåñòâî áóëåâûõ ôóíêöèé. Çàôèêñèðóåì íåêîòîðîå ñ÷åòíîå ìíîæåñòâî ïåðåìåííûõ V = {X1 , X2 , . . .}. Îïðåäåëèì ïî èíäóêöèè ìíîæåñòâî ôîðìóë íàä B ñ ïåðåìåííûìè èç V . Îäíîâðåìåííî áóäåì îïðåäåëÿòü ÷èñëîâóþ õàðàêòåðèñòèêó dep(Φ) ôîðìóëû Φ, íàçûâàåìóþ åå ãëóáèíîé è ìíîæåñòâî åå ïîäôîðìóë.

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

à) Áàçèñ èíäóêöèè. Êàæäàÿ ïåðåìåííàÿ Xi ∈ V è êàæäàÿ êîíñòàíòà c ∈ B ÿâëÿåòñÿ ôîðìóëîé ãëóáèíû 0, ò.å. dep(Xi ) = dep(c) = 0. Ìíîæåñòâî åå ïîäôîðìóë ñîñòîèò èç íåå ñàìîé. á) Øàã èíäóêöèè. Ïóñòü f (x1 , . . . , xm ) ∈ B è A1 , . . . , Am  ôîðìóëû, è max{dep(Ai ) | i = 1, . . . , m} = k . Òîãäà âûðàæåíèå Φ = f (A1 , . . . , Am ) ÿâëÿåòñÿ ôîðìóëîé, åå ãëóáèíà dep(Φ) ðàâíà k + 1, à ìíîæåñòâî ïîäôîðìóë Φ âêëþ÷àåò ñàìó ôîðìóëó Φ è âñå ïîäôîðìóëû ôîðìóë A1 , . . . , Am . Êàæäîé ôîðìóëå Φ(X1 , . . . , Xn ) ñîïîñòàâèì áóëåâó ôóíêöèþ, êîòîðóþ ýòà ôîðìóëà çàäàåò, èñïîëüçóÿ èíäóêöèþ ïî ãëóáèíå ôîðìóëû. Áàçèñ èíäóêöèè. Ïóñòü dep(Φ) = 0. Òîãäà Φ = Xi ∈ V èëè Φ = c ∈ B  ïåðâîì ñëó÷àå

1.4 Ôîðìóëû

7

Φ çàäàåò ôóíêöèþ fΦ (Xi ) = Xi , âî âòîðîì  ôóíêöèþ, òîæäåñòâåííî ðàâíóþ c. Øàã èíäóêöèè. Ïóñòü Φ  ïðîèçâîëüíàÿ ôîðìóëà ãëóáèíû dep(Φ) = k + 1. Òîãäà Φ(X1 , . . . , Xn ) = fi (A1 , . . . , Am ), ãäå fi ∈ B è A1 , . . . , Am  ôîðìóëû, äëÿ êîòîðûõ max1≤i≤m {dep(Ai )} = k . Ïðåäïîëîæèì (ïî èíäóêöèè), ÷òî ýòèì ôîðìóëàì óæå ñîïîñòàâëåíû ôóíêöèè g1 (X1 , . . . , Xn ), . . . , gm (X1 , . . . , Xn ). Òîãäà ôîðìóëà Φ çàäàåò ôóíêöèþ fΦ (X1 , . . . , Xn ) = fi (g1 (X1 , . . . , Xn ), . . . , gm (X1 , . . . , Xn )). Äàëåå ìû áóäåì ðàññìàòðèâàòü ôîðìóëû íàä ìíîæåñòâîì ýëåìåíòàðíûõ ôóíêöèé Be = {0, 1, ¬, ∧, ∨, →, +, ∼, |, ↓}. Âñå ýòè ôóíêöèè, êðîìå êîíñòàíò, íàçûâàþòñÿ ëîãè÷åñêèìè ñâÿçêàìè èëè ëîãè÷åñêèìè îïåðàöèÿìè. Ïðè ýòîì äëÿ 2-ìåñòíûõ ôóíêöèé èç ýòîãî ñïèñêà áóäåì èñïîëüçîâàòü èíôèêñíóþ çàïèñü, â êîòîðîé èìÿ ëîãè÷åñêîé ñâÿçêè ïîìåùàåòñÿ ìåæäó 1-ûì è 2-ûì àðãóìåíòàìè. Òîãäà îïðåäåëåíèå ôîðìóëû íàä Be èìååò ñëåäóþùèé âèä.

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

à) Áàçèñ èíäóêöèè. 0, 1 è êàæäàÿ ïåðåìåííàÿ Xi ∈ V ÿâëÿþòñÿ ôîðìóëàìè ãëóáèíû 0. á) Øàã èíäóêöèè. Ïóñòü Φ1 è Φ2  ôîðìóëû, ◦ ∈ {∧, ∨, →, +, ∼, |, ↓}. Òîãäà âûðàæåíèÿ ¬Φ1 è (Φ1 ◦ Φ2 ) ÿâëÿþòñÿ ôîðìóëàìè. Ïðè ýòîì dep(¬Φ1 ) = 1 + dep(Φ1 ), à dep((Φ1 ◦ Φ2 )) = 1 + max{dep(Φ1 ), dep(Φ2 )}.  ñîîòâåòñòâèè ñ ýòèì îïðåäåëåíèåì âûðàæåíèÿ Φ1 (X1 , X2 ) = ¬(X1 ∧ ¬X2 ) è Φ2 (X1 , X2 , X3 ) = ((X1 ∨¬¬X2 ) → (X3 ∼ (X1 ↓ ¬X2 ))) ÿâëÿþòñÿ ôîðìóëàìè. Ãëóáèíà Φ1 ðàâíà 3, à ãëóáèíà Φ2 ðàâíà 4. Âûðàæåíèÿ æå ¬X1 + (¬X2 ∨ X3 ), (X1 ¬ ∧ X2 ) è (X1 + X2 + X3 ) ôîðìóëàìè íå ÿâëÿþòñÿ (ïî÷åìó? ). Äëÿ îïðåäåëåíèÿ ôóíêöèè, çàäàâàåìîé ôîðìóëîé, óäîáíî èñïîëüçîâàòü òàáëèöó, ñòðîêè êîòîðîé ñîòâåòñòâóþò íàáîðàì çíà÷åíèé ïåðåìåííûõ, à â ñòîëáöå ïîä çíàêîì êàæäîé ëîãè÷åñêîé ñâÿçêè ñòîÿò çíà÷åíèÿ ôóíêöèè, çàäàâàåìîé ñîîòâåòñòâóþùåé ïîäôîðìóëîé. Íàïðèìåð, äëÿ ôîðìóëû Φ2 ôóíêöèÿ fΦ2 çàäàåòñÿ âûäåëåííûì ñòîëáöîì → ñëåäóþùåé òàáëèöû.

Òàáëèöà 4: Ôóíêöèÿ fΦ2 X1 0 0 0 0 1 1 1 1

X2 0 0 1 1 0 0 1 1

X3 0 1 0 1 0 1 0 1

((X1 0 0 0 0 1 1 1 1

∨ 0 0 1 1 1 1 1 1

¬ 0 0 1 1 0 0 1 1

¬ 1 1 0 0 1 1 0 0

X2 ) 0 0 1 1 0 0 1 1

→ 1 1 0 1 1 0 1 0

(X3 0 1 0 1 0 1 0 1

∼ 1 0 0 1 1 0 1 0

(X1 0 0 0 0 1 1 1 1

↓ 0 0 1 1 0 0 0 0

¬ 1 1 0 0 1 1 0 0

X2 ))) 0 0 1 1 0 0 1 1

8

1 Áóëåâû ôóíêöèè è èõ ïðåäñòàâëåíèÿ

1.5 Çàäà÷è Çàäà÷à 1.1. Êàêèå ïîäìíîæåñòâà âåðøèí B 4 ñîîòâåòñòâóþò ñëåäóþùèì áóëåâûì ôóíêöèÿì: à) f1 (x1 , x2 , x3 , x4 ) = 1 ⇔ á) f2 (x1 , x2 , x3 , x4 ) = 1 ⇔ â) f3 (x1 , x2 , x3 , x4 ) = 1 ⇔ ã) f4 (x1 , x2 , x3 , x4 ) = 1 ⇔

x1 = 0 ; x4 = 1 ; x1 + x2 ≥ x3 + x4 (çäåñü + - àðèôìåòè÷åñêîå ñëîæåíèå); x1 x2 = 0 èëè x3 x4 = 1.

Çàäà÷à 1.2. Ïîñòðîèòü òàáëèöû çíà÷åíèé äëÿ ñëåäóþùèõ áóëåâûõ ôóíêöèé:

à) f1 (X1 , X2 , X3 ) = 1 ⇔ X1 + X3 ≥ X2 ; á) f2 (X1 , X2 , X3 ) = 1 ⇔ ñóììà (X1 + X2 + X3 ) ÷åòíà; â) f3 (X1 , X2 , X3 ) = 0 ⇔ çíà÷åíèå X1 ñîâïàäàåò ñî çíà÷åíèåì X2 èëè ñî çíà÷åíèåì X3 . ã) f4 (X1 , X2 , X3 ) = åñëè X1 = 1, òî X2 , èíà÷å X3 .

Çàäà÷à 1.3. Ïîñòðîèòü òàáëèöû äëÿ ôóíêöèé, çàäàâàåìûõ ñëåäóþùèìè ôîðìóëà-

ìè: à) Ψ1 = ((X1 → ¬X3 ) ∨ (X2 + X3 )); á) Ψ2 = (¬(X1 | X2 ) ∼ (¬X1 ∧ X2 )); â) Ψ3 = ((X2 + ¬X3 ) ∧ ((X1 ∨ X2 ) → (X1 ∼ ¬X3 ))).

Çàäà÷à 1.4. Íàçîâåì äâà íàáîðà α = (α1 , . . . , αn ) ∈ B n è β = (β1 , . . . , βn ) ∈ B n

ñîñåäíèìè, åñëè îíè íàõîäÿòñÿ â ñîñåäíèõ ñòðîêàõ òàáëèöû äëÿ ôóíêöèè îò n ïåðåìåííûõ, ò.å. ïðåäñòàâëÿþò äâîè÷íûå çàïèñè ÷èñåë iα è iβ , äëÿ êîòîðûõ |iα − iβ | = 1. Íàéòè ÷èñëî ôóíêöèé â Pn , êîòîðûå íà ëþáîé ïàðå ñîñåäíèõ íàáîðîâ ïðèíèìàþò à) îäèíàêîâûå çíà÷åíèÿ; á) ðàçíûå çíà÷åíèÿ.

Çàäà÷à 1.5. Íàçîâåì äâà íàáîðà α = (α1 , . . . , αn ) ∈ B n è β = (β1 , . . . , βn ) ∈ B n

ïðîòèâîïîëîæíûìè, åñëè äëÿ âñÿêîãî i αi = 1 ⇔ βi = 0 (è, ñëåäîâàòåëüíî, αi = 0 ⇔ βi = 1). Íàéòè ÷èñëî ôóíêöèé â Pn , êîòîðûå íà ëþáîé ïàðå ïðîòèâîïîëîæíûõ íàáîðîâ ïðèíèìàþò ðàçíûå çíà÷åíèÿ.

Çàäà÷à 1.6. Ïóñòü n = 2k . Íàçîâåì íàáîð α = (α1 , . . . , αn ) ∈ B n ïàðíûì, åñëè äëÿ ëþáîãî i = 1, . . . , k αi = α2i , ò.å. α = α0 α0 äëÿ íåêîòîðîãî íàáîðà α0 ðàçìåðà k . Íàéòè ÷èñëî ôóíêöèé â Pn , êîòîðûå íà âñåõ ïàðíûõ íàáîðàõ ïðèíèìàþò îäèíàêîâîå çíà÷åíèå.

9

2 Áóëåâû ôóíêöèè è ëîãèêà âûñêàçûâàíèé Êàê ìû óæå îòìåòèëè, Äæ. Áóëü ââåë áóëåâû ôóíêöèè äëÿ ðåøåíèÿ ëîãè÷åñêèõ çàäà÷.  ëîãèêå ïîä âûñêàçûâàíèåì ïîíèìàþò íåêîòîðîå ïîâåñòâîâàòåëüíîå ïðåäëîæåíèå, îòíîñèòåëüíî êîòîðîãî ìîæíî ñêàçàòü, èñòèííî îíî èëè ëîæíî. Ëîãèêà âûñêàçûâàíèé çàíèìàåòñÿ âûÿñíåíèåì èñòèííîñòè òåõ èëè èíûõ âûñêàçûâàíèé, ñâÿçüþ ìåæäó èñòèííîñòüþ ðàçëè÷íûõ âûñêàçûâàíèé è ò.ï. Áóëåâû ôóíêöèè ìîãóò ñëóæèòü ïîëåçíûì èíñòðóìåíòîì ïðè ðåøåíèè ìíîãèõ ëîãè÷åñêèõ çàäà÷. Êàæäóþ ïåðåìåííóþ ìîæíî ðàññìàòðèâàòü êàê íåêîòîðîå ýëåìåíòàðíîå âûñêàçûâàíèå, ïðèíèìàþùåå îäíî èç äâóõ çíà÷åíèé: 1 (èñòèíà) èëè 0 (ëîæü). Ñëîæíûì âûñêàçûâàíèÿì ñîîîòâåòñòâóþò ôîðìóëû, ïîñòðîåííûå èç ýëåìåíòàðíûõ âûñêàçûâàíèé ñ ïîìîùüþ ëîãè÷åñêèõ ñâÿçîê. Âû÷èñëÿÿ çíà÷åíèÿ çàäàâàåìûõ èìè ôóíêöèé, ìîæíî óñòàíàâëèâàòü çàâèñèìîñòè èñòèííîñòíûõ çíà÷åíèé ñëîæíûõ âûñêàçûâàíèé îò çíà÷åíèé âõîäÿùèõ â íèõ ýëåìåíòàðíûõ âûñêàçûâàíèé. Ðàññìîòðèì ñëåäóþùèé ïðèìåð.

Ïðèìåð 2.1. Ïóñòü èçâåñòíî, ÷òî â äîðîæíîì ïðîèøåñòâèè ó÷àñòâîâàëè òðè

àâòîìîáèëÿ ñ âîäèòåëÿìè A, B è C . Ñâèäåòåëè ïðîèøåñòâèÿ äàëè ñëåäóþùèå ïîêàçàíèÿ: 1-ûé ñâèäåòåëü: åñëè A âèíîâåí, òî èç îñòàëüíûõ B è C õîòü îäèí íå âèíîâåí; 2-îé ñâèäåòåëü: åñëè C íå âèíîâåí, òî âèíîâåí êòî-òî îäèí èç ïàðû A, B íî íå îáà âìåñòå; 3-èé ñâèäåòåëü: â ñòîëêíîâåíèè âèíîâíû íå ìåíåå äâóõ âîäèòåëåé. Ìîæíî ëè íà îñíîâàíèè ýòèõ ïîêàçàíèé ñäåëàòü âûâîä, ÷òî C ÿâëÿåòñÿ âèíîâíèêîì ïðîèøåñòâèÿ? Ìîæíî ëè îäíîçíà÷íî îïðåäåëèòü âòîðîãî âèíîâíèêà? Äëÿ îòâåòà íà ýòè âîïðîñû ââåäåì òðè ïåðåìåííûõ, ñîîòâåòñòâóþùèõ ñëåäóþùèì âûñêàçûâàíèÿì: X1 :  âèíîâåí A , X2 :  âèíîâåí B  è X3 :  âèíîâåí C . Òîãäà ïîêàçàíèÿ 1-ãî ñâèäåòåëÿ îïèñûâàþòñÿ ôîðìóëîé Φ1 = (X1 → (¬X2 ∨ ¬X3 )), ïîêàçàíèÿ 2-ãî ñâèäåòåëÿ  Φ2 = (¬X3 → ((X1 ∨ X2 ) ∧ ¬(X1 ∧ X2 ))), à 3-ãî ñâèäåòåëÿ  Φ3 = ((X1 ∧ X2 ) ∨ ((X1 ∧ X3 ) ∨ (X2 ∧ X3 ))). Ïîêàçàíèÿì âñåõ òðåõ ñâèäåòåëåé ñîîòâåòñòâóåò êîíúþíêöèÿ ýòèõ ôîðìóë Ψ = (Φ1 ∧ (Φ2 ∧ Φ3 )). Ñîñòàâèì òàáëèöû çíà÷åíèé äëÿ ôóíêöèé fΦi (i = 1, 2, 3) , à çàòåì  äëÿ fΨ .

2 Áóëåâû ôóíêöèè è ëîãèêà âûñêàçûâàíèé

10

Òàáëèöà 5: Ôóíêöèÿ fΦ1 X1 0 0 0 0 1 1 1 1

X2 0 0 1 1 0 0 1 1

X3 0 1 0 1 0 1 0 1

(X1 0 0 0 0 1 1 1 1

→

1 1 1 1 1 1 1 0

(¬ 1 1 0 0 1 1 0 0

X2 0 0 1 1 0 0 1 1

∨ 1 1 1 0 1 1 1 0

¬ 1 0 1 0 1 0 1 0

X3 )) 0 1 0 1 0 1 0 1

¬ 1 1 1 1 1 1 0 0

(X1 0 0 0 0 1 1 1 1

Òàáëèöà 6: Ôóíêöèÿ fΦ2 X1 0 0 0 0 1 1 1 1

X2 0 0 1 1 0 0 1 1

X3 0 1 0 1 0 1 0 1

(¬ 1 0 1 0 1 0 1 0

X3 0 1 0 1 0 1 0 1

→

0 1 1 1 1 1 0 1

((X1 0 0 0 0 1 1 1 1

∨ 0 0 1 1 1 1 1 1

X2 ) 0 0 1 1 0 0 1 1

∧ 0 0 1 1 1 1 0 0

∧ 0 0 0 0 0 0 1 1

X2 ))) 0 0 1 1 0 0 1 1

Èç ýòîé òàáëèöû ñëåäóåò, ÷òî fΨ (X1 , X2 , X3 ) = 1 íà äâóõ íàáîðàõ: (X1 = 0, X2 = 1, X3 = 1) è (X1 = 1, X2 = 0, X3 = 1) (ñòðîêè ñ ýòèìè íàáîðàìè ïîä÷åðêíóòû). Ïîñêîëüêó â îáîèõ ñëó÷àÿõ X3 = 1, ìîæíî ñäåëàòü âûâîä, ÷òî Ñ ÿâëÿåòñÿ îäíèì èç âèíîâíèêîâ ïðîèøåñòâèÿ. Îäíîçíà÷íî îïðåäåëèòü âòîðîãî âèíîâíèêà ïîëó÷åííàÿ îò ñâèäåòåëåé èíôîðìàöèÿ íå ïîçâîëÿåò, òàê êàê â îäíîì ñëó÷àå èì ÿâëÿåòñÿ À, à â äðóãîì  Â. Âàæíóþ ðîëü â ëîãèêå èãðàþò ïîíÿòèÿ òîæäåñòâåííî èñòèííîé è âûïîëíèìîé ôîðìóëû.

Îïðåäåëåíèå 2.1. Áóëåâà ôîðìóëà Φ íàçûâàåòñÿ òîæäåñòâåííî èñòèííîé, åñëè

îíà èñòèííà ïðè ëþáûõ çíà÷åíèÿõ âõîäÿùèõ â íåå ïåðåìåííûõ, ò.å. ôóíêöèÿ fΦ òîæäåñòâåííî ðàâíà 1. Áóëåâà ôîðìóëà Φ íàçûâàåòñÿ âûïîëíèìîé, åñëè ñóùåñòâóåò òàêîé íàáîð çíà÷åíèé ïåðåìåííûõ, íà êîòîðîì îíà èñòèííà, ò.å. ôóíêöèÿ fΦ ðàâíà 1 õîòü íà îäíîì íàáîðå àðãóìåíòîâ.

11 Òàáëèöà 7: Ôóíêöèÿ fΦ3 X1 0 0 0 0 1 1 1 1

X2 0 0 1 1 0 0 1 1

X3 0 1 0 1 0 1 0 1

((X1 0 0 0 0 1 1 1 1

∧ 0 0 0 0 0 0 1 1

X2 ) 0 0 1 1 0 0 1 1

∨

0 0 0 1 0 1 1 1

((X1 0 0 0 0 1 1 1 1

∧ 0 0 0 0 0 1 0 1

X3 ) 0 1 0 1 0 1 0 1

∨ 0 0 0 1 0 1 0 1

(X2 0 0 1 1 0 0 1 1

∧ 0 0 0 1 0 0 0 1

X3 ))) 0 1 0 1 0 1 0 1

Òàáëèöà 8: Ôóíêöèÿ fΨ X1 0 0 0 0 1 1 1 1

X2 0 0 1 1 0 0 1 1

X3 0 1 0 1 0 1 0 1

(Φ1 1 1 1 1 1 1 1 0

∧

0 0 0 1 0 1 0 0

(Φ2 0 1 1 1 1 1 0 1

∧ 0 0 0 1 0 1 0 1

Φ3 )) 0 0 0 1 0 1 1 1

Êàê ïðîâåðèòü òîæäåñòâåííóþ èñòèííîñòü èëè âûïîëíèìîñòü ôîðìóëû Φ? Íà ïåðâûé âçãëÿä êàæåòñÿ, ÷òî îòâåò ïðîñò  ïîñòðîèì ïî Φ òàáëèöó äëÿ ôóíêöèè fΦ è, åñëè â ñòîëáöå çíà÷åíèé ñòîÿò òîëüêî åäèíèöû, òî çàêëþ÷àåì, ÷òî Φ òîæäåñòâåííî èñòèííà, åñëè òàì åñòü õîòü îäíà åäèíèöà, òî Φ âûïîëíèìà. Ê ñîæàëåíèþ, ýòîò ñïîñîá ïðèãîäåí òîëüêî äëÿ ôîðìóë ñ íåáîëüøèì ÷èñëîì ïåðåìåííûõ. Óæå äëÿ íåñêîëüêèõ äåñÿòêîâ è ñîòåí ïåðåìåííûõ îí íå ãîäèòñÿ èç-çà áîëüøîãî ðàçìåðà ïîëó÷àþùåéñÿ òàáëèöû  íåòðóäíî ïîäñ÷èòàòü, ÷òî ÷èñëî 290 ïðåâîñõîäèò êîëè÷åñòâî àòîìîâ âî âñåé âèäèìîé âñåëåííîé.  ìàòåìàòè÷åñêîé ëîãèêå ïîñòðîåíû àêñèîìàòè÷åñêèå ñèñòåìû, ïîçâîëÿþùèå ôîðìàëèçîâàòü ÷åëîâå÷åñêèå ðàññóæäåíèÿ î âûâîäèìîñòè îäíèõ òîæäåñòâåííî èñòèííûõ ôîðìóë èç äðóãèõ  íåêîòîðûõ ñëó÷àÿõ îíè ïîçâîëÿþò äîêàçàòü òîæäåñòâåííóþ èñòèííîñòü äîñòàòî÷íî äëèííûõ ôîðìóë, èìåþùèõ ðåãóëÿðíóþ ñòðóêòóðó. Íî â îáùåì ñëó÷àå è îíè ïðàêòè÷åñêè íå ïðèìåíèìû äëÿ ïðîèçâîëüíûõ ôîðìóë ñ áîëüøèì ÷èñëîì ïåðåìåííûõ.  òåîðèè ñëîæíîñòè àëãîðèòìîâ èìååòñÿ ðÿä ðåçóëüòàòîâ (îíè âûõîäÿò çà ðàì-

12

2 Áóëåâû ôóíêöèè è ëîãèêà âûñêàçûâàíèé

êè íàøåãî êóðñà), êîòîðûå ñâèäåòåëüñòâóþò î òîì, ÷òî ýôôåêòèâíûõ àëãîðèòìîâ äëÿ ïðîâåðêè âûïîëíèìîñòè èëè òîæäåñòâåííîé èñòèííîñòè ïðîèçâîëüíîé áóëåâîé ôîðìóëû íå ñóùåñòâóåò. Âìåñòå ñ òåì äëÿ íåêîòîðûõ ïîäêëàññîâ ôîðìóë ýòè çàäà÷è ðåøàþòñÿ äîñòàòî÷íî ýôôåêòèâíî. Îäèí òàêîé ïîäêëàññ  Õîðíîâñêèå ôîðìóëû  áóäåò ðàññìîòðåí äàëåå â ãëàâå 3.

2.1 Çàäà÷è Çàäà÷à 2.1. Àäìèíèñòðàòîð áàçû äàííûõ îáíàðóæèë, ÷òî îäíà èëè íåñêîëüêî èç

òðåõ çàïèñåé åãî áàçû: A, B è C îøèáî÷íà. Îí óñòàíîâèë, ÷òî à) åñëè çàïèñü B êîððåêòíà, òî A îøèáî÷íà; á) õîòÿ áû îäíà çàïèñü èç ïàðû B, C êîððåêòíà è õîòÿ áû îäíà çàïèñü èç ïàðû A, C êîððåêòíà; â) åñëè A îøèáî÷íà, òî õîòÿ îäíà èç çàïèñåé B, C êîððåêòíà (íî íå îáå âìåñòå). Îïèøèòå çíàíèÿ àäìèíèñòðàòîðà â âèäå áóëåâîé ôîðìóëû. Ìîæåò ëè îí ñäåëàòü âûâîä, ÷òî çàïèñü B îøèáî÷íà? Ìîæíî ëè äîñòîâåðíî óòâåðæäàòü, ÷òî îøèáî÷íàÿ çàïèñü åäèíñòâåííà?

Çàäà÷à 2.2. Ïðîãðàììèñò Ïåòð èñïîëüçîâàë â ñâîåé ïðîãðàììå òðè öåëî÷èñëåí-

íûå ïåðåìåííûå x, y è z . Â îïðåäåëåííîì ìåñòå ïðîãðàììû îí ïîìåñòèë óñëîâíûé îïåðàòîð: IF (x ∗ y ≥ 0) OR (x ∗ z ≥ 0) THEN x = 1 ELSE x = 2; Ïðîàíàëèçèðîâàâ ñâîþ ïðîãðàììó Ïåòð óñòàíîâèë, ÷òî ïåðåä âûïîëíåíèåì ýòîãî îïåðàòîðà âûïîëíåíû ñëåäóþùèå óñëîâèÿ: à) åñëè z < 0, òî x < 0 èëè y ≥ 0; á) x ≥ 0 èëè y < 0; â) åñëè y < 0 , òî õîòÿ áû îäíà èç ïåðåìåííûõ x, z îòðèöàòåëüíà, íî íå îáå âìåñòå. Îïèøèòå çíàíèÿ Ïåòðà â âèäå áóëåâîé ôîðìóëû. Ìîæåò ëè îí îïòèìèçèðîâàòü ïðîãðàììó, çàìåíèâ óêàçàííûé óñëîâíûé îïåðàòîð íà ïðèñâîåíèå x = 1 èëè íà ïðèñâîåíèå x = 2? Åñëè äà, òî íà êàêîå?

Çàäà÷à 2.3. Êîìèòåò ñîñòîèò èç ïÿòè ÷ëåíîâ. Ðåøåíèÿ ïðèíèìàþòñÿ áîëü-

øèíñòâîì ãîëîñîâ, îäíàêî, åñëè ïðåäñåäàòåëü ãîëîñóåò ïðîòèâ, òî ðåøåíèå íå ïðèíèìàåòñÿ. Ïîñòðîéòå ôîðìóëó, çàâèñÿùóþ îò 5 ïåðåìåííûõ X1 , X2 , X3 , X4 , Y (Xi = 1 ⇔ i-ûé ÷ëåí êîìèòåòà ãîëîñóåò çà, Y = 1 ⇔ ïðåäñåäàòåëü çà), çíà÷åíèå êîòîðîé ðàâíî 1 òîãäà è òîëüêî òîãäà, êîãäà â ðåçóëüòàòå ãîëîñîâàíèÿ ðåøåíèå ïðèíèìàåòñÿ.

13

3 Ýêâèâàëåíòíîñòü ôîðìóë Îïðåäåëåíèå 3.1. Áóëåâû ôîðìóëû Φ è Ψ íàçûâàþòñÿ ýêâèâàëåíòíûìè, åñëè ñî-

îòâåòñòâóþùèå èì ôóíêöèè fΦ è fΨ ðàâíû. Îáîçíà÷åíèå: Φ ≡ Ψ.

3.1 Îñíîâíûå ýêâèâàëåíòíîñòè (òîæäåñòâà) Ïóñòü ◦ - ýòî îäíà èç ôóíêöèé ∧, ∨, +. Äëÿ ýòèõ òðåõ ôóíêöèé âûïîëíåíû ñëåäóþùèå äâå ýêâèâàëåíòíîñòè (çàêîíû àññîöèàòèâíîñòè è êîììóòàòèâíîñòè). (1) Àññîöèàòèâíîñòü:

((X1 ◦ X2 ) ◦ X3 ) ≡ (X1 ◦ (X2 ◦ X3 )) (2) Êîììóòàòèâíîñòü:

(X1 ◦ X2 ) ≡ (X2 ◦ X1 )) (3) Äèñòðèáóòèâíûå çàêîíû:

((X1 ∨ X2 ) ∧ X3 ) ≡ ((X1 ∧ X3 ) ∨ (X2 ∧ X3 )) ((X1 ∧ X2 ) ∨ X3 ) ≡ ((X1 ∨ X3 ) ∧ (X2 ∨ X3 )) ((X1 + X2 ) ∧ X3 ) ≡ ((X1 ∧ X3 ) + (X2 ∧ X3 )) (4) Äâîéíîå îòðèöàíèå:

¬(¬X) ≡ X (5)Çàêîíû äå Ìîðãàíà (âíåñåíèå îòðèöàíèÿ âíóòðü ñêîáîê):

¬(X1 ∨ X2 ) ≡ (¬X1 ∧ ¬X2 ) ¬(X1 ∧ X2 ) ≡ (¬X1 ∨ ¬X2 ) (6) Çàêîíû óïðîùåíèÿ:

(X ∧ X) ≡ X

(X ∨ X) ≡ X

(X ∧ ¬X) ≡ 0

(X ∨ ¬X) ≡ 1

(X ∧ 0) ≡ 0

(X ∨ 0) ≡ X

(X ∧ 1) ≡ X

(X ∨ 1) ≡ 1

Íåêîòîðûå çàêîíû óïðîùåíèÿ èìåþò ñîáñòâåííûå íàçâàíèÿ: ýêâèâàëåíòíîñòè â ïåðâîé ñòðîêå íàçûâàþòñÿ çàêîíàìè èäåìïîòåíòíîñòè, (X ∧ ¬X) ≡ 0  ýòî çàêîí

3 Ýêâèâàëåíòíîñòü ôîðìóë

14

ïðîòèâîðå÷èÿ, (X ∨ ¬X) ≡ 1  ýòî çàêîí èñêëþ÷åííîãî òðåòüåãî. Ýêâèâàëåíòíîñòè â äâóõ ïîñëåäíèõ ñòðîêàõ èíîãäà íàçûâàþò çàêîíàìè 0 è 1. Ñëåäóþùèå äâå ýêâèâàëåíòíîñòè ïîçâîëÿþò âûðàçèòü èìïëèêàöèþ è ñëîæåíèå ïî ìîäóëþ 2 ÷åðåç äèçúþíêöèþ, êîíúþêöèþ è îòðèöàíèå. (7) (X1 → X2 ) ≡ (¬X1 ∨ X2 ) (8) (X1 + X2 ) ≡ ((X1 ∧ ¬X2 ) ∨ (¬X1 ∧ X2 )) Ïðîâåðêà ïðàâèëüíîñòè ýòèõ ýêâèâàëåíòíîñòåé îñòàâëÿåòñÿ ÷èòàòåëÿì (ñì. çàäà÷ó 3.1 íà ñòð. 15).

3.2 Ýêâèâàëåíòíûå ïðåîáðàçîâàíèÿ ôîðìóë Ñîãëàøåíèÿ îá óïðîùåííîé çàïèñè ôîðìóë. 1. Çàêîíû àññîöèàòèâíîñòè ïîêàçûâàþò, ÷òî çíà÷åíèÿ ôîðìóë, ñîñòàâëåííûõ èç ïåðåìåííûõ è îäíèõ îïåðàöèé êîíúþíêöèè, íå çàâèñÿò îò ðàññòàíîâêè ñêîáîê. Ïîýòîìó âìåñòî ôîðìóë (X1 ∧ X2 ) ∧ X3 ) è (X1 ∧ (X2 ∧ X3 )) ìû áóäåì äëÿ óïðîùåíèÿ ïèñàòü âûðàæåíèå (X1 ∧X2 ∧X3 ), êîòîðîå íå ÿâëÿåòñÿ ôîðìóëîé, íî ìîæåò áûòü ïðåâðàùåíî â íåå ñ ïîìîùüþ ðàññòàíîâêè ñêîáîê. Àíàëîãè÷íî, áóäåì èñïîëüçîâàòü âûðàæåíèÿ (X1 ∨ X2 ∨ X3 ) è (X1 + X2 + X3 ) äëÿ ñîêðàùåíèÿ ôîðìóë, ñîñòîÿùèõ èç îäíèõ äèçúþíêöèé èëè îäíèõ ñëîæåíèé ïî ìîäóëþ 2, ñîîòâåòñòâåííî. 2. Åñëè âíåøíåé ôóíêöèåé â ôîðìóëå ÿâëÿåòñÿ îäíà èç ôóíêöèé ∧, ∨, +, →, òî âíåøíèå ñêîáêè â çàïèñè ôîðìóëû ìîæíî îïóñòèòü. Òàêèì îáðàçîì, ñ èñïîëüçîâàíèåì ýòèõ ñîãëàøåíèé ôîðìóëà (((X ∨ Y ) ∨ (Z ∧ ¬X)) → ((Y + Z) + ¬X)) ìîæåò áûòü çàïèñàíà êàê (X ∨ Y ∨ (Z ∧ ¬X)) → (Y + Z + ¬X). Èç îïðåäåëåíèÿ ýêâèâàëåíòíîñòè ôîðìóë íåïîñðåäñòâåííî ñëåäóåò

Ïðèíöèï çàìåíû ýêâèâàëåíòíûõ ïîäôîðìóë:

ïóñòü ôîðìóëà α ÿâëÿåòñÿ ïîäôîðìóëîé ôîðìóëû Φ, ôîðìóëà α0 ýêâèâàëåíòíà α è ôîðìóëà Φ0 ïîëó÷åíà èç Φ ïîñðåäñòâîì çàìåíû íåêîòîðîãî âõîæäåíèÿ α íà α0 . Òîãäà Φ0 ýêâèâàëåíòíà Φ, ò.å. Φ0 ≡ Φ. Ïðèìåíÿÿ ýòîò ïðèíöèï è èñïîëüçóÿ îñíîâíûå òîæäåñòâà, ìîæíî íàõîäèòü äëÿ çàäàííîé ôîðìóëû äðóãèå ýêâèâàëåíòíûå åé ôîðìóëû. ×àñòî ýòî ìîæåò ïðèâîäèòü ê ñóùåñòâåííîìó óïðîùåíèþ èñõîäíîé ôîðìóëû. Íàïðèìåð, åñëè â ôîðìóëå ((X ∧ 0) ∨ Y ) çàìåíèì íà îñíîâàíèè òîæäåñòâ (6) ïîäôîðìóëó (X ∧ 0) íà 0, òî ïîëó÷èì ýêâèâàëåíòíóþ ôîðìóëó (0 ∨ Y ). Ïî çàêîíó êîììóòàòèâíîñòè (2) ýòà ôîðìóëà ýêâèâàëåíòíà ôîðìóëå (Y ∨0), êîòîðàÿ, â ñâîþ î÷åðåäü, ïî îäíîìó èç òîæäåñòâ ãðóïïû (6) ýêâèâàëåíòíà ôîðìóëå Y . Ýòó öåïî÷êó ýêâèâàëåíòíûõ ïðåîáðàçîâàíèé ìîæíî çàïèñàòü òàêæå ñëåäóþùèì îáðàçîì: ((X ∧ 0) ∨ Y ) ≡ (0 ∨ Y ) ≡ (Y ∨ 0) ≡ Y . (6)

(2)

(6)

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

3.3 Çàäà÷è

15

ïîìîùüþ êàêîé ãðóïïû îñíîâíûõ òîæäåñòâ ýòà ýêâèâàëåíòíîñòü ïîëó÷àåòñÿ. Âûâåäåì åùå íåñêîëüêî âàæíûõ ëîãè÷åñêèõ òîæäåñòâ, ïîçâîëÿþùèõ ïðîâîäèòü óïðîùåíèÿ ñëîæíûõ ôîðìóë. Èõ íàçûâàþò çàêîíû ïîãëîùåíèÿ. Ï1) X ∨ (X ∧ Φ)≡X Äåéñòâèòåëüíî, X ∨ (X ∧ Φ) ≡ (X ∧ 1) ∨ (X ∧ Φ) ≡ X ∧ (1 ∨ Φ) ≡ X ∧ 1 ≡ X (6)

(3)

(2,6)

(6)

Ï2) (X ∧ Φ) ∨ (¬X ∧ Φ)≡Φ Äåéñòâèòåëüíî, (X ∧ Φ) ∨ (¬X ∧ Φ) ≡ (X ∨ ¬X) ∧ Φ ≡ 1 ∧ Φ ≡ Φ (3)

(6)

(6)

Ï3) (X1 ∧ X2 ) ∨ (¬X1 ∧ X3 ) ∨ (X2 ∧ X3 )≡(X1 ∧ X2 ) ∨ (¬X1 ∧ X3 ) Äåéñòâèòåëüíî, (X1 ∧ X2 ) ∨ (¬X1 ∧ X3 )∨ (X2 ∧ X3 ) ≡ (X1 ∧ X2 ) ∨ (¬X1 ∧ X3 ) ∨ (X1 ∨ (2,6)

¬X1 ) ∧ (X2 ∧ X3 ) ≡ ((X1 ∧ X2 ) ∨ (X1 ∧ X2 ∧ X3 ))∨ ((¬X1 ∧ X2 ) ∨ (¬X1 ∧ X2 ∧ X3 )) ≡ (3,2)

(3)

((X1 ∧ X2 ) ∧ (1 ∨ X3 ))∨ ((¬X1 ∧ X2 ) ∧ (1 ∨ X3 )) ≡ ((X1 ∧ X2 ) ∧ 1)∨ ((¬X1 ∧ X2 ) ∧ 1) ≡ (6)

(6)

(X1 ∧ X2 ) ∨ (¬X1 ∧ X3 )

3.3 Çàäà÷è Çàäà÷à 3.1. Ïðîâåðüòå âñå âûøåïðèâåäåííûå ýêâèâàëåíòíîñòè (1) - (8), íåïîñðåäñòâåííî âû÷èñëÿÿ ôóíêöèè, ïðåäñòàâëÿåìûå èõ ëåâûìè è ïðàâûìè ÷àñòÿìè.

Çàäà÷à 3.2. Íàçîâåì ëîãè÷åñêèì ïðîèçâåäåíèåì ôîðìóëó âèäà Φ1 ∧ Φ2 ∧ . . . ∧ Φn (â ýòîì âûðàæåíèè èñïîëüçîâàíû ñîãëàøåíèÿ î ñîêðàùåíèè çàïèñè!). Åå ïîäôîðìóëû Φi , 1 ≤ i ≤ n, , áóäåì íàçûâàòü ñîìíîæèòåëÿìè. Àíàëîãè÷íî, ëîãè÷åñêîé ñóììîé íàçîâåì ôîðìóëó âèäà Φ1 ∨ Φ2 ∨ . . . ∨ Φn . Åå ïîäôîðìóëû Φi , 1 ≤ i ≤ n, , áóäåì íàçûâàòü ñëàãàåìûìè. Ïîêàæèòå, ÷òî èç îñíîâíûõ òîæäåñòâ ìîæíî âûâåñòè ñëåäóþùèå ïðàâèëà ïðåîáðàçîâàíèÿ ëîãè÷åñêèõ ïðîèçâåäåíèé è ñóìì. Ñ1) Åñëè â ëîãè÷åñêîì ïðîèçâåäåíèè îäèí èç ñîìíîæèòåëåé ðàâåí 0, òî è âñå ïðîèçâåäåíèå ðàâíî 0. Ñ2) Åñëè â ëîãè÷åñêîé ñóììå îäíî èç ñëàãàåìûõ ðàâíî 1, òî è âñÿ ñóììà ðàâíà 1. Ñ3) Åñëè â ëîãè÷åñêîì ïðîèçâåäåíèè n ≥ 2 è åñòü ñîìíîæèòåëü, ðàâíûé 1, òî åãî ìîæíî âû÷åðêíóòü. Ñ4) Åñëè â ëîãè÷åñêîé ñóììå n ≥ 2 è åñòü ñëàãàåìîå, ðàâíîå 0, òî åãî ìîæíî âû÷åðêíóòü.

Çàäà÷à 3.3. Èñïîëüçóÿ îñíîâíûå òîæäåñòâà, äîêàçàòü ýêâèâàëåíòíîñòü ñëåäóþ-

ùèõ ïàð ôîðìóë. (a) ¬(X ∨ ¬Y ) ∧ (X → ¬Y ) è (¬X ∧ Y ); (b) ¬[(X ∧ ¬Y ) → (¬X ∨ Z)] è (X ∧ ¬Y ∧ ¬Z); (c) (X + Y ) → (X ∧ ¬Y ) è (¬X ∧ ¬Y ) ∨ X .

16

4

Äèçúþíêòèâíûå è êîíúþíêòèâíûå íîðìàëüíûå ôîðìû

4 Äèçúþíêòèâíûå è êîíúþíêòèâíûå íîðìàëüíûå ôîðìû 4.1 Îïðåäåëåíèå ÄÍÔ è ÊÍÔ Â ýòîì ðàçäåëå ìû èíòåðåñóåìñÿ ïðåäñòàâëåíèåì ïðîèçâîëüíîé áóëåâîé ôóíêöèè ïîñðåäñòâîì ôîðìóë ñïåöèàëüíîãî âèäà, èñïîëüçóþùèõ òîëüêî îïåðàöèè ∧, ∨ è ¬. Ïóñòü X = {X1 , . . . , Xn } - ýòî ìíîæåñòâî ïðîïîçèöèîíàëüíûõ ïåðåìåííûõ. Ââåäåì äëÿ êàæäîãî i = 1, ..., n îáîçíà÷åíèÿ: Xi0 = ¬Xi è Xi1 = Xi . Ôîðìóëà Xiσ11 ∧ Xiσ22 ∧ . . . ∧ Xiσkk (Xiσ11 ∨ Xiσ22 ∨ . . . ∨ Xiσkk ), â êîòîðîé σij ∈ {0, 1} è âñå ïåðåìåííûå ðàçíûå, ò.å. Xij 6= Xir ïðè j 6= r, íàçûâàåòñÿ ýëåìåíòàðíîé êîíúþíêöèåé (ýëåìåíòàðíîé äèçúþíêöèåé).

Îïðåäåëåíèå 4.1. Ôîðìóëà D íàçûâàåòñÿ äèçúþíêòèâíîé íîðìàëüíîé ôîðìîé (ÄÍÔ), åñëè îíà ÿâëÿåòñÿ äèçúþíêöèåé ýëåìåíòàðíûõ êîíúþíêöèé, ò.å. èìååò âèä D = K1 ∨ K2 ∨ . . . ∨ Kr , ãäå êàæäàÿ ôîðìóëà Kj (j = 1, ..., r) - ýòî ýëåìåíòàðíàÿ êîíúþíêöèÿ. D íàçûâàåòñÿ ñîâåðøåííîé ÄÍÔ, åñëè â êàæäóþ èç åå êîíúþíêöèé Kj âõîäÿò âñå n ïåðåìåííûõ èç X. Àíàëîãè÷íî, ôîðìóëà C íàçûâàåòñÿ êîíúþíêòèâíîé íîðìàëüíîé ôîðìîé (ÊÍÔ), åñëè îíà ÿâëÿåòñÿ êîíúþíêöèåé ýëåìåíòàðíûõ äèçúþíêöèé, ò.å. C = D1 ∨ D2 ∨ . . . ∨ Dr , ãäå êàæäàÿ ôîðìóëà Dj (j = 1, ..., r) ýòî ýëåìåíòàðíàÿ äèçúþíêöèÿ. Îíà ÿâëÿåòñÿ ñîâåðøåííîé ÊÍÔ,åñëè â êàæäóþ Dj âõîäÿò âñå n ïåðåìåííûõ èç X.

4.2 Ñîâåðøåííûå ÄÍÔ è ÊÍÔ Ðàññìîòðèì ïðîèçâîëüíóþ áóëåâó ôóíêöèþ f (X1 , . . . , Xn ), çàâèñÿùóþ îò ïåðåìåííûõ èç X. Oáîçíà÷èì ÷åðåç Nf+ ìíîæåñòâî íàáîðîâ çíà÷åíèé ïåðåìåííûõ, íà êîòîðûõ f ïðèíèìàåò çíà÷åíèå 1, à ÷åðåç Nf− ìíîæåñòâî íàáîðîâ, íà êîòîðûõ f ïðèíèìàåò çíà÷åíèå 0, ò.å. Nf+ = {(σ1 , . . . , σn ) | f (σ1 , . . . , σn ) = 1} è Nf− = {(σ1 , . . . , σn ) | f (σ1 , . . . , σn ) = 0}. Îïðåäåëèì ïî ýòèì ìíîæåñòâàì äâå ôîðìóëû: _ Df = X1σ1 ∧ X2σ2 ∧ . . . ∧ Xnσn (σ1 ,...,σn )∈Nf+

è

Cf =

^

(X1¬σ1 ∨ X2¬σ2 ∨ . . . ∨ Xn¬σn )

(σ1 ,...,σn )∈Nf−

Òåîðåìà 4.1. (1) Åñëè ôóíêöèÿ f íå ðàâíà òîæäåñòâåííî 0, òî ôîðìóëà Df - ýòî ñîâåðøåííàÿ ÄÍÔ, çàäàþùàÿ ôóíêöèþ f . (2) Åñëè ôóíêöèÿ f íå ðàâíà òîæäåñòâåííî 1, òî ôîðìóëà Cf - ýòî ñîâåðøåííàÿ ÊÍÔ, çàäàþùàÿ ôóíêöèþ f .

4.2 Ñîâåðøåííûå ÄÍÔ è ÊÍÔ

17

Äîêàçàòåëüñòâî ïîëó÷àåòñÿ íåïîñðåäñòâåííûì âû÷èñëåíèåì çíà÷åíèÿ êàæäîé èç óêàçàííûõ ôîðìóë ñ ó÷åòîì òîãî, ÷òî äëÿ ëþáîãî σ ∈ {0, 1} èìåþò ìåñòî ðàâåíñòâà: 1σ = σ è 0σ = ¬σ ( ñì. çàäà÷ó 4.1 íà ñòð. 22).

Ñëåäñòâèå 4.1.1. Êàæäàÿ áóëåâà ôóíêöèÿ ìîæåò áûòü çàäàíà ôîðìóëîé, ñîäåðæàùåé ïåðåìåííûå è ôóíêöèè êîíúþíêöèè, äèçúþíêöèè è îòðèöàíèÿ.

Ïðèâåäåííûå âûøå ôîðìóëû äëÿ Df è Cf ïîçâîëÿþò ýôôåêòèâíî ñòðîèòü ñîâåðøåííûå ÄÍÔ è ÊÍÔ ïî òàáëè÷íîìó ïðåäñòàâëåíèþ ôóíêöèè f (Êàêèì îáðàçîì?). Ìîæíî ëè ïîëó÷èòü òàêèå ñïåöèàëüíûå ïðåäñòàâëåíèÿ ïî ïðîèçâîëüíîé ôîðìóëå, çàäàþùåé f , íå âûïèñûâàÿ åå ïîëíîé òàáëèöû? Ïðèâîäèìàÿ íèæå ïðîöåäóðà ïîçâîëÿåò ýòî ñäåëàòü, èñïîëüçóÿ îñíîâíûå ýêâèâàëåíòíîñòè ôîðìóë. Ïðîöåäóðà Ïðèâåäåíèå ê ñîâåðøåííîé ÄÍÔ Âõîä: ôîðìóëà Φ, âêëþ÷àþùàÿ ôóíêöèè ¬, ∧, ∨, → è +. (1) Èñïîëüçóÿ ýêâèâàëåíòíîñòü (7), çàìåíèòü âñå âõîæäåíèÿ ôóíêöèè → â Φ íà ¬, ∧ è ∨, çàòåì èñïîëüçîâàòü ýêâèâàëåíòíîñòü (8) äëÿ çàìåíû âñåõ âõîæäåíèé ôóíêöèè + íà ¬, ∧ è ∨. (2) Èñïîëüçóÿ çàêîíû äå Ìîðãàíà (5) è ñíÿòèÿ äâîéíîãî îòðèöàíèÿ (4), âíåñòè âñå çíàêè îòðèöàíèÿ âíóòðü ñêîáîê òàê, ÷òîáû âñå îñòàâøèåñÿ îòðèöàíèÿ íàõîäèëèñü íåïîñðåäñòâåííî ïåðåä ïåðåìåííûìè. (3) Ïîëó÷èâøàÿñÿ ïîñëå øàãà (2) ôîðìóëà Φ0 èìååò îäíó èç äâóõ ôîðì: (à) Φ0 = Φ1 ∧ Φ2 èëè (á) Φ0 = Φ1 ∨ Φ2 . Ïîñêîëüêó êàæäàÿ èç ôîðìóë Φ1 , Φ2 èìååò ìåíüøóþ ãëóáèíó ÷åì ôîðìóëà Φ0 , òî ïðåäïîëîæèì ïî èíäóêöèè, ÷òî äëÿ íèõ óæå ïîñòðîåíû ýêâèâàëåíòíûå ÄÍÔ D1 = K11 ∨ K12 ∨ . . . ∨ K1r è D2 = K21 ∨ K22 ∨ . . . ∨ K2s , ñîîòâåòñòâåííî. Òîãäà â ñëó÷àå (à) èìååì: 0 Φ ≡ (K11 ∨ . . . ∨ K1r ) ∧ (K21 ∨ . . . ∨ K2s ) ≡ (K11 ∧ K21 ) ∨ . . . ∨ (K1i ∧ K2j ) ∨ . . . ∨ (K1r ∧ K2s ). (3)

(K1i ∧ K2j )

Êàæäûé ÷ëåí ýòîé äèçúþíêöèè ïðåäñòàâëÿåò ñîáîé êîíúþíêöèþ ïåðåìåííûõ è èõ îòðèöàíèé. Ïðèìåíÿÿ ýêâèâàëåíòíîñòè ãðóïï (1), (2) è (6), ìîæíî óäàëèòü èç íåå ïîâòîðåíèÿ ïåðåìåííûõ, ïîñëå ÷åãî îíà ïðåâðàòèòñÿ â íåêîòîðóþ ýëåìåíòàðíóþ êîíúþíêöèþ èëè êîíñòàíòó. Ïðîäåëàâ òàêèå ïðåîáðàçîâàíèÿ ñî âñåìè ïàðàìè (i, j), 1 ≤ i ≤ r, 1 ≤ j ≤ s, è óäàëèâ, åñëè ïîòðåáóåòñÿ, êîíñòàíòû 0, ìû ïîëó÷èì ÄÍÔ, ýêâèâàëåíòíóþ èñõîäíîé ôîðìóëå Φ.  ñëó÷àå (á) ôîðìóëà Φ0 ≡ (K11 ∨ K12 ∨ . . . ∨ K1r ) ∨ (K21 ∨ K22 ∨ . . . ∨ K2s ) ñàìà óæå ÿâëÿåòñÿ ÄÍÔ. (4) Èñïîëüçóÿ ýêâèâàëåíòíîñòè ãðóïï (1), (2) è (6) óäàëèòü èç ïîëó÷èâøåéñÿ ïîñëå øàãà (3) ôîðìóëû ïîâòîðíûå âõîæäåíèÿ îäèíàêîâûõ êîíúþíêöèé. (5) Ïóñòü ïîñëå øàãà (4) ïîëó÷èëàñü ÄÍÔ Φ00 = K1 ∨ K2 ∨ . . . ∨ Km . ×òîáû ïîëó÷èòü ýêâèâàëåíòíóþ ñîâåðøåííóþ ÄÍÔ, ïîñòðîèì äëÿ êàæäîé Ki , (i = 1, . . . , m) ýêâè-

18

4

Äèçúþíêòèâíûå è êîíúþíêòèâíûå íîðìàëüíûå ôîðìû

âàëåíòíóþ ñîâåðøåííóþ ÄÍÔ (ñì. çàäà÷ó 4.2 íà ñòð. 22) , çàìåíèì åþ Ki , à çàòåì óñòðàíèì ïîâòîðåíèÿ îäèíàêîâûõ êîíúþíêöèé. Èç ôîðìóëèðîâîê ýêâèâàëåíòíîñòåé (7) è (8) íåïîñðåäñòâåííî âûòåêàåò

Ïðåäëîæåíèå 4.1. Íà ýòàïå (1) ïðîöåäóðû ïðè ïîñëåäîâàòåëüíîì âûïîëíåíèè ïðåîáðàçîâàíèé (7), à çàòåì (8) äî òåõ ïîð, ïîêà íè îäíî èç íèõ íå ïðèìåíèìî, ïîëó÷åííàÿ â ðåçóëüòàòå ôîðìóëà íå áóäåò ñîäåðæàòü ôóíêöèé → è +. Äîêàçàòåëüñòâî ýòîãî ïðåäëîæåíèÿ îñòàâëÿåì â âèäå óïðàæíåíèÿ (ñì. çàäà÷ó 4.4 íà ñòð. 22). Ñëåäóþùåå óòâåðæäåíèå ãàðàíòèðóåò êîððåêòíîñòü ýòàïà (2).

Ïðåäëîæåíèå 4.2. Íà ýòàïå (2) ïðîöåäóðû ïðè ëþáîì ïîðÿäêå âûïîëíåíèÿ ïðåîáðàçîâàíèé ãðóïï (4) è (5) äî òåõ ïîð, ïîêà íè îäíî èç íèõ íå ïðèìåíèìî, â ïîëó÷åííîé â ðåçóëüòàòå ôîðìóëå âñå çíàêè îòðèöàíèÿ áóäóò ñòîÿòü íåïîñðåäñòâåííî ïåðåä ïåðåìåííûìè.

Ïåðåä äîêàçàòåëüñòâîì ýòîãî óòâåðæäåíèÿ ââåäåì íåêîòîðûå îáîçíà÷åíèÿ. Íàïîìíèì, ÷òî â îïðåäåëåíèÿõ 1.2 íà ñòð. 6 è 1.3 íà ñòð. 7 äëÿ êàæäîé ôîðìóëû Φ áûëà îïðåäåëåíà åå ãëóáèíà dep(Φ). Íàïðèìåð, ôîðìóëà Φ = ¬(X +Y ) → (¬(X ∨¬Z)∧Y ), ïîñòðîåííàÿ íàä ñèñòåìîé F = {∨, ∧, ¬, →, +}, èìååò ãëóáèíó dep(Φ) = 5. Ïóñòü Φ - ýòî ôîðìóëà íàä F = {∨, ∧, ¬}. Îïðåäåëèì äëÿ êàæäîé åå îòðèöàòåëüíîé ïîäôîðìóëû âèäà ¬(Ψ) âûñîòó h(¬(Ψ)) êàê 3dep(Ψ) − 1. È ïóñòü âûñîòà âñåé ôîðìóëû H(Φ) ðàâíà ñóììå âûñîò âñåõ åå îòðèöàòåëüíûõ ïîäôîðìóë. Íàïðèìåð, äëÿ ïðèâåäåííîé âûøå ôîðìóëû Φ åå âûñîòà ðàâíà H(Φ) = h(¬(X + Y )) + h(¬(X ∨ ¬Z)) + h(¬Z) = (31 − 1) + (32 − 1) + (30 − 1) = 10. Äîêàçàòåëüñòâî ïðåäëîæåíèÿ 4.2 ïðîâåäåì èíäóêöèåé ïî âûñîòå ôîðìóë. Áàçèñ èíäóêöèè. Åñëè H(Φ) = 0, òî ëèáî â Φ íåò îòðèöàíèé, ëèáî âñå îòðèöàíèÿ íàõîäÿòñÿ íåïîñðåäñòâåííî ïåðåä ïåðåìåííûìè. Ñëåäîâàòåëüíî, Φ óäîâëåòâîðÿåò òðåáîâàíèþ ïðåäëîæåíèÿ 4.2. Øàã èíäóêöèè. Ïðåäïîëîæèì, ÷òî ïðè n ≤ k äëÿ âñåõ ôîðìóë âûñîòû n Ïðåäëîæåíèå 4.2 âûïîëíåíî. Ïóñòü Φ - ïðîèçâîëüíàÿ ôîðìóëà âûñîòû H(Φ) = k + 1. Äîêàæåì íàøå óòâåðæäåíèå äëÿ íåå. Ïîñêîëüêó H(Φ) ≥ 1, òî Φ ñîäåðæèò õîòÿ áû îäíó îòðèöàòåëüíóþ ïîäôîðìóëó ¬(Ψ), ó êîòîðîé h(¬(Ψ)) ≥ 1 è, ñëåäîâàòåëüíî, dep(Ψ) ≥ 1. Ê òàêîé ôîðìóëå îáÿçàòåëüíî ìîæíî ïðèìåíèòü ëèáî ñíÿòèå äâîéíîãî îòðèöàíèÿ (4), ëèáî îäèí èç çàêîíîâ äå Ìîðãàíà (5). (Îáúÿñíèòå ïî÷åìó ? ) Ïóñòü ¬(Ψ) - ýòî òà ïîäôîðìóëà Φ, êîòîðàÿ íà (2)-îì ýòàïå ïðîöåäóðû ïåðâîé çàìåíÿåòñÿ íà ýêâèâàëåíòíóþ ôîðìóëó Ψ0 â ñîîòâåòñòâèè ñ îäíîé èç óêàçàííûõ ýêâèâàëåíòíîñòåé. Ïóñòü Φ0 - ýòî ôîðìóëà, ïîëó÷èâøàÿñÿ â ðåçóëüòàòå ýòîé çàìåíû èç Φ. Íåòðóäíî ïðîâåðèòü ( ïðîäåëàéòå ýòó ïðîâåðêó! ), ÷òî ïðè ëþáîì èç ïðåîáðàçîâàíèé (4), (5) H(Ψ0 ) < H(¬(Ψ)) è, ñëåäîâàòåëüíî, H(Φ0 ) < H(Φ). Òîãäà, H(Φ0 ) ≤ k è ïî ïðåäïîëîæåíèþ èíäóêöèè ïðèìåíåíèå ýêâèâàëåíòíîñòåé (4), (5) â ïðîèçâîëüíîì ïîðÿäêå ïðèâåäåò â êîíöå êîíöîâ

4.2 Ñîâåðøåííûå ÄÍÔ è ÊÍÔ

19

ê ôîðìóëå, ó êîòîðîé âñå îòðèöàíèÿ áóäóò ñòîÿòü íåïîñðåäñòâåííî ïåðåä ïåðåìåííûìè. Ýòî îçíà÷àåò, ÷òî ïðåäëîæåíèå 4.2 âûïîëíåíî ïðè n = k + 1, ÷òî çàâåðøàåò èíäóêöèîííûé øàã è âñå äîêàçàòåëüñòâî. Ðàññìîòðèì ïðèìåíåíèå ïðîöåäóðû ïðèâåäåíèÿ ê ñîâåðøåííîé ÄÍÔ íà ïðèìåðå.

Ïðèìåð 4.1. Ïóñòü ôîðìóëà Φ = ((¬X ∨ Z) → (Y → (X + Z))). Íà (1)-îì ýòàïå ïðîöåäóðû ïîëó÷àåì ñëåäóþùóþ öåïî÷êó ýêâèâàëåíòíîñòåé: Φ ≡ ¬(¬X ∨ Z) ∨ (Y → (X + Z)) ≡ ¬(¬X ∨ Z) ∨ (¬Y ∨ (X + Z)) ≡ ¬(¬X ∨ Z) ∨ (¬Y ∨ (7)

(7)

(8)

((X ∧ ¬Z) ∨ (¬X ∧ Z))). Íà (2)-îì ýòàïå âíîñèì îòðèöàíèå âíóòðü ïåðâîé ñêîáêè è ïîëó÷àåì ôîðìóëó Φ0 = (¬¬X ∧ ¬Z) ∨ (¬Y ∨ ((X ∧ ¬Z) ∨ (¬X ∧ Z))). Óñòðàíèâ äâîéíîå îòðèöàíèå, ïîëó÷èì Φ00 = (X ∧ ¬Z) ∨ (¬Y ∨ ((X ∧ ¬Z) ∨ (¬X ∧ Z))). Íåòðóäíî âèäåòü, ÷òî ýòî óæå ÄÍÔ. Óäàëèì íà (4)-îì ýòàïå ïîâòîðíîå âõîæäåíèå ïåðâîé êîíúíêöèè è ïîëó÷èì ÄÍÔ Φ1 = (X ∧ ¬Z) ∨ ¬Y ∨ (¬X ∧ Z). Ýòà ÄÍÔ íå ÿâëÿåòñÿ ñîâåðøåííîé, òàê êàê â êàæäóþ èç åå òðåõ êîíúþíêöèé âõîäÿò íå âñå ïåðåìåííûå. Ïîñòðîèì íà ýòàïå (5) äëÿ íèõ ýêâèâàëåíòíûå ñîâåðøåííûå ÄÍÔ (èñïîëüçóÿ ðåøåíèå çàäà÷è 4.2 íà ñòð. 22!). (X ∧ ¬Z) ≡ (X ∧ Y ∧ ¬Z) ∨ (X ∧ ¬Y ∧ ¬Z), ¬Y ≡ (X ∧ ¬Y ∧ Z) ∨ (X ∧ ¬Y ∧ ¬Z) ∨ (¬X ∧ ¬Y ∧ Z) ∨ (¬X ∧ ¬Y ∧ ¬Z), (¬X ∧ Z) ≡ (¬X ∧ Y ∧ Z) ∨ (¬X ∧ ¬Y ∧ Z). Ïîäñòàâèâ ýòè ôîðìóëû â Φ1 è óñòðàíèâ ïîâòîðåíèÿ êîíúþíêöèé, ïîëó÷èì ñîâåðøåííóþ ÄÍÔ, ýêâèâàëåíòíóþ èñõîäíîé ôîðìóëå Φ: Φ2 = (X ∧ Y ∧ ¬Z) ∨ (X ∧ ¬Y ∧ ¬Z) ∨ (X ∧ ¬Y ∧ Z)∨ (¬X ∧ ¬Y ∧ Z) ∨ (¬X ∧ ¬Y ∧ ¬Z) ∨ (¬X ∧ Y ∧ Z). Ìû âèäèì, ÷òî ÄÍÔ Φ1 , ïîëó÷åííàÿ ïîñëå 4-ãî ýòàïà, âûãëÿäèò ñóùåñòâåííî ïðîùå, ò.å. ÿâëÿåòñÿ áîëåå êîðîòêîé, ÷åì ñîâåðøåííàÿ ÄÍÔ Φ2 . Îäíàêî ñîâåðøåííûå ÄÍÔ è ÊÍÔ îáëàäàþò âàæíûì ñâîéñòâîì åäèíñòâåííîñòè, êîòîðîå ñëåäóåò èç èõ êîíñòðóêöèè â òåîðåìå 4.1 íà ñòð. 16.

Ñëåäñòâèå 4.1.2. Äëÿ êàæäîé áóëåâîé ôóíêöèè îò n ïåðåìåííûõ, íå ðàâíîé òîæäåñòâåííî 0, ñóùåñòâóåò åäèíñòâåííàÿ ñ òî÷íîñòüþ äî ïåðåñòàíîâêè êîíúþíêöèé è ïåðåìåííûõ âíóòðè êîíúþíêöèé ñîâåðøåííàÿ ÄÍÔ, çàäàþùàÿ ýòó ôóíêöèþ.

Ýòî ñëåäñòâèå ïîçâîëÿåò ïðåäëîæèòü ñëåäóþùóþ ïðîöåäóðó äëÿ ïðîâåðêè ýêâèâàëåíòíîñòè ôîðìóë Φ è Ψ. (1) Ïîñòðîèòü äëÿ Φ è Ψ ýêâèâàëåíòíûå ñîâåðøåííûå ÄÍÔ Φ0 è Ψ0 , èñïîëüçóÿ ïðîöåäóðó ïðèâåäåíèÿ ê ñîâåðøåííîé ÄÍÔ.

20

4

Äèçúþíêòèâíûå è êîíúþíêòèâíûå íîðìàëüíûå ôîðìû

(2) Óïîðÿäî÷èòü â ñîîòâåòñòâèè ñ íóìåðàöèåé ïåðåìåííûõ X âõîæäåíèÿ ïåðåìåííûõ â êàæäóþ êîíúþíêöèþ, à çàòåì ëåêñèêîãðàôè÷åñêè óïîðÿäî÷èòü ìåæäó ñîáîé êîíúþíêöèè, âõîäÿùèå â Φ0 è Ψ0 . Ïóñòü â ðåçóëüòàòå ïîëó÷àòñÿ ñîâåðøåííûå ÄÍÔ Φ00 è Ψ00 . (3) Åñëè Φ00 = Ψ00 , òî âûäàòü îòâåò Äà, èíà÷å  îòâåò Íåò. Çàìå÷àíèå. Àíàëîãè÷íóþ ïðîöåäóðó ìîæíî ïîñòðîèòü ñ èñïîëüçîâàíèåì ñîâåðøåííûõ ÊÍÔ.

4.3 Ñîêðàùåííûå ÄÍÔ Ñîêðàùåííûå ÄÍÔ ÿâëÿþòñÿ åùå îäíèì ñïîñîáîì îäíîçíà÷íîãî ïðåäñòàâëåíèÿ áóëåâûõ ôóíêöèé, êîòîðîå âî ìíîãèõ ñëó÷àÿõ ìîæåò îêàçàòüñÿ áîëåå ïðîñòûì, ÷åì ïðåäñòàâëåíèå ñ ïîìîùüþ ñîâåðøåííûõ ÄÍÔ. Íàïîìíèì, ÷òî ìû ðàññìàòðèâàåì áóëåâû ôóíêöèè íàä ïåðåìåííûìè X = {X1 , . . . , Xn }. Ñ êàæäîé ýëåìåíòàðíîé êîíúþíêöèåé K = Xiσ11 ∧ Xiσ22 ∧ . . . ∧ Xiσkk ñâÿçàíî ìíîæåñòâî NK+ íàáîðîâ ïåðåìåííûõ, íà êîòîðûõ K ïðèíèìàåò çíà÷åíèå 1. Íåòðóäíî ïîíÿòü, ÷òî ýòî ìíîæåñòâî ñîäåðæèò 2(n−k) íàáîðîâ, â êîòîðûõ êàæäàÿ èç âõîäÿùèõ â K ïåðåìåííûõ Xir (1 ≤ r ≤ k) èìååò ôèêñèðîâàííîå çíà÷åíèå σr , à çíà÷åíèÿ îñòàëüíûõ (n − k) ïåðåìåííûõ ïðîèçâîëüíû.

Îïðåäåëåíèå 4.2. Ïóñòü f - ïðîèçâîëüíàÿ áóëåâà ôóíêöèÿ íàä X. Ýëåìåíòàðíàÿ

êîíúþíêöèÿ K íàçûâàåòñÿ äîïóñòèìîé äëÿ f , åñëè NK+ ⊆ Nf+ . Ýëåìåíòàðíàÿ êîíúþíêöèÿ K íàçûâàåòñÿ ìàêñèìàëüíîé äëÿ f , åñëè äëÿ ëþáîé ýëåìåíòàðíîé êîíúþíêöèè L èç óñëîâèÿ NK+ ⊆ NL+ ⊆ Nf+ ñëåäóåò, ÷òî NK+ = NL+ . Ñîêðàùåííîé ÄÍÔ äëÿ ôóíêöèè f íàçûâàåòñÿ äèçúþíêöèÿ âñåõ ìàêñèìàëüíûõ äëÿ ýòîé ôóíêöèè ýëåìåíòàðíûõ êîíúþíêöèé.

Èç ýòîãî îïðåäåëåíèÿ íåïîñðåäñòâåííî ñëåäóåò, ÷òî ñîêðàùåííàÿ ÄÍÔ äëÿ ôóíêöèè f åäèíñòâåííà (ñ òî÷íîñòüþ äî ïîðÿäêà ýëåìåíòàðíûõ êîíúþíêöèé è ïîðÿäêà ïåðåìåííûõ â íèõ) è â òî÷íîñòè çàäàåò ôóíêöèþ f . Ïðèìåðîì ñîêðàùåííîé ÄÍÔ ÿâëÿåòñÿ ôîðìóëà Φ1 = (X ∧ ¬Z) ∨ ¬Y ∨ (¬X ∧ Z) èç ïðèìåðà 4.1 íà ñòð. 19. Ñîêðàùåííóþ ÄÍÔ ìîæíî ïîëó÷èòü èç ïðîèçâîëüíîé ÄÍÔ D, èñïîëüçóÿ ïðîöåäóðó, íàçûâàåìóþ ìåòîäîì Áëåéêà. (1) Ïðèìåíÿòü, ñêîëüêî âîçìîæíî, çàêîí ïîãëîùåíèÿ (Ï3): (X ∧ K1 ) ∨ (¬X ∧ K2 ) ≡ (X ∧ K1 ) ∨ (¬X ∧ K2 ) ∨ (K1 ∧ K2 ) ñëåâà íàïðàâî ïðè óñëîâèè, ÷òî êîíúþíêöèÿ (K1 ∧ K2 ) íåïðîòèâîðå÷èâà, ò.å. íå ñîäåðæèò îäíîâðåìåííî íåêîòîðóþ ïåðåìåííóþ è åå îòðèöàíèå. (Çàìåòèì, ÷òî íà ýòîì ýòàïå ÷èñëî ýëåìåíòàðíûõ êîíúþíêöèé â ÄÍÔ, âîîáùå ãîâîðÿ, óâåëè÷èâàåòñÿ). (2) Ïðèìåíÿòü, ñêîëüêî âîçìîæíî, ïðàâèëî ïîãëîùåíèÿ (Ï1): X ∨ (X ∧ K) ≡ X . Çàòåì óäàëèòü ïîâòîðíûå âõîæäåíèÿ êîíúþíêöèé.

4.3 Ñîêðàùåííûå ÄÍÔ

21

Òåîðåìà 4.2.  ðåçóëüòàòå ïðèìåíåíèÿ ìåòîäà Áëåéêà ê ïðîèçâîëüíîé ÄÍÔ ÷åðåç êîíå÷íîå ÷èñëî øàãîâ áóäåò ïîëó÷åíà ýêâèâàëåíòíàÿ åé ñîêðàùåííàÿ ÄÍÔ.

Äîêàçàòåëüñòâî. Ïóñòü ïîñëå (1)-ãî ýòàïà ïðîöåäóðû ÄÍÔ D ôóíêöèè f ïðåîáðàçîâàëàñü â ýêâèâàëåíòíóþ ÄÍÔ D1 . Ïîêàæåì, ÷òî äëÿ âñÿêîé äîïóñòèìîé äëÿ f ýëåìåíòàðíîé êîíúþíêöèÿ K â D1 íàéäåòñÿ òàêàÿ êîíúþíêöèÿ K 0 , ÷òî NK+ ⊆ NK+0 . Äîêàçàòåëüñòâî ïðîâåäåì âîçâðàòíîé èíäóêöèåé ïî ÷èñëó ïåðåìåííûõ â K . Áàçèñ èíäóêöèè. Ïóñòü K ñîäåðæèò âñå n ïåðåìåííûõ èç X. Òîãäà NK+ ñîñòîèò èç + åäèíñòâåííîãî íàáîðà è, ïîñêîëüêó NK ⊆ ND+1 , òî â D1 ñóùåòñâóåò êîíúþíêöèÿ K 0 , + äëÿ êîòîðîé NK ⊆ NK+0 . Øàã èíäóêöèè. Ïóñòü äëÿ íåêîòîðîãî k < n óòâåðæäåíèå âåðíî äëÿ âñåõ äîïóñòèìûõ äëÿ f êîíúþíêöèé, ñîäåðæàùèõ íå ìåíåå (k + 1)-îé ïåðåìåííîé. Äîêàæåì, ÷òî îíî âåðíî è äëÿ äîïóñòèìûõ êîíúþíêöèé ñ k ïåðåìåííûìè. Ïóñòü äîïóñòèìàÿ äëÿ f ýëåìåíòàðíàÿ êîíúþíêöèÿ K ñîäåðæèò k ïåðåìåííûõ è ïóñòü X ∈ X - ïåðåìåííàÿ, íå âõîäÿùàÿ â K . Òîãäà îáå ýëåìåíòàðíûå êîíúþíêöèè K1 = (X ∧ K) è K2 = (¬X ∧ K) ÿâëÿþòñÿ äîïóñòèìûìè äëÿ f è ïî ïðåäïîëîæåíèþ + èíäóêöèè äëÿ íèõ â Φ1 íàéäóòñÿ òàêèå K10 è K20 , ÷òî NK ⊆ NK+0 è NK+2 ⊆ NK+0 . Åñëè 1 1 2 õîòÿ áû îäíà èç íèõ íå ñîäåðæèò X , òî åå ìîæíî âûáðàòü â êà÷åñòâå K 0 .  ïðîòèâíîì ñëó÷àå, èõ ìîæíî ïðåäñòàâèòü â âèäå K10 = (X ∧ K100 ) è K20 = (¬X ∧ K200 ). Ïðè ýòîì NK+ ⊆ NK+00 è NK+ ⊆ NK+00 . Ïîñêîëüêó âñå ïðåîáðàçîâàíèÿ âèäà (Ï3) âûïîëíåíû, òî D1 1 2 + òîãäà ñîäåðæèò è êîíúþíêöèþ K 0 = (K100 ∧ K200 ), äëÿ êîòîðîé NK ⊆ NK+0 . + Çàìåòèì, ÷òî åñëè K ìàêñèìàëüíà äëÿ f , òî NK = NK+0 . Òàêèì îáðàçîì, âñå ìàêñèìàëüíûå êîíúþíêöèè âõîäÿò â D1 . Òåïåðü, ÷òîáû çàâåðøèòü äîêàçàòåëüñòâî òåîðåìû, íóæíî ïîêàçàòü, ÷òî íà ýòàïå (2) èç D1 áóäóò óäàëåíû âñå íåìàêñèìàëüíûå ýëåìåíòàðíûå êîíúþíêöèè. (Äîêàæèòå ýòî èíäóêöèåé ïî ÷èñëó íåìàêñèìàëüíûõ êîíúþíêöèé â D1 .)

Ïðèìåð 4.2. Ïðèìåíèì ìåòîä Áëåéêà ê ñîâåðøåííîé ÄÍÔ ôóíêöèè f (X1 , X2 , X3 ), ïðèíèìàþùåé çíà÷åíèå 1 íà íàáîðàõ ìíîæåñòâà Nf+ = {(001), (010), (011), (101)}.

Åå ñîâåðøåííàÿ ÄÍÔ D = (¬X1 ∧ ¬X2 ∧ X3 ) ∨ (¬X1 ∧ X2 ∧ ¬X3 ) ∨ (¬X1 ∧ X2 ∧ X3 ) ∨ (X1 ∧ ¬X2 ∧ X3 ). Ïîñëå ïðèìåíåíèÿ ïðåîáðàçîâíàèé (Ï3) íà (1)-îì ýòàïå ïîëó÷èì D1 = (¬X1 ∧ ¬X2 ∧ X3 ) ∨ (¬X1 ∧ X2 ∧ ¬X3 ) ∨ (¬X1 ∧ X2 ∧ X3 ) ∨ (X1 ∧ ¬X2 ∧ X3 ) ∨ (¬X2 ∧ X3 ) ∨ (¬X1 ∧ X2 ) ∨ (¬X1 ∧ X3 ) Ïîñëå ïîãëîùåíèé (Ï1) íà âòîðîì ýòàïå îñòàíåòñÿ ñîêðàùåííàÿ ÄÍÔ D2 = (¬X2 ∧ X3 ) ∨ (¬X1 ∧ X2 ) ∨ (¬X1 ∧ X3 ). Çàìåòèì, ÷òî îíà íå ÿâëÿåòñÿ ñàìîé êîðîòêîé ÄÍÔ äëÿ f , ò.ê. D2 ≡ (¬X2 ∧ X3 ) ∨ (¬X1 ∧ X2 ).

22

5 Ìíîãî÷ëåíû Æåãàëêèíà

4.4 Çàäà÷è Çàäà÷à 4.1.

Äîêàæèòå òåîðåìó 4.1 íà ñòð. 16, ïðîâåðèâ, ÷òî äëÿ ëþáîãî íàáîðà çíà÷åíèé àðãóìåíòîâ σ1 , . . . , σn âûïîëíåíû ðàâåíñòâà f (σ1 , . . . , σn ) = Df (σ1 , . . . , σn ) è f (σ1 , . . . , σn ) = Cf (σ1 , . . . , σn ).

Çàäà÷à 4.2.

(1) Ïðåäëîæèòå ïðîöåäóðó, êîòîðàÿ ïî ïðîèçâîëüíîé ýëåìåíòàðíîé êîíúþíêöèè ñòðîèò ýêâèâàëåíòíóþ åé ñîâåðøåííóþ ÄÍÔ. (2) Ïðåäëîæèòå ïðîöåäóðó, êîòîðàÿ ïî ïðîèçâîëüíîé ýëåìåíòàðíîé äèçúþíêöèè ñòðîèò ýêâèâàëåíòíóþ åé ñîâåðøåííóþ ÊÍÔ.

Çàäà÷à 4.3. Äîêàæèòå, ÷òî äëÿ ëþáîãî k ≤ n êàæäóþ áóëåâó ôóíêöèþ f ∈ Pn

ìîæíî ïðåäñòàâèòü â âèäå W f (X1 , . . . , Xk , Xk+1 , . . . , Xn ) = (σ1 ,...,σk )∈B k X1σ1 ∧ . . . Xkσk ∧ f (σ1 , . . . , σk , Xk+1 , . . . , Xn ). Òàêîå ïðåäñòàâëåíèå íàçûâàåòñÿ ðàçëîæåíèåì f ïî X1 , . . . , Xk . Ïðè k = n èç íåãî ïîëó÷àåòñÿ ñîâåðøåííàÿ ÄÍÔ èç òåîðåìû 4.1.

Çàäà÷à 4.4.

Äîêàæèòå ïðåäëîæåíèå 4.1 íà ñòð. 18, èñïîëüçóÿ èíäóêöèþ ïî îáùåìó êîëè÷åñòâó ôóíêöèé → è + â ôîðìóëå.

Çàäà÷à 4.5. Êàê èçìåíèòü (3)-èé, (4)-ûé è (5)-ûé ýòàïû ïðîöåäóðû Ïðèâåäåíèå ê ñîâåðøåííîé ÄÍÔ, ÷òîáû â ðåçóëüòàòå ïîëó÷èòü ïðîöåäóðó Ïðèâåäåíèå ê ñîâåðøåííîé ÊÍÔ, êîòîðàÿ ïî ïðîèçâîëüíîé ôîðìóëå ñòðîèò ýêâèâàëåíòíóþ ñîâåðøåííóþ ÊÍÔ.

Çàäà÷à 4.6. Íàéòè ýêâèâàëåíòíûå ñîêðàùåííûå ÄÍÔ è äîêàçàòü ýêâèâàëåíòíîñòü ñëåäóþùèõ ïàð ôîðìóë: à) Φ = (((¬X ∧ ¬Y ) → ¬Z) ∧ (X → Y )), Ψ = ((1 + Y ) → (¬X ∧ (1 + Z))). á) Φ = (¬((X1 → X2 ) ∨ ¬(X2 → X1 )) ∧ X3 ), Ψ = ¬((X1 ∧ X3 ) → X2 ). â) Φ = ¬(¬X ∧ Y ∧ ¬Z) → ((Y + 1) ∧ ((X + 1) → ¬(¬U ∨ ¬Z))), Ψ = (¬X ∨ Y ) → ((¬U ∨ Y ∨ Z) → (¬(X ∨ ¬Y ) ∧ ¬Z)).

5 Ìíîãî÷ëåíû Æåãàëêèíà Ìíîãî÷ëåíû Æåãàëêèíà ÿâëÿþòñÿ åùå îäíèì èíòåðåñíûì ïîäêëàññîì ôîðìóë, ïîçâîëÿþùèì îäíîçíà÷íî ïðåäñòàâëÿòü áóëåâû ôóíêöèè.

Îïðåäåëåíèå 5.1. Ìíîãî÷ëåíàìè Æåãàëêèíà íàçâàþòñÿ ôîðìóëû íàä ìíîæåñòâîì ôóíêöèé FJ = {0, 1, ∗, +} (çäåñü ∗ - ýòî äðóãîå îáîçíà÷åíèå êîíúþíêöèè).

23 Òàêèì îáðàçîì, êàæäûé ìíîãî÷ëåí Æåãàëêèíà (âîçìîæíî, ïîñëå ðàñêðûòèÿ ñêîáîê è ïðèâåäåíèÿ ïîäîáíûõ ÷ëåíîâ) ïðåäñòàâëÿåò ñóììó (ïî ìîäóëþ 2) ïîëîæèòåëüíûõ (ìîíîòîííûõ) ýëåìåíòàðíûõ êîíúþíêöèé (ò.å. ýëåìåíòàðíûõ êîíúþíêöèé áåç îòðèöàíèé). Ïîñêîëüêó äëÿ + è * ñïðàâåäëèâû çàêîíû àññîöèàòèâíîñòè, ìû áóäåì ïðè çàïèñè ìíîãî÷ëåíà Æåãàëêèíà îïóñêàòü ñêîáêè, ñ÷èòàÿ, ÷òî ∗ ñâÿçûâàåò àðãóìåíòû ñèëüíåå, ÷åì +. Íåòðóäíî ïðîâåðèòü, ÷òî ñïðàâåäëèâû ñëåäóþùèå ýêâèâàëåíòíîñòè:

(J1) ¬X (J2) (X1 ∧ X2 ) (J3) (X1 ∨ X2 ) (J4) (X1 + X2 ) ∗ (X3 + X4 )

≡ ≡ ≡ ≡

(X + 1), (X1 ∗ X2 ), (X1 ∗ X2 + X1 + X2 ) ≡ (X1 + 1) ∗ (X2 + 1) + 1, (X1 ∗ X2 + X1 ∗ X3 + X2 ∗ X3 + X2 ∗ X4 ).

Èç ýòèõ ýêâèâàëåíòíîñòåé è òåîðåìû 4.1 íà ñòð. 16 ëåãêî ïîëó÷èòü ïåðâóþ ÷àñòü ñëåäóþùåãî óòâåðæäåíèÿ.

Òåîðåìà 5.1. Äëÿ ëþáîé áóëåâîé ôóíêöèè ñóùåñòâóåò çàäàþùèé åå ìíîãî÷ëåí Æåãàëêèíà. Îí åäèíñòâåíåí ñ òî÷íîñòüþ äî ïåðåñòàíîâîê ñëàãàåìûõ è ïîðÿäêà ïåðåìåííûõ â êîíúþíêöèÿõ.

Äîêàçàòåëüñòâî. Ñóùåñòâîâàíèå òàêîãî ìíîãî÷ëåíà ñëåäóåò èç òîãî, ÷òî äëÿ ëþáîé ÄÍÔ èëè ÊÍÔ ìîæíî ñ ïîìîùüþ óêàçàííûõ ýêâèâàëåíòíîñòåé íàéòè ýêâèâàëåíòíûé ìíîãî÷ëåí Æåãàëêèíà: (J1)-(J3) ïîçâîëÿþò çàìåíÿòü âñå âõîæäåíèÿ ¬, ∧ è ∨ íà + è *, à (J4) - ïåðåìíîæàòü ïîëó÷èâøèåñÿ ïîñëå òàêîé çàìåíû ìíîãî÷ëåíû. Äëÿ äîêàçàòåëüñòâà åäèíñòâåííîñòè ïðåäñòàâëåíèÿ ïîäñ÷èòàåì ÷èñëî ðàçëè÷íûõ ìíîãî÷ëåíîâ Æåãàëêèíà îò n ïåðåìåííûõ. Êàæäàÿ ïîëîæèòåëüíàÿ ýëåìåíòàðíàÿ êîíúþíêöèÿ èìååò âèä Xi1 ∗ . . . ∗ Xik , ãäå 1 ≤ i1 < . . . < ik ≤ n. Òàêèõ êîíúþíêöèé ñòîëüêî æå, ñêîëüêî ïîäìíîæåñòâ ìíîæåñòâà X = {X1 , . . . , Xn }, ò.å. 2n . ( Êîíúþíêöèÿ, ñîîòâåòñòâóþùàÿ ïóñòîìó ïîäìíîæåñòâó ïåðåìåííûõ ðàâíà 1). Óïîðÿäî÷èì èõ ïðîèçâîëüíûì îáðàçîì (íàïðèìåð, ëåêñèêîãðàôè÷åñêè): K1 , K2 , . . . , K2n . Tîãäà êàæäûé ìíîãî÷ëåí Æåãàëêèíà åäèíñòâåííûì îáðàçîì ìîæíî ïðåäñòàâèòü êàê ñóììó α1 ∗ K1 + α2 ∗ K2 + . . . + α2n ∗ K2n , ãäå êàæäûé èç êîýôôèöèåíòîâ αi ðàâåí 0 èëè 1. Ñëåäîâàòåëüíî, ÷èñëî ìíîãî÷ëåíîâ n Æåãàëêèíà ðàâíî 22 , ò.å. ÷èñëó âñåõ áóëåâûõ ôóíêöèé îò n ïåðåìåííûõ. Ïîýòîìó êàæäàÿ ôóíêöèÿ çàäàåòñÿ â òî÷íîñòè îäíèì ìíîãî÷ëåíîì Æåãàëêèíà.2

Ïðèìåð 5.1. Ïóñòü ôóíêöèÿ f (X1 , X2 , X3 ) çàäàåòñÿ ÄÍÔ Φ = (X1 ∧ ¬X2 ) ∨ (¬X1 ∧ X2 ∧ ¬X3 ). Íàéäåì ïîëèíîì Æåãàëêèíà, êîòîðûé òàêæå çàäàåò ýòó ôóíêöèþ. Ñíà÷àëà çàìåíÿåì ∧ íà *, à çàòåì,ïðèìåíÿÿ ýêâèâàëåíòíîñòü (J1), óñòðàíÿåì îòðèöàíèÿ è ïîëó÷àåì: Φ ≡ X1 ∗ (X2 + 1) ∨ (X1 + 1) ∗ X2 ∗ (X3 + 1). Ïåðåìíîæèâ ïî ïðàâèëàì (J4), ïîëó÷èì:

24

5 Ìíîãî÷ëåíû Æåãàëêèíà

Φ ≡ (X1 ∗ X2 + X1 ) ∨ (X1 ∗ X2 ∗ X3 + X1 ∗ X2 + X2 ∗ X3 + X2 ) Ýêâèâàëåíòíîñòü (J3) ïîçâîëÿåò óñòðàíèòü ∨: Φ ≡ (X1 ∗ X2 + X1 ) ∗ (X1 ∗ X2 ∗ X3 + X1 ∗ X2 + X2 ∗ X3 + X2 )+ (X1 ∗ X2 + X1 ) + (X1 ∗ X2 ∗ X3 + X1 ∗ X2 + X2 ∗ X3 + X2 ). Ñíîâà, èñïîëüçóÿ (J4), ïåðåìíîæèì ïåðâûå äâå ñêîáêè è óñòðàíèì ïîâòîðåíèÿ ïåðåìåííûõ â êîíúþíêöèÿõ: Φ ≡ (X1 ∗ X2 ∗ X3 + X1 ∗ X2 + X1 ∗ X2 ∗ X3 + X1 ∗ X2 ∗ X3 + X1 ∗ X2 + X1 ∗ X2 ∗ X3 + X1 ∗ X2 + X1 ∗ X2 )+ (X1 ∗ X2 + X1 ) + (X1 ∗ X2 ∗ X3 + X1 ∗ X2 + X2 ∗ X3 + X2 ). Óïðîñòèì ýòó ñóììó, èñïîëüçóÿ ýêâèâàëåíòíîñòè: X + X ≡ 0 è X + 0 ≡ X.  ðåçóëüòàòå ïîëó÷èì ìíîãî÷ëåí Æåãàëêèíà P (X1 , X2 , X3 ) = X1 + X2 + X2 ∗ X3 + X1 ∗ X2 ∗ X3 , ýêâèâàëåíòíûé èñõîäíîé ÄÍÔ Φ. Åñëè ôóíêöèÿ f (X1 , . . . , Xn ) çàäàíà òàáëè÷íî, òî äëÿ ïîñòðîåíèÿ ðåàëèçóþùåãî åå ìíîãî÷ëåíà Æåãàëêèíà ìîæíî ïðèìåíèòü ìåòîä íåîïðåäåëåííûõ êîýôèöèåíòîâ. Ñîïîñòàâèì i-îìó íàáîðó çíà÷åíèé ïåðåìåííûõ σi = (σi1 , . . . , σin ) â òàáëèöå ïîëîæèV òåëüíóþ êîíúþíêöèþ Ki = σj =1 Xj ïåðåìåííûõ, ðàâíûõ 1 â ýòîì íàáîðå.  ÷àñòi íîñòè, K1 - ïóñòàÿ êîíúþíêöèÿ, K2 = Xn , K3 = Xn−1 , K4 = (Xn ∗ Xn−1 ). è ò.ä. Òîãäà äëÿ ïîëó÷åíèÿ íóæíîãî ìíîãî÷ëåíà Æåãàëêèíà äîñòàòî÷íî îïðåäåëèòü âñå êîýôôèöèåíòû αi , i = 1, . . . , 2n , â âûðàæåíèè f (X1 , . . . , Xn ) = α1 ∗ K1 + α2 ∗ K2 + . . . + α2n ∗ K2n , Ïîäñòàâëÿÿ â ýòî ðàâåíñòâî çíà÷åíèÿ ïåðåìåííûõ èç íàáîðà σi , i = 1, . . . , 2n , ìû ïîëó÷èì 2n ëèíåéíûõ óðàâíåíèé îòíîñèòåëüíî 2n íåèçâåñòíûõ êîýôôèöèåíòîâ αi . Ðåøèâ ýòó ñèñòåìó, ïîëó÷èì òðåáóåìûé ìíîãî÷ëåí Æåãàëêèíà. Ýòà ñèñòåìà òðåóãîëüíàÿ è ëåãêî ðåøàåòñÿ ñâåðõó-âíèç: êàæäîå αi îïðåäåëÿåòñÿ ïî çíà÷åíèÿì α1 , . . . , αi−1 èç óðàâíåíèÿ, ñîîòâåòñòâóþùåãî íàáîðó σi .

Ïðèìåð 5.2. Ðàññìîòðèì â êà÷åñòâå ïðèìåðà ôóíêöèþ f (X1 , X2 , X3 ), çàäàííóþ ñëåäóþùåé òàáëèöåé.

Ìíîãî÷ëåí Æåãàëêèíà äëÿ íåå (êàê è äëÿ ëþáîé ôóíêöèè îò 3-õ ïåðåìåííûõ) ïðåäñòàâëÿåòñÿ â âèäå p(X1 , X2 , X3 ) = α0 + α1 ∗ X1 + α2 ∗ X2 + α3 ∗ X3 + α12 ∗ X1 ∗ X2 + α13 ∗ X1 ∗ X3 + α23 ∗ X2 ∗ X3 + α123 ∗ X1 ∗ X2 ∗ X3  ýòîì ïðåäñòàâëåíèè â èíäåêñàõ ó êîýôôèöèåíòîâ α ïåðå÷èñëåíû ïåðåìåííûå, âõîäÿùèå â ñîîòâåòñòâóþùèå êîíúþíêöèè. Ïîñëåäîâàòåëüíî ïîäñòàâëÿÿ çíà÷åíèÿ ïåðåìåííûõ è f èç òàáëèöû, ïîëó÷àåì: p(0, 0, 0) = α0 = 1; p(0, 0, 1) = α0 + α3 = 0 ⇒ α3 = 1; p(0, 1, 0) = α0 + α2 = 0 ⇒ α2 = 1; p(0, 1, 1) = α0 + α2 + α3 + α23 = 0 ⇒ α23 = 1; p(1, 0, 0) = α0 + α1 = 1 ⇒ α1 = 0;

5.1 Çàäà÷è

25 Òàáëèöà 9: Ôóíêöèÿ f (X1 , X2 , X3 )

X1 0 0 0 0 1 1 1 1

X2 0 0 1 1 0 0 1 1.

X3 0 1 0 1 0 1 0 1

f (X1 , X2 , X3 ) 1 0 0 0 1 0 0 1

p(1, 0, 1) = α0 + α1 + α3 + α13 = 0 ⇒ α13 = 0; p(1, 1, 0) = α0 + α1 + α2 + α12 = 0 ⇒ α12 = 0; p(1, 1, 1) = α0 + α1 + α2 + α3 + α12 + α13 + α23 + α123 = 1 ⇒ α123 = 1. Ñëåäîâàòåëüíî, ôóíêöèÿ f (X1 , X2 , X3 ) ïðåäñòàâëÿåòñÿ ìíîãî÷ëåíîì Æåãàëêèíà

pf (X1 , X2 , X3 ) = 1 + X3 + X2 + X2 ∗ X3 + X1 ∗ X2 ∗ X3 .

5.1 Çàäà÷è Çàäà÷à 5.1. Èñïîëüçóÿ îñíîâíûå ýêâèâàëåíòíîñòè, íàéòè ýêâèâàëåíòíûå ìíîãî÷ëåíû Æåãàëêèíà è äîêàçàòü ýêâèâàëåíòíîñòü ñëåäóþùèõ ôîðìóë: Φ = ((Z ∧ (X → Y )) ∨ ¬(¬X → Z)), Ψ = (X → (Y ∧ Z)).

Çàäà÷à 5.2. Íàéòè ñîêðàùåííóþ äèçúþíêòèâíóþ íîðìàëüíóþ ôîðìó è ìíîãî÷ëåí

Æåãàëêèíà (ìåòîäîì íåîïðåäåëåííûõ êîýôôèöèåíòîâ) äëÿ ñëåäóþùèõ ôóíêöèé îò òðåõ àðãóìåíòîâ. Ñ÷èòàåì, ÷òî íàáîðû èõ àðãóìåíòîâ óïîðÿäî÷åíû ëåêñèêîãðàôè÷åñêè è çíà÷åíèÿ íà íèõ çàäàþòñÿ ïîñëåäîâàòåëüíîñòüþ 8 íóëåé è åäèíèö. à) f = (0010 1100). â) f = (1100 0011). á) f = (1110 1100). ã) f = (0110 1011).

6 Ïîëíûå ñèñòåìû ôóíêöèé è òåîðåìà Ïîñòà S Ïóñòü P = ∞ n=0 Pn  ýòî ìíîæåñòâî âñåõ áóëåâûõ ôóíêöèé.  ïðåäûäóùåì ðàçäåëå ìû óñòàíîâèëè, ÷òî ëþáóþ ôóíêöèþ èç P ìîæíî çàäàòü ôîðìóëîé íàä ñèñòåìîé FB = {¬, ∧, ∨} (â êà÷åñòâå òàêèõ ôîðìóë ìîæíî, íàïðèìåð, âçÿòü ñîîòâåòñòâóþùèå ÄÍÔ è ÊÍÔ). Òàêèå ñèñòåìû ôóíêöèé íàçûâàþòñÿ ïîëíûìè.

6

26

Ïîëíûå ñèñòåìû ôóíêöèé è òåîðåìà Ïîñòà

Îïðåäåëåíèå 6.1. Ñèñòåìà áóëåâûõ ôóíêöèé F íàçûâàåòñÿ ïîëíîé, åñëè ôîðìóëàìè íàä ýòîé ñèñòåìîé ìîæíî çàäàòü ëþáóþ áóëåâó ôóíêöèþ èç P. Äðóãèì óæå èçâåñòíûì íàì ïðèìåðîì ïîëíîé ñèñòåìû ôóíêöèé ÿâëÿåòñÿ ñèñòåìà FJ = {0, 1, ∗, +}, ïîçâîëÿþùàÿ çàäàòü ïðîèçâîëüíóþ áóëåâó ôóíêöèþ ñ ïîìîùüþ ìíîãî÷ëåíà Æåãàëêèíà. Ðàçóìååòñÿ, íå âñÿêàÿ ñèñòåìà ÿâëÿåòñÿ ïîëíîé. Íàïðèìåð, ôîðìóëàìè íàä ñèñòåìîé {∨} íåâîçìîæíî âûðàçèòü ôóíêöèþ òîæäåñòâåííî ðàâíóþ 0 (ïî÷åìó?). Íàøà öåëü â ýòîì ðàçäåëå  íàéòè êðèòåðèé, ïîçâîëÿþùèé ïî ñèñòåìå ôóíêöèé îïðåäåëÿòü åå ïîëíîòó. Äëÿ èññëåäîâàíèÿ ïîëíîòû ïîëåçíî ñëåäóþùåå ïîíÿòèå.

Îïðåäåëåíèå 6.2. Çàìûêàíèå [F ] ñèñòåìû ôóíêöèé F  ýòî ìíîæåñòâî âñåõ ôóíêöèé, êîòîðûå ìîæíî çàäàòü ñ ïîìîùüþ ôîðìóë íàä F .

Òîãäà îïðåäåëåíèå ïîëíîé ñèñòåìû ìîæíî ïåðåôîðìóëèðîâàòü òàê: ñèñòåìà F ÿâëÿåòñÿ ïîëíîé òîãäà è òîëüêî òîãäà, êîãäà [F ] = P. Çàìûêàíèå îáëàäàåò ñëåäóþùèìè îñíîâíûìè ñâîéñòâàìè.

Ïðåäëîæåíèå 6.1.

(1) (2) (3) (4)

F ⊆ [F ]. [[F ]] = [F ]. F ⊆ G ⇒ [F ] ⊆ [G]. Åñëè ñèñòåìà F ÿâëÿåòñÿ ïîëíîé è F ⊆ [G], òî è ñèñòåìà G ÿâëÿåòñÿ ïîëíîé.

Äîêàçàòåëüñòâî. Âñå ýòèõ óòâåðæäåíèÿ äîñòàòî÷íî ïðîñòî ñëåäóþò èç îïðåäåëåíèÿ çàìûêàíèÿ. Íàïðèìåð, ñïðàâåäëèâîñòü ïóíêòà (2) ñëåäóåò èç òîãî, ÷òî âñÿêàÿ ôóíêöèÿ èç [F ] çàäàåòñÿ íåêîòîðîé ôîðìóëîé íàä F , à òîãäà âñÿêàÿ ôóíêöèÿ èç [[F ]], êîòîðàÿ çàäàåòñÿ ñóïåðïîçèöèåé ôóíêöèé èç [F ], çàäàåòñÿ òàêæå íåêîòîðîé ôîðìóëîé íàä F . Ïóíêò (3) î÷åâèäåí, à ïóíêò (4) ñëåäóåò èç (2) è (3): F ⊆ [G] ⇒ [F ] ⊆ [[G]] ⇒ [F ] ⊆ [G] è òàê êàê [F ] = P, òî è [G] = P.2 Óòâåðæäåíèå (4) ïîçâîëÿåò óñòàíàâëèâàòü ïîëíîòó íåêîòîðîé ñèñòåìû, âûðàæàÿ ñ åå ïîìîùüþ âñå ôóíêöèè äðóãîé ñèñòåìû, ïîëíîòà êîòîðîé óæå óñòàíîâëåíà. Íàïðèìåð, çàêîíû äå Ìîðãàíà ïîçâîëÿþò âûðàçèòü ∨ ÷åðåç ïàðó ¬, ∧: X ∨ Y ≡ ¬(¬X ∧ ¬Y ) è ∧  ÷åðåç ïàðó ¬, ∨: X ∧ Y ≡ ¬(¬X ∨ ¬Y ). Ïîýòîìó êàæäàÿ èç ñèñòåì F∧ = {¬, ∧} è F∨ = {¬, ∨} òàêæå ÿâëÿåòñÿ ïîëíîé. Ýêâèâàëåíòíîñòè (7) è (8) ïîçâîëÿþò âûðàçèòü ∨ ÷åðåç ïàðó ¬, →: X ∨ Y ≡ ¬X → Y . Ñëåäîâàòåëüíî, ïîëíîé áóäåò è ñèñòåìà F→ = {¬, →}. Èìåþòñÿ ëè ïîëíûå ñèñòåìû èç îäíîé äâóìåñòíîé ôóíêöèè? Äà. Ðàññìîòðèì ñèñòåìó, {|}, âêëþ÷àþùóþ ëèøü øòðèõ Øåôôåðà. Íàïîìíèì, ÷òî (X|Y ) ≡ ¬(X ∧ Y ). Òîãäà íåòðóäíî ïðîâåðèòü, ÷òî ¬X ≡ (X|X) è (X ∧ Y ) ≡ ((X|Y )|(X|Y )). Ñëåäîâàòåëüíî, ñèñòåìà {|} ïîëíàÿ.

Îïðåäåëåíèå 6.3. Ñèñòåìà ôóíêöèé [F ] íàçûâàåòñÿ çàìêíóòîé, åñëè F = [F ].

27 Î÷åâèäíî, ÷òî çàìêíóòàÿ ñèñòåìà [F ], íå ñîäåðæàùàÿ âñåõ ôóíêöèé èç P, íå ÿâëÿåòñÿ ïîëíîé. Äàëåå â ýòîì ðàçäåëå ìû áóäåì èñïîëüçîâàòü âåðõíèé èíäåêñ â êðóãëûõ ñêîáêàõ äëÿ óêàçàíèÿ ÷èñëà àðãóìåíòîâ ôóíêöèè,ò.å. f (n) îçíà÷àåò, ÷òî f ∈ Pn . Îïðåäåëèì ïÿòü âàæíûõ çàìêíóòûõ ñèñòåì.

Îïðåäåëåíèå 6.4. (1,2) Ôóíêöèÿ f (n) ∈ P ñîõðàíÿåò 0 ( ñîõðàíÿåò 1), åñëè f (0, 0, . . . , 0) =

0 (f (1, 1, . . . , 1) = 1). Êëàññ âñåõ ôóíêöèé, ñîõðàíÿþùèõ 0, îáîçíà÷èì ÷åðåç S0 , à êëàññ âñåõ ôóíêöèé, ñîõðàíÿþùèõ 1,  ÷åðåç S1 . (3) Ôóíêöèÿ f (n) ∈ P íàçûâàåòñÿ ñàìîäâîéñòâåííîé, åñëè äëÿ ëþáîãî íàáîðà àðãóìåíòîâ (σ1 , σ2 , . . . , σn ) ∈ Bn èìååò ìåñòî ðàâåíñòâî: f (σ1 , σ2 , . . . , σn ) = ¬f (¬σ1 , ¬σ2 , . . . , ¬σn ). Òàêèì îáðàçîì, ñàìîäâîéñòâåííûå ôóíêöèè ïðèíèìàþò íà ïðîòèâîïîëîæíûõ íàáîðàõ ïðîòèâîïîëîæíûå çíà÷åíèÿ. Êëàññ âñåõ ñàìîäâîéñòâåííûõ ôóíêöèé îáîçíà÷èì ÷åðåç S. (4) Ôóíêöèÿ f (n) ∈ P íàçûâàåòñÿ ëèíåéíîé, åñëè îíà ìîæåò áûòü çàäàíà ëèíåéíûì ìíîãî÷ëåíîì Æåãàëêèíà âèäà α0 + α1 X1 + α2 X2 + . . . αn Xn , ãäå αi ∈ {0, 1} ïðè i = 0, 1, 2, . . . , n. Êëàññ âñåõ ëèíåéíûõ ôóíêöèé îáîçíà÷èì ÷åðåç L.

(5) Ôóíêöèÿ f (n) ∈ P íàçûâàåòñÿ ìîíîòîííîé, åñëè äëÿ ëþáûõ äâóõ íàáîðîâ àðãóìåíòîâ (σ1 , σ2 , . . . , σn ) ∈ Bn è (ρ1 , ρ2 , . . . , ρn ) ∈ Bn òàêèõ, ÷òî äëÿ âñåõ j ∈ [1, n] σj ≥ ρj , èìååò ìåñòî íåðàâåíñòâî f (σ1 , σ2 , . . . , σn ) ≥ f (ρ1 , ρ2 , . . . , ρn ). Êëàññ âñåõ ìîíîòîííûõ ôóíêöèé îáîçíà÷èì ÷åðåç M.

Ïðèìåð 6.1. Ðàññìîòðèì äëÿ ïðèìåðà ïÿòü ôóíêöèé îò 3-õ ïåðåìåííûõ, êîòîðûå ïðåäñòàâëåíû â ñëåäóþùåé òàáëèöå.

Èç îïðåäåëåíèé íåïîñðåäñòâåííî ñëåäóåò, ÷òî f3 , f4 è f5 ñîõðàíÿþò 0, ò.å. âõîäÿò â S0 , à ôóíêöèè f2 , f3 , f4 è f5 ñîõðàíÿþò 1, ò.å. âõîäÿò â S1 . Ôóíêöèÿ f3 ÿâëÿåòñÿ ñàìîäâîéñòâåííîé, à f2  íåò, òàê êàê f2 (0, 0, 0) = f2 (1, 1, 1). Ôóíêöèÿ f2 ÿâëÿåòñÿ ëèíåéíîé  îíà çàäàåòñÿ ìíîãî÷ëåíîì X1 + X2 + 1. Ôóíêöèÿ f5 ÿâëÿåòñÿ ìîíîòîííîé, à f3  íåò, òàê êàê f3 (0, 1, 1) = 0 < 1 = f3 (0, 1, 0).

Òåîðåìà 6.1. Êëàññû S0 , S1 , S, L è M ÿâëÿþòñÿ çàìêíóòûìè. Äîêàçàòåëüñòâî. Çàìêíóòîñòü âñåõ óêàçàííûõ êëàññîâ óñòàíàâëèâàåòñÿ èíäóêöèåé ïî ïîñòðîåíèþ ôîðìóë. Ïóñòü F ∈ {S0 , S1 , S, L, M} è f ∈ [F ] çàäàåòñÿ íåêîòîðîé ôîðìóëîé íàä F . Íóæíî ïîêàçàòü, ÷òî òîãäà f ∈ F .

6

28

Ïîëíûå ñèñòåìû ôóíêöèé è òåîðåìà Ïîñòà

Òàáëèöà 10: Ôóíêöèè f1 , f2 , f3 , f4 è f5 .

X1 0 0 0 0 1 1 1 1

X2 0 0 1 1 0 0 1 1.

X3 0 1 0 1 0 1 0 1

f1 1 0 0 1 1 0 0 0

f2 1 1 0 0 0 0 1 1

f3 0 0 1 0 1 0 1 1

f4 0 1 1 0 1 0 0 1

f5 0 0 1 1 0 0 1 1

Áàçèñ èíäóêöèè, êîãäà ýòà ôîðìóëà åñòü ïåðåìåííàÿ X , î÷åâèäåí. (k) (k) Ïóñòü f (X1 , . . . , Xk ) = g(f1 (X1 , . . . , Xk ), . . . , fn (X1 , . . . , Xk )), è ôóíêöèè g (n) , f1 , . . . , fn âõîäÿò â F . Òðåáóåòñÿ ïîêàçàòü, ÷òî òîãäà è f âõîäèò â F . Äëÿ F = S0 ýòî ïðîñòî: f (0, 0, . . . , 0) = g(f1 (0, . . . , 0), . . . , fn (0, . . . , 0)) = g(0, 0, . . . , 0) = 0. Àíàëîãè÷íî ïðîâåðÿåòñÿ ñëó÷àé F = S1 . Åñëè F = S è (σ1 , σ2 , . . . , σk )  ïðîèçâîëüíûé íàáîð àðãóìåíòîâ, òî f (σ1 , σ2 , . . . , σk ) = ¬g(¬f1 (σ1 , . . . , σk ), . . . , ¬fn (σ1 , . . . , σk )) = ¬g(¬¬f1 (¬σ1 , . . . , ¬σk ), . . . , ¬¬fn (¬σ1 , . . . , ¬σk ) = ¬g(f1 (¬σ1 , . . . , ¬σk ), . . . , fn (¬σ1 , . . . , ¬σk )) = ¬f (¬σ1 , ¬σ2 , . . . , ¬σk ). Ñëåäîâàòåëüíî, f ∈ S. (k) Ïóñòü F = L. Òàê êàê òîãäà g (n) è âñå fi ëèíåéíû, òî ñóùåñòâóþò òàêèå êîýôôèöèåíòû α0 , α1 , . . . , αn è β0i , β1i , . . . , βki (i = 1, . . . , n) òàêèå, ÷òî g(X1 , . . . , Xn ) = α0 + α1 X1 + . . . + αn Xn è fi (X1 , . . . , Xk ) = β0i + β1i X1 + βki Xk (i = 1, . . . , n). Ïîäñòàâèâ ýòè âûðàæåíèÿ â ôîðìóëó äëÿ f (k) , ïîëó÷èì f (X1 , . . . , Xk ) = α0 +α1 (β01 +β11 X1 +βk1 Xk )+. . .+αn (β0n +β1n X1 +βkn Xk ) = (α0 +β01 + . . .+β0n )+(α1 β11 +. . .+αn β1n )X1 +. . .+(α1 βk1 +. . .+αn βkn )Xk = γ0 +γ1 X1 +. . .+γk Xk , ãäå γ0 , γ1 , . . . , γk  çíà÷åíèÿ ñóìì êîíñòàíò â ñîîòâåòñòâóþùèõ ñêîáêàõ. Ñëåäîâàòåëüíî, f ∈ L. (k) Íàêîíåö ðàññìîòðèì êëàññ ìîíîòîííûõ ôóíêöèé. Åñëè g (n) è âñå fi ∈ M è (σ1 , σ2 , . . . , σk ) è (ρ1 , ρ2 , . . . , ρk )  äâà íàáîðà àðãóìåíòîâ òàêèå, ÷òî äëÿ âñåõ j ∈ [1, k] σj ≥ ρj , òî fi (σ1 , σ2 , . . . , σk ) ≥ fi (ρ1 , ρ2 , . . . , ρk ) è ïîýòîìó f (σ1 , σ2 , . . . , σk ) = g(f1 (σ1 , σ2 , . . . , σk ), . . . , fn (σ1 , σ2 , . . . , σk )) ≥ g(f1 (ρ1 , ρ2 , . . . , ρk ), . . . , fn (ρ1 , ρ2 , . . . , ρk )) = f (ρ1 , ρ2 , . . . , ρk ). Òàêèì îáðàçîì, f ∈ M. 2

29

Ñëåäñòâèå 6.1.1. Êëàññû ôóíêöèé S0 , S1 , S, M è L íå ÿâëÿþòñÿ ïîëíûìè. Îêàçûâàåòñÿ, ÷òî âñÿêàÿ ñèñòåìà, íå ñîäåðæàùàÿñÿ âíóòðè îäíîãî èç óêàçàííûõ ïÿòè êëàññîâ ïîëíà.

Òåîðåìà 6.2. (Òåîðåìà Ïîñòà î ïîëíîòå) Ñèñòåìà áóëåâûõ ôóíêöèé F ÿâëÿåòñÿ ïîëíîé òîãäà è òîëüêî òîãäà, êîãäà îíà íå ñîäåðæèòñÿ íè â îäíîì èç êëàññîâ S0 , S1 , S, M è L, ò.å. êîãäà â íåé èìååòñÿ õîòÿ áû îäíà ôóíêöèÿ, íå ñîõðàíÿþùàÿ 0, õîòÿ áû ïî îäíà ôóíêöèÿ, íå ñîõðàíÿþùàÿ 1, õîòÿ áû ïî îäíà íåñàìîäâîéñòâåííàÿ ôóíêöèÿ, õîòÿ áû ïî îäíà íåìîíîòîííàÿ ôóíêöèÿ è õîòÿ áû ïî îäíà íåëèíåéíàÿ ôóíêöèÿ. Äîêàçàòåëüñòâî. Íåîáõîäèìîñòü óñëîâèÿ òåîðåìû íåïîñðåäñòâåííî ñëåäóåò èç óñòàíîâëåííîãî âûøå ñëåäñòâèÿ 6.1.1 íà ñòð. 28. Äëÿ äîêàçàòåëüñòâà äîñòàòî÷íîñòè ïðåäïîëîæèì, ÷òî F ñîäåðæèò íå ñîõðàíÿ(i) (j) þùóþ 0 ôóíêöèþ f0 , íå ñîõðàíÿþùóþ 1 ôóíêöèþ f1 , íåñàìîäâîéñòâåííóþ ôóíê(k) (r) (p) öèþ fs , íåìîíîòîííóþ ôóíêöèþ fm è íåëèíåéíóþ ôóíêöèþ fl . Ïîêàæåì, ÷òî ñ ïîìîùüþ ýòèõ ôóíêöèé âñåãäà ìîæíî âûðàçèòü ôóíêöèè îäíîé èç äâóõ óæå èçâåñòíûõ íàì ïîëíûõ ñèñòåì: {¬, ∧} èëè {¬, ∨}. Äëÿ ýòîãî óñòàíîâèì, ÷òî: 1) èñïîëüçóÿ f0 , f1 è fs , ìîæíî âûðàçèòü êîíñòàíòû 0 è 1; 2) ñ ïîìîùüþ êîíñòàíò èç fm ìîæíî ïîëó÷èòü îòðèöàíèå ¬; 3) ñ ïîìîùüþ êîíñòàíò è îòðèöàíèÿ èç fl ìîæíî ïîëó÷èòü êîíúþíêöèþ ∧ èëè äèçúþíêöèþ ∨.

Ëåììà 6.1. Ôîðìóëàìè, ïîñòðîåííûìè èç ôóíêöèé f0 , f1 è fs , ìîæíî çàäàòü êîíñòàíòû 0 è 1.

Äîêàçàòåëüñòâî. . Ðàññìîòðèì äâà âîçìîæíûõ çíà÷åíèÿ f0 íà íàáîðå àðãóìåíòîâ, ñîñòîÿùåì èç îäíèõ åäèíèö. Ñëó÷àé 1. f0 (1, . . . , 1) = 0. Ðàññìîòðèì ôóíêöèþ g(X), çàäàííóþ ôîðìóëîé f0 (X, . . . , X). Òîãäà, î÷åâèäíî, g(0) = f0 (0, . . . , 0) = 1, à g(1) = f0 (1, . . . , 1) = 0. Òàêèì îáðàçîì, (k) ïîëó÷èëè îòðèöàíèå: g(X) = ¬X . Òàê êàê fs ∈ / S, òî äëÿ íåêîòîðîãî íàáîðà çíà÷åíèé àðãóìåíòîâ (σ1 , . . . , σk ) èìååò ìåñòî ðàâåíñòâî fs (σ1 , . . . , σk ) = fs (¬σ1 , . . . , ¬σk ) = const ∈ {0, 1}. Ïîëîæèì òîãäà h(X) = fs (X σ1 , . . . , X σk ) (òàêàÿ ïîäñòàíîâêà ïåðåìåííîé X 1 è åå îòðèöàíèÿ X 0 âîçìîæíà, òàê êàê ìû óæå ïîëó÷èëè îòðèöàíèå). Òîãäà h  ýòî êîíñòàíòà const. Äåéñòâèòåëüíî, h(1) = fs (1σ1 , . . . , 1σk ) = fs (σ1 , . . . , σk ) = fs (¬σ1 , . . . , ¬σk ) = fs (0σ1 , . . . , 0σk ) = h(0) = const. Äðóãàÿ êîíñòàíòà òîãäà çàäàåòñÿ ôîðìóëîé ¬h(X). Ñëó÷àé 2. f0 (1, . . . , 1) = 1.  ýòîì ñëó÷àå ôîðìóëà f0 (X, . . . , X) çàäàåò ôóíêöèþ g(X), òîæäåñòâåííî ðàâíóþ 1, à ôîðìóëà f1 (g(X), . . . , g(X)) çàäàåò ôóíêöèþ h(X), òîæäåñòâåííî ðàâíóþ 0. Äåéñòâèòåëüíî, h(σ) = f1 (g(σ), . . . , g(σ)) = f1 (1, . . . , 1) = 0 äëÿ ëþáîãî σ ∈ {0, 1}. 2

6

30

Ïîëíûå ñèñòåìû ôóíêöèé è òåîðåìà Ïîñòà

Ëåììà 6.2. Ôîðìóëàìè, ïîñòðîåííûìè èç êîíñòàíò 0 è 1 è íåìîíîòîííîé ôóíê(r)

öèè fm , ìîæíî çàäàòü îòðèöàíèå ¬. (r)

Äîêàçàòåëüñòâî. Òàê êàê fm íåìîíîòîííà, òî èìåþòñÿ äâà ðàçíûõ íàáîðà àðãóìåíòîâ σ ˜ = (σ1 , . . . , σr ) è ρ˜ = (ρ1 , . . . , ρr ) òàêèõ, ÷òî äëÿ âñåõ j ∈ [1, r] σj ≥ ρj è ïðè ýòîì fm (σ1 , σ2 , . . . , σn ) = 0, à fm (ρ1 , ρ2 , . . . , ρn ) = 1. Ïóñòü i1 , . . . , il  ýòî âñå èíäåêñû, äëÿ êîòîðûõ σij = 1 > ρij = 0. Òàê êàê σ ˜ 6= ρ˜, òî l ≥ 1. Îïðåäåëèì ïîñëåäîâàòåëüíîñòü èç (l + 1)-ãî íàáîðà àðãóìåíòîâ ρ˜0 , ρ˜1 , . . . , ρ˜l ñëåäóþùèì îáðàçîì: ρ˜0 = ρ˜, à äàëåå êàæäûé íàáîð ρ˜j ïîëó÷åòñÿ èç ïðåäûäóùåãî ρ˜j−1 çàìåíîé ij -îé êîîðäèíàòû ñ 0 íà 1. Òàêèì îáðàçîì, ïîñëåäíèé èç ýòèõ íàáîðîâ ρ˜l ñîâïàäàåò ñ σ ˜ . Ðàññìîòðèì çíà÷åíèÿ ôóíêöèè fm íà ýòèõ íàáîðàõ: fm (ρ˜0 ), fm (ρ˜1 ), . . . , fm (ρ˜l ). Òàê êàê ïåðâîå èç íèõ fm (ρ˜0 ) = fm (˜ ρ) = 1, à ïîñëåäíåå fm (ρ˜l ) = fm (˜ σ ) = 0, òî íàéäóòñÿ äâà ñîñåäíèõ íàáîðà ρ˜j−1 è ρ˜j òàêèõ, ÷òî fm (˜ ρj−1 ) = 1, à fm (ρ˜j ) = 0. Îíè îòëè÷àþòñÿ òîëüêî ij -îé êîîðäèíàòîé. Ïóñòü ρ˜j−1 = (α1 , . . . , αij −1 , 0, αij +1 , . . . , αr ), a ρ˜j = (α1 , . . . , αij −1 , 1, αij +1 , . . . , αr ). Ïîëîæèì òîãäà g(X) = fm (α1 , . . . , αij −1 , X, αij +1 , . . . , αr ). Òîãäà g(0) = fm (α1 , . . . , αij −1 , 0, αij +1 , . . . , αr ) = 1, a g(1) = fm (α1 , . . . , αij −1 , 1, αij +1 , . . . , αr ) = 0. Ñëåäîâàòåëüíî, g(X) = ¬X. 2

Ëåììà 6.3. Ôîðìóëàìè, ïîñòðîåííûìè èç êîíñòàíò 0 è 1, îòðèöàíèÿ ¬ è íåëè(p)

íåéíîé ôóíêöèè fl

, ìîæíî çàäàòü äèçúþíêöèþ ∨ èëè êîíúþíêöèþ ∧. (p)

Äîêàçàòåëüñòâî. Òàê êàê fl ∈ / L, òî â ïðåäñòàâëÿþùèé åå ìíîãî÷ëåí Æåãàëêèíà îáÿçàòåëüíî âõîäèò ñëàãàåìîå âèäà Xi1 ∗Xi2 ∗. . .∗Xik (k ≥ 2). Âûáåðåì ñàìîå êîðîòêîå èç òàêèõ ñëàãàåìûõ è ðàññìîòðèì ôóíêöèþ g1 (Xi1 , Xi2 ) = fl (σ1 , . . . , σi1 −1 , Xi1 , σi1 +1 , . . . , σi2 −1 , Xi2 , σi2 +1 , . . . , σp ), ãäå σj = 1 ïðè j ∈ {i3 , . . . , ik } è σj = 0 â îñòàëüíûõ ñëó÷àÿõ. Ïðè òàêîé ïîäñòàíîâêå êîíñòàíò ìíîãî÷ëåí Æåãàëêèíà äëÿ g(X1 , X2 ) = g1 (X1 , X2 ) èìååò âèä: α0 + α1 X1 + α2 X2 + X1 ∗ X2 , ãäå α0 , α1 , α2 ∈ {0, 1}. Òàêèì îáðàçîì, âñåãî âîçìîæíî 8 âàðèàíòîâ. Ðàññìîòðèì 4 èç íèõ â ñëó÷àå, êîãäà α0 = 0. Òîãäà 1) ïðè α1 = 0 è α2 = 0 ïîëó÷àåì, ÷òî g(X1 , X2 ) ≡ X1 ∧ X2 ; 2) ïðè α1 = 0 è α2 = 1 ïîëó÷àåì, ÷òî g(¬X1 , X2 ) ≡ X2 + ¬X1 ∗ X2 ≡ (1 + ¬X1 ) ∗ X2 ≡ X1 ∧ X2 ; 3) ïðè α1 = 1 è α2 = 0 ïîëó÷àåì, ÷òî g(X1 , ¬X2 ) ≡ X1 + X1 ∗ ¬X2 ≡ X1 ∗ (1 + ¬X2 ) ≡ X1 ∧ X2 ; 4) ïðè α1 = 1 è α2 = 1 èìååì g(X1 , X2 ) ≡ X1 + X2 + X1 ∗ X2 ≡ X1 ∨ X2 . Îñòàëüíûå 4 âàðèàíòà â ñëó÷àå , êîãäà α0 = 1, ïîëó÷àþòñÿ êàê îòðèöàíèÿ ñîîòâåòñòâóþùèõ âàðèàíòîâ äëÿ α0 = 0. 2 Èç ïðèâåäåííûõ òðåõ ëåìì, î÷åâèäíî, ñëåäóåò äîñòàòî÷íîñòü óñëîâèÿ òåîðåìû Ïîñòà. 2

31

Ïðèìåð 6.2. Ðàññìîòðèì ñëåäóþùèé íàáîð ôóíêöèé. Òàáëèöà 11: Ôóíêöèè f , g è h.

X1 0 0 0 0 1 1 1 1

X2 0 0 1 1 0 0 1 1

X3 0 1 0 1 0 1 0 1

f 1 0 0 1 0 1 1 0

g 1 1 0 0 0 1 1 1

h 0 0 1 0 1 0 1 0

Ôóíêöèÿ f , î÷åâèäíî, íå ñîõðàíÿåò 0 è 1, íî ÿâëÿåòñÿ ñàìîäâîéñòâåííîé. Ôóíêöèÿ g(X1 , X2 , X3 ) = 1 + X1 + X2 + X1 ∗ X3 + X1 ∗ X2 ∗ X3 ÿâëÿåòñÿ íåñàìîäâîéñòâåííîé, íåìîíîòîííîé è íåëèíåéíîé. Ïî ëåììå 6.1 íà ñòð. 29 ïîëó÷àåì, ÷òî f (X, X, X) = ¬X , ôóíêöèÿ g1 (X) = g(X, X, X) ≡ 1, à ôóíêöèÿ g0 (X) = ¬g1 (X) ≡ 0. Ïîäñòàâèâ X2 = 0 â g ïîëó÷èì g3 (X1 , X3 ) = g(X1 , 0, X3 ) = 1 + X1 + X1 ∗ X3 . Òîãäà h(X1 , X2 ) = ¬g3 (X1 , ¬X2 ) = ¬(1+X1 +X1 ∗¬X2 ) ≡ ¬(1+X1 ∗(1+¬X2 )) ≡ X1 ∗X2 . Òàêèì îáðàçîì, ìû ñ ïîìîùüþ f è g ñóìåëè âûðàçèòü îáå ôóíêöèè ïîëíîé ñèñòåìû {¬, ∗(= ∧)} è, ñëåäîâàòåëüíî, ñèñòåìà ôóíêöèé {f, g} ïîëíàÿ.

Îïðåäåëåíèå 6.5. Ïîëíàÿ ñèñòåìà ôóíêöèé íàçûâàåòñÿ ìèíèìàëüíîé ïîëíîé ñèñòåìîé èëè áàçèñîì , åñëè ïîñëå óäàëåíèÿ èç íåå ëþáîé ôóíêöèè îíà ïåðåñòàåò áûòü ïîëíîé.

Íàïðèìåð, ñèñòåìà {¬, ∧, ∨} íå ÿâëÿåòñÿ áàçèñîì, à êàæäàÿ èç ñèñòåì {¬, ∧}, {¬, ∨} ÿâëÿåòñÿ. Ìû óæå çíàåì, ÷òî èìåþòñÿ ïîëíûå ñèñòåìû, ñîñòîÿùèå èç îäíîé ôóíêöèè (íàïðèìåð, ñèñòåìà {|}). Îíè, êîíå÷íî, ÿâëÿþòñÿ áàçèñàìè. Èìåþòñÿ è ïîëíûå ñèñòåìû, âêëþ÷àþùèå 3 ôóíêöèè, íàïðèìåð ñèñòåìà {1, ∗, +}, íà êîòîðîé îñíîâàíû ìíîãî÷ëåíû Æåãàëêèíà (îòìåòèì, ÷òî êîíñòàíòó 0 ìîæíî âûðàçèòü êàê 1+1). Èç òåîðåìû Ïîñòà ñëåäóåò, ÷òî íèêàêàÿ ìèíèìàëüíàÿ ñèñòåìà íå ñîäåðæèò áîëåå 5 ôóíêöèé. Îêàçûâàåòñÿ, ÷òî äëÿ ïîëíîòû âñåãäà äîñòàòî÷íî ÷åòûðåõ ôóíêöèé.

Òåîðåìà 6.3. Âî âñÿêîì áàçèñå F ñîäåðæèòñÿ íå áîëåå 4-õ ôóíêöèé. (i)

f0

Äîêàçàòåëüñòâî. Äåéñòâèòåëüíî, ïî òåîðåìå Ïîñòà â áàçèñå F èìååòñÿ ôóíêöèÿ ∈ / S0 . Ïîýòîìó f0 (0, 0, . . . , 0) = 1. Åñëè îíà õîòÿ áû íà îäíîì íàáîðå çíà÷åíèé

32

6

Ïîëíûå ñèñòåìû ôóíêöèé è òåîðåìà Ïîñòà (i)

àðãóìåíòîâ ïðèíèìàåò çíà÷åíèå 0, òî îíà íåìîíîòîííà, ò.å. f0 ∈ / M.  ïðîòèâíîì ñëó÷àå, f0 íà âñåõ íàáîðàõ çíà÷åíèé àðãóìåíòîâ ðàâíà 1. Íî òîãäà îíà íåñàìîäâîéñòâåííà , òàê êàê f0 (0, 0, . . . , 0) = 1 = f0 (1, 1, . . . , 1). Âî âñåõ ñëó÷àÿõ f0 ∈ / M èëè f0 ∈ / S è, ñëåäîâàòåëüíî, â ñèñòåìå F ñîäåðæèòñÿ íå áîëåå 4-õ ôóíêöèé. 2 Ìîæåò áûòü, â ìèíèìàëüíîé ñèñòåìå ìîæíî îáîéòèñü òðåìÿ ôóíêöèÿìè? Ýòî íå òàê. Ðàñìîòðèì, íàïðèìåð, ñèñòåìó F (4) = {0, 1, X ∧ Y, X + Y + Z}.  ýòîé ñèñòåìå, 0∈ / S1 ∪ S, 1 ∈ / S0 , X + Y + Z ∈ / M, X ∧ Y ∈ / L. Ëåãêî ïðîâåðèòü, ÷òî ïðè óäàëåíèè (4) ëþáîé èç ôóíêöèé ñèñòåìà F ïåðåñòàåò áûòü ïîëíîé. Òàêèì îáðàçîì, òåîðåìà 6.3 íà ñòð. 31 äàåò íàèëó÷øóþ âåðõíþþ îöåíêó ÷èñëà ôóíêöèé â áàçèñå.

Çàìå÷àíèå. Å. Ïîñò â ðàáîòàõ, îïóáëèêîâàííûõ â 1921 è 1941 ãã. óñòàíîâèë íå òîëüêî êðèòåðèé ïîëíîòû, íî è îïèñàë ñòðóêòóðó âñåõ çàìêíóòûõ êëàññîâ ôóíêöèé â P. Îí ïîêàçàë, ÷òî ÷èñëî òàêèõ êëàññîâ ñ÷åòíî è ÷òî â êàæäîì èç íèõ èìååòñÿ ñîáñòâåííûé êîíå÷íûé áàçèñ.

6.1 Çàäà÷è Çàäà÷à 6.1. Äîêàæèòå ïîëíîòó ñèñòåìû {↓}, âêëþ÷àþùåé òîëüêî ñòðåëêó Ïèðñà, íåïîñðåäñòâåííî âûðàçèâ ÷åðåç íåå îòðèöàíèå, äèçúþíêöèþ è êîíúþíêöèþ.

Çàäà÷à 6.2. Îïðåäåëèòå ïðèíàäëåæíîñòü êàæäîé èç ôóíêöèé f1 , f2 , f3 , f4 è f5 , ïðåäñòàâëåííûõ â òàáëèöå 10 íà ñòð. 28, êàæäîìó èç êëàññîâ S0 , S1 , S, L è M.

Çàäà÷à 6.3. Èñïîëüçóÿ ðåçóëüòàòû çàäà÷è 6.2, îïðåäåëèòå, êàêèå èç òðîåê ôóíêöèé, ïðåäñòàâëåííûõ â òàáëèöå 10 íà ñòð. 28, ÿâëÿþòñÿ ïîëíûìè ñèñòåìàìè. Èìåþòñÿ ëè ñðåäè íèõ ïîëíûå ñèñòåìû èç äâóõ ôóíêöèé? Èç îäíîé ôóíêöèè?

Çàäà÷à 6.4. Ïðîâåðüòå ïîëíîòó ñèñòåìû ôóíêöèé {g, h} , ïðåäñòàâëåííûõ â òàáëèöå 11 íà ñòð. 31. Åñëè îíà ïîëíà, âûðàçèòå ñ ïîìîùüþ ýòèõ ôóíêöèé îáå êîíñòàíòû, îòðèöàíèå ¬ è èìïëèêàöèþ →.

Çàäà÷à 6.5. Äîêàæèòå, ÷òî ñèñòåìà {∨, ∧, →} íå ÿâëÿåòñÿ ïîëíîé. Ìîæíî ëè åå ñäåëàòü ïîëíîé, äîáàâèâ íåêîòîðóþ êîíñòàíòó?

Çàäà÷à 6.6. Âûðàçèòå ôóíêöèè {0, 1, ∨, ∧, ∼} ñ ïîìîùüþ ôîðìóë, ïîñòðîåííûõ èç ôóíêöèé ïîëíîé ñèñòåìû {¬, →}.

Çàäà÷à 6.7. Îïðåäåëèòå êîëè÷åñòâî ôóíêöèé èç Pn , ïðèíàäëåæàùèõ êàæäîìó èç êëàññîâ S0 , S1 , S è L.

Çàäà÷à 6.8. Äîêàçàòü, ÷òî äëÿ ìîíîòîííûõ ôóíêöèé f (n) ∈ M ñïðàâåäëèâî ïðåä-

ñòàâëåíèå f (X1 , . . . , Xn ) = (Xi ∧f (X1 , . . . , Xi−1 , 1, Xi+1 , . . . , Xn ))∨f (X1 , . . . , Xi−1 , 0, Xi+1 , . . . , Xn ),

6.1 Çàäà÷è

33

(1 ≤ i ≤ n). Âûâåñòè îòñþäà (èíäóêöèåé ïî n), ÷òî äëÿ âñÿêîé ìîíîòîííîé ôóíêöèè, îòëè÷íîé îò êîíñòàíòû, ñóùåñòâóåò çàäàþùàÿ åå ÄÍÔ, íå ñîäåðæàùàÿ îòðèöàíèé ïåðåìåííûõ. [n/2]

Çàäà÷à 6.9. Äîêàæèòå, ÷òî ÷èñëî ìîíîòîííûõ ôóíêöèé â Pn íå ìåíüøå 2Cn . Çàäà÷à 6.10. Íàéäèòå âñå áàçèñû, êîòîðûå ìîæíî ïîëó÷èòü, óäàëÿÿ ôóíêöèè èç ñèñòåìû {0, 1, ∧, ∨, →}.

Çàäà÷à 6.11. Íàéòè ÷èñëî áóëåâûõ ôóíêöèé îò n ïåðåìåííûõ, ÿâëÿþùèõñÿ îäíîâðåìåííî ñàìîäâîéñòâåííûìè è ëèíåéíûìè.

Çàäà÷à 6.12. Íàéòè ÷èñëî áóëåâûõ ôóíêöèé îò n ïåðåìåííûõ, ÿâëÿþùèõñÿ îäíîâðåìåííî ìîíîòîííûìè è ëèíåéíûìè.

Çàäà÷à 6.13. Äîêàçàòü, ÷òî åñëè f (X1 , . . . , Xn )  ëèíåéíàÿ ôóíêöèÿ, îòëè÷íàÿ îò êîíñòàíòû, òî |Nf+ | = 2n−1 . Âåðíî ëè îáðàòíîå?