Факультативный курс ''Система автоматизации процесса решения задач''. Часть 2. Построение доказательства

Äìèòðèåâà Ì.Â., Ïàâëîâà Ì.Â. Äìèòðèåâà Ìàðèíà Âàëåðüåâíà Ïàâëîâà Ìàðèàííà Âëàäèìèðîâíà ÔÀÊÓËÜÒÀÒÈÂÍÛÉ ÊÓÐÑ "ÑÈÑÒÅÌÀ ÀÂÒÎÌÀÒÈÇÀÖÈÈ ÏÐÎÖÅÑÑÀ ÐÅØÅÍÈß ÇÀÄÀ×" ×ÀÑÒÜ 2. ÏÎÑÒÐÎÅÍÈÅ

ÄÎÊÀÇÀÒÅËÜÑÒÂÀ

 ïåðâîé ÷àñòè äàííîé ñòàòüè [9] ìû îáñóäèëè íåêîòîðûå ñïîñîáû ðåøåíèÿ çàäà÷, â êîòîðûõ òðåáóåòñÿ îïðåäåëèòü, ñëåäóåò ëè óòâåðæäåíèå G èç èçâåñòíûõ ôàêòîâ F1,F2,....,Fm. Ïî òåîðåìå 2 î ëîãè÷åñêîì ñëåäñòâèè äëÿ ðåøåíèÿ ýòîãî âîïðîñà íàì äîñòàòî÷íî îïðåäåëèòü, ÿâëÿåòñÿ ëè ôîðìóëà F: F1&F2&...Fm&~G ïðîòèâîðå÷èâîé. Ôîðìóëà F íå îáÿçàíà íàõîäèòüñÿ â êîíúþíêòèâíî- íîðìàëüíîé ôîðìå. Íî èçâåñòíî, ÷òî ïî ôîðìóëå F ìîæåò áûòü ïîñòðîåíà ðàâíîçíà÷íàÿ åé ôîðìóëà S, íàõîäÿùàÿñÿ â êîíúþíêòèâíîíîðìàëüíîé ôîðìå. Ôîðìóëà S èìååò âèä S: S1&S2&...&Sn, ãäå Si- äèçúþíêòû. Ìû áóäåì ðàññìàòðèâàòü â äàëüíåéøåì ìíîæåñòâî äèçúþíêòîâ S={S1,S2,...,Sn}. Âñå óòâåðæäåíèÿ Si èìåþò ïðîñòóþ ôîðìó. Íàì íàäî óìåòü îò èçâåñòíûõ ðàññóæäåíèé Si è Sj ïåðåõîäèòü ê íåêîòîðîìó íîâîìó óòâåðæäåíèþ Sk. Ââåäåì ïðàâèëî ðåçîëþöèè, ñîãëàñíî êîòîðîìó ïî äâóì äèçúþíêòàì ìîæíî ïîëó÷àòü òðåòèé. Íàïîìíèì, ÷òî ëèòåðàëîì íàçûâàåòñÿ àòîì èëè åãî îòðèöàíèå. Åñëè ó íàñ åñòü äâà äèçúþíêòà è îäèí èç íèõ ñîäåðæèò ëèòåðàë L, à äðóãîé - ëèòåðàë ~L, òî ìû ìîæåì ðàññìîòðåòü äèçúþíêò, êîòîðûé ñîäåðæèò ëèòåðàëû ïåðâîãî çà èñêëþ÷åíèåì ëèòåðàëà L, è ëèòåðàëû âòîðîãî çà èñêëþ÷åíèåì ~L. Òàêîé äèçúþíêò íàçûâàåòñÿ ðåçîëüâåíòîé ïåðâûõ äâóõ. Íàïðèìåð, åñëè ïåðâûé äèçúþíêò ~A∨C, âòîðîé ~C∨D, òî ðåçîëüâåíòîé áóäåò ôîðìóëà ~A∨D. Åñëè ïåðâûé äèçúþíêò ñîñòîèò èç îäíîãî ëèòåðàëà À, à âòîðîé èç ëèòåðàëà ~A, òî èõ ðåçîëüâåíòîé áóäåò òîæäåñòâåííî- ëîæíûé äèçúþíêò, êîòîðûé, êàê óæå ãîâîðèëîñü, ïðèíÿòî îáîçíà÷àòü ñèìâîëîì o. Òåîðåìà (î ðåçîëüâåíòå). Ðåçîëüâåíòà äâóõ äèçúþíêòîâ ÿâëÿåòñÿ èõ ëîãè÷åñêèì ñëåäñòâèåì. Ðåçîëüâåíòà ïîçâîëÿåò ïåðåõîäèòü îò äâóõ ðàññóæäåíèé ê òðåòüåìó, à òåîðåìà î ðåçîëüâåíòå ãàðàíòèðóåò, ÷òî åñëè èñõîäíûå óòâåðæäåíèÿ áûëè èñòèííûìè, òî èñòèííûì áóäåò è ïîñòðîåííîå óòâåðæäåíèå, òî åñòü ðåçîëüâåíòà. Ïîíÿòèå âûâîäà - ôîðìàëèçîâàííûé àíàëîã ïîíÿòèÿ äîêàçàòåëüñòâà. Ðàññìîòðèì ìíîæåñòâî äèçúþíêòîâ S. Âûâîäîì â S íàçûâàåòñÿ ïîñëåäîâàòåëüíîñòü äèçúþíêòîâ D1,D2,...DN, ãäå êàæäûé Di (i=1,2,...N) ëèáî èç S, ëèáî ÿâëÿåòñÿ ðåçîëüâåíòîé ïðåäûäóùèõ Dj è Dk (j
62

© ÊÎÌÏÜÞÒÅÐÍÛÅ ÈÍÑÒÐÓÌÅÍÒÛ Â ÎÁÐÀÇÎÂÀÍÈÈ. ¹ 3-4, 1998 ã.

Ôàêóëüòàòèâíûé êóðñ «Ñèñòåìà àâòîìàòèçàöèè ïðîöåññà ðåøåíèÿ çàäà÷» Òàêèì îáðàçîì, äëÿ òîãî, ÷òîáû îïðåäåëèòü, ÿâëÿåòñÿ ëè ìíîæåñòâî äèçúþíêòîâ ïðîòèâîðå÷èâûì, äîñòàòî÷íî íàéòè òàêóþ ïîñëåäîâàòåëüíîñòü ðàññóæäåíèé, ãäå êàæäîå ðàññóæäåíèå ñëåäóåò èç äâóõ ðàíåå ðàññìîòðåííûõ, è êîòîðàÿ ïðèâîäèò ê òîæäåñòâåííîëîæíîìó óòâåðæäåíèþ.  êà÷åñòâå ïðèìåðà âûâîäà â ìåòîäå ðåçîëþöèé ðàññìîòðèì çàäà÷ó èç [5]. Ïðèìåð. “Èíñïåêòîð Êðåã ñòðåìèòñÿ ïðè ïîìîùè ëîãè÷åñêèõ ðàññóæäåíèé óñòàíîâèòü èñòèíó. Ðàññìàòðèâàåòñÿ äåëî, â êîòîðîì ÷åòâåðî ïîäñóäèìûõ: A,B,C è D. 1. Åñëè A âèíîâåí, òî B áûë ñîó÷àñòíèêîì (è, ñëåäîâàòåëüíî, âèíîâåí); 2. Åñëè B âèíîâåí, òî ëèáî C áûë ñîó÷àñòíèêîì, ëèáî A íå âèíîâåí; 3. Åñëè D íå âèíîâåí, òî A âèíîâåí è C íå âèíîâåí; 4. Åñëè D âèíîâåí, òî A âèíîâåí. Ñïðàøèâàåòñÿ, âèíîâåí ëè D?” Ïðåäïîëîæèì, ÷òî ÷åðåç A îáîçíà÷àåòñÿ âûñêàçûâàíèå “A- âèíîâåí”; ÷åðåç B: “Bâèíîâåí”; ÷åðåç Ñ: “C- âèíîâåí”; è, íàêîíåö, ÷åðåç D: “D- âèíîâåí”. Çàïèøåì êàæäîå èç óòâåðæäåíèé ôîðìóëîé èñ÷èñëåíèÿ âûñêàçûâàíèé: F1: A⇒B F2: B⇒ ~A∨C F3: ~D⇒ A&~C F4: D⇒A Òðåáóåòñÿ âûÿñíèòü, ñëåäóåò ëè óòâåðæäåíèå D: “D âèíîâåí” èç ýòèõ ÷åòûðåõ. Ïî òåîðåìå 2 íàì äîñòàòî÷íî èññëåäîâàòü íà ïðîòèâîðå÷èâîñòü ñëåäóþùóþ ôîðìóëó F: (A⇒B)&(B⇒~A∨C)&(~D⇒ A&~C)&( D⇒A)& ~D. Ïðèâåäåì ôîðìóëó F ê ÊÍÔ. Ïîëó÷èì ìíîæåñòâî S, ñîñòîÿùåå èç øåñòè äèçúþíêòîâ S1,S2,S3,S4,S5 è S6. S: {~A∨B, ~B∨~A∨C, A∨D, ~C∨D, ~D∨A, ~D}. Ïî òåîðåìå î ïîëíîòå ìåòîäà ðåçîëþöèé, äëÿ òîãî ÷òîáû óñòàíîâèòü ïðîòèâîðå÷èâîñòü S, äîñòàòî÷íî ïîñòðîèòü îïðîâåðæåíèå â S. Îäíî èç îïðîâåðæåíèé ìîæåò áûòü ñëåäóþùèì: S7: ~A∨C, ðåçîëüâåíòà S1 è S2; S8: A, ðåçîëüâåíòà S3 è S6; S9: ~C, ðåçîëüâåíòà S4 è S6; S10: C, ðåçîëüâåíòà S7 è S8; S11: o, ðåçîëüâåíòà S9 è S10; Ïðîöåññ ïîñòðîåíèÿ òàêîé ïîñëåäîâàòåëüíîñòè ðàññóæäåíèé (èëè âûâîäà) ìîæíî àâòîìàòèçèðîâàòü. Îäíàêî î÷åâèäíî, ÷òî ïðè ïîñòðîåíèè âûâîäà â îáùåì ñëó÷àå òðåáóåòñÿ ïðîñìîòð áîëüøîãî ÷èñëà âàðèàíòîâ. Ïîýòîìó â ñèñòåìå ðåàëèçîâàíà òàê íàçûâàåìàÿ ëèíåéíàÿ ðåçîëþöèÿ. Ëèíåéíàÿ ðåçîëþöèÿ ïðîùå îáû÷íîé è ïîçâîëÿåò àâòîìàòèçèðîâàòü ïðîöåññ ïîèñêà ðåøåíèÿ, ïðè÷åì ëèíåéíóþ ðåçîëþöèþ ìîæíî ýôôåêòèâíî ðåàëèçîâàòü. Ïî-ïðåæíåìó, ðàññìàòðèâàåòñÿ ìíîæåñòâî äèçúþíêòîâ S è áåðåòñÿ êàêîé-ëèáî äèçúþíêò Ñ0 èç S, íàçûâàåìûé âåðõíèì. Ñòðîèòñÿ ëèíåéíûé âûâîä äèçúþíêòà ÑN, îáëàäàþùèé ñâîéñòâàìè: 1) äëÿ i=1,2,...,N-1 Ci+1 åñòü ðåçîëüâåíòà äèçúþíêòà Ñi, íàçûâàåìîãî öåíòðàëüíûì è Âi, íàçûâàåìîãî áîêîâûì. 2) êàæäûé Âi ëèáî èç S, ëèáî åñòü Ñj äëÿ íåêîòîðîãî j
63

Äìèòðèåâà Ì.Â., Ïàâëîâà Ì.Â. S8: C∨D, ðåçîëüâåíòà S7 è S3; S9: D, ðåçîëüâåíòà S8 è S4; S10: o, ðåçîëüâåíòà S9 è S6;  ýòîì âûâîäå â êà÷åñòâå âåðõíåãî äèçúþíêòà âçÿò äèçúþíêò S1, äèçúþíêòû S7,S8,S9,S10 ÿâëÿþòñÿ öåíòðàëüíûìè, äèçúþíêòû S2,S3,S4,S6 - áîêîâûìè. Íà ðèñ. 1 è ðèñ. 2 èçîáðàæåíû ñõåìàòè÷íî äâà ïîñëåäíèõ ïîñòðîåííûõ âûâîäà. Ïðåäïîëîæèì, ÷òî ìû âûáðàëè íåêîòîðûé äèçúþíêò Ñ0, òåïåðü ìîæíî âûäåëèòü âñå âîçìîæíûå áîêîâûå äèçúþíêòû. Ïîñëå ïðèìåíåíèÿ ðåçîëþöèè ê Ñ0 ñ ýòèìè áîêîâûìè äèçúþíêòàìè ìû ïîëó÷àåì ðåçîëüâåíòû R1,R2,...,RM. Êàæäûé èç Ðèñóíîê 1. äèçúþíêòîâ Ri ÿâëÿåòñÿ âîçìîæíûì öåíòðàëüíûì äèçúþíêòîì, êîòîðûé ìîæåò ïðèâåñòè ê äîêàçàòåëüñòâó. Åñëè íà ýòîì øàãå îïðîâåðæåíèå ïîëó÷èòü íå óäàëîñü, òî ïðîöåññ ïîâòîðÿåòñÿ. Òàêîé ìåòîä íàçûâàåòñÿ ìåòîäîì ïîèñêà äîêàçàòåëüñòâà â øèðèíó.  íàøåì ïðèìåðå, åñëè â êà÷åñòâå âåðõíåãî äèçúþíêòà âûáðàëè S1, òîãäà áîêîâûìè äèçúþíêòàìè ìîãóò áûòü: S2,S3,S5. Ïîñòðîèì ðåçîëüâåíòó äëÿ êàæäîé èç ïàð (S1,S2), (S1,S3), (S1,S5) è ïîëó÷èì êàíäèäàòîâ íà ñëåäóþùèé öåíòðàëüíûé äèçúþíêò. Åñëè êàêàÿ-ëèáî ðåçîëüâåíòà ïóñòà, òî îïðîâåðæåíèå ïîñòðîåíî è çàäà÷à ðåøåíà, â ïðîòèâíîì ñëó÷àå ïðîöåññ ïîâòîðÿåòñÿ. Äðóãîé ïóòü ïîèñêà äîêàçàòåëüñòâà - ýòî ìåòîä ïîèñêà â ãëóáèíó, òî åñòü íà êàæäîì óðîâíå äåðåâà áåðåòñÿ îäíà âåðøèíà è îñóùåñòâëÿåòñÿ ïåðåõîä ê âåðøèíå áîëåå íèçêîãî óðîâíÿ.  íàøåì ïðèìåðå ïðè ïîèñêå â ãëóáèíó ïîñòóïàåì ñëåäóþùèì îáðàçîì: åñëè âåðõíèé äèçúþíêò S1, áîêîâîé - S2, òî ñòðîèòñÿ ðåçîëüâåíòà S7, îíà ÿâëÿåòñÿ öåíòðàëüíûì äèçúþíêòîì äëÿ ñëåäóþùåãî øàãà è äëÿ íåå èùåì áîêîâîé äèçúþíêò, â íàøåì ñëó÷àå - ýòî äèçúþíêò S3, è ò.ä. Ïðè ïîèñêå â ãëóáèíó ñëåäóåò çàäàòü ãðàíèöó ïîèñêà, ÷òîáû ïðåäîòâðàòèòü ïîèñê äîêàçàòåëüñòâà ïî íåâåðíîìó ïóòè, òî åñòü ïî ïóòè, êîòîðûé íå ìîæåò ïðèâåñòè ê ïóñòîìó äèçúþíêòó.  ïåðâîé âåðñèè ñèñòåìû ðåàëèçîâàíî äâà ìåòîäà. Ñíà÷àëà îñóùåñòâëÿåòñÿ ïîñòðîåíèå ðåøåíèÿ ìåòîäîì ïîèñêà â øèðèíó, òåì ñàìûì ïîñòðîåí ñàìûé êîðîòêèé âûâîä, çàòåì, çàäàâ ãëóáèíó ïîèñêà, äåëàåòñÿ ïîïûòêà îòûñêàòü ðåøåíèå ìåòîäîì ïîèñêà â ãëóáèíó. Äëÿ êàæäîãî èç ýòèõ ìåòîäîâ òðåáîâàëîñü ôèêñèðîâàòü íåêîòîðûå õàðàêòåðèñòèêè ñàìîãî âûâîäà è âðåìÿ ïîèñêà. Ðèñóíîê 2.

64

© ÊÎÌÏÜÞÒÅÐÍÛÅ ÈÍÑÒÐÓÌÅÍÒÛ Â ÎÁÐÀÇÎÂÀÍÈÈ. ¹ 3-4, 1998 ã.

Ôàêóëüòàòèâíûé êóðñ «Ñèñòåìà àâòîìàòèçàöèè ïðîöåññà ðåøåíèÿ çàäà÷» Ðàññìîòðèì åùå îäíó çàäà÷ó. Çàäà÷à ïîëó÷èëà íàçâàíèå “Çàãàäî÷íûé îáâèíèòåëü”. Ñóòü åå â ñëåäóþùåì. Íà îñòðîâå ðûöàðåé è ëæåöîâ çà ñîâåðøåíèå ïðåñòóïëåíèÿ ñóäèëè äâóõ ìåñòíûõ æèòåëåé X è Y. Äåëî íåîáû÷íîå, òàê êàê îá îáâèíèòåëå áûëî èçâåñòíî, ÷òî îí ëèáî ðûöàðü, ëèáî ëæåö. Íà ñóäå îáâèíèòåëü ñäåëàë äâà ñëåäóþùèõ çàÿâëåíèÿ: 1. X âèíîâåí 2. X è Y íå ìîãóò áûòü âèíîâíû îáà. Ê êàêîìó çàêëþ÷åíèþ âû áû ïðèøëè íà ìåñòå ïðèñÿæíûõ? Êòî æå îáâèíèòåëü: ðûöàðü èëè ëæåö? Ïðåäïîëîæèì, ÷òî ìû õîòèì äîêàçàòü, ÷òî îáâèíèòåëü ðûöàðü. Ïóñòü R îáîçíà÷àåò óòâåðæäåíèå “Îáâèíèòåëü - ðûöàðü”, X- “X âèíîâåí ” è Y- “Y âèíîâåí”. Òîãäà èçâåñòíûå ôàêòû ìîæíî çàïèñàòü ñëåäóþùèì îáðàçîì: F1: R⇔ X F2: R⇔(X&~Y∨~X&Y) Ëîãè÷åñêîå ñëåäñòâèå- óòâåðæäåíèå R. Ïî òåîðåìå 2 ñòðîèì ôîðìóëó: (R⇔X)&(R⇔(X&~Y∨~X&Y))&~R. Ïðèâåñòè ýòó ôîðìó ê ÊÍÔ, ïîëó÷èòü ìíîæåñòâî äèçúþíêòîâ è ïîñòðîèòü îïðîâåðæåíèå ÷èòàòåëþ ïðåäîñòàâëÿåòñÿ ñàìîñòîÿòåëüíî. Ñîêðàùåíèå ìíîæåñòâà äèçúþíêòîâ. Ìû èññëåäóåì âîïðîñ, ÿâëÿåòñÿ ëè ïðîòèâîðå÷èâûì ìíîæåñòâî äèçúþíêòîâ S. Îäíàêî ýòî ìíîæåñòâî ìîæåò áûòü äîñòàòî÷íî âåëèêî, ïîýòîìó èñêàòü âûâîä èç áîëüøîãî ìíîæåñòâà äèçúþíêòîâ ìîæåò áûòü çàòðóäíèòåëüíî. Âîçíèêàåò âîïðîñ, ìîæíî ëè êàêíèáóäü ýòî ìíîæåñòâî ñîêðàòèòü? Äåâèñ è Ïàòíåì â [4] ïðåäëîæèëè íåñêîëüêî ïðàâèë, êîòîðûå ïîçâîëÿþò ñîêðàòèòü èñõîäíîå ìíîæåñòâî äèçúþíêòîâ. Ïðàâèëî òàâòîëîãèè. Èç ìíîæåñòâà S ìîæíî âû÷åðêíóòü âñå äèçúþíêòû, êîòîðûå ÿâëÿþòñÿ òàâòîëîãèÿìè. Îñòàâøååñÿ ìíîæåñòâî äèçúþíêòîâ ïðîòèâîðå÷èâî òîãäà è òîëüêî òîãäà, êîãäà ïðîòèâîðå÷èâî ìíîæåñòâî S. Ïðàâèëî îäíîëèòåðíûõ äèçúþíêòîâ. Åñëè â ìíîæåñòâå S åñòü åäèíè÷íûé äèçúþíêò - ëèòåðàë L, òî ìû ìîæåì ïîñòóïèòü òàê: ïîñòðîèòü ìíîæåñòâî äèçúþíêòîâ Z, êîòîðîå ïîëó÷àåòñÿ èç èñõîäíîãî S âû÷åðêèâàíèåì âñåõ äèçúþíêòîâ, ñîäåðæàùèõ ëèòåðàë L. Åñëè ïðè ýòîì îêàæåòñÿ, ÷òî ïîëó÷åííîå ìíîæåñòâî Z ïóñòî, òî ýòî îçíà÷àåò, ÷òî ìíîæåñòâî S íå ïðîòèâîðå÷èâî, èëè, äðóãèìè ñëîâàìè, äîêàçàòåëüñòâî ìîæíî íå èñêàòü, òàê êàê åãî íå ñóùåñòâóåò.  òîì, ÷òî S íå ïðîòèâîðå÷èâî, íåòðóäíî óáåäèòüñÿ, äîñòàòî÷íî âçÿòü èíòåðïðåòàöèþ, â êîòîðîé èñòèíåí ëèòåðàë L. Åñëè æå ìíîæåñòâî Z íå ïóñòî, òî ïîñòðîèì ïî íåìó ìíîæåñòâî T, âû÷åðêíóâ èç äèçúþíêòîâ ìíîæåñòâà Z âñå ëèòåðàëû ~L. Ìîæíî äîêàçàòü, ÷òî ìíîæåñòâî S ïðîòèâîðå÷èâî òîãäà è òîëüêî òîãäà, êîãäà ìíîæåñòâî T ïðîòèâîðå÷èâî.  ìíîæåñòâå T äèçúþíêòîâ è ëèòåðàëîâ ìåíüøå, ÷åì â èñõîäíîì ìíîæåñòâå S. Ðàññìîòðèì ïðèìåð, êîòîðûé ìû óæå ðàññìàòðèâàëè: S={ ~A∨B,~A∨~B∨C,A∨D,~C∨D,A∨~D,~D} Ìû óæå óñòàíîâèëè, ÷òî ìíîæåñòâî S ïðîòèâîðå÷èâî, ïîñòðîèâ îïðîâåðæåíèå â S. Òàê êàê â S åñòü åäèíè÷íûé äèçúþíêò ~D, òî ê S ìîæíî ïðèìåíèòü ïðàâèëî åäèíè÷íîãî äèçúþíêòà. Ñíà÷àëà âû÷åðêíåì èç ìíîæåñòâà S âñå äèçúþíêòû, ñîäåðæàùèå ëèòåðàë ~D. Ïîëó÷èì ìíîæåñòâî äèçúþíêòîâ Z1: Z1={ ~A∨B,~A∨~B∨C,A∨D,~C∨D } Òàê êàê ìíîæåñòâî Z1 íå ïóñòî, òî èç îñòàâøèõñÿ äèçúþíêòîâ âû÷åðêíåì ëèòåðàë D, ïîëó÷èì ìíîæåñòâî T1: T1={ ~A∨B,~A∨~B∨C,A,~C}. Ìíîæåñòâî Ò1 ñîäåðæèò ìåíüÑÖÅÍÀÐÈÈ ÓÐÎÊÎÂ

65

Äìèòðèåâà Ì.Â., Ïàâëîâà Ì.Â. øå ëèòåðàëîâ è ìåíüøåå ÷èñëî äèçúþíêòîâ, ÷åì èñõîäíîå ìíîæåñòâî S.  äàëüíåéøåì ìîæíî èññëåäîâàòü ìíîæåñòâî T1. Ïðàâèëî ÷èñòûõ ëèòåðàëîâ. Ëèòåðàë L íàçûâàåòñÿ ÷èñòûì ëèòåðàëîì, åñëè â S íå âõîäèò ëèòåðàë ~L. Åñëè L- ÷èñòûé ëèòåðàë, òî âû÷åðêèâàåì èç S âñå äèçúþíêòû, ñîäåðæàùèå L. Îñòàâøååñÿ ìíîæåñòâî äèçúþíêòîâ îáîçíà÷èì ÷åðåç S1. Ìíîæåñòâî äèçúþíêòîâ S1 ïðîòèâîðå÷èâî òîãäà è òîëüêî òîãäà, êîãäà ïðîòèâîðå÷èâî ìíîæåñòâî S. Ïðèìåð. S={A∨B∨C, A∨B∨~C , ~B, ~C}. ×èñòûé ëèòåðàë - À. Ìíîæåñòâî ïîñëå ïðèìåíåíèÿ ïðàâèëà ÷èñòîãî ëèòåðàëà: S1={~B, ~C}. Ïðàâèëî ðàñùåïëåíèÿ. Ïóñòü ìíîæåñòâî S ìîæíî ïðåäñòàâèòü â âèäå S={A1∨L,...,Am∨L, B1∨~L,..., Bk∨~L, R1,...,Rq}, ïðè÷åì Ai, Bi, Ri íå ñîäåðæàò íè L, íè ~L. Ðàññìîòðèì äâà ìíîæåñòâà S1={A1, A2,..., Am, R1,..., Rq}; S2={B1, B2,..., Bk, R1,...,, Rq} Ìíîæåñòâî S ïðîòèâîðå÷èâî òîãäà è òîëüêî òîãäà, êîãäà S1 è S2 ïðîòèâîðå÷èâû. Ïðèìåð. Ðàññìîòðèì ìíîæåñòâî äèçúþíêòîâ S è ïðèìåíèì ê íåìó ïðàâèëî ðàñùåïëåíèÿ ïî ëèòåðàëó À. S={~A∨B, ~A ∨~B∨C, A∨D, D∨~C, A∨~D, ~D] Ïîëó÷åííûå ìíîæåñòâà S1={B, ~B∨C, D∨~C, ~D}; S2= {D, ~D, D∨~C} Ìíîæåñòâî S1 ïðîòèâîðå÷èâî. Äîêàçàòü ýòî ìîæíî, ïîñòðîèâ, íàïðèìåð, îïðîâåðæåíèå S5: C -ðåçîëüâåíòà äèçúþíêòîâ B è ~B∨C S6: D -ðåçîëüâåíòà äèçúþíêòîâ C è D∨~C S5: o -ðåçîëüâåíòà äèçúþíêòîâ D è ~D Ìíîæåñòâî S2 ïðîòèâîðå÷èâî, òàê êàê îïðîâåðæåíèå ñòðîèòñÿ ïî äèçúþíêòàì D è ~D.  íåêîòîðûõ ñëó÷àÿõ óäàåòñÿ ðåøèòü çàäà÷ó, èñïîëüçóÿ ëèøü ïðàâèëà ñîêðàùåíèÿ äèçúþíêòîâ. Ïðîäåìîíñòðèðóåì òàêóþ âîçìîæíîñòü ïðè ðåøåíèè ñëåäóþùåé çàäà÷è. Ïåðåä íàìè òðè äåâóøêè: Ñüþ, Ìàðöèÿ è Äèàíà. Ïðåäïîëîæèì, ÷òî èçâåñòíî ñëåäóþùåå: 1) ß ëþáëþ, ïî êðàéíåé ìåðå, îäíó èç ýòèõ òðåõ äåâóøåê. 2) Åñëè ÿ ëþáëþ Ñüþ, à íå Äèàíó, òî ÿ òàêæå ëþáëþ Ìàðöèþ. 3) ß ëèáî ëþáëþ Äèàíó è Ìàðöèþ, ëèáî íå ëþáëþ íè îäíó èç íèõ. 4) Åñëè ÿ ëþáëþ Äèàíó, òî ÿ òàêæå ëþáëþ Ñüþ. Ëþáëþ ëè ÿ Äèàíó? Çàïèøåì ôîðìóëàìè ÷åòûðå âûñêàçûâàíèÿ è ïðåäïîëàãàåìîå ñëåäñòâèå. F1: C∨M∨D F2: C&~D⇒M F3: D&M∨~D&~M F4:D⇒C G:D Ôîðìóëó (C∨M∨D)&(C&~D⇒M)&(D&M∨~D&~M)&(D⇒C)&~D ïðèâåäåì ê êîíúþíêòèâíî - íîðìàëüíîé ôîðìå, ïîëó÷èì èíòåðåñóþùåå íàñ ìíîæåñòâî äèçúþíêòîâ S={C∨M∨D, ~C∨M∨D, M∨~D, ~M∨D, ~D∨C, ~D}.  ìíîæåñòâå S åñòü åäèíè÷íûé äèçú-

66

© ÊÎÌÏÜÞÒÅÐÍÛÅ ÈÍÑÒÐÓÌÅÍÒÛ Â ÎÁÐÀÇÎÂÀÍÈÈ. ¹ 3-4, 1998 ã.

Ôàêóëüòàòèâíûé êóðñ «Ñèñòåìà àâòîìàòèçàöèè ïðîöåññà ðåøåíèÿ çàäà÷» þíêò ~D, ïðèìåíÿåì ïðàâèëî åäèíè÷íîãî äèçúþíêòà ê S, ïîëó÷àåì ìíîæåñòâî {C∨M, ~C∨M, ~M}.  ïîñòðîåííîì ìíîæåñòâå îïÿòü åñòü åäèíè÷íûé äèçúþíêò ~M. Ïîñëå ïðèìåíåíèÿ ïðàâèëà åäèíè÷íîãî äèçúþíêòà ê ýòîìó ìíîæåñòâó ïîëó÷àåì {C, ~C}.  ïîñëåäíåì ìíîæåñòâå òàêæå åñòü åäèíè÷íûé äèçúþíêò, ïîñëå ïðèìåíåíèÿ ïðàâèëà ïîëó÷àåì ïðîòèâîðå÷èâîå ìíîæåñòâî, ñëåäîâàòåëüíî, è èñõîäíîå ìíîæåñòâî S ïðîòèâîðå÷èâî, òî åñòü D - ëîãè÷åñêîå ñëåäñòâèå. Äëÿ äåìîíñòðàöèè ìåòîäîâ ìû ñïåöèàëüíî âûáèðàåì ïðîñòûå ïðèìåðû, áîëåå ñëîæíûå ïðèìåðû “ïîðó÷èì” ðåøàòü ñèñòåìå ïîèñêà äîêàçàòåëüñòâ, îïèñàíèå êîòîðîé ïðèâåäåì â çàêëþ÷èòåëüíîé òðåòüåé ÷àñòè. Ëèòåðàòóðà. 1. Í. Äæ. Íèëüñîí. Ïðèíöèïû èñêóññòâåííîãî èíòåëëåêòà. - Ì.: Ðàäèî è ñâÿçü, 1985. 2. Í. Äæ. Íèëüñîí. Èñêóññòâåííûé èíòåëëåêò. Ìåòîäû ïîèñêà ðåøåíèé. - Ì.: Ìèð, 1973. 3. Ñ.Êëèíè. Ìàòåìàòè÷åñêàÿ ëîãèêà. - Ì.: Mèð, 1973. 4. ×.×åíü, Ð.Ëè. Ìàòåìàòè÷åñêàÿ ëîãèêà è àâòîìàòè÷åñêîå äîêàçàòåëüñòâî òåîðåì. - Ì.: Hàóêà, 1983. 5. Ð.Ñìàëëèàí. Êàê æå íàçûâàåòñÿ ýòà êíèãà? - M.: Mèð, 1981. 6. Ð.Ñìàëëèàí. Ïðèíöåññà èëè òèãð? - Ì.: Ìèð, 1985. 7. Ð.Ñìàëëèàí. Àëèñà â ñòðàíå ñìåêàëêè. - Ì.: Ìèð, 1987. 8. Í.Ê. Êîñîâñêèé. Ýëåìåíòû ìàòåìàòè÷åñêîé ëîãèêè è åå ïðèìåíåíèå ê òåîðèè ñóáðåêóðñèâíûõ àëãîðèòìîâ. - Ë.: Èçä-âî ËÃÓ, 1981. 9. Ì.Â. Äìèòðèåâà, Ì.Â. Ïàâëîâà. Ñèñòåìà àâòîìàòèçàöèè ïðîöåññà ðåøåíèÿ çàäà÷. ×àñòü 1. Æóðíàë “Êîìïüþòåðíûå èíñòðóìåíòû â îáðàçîâàíèè.” ¹2, 1998.

Äìèòðèåâà Ìàðèíà Âàëåðüåâíà, äîöåíò êàôåäðû èíôîðìàòèêè Ñàíêò-Ïåòåðáóðãñêîãî ãîñóäàðñòâåííîãî óíèâåðñèòåòà. Ïàâëîâà Ìàðèàííà Âëàäèìèðîâíà, ñòàðøèé ïðåïîäàâàòåëü êàôåäðû èíôîðìàòèêè ÑÏáÃÓ, ïðåïîäàâàòåëü øêîëû-ëèöåÿ ¹ 419. ÑÖÅÍÀÐÈÈ ÓÐÎÊÎÂ

ÍÀØÈ

ÀÂÒÎÐÛ

67