D:\User\sbornik_38_pdf\11.DVI


Ìàòåìàòè÷åñêèå âîïðîñû êèáåðíåòèêè è âû÷èñëèòåëüíîé òåõíèêè 38, 26{28, 2012.

Íîâûå ëîãè÷åñêèå ñâÿçêè â ñóïåðèíòóèöèîíèñòñêèõ
ëîãèêàõ: ïîäõîä Ï.Ñ.Íîâèêîâà

À. Ä. ßøèí
Ìîñêîâñêèé ãîðîäñêîé ïñèõîëîãî–ïåäàãîãè÷åñêèé óíèâåðñèòåò

E-mail: yashin.alexandr@ya.ru

 êëàññè÷åñêîé äâóçíà÷íîé, à òàêæå èíòóèöèîíèñòñêîé, ëîãèêå âûñêàçûâàíèé
ðàññìàòðèâàþòñÿ ñòàíäàðòíûå ëîãè÷åñêèå ñâÿçêè _, ^, !, :: Ýêâèâàëåíöèÿ $ ââîäèòñÿ
êàê ñîêðàùåíèå:

A $ B *) ( A ! B ) ^ ( B ! A ) :
Êðîìå òîãî, ìîæíî ââîäèòü â ÿçûê ñòàíäàðòíûå ëîãè÷åñêèå êîíñòàíòû 0 (ëîæü) è 1
(èñòèíà).

Êëàññ F m ôîðìóë ñòðîèòñÿ èíäóêòèâíî èç ïðîïîçèöèîíàëüíûõ ïåðåìåííûõ è
êîíñòàíò ñ ïîìîùüþ ñâÿçîê îáû÷íûì ïóò¸ì.

Ðàçíûå ñïîñîáû ïðåäñòàâëåíèÿ êëàññè÷åñêîé ëîãèêè Cl è èíòóèöèîíèñòñêîé Int
ëîãèê (ñåìàíòè÷åñêèå è äåäóêòèâíûå) õîðîøî èçâåñòíû. Èç íèõ âûòåêàåò, â ÷àñòíîñòè,
âêëþ÷åíèå

Int ½ Cl;
ïðè÷¸ì ýòî âêëþ÷åíèå ñîáñòâåííîå.

Îòìåòèì íåêîòîðûå ñâîéñòâà ýòèõ ëîãèê:
à) Cl è Int çàìêíóòû îòíîñèòåëüíî ïðàâèë ïîäñòàíîâêè è ìîäóñ ïîíåíñ (A; A !

B=B);
á) îáå ñîäåðæàò ò.í. àêñèîìû (ýêâèâàëåíòíîé) çàìåíû äëÿ ñòàíäàðòíûõ ñâÿçîê:
( p $ q ) ! ( :p $ :q ) ,
( p $ q ) ^ ( r $ s) ! ( p ^ r ) $ ( q ^ s) ,
( p $ q ) ^ ( r $ s) ! ( p _ r ) $ ( q _ s) ,
( p $ q ) ^ ( r $ s) ! ( p ! r ) $ ( q ! s) .
Èç ýòèõ àêñèîì âûòåêàåò ñõåìà çàìåíû ýêâèâàëåíòíûõ äëÿ ïðîèçâîëüíûõ ôîðìóë:

( p1 $ q1 ) ^ ¢ ¢ ¢ ^ ( pn $ qn ) ! ( D ( p1; : : : ; pn ) $ D ( q1; : : : ; qn ) ) :

Èç ñõåìû çàìåíû ýêâèâàëåíòíûõ âûòåêàåò çàìêíóòîñòü îòíîñèòåëüíî ïðàâèëà
çàìåíû ýêâèâàëåíòíûõ (íî íå íàîáîðîò!):

( A1 $ B1 ) ^ ¢ ¢ ¢ ^ ( An $ Bn )
D ( A1; : : : ; An ) $ D ( B1; : : : ; Bn )

:

Ñóïåðèíòóèöèîíèñòñêîé ëîãèêîé (ñ.è.ë.) íàçûâàþò ïðîèçâîëüíîå ïîäìíîæåñòâî L ½
F m, âêëþ÷àþùåå èíòóèöèîíèñòñêóþ ïðîïîçèöèîíàëüíóþ ëîãèêó Int è çàìêíóòîå
îòíîñèòåëüíî ïðàâèë modus ponens è ïîäñòàíîâêè.

2 6



À. ßøèí 2 7

×åðåç L + A îáîçíà÷àåòñÿ íàèìåíüøàÿ ñ.è.ë., âêëþ÷àþùàÿ ëîãèêó L è ñîäåðæàùàÿ
ôîðìóëó A.

Ñåìåéñòâî ñ.è.ë àêòèâíî èçó÷àëîñü, â ÷àñòíîñòè, îíî îêàçàëîñü êîíòèíóàëüíûì.
 50-å ãã. 20 â. Ï.Ñ. Íîâèêîâ, ïî âèäèìîìó, èìåÿ â âèäó àêòèâíî ðàçâèâàþùèåñÿ

ðàçäåëû ìîäàëüíîé ëîãèêè (íà îñíîâå êëàññè÷åñêîé äâóçíà÷íîé ëîãèêè), ïîñòàâèë
çàäà÷ó î âîçìîæíîñòè ïðèñîåäèíåíèÿ ê äàííîé ñ.è.ë. (â ÷àñòíîñòè, Int è Cl)
íîâîé îäíîìåñòíîé îïåðàöèè. Ïðè ýòîì îí ïðåäëîæèë ñâîþ òðàêòîâêó ”íîâèçíû” (â
îïóáëèêîâàííûõ ðàáîòàõ ñàìîãî Ï.Ñ.Íîâèêîâà îïèñàíèå åãî ïîäõîäà íàéòè íå óäàëîñü,
èçëîæåíèå îñíîâàíî íà ðàáîòàõ ß.Ñ.Ñìåòàíè÷à [1959,1960]).

Äîáàâèì ê ÿçûêó îäíîìåñòíóþ ñâÿçêó '( ¢ ) , ðàñøèðåííûé êëàññ ôîðìóë îáîçíà÷èì
÷åðåç F m ( ') , ïðè ýòîì ôîðìóëû áåç ' áóäåì íàçûâàòü ÷èñòûìè (ß.Ñ.Ñìåòàíè÷
ïðèìåíÿë òåðìèí ôîðìóëû ÷èñòîé ëîãèêè).

Ïîä '-ëîãèêîé áóäåì ïîíèìàòü ïðîèçâîëüíîå ïîäìíîæåñòâî L ½ F m ( ') ,
âêëþ÷àþùåå Int è çàìêíóòîå îòíîñèòåëüíî ïðàâèë modus ponens, ïîäñòàíîâêè è çàìåíû
ýêâèâàëåíòíûõ (ðàñïðîñòðàí¸ííûå íà ðàñøèðåííûé êëàññ ôîðìóë).

'-Ëîãèêà L íàçûâàåòñÿ êîíñåðâàòèâíûì ðàñøèðåíèåì ñ.è.ëîãèêè L, åñëè äëÿ âñÿêîé
÷èñòîé ôîðìóëû A èç A 2 L ñëåäóåò A 2 L.

Äàëåå, ÿâíûì ñîîòíîøåíèåì äëÿ ' íàçûâàåòñÿ ôîðìóëà âèäà '( p) $ B, ãäå B —
÷èñòàÿ.

Åñòåñòâåííî, ÷òî ñâÿçêà ' ìîæåò ñ÷èòàòüñÿ íîâîé ïî îòíîøåíèþ ê ñòàíäàðòíûì
ñâÿçêàì â '-ëîãèêå L , åñëè ïîñëåäíÿÿ íå ñîäåðæèò íèêàêîãî ÿâíîãî ñîîòíîøåíèÿ äëÿ
'.

Ï.Ñ. Íîâèêîâ ïðåäëàãàåò áîëåå ñèëüíóþ òðàêòîâêó: íå òîëüêî íå ñîäåðæèò ÿâíîãî
ñîîòíîøåíèÿ, íî íèêàêîå ÿâíîå ñîîòíîøåíèå íå ìîæåò áûòü ïðèñîåäèíåíî! Òî÷íàÿ
ôîðìóëèðîâêà òàêîâà:

Ïóñòü L - ñ.è.ë. '-ëîãèêà L îïðåäåëÿåò íîâóþ ëîãè÷åñêóþ ñâÿçêó â L, åñëè âûïîëíåíû
ñëåäóþùèå óñëîâèÿ:

² L ñîäåðæèò àêñèîìó çàìåíû äëÿ ';

² L êîíñåðâàòèâíà íàä L;

² äëÿ ëþáîé ÷èñòîé ôîðìóëû B '-ëîãèêà L + '( p) $ B íå êîíñåðâàòèâíà íàä L
(íåâîçìîæíîñòü ïðèñîåäèíåíèÿ ÿâíûõ ñîîòíîøåíèé).

Ïåðâîå óñëîâèå ââåäåíî, âèäèìî, ïîòîìó, ÷òî äëÿ ñòàíäàðòíûõ ñâÿçîê îíî âûïîëíåíî
(ýòî óñëîâèå ñðàçó îòìåòàåò öåëûé ðÿä êàæóùèõñÿ âîçìîæíûìè ïðèìåðîâ òèïà àíàëîãîâ
êëàññè÷åñêèõ ìîäàëüíîñòåé, ïðåöåäåíòíîå îòðèöàíèå, è äð.). Âòîðîå óñëîâèÿ îçíà÷àåò,
÷òî ñâÿçêà ' ÿâëÿåòñÿ ”ýêñòðàïîíÿòèåì” ïî îòíîøåíèþ ê ”èñõîäíîé òåîðèè” L, è îíî
âìåñòå ñ íîâûìè ñïîñîáàìè óìîçàêëþ÷åíèé íå äîëæíî ”íàðóøàòü” èñõîäíóþ òåîðèþ.
Íàêîíåö, ”íåâîçìîæíîñòü ïðèñîåäèíåíèÿ” òðàêòóåòñÿ ñ òî÷êè çðåíèÿ íàðóøåíèÿ
êîíñåðâàòèâíîñòè.

 óïîìÿíóòûõ âûøå ðàáîòàõ ß.Ñ.Ñìåòàíè÷ ïðèâ¸ë ïðèìåð '-ëîãèêè, îïðåäåëÿþùåé
íîâóþ îäíîìåñòíóþ ñâÿçêó â Int, ïðè÷¸ì ýòà ñâÿçêà îêàçàëàñü êîíñòàíòíîé. À.Â.
Áåññîíîâ [1977] ìîäèôèêàöèåé ïðèìåðà ß.Ñ. Ñìåòàíè÷à ïîêàçàë, ÷òî ñóùåñòâóåò
êîíòèíóóì '-ëîãèê, êàæäàÿ èç êîòîðûõ îïðåäåëÿåò íîâóþ ñâÿçêó â Int.

Êàêèå æå èç '-ëîãèê çàñëóæèâàþò ðàññìîòðåíèÿ? Ï.Ñ. Íîâèêîâ ïðåäëàãàåò
ðàññìîòðåòü ìàêñèìàëüíûå êîíñåðâàòèâíûå ðàñøèðåíèÿ. Èìåííî, '-ëîãèêà L ïîëíà
ïî Íîâèêîâó íàä L, åñëè



2 8 Íîâûå ëîãè÷åñêèå ñâÿçêè â ñóïåðèíòóèöèîíèñòñêèõ ëîãèêàõ: ïîäõîä Ï.Ñ.Íîâèêîâà

² L ñîäåðæèò àêñèîìó çàìåíû äëÿ ';

² L êîíñåðâàòèâíà íàä L;

² äëÿ ëþáîé ôîðìóëû B 2 F m ( ') n L '-ëîãèêà L + B íå êîíñåðâàòèâíà íàä L
(íåâîçìîæíîñòü ïðèñîåäèíåíèÿ íîâûõ àêñèîì).

Ïðîáëåìîé-ìèíèìóì Íîâèêîâà äëÿ L íàçûâàåòñÿ çàäà÷à ïîñòðîåíèÿ ÿâíîãî ïðèìåðà
ïîëíîé íàä L '-ëîãèêè ñ íîâîé ñâÿçêîé. Ïðîáëåìîé ìàêñèìóì íàçûâàåòñÿ çàäà÷à
îïèñàíèÿ âñåãî ñåìåéñòâà ïîïîëíåíèé äëÿ L.

 äîêëàäå ïðåäïîëàãàåòñÿ ðàññêàçàòü î ïðîäâèæåíèÿõ â ðåøåíèè ïðîáëåìû-ìèíèìóì
è ïðîáëåìû-ìàêñèìóì.

Ñïèñîê ëèòåðàòóðû

[1] Ñìåòàíè÷ ß.Ñ. Î ïîëíîòå èñ÷èñëåíèÿ âûñêàçûâàíèé ñ äîïîëíèòåëüíîé îïåðàöèåé
îò îäíîé ïåðåìåííîé// Òð. Ìîñê. ìàòåì. îá-âà.– 1960.–Ò. 9.– Ñ. 357–371.

[2] Ñìåòàíè÷ ß.Ñ. Îá èñ÷èñëåíèÿõ âûñêàçûâàíèé ñ äîïîëíèòåëüíîé îïåðàöèåé//
ÄÀÍ ÑÑÑÐ.– 1959.– Ò. 139, ¹ 2.– Ñ. 309–312.

[3] Áåññîíîâ À.Â. Î íîâûõ îïåðàöèÿõ â èíòóèöèîíèñòñêîì èñ÷èñëåíèè âûñêàçûâàíèé//
Ìàòåì. çàìåòêè.– 1977.– Ò.22. Âûï.1.– Ñ.23–28.