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

Äìèòðèåâà Ìàðèíà Âàëåðüåâíà Ïàâëîâà Ìàðèàííà Âëàäèìèðîâíà

ÔÀÊÓËÜÒÀÒÈÂÍÛÉ ÊÓÐÑ "ÑÈÑÒÅÌÀ ÀÂÒÎÌÀÒÈÇÀÖÈÈ ÏÐÎÖÅÑÑÀ ÐÅØÅÍÈß ÇÀÄÀ×" ×ÀÑÒÜ 3. ÎÏÈÑÀÍÈÅ ÑÈÑÒÅÌÛ È ÏÐÈÌÅÐÛ ÅÅ ÈÑÏÎËÜÇÎÂÀÍÈß Â íàñòîÿùåå âðåìÿ ðàçðàáîòàíû è ðåàëèçîâàíû íåñêîëüêî âåðñèé ñèñòåìû àâòîìàòèçàöèè ïîèñêà ðåøåíèé.  ñòàòüå ðàññìàòðèâàþòñÿ äâå âåðñèè, ïðåäíàçíà÷åííûå äëÿ ðåøåíèÿ çàäà÷, îïèñûâàåìûõ ôîðìóëàìè èñ÷èñëåíèÿ âûñêàçûâàíèé. Áîëåå ïîçäíèå âåðñèè ïîçâîëÿþò ðåøàòü íåêîòîðûå çàäà÷è, îïèñûâàåìûå ôîðìóëàìè èñ÷èñëåíèÿ ïðåäèêàòîâ.  äâóõ ïðåäûäóùèõ ÷àñòÿõ ýòîé ñòàòüè áûëè îïèñàíû ìàòåìàòè÷åñêèå ìåòîäû, ïîçâîëÿþùèå àâòîìàòèçèðîâàòü ïðîöåññ äîêàçàòåëüñòâà, è ðàññìîòðåíû ðàçëè÷íûå ïðèìåðû. Îäèí èç ýôôåêòèâíûõ ìåòîäîâ, à èìåííî - ëèíåéíûé âûâîä, ðåàëèçîâàí â ñèñòåìå.  íàñòîÿùåå âðåìÿ ðåàëèçîâàí òàêæå ïàêåò äðóãèõ ìåòîäîâ: ìåòîä ñåìàíòè÷åñêîé ðåçîëþöèè, ìåòîä ïîääåðæêè, âõîäíàÿ è åäèíè÷íàÿ ðåçîëþöèè è ò.ä., êîòîðûå ïðè æåëàíèè ìîæíî ïîäêëþ÷èòü ê ñèñòåìå. Ñèñòåìà ðåàëèçîâàíà íà ÿçûêå Turbo Pascal 7.0 ñ èñïîëüçîâàíèåì ñðåäñòâ îáúåêòíî-îðèåíòèðîâàííîãî ïðîãðàììèðîâàíèÿ, äëÿ òîãî, ÷òîáû â äàëüíåéøåì åå ìîæíî áûëî ëåãêî ìîäèôèöèðîâàòü è ïðèìåíèòü äëÿ ðåøåíèÿ äðóãèõ êëàññîâ çàäà÷. Îïèøåì ñíà÷àëà ðàáîòó ñèñòåìû, ôóíêöèîíèðóþùåé ïîä MS DOS. Ðàáîòà ñèñòåìû îðãàíèçîâàíà ñ ïîìîùüþ ìåíþ. Ãëàâíîå ìåíþ ñîäåðæèò òðè ïóíêòà: ïîçâîëÿåò ïåðåéòè ê äâóì ðàçëè÷íûì ðåæèìàì ñèñòåìû èëè âûéòè èç íåå. Ïðè âõîäå â ëþáîé èç ðåæèìîâ ñîîòâåòñòâóþùåå ìåíþ ðåæèìà è ñòðîêà ïîäñêàçêè ñîäåðæàò èíôîðìàöèþ î âñåõ âîçìîæíîñòÿõ, ïðåäîñòàâëÿåìûõ ïîëüçîâàòåëþ äëÿ óñïåøíîé ðàáîòû â äàííîì ðåæèìå. Áàçà äàííûõ ñèñòåìû ñîäåðæèò íàáîð çàäà÷, ðåøåíèå êîòîðûõ ìîæåò áûòü ïðîäåìîíñòðèðîâàíî ïîëüçîâàòåëþ èëè êîòîðûå ïîëüçîâàòåëü ìîæåò ïûòàòüñÿ ðåøèòü ñàìîñòîÿòåëüíî. Ðåæèì ïðîñìîòðà è êîððåêòèðîâêè

ïîçâîëÿåò ïðîñìàòðèâàòü èìåþùèåñÿ â ñèñòåìå çàäà÷è, ïðè æåëàíèè ïîïîëíÿòü ñïèñîê çàäà÷ - äîáàâëÿòü íîâûå èëè èçìåíÿòü óæå èìåþùèåñÿ. Äëÿ êàæäîé çàäà÷è, õðàíÿùåéñÿ â ñèñòåìå, èìååòñÿ ñïèñîê ôîðìóë, îïèñûâàþùèõ óñëîâèÿ çàäà÷è, è ôîðìóëà, êîòîðàÿ ñîîòâåòñòâóåò ëîãè÷åñêîìó ñëåäñòâèþ. Ïîëüçîâàòåëü ïðè ðàáîòå ìîæåò îçíàêîìèòüñÿ êàê ñî ñïèñêîì çàäà÷, òàê è ñ ôîðìóëàìè, îïèñûâàþùèìè ýòè çàäà÷è. Êðîìå òîãî, â ýòîì ðåæèìå ïðåäîñòàâëåíà âîçìîæíîñòü çàïóñòèòü çàäà÷ó íà âûïîëíåíèå, òî åñòü ïîïûòàòüñÿ íàéòè äîêàçàòåëüñòâî ïóòåì ïîñòðîåíèÿ ëèíåéíîãî âûâîäà.  ýòîì ñëó÷àå ñèñòåìà ïðèâîäèò ôîðìóëó, îïèñûâàþùóþ çàäà÷ó, ê êîíúþíêòèâíî-íîðìàëüíîé ôîðìå, è ïîëó÷åííîå ìíîæåñòâî äèçúþíêòîâ âûâîäèò íà ýêðàí. Ïîñòðîåííîå ìíîæåñòâî äèçúþíêòîâ ìîæåò áûòü äîñòàòî÷íî âåëèêî, ïîýòîìó è ïîèñê äîêàçàòåëüñòâà ìîæåò áûòü âåñüìà äîëãèì.  ñèñòåìå ðàçðàáîòàíû ñðåäñòâà, ïîçâîëÿþùèå ñîêðàòèòü ýòî ìíîæåñòâî, èñïîëüçóÿ ïðàâèëà, ïðåäëîæåííûå Äåâèñîì è Ïàòíåìîì. Ïîñëå òîãî, êàê âûïîëíåíû äåéñòâèÿ íàä ìíîæåñòâîì äèçúþíêòîâ, èëè ðåøåíî, ÷òî áóäåò èñïîëüçîâàòüñÿ ïåðâîíà÷àëüíî ïîñòðîåííîå ìíîæåñòâî áåç èçìåíåíèé, ìîæíî îáðàòèòüñÿ ê ñèñòåìå äëÿ ïîèñêà òðåáóåìîãî ðåøåíèÿ, òî åñòü ïîñòðîåíèÿ äîêàçàòåëüñòâà. Ñèñòåìà ìîæåò íàõîäèòü äîêàçàòåëüñòâà äâóìÿ ñïîñîáàìè: ïîñòðîåíèå äîêàçàòåëüñòâà, îïèðàÿñü íà ìåòîä ïîèñêà â øèðèíó (â ýòîì ñëó÷àå äëèíà âûâîäà ìèíèìàëüíà), è íà ìåòîä ïîèñêà â ãëóáèíó. Ïîñòðîåííûå äîêàçàòåëüñòâà ìîãóò áûòü âûâåäåíû íà ýêðàí èëè ñîõðàíåíû â ôàéëå äëÿ äàëüíåéøåãî àíàëèçà. Ñ êàæäûì âûâîäîì (äîêàçàòåëüñòâîì) ôèêñèðóþòñÿ íåêîòîðûå õàðàêòåðèñòèêè âûâîäà: äëèíà âûâîäà; âðåìÿ, çàòðà÷åííîå íà ïî-

53

èñê ðåøåíèÿ; îáùåå ÷èñëî ïîðîæäåííûõ äèçúþíêòîâ; âåëè÷èíà, íàçûâàåìàÿ íàïðàâëåííîñòüþ ïîèñêà è ðàâíàÿ îòíîøåíèþ äëèíû âûâîäà ê îáùåìó ÷èñëó ïîðîæäåííûõ äèçúþíêòîâ. Âòîðîé îñíîâíîé ðåæèì - ðåæèì ñàìîñòîÿòåëüíîãî ðåøåíèÿ. Ïîëüçîâàòåëþ, îáðàòèâøåìóñÿ ê ýòîìó ðåæèìó, ïðåäîñòàâëÿåòñÿ âîçìîæíîñòü äëÿ òåêóùåé çàäà÷è ñàìîñòîÿòåëüíî ââåñòè ôîðìóëû, îïèñûâàþùèå óñëîâèå çàäà÷è. Åñëè ïðè çàäàíèè ôîðìóë ïîëüçîâàòåëü ñîâåðøàåò îøèáêó, òî ñèñòåìà ôèêñèðóåò åå, òðåáóÿ èñïðàâëåíèÿ. Ïðè æåëàíèè ðàçðàáîòàííóþ ñèñòåìó ìîæíî èñïîëüçîâàòü êàê ñèñòåìó, îáó÷àþùóþ çàïèñûâàòü ðàçëè÷íûå óòâåðæäåíèÿ ñ ïîìîùüþ ôîðìóë èñ÷èñëåíèÿ âûñêàçûâàíèé. Äëÿ ýòîãî íàäî ñîçäàòü ôàéë ðàçëè÷íûõ óòâåðæäåíèé, ôàéë ïðàâèëüíûõ îòâåòîâ, è ïîëüçîâàòåëü äëÿ êàæäîãî óòâåðæäåíèÿ ââîäèò ñâîé âàðèàíò îòâåòà, à ñèñòåìà êîíòðîëèðóåò, ïðàâèëüíî ëè ïîñòðîåíà ôîðìóëà, ñîîòâåòñòâóåò ëè îíà ðàññìàòðèâàåìîìó óòâåðæäåíèþ. Ïîñëå òîãî, êàê ôîðìóëû, îïèñûâàþùèå çàäà÷ó, ââåäåíû, ïîëüçîâàòåëü ìîæåò îáðàòèòüñÿ ê ñèñòåìå äëÿ àâòîìàòè÷åñêîãî ïîèñêà ðåøåíèÿ. Êàê è â ïðåäûäóùåì ðåæèìå, ôîðìóëà, îïèñûâàþùàÿ çàäà÷ó, áóäåò ïðåîáðàçîâàíà ê êîíúþíêòèâíîíîðìàëüíîé ôîðìå, òî åñòü áóäåò ïîñòðîåíî ìíîæåñòâî äèçúþíêòîâ. Êàê è ðàíüøå, ýòî ìíîæåñòâî ìîæíî ñîêðàòèòü è îáðàòèòüñÿ ê

Ðèñóíîê 1

54

ñèñòåìå çà ïîèñêîì äîêàçàòåëüñòâà. Äëÿ ðåàëèçàöèè ñëåäóþùåé âåðñèè áûëà âûáðàíà cðåäà ïðîãðàììèðîâàíèÿ Borland Pascal 7.0 äëÿ Windows. Ýêðàí ìîíèòîðà ïðè ðàáîòå ñ ñèñòåìîé âûãëÿäèò òàê, êàê ïîêàçàíî íà ðèñóíêå 1. Ðàáîòà ñèñòåìû îñóùåñòâëÿåòñÿ ñ ïîìîùüþ ìåíþ. Ìåíþ “Çàäà÷à” ïîçâîëÿåò âûáðàòü èç áàçû äàííûõ ñèñòåìû çàäà÷ó äëÿ ðåøåíèÿ. Ïðè íåîáõîäèìîñòè ìîæíî îòðåäàêòèðîâàòü êàê òåêñò çàäà÷è, òàê è ôîðìóëû, îïèñûâàþùèå çàäà÷ó. Äëÿ ýòîãî íàäî âûáðàòü ïóíêò ìåíþ “Ðåäàêòèðîâàíèå”. Ìîæíî âíåñòè â áàçó äàííûõ íîâóþ çàäà÷ó èëè èçìåíèòü èìåþùóþñÿ. Ìåíþ “Ïîèñê” ïðåäîñòàâëÿåò íåêîòîðûå âîçìîæíîñòè äëÿ ïåðåìåùåíèÿ ïî òåêñòó çàäà÷è è ïîèñêà â íåì íóæíîãî ôðàãìåíòà. Ïóíêò ìåíþ “ÊÍԔ èñïîëüçóåòñÿ äëÿ ïîñòðîåíèÿ èñõîäíîãî ìíîæåñòâà äèçúþíêòîâ, ñ êîòîðûì ìîæíî áóäåò ïðîèçâîäèòü äàëüíåéøèå äåéñòâèÿ. Ïîñòðîåííîå ìíîæåñòâî äèçúþíêòîâ ìîæåò áûòü äîñòàòî÷íî âåëèêî, è ïîýòîìó ïðåäîñòàâëÿþòñÿ ñðåäñòâà äëÿ åãî ñîêðàùåíèÿ. Âûáèðàÿ ðàçëè÷íûå ïóíêòû ìåíþ “Ñîêðàùåíèå”, ìîæíî ñîêðàòèòü èññëåäóåìîå ìíîæåñòâî äèçúþíêòîâ ïî ïðàâèëàì Äåâèñà-Ïàòíåìà. Ïîñëå ñîêðàùåíèÿ ìíîæåñòâà äèçúþíêòîâ ìîæíî ïðèñòóïèòü ê ïîèñêó ðåøåíèÿ. Äëÿ ýòîãî ñëåäóåò âûáðàòü ïóíêò ìåíþ “Ðåøåíèå”, à â íåì ìåòîä, êîòîðûì áóäåò îñóùåñòâëÿòüñÿ ïîèñê äîêàçàòåëüñòâà. Ìåíþ “Îêíî” ïîçâîëÿåò ìàíèïóëèðîâàòü îêíàìè: îòîáðàæàòü íà ýêðàí âñå îêíà, ëèáî ðàñïîëàãàòü îòêðûòûå îêíà êàñêàäîì è äð. Ïðè çàïóñêå ñèñòåìû âñå ïóíêòû ìåíþ, êðîìå “Ñîçäàòü” è “Îòêðûòü”, ÿâëÿþòñÿ íåäîñòóïíûìè, òàê êàê íå âûáðàíà çàäà÷à äëÿ ðåøåíèÿ. Ïîñëå âûáîðà çàäà÷è èç áàçû äàííûõ èëè ïîñëå ñîõðàíåíèÿ òîëüêî ÷òî ñîçäàííîé çàäà÷è ñòàíîâèòñÿ äîñòóïíûì ïóíêò ìåíþ “ÊÍԔ. Ñ íåãî íåîáõîäèìî íà÷èíàòü ðåøåíèå ëþáîé çàäà÷è. Ïîñëå ïîñòðîåíèÿ íà÷àëüíîãî ìíîæåñòâà äèçúþíêòîâ ñòàíîâÿòñÿ äîñòóï-

íûìè âñå ïóíêòû ìåíþ. Ïîëüçîâàòåëü ñàì ìîæåò âûáèðàòü ïîñëåäîâàòåëüíîñòü ñîêðàùåíèÿ ìíîæåñòâà äèçúþíêòîâ. Íà ðèñóíêå 1 ðàçìåùåíû îêíà: òåêóùåé çàäà÷è, ôîðìóë, îïèñûâàþùèõ çàäà÷ó, è îêíî, ñîäåðæàùåå èñõîäíîå ìíîæåñòâî äèçúþíêòîâ. Çíàê ‘=’ èñïîëüçóåòñÿ äëÿ ëîãè÷åñêîé ýêâèâàëåíòíîñòè, çíàê ‘>’ äëÿ èìïëèêàöèè è, íàêîíåö, çíàê ‘|’ äëÿ äèçúþíêöèè. ÏÐÈÌÅÐÛ ÈÑÏÎËÜÇÎÂÀÍÈß ÑÈÑÒÅÌÛ

 ñèñòåìå ðåàëèçîâàíà ëèíåéíàÿ ðåçîëþöèÿ, èñïîëüçóþùàÿ òàêèå ïîíÿòèÿ, êàê óïîðÿäî÷åííûé äèçúþíêò è îòðåçàåìûå ëèòåðàëû. Ýòè äâà ïîíÿòèÿ ïîçâîëÿò óëó÷øèòü ëèíåéíóþ ðåçîëþöèþ, òî åñòü ñîêðàòèòü ïîèñê ðåøåíèÿ. Íà ìíîæåñòâå ëèòåðàëîâ, âõîäÿùèõ â äèçúþíêòû, çàäàåòñÿ ïîðÿäîê. Ãîâîðÿò, ÷òî ëèòåðàë L2 áîëüøå, ÷åì ëèòåðàë L1, åñëè L2 ñëåäóåò çà L1 â óïîðÿäî÷åíèè ýòîãî äèçúþíêòà. Äëÿ óïîðÿäî÷åííûõ äèçúþíêòîâ ââîäèòñÿ ïîíÿòèå óïîðÿäî÷åííîé ðåçîëüâåíòû. Åñëè ïðè ïîñòðîåíèè ðåçîëüâåíòû äâà èëè áîëåå ëèòåðàëîâ îäèíàêîâû, òî óïîðÿäî÷åííûé äèçúþíêò ïîëó÷àåòñÿ âûáðàñûâàíèåì âñåõ ëèòåðàëîâ, ñîâïàäàþùèõ ñ ìåíüøèìè. Èíôîðìàöèÿ îá îòðåçàåìûõ ëèòåðàëàõ õðàíèòñÿ îñîáûì îáðàçîì â äèçúþíêòå, è, åñëè ìû ðåøèëè, ÷òî áîêîâûì äèçúþíêòîì äîëæåí áûòü ðàíåå ïîðîæäåííûé öåíòðàëüíûé äèçúþíêò, òî íå íóæíî áóäåò ðåøàòü, êàêîé öåíòðàëüíûé äèçúþíêò èñïîëüçîâàòü, ïðîñòî âûïîëíèì íåêîòîðóþ îïåðàöèþ íàä ýòèì äèçúþíêòîì è ïîëó÷èì íîâûé öåíòðàëüíûé äèçúþíêò. Áîëåå ïîäðîáíî îá óïîðÿäî÷åííûõ äèçúþíêòàõ, î ïðåäñòàâëåíèè îòðåçàåìûõ ëèòåðàëîâ ìîæíî ïðî÷åñòü â ðàáîòå ×åíÿ è Ëè. Îòìåòèì, ÷òî â ñèñòåìå îòðåçàåìûå ëèòåðàëû îáîçíà÷àþòñÿ ìàëåíüêèìè áóêâàìè ëàòèíñêîãî àëôàâèòà. Àëãîðèòì, èñïîëüçóþùèé êàê ïîíÿòèå óïîðÿäî÷åííîãî äèçúþíêòà, òàê è èíôîðìàöèþ îá îòðåçàåìûõ ëèòåðàëàõ, íàçûâàåòñÿ OL-âûâîäîì. Èçëîæèì àëãîðèòì íà ïðèìåðå. Ðàññìîòðèì ñëåäóþùåå ìíîæåñòâî óïîðÿäî÷åííûõ äèçúþíêòîâ: S={A∨B∨C, ~A∨B∨C, ~C, ~B} 1. Íà÷èíàåì âûâîä ñ óïîðÿäî÷åííîãî äèçúþíêòà A∨B∨C. Ïîñëåäíèé ëèòåðàë ýòîãî äèçúþíêòà Ñ, è îí ìîæåò áûòü îòðåçàí â ïðîöåññå

ïðèìåíåíèÿ ïðàâèëà ðåçîëþöèè ñî âòîðîé ïîñûëêîé ~C. Ïîýòîìó, âûïîëíÿÿ ýòî ïðàâèëî è çàïèñûâàÿ ëèòåðàë Ñ â ðàìêó (â îïèñûâàåìîé ñèñòåìå îáðàìëåíèå ñîñòîèò â òîì, ÷òî îáðàìëÿåìûé ëèòåðàë çàïèñûâàåòñÿ ìàëåíüêîé áóêâîé), ìû ïîëó÷àåì óïîðÿäî÷åííóþ ðåçîëüâåíòó A∨B∨c. Òàê êàê çà ëèòåðàëîì ñ íå ñëåäóåò íèêàêîãî íåîáðàìëåííîãî ëèòåðàëà, îí âûáðàñûâàåòñÿ, ïîýòîìó ìû ïîëó÷àåì äèçúþíêò A∨B. 2. Ïîñëåäíèé ëèòåðàë óïîðÿäî÷åííîãî äèçúþíêòà, ïîëó÷åííîãî òîëüêî ÷òî íà ïðåäûäóùåì øàãå, åñòü ëèòåðàë Â, è îí ìîæåò áûòü îòðåçàí âìåñòå ñ ëèòåðàëîì ~B ïðèìåíåíèåì ïðàâèëà ñî âòîðîé ïîñûëêîé ~B. Ïîëó÷àåì äèçúþíêò A. 3. Åäèíñòâåííûé ëèòåðàë óïîðÿäî÷åííîãî äèçúþíêòà, ïîëó÷åííîãî íà ïðåäûäóùåì øàãå, ýòî À. Ñòðîÿ ðåçîëüâåíòó À ñ äèçúþíêòîì ~A∨B∨C, ïîëó÷àåì äèçúþíêò a∨B∨C, îòðåçàåìûé ëèòåðàë îáðàìëåí. 4. Óïîðÿäî÷åííàÿ ðåçîëþöèÿ äèçúþíêòà a∨B∨C è äèçúþíêòà ~C ïðèâåäåò ê ðåçîëüâåíòå a∨B∨c. Òàê êàê çà ëèòåðàëîì ñ íå ñëåäóåò íèêàêîãî íåîáðàìëåííîãî ëèòåðàëà, îí âûáðàñûâàåòñÿ è ïîëó÷àåì äèçúþíêò a∨B. 5. Ïî äèçúþíêòó, ïîëó÷åííîìó íà øàãå 4, è äèçúþíêòó ~B ñòðîèòñÿ ðåçîëüâåíòà a∨b, ñîäåðæàùàÿ äâà îáðàìëåííûõ ëèòåðàëà, êîòîðûå âûáðàñûâàþòñÿ. Ïîëó÷àåì ïóñòîé äèçúþíêò. Ïîñòðîåíèå äîêàçàòåëüñòâà äëÿ äàííîãî ïðèìåðà çàâåðøåíî. Ïðèâåäåì ðåøåíèå äâóõ çàäà÷ ïåðâîé âåðñèè ñèñòåìû. ÒÅÊÓÙÀß ÇÀÄÀ×À: Ôèëîñîôó òðåáóåòñÿ íàéòè êàðòó íà îñòðîâ ñîêðîâèù. Íà ñòîëå ðàçëîæåíû òðè êàðòû: X, Y è Z. Òîëüêî îäíà êàðòà ïîçâîëÿåò íàéòè îñòðîâ.  êîìíàòå íàõîäèòñÿ 5 êîëäóíîâ: A, B, C, D, E, êàæäûé èç êîòîðûõ ëèáî ðûöàðü, ëèáî ëæåö. Êàæäûé êîëäóí äàë ôèëîñîôó ñîâåò: E: ëèáî ÿ ëæåö, ëèáî Ñ è D îäíîòèïíû; A: X- ïðàâèëüíàÿ êàðòà; B: Y - ïðàâèëüíàÿ êàðòà; Ñ: íåâåðíî, ÷òî A è B îáà ëæåöà; D: ëèáî A - ëæåö, ëèáî B - ðûöàðü.

55

Êàêàÿ èç êàðò ïðàâèëüíàÿ? Îáîçíà÷èì ÷åðåç X óòâåðæäåíèå “X - ïðàâèëüíàÿ êàðòà” (àíàëîãè÷íî äëÿ Y,Z), ÷åðåç A - “A - ðûöàðü” (àíàëîãè÷íî äëÿ B, C, D, E). ÐÅØÅÍÈÅ: F1: E<=>~E∨(C<=>D) F2: A<=>X F3: B<=>Y F4: C<=>A∨B F5: D<=>(~A∨B) G: Y ÏÎÐÎÆÄÅÍÎ ÑËÅÄÓÞÙÅÅ ÌÍÎÆÅÑÒÂÎ ÄÈÇÚÞÍÊÒÎÂ: ÄÎ ÏÐÅÎÁÐÀÇÎÂÀÍÈÉ: {E∨C∨D,E∨~C∨D,~E∨~C∨D,E∨C∨~D, ~E∨C∨~D,E∨~C∨~D,~A∨X,A∨~X,~B∨Y,B∨~Y, ~C∨A∨B, C∨~A∨B,C∨A∨~B,C∨~A∨~B, D∨A∨B,~D∨~A∨B,D∨A∨~B,D∨~A∨~B,~Y} ÏÎÑËÅ ÏÐÅÎÁÐÀÇÎÂÀÍÈÉ: ïðàâèëî åäèíè÷íîãî äèçúþíêòà ~Y {E∨C∨D,E∨~C∨D,~E∨~C∨D,E∨C∨~D, ~E∨C∨~D,E∨~C∨~D,~A∨X,A∨~X,~B, ~C∨A∨B, C∨~A∨B,C∨A∨~B,C∨~A∨~B, D∨A∨B,~D∨~A∨B,D∨A∨~B,D∨~A∨~B} ÏÎÑËÅ ÏÐÅÎÁÐÀÇÎÂÀÍÈÉ: ïðàâèëî åäèíè÷íîãî äèçúþíêòà ~B {E∨C∨D,E∨~C∨D,~E∨~C∨D,E∨C∨~D, ~E∨C∨~D,E∨~C∨~D,~A∨X,A∨~X, ~C∨A,C∨~A,D∨A,~D∨~A} ÌÅÒÎÄ ÏÎÈÑÊÀ  ØÈÐÈÍÓ: ÏÐÎÒÈÂÎÐÅ×ÈÅ ÍÀÉÄÅÍÎ OL-ÂÛÂÎÄ: E∨C∨D, E∨C∨~D —> E∨C E∨C, E∨~C∨D —> E∨c∨D E∨c∨D, E∨~C∨~D —> E E, ~E∨~C∨D —> e∨~C∨D e∨~C∨D, ~D∨~A —> e∨~C∨d∨~A e∨~C∨d∨~A, ~C∨A —> e∨~C e∨~C, ~E∨C∨~D —> e∨~c ∨~D e∨~c ∨~D, D∨A —> e∨~c ∨~d∨A e∨~c ∨~d∨A, C∨~A —> o ÄËÈÍÀ ÂÛÂÎÄÀ ÐÀÂÍÀ 9 ÊÎËÈ×ÅÑÒÂÎ ÏÎÐÎÆÄÅÍÍÛÕ ÄÈÇÚÞÍÊÒΠ140 ÍÀÏÐÀÂËÅÍÍÎÑÒÜ ÏÎÈÑÊÀ 0.0643 ÂÐÅÌß ÐÀÁÎÒÛ 00:00:22 ÌÅÒÎÄ ÏÎÈÑÊÀ  ÃËÓÁÈÍÓ:

56

ÏÐÎÒÈÂÎÐÅ×ÈÅ ÍÀÉÄÅÍÎ OL-ÂÛÂÎÄ: E∨C∨D, E∨C∨~D —> E∨C E∨C, ~C∨A —> E∨c∨A E∨c∨A, ~D∨~A —> E∨c∨a∨~D E∨c∨a∨~D, E∨~C∨D —> E E, ~E∨C∨~D —> e∨C∨~D e∨C∨~D, D∨A —> e∨C∨~d∨A e∨C∨~d∨A, C∨~A —> e∨C e∨C, ~C∨A —> e∨c∨A e∨c∨A, ~D∨~A —> e∨c∨a∨~D e∨c∨a∨~D, ~E∨~C∨D —> o ÄËÈÍÀ ÂÛÂÎÄÀ ÐÀÂÍÀ 10 ÊÎËÈ×ÅÑÒÂÎ ÏÎÐÎÆÄÅÍÍÛÕ ÄÈÇÚÞÍÊÒΠ100 ÍÀÏÐÀÂËÅÍÍÎÑÒÜ ÏÎÈÑÊÀ 0.1000 ÂÐÅÌß ÐÀÁÎÒÛ 00:00:11 ÒÅÊÓÙÀß ÇÀÄÀ×À: Òðè áîãèíè çàÿâèëè ñëåäóþùåå: Àôðîäèòà: ß ñàìàÿ ïðåêðàñíàÿ. Àôèíà: Àôðîäèòà íå ñàìàÿ ïðåêðàñíàÿ. Ãåðà: ß ñàìàÿ ïðåêðàñíàÿ. Àôðîäèòà: Ãåðà íå ñàìàÿ ïðåêðàñíàÿ. Àôèíà: ß ñàìàÿ ïðåêðàñíàÿ. Âûñêàçûâàíèå ïðåêðàñíåéøåé èñòèííû. Âûñêàçûâàíèÿ îñòàëüíûõ ëîæíû. Êòî ïðåêðàñíåéøàÿ? Äîêàæèòå! Îáîçíà÷åíèÿ: A - “ïðåêðàñíåéøàÿ Àôðîäèòà”;  - “ïðåêðàñíåéøàÿ Àôèíà”; Ñ - “ïðåêðàñíåéøàÿ Ãåðà”. ÐÅØÅÍÈÅ: F1: A∨B∨C F2:(~A∨~B)&(~A∨~C)&(~B∨~C) F3: A=>(A&A&~C&~C&~B) F4: B=>(~A&~A&~C&C&B) F5: C=>(~A&A&C&C&~B) G: A ÏÎÐÎÆÄÅÍÎ ÑËÅÄÓÞÙÅÅ ÌÍÎÆÅÑÒÂÎ ÄÈÇÚÞÍÊÒÎÂ: ÄÎ ÏÐÅÎÁÐÀÇÎÂÀÍÈÉ: {A∨B∨C, ~A∨~B∨C, ~A∨B∨~C, A∨~B∨~C,~A∨~B∨~C, ~A∨~C∨B,~A∨C∨~B,~A∨~C∨~B,~B∨A∨C, ~B∨~A∨C,~B∨A∨~C,~B∨~A∨~C,~C∨A∨B, ~C∨~A∨B,~C∨A∨~B,~C∨~A∨~B,~A} ÏÎÑËÅ ÏÐÅÎÁÐÀÇÎÂÀÍÈÉ: { B∨C,~B∨~C,~B∨C,~C∨B} ÌÅÒÎÄ ÏÎÈÑÊÀ  ØÈÐÈÍÓ:

ÏÐÎÒÈÂÎÐÅ×ÈÅ ÍÀÉÄÅÍÎ OL-ÂÛÂÎÄ: B∨C, ~C∨B —> B B, ~B∨~C —> b∨~C b∨~C, ~B∨C —> o ÄËÈÍÀ ÂÛÂÎÄÀ ÐÀÂÍÀ 3 ÊÎËÈ×ÅÑÒÂÎ ÏÎÐÎÆÄÅÍÍÛÕ ÄÈÇÚÞÍÊÒΠ5 ÍÀÏÐÀÂËÅÍÍÎÑÒÜ ÏÎÈÑÊÀ 0.6000 ÌÅÒÎÄ ÏÎÈÑÊÀ  ÃËÓÁÈÍÓ: ÏÐÎÒÈÂÎÐÅ×ÈÅ ÍÀÉÄÅÍÎ OL-ÂÛÂÎÄ: B∨C, ~C∨B —> B B, ~B∨C —> b∨C b∨C, ~B∨~C —> o ÄËÈÍÀ ÂÛÂÎÄÀ ÐÀÂÍÀ 3 ÊÎËÈ×ÅÑÒÂÎ ÏÎÐÎÆÄÅÍÍÛÕ ÄÈÇÚÞÍÊÒΠ4 ÍÀÏÐÀÂËÅÍÍÎÑÒÜ ÏÎÈÑÊÀ 0.7500 Íàïîìíèì, ÷òî íà ðèñóíêå 1 óæå áûëè ðàçìåùåíû îêíà äëÿ âåðñèè ñèñòåìû, ôóíêöèîíèðóþùåé ïîä Windows 3.11.  ðåçóëüòàòå ðàáîòû ñèñòåìû ôîðìèðóåòñÿ ôàéë, â êîòîðîì õðàíèòñÿ ïîñëåäîâàòåëüíîñòü ïðåîáðàçîâàíèé ìíîæåñòâà äèçúþíêòîâ è ïîñòðîåííûå âûâîäû. Äëÿ çàäà÷è, óñëîâèå êîòîðîé õðàíèòñÿ â îêíå, èçîáðàæåííîì íà ðèñóíêå 1, áûëà ñôîðìèðîâàíà ñëåäóþùàÿ èíôîðìàöèÿ. Èñõîäíîå ìíîæåñòâî äèçúþíêòîâ èç ôàéëà d:\dmv\grant\13.frm C|F|G,C|~F|G,~C|F|~G,~C|~F|G,A|~X, ~A|X,B|Y|~Z,B|~Y|Z,B|~Y|~Z,~B|Y|Z, A|B|~C,A|~B|~C,~A|B|~C,~A|~B|C,D|~X|~Y, ~D|X|Y,~D|X|~Y,~D|~X|Y, E|~X|~Z,~E|X|Z,~E|X|~Z,~E|~X|Z,D|E|~F, D|~E|F,~D|E|F,~D|~E|F,A|G|H, A|~G|H,A|~G|~H,~A|G|H,~A|~G|H,~X Ìåòîä ïîèñêà â øèðèíó: ïðîòèâîðå÷èå íàéäåíî OL-âûâîä: C|F|G, A|~G|H -> C|F|gAH C|F|gAH, A|~G|~H -> C|F|gA C|F|gA, ~A|X -> C|F|gaX C|F|gaX, ~X -> C|F C|F, C|~F|G -> C|fG C|fG, A|~G|H -> C|fgAH C|fgAH, A|~G|~H -> C|fgA C|fgA, ~A|X -> C|fgaX

C|fgaX, ~X -> C C, A|B|~C -> cA|B cA|B, A|~B|~C -> cA cA, ~A|X -> ca|X ca|X, ~X -> o Çàìåòèì, ÷òî èñõîäíîå ìíîæåñòâî íå ïðåîáðàçîâûâàëîñü è äëèíà ïîëó÷åííîãî âûâîäà ðàâíà 13. Ïðèâåäåì åùå îäíî ðåøåíèå ýòîé çàäà÷è, íî â äàííîì ñëó÷àå âûïîëíèì ïðåîáðàçîâàíèÿ íàä èñõîäíûì ìíîæåñòâîì äèçúþíêòîâ.  ôàéë ðåçóëüòàòà ïîñòóïèò ñëåäóþùàÿ èíôîðìàöèÿ î âûïîëíåííûõ ïðåîáðàçîâàíèÿõ è ïîñòðîåííîì âûâîäå. Èñõîäíîå ìíîæåñòâî äèçúþíêòîâ èç ôàéëà d:\dmv\grant\13.frm C|F|G,C|~F|G,~C|F|~G,~C|~F|G,A|~X, ~A|X,B|Y|~Z,B|~Y|Z,B|~Y|~Z,~B|Y|Z, A|B|~C,A|~B|~C,~A|B|~C,~A|~B|C,D|~X|~Y, ~D|X|Y,~D|X|~Y,~D|~X|Y, E|~X|~Z,~E|X|Z,~E|X|~Z,~E|~X|Z,D|E|~F, D|~E|F,~D|E|F,~D|~E|F,A|G|H, A|~G|H,A|~G|~H,~A|G|H,~A|~G|H,~X Ðåçóëüòàò óïðîùåíèÿ ïî ïðàâèëó åäèíè÷íîãî äèçúþíêòà X: Íîâîå ìíîæåñòâî äèçúþíêòîâ: C|F|G,C|~F|G,~C|F|~G,~C|~F|G,~A,B|Y|~Z, B|~Y|Z,B|~Y|~Z,~B|Y|Z,A|B|~C, A|~B|~C,~A|B|~C,~A|~B|C,~D|Y,~D|~Y, ~E|Z,~E|~Z,D|E|~F,D|~E|F,~D|E|F, ~D|~E|F,A|G|H,A|~G|H,A|~G|~H,~A|G|H,~A|~G|H. ×èñòûõ ëèòåðàëîâ íåò! Ðåçóëüòàò óïðîùåíèÿ ïî ïðàâèëó åäèíè÷íîãî äèçúþíêòà A: Íîâîå ìíîæåñòâî äèçúþíêòîâ: C|F|G,C|~F|G,~C|F|~G,~C|~F|G,B|Y|~Z, B|~Y|Z,B|~Y|~Z,~B|Y|Z,B|~C,~B|~C, ~D|Y,~D|~Y,~E|Z,~E|~Z,D|E|~F,D|~E|F, ~D|E|F,~D|~E|F,G|H,~G|H,~G|~H. Åäèíè÷íûõ äèçúþíêòîâ íåò! Ðåçóëüòàò óïðîùåíèÿ ïî ïðàâèëó òàâòîëîãèè: C|F|G,C|~F|G,~C|F|~G,~C|~F|G,B|Y|~Z, B|~Y|Z,B|~Y|~Z,~B|Y|Z,B|~C,~B|~C, ~D|Y,~D|~Y,~E|Z,~E|~Z,D|E|~F,D|~E|F, ~D|E|F,~D|~E|F,G|H,~G|H,~G|~H. Ìåòîä ïîèñêà â øèðèíó: ïðîòèâîðå÷èå íàéäåíî. OL-âûâîä: C|F|G, ~G|H -> C|F|gH C|F|gH, ~G|~H -> C|F

57

C|F, C|~F|G -> C|fG C|fG, ~G|H -> C|fgH C|fgH, ~G|~H -> C C, B|~C -> cB cB, ~B|~C -> o  ïîñëåäíåì ñëó÷àå äëèíà ïîñòðîåííîãî âûâîäà ðàâíà 7, ê èñõîäíîìó ìíîæåñòâó äèçúþíêòîâ ïðèìåíÿëèñü ïðàâèëà åäèíè÷íîãî äèçúþíêòà, òàâòîëîãèè è ÷èñòîãî ëèòåðàëà. Ïîëüçîâàòåëü ìîæåò ïðîàíàëèçèðîâàòü ïîñòðîåííûå äîêàçàòåëüñòâà, ñðàâíèòü òå, êîòîðûå ñòðîèëèñü ïî èñõîäíîìó ìíîæåñòâó, ñ òåìè, êîòîðûå ñòðîèëèñü ïîñëå ñîêðàùåíèÿ ìíîæåñòâà äèçúþíêòîâ. Ìîæíî ïîïûòàòüñÿ èçìåíèòü ïîðÿäîê ñëåäîâàíèÿ äèçúþíêòîâ ïðè îïèñàíèè çàäà÷è, â ýòîì ñëó÷àå ìîæåò èçìåíèòüñÿ âûâîä, òàê êàê ñòðàòåãèÿ ïîèñêà äîêàçàòåëüñòâ çàâèñèò îò ïîðÿäêà ñëåäîâàíèÿ äèçú-

þíêòîâ. Æåëàþùèå ìîãóò ïîïûòàòüñÿ ðåøèòü ðàññìîòðåííûå çàäà÷è, èñïîëüçóÿ ïðîãðàììó äëÿ ìîäåëèðîâàíèÿ è àíàëèçà åñòåñòâåííûõ ðàññóæäåíèé, ïðåäëîæåííóþ Á.À. Êóëèêîì âî 2 íîìåðå æóðíàëà. Òîãäà ïðè íåñêîëüêî áîëüøåé ïîäãîòîâèòåëüíîé ðàáîòå ïðè çàïèñè óòâåðæäåíèé áóäåò ïîëó÷åí öåëûé ñïèñîê âîçìîæíûõ ëîãè÷åñêèõ ñëåäñòâèé, ÷òî ìîæåò îêàçàòüñÿ óäîáíûì äëÿ çàäà÷ ñ òðóäíî ïðîãíîçèðóåìûì èñõîäîì. Ïîëüçîâàòåëü ìîæåò ïîïðîáîâàòü íàéòè ñîáñòâåííîå ðåøåíèå, à çàòåì ñðàâíèòü åãî ñ ðåøåíèåì, ïîñòðîåííûì ñèñòåìîé. È, íàêîíåö, ìîæíî ïðèäóìûâàòü íîâûå çàäà÷è è ñôîðìèðîâàòü ñâîþ ñîáñòâåííóþ îðèãèíàëüíóþ áàçó äàííûõ. Æåëàåì óñïåõîâ!

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

ÍÀØÈ

58

ÀÂÒÎÐÛ

Äìèòðèåâà Ìàðèíà Âàëåðüåâíà, äîöåíò êàôåäðû èíôîðìàòèêè ÑÏáÃÓ. Ïàâëîâà Ìàðèàííà Âëàäèìèðîâíà, ñòàðøèé ïðåïîäàâàòåëü êàôåäðû èíôîðìàòèêè ÑÏáÃÓ, ïðåïîäàâàòåëü øêîëû-ëèöåÿ ¹ 419.