Лекции - Математическая логика

Подождите немного. Документ загружается.

151

Ïðèìåð. Ðàññìîòðèì äâå ôîðìóëû:

11 1 2 2 1 2

()& (, )

xP x xP x x

∃∀

;

11 1 22 12

()& (, ))

(

xPx xP xx

∃∀

Â ïåðâîé ôîðìóëå îáëàñòüþ äåéñòâèÿ âõîæäåíèÿ êâàíòîðà ñó-

ùåñòâîâàíèÿ ∃õ

ñëóæèò ôîðìóëà

()

, à âî âòîðîé – ôîðìóëà

(

(õ

) & >õ

(õ

)). Êàê âèäíî èç âòîðîãî ïðèìåðà, ñêîáêè óêà-

çûâàþò îáëàñòü äåéñòâèÿ âõîæäåíèÿ êâàíòîðà ∃õ

è, åñëè èõ îïóñ-

òèòü, ñìûñë ôîðìóëû èçìåíèòñÿ. 

Çàìå÷àíèå 1. ×àñòî, ãîâîðÿ î êâàíòîðå ïî ïåðåìåííîé õ

, èìåþò

â âèäó âõîæäåíèå ýòîãî êâàíòîðà ïî ïåðåìåííîé õ

. 

Âõîæäåíèå ïåðåìåííîé õ

â ôîðìóëó À íàçûâàþò ñâÿçàííûì

âõîæäåíèåì, åñëè îíî íàõîäèòñÿ â îáëàñòè äåéñòâèÿ êàêîãî-

ëèáî êâàíòîðà ïî ïåðåìåííîé õ

èëè ÿâëÿåòñÿ âõîæäåíèåì â

ñàì êâàíòîð ïî ïåðåìåííîé õ

. Âõîæäåíèå ïåðåìåííîé õ

â ôîð-

ìóëó À íàçûâàþò ñâîáîäíûì âõîæäåíèåì, åñëè îíî íå ÿâëÿåòñÿ

ñâÿçàííûì.

Ïåðåìåííóþ õ

íàçûâàþò ñâîáîäíîé ïåðåìåííîé ôîðìóëû À, åñëè

îíà èìååò õîòÿ áû îäíî ñâîáîäíîå âõîæäåíèå â ýòó ôîðìóëó.

Åñëè âñå âõîæäåíèÿ ïåðåìåííîé õ

â ôîðìóëó À ÿâëÿþòñÿ ñâÿ-

çàííûìè, òî õ

íàçûâàþò ñâÿçàííîé ïåðåìåííîé

ôîðìóëû À.

Ôîðìóëó íàçûâàþò çàìêíóòîé ôîðìóëîé, åñëè îíà íå ñîäåðæèò

ñâîáîäíûõ ïåðåìåííûõ.

Ïðèìåðû.

1. Ïåðåìåííàÿ õ

èìååò òðè âõîæäåíèÿ â ôîðìóëó

11 11 12

() (, )

Px xPxx

∀

⊃

ïåðâîå èç êîòîðûõ – ñâîáîäíîå, à äâà äðóãèå – ñâÿçàííûå. Åäèí-

ñòâåííîå âõîæäåíèå ïåðåìåííîé õ

â ýòó ôîðìóëó ñâîáîäíîå. Îáå

ïåðåìåííûå ÿâëÿþòñÿ ñâîáîäíûìè â ýòîé ôîðìóëå. Ñàìà ôîðìóëà

íå ÿâëÿåòñÿ çàìêíóòîé.

2. Ôîðìóëà

11 1 2

(, )

xxPxx

∃∀

íå ñîäåðæèò ñâîáîäíûõ ïåðåìåí-

íûõ, âñå âõîæäåíèÿ ïåðåìåííûõ â íåå ñâÿçàííûå, à ñàìà ôîðìóëà

çàìêíóòà.



Èíîãäà ñâÿçàííîé ïåðåìåííîé ôîðìóëû À íàçûâàþò ïåðåìåííóþ, êîòî-

ðàÿ èìååò õîòÿ áû îäíî ñâÿçàííîå âõîæäåíèå â À.

152

Çàìå÷àíèå 2. Ìîæíî ñôîðìóëèðîâàòü èíäóêòèâíîå îïðåäåëå-

íèå ñâîáîäíîãî âõîæäåíèÿ ïåðåìåííîé â ôîðìóëó ßËÏ. 

Çàìûêàíèåì ôîðìóëû À íàçûâàþò:

1) ôîðìóëó

...

∀∀

, åñëè À íåçàìêíóòà, à (

, ...,

) –

ñïèñîê âñåõ åå ñâîáîäíûõ ïåðåìåííûõ (i

< i

< … < i

);

2) ñàìó ôîðìóëó À, åñëè À – çàìêíóòàÿ ôîðìóëà.

Çàìûêàíèå ôîðìóëû À áóäåì îáîçíà÷àòü ñèìâîëîì ÀR.

Â ôîðìóëû âìåñòî ñâîáîäíûõ ïåðåìåííûõ ìîæ-

íî ïîäñòàâëÿòü òåðìû, ïîëó÷àÿ ïðè ýòîì íîâûå

ôîðìóëû. Â òåðìû òàêæå âìåñòî ïåðåìåííûõ

ìîæíî ïîäñòàâëÿòü òåðìû, ïîëó÷àÿ ïðè ýòîì íîâûå òåðìû.

S Ïóñòü õ, t, s, À – ïðîèçâîëüíûå ïðåäìåòíàÿ ïåðåìåííàÿ, òåðìû

è ôîðìóëà ßËÏ ñîîòâåòñòâåííî. Åñëè êàæäîå âõîæäåíèå ïåðåìåí-

íîé x â òåðì s çàìåíèòü âõîæäåíèåì òåðìà t, òî ïîëó÷èì òåðì,

êîòîðûé áóäåì íàçûâàòü ðåçóëüòàòîì ïîäñòàíîâêè òåðìà t â òåðì

s âìåñòî ïåðåìåííîé õ è îáîçíà÷àòü ÷åðåç

()

. Åñëè êàæäîå ñâî-

áîäíîå âõîæäåíèå ïåðåìåííîé õ â ôîðìóëó À çàìåíèòü âõîæäåíè-

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

òàòîì ïîäñòàíîâêè òåðìà t â ôîðìóëó À âìåñòî ïåðåìåííîé õ è

îáîçíà÷àòü ÷åðåç

()

★ Óòî÷íèì ýòè ïîíÿòèÿ ñ ïîìîùüþ èíäóêòèâíûõ îïðåäåëåíèé.

Îïðåäåëåíèå ðåçóëüòàòà ïîäñòàíîâêè òåðìà t â òåðì s âìåñòî

ïåðåìåííîé x:

1. à) äëÿ ëþáîé ïåðåìåííîé ó, îòëè÷íîé îò ïåðåìåííîé õ,

()

= ó;

á) äëÿ ïåðåìåííîé õ

()

= t;

â) äëÿ ëþáîé ïðåäìåòíîé êîíñòàíòû ñ

()

= ñ;

2. Äëÿ ëþáûõ òåðìîâ t

, ..., t

è n-ìåñòíîãî ôóíêöèîíàëüíîãî

ñèìâîëà

(

( , ..., ))

mnt

(( ) , ..., ( ) )

nx x

mt nt

Èñïîëüçóÿ ïðèíöèï èíäóêöèè äëÿ òåðìîâ ßËÏ, ëåãêî äîêà-

çàòü, ÷òî ðåçóëüòàò ïîäñòàíîâêè òåðìà t â òåðì s âìåñòî ïåðåìåí-

íîé õ ÿâëÿåòñÿ òåðìîì.

Подстановка

терма в формулу

153

Îïðåäåëåíèå ðåçóëüòàòà ïîäñòàíîâêè òåðìà t â ôîðìóëó À âìåñ-

òî ïåðåìåííîé õ:

1. Êàêîâû áû íè áûëè ýëåìåíòàðíàÿ ôîðìóëà

, ..., t

òåðì t è ïåðåìåííàÿ x:

(

, ..., t

)

(( ) , ..., ( ) )

nx x

mt nt

2.1. Êàêîâû áû íè áûëè ôîðìóëû À è Â, òåðì t è ïåðåìåííàÿ x:

() ()

¬=¬

;

( ) () ()

xxx

ttt

AB A B

⊕⊕=

, ãäå ⊕ åñòü &, ∨, ⊃.

2.2. Êàêîâû áû íè áûëè ôîðìóëà À, òåðì t è ïåðåìåííàÿ õ:

()

∀

= >õ À;

()

∀

()

∀

, ãäå ó – ïåðåìåííàÿ, îòëè÷íàÿ îò õ;

()

∃

= ∃õÀ;

()

∃

()

∃

, ãäå ó – ïåðåìåííàÿ, îòëè÷íàÿ îò õ.

Çàìåòèì, ÷òî åñëè ïåðåìåííàÿ õ íå âõîäèò ñâîáîäíî â ôîðìó-

ëó À, â ÷àñòíîñòè êîãäà À çàìêíóòà, òî

()

ñîâïàäàåò ñ À.

Íåñëîæíî äîêàçàòü, ÷òî

()

– ðåçóëüòàò ïîäñòàíîâêè òåðìà t

â ôîðìóëó À âìåñòî ïåðåìåííîé õ – åñòü ôîðìóëà ßËÏ.

✰

S Çàìå÷àíèå 3. Èíîãäà óäîáíî ïðîèçâîëüíóþ ôîðìóëó îáîçíà-

÷àòü ÷åðåç À(õ). Ïðè ýòîì âîâñå íå îáÿçàòåëüíî ïåðåìåííàÿ õ

âõîäèò â ôîðìóëó À, à òàêæå, âîçìîæíî, â À âõîäÿò ñâîáîäíî

ïåðåìåííûå, îòëè÷íûå îò õ. Ýòî óäîáíî äëÿ òîãî, ÷òîáû çàòåì

ðåçóëüòàò ïîäñòàíîâêè òåðìà t â ôîðìóëó À(x) âìåñòî õ îáîçíà÷àòü

÷åðåç À(t).



Èíîãäà ôîðìóëó

()

áóäåì íàçûâàòü ïðîñòî ïîäñòàíîâêîé òåð-

ìà t â ôîðìóëó À âìåñòî ïåðåìåííîé õ.

Îòìåòèì, ÷òî íå âñÿêàÿ ïîäñòàíîâêà òåðìà â ôîðìóëó ÿâëÿåòñÿ

â îïðåäåëåííîì ñìûñëå äîïóñòèìîé (êîððåêòíîé), îñìûñëåííîé

(ñì. çàìå÷àíèå 3 â êîíöå § 3.3). Âî èçáåæàíèå íåæåëàòåëüíûõ ñè-

òóàöèé îãðàíè÷èìñÿ ïîäñòàíîâêàìè, ïðè êîòîðûõ ïåðåìåííûå,

âõîäÿùèå â òåðì t, ïðè ïîäñòàíîâêå åãî â ôîðìóëó À íå ñâÿçûâàþò-

ñÿ êâàíòîðàìè, âõîäÿùèìè â À. Äðóãèìè ñëîâàìè, âõîäÿùèå â òåðì

t ïåðåìåííûå äîëæíû îñòàâàòüñÿ ñâîáîäíûìè â ðåçóëüòàòå ïîäñòà-

íîâêè

()

. Óòî÷íèì ñêàçàííîå.

154

Òåðì t íàçûâàþò äîïóñòèìûì äëÿ ïîäñòàíîâêè

â ôîðìóëó À

âìåñòî ïåðåìåííîé õ

(À-õ

-äîïóñòèìûì òåðìîì), åñëè íèêà-

êîå ñâîáîäíîå âõîæäåíèå õ

â ôîðìóëó À íå íàõîäèòñÿ â îáëà-

ñòè äåéñòâèÿ êâàíòîðà ïî êàêîé-ëèáî ïåðåìåííîé, âõîäÿùåé â

òåðì t.

Ïðèìåð. Åñëè ôîðìóëà À åñòü

11 3213

() (, )

Px xPxx

⊃∀

, òî

òåðìû

112

fxx

()

ÿâëÿþòñÿ À-õ

-äîïóñòèìûìè, à òåðìû

()

113

(,)

fxx

íå ÿâëÿþòñÿ À-õ

-äîïóñòèìûìè. 

S Ëåãêî ïðîâåðèòü, ÷òî:

1) òåðì õ

ÿâëÿåòñÿ À-õ

-äîïóñòèìûì äëÿ ëþáîé ôîðìóëû À;

2) òåðì t, íå ñîäåðæàùèé ïåðåìåííûõ, À-õ

-äîïóñòèì äëÿ ëþ-

áîé ôîðìóëû À è ëþáîé ïåðåìåííîé õ

;

3) âñÿêèé òåðì t ÿâëÿåòñÿ À-õ

-äîïóñòèìûì äëÿ ëþáîé ôîðìó-

ëû À, íå ñîäåðæàùåé õ

ñâîáîäíî (â ÷àñòíîñòè, äëÿ çàìêíóòîé ôîðìó-

ëû);

4) âñÿêèé òåðì t ÿâëÿåòñÿ À-õ

-äîïóñòèìûì äëÿ ëþáîé áåñêâàí-

òîðíîé ôîðìóëû À è ëþáîé ïåðåìåííîé õ

Åñëè òåðì t äîïóñòèì äëÿ ïîäñòàíîâêè â ôîðìóëó À âìåñòî

ïåðåìåííîé õ

(À-õ

-äîïóñòèì), òî ïîäñòàíîâêó òåðìà t â ôîðìóëó À

âìåñòî ïåðåìåííîé õ

áóäåì íàçûâàòü äîïóñòèìîé èëè êîððåêòíîé.

Çàìå÷àíèå 4. Ìîæíî ñôîðìóëèðîâàòü èíäóêòèâíîå îïðåäåëåíèå

ðåçóëüòàòà îäíîâðåìåííîé ïîäñòàíîâêè â ôîðìóëó À òåðìîâ t

, …, t

âìåñòî ïåðåìåííûõ õ

, …, õ

–

, ...,

()

, à òàêæå èíäóêòèâíîå îï-

ðåäåëåíèå äîïóñòèìîé îäíîâðåìåííîé ïîäñòàíîâêè òåðìîâ âìåñòî

ïåðåìåííûõ â ôîðìóëó À.



Îáû÷íî, äëÿ òîãî ÷òîáû íà ÿçûêå ôîðìóë âû-

ðàçèòü òå èëè èíûå ñâîéñòâà, çàïèñàòü òå èëè

èíûå óòâåðæäåíèÿ íåêîòîðîé ìàòåìàòè÷åñêîé

òåîðèè, äîñòàòî÷íî ëèøü ÷àñòè÷íî èñïîëüçîâàòü ìíîæåñòâà ïðå-

äèêàòíûõ ñèìâîëîâ, ôóíêöèîíàëüíûõ ñèìâîëîâ è ïðåäìåòíûõ

êîíñòàíò ßËÏ. Ïðè ýòîì â íåêîòîðûõ ñëó÷àÿõ ìîæíî îáîéòèñü

âîâñå áåç ôóíêöèîíàëüíûõ ñèìâîëîâ è ïðåäìåòíûõ êîíñòàíò, â

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

íè îäíîé ôîðìóëû.

×àñòî âìåñòî òåðìèíà «òåðì äîïóñòèì äëÿ ïîäñòàíîâêè…» èñïîëüçóþò

òåðìèí «òåðì ñâîáîäåí äëÿ ïîäñòàíîâêè…».

Языки

первого порядка

155

Ñèãíàòóðîé σ áóäåì íàçûâàòü ìíîæåñòâî Pred

∪ Func

∪ Const

ãäå Pred

, Func

, Const

– ïðîèçâîëüíûå ìíîæåñòâà ñîîòâåòñòâåí-

íî ïðåäèêàòíûõ ñèìâîëîâ, ôóíêöèîíàëüíûõ ñèìâîëîâ è ïðåä-

ìåòíûõ êîíñòàíò, ïðè÷åì Pred

≠ ∅ .

Ôðàãìåíòîì ßËÏ ñèãíàòóðû σ (ßËÏ

) áóäåì íàçûâàòü ÿçûê,

ôîðìóëû êîòîðîãî ñòðîÿòñÿ èç ýëåìåíòîâ σ, âñåõ ïðåäìåòíûõ

ïåðåìåííûõ (áåç îãðàíè÷åíèÿ) ñ ïîìîùüþ ñâÿçîê, êâàíòîðîâ è

òåõíè÷åñêèõ ñèìâîëîâ òàê æå, êàê ôîðìóëû ßËÏ.

S Ôðàãìåíòû ßËÏ ïðèíÿòî òàêæå íàçûâàòü ÿçûêàìè ïåðâîãî

ïîðÿäêà.

Â ÿçûêàõ ïåðâîãî ïîðÿäêà, â îòëè÷èå îò ÿçûêîâ áîëåå âûñîêîãî

ïîðÿäêà, íå äîïóñêàþòñÿ êâàíòîðû ïî ïðåäèêàòíûì è ïî ôóíêöè-

îíàëüíûì ñèìâîëàì. Òàêæå íà ÿçûêå ïåðâîãî ïîðÿäêà íåëüçÿ íå-

ïîñðåäñòâåííî çàïèñàòü ïðåäëîæåíèÿ, â êîòîðûõ ôèãóðèðóþò ïðå-

äèêàòû, çàäàííûå íà ôóíêöèÿõ, èëè ôóíêöèè, çàäàííûå íà ïðåäè-

êàòàõ.

Ñèãíàòóðîé ôîðìóëû F (ìíîæåñòâà ôîðìóë Ã) íàçûâàþò ìíî-

æåñòâî âñåõ ïðåäèêàòíûõ ñèìâîëîâ, ôóíêöèîíàëüíûõ ñèìâî-

ëîâ è ïðåäìåòíûõ êîíñòàíò, âõîäÿùèõ â ýòó ôîðìóëó (ìíîæå-

ñòâî ôîðìóë Ã). Ñèãíàòóðó ôîðìóëû F (ìíîæåñòâà ôîðìóë Ã)

áóäåì îáîçíà÷àòü ÷åðåç σ(F) (σ(Ã)).

Åñëè ÿçûê ñèãíàòóðû σ èñïîëüçóþò äëÿ çàïèñè ïðåäëîæåíèé

íåêîòîðîé ñîäåðæàòåëüíîé òåîðèè, òî âìåñòî ñèìâîëîâ

è ñ

îáû÷íî èñïîëüçóþò ñèìâîëû, òðàäèöèîííî îáîçíà÷àþùèå ñîîò-

âåòñòâóþùèå ïðåäèêàòû è ôóíêöèè ýòîé òåîðèè.

Ïðèìåð. Ïðè èñïîëüçîâàíèè ÿçûêà ïåðâîãî ïîðÿäêà äëÿ çà-

ïèñè ïðåäëîæåíèé òåîðèè ìíîæåñòâ äîñòàòî÷íî îäíîãî åäèíñòâåí-

íîãî äâóìåñòíîãî ïðåäèêàòíîãî ñèìâîëà. Ðàññìîòðèì ñèãíàòóðó ñ

åäèíñòâåííûì äâóìåñòíûì ïðåäèêàòíûì ñèìâîëîì ∈, ò. å.

σ = {∈}, ïðè ýòîì âìåñòî ∈(t

, t

) áóäåì ïèñàòü t

∈ t

Ïðèâåäåì ïðèìåðû ôîðìóë ßËÏ

à) >z (z ∈ õ

z ∈ ó); ââåäåì äëÿ ýòîé ôîðìóëû îáîçíà÷åíèå õ = ó;

á) >z (z ∈ õ ⊃ z ∈ ó); ýòó ôîðìóëó îáîçíà÷èì ÷åðåç õ ⊆ ó;

â) >y ¬(y ∈ x); ýòó ôîðìóëó îáîçíà÷èì ñëåäóþùèì îáðàçîì: õ = ∅. 

Ïðèìåð. Ðàññìîòðèì ñèãíàòóðó { = ,

⋅

, 1} ñ äâóìåñòíûì ïðåäè-

êàòíûì ñèìâîëîì = , äâóìåñòíûì ôóíêöèîíàëüíûì ñèìâîëîì

⋅

êîíñòàíòîé 1 (âìåñòî

⋅

, t

) áóäåì ïèñàòü ïðèâû÷íûì îáðàçîì

⋅

). Ïðèìåðû ôîðìóë â ýòîé ñèãíàòóðå:

156

à) ∃z (ó = õ

⋅

z);

á) >y(∃z (õ = ó

⋅

z) ⊃ ó = 1 ∨ ó = õ) & ¬(õ = 1). 

§ 3.3. Èíòåðïðåòàöèè

ÿçûêà ëîãèêè ïðåäèêàòîâ

Êîãäà òîò èëè èíîé ÿçûê ïåðâîãî ïîðÿäêà ïîñò-

ðîåí, âîçíèêàåò çàäà÷à èñòîëêîâàíèÿ îáúåêòîâ ýòîãî ÿçûêà. Èñ-

òîëêîâûâàòü ñèìâîëû, òåðìû è ôîðìóëû ýòîãî ÿçûêà, âêëàäûâàòü

â íèõ ñìûñë ìîæíî ïî-ðàçíîìó.

Ââåäåì ïîíÿòèÿ èíòåðïðåòàöèè ßËÏ

è çíà÷åíèÿ ôîðìóëû â

çàäàííîé èíòåðïðåòàöèè.

Áóäåì ãîâîðèòü, ÷òî çàäàíà èíòåðïðåòàöèÿ

ßËÏ

(èíòåðïðå-

òàöèÿ ñèãíàòóðû σ), åñëè çàäàíî íåïóñòîå ìíîæåñòâî M – ïîëå

èíòåðïðåòàöèè, è:

1) êàæäîìó n-ìåñòíîìó ïðåäèêàòíîìó ñèìâîëó

èç σ ïîñòàâ-

ëåí â ñîîòâåòñòâèå n-ìåñòíûé ïðåäèêàò



íà M, ò. å.



: M

→ {È, Ë};

2) êàæäîìó n-ìåñòíîìó ôóíêöèîíàëüíîìó ñèìâîëó

èç σ

ïîñòàâëåíà â ñîîòâåòñòâèå n-ìåñòíàÿ ôóíêöèÿ



íà M, ò. å.



: M

→ M;

3) êàæäîé ïðåäìåòíîé êîíñòàíòå ñ

èç σ ïîñòàâëåí â ñîîòâåò-

ñòâèå ýëåìåíò



èç M.

Ââåäåì ñëåäóþùèå îáîçíà÷åíèÿ:



Pred

 {



∈Pred



Func

 {



∈ Func



Const

 {



| ñ

∈ Const

Àëãåáðàè÷åñêóþ ñèñòåìó M

= < M,



Pred



Func



Const

áóäåì íàçûâàòü èíòåðïðåòàöèåé ñèãíàòóðû σ.

Èíòåðïðåòàöèÿ – îò ëàò. interpretatio («èñòîëêîâàíèå»).

157

Åñëè ñèãíàòóðà ôèêñèðîâàíà, òî ïðè îáîçíà÷åíèè èíòåðïðåòà-

öèè ýòîé ñèãíàòóðû èíäåêñ σ èíîãäà áóäåì îïóñêàòü, ò. å. ïèñàòü

ïðîñòî M âìåñòî M

S Ïðèìåð. Ðàññìîòðèì ÿçûê ñèãíàòóðû ñ îäíèì äâóìåñòíûì

ïðåäèêàòíûì ñèìâîëîì = , äâóìÿ äâóìåñòíûìè ôóíêöèîíàëüíû-

ìè ñèìâîëàìè + è

⋅

, îäíèì îäíîìåñòíûì ôóíêöèîíàëüíûì ñèì-

âîëîì R è ïðåäìåòíîé êîíñòàíòîé 0. Ýòîò ÿçûê áóäåì íàçûâàòü

ÿçûêîì ôîðìàëüíîé àðèôìåòèêè è îáîçíà÷àòü ß

. Íàèáîëåå âàæ-

íîé èíòåðïðåòàöèåé ýòîãî ÿçûêà ÿâëÿåòñÿ ìíîæåñòâî íàòóðàëüíûõ

÷èñåë ñ îïåðàöèÿìè ñëîæåíèÿ, óìíîæåíèÿ, ïåðåõîäà ê ñëåäóþùå-

ìó è íóëåì: N = < N, = , + ,

⋅

, R, 0 >, ïðåäèêàòíûé ñèìâîë =

èíòåðïðåòèðóåòñÿ êàê îòíîøåíèå ðàâåíñòâà (ñîâïàäåíèÿ). Ýòó èí-

òåðïðåòàöèþ íàçûâàþò ñòàíäàðòíîé èíòåðïðåòàöèåé ß

. 

Ïðèìåð. Äëÿ çàïèñè àêñèîì òåîðèè ãðóïï ìîæíî èñïîëüçî-

âàòü ÿçûê ïåðâîãî ïîðÿäêà, ñèãíàòóðà êîòîðîãî ñîäåðæèò äâóìåñò-

íûé ïðåäèêàòíûé ñèìâîë = , äâóìåñòíûé ôóíêöèîíàëüíûé ñèì-

âîë ∗ è ïðåäìåòíóþ êîíñòàíòó å. Äëÿ ôóíêöèîíàëüíîãî ñèìâîëà è

êîíñòàíòû ïðèíÿòî èñïîëüçîâàòü ïðè àääèòèâíîé ôîðìå çàïèñè

çíàêè + è 0, à ïðè ìóëüòèïëèêàòèâíîé – çíàêè

⋅

è 1 ñîîòâåòñòâåí-

íî. Âñÿêàÿ ãðóïïà ÿâëÿåòñÿ èíòåðïðåòàöèåé ýòîãî ÿçûêà. 

Êàæäîé ôîðìóëå F ßËÏ

â èíòåðïðåòàöèè M

ïîñòàâèì â ñîîò-

âåòñòâèå ñîäåðæàòåëüíîå ïðåäëîæåíèå



åñòåñòâåííîãî ÿçû-

êà, êîòîðîå ïîëó÷àåòñÿ èç ôîðìóëû F ñëåäóþùèì îáðàçîì:

1) êàæäûé ïðåäèêàòíûé ñèìâîë

ôîðìóëû F çàìåíÿþò íà

îáîçíà÷åíèå ñîîòâåòñòâóþùåãî ïðåäèêàòà



;

2) êàæäûé ôóíêöèîíàëüíûé ñèìâîë

ôîðìóëû F – íà îáî-

çíà÷åíèå ñîîòâåòñòâóþùåé ôóíêöèè



;

3) êàæäóþ ïðåäìåòíóþ êîíñòàíòó ñ

ôîðìóëû F – íà ýëåìåíò



èç M;

4) ñâÿçêè &, ∨, ⊃, ¬ çàìåíÿþò ñîîòâåòñòâåííî íà ñëîâà «è»,

«èëè», «åñëè ..., òî», «íå»;

5) êâàíòîðû >õ

è ∃õ

– ñîîòâåòñòâåííî íà ñëîâà «äëÿ âñÿêîãî õ

èç M» è «ñóùåñòâóåò õ

èç M»;

6) ñâîáîäíûå ïðåäìåòíûå ïåðåìåííûå õ

ôîðìóëû F ðàññìàò-

ðèâàþò êàê ïåðåìåííûå ïî ìíîæåñòâó M.

158

S Åñëè ôîðìóëà F çàìêíóòà, òî



ÿâëÿåòñÿ âûñêàçûâàíèåì, à

åñëè ôîðìóëà F èìååò k ñâîáîäíûõ ïåðåìåííûõ, òî



– ïðåäëî-

æåíèå ñ k ïåðåìåííûìè ïî ìíîæåñòâó M (âûñêàçûâàòåëüíàÿ ôîð-

ìà), çàäàþùåå k-ìåñòíûé ïðåäèêàò íà M. Ïðåäëîæåíèå



áóäåì

íàçûâàòü ïðî÷òåíèåì ôîðìóëû F â èíòåðïðåòàöèè M

Ïðèìåðû. Ðàññìîòðèì èíòåðïðåòàöèþ: < N, < > , ãäå N =

= {0, 1, 2, 3, ...}. Äëÿ ñëåäóþùèõ ôîðìóë ïîñòðîèì ïðåäëîæåíèÿ,

ñîîòâåòñòâóþùèå èì â äàííîé èíòåðïðåòàöèè (ÿâëÿþùèåñÿ ïðî-

÷òåíèÿìè ýòèõ ôîðìóë).

1. «Ïðî÷èòàåì» ôîðìóëó ∃ó >õ Ð(õ, ó) â äàííîé èíòåðïðåòàöèè:

«ñóùåñòâóåò (íàòóðàëüíîå) ÷èñëî, êîòîðîå áîëüøå ëþáîãî (íàòóðàëü-

íîãî) ÷èñëà». Ýòî ïðåäëîæåíèå ÿâëÿåòñÿ ëîæíûì âûñêàçûâàíèåì.

2. «Ïðî÷èòàåì» ôîðìóëó >õ ∃ó Ð(õ, ó): «äëÿ âñÿêîãî (íàòóðàëü-

íîãî) ÷èñëà ñóùåñòâóåò áîëüøåå åãî (íàòóðàëüíîå) ÷èñëî». Ýòî ïðåä-

ëîæåíèå ÿâëÿåòñÿ èñòèííûì âûñêàçûâàíèåì.

3. «Ïðî÷èòàåì» ôîðìóëó ∃õ Ð(õ, ó): «ñóùåñòâóåò (íàòóðàëüíîå)

÷èñëî ìåíüøåå, ÷åì ó». Ýòî ïðåäëîæåíèå ñ îäíîé ñâîáîäíîé ïåðå-

ìåííîé. Îíî çàäàåò îäíîìåñòíûé ïðåäèêàò íà ìíîæåñòâå N, êîòî-

ðûé ëîæåí ïðè ó = 0 è èñòèíåí ïðè ëþáîì äðóãîì çíà÷åíèè ó.

4. «Ïðî÷èòàåì» ôîðìóëó >ó Ð(õ, ó): «âñÿêîå (íàòóðàëüíîå) ÷èñ-

ëî áîëüøå õ». Ýòî ïðåäëîæåíèå ñ îäíîé ñâîáîäíîé ïåðåìåííîé

çàäàåò òîæäåñòâåííî ëîæíûé ïðåäèêàò íà N (ïðèíèìàþùèé çíà-

÷åíèå Ë ïðè ëþáîì çíà÷åíèè õ).

5. «Ïðî÷èòàåì» ôîðìóëó ∃ó Ð(õ, ó) â äàííîé èíòåðïðåòàöèè:

«ñóùåñòâóåò íàòóðàëüíîå ÷èñëî áîëüøåå, ÷åì õ». Ýòî ïðåäëîæåíèå

ñ ïåðåìåííîé x çàäàåò òîæäåñòâåííî èñòèííûé ïðåäèêàò íà N.



Àíàëîãè÷íûì îáðàçîì êàæäîìó òåðìó t ßËÏ

â èíòåðïðåòàöèè

ñòàâèòñÿ â ñîîòâåòñòâèå íåêîòîðûé îáúåêò, îáîçíà÷àåìûé ÷å-

ðåç



è ïðåäñòàâëÿþùèé ñîáîé âûðàæåíèå, ïîñòðîåííîå èç ïåðå-

ìåííûõ ïî M è êîíñòàíò èç ìíîæåñòâà



Const

ñ ïîìîùüþ îáîçíà-

÷åíèé äëÿ ôóíêöèé èç ìíîæåñòâà



Func

. Åñëè â òåðì âõîäèëè

ïåðåìåííûå, òî âûðàæåíèå



ïðåäñòàâëÿåò ñîáîé èìåííóþ ôîðìó

è çàäàåò íåêîòîðóþ îïåðàöèþ íà M. Åñëè â òåðì íå âõîäèëè íèêà-

êèå ïåðåìåííûå, òî



– ýòî íåêîòîðûé ýëåìåíò èç M (òî÷íåå èìÿ

ýëåìåíòà èç M). Âûðàæåíèå



áóäåì íàçûâàòü ïðî÷òåíèåì òåðìà t

â èíòåðïðåòàöèè M

159

Ïóñòü çàäàíû ñèãíàòóðà σ, èíòåðïðåòàöèÿ M

ñ ïîëåì M, à

òàêæå n-ìåñòíûé ïðåäèêàò P íà ìíîæåñòâå M. Áóäåì ãîâîðèòü,

÷òî ôîðìóëà F(õ

, …, õ

) ßËÏ

ñî ñâîáîäíûìè ïåðåìåííûìè õ

…, õ

âûðàæàåò ïðåäèêàò P â M

, à ïðåäèêàò P âûðàçèì ñ ïîìî-

ùüþ ôîðìóëû F(õ

, …, õ

) â M

, åñëè äëÿ ëþáûõ à

, …, à

èç M

ïðåäëîæåíèå



(à

, …, à

) èñòèííî â M

òîãäà è òîëüêî òîãäà,

êîãäà P(à

, …, à

) = È.

Ïðåäèêàò P íà ìíîæåñòâå M íàçûâàþò âûðàçèìûì â M

åñëè ñóùåñòâóåò ôîðìóëà F ßËÏ

, êîòîðàÿ âûðàæàåò ýòîò

ïðåäèêàò.

Ïðèìåð. Ðàññìîòðèì ßËÏ

ñ åäèíñòâåííûì äâóìåñòíûì ïðå-

äèêàòíûì ñèìâîëîì ∈ è èíòåðïðåòàöèþ M

ñ íåêîòîðîé ñîâîêóï-

íîñòüþ ìíîæåñòâ â êà÷åñòâå ïîëÿ èíòåðïðåòàöèè è îòíîøåíèåì «õ

ýëåìåíò ó». Çàïèøåì ôîðìóëû, âûðàæàþùèå èçâåñòíûå îòíîøå-

íèÿ ìåæäó ìíîæåñòâàìè èëè ñâîéñòâà ìíîæåñòâ, êîòîðûå èñïîëü-

çóþò â èíòóèòèâíîé òåîðèè ìíîæåñòâ:

à) ôîðìóëà >z (z ∈ õ

z ∈ ó) âûðàæàåò ïðåäèêàò ðàâåíñòâà

ìíîæåñòâ (õ = ó);

á) ôîðìóëà >z (z ∈ õ ⊃ z ∈ ó) âûðàæàåò ïðåäèêàò âêëþ÷åíèÿ

(õ ⊆ ó);

â) ôîðìóëà >ó ¬(y ∈ x) âûðàæàåò ïðåäèêàò «õ – ïóñòîå ìíîæå-

ñòâî».



Ïðèìåð. Ðàññìîòðèì ñèãíàòóðó { = ,

⋅

, 1} è èíòåðïðåòàöèþ

ñ ïîëåì N, îòíîøåíèåì ðàâåíñòâà, îïåðàöèåé óìíîæåíèÿ è

åäèíèöåé. Â ýòîé èíòåðïðåòàöèè:

à) ôîðìóëà ∃z (ó = õæz) âûðàæàåò ïðåäèêàò äåëèìîñòè «õ äåëèò ó»;

á) ôîðìóëà >y (∃z (õ = óæz) ⊃ ó = 1 ∨ ó = õ) & ¬(õ = 1) âûðàæàåò

ïðåäèêàò «õ – ïðîñòîå ÷èñëî».



×àñòî ïðè çàïèñè ìàòåìàòè÷åñêèõ ïðåäëîæåíèé

èñïîëüçóþò ñèìâîëèêó, ïîçâîëÿþùóþ ñäåëàòü

çàïèñü çíà÷èòåëüíî êîðî÷å. Òàêîâû, íàïðèìåð,

èñïîëüçóåìûå íàìè ñèìâîëè÷åñêèå çàïèñè ìå-

òàÿçûêà (õ) P(õ) è (Eõ) P(õ) äëÿ ïðåäëîæåíèé

«äëÿ âñÿêîãî õ P (õ)» è «ñóùåñòâóåò õ òàêîå, ÷òî P(õ)» ñîîòâåòñòâåí-

íî. Ñèíòàêñèñ òàêèõ è ïîäîáíûõ èì çàïèñåé ñîîòâåòñòâóåò ñèí-

òàêñèñó ßËÏ.

S Â ìàòåìàòè÷åñêèõ òåêñòàõ ÷àñòî âñòðå÷àþòñÿ ïðåäëîæåíèÿ ñëå-

äóþùåãî âèäà: «âñÿêèé îáúåêò, îáëàäàþùèé ñâîéñòâîì P, îáëàäàåò

Символическая

запись

математических

предложений

160

ñâîéñòâîì Q». Ëîãè÷åñêàÿ ñòðóêòóðà òàêèõ ïðåäëîæåíèé âûÿâëÿåò-

ñÿ (îòðàæàåòñÿ) ïðè èõ ñèìâîëè÷åñêîé çàïèñè:

(õ) (P(õ) → Q(õ)).

S Íå ìåíåå ðàñïðîñòðàíåíû ïðåäëîæåíèÿ äðóãîãî âèäà: «íåêîòî-

ðûå îáúåêòû, îáëàäàþùèå ñâîéñòâîì P, îáëàäàþò ñâîéñòâîì Q».

Òîò æå ñìûñë èìåþò ïðåäëîæåíèÿ âèäà: «ñóùåñòâóåò îáúåêò, îáëà-

äàþùèé ñâîéñòâîì P, êîòîðûé îáëàäàåò ñâîéñòâîì Q». Îòðàçèì

ëîãè÷åñêóþ ñòðóêòóðó òàêèõ ïðåäëîæåíèé â èõ ñèìâîëè÷åñêîé çà-

ïèñè:

(Eõ) (P(õ) & Q(õ)).

Â îáîèõ ïðèìåðàõ P(õ) ìîæíî ðàññìàòðèâàòü êàê íåêîòîðîå

îãðàíè÷èâàþùåå óñëîâèå íà õ.

S Äëÿ çàïèñè òàêèõ ïðåäëîæåíèé íà ïðàêòèêå îáû÷íî èñïîëüçó-

þò òàê íàçûâàåìûå (íåôîðìàëüíûå) îãðàíè÷åííûå êâàíòîðû:

âìåñòî (õ) (P(õ) → Q(õ)) ïèøóò (õ)

P(õ)

Q(õ),

à âìåñòî (Eõ) (P(õ) & Q(õ)) ïèøóò (Eõ)

P(õ)

Q(õ).

Íàïðèìåð, ïðåäëîæåíèå «äëÿ âñÿêîãî íåîòðèöàòåëüíîãî õ ñó-

ùåñòâóåò íåîòðèöàòåëüíîå ÷èñëî, êâàäðàò êîòîðîãî ðàâåí õ» (ãäå

õ – äåéñòâèòåëüíàÿ ïåðåìåííàÿ) áåç èñïîëüçîâàíèÿ îãðàíè÷åííûõ

êâàíòîðîâ çàïèñûâàþò òàê:

(õ) (õ  0 → (Eó) (ó  0 & õ = ó

)).

Èñïîëüçóÿ îãðàíè÷åííûå êâàíòîðû, åãî ìîæíî çàïèñàòü êîðî÷å:

(õ)

 0

(Eó)

 0

(õ = ó

Äëÿ ôîðìóë ßËÏ òàêæå ìîæíî èñïîëüçîâàòü (ôîðìàëüíûå)

îãðàíè÷åííûå êâàíòîðû, ââåäÿ ñëåäóþùèå îáîçíà÷åíèÿ:

>õ

À(õ)

B(õ)  >õ (À(õ) ⊃ B(õ));

∃õ

À(õ)

B(õ)  ∃õ (À(õ) & Â(õ)).

Òàê, íàïðèìåð, óñëîâèå, îïðåäåëÿþùåå ôóíêöèþ f, íåïðåðûâ-

íóþ â òî÷êå à (áóäåì ñ÷èòàòü, ÷òî f îïðåäåëåíà íà ïðîìåæóòêå D,

ñîäåðæàùåì òî÷êó à), çàïèñûâàþò â âèäå ôîðìóëû ÿçûêà ñîîòâåò-

ñòâóþùåé ñèãíàòóðû òàê:

>ε (ε > 0 ⊃ ∃δ (δ > 0 & >õ (õ ∈ D ⊃ (| õ – à | < δ ⊃ | f(õ) – f(à)| < ε)))).

Ñ ïîìîùüþ îãðàíè÷åííûõ êâàíòîðîâ ìîæíî òî æå ñàìîå çàïè-

ñàòü êîðî÷å è áîëåå îáîçðèìî:

>ε

ε > 0

∃δ

δ > 0

∀ õ

x ∈ D

(| õ – à | < δ ⊃ | f(õ) – f(à)| < ε).

Áîëåå ïðèâû÷íî ýòî ìîæíî çàïèñàòü òàê:

>ε

> 0 ∃δ

> 0 ∀õ

∈

D (| õ – à | < δ ⊃ | f(õ) – f(à)| < ε).