Логика и исчисление предикатов: Методические указания

Ìèíèñòåðñòâî îáðàçîâàíèÿ Ðîññèéñêîé Ôåäåðàöèè

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

Êàôåäðà íåëèíåéíûõ êîëåáàíèé

ËÎÃÈÊÀ È ÈÑ×ÈÑËÅÍÈÅ ÏÐÅÄÈÊÀÒÎÂ

Ìåòîäè÷åñêèå óêàçàíèÿ äëÿ ñòóäåíòîâ 1 êóðñà ôàêóëüòåòà ïðèêëàäíîé ìàòåìàòèêè è ìåõàíèêè

Ñîñòàâèòåëü: Ò.Ê. Êàöàðàí

Öåëüþ íàñòîÿùåé ìåòîäè÷åñêîé ðàçðàáîòêè, ïîìèìî èçëîæåíèÿ ôàêòè÷åñêîãî ìàòåðèàëà êóðñà "Äèñêðåòíàÿ ìàòåìàòèêà", ÿâëÿåòñÿ ñòàíîâëåíèå è ðàçâèòèå ïîä÷èíåííîãî çàêîíàì ôîðìàëüíîé ëîãèêè ìàòåìàòè÷åñêîãî ìûøëåíèÿ ñòóäåíòîâ. Ïðèâîäèìûå çäåñü äîêàçàòåëüñòâà òåîðåì òèïè÷íû è ôàêòè÷åñêè ÿâëÿþòñÿ óêàçàíèÿìè äëÿ ðåøåíèÿ çàäà÷ ëîãèêè ïðåäèêàòîâ.Îäíà èç òàêèõ çàäà÷ - ïðîâåðêà òîæäåñòâåííîé èñòèííîñòè èëè âûïîëíèìîñòè ïðåäèêàòíûõ ôîðìóë.

Ÿ1.ÔÎÐÌÓËÛ ËÎÃÈÊÈ ÏÐÅÄÈÊÀÒΠ1.Îïðåäåëåíèå ôîðìóëû.Îïèøåì ïðåäâàðèòåëüíî ãðóïïû ñèìâîëîâ, èç êîòîðûõ ñòðîÿòñÿ ïðåäèêàòíûå ôîðìóëû: ïðåäìåòíûå ïåðåìåííûå: x; y; z; xi ; yi ; zi (i 2 N ) - ìàëûå ëàòèíñêèå áóêâû ñ èíäåêñàìè âíèçó èëè áåç íèõ; íóëüìåñòíûå ïðåäèêàòíûå ïåðåìåííûå: P; Q; :::; R; Qi ; Pi , Ri (i 2 N ) - áîëüøèå ëàòèíñêèå áóêâû ñ èíäåêñàìè âíèçó èëè áåç íèõ; n - ìåñòíûå ïðåäèêàòíûå ïåðåìåííûå: P ( ;


; ), Q( ;


; ), R( ;


; ), Pi ( ;


; ), Qi ( ;


; ),Ri ( ;


; )(i 2 N ) ñ óêàçàíèåì ÷èñëà ñâîáîäíûõ ìåñò â íèõ; ëîãè÷åñêèå ñâÿçêè: _; ^; :, !; !; êâàíòîðû: 8; 9; âñïîìîãàòåëüíûå ñèìâîëû: (,) - ñêîáêè,çàïÿòàÿ. Îïèñàííûå ãðóïïû ñèìâîëîâ îáðàçóþò àëôàâèò. Êàæäàÿ ïðåäèêàòíàÿ ôîðìóëà ïðåäñòàâëÿåò ñîáîé ñëîâî èç ñèìâîëîâ ýòîãî àëôàâèòà.Ñëåäóåò èìåòü â âèäó,÷òî íå âñÿêîå ñëîâî ÿâëÿåòñÿ ïðåäèêàòíîé ôîðìóëîé. Îïðåäåëåíèå ôîðìóëû ëîãèêè ïðåäèêàòîâ,ïðèâîäèìîå íèæå, òàêæå êàê îïðåäåëåèå ôîðìóëû ëîãèêè âûñêàçûâàíèé, íîñèò èíäóêòèâíûé õàðàêòåð. 1).Êàæäàÿ íóëüìåñòíàÿ ïðåäèêàòíàÿ ïåðåìåííàÿ åñòü ôîðìóëà. 2).Åñëè P ( ;


; ) - n-ìåñòíàÿ ïðåäèêàòíàÿ ïåðåìåííàÿ,òî P (x1 ;


; xn ) åñòü ôîðìóëà, â êîòîðîé âñå ïðåäìåòíûå ïåðåìåííûå ñâîáîäíû. 3).Åñëè F - ôîðìóëà è x - ïðåäìåòíàÿ ïåðåìåííàÿ, âõîäÿùàÿ â F ñâîáîäíî, òî âûðàæåíèÿ (8x)F è (9x)F òàêæå ÿâëÿþòñÿ ôîðìóëàìè, â êîòîðûõ ïðåäìåòíàÿ ïåðåìåííàÿ x ñâÿçàííàÿ, à âñå îñòàëüíûå ïðåäìåòíûå ïåðåìåííûå, âõîäÿùèå â ôîðìóëó F ñâîáîäíî èëè ñâÿçàííî, îñòàþòñÿ è â íîâûõ ôîðìóëàõ ñîîòâåòñòâåííî òàêèìè æå. 4).Åñëè - F - ôîðìóëà, òî (:F ) - òàêæå ôîðìóëà. Ñâîáîäíûå (ñâÿçàííûå) ïðåäìåòíûå ïåðåìåííûå â ôîðìóëå (:F ) òå è òîëüêî òå, êîòîðûå ÿâëÿþòñÿ ñâîáîäíûìè (ñâÿçàííûìè) â F . 5).Åñëè F1 è F2 ôîðìóëû è åñëè ïðåäìåòíûå ïåðåìåííûå, âõîäÿùèå îäíîâðåìåííî â îáå ôîðìóëû, ñâîáîäíû â êàæäîé èç íèõ, òî âûðàæåíèÿ (F1 ^ F2 ), (F1 _ F2 ), (F1 ! F2 ), (F1 ! F2 ) òàêæå ÿâëÿþòñÿ ôîðìóëàìè. Ïðè ýòîì ïðåäìåòíûå ïåðåìåííûå, ñâîáîäíûå (ñâÿçàííûå) õîòÿ áû â îäíîé èç ôîðìóë, íàçûâàþòñÿ ñâîáîäíûìè (ñâÿçàííûìè) è â íîâûõ ôîðìóëàõ. 6).Íèêàêèõ äðóãèõ ôîðìóë ëîãèêè ïðåäèêàòîâ, êðîìå ïîëó÷àþùèõñÿ ñîãëàñíî ïóíêòàì 1) - 5), íåò. Ôîðìóëû, îïðåäåëåííûå â ïóíêòàõ 1) è 2), íàçûâàþòñÿ ýëåìåíòàðíûìè èëè àòîìàðíûìè. Ôîðìóëû, íå ÿâëÿþùèåñÿ àòîìàðíûìè, íàçûâàþòñÿ ñîñòàâíûìè.

Íàïðèìåð, ôîðìóëû P (x; y; z ); Q(x1 ; x2 ); A; B ÿâëÿþòñÿ ýëåìåíòàðíûìè, à ôîðìóëû (P (x; y ) ! (8x1 )(9z )R(x1 ; y; z )); (9z )Q(x; y; z ) - ñîñòàâíûìè. Ïðè ýòîì â ïåðâîé ñîñòàâíîé ôîðìóëå ïåðåìåííûå x; y ñâîáîäíû, à ïåðåìåííûå x1 ; z - ñâÿçàííûå. Âî âòîðîé ñîñòàâíîé ôîðìóëå ñâîáîäíû äâå ïåðåìåííûå x; y , ïåðåìåííàÿ z ñâÿçàíà. Âûðàæåíèå (9z )(9y )Q(y; z ) ! (8x)A(x; y ) íå ÿâëÿåòñÿ ôîðìóëîé, òàê êàê â íåì ïåðåìåííàÿ y ÿâëÿåòñÿ îäíîâðåìåííî ñâîáîäíîé (âî âòîðîì âõîæäåíèè) è ñâÿçàííîé (â ïåðâîì âõîæäåíèè). Ýòî âûðàæåíèå ñòàíåò ôîðìóëîé, åñëè çàìåíèòü ñâÿçàííóþ ïåðåìåííóþ y êàêîé-íèáóäü áóêâîé, íå âõîäÿùåé â äàííîå âûðàæåíèå, íàïðèìåð, t:

9 )(9 )

(

! (8

t Q(t; z )

z

x)A(x; y ):

Êàê è â àëãåáðå âûñêàçûâàíèé, äîãîâîðèìñÿ âíåøíèå ñêîáêè ó ôîðìóëû íå ïèñàòü, åñëè òîëüêî îíà íå ÿâëÿåòñÿ ÷àñòüþ ñîñòàâíîé ôîðìóëû. Íà îñíîâàíèè ïóíêòîâ 1,4,5 ñôîðìóëèðîâàííîãî îïðåäåëåíèÿ, âñÿêàÿ ôîðìóëà àëãåáðû âûñêàçûâàíèé ÿâëÿåòñÿ ôîðìóëîé ëîãèêè ïðåäèêàòîâ.  ôîðìóëàõ âèäà (8x)F è (9x)F ôîðìóëà F íàçûâàåòñÿ îáëàñòüþ äåéñòâèÿ êâàíòîðîâ îáùíîñòè 8 è ñóùåñòâîâàíèÿ 9 ñîîòâåòñòâåííî. Âõîæäåíèå ïðåäìåòíîé ïåðåìåííîé â ôîðìóëó áóäåò ñâÿçàííûì, åñëè ýòà ïåðåìåííàÿ ñòîèò ïîä çíàêîì êâàíòîðà èëè íàõîäèòñÿ â îáëàñòè äåéñòâèÿ êâàíòîðà ïî ýòîé ïåðåìåííîé. Ôîðìóëû, â êîòîðûõ íåò ñâîáîäíûõ ïðåäìåòíûõ ïåðåìåííûõ, íàçûâàþòñÿ çàìêíóòûìè, à ôîðìóëû, ñîäåðæàùèå ñâîáîäíûå ïðåäìåòíûå ïåðåìåííûå, îòêðûòûìè. Ïðèìåðû çàìêíóòûõ ôîðìóë: Q;

(

8 )(9 )(9 z

y

z )P (x; y; z );

8

(

x)A(x)

x)B (x; y );

A(x; y )

! (9

1 )(8x2 )B (x1 ; x2 ):

x

Ïðèìåðû îòêðûòûõ ôîðìóë: P (x; y; z );

8

(

! (9

z )B (x; y; z ):

2.Èíòåðïðåòàöèÿ ôîðìóë. Åñëè â ôîðìóëó ëîãèêè ïðåäèêàòîâ âìåñòî êàæäîé ïðåäèêàòíîé ïåðåìåííîé ïîäñòàâèòü êîíêðåòíûé ïðåäèêàò, îïðåäåëåííûé íà íåêîòîðîì ìíîæåñòâå M , òî ôîðìóëà ïðåâðàòèòñÿ â êîíêðåòíûé ïðåäèêàò, çàäàííûé íà ýòîì ìíîæåñòâå. Ïðè ýòîì, åñëè íåêîòîðàÿ ôîðìóëà áûëà çàìêíóòîé, òî ïîëó÷åííûé êîíêðåòíûé ïðåäèêàò îêàæåòñÿ íóëüìåñòíûì, ò.å. áóäåò âûñêàçûâàíèåì. Åñëè æå èñõîäíàÿ ôîðìóëà áûëà îòêðûòîé, ò.å. ñîäåðæàëà ñâîáîäíûå âõîæäåíèÿ ïðåäìåòíûõ ïåðåìåííûõ, òî â ðåçóëüòàòå ïîäñòàíîâêè ïîëó÷èì ïðåäèêàò, çàâèñÿùèé îò íåêîòîðûõ ïðåäìåòíûõ ïåðåìåííûõ. Åñëè òåïåðü ïîäñòàâèòü âìåñòî ýòèõ ïðåäìåòíûõ ïåðåìåííûõ êîíêðåòíûå ïðåäìåòû èç ìíîæåñòâà M , òî ïîëó÷åííûé ïðåäèêàò, à â êîíå÷íîì èòîãå èñõîäíàÿ ôîðìóëà, ïðåâðàòèòñÿ â êîíêðåòíîå âûñêàçûâàíèå. Ïðåâðàùåíèå ôîðìóëû â ïðåäèêàò èëè âûñêàçûâàíèå îïèñàííûì âûøå ñïîñîáîì, à òàêæå ïîëó÷åííûå â ðåçóëüòàòå ïðåäèêàòû è âûñêàçûâàíèÿ íàçûâàþòñÿ èíòåðïðåòàöèåé ýòîé ôîðìóëû íà ìíîæåñòâå M . Ïðèìåð 1. Ðàññìîòðèì ðàçëè÷íûå èíòåðïðåòàöèè ñëåäóþùåé çàìêíóòîé ôîðìóëû: (8x)(9y )P (x; y ).  êà÷åñòâå ìíîæåñòâà M âîçüìåì ñîâîêóïíîñòü âñåõ ïðÿìûõ íà ïëîñêîñòè , à âìåñòî ïðåäèêàòíîé ïåðåìåííîé P (x; y ) ïîäñòàâèì êîíêðåòíûé ïðåäèêàò, îïðåäåëåííûé íà M : [ ïðÿìàÿ x ïàðàëëåëüíà ïðÿìîé y ]. Òîãäà èñõîäíàÿ ôîðìóëà ïðåâðàòèòñÿ â ñëåäóþùåå (î÷åâèäíî, èñòèííîå) âûñêàçûâàíèå: "Äëÿ êàæäîé ïðÿìîé íà ïëîñêîñòè ñóùåñòâóåò ïðÿìàÿ, ïàðàëëåëüíàÿ åé". Ýòîé æå ôîðìóëå ìîæíî äàòü äðóãóþ

èíòåðïðåòàöèþ. Âîçüìåì â êà÷åñòâå M ìíîæåñòâî âñåõ ëþäåé, à âìåñòî ïðåäèêàòíîé ïåðåìåííîé P (x; y ) ïîäñòàâèì äâóìåñòíûé ïðåäèêàò : [ó åñòü áðàò x]. Òîãäà èñõîäíàÿ ôîðìóëà ïðåâðàòèòñÿ â ëîæíîå âûñêàçûâàíèå "Ó êàæäîãî ÷åëîâåêà åñòü áðàò". Äàëåå, âîçìåì â êà÷åñòâå M ìíîæåñòâî öåëûõ ÷èñåë, à âìåñòî ïðåäèêàòíîé ïåðåìåííîé P (x; y ) ïîäñòàâèì äâóìåñòíûé ïðåäèêàò [x > y ], îïðåäåëåííûé íà Z . Òîãäà èñõîäíàÿ ôîðìóëà ïðåâðàòèòñÿ â èñòèííîå âûñêàçûâàíèå: "Äëÿ êàæäîãî öåëîãî ÷èñëà ñóùåñòâóåò ìåíüøå åãî öåëîå ÷èñëî". Ïðèìåð 2.Äàäèì èíòåðïðåòàöèþ îòêðûòîé ôîðìóëû

9

(

x)P (x; y; z )

!

Q:

 êà÷åñòâå ìíîæåñòâà M âîçüìåì ìíîæåñòâî R âñåõ äåéñòâèòåëüíûõ ÷èñåë. Âìåñòî ïðåäèêàòíûõ ïåðåìåííûõ P (x; y; z ) è Q ïîäñòàâèì òðåõìåñòíûé ïðåäèêàò [j x j + j y j + j z j< 0], êîòîðûé ÿâëÿåòñÿ òîæäåñòâåííî ëîæíûì, è èñòèííîå âûñêàçûâàíèå [2+2=4], òîãäà ïðåäèêàò (9x)[j x j + j y j + j z j< 0] ! [2 + 2 = 4] ÿâëÿåòñÿ òîæäåñòâåííî èñòèííûì íà R. Ïîäñòàâèâ â ðàññìàòðèâàåìóþ ôîðìóëó âìåñòî ñèìâîëà Q ëþáîå ëîæíîå âûñêàçûâàíèå, íàïðèìåð, [10 - ïðîñòîå ÷èñëî], à âìåñòî àòîìà P (x; y; z ) òîæäåñòâåííî èñòèííûé ïðåäèêàò, ìû ïîëó÷èì òîæäåñòâåííî ëîæíûé ïðåäèêàò . 3.Êëàññèôèêàöèÿ ôîðìóë. Íèæå ïðèâîäÿòñÿ êëàññèôèêàöèîííûå îïðåäåëåíèÿ äëÿ ôîðìóë ëîãèêè ïðåäèêàòîâ. Ôîðìóëà ëîãèêè ïðåäèêàòîâ íàçûâàåòñÿ îáùåçíà÷èìîé èëè òàâòîëîãèåé (òîæäåñòâåííî ëîæíîé èëè ïðîòèâîðå÷èåì), åñëè ëþáàÿ åå èíòåðïðåòàöèÿ ïðåäñòàâëÿåò ñîáîé òîæäåñòâåííî èñòèííûé (òîæäåñòâåííî ëîæíûé) ïðåäèêàò. Ôîðìóëà ëîãèêè ïðåäèêàòîâ íàçûâàåòñÿ âûïîëíèìîé (îïðîâåðæèìîé), åñëè ñóùåñòâóåò òàêàÿ åå èíòåðïðåòàöèÿ, êîòîðàÿ ïðåäñòàâëÿåò ñîáîé âûïîëíèìûé (îïðîâåðæèìûé) ïðåäèêàò. Ïðèâåäåííûå â ïðèìåðàõ 1 è 2 ïðåäûäóùåãî ïóíêòà ôîðìóëû ÿâëÿþòñÿ âûïîëíèìûìè è îïðîâåðæèìûìè îäíîâðåìåííî. Ïðèìåð 3. Ïîêàæåì, ÷òî ôîðìóëà (8y )P (y ) ^ (:P (x)) ÿâëÿåòñÿ ïðîòèâîðå÷èåì. Ïðåäïîëîæèì, ÷òî ýòî íå òàê. Òîãäà íà íåêîòîðîì ìíîæåñòâå M ñóùåñòâóåò ïðåäèêàò A(x) òàêîé, ÷òî ôîðìóëà ïðåâðàùàåòñÿ â âûïîëíèìûé ïðåäèêàò (8y )A(y ) ^ (:A(x)). Ïîñëåäíåå îçíà÷àåò, ÷òî ñóùåñòâóåò ýëåìåíò x0 òàêîé, ÷òî âûñêàçûâàíèå (8y )A(y )^(:A(x0 )) èñòèííî. Èç èñòèííîñòè âûñêàçûâàíèÿ (8y )A(y ) ñëåäóåò, ÷òî A(x0 ) = 1, à èç èñòèííîñòè âûñêàçûâàíèÿ :A(x0 ) ñëåäóåò, ÷òî A(x0 ) = 0. Ìû ïðèøëè ê ïðîòèâîðå÷èþ, êîòîðîå èñêëþ÷àåò ïðåäïîëîæåíèå î âûïîëíèìîñòè èñõîäíîé ôîðìóëû. Ñëåäîâàòåëüíî, îíà òîæäåñòâåííî ëîæíà. Íàõîæäåíèå òàâòîëîãèé ÿâëÿåòñÿ îäíîé èç çàäà÷ ëîãèêè ïðåäèêàòîâ. Òåîðåìà 1. Âñÿêàÿ ôîðìóëà ëîãèêè ïðåäèêàòîâ, ïîëó÷àþùàÿñÿ èç òàâòîëîãèè àëãåáðû âûñêàçûâàíèé çàìåíîé âõîäÿùèõ â íåå áóëåâûõ ïåðåìåííûõ ïðîèçâîëüíûìè ïðåäèêàòíûìè ïåðåìåííûìè, ÿâëÿåòñÿ òàâòîëîãèåé ëîãèêè ïðåäèêàòîâ.

Äîêàçàòåëüñòâî î÷åâèäíî.

Ÿ2.ÒÀÂÒÎËÎÃÈÈ ËÎÃÈÊÈ ÏÐÅÄÈÊÀÒΠ ïðåäûäóùåì ïàðàãðàôå ãîâîðèëîñü î ïîëó÷åíèè òàâòîëîãèé ëîãèêè ïðåäèêàòîâ èç òàâòîëîãèé àëãåáðû âûñêàçûâàíèé. Çäåñü ïðèâîäÿòñÿ íàèáîëåå âàæíûå òàâòîëîãèè ëî-

ãèêè ïðåäèêàòîâ, íå ñâîäÿùèåñÿ ê òàâòîëîãèÿì àëãåáðû âûñêàçûâàíèé. Âñå òàâòîëîãèè ñîäåðæàò êâàíòîðû. Teopeìà 2(çàêîíû äå Ìîðãàíà äëÿ êâàíòîðîâ). Ñëåäóþùèå ôîðìóëû ëîãèêè ïðåäèêàòîâ ÿâëÿþòñÿ òàâòîëîãèÿìè:

à):(8x)P (x)

! (9 )(: ! (8 )(:

á):(9x)P (x)

x

P (x));

(1)

x

P (x)):

(2)

Ôîðìóëû à) è á) çàìêíóòû, ò.å. íå ñîäåðæàò ñâîáîäíûõ ïðåäìåòíûõ ïåðåìåííûõ. Ïîýòîìó, ïîäñòàâèâ â ýòè ôîðìóëû âìåñòî ïðåäèêàòíîé ïåðåìåííîé P (x) ëþáîé êîíêðåòíûé îäíîìåñòíûé ïðåäèêàò P  (x), îïðåäåëåííûé íà íåêîòîðîì ìíîæåñòâå M , ïîëó÷èì âûñêàçûâàíèÿ à):(8x)P  (x) ! (9x)(:P  (x)); á):(9x)P  (x)

! (8 )(: x

P



(x)):

Âûñêàçûâàíèå à) èñòèííî òîãäà è òîëüêî òîãäà,êîãäà âûñêàçûâàíèÿ :(9x)P  (x) è (8x)(:P  (x)) îäíîâðåìåííî èñòèííû èëè îäíîâðåìåííî ëîæíû. Äåéñòâèòåëüíî, âûñêàçûâàíèå :(9x)P  (x) èñòèííî òîãäà è òîëüêî òîãäà, êîãäà âûñêàçûâàíèå (9x)P  (x) ëîæíî, ÷òî âîçìîæíî â òîì è òîëüêî â òîì ñëó÷àå, íà îñíîâàíèè îïðåäåëåíèÿ êâàíòîðà ñóùåñòâîâàíèÿ, êîãäà ïðåäèêàò P  (x) ÿâëÿåòñÿ òîæäåñòâåííî ëîæíûì íà M . Èç òîæäåñòâåííîé ëîæíîñòè ïðåäèêàòà P  (x) ñëåäóåò òîæäåñòâåííàÿ èñòèííîñòü ïðåäèêàòà :P (x) è èñòèííîñòü âûñêàçûâàíèÿ (8x):P  (x). Èòàê, âûñêàçûâàíèå :(9x)P  (x) èñòèííî òîãäà è òîëüêî òîãäà, êîãäà èñòèííî âûñêàçûâàíèå (8x):P  (x), ÷òî è äîêàçûâàåò òàâòîëîãèþ à). Ïðîâåäåííîå äîêàçàòåëüñòâî ìîæíî êðàòêî èçëîæèòü â âèäå ñëåäóþùåé ñõåìû:

:(9

() (9 )  ( ) = 0 () ( )  0 () :  ( )  1 () (8 )(: ( )) = 1

x)P



(x) = 1 P

x P

x

x

P

x

P

x

x

:

Äîêàçàòåëüñòâî òàâòîëîãèè á) ïðîâîäèòñÿ ïî ñõåìå:

:(8 )  ( ) = 0 () (8 ) ( ) = 1   )  1 () : ( )  0 () (9 )(: ( x P

()

P



(x

x

x P

P

x

x

x

P

x))

= 0:

Òåîðåìà äîêàçàíà. Èç òàâòîëîãèé (1) è (2) äîêàçàííîé òåðåìû ñ èñïîëüçîâàíèåì çàêîíà äâîéíîãî îòðèöàíèÿ ïîëó÷àþòñÿ òàâòîëîãèè,âûðàæàþùèå êâàíòîðû äðóã ÷åðåç äðóãà:

9 (8

(

x)P (x) x)P (x)

! (:(8 )(: ! (:(9 )(: x

P (x)));

(3)

x

P (x))):

(4)

Òåîðåìà 3 (çàêîíû ïðîíåñåíèÿ êâàíòîðîâ ÷åðåç êîíúþíêöèþ è äèçúþíêöèþ). Ñëåäóþùèå ôîðìóëû ëîãèêè ïðåäèêàòîâ ÿâëÿþòñÿ òàâòîëîãèÿìè:

8 (9 (

^ )_

x)(P (x)

Q(x))

x)(P (x

Q(x))

! (8 ! (9

^ (8 ) _ (9

x)P (x)

x)Q(x);

(5)

x)P (x

x)Q(x);

(6)

8 (9 (

_ )^

x)(P (x)

Q)

x)(P (x

Q)

! (8 ! (9

_ )^

x)P (x)

Q;

(7)

x)P (x

Q:

(8)

Äîêàçàòåëüñòâî.Äîêàæåì îäíó èç òàâòîëîãèé (5)-(8),íàïðèìåð, òàâòîëîãèþ (6). Äëÿ ýòîãî ïîäñòàâèì âìåñòî ïðåäêàòíûõ ïåðåìåííûõ P (x) è Q(x) êîíêðåòíûå ïðåäèêàòû   P (x) è Q (x), îïðåäåëåííûå íà íåêîòîðîì ìíîæåñòâå M . Ôîðìóëà ïðåâðàòèòñÿ â âûñêàçûâàíèå

9

(

x)(P



_

(x)

Q



! (9

(x))



x)P

(x)

_ (9

x)Q



(x);

(9)

êîòîðîå èñòèííî òîãäà è òîëüêî òîãäà, êîãäà âûñêàçûâàíèÿ (9x)(P  (x) _ Q (x)) è (9x)P  (x) _ (9x)Q (x) îäíîâðåìåííî èñòèííû èëè îäíîâðåìåííî ëîæíû. Èç îïðåäåëåíèÿ êâàíòîðà ñóùåñòâîâàíèÿ ñëåäóåò,÷òî âûñêàçûâàíèå (9x)(P  (x) _ Q (x)) ëîæíî òîãäà è òîëüêî òîãäà, êîãäà îäíîìåñòíûé ïðåäèêàò P  (x) _ Q (x) òîæäåñòâåííî ëîæåí. Èç òîæäåñòâåííîé ëîæíîñòè äèçúþíêöèè ïðåäèêàòîâ âûòåêàåò òîæäåñòâåííàÿ ëîæíîñòü êàæäîãî äèçúþíêòèâíîãî ñëàãàåìîãî: P  (x)  0 è Q (x)  0. Èç òîæäåñòâåííîé ëîæíîñòè ïðåäèêàòîâ P  (x) è Q (x) âûòåêàåò ëîæíîñòü âûñêàçûâàíèé (9x)P  (x), (9x)Q (x) è íàîáîðîò. Äèçúþíêöèÿ ýòèõ âûñêàçûâàíèé , êàê è ëþáûõ äðóãèõ âûñêàçûâàíèé,ëîæíà òîãäà è òîëüêî òîãäà, êîãäà îáà îíè ëîæíû. Ñõåìàòè÷íî ïðîâåäåííûå ðàññóæäåíèÿ âûãëÿäÿò ñëåäóþùèì îáðàçîì:

9 )( )0

(

()

P



x

P

(x

() è  ( )  0 () (9 ) () (9 )  ( ) _ (9 ) 

(x)

Q

_



Q

(x)) = 0

x

x P

x P

x



P



_



Q

0  (9 ) (

(x )

è

(x) = 0



x Q

(x)

x Q

x)

=0

(x) = 0:

Òàâòîëîãèè (7) è (8) îòëè÷àþòñÿ îò (5) è (6) òåì, ÷òî â íèõ àòîìàðíàÿ ôîðìóëà Q íå ñîäåðæèò x â êà÷åñòâå ñâîáîäíîé ïåðåìåííîé è ëþáàÿ åå èíòåðïðåòàöèÿ â ðàññìàòðèâàåìîì ñëó÷àå ïðåäñòàâëÿåò ñîáîé âûñêàçûâàíèå, êîòîðîå îáîçíà÷èì Q . Ñõåìà äîêàçàòåëüñòâà òàâòîëîãèè (7) ñëåäóþùàÿ

8

(

_ () (8

x)(P



(x)



Q

)=1

x)P



()

(x) = 1

P



(x)

èëè

_

 1 () ( )  1   = 1 () (8 ) ( )_ 

Q

P

Q

x P

èëè

x

x



Q



Q

=1

= 1:

Àíàëîãè÷íî äîêàçûâàþòñÿ è äðóãèå òàâòîëîãèè - çàêîíû ïðîíåñåíèÿ êâàíòîðîâ ÷åðåç êîíúþíêöèþ è äèçúþíêöèþ. Òåîðåìà 4(çàêîíû ïðîíåñåíèÿ êâàíòîðîâ ÷åðåç èìïëèêàöèþ). Ñëåäóþùèå ôîðìóëû ëîãèêè ïðåäèêàòîâ ÿâëÿþòñÿ òàâòîëîãèÿìè:

8 (9 (8 (9

(

x)(P (x) x)(P (x) x)(Q x)(Q

! !

! !

Q) Q)

P (x)) P (x))

! ((9 ) ( ) ! ! ((8 ) ( ) ! ! ( ! (8 ) ( ! ( ! (9 ) ( x P x

Q);

(10)

x P x

Q);

(11)

Q

x P x));

(12)

Q

x P x)):

(13)

Äîêàçàòåëüñòâà òàâòîëîãèé (10) - (13) îñíîâàíû íà ñâîéñòâàõ îïåðàöèé èìïëèêàöèè è ýêâèâàëåíöèè è íà îïðåäåëåíèÿõ êâàíòîðîâ îáùíîñòè è ñóùåñòâîâàíèÿ. Äîêàæåì äëÿ ïðèìåðà òàâòîëîãèþ (12).Ïðåäïîëîæèì îáðàòíîå - ôîðìóëà (12) íå ÿâëÿåòñÿ òàâòîëîãèåé. Òîãäà ñóùåñòâóåò åå èíòåðïðåòàöèÿ, êîòîðàÿ íå ÿâëÿåòñÿ òîæäåñòâåííî èñòèííûì ïðåäèêàòîì. Îáîçíà÷èì ÷åðåç P  (x) è Q ïðåäèêàòû, çàìåíÿþùèå àòîìàðíûå ôîðìóëû

è Q â ýòîé èíòåðïðåòàöèè, ÷åðåç M îáîçíà÷èì ìíîæåñòâî, íà êîòîðîì îïðåäåëåíû ïðåäèêàòû P  (x) è Q . Îáà ýòè ïðåäèêàòà ìîãóò çàâèñåòü îò ëþáîãî ÷èñëà ïåðåìåííûõ, ñóùåñòâåííûì ÿâëÿåòñÿ òî, ÷òî ïðåäèêàò Q íå ñîäåðæèò ïåðåìåííîé x â êà÷åñòâå ñâîáîäíîé (ñâÿçàííóþ ïåðåìåííóþ ìîæíî îáîçíà÷èòü äðóãîé áóêâîé). Ïîäñòàâèì â ïðåäèêàòû P  (x) è Q âìåñòî âñåõ ïðåäìåòíûõ ïåðåìåííûõ, êðîìå ïåðåìåííîé x, êîíêðåòíûå ïðåäìåòû èç ìíîæåñòâà M . Òîãäà P  (x) è Q ïðåâðàòÿòñÿ ñîîòâåòñòâåííî â îäíîìåñòíûé ïðåäèêàò è âûñêàçûâàíèå. Ñîãëàñíî ñäåëàííîìó ïðåäïîëîæåíèþ,âûñêàçûâàíèå P (x)

8

(

!



x)(Q



P

!(

(x))

Q



! (8

x)(P



(x))

ÿâëÿåòñÿ ëîæíûì. Ýêâèâàëåíöèÿ ëîæíà, êîãäà åå ÷ëåíû ïðèíèìàþò ðàçíûå çíà÷åíèÿ èñòèííîñòè. Çäåñü ìîãóò ïðåäñòàâèòüñÿ äâå âîçìîæíîñòè. Ïåðâàÿ:

8



!

8



!

(

è âòîðàÿ:

x)(Q

(

x)(Q

P

P





! (8







! (8



(x)) = 1; (Q

x)P

(x)) = 0; (Q

x)P

(x)) = 0;

(14)

(x)) = 1:

(15)

Èç óñëîâèé (14) âûòåêàåò îäíîâðåìåííî âûïîëíåíèå ñëåäóþùèõ ðàâåíñòâ 

Q

!

P



1

(x)

;

Q

8



= 1; (

x)P



(x) = 0;

êîòîðûå ÿâëÿþòñÿ ïðîòèâîðå÷èâûìè, òàê êàê ïðè óñëîâèè Q = 1 èç ðàâåíñòâà Q !    P (x)  1 ñëåäóåò, ÷òî P (x) - òîæäåñòâåííî èñòèííûé ïðåäèêàò, à óñëîâèå (8x)P (x) = 0 ãàðàíòèðóåò îïðîâåðæèìîñòü ýòîãî ïðåäèêàòà.  ñèëó ïåðâîãî èç óñëîâèé (15) ïðåäèêàò Q ! P  (x) ÿâëÿåòñÿ îïðîâåðæèìûì è, ñëåäîâàòåëüíî, ñóùåñòâóåò ýëåìåíò    x0 2 M òàêoé, ÷òî P (x0 ) = 0 ïðè Q = 1. B ñèëó âòîðîãî èç óñëîâèé (15) ïðè Q = 1  ïðåäèêàò (8x)P (x) ÿâëÿåòñÿ òîæäåñòâåííî èñòèííûì, è ïîýòîìó â ðàíåå óïîìÿíóòîé òî÷êå x0 çíà÷åíèå P  (x0 ) = 1. Ïîëó÷åííîå ïðîòèâîðå÷èå äîêàçûâàåò íåâîçìîæíîñòü îäíîâðåìåííîãî âûïîëíåíèÿ óñëîâèé (15) è çàâåðøàåò äîêàçàòåëüñòâî ñîîòíîøåíèÿ (12) òåîðåìû 4. Òåîðåìà 5(çàêîíû óäàëåíèÿ êâàíòîðà îáùíîñòè è ââåäåíèÿ êâàíòîðà ñóùåñòâîâàíèÿ).Ñëåäóþùèå ôîðìóëû ëîãèêè ïðåäèêàòîâ ÿâëÿþòñÿ òàâòîëîãèÿìè):

8

(

!

x)(P (x))

P (t)

P (t);

(16)

x)(P (x)):

(17)

! (9

Äîêàçàòåëüñòâî.Ïîêàæåì, ÷òî ôîðìóëà (17) ââåäåíèÿ êâàíòîðà ñóùåñòâîâàíèÿ ÿâëÿåòñÿ òîæäåñòâåííî èñòèííîé. Ïðåäïîëîæèì, ÷òî ýòî íå òàê: ñóùåñòâóåò ïðåäèêàò P  (t), îïðåäåëåííûé íà íåêîòîðîì ìíîæåñòâå M è òàêîé, ÷òî ïðåäèêàò P  (t) ! (9x)P  (x) îïðîâåðæèì, ò.å. ïðåâðàùàåòñÿ â ëîæíîå âûñêàçûâàíèå ïðè ïîäñòàíîâêå âìåñòî t íåêîòîðîãî t0 2 M : P

Ïîñëåäíåå îçíà÷àåò,÷òî P





(t0 )

! (9

x)(P

9

(t0 ) = 1; (



x)(P

(x)) = 0:



(x)) = 0:

(18)

(19)

Èç ñîîòíîøåíèÿ (9x)(P  (x)) = 0 âûòåêàåò, ÷òî ïðåäèêàò P  (x) òîæäåñòâåííî ëîæíûé, ÷òî ïðîòèâîðå÷èò ïåðâîìó èç óñëîâèé (19).Ñëåäîâàòåëüíî, ñäåëàííîå ïðåäïîëîæåíèå íåâåðíî è äàííàÿ ôîðìóëà - òàâòîëîãèÿ.

Ïðîäåëàéòå ñîîòâåòñòâóþùóþ ïðîâåðêó çàêîíà (16) óäàëåíèÿ êâàíòîðà îáùíîñòè. Òåîðåìà 6(çàêîíû êîììóòàòèâíîñòè äëÿ êâàíòîðîâ).Ñëåäóþùèå ôîðìóëû ëîãèêè ïðåäèêàòîâ ÿâëÿþòñÿ òàâòîëîãèÿìè:

8 )(8 )( (9 )(9 )( (9 )(8 )( (

x

y

P (x; y ))

x

y

P (x; y ))

x

y

P (x; y ))

! (8 )(8 ! (9 )(9 ! (8 )(9 y

x)(P (x; y ));

(20)

y

x)(P (x; y ));

(21)

y

x)(P (x; y ):

(22)

Äîêàçàòåëüñòâî. Òîæäåñòâåííàÿ èñòèííîñòü ïåðâûõ äâóõ ôîðìóë âûòåêàåò íåïîñðåäñòâåííî èç îïðåäåëåíèÿ êâàíòîðîâ îáùíîñòè è ñóùåñòâîâàíèÿ. Èõ äîêàçàòåëüñòâî äîñòàòî÷íî î÷åâèäíî, ïîýòîìó ïåðåéäåì ê äîêàçàòåëüñòâó òàâòîëîãèè (22). Ïðåäïîëîæèì, ÷òî ïîñëåäíÿÿ èç ôîðìóë íå ÿâëÿåòñÿ òàâòîëîãèåé, òîãäà ñóùåñòâóåò ïðåäèêàò P  (x; y ), îïðåäåëåííûé íà ìíîæåñòâå M1  M2 , òàêîé, ÷òî âûñêàçûâàíèå

9 )(8

(

x

y )(P



(x; y ))

! (8 )(9

x)(P

y



(x; y ))

ëîæíî. Èìïëèêàöèÿ ëîæíà òîãäà è òîëüêî òîãäà

9 )(8

(

y )(P

x



8 )(9

(x; y )) = 1; (

y

x)(P



(x; y )) = 0:

(23)

Èç ñîîòíîøåíèé (23) íà îñíîâàíèè îïðåäåëåíèÿ êâàíòîðîâ ñóùåñòâîâàíèÿ è îáùíîñòè ñîîòâåòñòâåííî âûòåêàåò, ÷òî ïðåäèêàò (8y )P  (x; y ) âûïîëíèì, à ïðåäèêàò (9x)P  (x; y ) îïðîâåðæèì. Ñëåäîâàòåëüíî, ñóùåñòâóþò ýëåìåíòû x0 2 M1 , y0 2 M2 òàêèå, ÷òî

8

(

y )(P



9

(x0 ; y )) = 1; (

x)(P



(x; y0 )) = 0:

(24)

Ïåðâîå èç ñîîòíîøåíèé (24) îçíà÷àåò, ÷òî ïðåäèêàò P  (x0 ; y ) ÿâëÿåòñÿ òîæäåñòâåííî èñòèííûì, îòêóäà âûòåêàåò, ÷òî P  (x0 ; y0 ) = 1.  ñèëó âòîðîãî èç ñîîòíîøåíèé (24) ïðåäèêàò P  (x; y0 ) ÿâëÿåòñÿ òîæäåñòâåííî ëîæíûì è, ñëåäîâàòåëüíî, P  (x0 ; y0 ) = 0. Ìû ïðèøëè ê ïðîòèâîðå÷èþ, êîòîðîå äîêàçûâàåò, ÷òî íàøå ïðåäïîëîæåíèå íåâåðíî è ôîðìóëà (22) ÿâëÿåòñÿ òàâòîëîãèåé. Çàìå÷àíèå. Åñëè â òàâòîëîãèÿõ òåîðåì 2-5, äîêàçàííûõ â íàñòîÿùåì ïàðàãðàôå, ñ÷èòàòü, ÷òî ïðåäèêàòíûå ïåðåìåííûå çàâèñÿò îò ïðîèçâîëüíîãî êîíå÷íîãî ÷èñëà ïåðåìåííûõ, òî ïîëó÷åííûå ôîðìóëû òàêæå áóäóò òàâòîëîãèÿìè ëîãèêè ïðåäèêàòîâ. Áîëåå òîãî, ìîæíî ñ÷èòàòü, ÷òî áóêâû P è Q ïðåäñòàâëÿþò ñîáîé ïðîèçâîëüíûå ôîðìóëû ëîãèêè ïðåäèêàòîâ, à íå ïðîñòî n-ìåñòíûå ïðåäèêàòíûå ïåðåìåííûå, ïðåäñòàâëÿþùèå ñîáîé ïðîñòûå èëè àòîìàðíûå ôîðìóëû. Ÿ3. ÐÀÂÍÎÑÈËÜÍÛÅ ÏÐÅÎÁÐÀÇÎÂÀÍÈß ÔÎÐÌÓË Îïðåäåëåíèå. Äâå ôîðìóëû ëîãèêè ïðåäèêàòîâ íàçûâàþòñÿ ðàâíîñèëüíûìè íà ìíîæåñòâå M , åñëè ïðè ëþáîé ïîäñòàíîâêå â ýòè ôîðìóëû âìåñòî ïðåäèêàòíûõ ïåðåìåííûõ ëþáûõ êîíêðåòíûõ ïðåäèêàòîâ, îïðåäåëåííûõ íà M , ôîðìóëû ïðåâðàùàþòñÿ â ðàâíîñèëüíûå ïðåäèêàòû. Åñëè äâå ôîðìóëû ðàâíîñèëüíû íà ëþáûõ ìíîæåñòâàõ,òî îíè íàçûâàþòñÿ ïðîñòî ðàâíîñèëüíûìè. Äðóãèìè ñëîâàìè, ôîðìóëû ðàâíîñèëüíû, åñëè ëþáûå èõ èíòåðïðåòàöèè ïðåäñòàâëÿþò ñîáîé ðàâíîñèëüíûå ïðåäèêàòû. Ðàâíîñèëüíîñòü ôîðìóë F è G áóäåì îáîçíà÷àòü òàê: F  = G.

Èç ïðèâåäåííîãî îïðåäåëåíèÿ, à òàêæå èç îïðåäåëåíèÿ ýêâèâàëåíòíîñòè ñëåäóåò, ÷òî ôîðìóëû F è G ðàâíîñèëüíû òîãäà è òîëüêî òîãäà,êîãäà ôîðìóëà F ! G ÿâëÿåòñÿ òàâòîëîãèåé. Èñïîëüçóÿ ýòîò ôàêò è äîêàçàííûå â ïðåäûäóùåì ïàðàãðàôå òàâòîëîãèè, ïîëó÷èì ñëåäóþùèå îñíîâíûå ðàâíîñèëüíîñòè ëîãèêè ïðåäèêàòîâ:

= (9 )(: ( )) ))  = (8 )(: ( )) ( ) = (8 )( ( ) ^ ( )) ( ) = (9 )( ( ) _ ( )) ) = (9 )( ^ ( )) ) = (8 )( _ ( )) ) ! ( )) = (9 )( = (8 )( ( ) ! ) = (9 )( ( ) ! ) ) ) = (8 )(8 ) ( ) ) = 9 )(9 ) (

:(8 )( ( :(9 )( ( (8 ) ( ) ^ (8 ) (9 ) ( ) _ (9 ) ^ (9 ) ( _ (8 ) ( ! (9 ) ( (9 ) ( ) ! (8 ) ( ) ! (8 )(8 ) ( (9 )(9 ) ( x

F x))

x

F x

;

(25)

x

F x

x

F x

;

(26)

x F x

x G x

x

F x

G x

;

(27)

x F x

x G x

x

F x

G x

;

(28)

H

x F x

x

H

F x

;

(29)

H

x F x

x

H

F x

;

(30)

x F x

x

H

H

F x

;

(31)

x F x

H

x

F x

H ;

(32)

x F x

H

x

F x

H ;

(33)

x

y F x; y

x

y

y F x; y

y

x F x; y ;

x F x; y :

(34) (35)

Ïðèâåäåì ïðèìåðû ïàð íåðàâíîñèëüíûõ ôîðìóë ëîãèêè ïðåäèêàòîâ:

8 (9

(

_ )^

6= (8 )) = 6 (9

_ (8 ) ^ (9

x)(P (x)

Q(x))

x)P (x)

x)Q(x);

(37)

x)(P (x

Q(x

x)P (x

x)Q(x):

(38)

Äåéñòâèòåëüíî, ïîäñòàâèì â (37)-(38) âìåñòî ïðåäèêàòíûõ ïåðåìåííûõ P (x) è Q(x) êîíêðåòíûå ïðåäèêàòû P  (x) è Q (x), îïðåäåëåííûå íà ìíîæåñòâå R âåùåñòâåííûõ ÷èñåë, ãäå P  (x) åñòü ïðåäèêàò [x > 0], à Q (x) - ïðåäèêàò [x  0]. Òîãäà ëåâàÿ ôîðìóëà ñîîòíîøåíèÿ (37) ïðåâðàòèòñÿ â èñòèííîå âûñêàçûâàíèå: "Êàæäîå âåùåñòâåííîå ÷èñëî ëèáî ïîëîæèòåëüíî ëèáî íåïîëîæèòåëüíî". Ïðàâàÿ ÷àñòü ñîîòíîøåíèÿ (37) ïðåâðàùàåòñÿ â äèçúþíêöèþ äâóõ ëîæíûõ âûñêàçûâàíèé: "Êàæäîå âåùåñòâåííîå ÷èñëî íåïîëîæèòåëüíî" èëè "Êàæäîå âåùåñòâåííîå ÷èñëî ïîëîæèòåëüíî",- è ïðåäñòàâëÿåò ñîáîé ëîæíîå âûñêàçûâàíèå.Ïîëó÷åííîå ïðîòèâîðå÷èå è äîêàçûâàåò íåðàâíîñèëüíîñòü ôîðìóë â ñîîòíîøåíèè (37). Äëÿ äîêàçàòåëüñòâà íåðàâíîñèëüíîñòè ôîðìóë â ñîîòíîøåíèè (38) âìåñòî àòîìàðíûõ ôîðìóë P (x) è Q(x) ìîæíî âçÿòü èñïîëüçîâàííûå âûøå ïðåäèêàòû. Äëÿ ðàçíîîáðàçèÿ â êà÷åñòâå P  (x) âîçìåì ïðåäèêàò, îïðåäåëåííûé íà ìíîæåñòâå íàòóðàëüíûõ ÷èñåë: [x êðàòííî 7], à â êà÷åñòâå Q (x) îòðèöàíèå P  (x); [x íå êðàòíî 7]. Òîãäà ëåâàÿ ôîðìóëà ñîîòíîøåíèÿ (38) ïðåäñòàâëÿåò ñîáîé âûñêàçûâàíèå: "Ñóùåñòâóåò íàòóðàëüíîå ÷èñëî, êîòîðîå îäíîâðåìåííî êðàòíî è íå êðàòíî 7",êîòîðîå ëîæíî. Ïðàâàÿ ôîðìóëà ñîîòíîøåíèÿ (38) ïðåâðàùàåòñÿ â êîíúþíêöèþ èñòèííûõ âûñêàçûâàíèé: "Ñóùåñòâóåò íàòóðàëüíîå ÷èñëî, êîòîðîå êðàòíî 7" è "Ñóùåñòâóåò íàòóðàëüíîå ÷èñëî, êîòîðîå íå êðàòíî 7" è ïðåäñòàâëÿåò ñîáîé èñòèííîå âûñêàçûâàíèå. Èòàê, ìû ïîñòðîèëè èíòåðïðåòàöèþ, êîòîðàÿ äëÿ ëåâîé ôîðìóëû (38) ïðåäñòàâëÿåò ñîáîé ëîæíîå âûñêàçûâàíèå, à äëÿ ïðàâîé - èñòèííîå âûñêàçûâàíèå, ÷òî è äîêàçûâàåò íåðàâíîñèëüíîñòü ýòèõ ôîðìóë. Èç ïðèâåäåííûõ ïðèìåðîâ ñ î÷åâèäíîñòüþ ñëåäóåò îáùèé ïðèíöèï ïîñòðîåíèÿ

èíòåðïðåòàöèé, äîêàçûâàþùèõ íåðàâíîñèëüíîñòü ôîðìóë (37)-(38). Âìåñòî P (x) äîñòàòî÷íî ïîäñòàâèòü êàêîé-ëèáî âûïîëíèìûé è îïðîâåðæèìûé ïðåäèêàò, à âìåñòî Q(x) åãî îòðèöàíèå. Êàê è â àëãåáðå âûñêàçûâàíèé, â ëîãèêå ïðåäèêàòîâ ìîæíî çàìåíÿòü îäíó ôîðìóëó äðóãîé,ðàâíîñèëüíîé åé. Ïåðåõîä îò îäíîé ðàâíîñèëüíîé ôîðìóëû ê äðóãîé íàçûâàåòñÿ ðàâíîñèëüíûì ïðåîáðàçîâàíèåì èñõîäíîé ôîðìóëû.  ïðîöåññå ðàâíîñèëüíûõ ïðåîáðàçîâàíèé ôîðìóë ëîãèêè ïðåäèêàòîâ èñïîëüçóþò ðàâíîñèëüíîñòè (25)-(36),à òàêæå ðàâíîñèëüíîñòè àëãåáðû âûñêàçûâàíèé.

Ÿ4. ÏÐÈÂÅÄÅÍÍÀß ÍÎÐÌÀËÜÍÀß ÔÎÐÌÀ. Îäíèì èç âàæíåéøèõ âîïðîñîâ ìàòåìàòè÷åñêîé ëîãèêè ÿâëÿåòñÿ âîïðîñ âûïîëíèìîñòè òîé èëè èíîé ïðåäèêàòíîé ôîðìóëû.×àñòî ðåøåíèþ ýòîãî âîïðîñà ñïîñîáñòâóþò ðàâíîñèëüíûå ïðåîáðàçîâàíèÿ èñõîäíîé ïðåäèêàòíîé ôîðìóëû ê ñïåöèàëüíîìó âèäó. Íèæå áóäåò èäòè ðå÷ü î äâóõ âèäàõ ïðåäèêàòíûõ ôîðìóë: ïðèâåäåííîé íîðìàëüíîé ôîðìå è ïðåäâàðåííîé íîðìàëüíîé ôîðìå. Îïðåäåëåíèå. Ïðèâåäåííîé íîðìàëüíîé ôîðìîé íàçûâàåòñÿ ôîðìó ëà ëîãèêè ïðåäèêàòîâ,êîòîðàÿ íå ñîäåðæèò íèêàêèõ äðóãèõ ëîãè÷åñêèõ ñâÿçîê, êðîìå ^, _ è :,ïðè÷åì çíàêè îòðèöàíèÿ îòíîñÿòñÿ òîëüêî ê ýëåìåíòàðíûì ôîðìóëàì. Ïðèìåðàìè ïðèâåäåííûõ íîðìàëüíûõ ôîðì ÿâëÿþòñÿ ôîðìóëû

:

P (x; y )

_ (9

z )R(z );

8 )(8 )(:

(

x

y

P (x; y; z )):

Áóäåì îáîçíà÷àòü ïðèâåäåííóþ íîðìàëüíóþ ôîðìó ôîðìóëû

(39)

÷åðåç

F

F



.

Òåîðåìà 7.Äëÿ êàæäîé ôîðìóëû ëîãèêè ïðåäèêàòîâ ñóùåñòâóåò ðàâíîñèëüíàÿ åé ïðèâåäåííàÿ íîðìàëüíàÿ ôîðìà.

Äëÿ äîêàçàòåëüñòâà òåîðåìû èñïîëüçóåì ìåòîä ìàòåìàòè÷åñêîé èíäóêöèè.Èíäóêöèþ ïðîâåäåì ïî ÷èñëó k ëîãè÷åñêèõ îïåðàöèé â ôîðìóëå.Ïðè k = 0 ìû èìååì äåëî ñ ýëåìåíòàðíîé ôîðìóëîé, êîòîðàÿ ñàìà ïî ñåáå ÿâëÿåòñÿ ïðèâåäåííîé íîðìàëüíîé ôîðìîé. Ïðåäïîëîæèì, ÷òî âñÿêàÿ ôîðìóëà, ñîäåðæàùàÿ íå áîëåå k ëîãè÷åñêèõ îïåðàöèé, èìååò ðàâíîñèëüíóþ åé ïðèâåäåííóþ íîðìàëüíóþ ôîðìó. Ïîêàæåì òåïåðü, ÷òî ïðèâåäåííîé ôîðìîé îáëàäàåò âñÿêàÿ ôîðìóëà,ñîäåðæàùàÿ k + 1 ëîãè÷åñêóþ îïåðàöèþ. Åñëè F òàêàÿ ôîðìóëà, òî îíà èìååò îäèí èç ñëåäóþùèõ âèäîâ;

:

F

1 ; F1 ^ F2 ; F1 _ F2 ;

8

(

1

x)F ;

9

(

2

1

x)F ; F

!

2

1

F ; F

!

2

F ;

(40)

ãäå êàæäàÿ èç ôîðìóë F1 è F2 ñîäåðæèò íå áîëåå k ëîãè÷åñêèõ îïåðàöèé.Ïóñòü F1 è F2 - ïðèâåäåííûå ôîðìû äëÿ F1 è F2 , òîãäà F1 ^ F2 , F1 _ F2 , (8x)F1 , (9x)F1 - ïðèâåäåííûå ôîðìóëû äëÿ F1 ^ F2 , F1 _ F2 , (8x)F1 , (9x)F1 . Åñëè F = :F1 ,òî äëÿ ïîñòðîåíèÿ ïðèâåäåííîé ôîðìû ôîðìóëû F íóæíî ïðîíåñòè îïåðàöèþ îòðèöàíèÿ ÷åðåç äèçúþíêöèþ,êîíúþíêöèþ è îïåðàöèè ñâÿçûâíèÿ êâàíòîðàìè.Äëÿ ýòîãî ìîæíî èñïîëüçîâàòü ôîðìóëû äå Ìîðãàíà (ñì. ðàâíîñèëüíîñòè (25)(26)). ×òî êàñàåòñÿ îñòàëüíûõ ôîðìóë, äîñòàòî÷íî âûðàçèòü îïåðàöèè !, ! ÷åðåç êîíúþíêöèþ, äèçúþíêöèþ è îòðèöàíèå, èñïîëüçóÿ ñëåäóþùèå ðàâíîñèëüíîñòè àëãåáðû âûñêàçûâàíèé: F

1

!

= (:F1 _ F2 ) ^ (F1 _ :F2 ); 2

F

!

1

F

F

2

 =: 1_ F

2

F :

Èòàê, â ëþáîì ñëó÷àå äëÿ ôîðìóëû ñóùåñòâóåò ðàâíîñèëüíàÿ åé â ïðèâåäåííîé ôîðìå. Ïðèìåð 4. F

= :((8

! (9 ) ( )) = :(:(8 ) ( ) _ (9 ) ( ))  =  ) ^ :(9 ) ( )  ) ^ (8 )(: ( ))  = (8 ) ( =

x)P (x; y )

8

(

x)P (x; y

z Q z

z Q z

x P x; y

x P x; y

z

z Q z

Q z

F

Ÿ5. ÏÐÅÄÂÀÐÅÍÍÀß ÍÎÐÌÀËÜÍÀß ÔÎÐÌÀ Åùå îäíèì óäîáíûì âèäîì ôîðìóëû, ê êîòîðîìó åå ìîæíî ïðèâåñòè ðàâíîñèëüíûìè ïðåîáðàçîâàíèÿìè, ÿâëÿåòñÿ ïðåäâàðåííàÿ íîðìàëüíàÿ ôîðìà. Îïðåäåëåíèå. Ïðåäâàðåííîé íîðìàëüíîé ôîðìîé äëÿ ôîðìóëû ëîãèêè ïðåäèêàòîâ íàçâàåòñÿ òàêàÿ åå ïðèâåäåííàÿ íîðìàëüíàÿ ôîðìà, â êîòîðîé âñå êâàíòîðû ñòîÿò â åå íà÷àëå, à îáëàñòü äåéñòâèÿ êàæäîãî èç íèõ ðàñïðîñòðàíÿåòñÿ äî êîíöà ôîðìóëû, ò.å. ýòî ôîðìóëà âèäà (h1 x1 ):::(hn xn )F (x1 ; :::; xn ; y1 ; :::; ym );

ãäå

hi

8 èëè 9, à ôîðìóëà

åñòü îäèí èç êâàíòîðîâ

F

(40)

íå ñîäåðæèò êâàíòîðîâ.

Òåîðåìà 8.Äëÿ êàæäîé ôîðìóëû ëîãèêè ïðåäèêàòîâ ñóùåñòâóåò ðàâíîñèëüíàÿ åé

ïðèâåäåííàÿ íîðìàëüíàÿ ôîðìà.

Äîêàçàòåëüñòâî, êàê è â ñëó÷àå ïðåäûäóùåé òåîðåìû, ïðîâîäèòñÿ ìåòîäîì ìàòåìàòè÷åñêîé èíäóêöèè ïî ÷èñëó k ëîãè÷åñêèõ îïåðàöèé, ïðåäñòàâëåííûõ â ôîðìóëå. Åñëè ôîðìóëà F àòîìàðíà (k = 0), îíà ïðåäñòàâëÿåò ñîáîé ïðåäâàðåííóþ íîðìàëüíóþ ôîðìó. Ïðåäïîëîæèì, ÷òî äëÿ ôîðìóë, â êîòîðûõ ÷èñëî ëîãè÷åñêèõ îïåðàöèé íå ïðåâîñõîäèò k , óòâåðæäåíèå òåîðåìû èìååò ìåñòî. Ïóñòü F = F1 _ F2 , ãäå ôîðìóëû F1 è F2 óäîâëåòâîðÿþò ïðåäïîëîæåíèþ èíäóêöèè,ò.å.

+ = (h1 x1 ):::(hn xn )F1 ; 1 +  F2 = (k1 y1 ):::(kn ym )F2 ; + + = 1; :::; m; F1 ; F2 íå ñîäåðæàò êâàíòîðîâ è ïðåäñòàâëÿþò F

ãäå ki ; hj 2 f8; 9g; i = 1; :::; n; j ñîáîé ïðèâåäåííûå íîðìàëüíûå ôîðìû. Ïðåäâàðèòåëüíî ïåðåîáîçíà÷èì ïðåäìåòíûå ïåðåìåííûå â F òàêèì îáðàçîì,÷òîáû ñâîáîäíûå ïåðåìåííûå íå ñîâïàäàëè ñî ñâÿçàííûìè. ýòîì ñëó÷àå ê F ìîãóò áûòü ïðèìåíåíû ðàâíîñèëüíîñòè (29),(31) î ïðîíåñåíèè êâàíòîðîâ ÷åðåç äèçúþíêöèþ,òîãäà ôîðìóëà F

= (

+ + 1 1 ):::(hn xn )(k1 y1 ); :::; (km ym )(F1 _ F2 )

h x

ïðåäñòàâëÿåò ñîáîé ïðåäâàðåííóþ íîðìàëüíóþ ôîðìó ïðåäèêàòíîé ôîðìóëû F, Åñëè G = (:F1 ),òî äëÿ ïîñòðîåíèÿ ïðåäâàðåííîé íîðìàëüíîé ôîðìû èñïîëüçóþòñÿ ðàâíîñèëüíîñòè äå Ìîðãàíà (25),(26), òîãäà G

 =(

1 1 ):::(hn xn )(:F1 ); 

h x



ãäå h1 ; :::; hn - êâàíòîðû, äâîéñòâåííûå h1 ; :::; hn (9 = 8; 8 = 9). Ïîñòðîèâ ïðèâåäåííóþ ôîðìó äëÿ :F1 , ïîëó÷èì ïðåäâàðåííóþ íîðìàëüíóþ ôîðìó äëÿ G: G

= (

1 1 ):::(hn xn )(:F1 ) 



h x



:

Àíàëîãè÷íî ñòðîèòñÿ ïðåäâàðåííàÿ íîðìàëüíàÿ ôîðìà äëÿ âñåõ ôîðìóë ðÿäà (40).Ýòî çàìå÷àíèå çàâåðøàåò äîêàçàòåëüñòâî òåîðåìû. Ðàññìîòðèì ïðèìåðû ïîñòðîåíèÿ ïðåäâàðåííîé íîðìàëüíîé ôîðìû.

:

_ (9 ) ( ) = (9 )(: ( ) _ ( )); (8 )(9 )(9 ) ( ) ! (9 ) ( )  = ( )) _ (9 ) ( )  = (9 )(8 )(8 )(: ( = (9 )(8 )(8 )(9 )(: ( ) _ ( ))

P (x; y )

x

:((8 )(9 )(9 x

y

z R z

y

P x; y

z R x; y; z

z )R x; y; z

x

z

t G t

y

z

t G t

x

t

R z

y

R x; y; z ))

z

R x; y; z

G t

_ (9 )

t G(t)

:

Ÿ6. ÈÑ×ÈÑËÅÍÈÅ ÏÐÅÄÈÊÀÒΠ(ÎÁÙÀß ÕÀÐÀÊÒÅÐÈÑÒÈÊÀ) Èñ÷èñëåíèå ïðåäèêàòîâ (ÈÏ) ïðåäñòàâëÿåò ñîáîé àêñèîìàòè÷åñêóþ òåîðèþ.Êàê è äðóãèå àêñèîìàòè÷åñêèå òåîðèè, íàïðèìåð, èñ÷ècëåíèå âûñêàçûâàíèé (ÈÂ), îíî âêëþ÷àåò àêñèîìû, ïðàâèëà âûâîäà è òåîðåìû.Ôîðìóëû ÈÏ îïðåäåëÿþòñÿ òàê æå, êàê è ôîðìóëû ëîãèêè ïðåäèêàòîâ, çà íåáîëüøèì èñêëþ÷åíèåì. Òàê â êà÷åñòâå ëîãè÷åñêèõ ñâÿçîê â ÈÏ èñïîëüçóåòñÿ íå âñÿ ñèñòåìà ñâÿçîê ëîãèêè ïðåäèêàòîâ, à ëþáàÿ åå ïîäñèñòåìà, ñîîòâåòñòâóþùàÿ ïîëíîé ñèñòåìå áóëåâûõ ôóíêöèé, íàïðèìåð,câÿçêè :; !. Ñèñòåìà àêñèîì èñ÷èñëåíèÿ ïðåäèêàòîâ âêëþ÷àåò â ñåáÿ àêñèîìû èñ÷èñëåíèÿ âûñêàçûâàíèé, à òàêæå àêñèîìàìè èñ÷èñëåíèÿ ïðåäèêàòîâ îáúÿâëÿþòñÿ òàâòîëîãèè ëîãèêè ïðåäèêàòîâ (16)-(17). Äàëåå, ê ïðàâèëó âûâîäà modus ponens : èç ôîðìóë F è F ! G íåïîñðåäñòâåííî cëåäóåò ôîðìóëà G, - äîáàâëÿþòñÿ åùå äâà ïðàâèëà âûâîäà, íàçûâàåìûå ïðàâèëàìè ââåäåíèÿ êâàíòîðà îáùíîñòè è êâàíòîðà ñóùåñòâîâàíèÿ ñîîòâåòñòâåííî: (

8

ïðàâèëî)

9

ïðàâèëî)

(

F F

9

(

! ! (8

G(x)

x)G(x)

! ) !

G(x) x)G(x

F

F

;

;

åñëè x íå âõîäèò ñâîáîäíî â ôîðìóëó F . Íàêîíåö, ïîíÿòèÿ âûâîäà è òåîðåìû îïðåäåëÿþòñÿ ñîâåðøåííî àíàëîãè÷íî ñîîòâåòñòâóþùèì ïîíÿòèÿì ôîðìàëèçîâàííîãî èñ÷èñëåíèÿ âûñêàçûâàíèé. Äàëåå, â ôîðìàëèçîâàííîì èñ÷èñëåíèè ïðåäèêàòîâ ìîæåò áûòü äîêàçàíà òåîðåìà î äåäóêöèè, êîòîðàÿ ñ óñïåõîì ïðèìåíÿåòñÿ ê ïîñòðîåíèþ äîêàçàòåëüñòâ. Çàòåì óñòàíàâëèâàåòñÿ ïîëíîòà ôîðìàëèçîâàííîãî èñ÷èñëåíèÿ ïðåäèêàòîâ(òåîðåìà Ê.Ãåäåëÿ î ïîëíîòå, äîêàçàííàÿ â 1930 ãîäó): òåîðåìàìè ôîðìàëèçîâàííîãî èñ÷èñëåíèÿ ïðåäèêàòîâ ÿâëÿþòñÿ òàâòîëîãèè ëîãèêè ïðåäèêàòîâ, è òîëüêî îíè. Ôîðìàëèçîâàííîå èñ÷èñëåíèå ïðåäèêàòîâ, êàê è ôîðìàëèçîâàííîå èñ÷èñëåíèå âûñêàçûâàíèé, íåïðîòèâîðå÷èâî, à åãî àêñèîìû íåçàâèñèìû. Àêñèîìàòè÷åñêàÿ òåîðèÿ íàçûâàåòñÿ íåïðîòèâîðå÷èâîé, åñëè íè äëÿ êàêîãî óòâåðæäåíèÿ A, ñôîðìóëèðîâàííîãî

â òåðìèíàõ ýòîé òåîðèè, ñàìî óòâåðæäåíèå A è åãî îòðèöàíèå :A íå ìîãóò áûòü îäíîâðåìåííî òåîðåìàìè äàííîé òåîðèè. Àêñèîìà B èç ñèñòåìû àêñèîì S íàçûâàåòñÿ íåçàâèñèìîé îò îñòàëüíûõ àêñèîì ýòîé ñèñòåìû, åñëè åå íåëüçÿ âûâåñòè (äîêàçàòü) èç ìíîæåñòâà àêñèîì S n B . Ñèñòåìà àêñèîì íàçûâàåòñÿ íåçàâèñèìîé, åñëè êàæäàÿ åå àêñèîìà íå çàâèñèò îò îñòàëüíûõ. Íàêîíåö, â îòëè÷èå îò ôîðìàëèçîâàííîãî èñ÷èñëåíèÿ âûñêàçûâàíèé ôîðìàëèçîâàííîå èñ÷èñëåíèå ïðåäèêàòîâ åñòü íåðàçðåøèìàÿ àêñèîìàòè÷åñêàÿ òåîðèÿ, ò.å. íå ñóùåñòâóåò åäèíîãî àëãîðèòìà, ïîçâîëÿþùåãî äëÿ ëþáîé ôîðìóëû ëîãèêè ïðåäèêàòîâ îïðåäåëèòü, ÿâëÿåòñÿ ëè îíà òåîðåìîé ôîðìàëèçîâàííîãî èñ÷èñëåíèÿ ïðåäèêàòîâ. Ýòî áûëî óñòàíîâëåíî À.×åð÷åì â 1936 ãîäó. ËÈÒÅÐÀÒÓÐÀ 1.Ïðåäèêàòû: ìåòîä. óêàçàíèÿ ê ñàìîñòîÿòåëüíîé ðàáîòå äëÿ ñòóäåíòîâ 1 êóðñà ôàêóëüòåòà ÏÌÌ /Ñîñò.Êàöàðàí Ò.Ê.-Âîðîíåæ: ÂÃÓ,1997.- 24ñ.

Ñîñòàâèòåëü Êàöàðàí Òàòüÿíà Êîíñòàíòèíîâíà. Ðåäàêòîð Áóíèíà Ò.Ä.