Самохин А.В. Математическая логика и теория алгоритмов

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

§4. ÷ÙÒÁÚÉÍÏÓÔØ × ÁÒÉÆÍÅÔÉËÅ 111

üÔÏ ÓÏÏÔ×ÅÔÓÔ×ÉÅ ÚÁÄÁ¾ÔÓÑ ÔÁË: ÞÔÏÂÙ ÐÏÌÕÞÉÔØ ÓÌÏ×Ï, ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÅÅ

ÞÉÓÌÕ n, ÎÁÄÏ ÚÁÐÉÓÁÔØ n + 1 × Ä×ÏÉÞÎÏÊ ÓÉÓÔÅÍÅ É ÕÄÁÌÉÔØ ÐÅÒ×ÕÀ ÅÄÉÎÉ-

ÃÕ. îÁÐÒÉÍÅÒ, ÎÕÌÀ ÓÏÏÔ×ÅÔÓÔ×ÕÅÔ ÐÕÓÔÏÅ ÓÌÏ×Ï ˜, ÞÉÓÌÕ 15 ¡ ÓÌÏ×Ï 0000

É Ô. Ä. ôÅÐÅÒØ ÍÏÖÎÏ ÇÏ×ÏÒÉÔØ ÏÂ ÁÒÉÆÍÅÔÉÞÎÏÓÔÉ ÐÒÅÄÉËÁÔÏ×, ÏÐÒÅÄÅÌ¾Î-

ÎÙÈ ÎÁ Ä×ÏÉÞÎÙÈ ÓÌÏ×ÁÈ, ÉÍÅÑ × ×ÉÄÕ ÁÒÉÆÍÅÔÉÞÎÏÓÔØ ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÉÈ

ÐÒÅÄÉËÁÔÏ× ÎÁ N.

• ðÒÅÄÉËÁÔ ¥ÓÌÏ×Ï x ÓÏÓÔÏÉÔ ÉÚ ÏÄÎÉÈ ÎÕÌÅÊ¥ ÁÒÉÆÍÅÔÉÞÅÎ. ÷ ÓÁÍÏÍ

ÄÅÌÅ, ÐÒÉ ÐÅÒÅÈÏÄÅ Ë ÞÉÓÌÁÍ ÅÍÕ ÓÏÏÔ×ÅÔÓÔ×ÕÅÔ ÐÒÅÄÉËÁÔ x + 1 ÅÓÔØ

ÓÔÅÐÅÎØ Ä×ÏÊËÉ¥, ËÏÔÏÒÙÊ (ËÁË ÍÙ ×ÉÄÅÌÉ) ÁÒÉÆÍÅÔÉÞÅÎ.

• ðÒÅÄÉËÁÔ ¥ÓÌÏ×Á x É y ÉÍÅÀÔ ÏÄÉÎÁËÏ×ÕÀ ÄÌÉÎÕ¥ ÁÒÉÆÍÅÔÉÞÅÎ. ÷

ÓÁÍÏÍ ÄÅÌÅ, ÜÔÏ ÏÚÎÁÞÁÅÔ, ÞÔÏ ÎÁÊÄ¾ÔÓÑ ÓÔÅÐÅÎØ Ä×ÏÊËÉ c, ÄÌÑ ËÏÔÏÒÏÊ

c − 1 6 x, y < 2c − 1 (ÉÍÅÎÎÏ ÔÁËÏÊ ÐÒÏÍÅÖÕÔÏË ÚÁÐÏÌÎÑÀÔ ÞÉÓÌÁ,

ËÏÔÏÒÙÍ ÓÏÏÔ×ÅÔÓÔ×ÕÀÔ ÓÌÏ×Á ÏÄÎÏÊ ÄÌÉÎÙ).

• ðÒÅÄÉËÁÔ ¥ÓÌÏ×Ï z Ñ×ÌÑÅÔÓÑ ËÏÎËÁÔÅÎÁÃÉÅÊ ÓÌÏ× x É y¥ (ÐÒÏÝÅ ÇÏ×Ï-

ÒÑ, z ÐÏÌÕÞÁÅÔÓÑ ÐÒÉÐÉÓÙ×ÁÎÉÅÍ y ÓÐÒÁ×Á Ë ÓÌÏ×Õ x) ÁÒÉÆÍÅÔÉÞÅÎ.

÷ ÓÁÍÏÍ ÄÅÌÅ, ÅÇÏ ÍÏÖÎÏ ×ÙÒÁÚÉÔØ ÔÁË: ÎÁÊÄ¾ÔÓÑ ÓÌÏ×Ï y

ÉÚ ÏÄÎÉÈ

ÎÕÌÅÊ, ÉÍÅÀÝÅÅ ÔÕ ÖÅ ÄÌÉÎÕ, ÞÔÏ É ÓÌÏ×Ï y, ÐÒÉ ÜÔÏÍ (z + 1) =

= (x + 1)(y

+ 1) + (y − y

) (ÕÍÎÏÖÅÎÉÅ ÎÁ y

+ 1 ÓÏÏÔ×ÅÔÓÔ×ÕÅÔ ÄÏ-

ÐÉÓÙ×ÁÎÉÀ ÎÕÌÅÊ, Á ÄÏÂÁ×ÌÅÎÉÅ y − y

ÚÁÍÅÎÑÅÔ ÎÕÌÉ ÎÁ ÂÕË×Ù ÓÌÏ×Á

y).

• ðÒÅÄÉËÁÔ ¥ÓÌÏ×Ï x Ñ×ÌÑÅÔÓÑ ÎÁÞÁÌÏÍ ÓÌÏ×Á y¥ ÁÒÉÆÍÅÔÉÞÅÎ. ÷ ÓÁÍÏÍ

ÄÅÌÅ, ÜÔÏ ÏÚÎÁÞÁÅÔ, ÞÔÏ ÓÕÝÅÓÔ×ÕÅÔ ÓÌÏ×Ï t, ÐÒÉ ËÏÔÏÒÏÍ y ÅÓÔØ ËÏÎËÁ-

ÔÅÎÁÃÉÑ x É t.

• ôÏ ÖÅ ÓÁÍÏÅ ×ÅÒÎÏ ÄÌÑ ÐÒÅÄÉËÁÔÏ× ¥x ÅÓÔØ ËÏÎÅÃ ÓÌÏ×Á y¥, ¥x ÅÓÔØ

ÐÏÄÓÌÏ×Ï ÓÌÏ×Á y¥ (ÐÏÓÌÅÄÎÅÅ ÏÚÎÁÞÁÅÔ, ÞÔÏ ÎÁÊÄÕÔÓÑ ÓÌÏ×Á u É v, ÄÌÑ

ËÏÔÏÒÙÈ y ÅÓÔØ ËÏÎËÁÔÅÎÁÃÉÑ u, x É v; ËÏÎËÁÔÅÎÁÃÉÑ ÔÒ¾È ÓÌÏ× ×ÙÒÁ-

ÚÉÍÁ ÞÅÒÅÚ ËÏÎËÁÔÅÎÁÃÉÀ Ä×ÕÈ).

• óÕÝÅÓÔ×ÕÅÔ ÁÒÉÆÍÅÔÉÞÅÓËÉÊ ÔÒ¾ÈÍÅÓÔÎÙÊ ÐÒÅÄÉËÁÔ S(x, a, b) Ó ÔÁËÉ-

ÍÉ Ó×ÏÊÓÔ×ÁÍÉ: (Á) ÄÌÑ ÌÀÂÙÈ a É b ÍÎÏÖÅÓÔ×Ï S

= {x | S(x, a, b)}

ËÏÎÅÞÎÏ; (Â) ÓÒÅÄÉ ÍÎÏÖÅÓÔ× S

ÐÒÉ ÒÁÚÌÉÞÎÙÈ ÐÁÒÁÈ a, b ×ÓÔÒÅÞÁÀÔ-

ÓÑ ×ÓÅ ËÏÎÅÞÎÙÅ ÍÎÏÖÅÓÔ×Á. îÁÐÒÉÍÅÒ, × ËÁÞÅÓÔ×Å ÔÁËÏÇÏ ÐÒÅÄÉËÁÔÁ

ÍÏÖÎÏ ×ÚÑÔØ ¥axa ÅÓÔØ ÐÏÄÓÌÏ×Ï ÓÌÏ×Á b¥ (ÚÄÅÓØ axa ÅÓÔØ ËÏÎËÁÔÅÎÁÃÉÑ

ÔÒ¾È ÓÌÏ×: a, x É ÓÎÏ×Á a).

÷ ÓÁÍÏÍ ÄÅÌÅ, ÑÓÎÏ, ÞÔÏ ÓÌÏ×Ï x ÎÅ ÄÌÉÎÎÅÅ ÓÌÏ×Á b, É ÐÏÔÏÍÕ ÍÎÏ-

ÖÅÓÔ×Ï S

×ÓÅÇÄÁ ËÏÎÅÞÎÏ. ó ÄÒÕÇÏÊ ÓÔÏÒÏÎÙ, ÐÕÓÔØ ÉÍÅÅÔÓÑ ÎÅËÏÔÏÒÏÅ

ËÏÎÅÞÎÏÅ ÍÎÏÖÅÓÔ×Ï ÓÌÏ× x

, . . . , x

. ðÏÌÏÖÉÍ a = 100 . . . 001, ÇÄÅ ÞÉÓÌÏ

ÎÕÌÅÊ ÂÏÌØÛÅ ÄÌÉÎÙ ÌÀÂÏÇÏ ÉÚ ÓÌÏ× x

, É b = ax

a . . . ax

ðÏÓÌÅÄÎÅÅ ÕÔ×ÅÒÖÄÅÎÉÅ ÎÅ ÕÐÏÍÉÎÁÅÔ Ñ×ÎÏ Ï ÓÌÏ×ÁÈ, É ÂÏÌØÛÅ ÏÎÉ ÎÁÍ

ÎÅ ÐÏÎÁÄÏÂÑÔÓÑ: ÄÏÓÔÁÔÏÞÎÏ ÚÎÁÔØ, ÞÔÏ ËÏÎÅÞÎÙÅ ÍÎÏÖÅÓÔ×Á ÎÁÔÕÒÁÌØÎÙÈ

112 çÌÁ×Á V. ñÚÙËÉ ÐÅÒ×ÏÇÏ ÐÏÒÑÄËÁ

ÞÉÓÅÌ ÍÏÖÎÏ ËÏÄÉÒÏ×ÁÔØ ÐÁÒÁÍÉ ÎÁÔÕÒÁÌØÎÙÈ ÞÉÓÅÌ × ÏÐÉÓÁÎÎÏÍ ÓÍÙÓÌÅ.

ôÅÐÅÒØ ÍÙ ÍÏÖÅÍ ×ÙÒÁÚÉÔØ, ÞÔÏ ÞÉÓÌÏ x Ñ×ÌÑÅÔÓÑ ÓÔÅÐÅÎØÀ ÞÉÓÌÁ 4,

ÓÌÅÄÕÀÝÉÍ ÏÂÒÁÚÏÍ: ÓÕÝÅÓÔ×ÕÅÔ ËÏÎÅÞÎÏÅ ÍÎÏÖÅÓÔ×Ï U, ËÏÔÏÒÏÅ ÓÏÄÅÒÖÉÔ

ÞÉÓÌÏ x É ÏÂÌÁÄÁÅÔ ÔÁËÉÍ Ó×ÏÊÓÔ×ÏÍ: ×ÓÑËÉÊ ÜÌÅÍÅÎÔ u ∈ U ÌÉÂÏ ÒÁ×ÅÎ 1,

ÌÉÂÏ ÄÅÌÉÔÓÑ ÎÁ 4 É u/4 ÔÁËÖÅ ÐÒÉÎÁÄÌÅÖÉÔ U. ôÅÐÅÒØ ÎÁÄÏ ×ÅÚÄÅ ÚÁÍÅÎÉÔØ

ÍÎÏÖÅÓÔ×Ï U ÎÁ ÅÇÏ ËÏÄ u

, u

, Á ÕÔ×ÅÒÖÄÅÎÉÅ x ∈ U ÎÁ S(x, u

, u

), ÇÄÅ S ¡

ÐÏÓÔÒÏÅÎÎÙÊ ÎÁÍÉ ËÏÄÉÒÕÀÝÉÊ ÐÒÅÄÉËÁÔ.

îÅÍÎÏÇÏ ÓÌÏÖÎÅÅ ×ÙÒÁÚÉÔØ Ä×ÕÍÅÓÔÎÙÊ ÐÒÅÄÉËÁÔ x = 4

. úÄÅÓØ ÎÁÍ ÈÏ-

ÔÅÌÏÓØ ÂÙ ÓËÁÚÁÔØ ÔÁË: ÓÕÝÅÓÔ×ÕÅÔ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ x

, x

, . . . , x

, ÄÌÑ

ËÏÔÏÒÏÊ x

= 1, ËÁÖÄÙÊ ÓÌÅÄÕÀÝÉÊ ÞÌÅÎ ×ÞÅÔ×ÅÒÏ ÂÏÌØÛÅ ÐÒÅÄÙÄÕÝÅ-

ÇÏ (x

i+1

= 4x

) É x

= x. ëÁË ÎÁÕÞÉÔØÓÑ ÇÏ×ÏÒÉÔØ Ï ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏ-

ÓÔÑÈ, ÅÓÌÉ ÍÙ ÕÍÅÅÍ ÇÏ×ÏÒÉÔØ Ï ÍÎÏÖÅÓÔ×ÁÈ? ÷ÓÐÏÍÎÉÍ, ÞÔÏ × ÔÅÒÍÉ-

ÎÁÈ ÔÅÏÒÉÉ ÍÎÏÖÅÓÔ× ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ ÅÓÔØ ÆÕÎËÃÉÑ, ÏÐÒÅÄÅÌ¾ÎÎÁÑ ÎÁ

ÎÁÞÁÌØÎÏÍ ÏÔÒÅÚËÅ ÎÁÔÕÒÁÌØÎÏÇÏ ÒÑÄÁ, ÔÏ ÅÓÔØ ËÏÎÅÞÎÏÅ ÍÎÏÖÅÓÔ×Ï ÐÁÒ

{h0, x

i, h1, x

i, . . . , hk, x

i}. ðÁÒÙ ÍÏÖÎÏ ËÏÄÉÒÏ×ÁÔØ ÞÉÓÌÁÍÉ. îÁÐÒÉÍÅÒ,

ÍÏÖÎÏ ÓÞÉÔÁÔØ ËÏÄÏÍ ÐÁÒÙ hx, yi ÞÉÓÌÏ c = (x + y)

+ x, ÐÏÓËÏÌØËÕ ÐÏ ÎÅÍÕ

ÁÒÉÆÍÅÔÉÞÅÓËÉ ×ÏÓÓÔÁÎÁ×ÌÉ×ÁÅÔÓÑ x + y (ËÁË ÎÁÉÂÏÌØÛÅÅ ÞÉÓÌÏ, Ë×ÁÄÒÁÔ

ËÏÔÏÒÏÇÏ ÎÅ ÐÒÅ×ÏÓÈÏÄÉÔ c), Á ÚÁÔÅÍ x É y. ôÅÐÅÒØ ËÏÎÅÞÎÏÅ ÍÎÏÖÅÓÔ×Ï ÐÁÒ

ÍÏÖÎÏ ÚÁÍÅÎÉÔØ ËÏÎÅÞÎÙÍ ÍÎÏÖÅÓÔ×ÏÍ ÉÈ ËÏÄÏ×, ËÏÔÏÒÏÅ × Ó×ÏÀ ÏÞÅÒÅÄØ

ÍÏÖÎÏ ÚÁËÏÄÉÒÏ×ÁÔØ ÐÁÒÏÊ ÞÉÓÅÌ.

úÁÄÁÞÁ 146. ðÒÏ×ÅÄÉÔÅ ÜÔÏ ÒÁÓÓÕÖÄÅÎÉÅ ÐÏÄÒÏÂÎÏ.

úÁÄÁÞÁ 147. ðÏËÁÖÉÔÅ, ÞÔÏ Ä×ÕÍÅÓÔÎÙÊ ÐÒÅÄÉËÁÔ ¥x ÅÓÔØ n-ÏÅ ÐÏ

ÐÏÒÑÄËÕ ÐÒÏÓÔÏÅ ÞÉÓÌÏ¥ ÁÒÉÆÍÅÔÉÞÅÎ.

§5. îÅ×ÙÒÁÚÉÍÙÅ ÐÒÅÄÉËÁÔÙ: Á×ÔÏÍÏÒÆÉÚÍÙ

íÙ ×ÉÄÅÌÉ, ËÁË ÍÏÖÎÏ ÄÏËÁÚÁÔØ ×ÙÒÁÚÉÍÏÓÔØ ÎÅËÏÔÏÒÙÈ Ó×ÏÊÓÔ×. óÅÊÞÁÓ

ÍÙ ÐÏËÁÖÅÍ, ËÁËÉÍ ÏÂÒÁÚÏÍ ÍÏÖÎÏ ÄÏËÁÚÙ×ÁÔØ ÎÅ×ÙÒÁÚÉÍÏÓÔØ.

îÁÞÎ¾Í Ó ÔÁËÏÇÏ ÐÒÉÍÅÒÁ. ðÕÓÔØ ÓÉÇÎÁÔÕÒÁ ÓÏÄÅÒÖÉÔ Ä×ÕÍÅÓÔÎÙÊ ÐÒÅ-

ÄÉËÁÔ ÒÁ×ÅÎÓÔ×Á (=) É Ä×ÕÍÅÓÔÎÕÀ ÏÐÅÒÁÃÉÀ ÓÌÏÖÅÎÉÑ (+). òÁÓÓÍÏÔÒÉÍ Å¾

ÉÎÔÅÒÐÒÅÔÁÃÉÀ, ÎÏÓÉÔÅÌÅÍ ËÏÔÏÒÏÊ Ñ×ÌÑÀÔÓÑ ÃÅÌÙÅ ÞÉÓÌÁ, Á ÒÁ×ÅÎÓÔ×Ï É

ÓÌÏÖÅÎÉÅ ÉÎÔÅÒÐÒÅÔÉÒÕÀÔÓÑ ÓÔÁÎÄÁÒÔÎÙÍ ÏÂÒÁÚÏÍ. ïËÁÚÙ×ÁÅÔÓÑ, ÞÔÏ ÐÒÅ-

ÄÉËÁÔ x > y ÎÅ Ñ×ÌÑÅÔÓÑ ×ÙÒÁÚÉÍÙÍ.

ðÒÉÞÉÎÁ ÏÞÅ×ÉÄÎÁ: Ó ÔÏÞËÉ ÚÒÅÎÉÑ ÓÌÏÖÅÎÉÑ ÃÅÌÙÅ ÞÉÓÌÁ ÕÓÔÒÏÅÎÙ ÓÉÍ-

ÍÅÔÒÉÞÎÏ, ÐÏÌÏÖÉÔÅÌØÎÙÅ ÎÉÞÅÍ ÎÅ ÏÔÌÉÞÁÀÔÓÑ ÏÔ ÏÔÒÉÃÁÔÅÌØÎÙÈ. åÓÌÉ

ÍÙ ÉÚÍÅÎÉÍ ÚÎÁË Õ ×ÓÅÈ ÐÅÒÅÍÅÎÎÙÈ, ×ÈÏÄÑÝÉÈ × ÆÏÒÍÕÌÕ, ÔÏ Å¾ ÉÓÔÉÎÎÏÓÔØ

ÎÅ ÍÏÖÅÔ ÉÚÍÅÎÉÔØÓÑ. îÏ ÐÒÉ ÜÔÏÍ x > y ÚÁÍÅÎÉÔÓÑ ÎÁ x < y, É ÐÏÔÏÍÕ ÜÔÏ

Ó×ÏÊÓÔ×Ï ÎÅ Ñ×ÌÑÅÔÓÑ ×ÙÒÁÚÉÍÙÍ.

§5. îÅ×ÙÒÁÚÉÍÙÅ ÐÒÅÄÉËÁÔÙ: Á×ÔÏÍÏÒÆÉÚÍÙ 113

æÏÒÍÁÌØÎÏ ÇÏ×ÏÒÑ, ÎÁÄÏ ÄÏËÁÚÙ×ÁÔØ ÐÏ ÉÎÄÕËÃÉÉ ÔÁËÏÅ Ó×ÏÊÓÔ×Ï: ÅÓÌÉ

ÆÏÒÍÕÌÁ ϕ ÕËÁÚÁÎÎÏÊ ÓÉÇÎÁÔÕÒÙ ÉÓÔÉÎÎÁ ÐÒÉ ÏÃÅÎËÅ π, ÔÏ ÏÎÁ ÉÓÔÉÎÎÁ É

ÐÒÉ ÏÃÅÎËÅ π

, × ËÏÔÏÒÏÊ ÚÎÁÞÅÎÉÑ ×ÓÅÈ ÐÅÒÅÍÅÎÎÙÈ ÍÅÎÑÀÔ ÚÎÁË. (ðÏÄÒÏÂÎÏ

ÍÙ ÏÂßÑÓÎÉÍ ÜÔÏ × ÏÂÝÅÊ ÓÉÔÕÁÃÉÉ ÄÁÌØÛÅ.)

óÆÏÒÍÕÌÉÒÕÅÍ ÏÂÝÕÀ ÓÈÅÍÕ, ËÏÔÏÒÏÊ ÓÌÅÄÕÅÔ ÜÔÏ ÒÁÓÓÕÖÄÅÎÉÅ. ðÕÓÔØ

ÉÍÅÅÔÓÑ ÎÅËÏÔÏÒÁÑ ÓÉÇÎÁÔÕÒÁ σ É ÉÎÔÅÒÐÒÅÔÁÃÉÑ ÜÔÏÊ ÓÉÇÎÁÔÕÒÙ, ÎÏÓÉ-

ÔÅÌÅÍ ËÏÔÏÒÏÊ Ñ×ÌÑÅÔÓÑ ÍÎÏÖÅÓÔ×Ï M. ÷ÚÁÉÍÎÏ ÏÄÎÏÚÎÁÞÎÏÅ ÏÔÏÂÒÁÖÅÎÉÅ

α: M → M ÎÁÚÙ×ÁÅÔÓÑ Á×ÔÏÍÏÒÆÉÚÍÏÍ ÉÎÔÅÒÐÒÅÔÁÃÉÉ, ÅÓÌÉ ×ÓÅ ÆÕÎËÃÉÉ

É ÐÒÅÄÉËÁÔÙ, ×ÈÏÄÑÝÉÅ × ÉÎÔÅÒÐÒÅÔÁÃÉÀ, ÕÓÔÏÊÞÉ×Ù ÏÔÎÏÓÉÔÅÌØÎÏ α. ðÒÉ

ÜÔÏÍ k-ÍÅÓÔÎÙÊ ÐÒÅÄÉËÁÔ P ÎÁÚÙ×ÁÅÔÓÑ ÕÓÔÏÊÞÉ×ÙÍ ÏÔÎÏÓÉÔÅÌØÎÏ α, ÅÓÌÉ

P (α(m

), . . . , α(m

)) ⇔ P (m

, . . . , m

)

ÄÌÑ ÌÀÂÙÈ ÜÌÅÍÅÎÔÏ× m

, . . . , m

∈ M. áÎÁÌÏÇÉÞÎÙÍ ÏÂÒÁÚÏÍ k-ÍÅÓÔÎÁÑ

ÆÕÎËÃÉÑ f ÎÁÚÙ×ÁÅÔÓÑ ÕÓÔÏÊÞÉ×ÏÊ ÏÔÎÏÓÉÔÅÌØÎÏ α, ÅÓÌÉ

f(α(m

), . . . , α(m

)) = α(f(m

, . . . , m

)).

üÔÏ ÏÐÒÅÄÅÌÅÎÉÅ ÏÂÏÂÝÁÅÔ ÓÔÁÎÄÁÒÔÎÏÅ ÏÐÒÅÄÅÌÅÎÉÅ Á×ÔÏÍÏÒÆÉÚÍÁ ÄÌÑ

ÇÒÕÐÐ, ËÏÌÅÃ, ÐÏÌÅÊ É Ô. Ä.

ôÅÏÒÅÍÁ 37. ðÒÅÄÉËÁÔ, ×ÙÒÁÚÉÍÙÊ × ÄÁÎÎÏÊ ÉÎÔÅÒÐÒÅÔÁÃÉÉ, ÕÓÔÏÊ-

ÞÉ× ÏÔÎÏÓÉÔÅÌØÎÏ Å¾ Á×ÔÏÍÏÒÆÉÚÍÏ×.

äÏËÁÚÁÔÅÌØÓÔ×Ï. ðÒÏ×ÅÄ¾Í ÄÏËÁÚÁÔÅÌØÓÔ×Ï ÜÔÏÇÏ (ÄÏÓÔÁÔÏÞÎÏ ÏÞÅ×ÉÄÎÏ-

ÇÏ) ÕÔ×ÅÒÖÄÅÎÉÑ ÆÏÒÍÁÌØÎÏ.

ðÕÓÔØ π ¡ ÎÅËÏÔÏÒÁÑ ÏÃÅÎËÁ, ÔÏ ÅÓÔØ ÏÔÏÂÒÁÖÅÎÉÅ, ÓÔÁ×ÑÝÅÅ × ÓÏÏÔ×ÅÔ-

ÓÔ×ÉÅ ×ÓÅÍ ÉÎÄÉ×ÉÄÎÙÍ ÐÅÒÅÍÅÎÎÙÍ ÎÅËÏÔÏÒÙÅ ÜÌÅÍÅÎÔÙ ÎÏÓÉÔÅÌÑ. þÅÒÅÚ

α ◦ π ÏÂÏÚÎÁÞÉÍ ÏÃÅÎËÕ, ËÏÔÏÒÁÑ ÐÏÌÕÞÉÔÓÑ, ÅÓÌÉ Ë ÚÎÁÞÅÎÉÀ ËÁÖÄÏÊ ÐÅÒÅ-

ÍÅÎÎÏÊ ÐÒÉÍÅÎÉÔØ ÏÔÏÂÒÁÖÅÎÉÅ α; ÄÒÕÇÉÍÉ ÓÌÏ×ÁÍÉ, α ◦ π(ξ) = α(π(ξ)) ÄÌÑ

ÌÀÂÏÊ ÐÅÒÅÍÅÎÎÏÊ ξ.

ðÅÒ×ÙÊ ÛÁÇ ÓÏÓÔÏÉÔ × ÔÏÍ, ÞÔÏÂÙ ÉÎÄÕËÃÉÅÊ ÐÏ ÐÏÓÔÒÏÅÎÉÀ ÔÅÒÍÁ t

ÄÏËÁÚÁÔØ ÔÁËÏÅ ÕÔ×ÅÒÖÄÅÎÉÅ: ÚÎÁÞÅÎÉÅ ÔÅÒÍÁ t ÐÒÉ ÏÃÅÎËÅ α ◦ π ÐÏÌÕÞÁÅÔÓÑ

ÐÒÉÍÅÎÅÎÉÅÍ α Ë ÚÎÁÞÅÎÉÀ ÔÅÒÍÁ t ÐÒÉ ÏÃÅÎËÅ π:

[t](α ◦ π) = α([t](π)).

äÌÑ ÐÅÒÅÍÅÎÎÙÈ ÜÔÏ ÏÞÅ×ÉÄÎÏ, Á ÛÁÇ ÉÎÄÕËÃÉÉ ÉÓÐÏÌØÚÕÅÔ ÕÓÔÏÊÞÉ×ÏÓÔØ

×ÓÅÈ ÆÕÎËÃÉÊ ÉÎÔÅÒÐÒÅÔÁÃÉÉ ÏÔÎÏÓÉÔÅÌØÎÏ α.

ôÅÐÅÒØ ÉÎÄÕËÃÉÅÊ ÐÏ ÐÏÓÔÒÏÅÎÉÀ ÆÏÒÍÕÌÙ ϕ ÌÅÇËÏ ÄÏËÁÚÁÔØ ÔÁËÏÅ ÕÔ×ÅÒ-

ÖÄÅÎÉÅ:

[ϕ](α ◦ π) = [ϕ](π).

íÙ ÎÅ ÂÕÄÅÍ ×ÙÐÉÓÙ×ÁÔØ ÜÔÕ ÐÒÏ×ÅÒËÕ; ÓËÁÖÅÍ ÌÉÛØ, ÞÔÏ ×ÚÁÉÍÎÁÑ ÏÄÎÏ-

ÚÎÁÞÎÏÓÔØ α ÉÓÐÏÌØÚÕÅÔÓÑ, ËÏÇÄÁ ÍÙ ÒÁÚÂÉÒÁÅÍ ÓÌÕÞÁÊ Ë×ÁÎÔÏÒÏ×. (÷ ÓÁÍÏÍ

114 çÌÁ×Á V. ñÚÙËÉ ÐÅÒ×ÏÇÏ ÐÏÒÑÄËÁ

ÄÅÌÅ, ÅÓÌÉ Ó ÏÄÎÏÊ ÓÔÏÒÏÎÙ ÉÚÏÍÏÒÆÉÚÍÁ ÂÅÒ¾ÔÓÑ ËÁËÏÊ-ÔÏ ÏÂßÅËÔ, ÔÏ ×ÚÁÉÍ-

ÎÁÑ ÏÄÎÏÚÎÁÞÎÏÓÔØ ÐÏÚ×ÏÌÑÅÔ ×ÚÑÔØ ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÉÊ ÅÍÕ ÏÂßÅËÔ Ó ÄÒÕÇÏÊ

ÓÔÏÒÏÎÙ ÉÚÏÍÏÒÆÉÚÍÁ.)

ôÅÏÒÅÍÁ 37 ÐÏÚ×ÏÌÑÅÔ ÄÏËÁÚÁÔØ ÎÅ×ÙÒÁÚÉÍÏÓÔØ ËÁËÏÇÏ-ÔÏ ÐÒÅÄÉËÁÔÁ,

ÐÒÅÄßÑ×É× Á×ÔÏÍÏÒÆÉÚÍ ÉÎÔÅÒÐÒÅÔÁÃÉÉ, ÏÔÎÏÓÉÔÅÌØÎÏ ËÏÔÏÒÏÇÏ ÉÎÔÅÒÅ-

ÓÕÀÝÉÊ ÎÁÓ ÐÒÅÄÉËÁÔ ÎÅÕÓÔÏÊÞÉ×. ÷ÏÔ ÎÅÓËÏÌØËÏ ÐÒÉÍÅÒÏ×:

• (Z, =, <) óÉÇÎÁÔÕÒÁ ÓÏÄÅÒÖÉÔ ÒÁ×ÅÎÓÔ×Ï É ÏÔÎÏÛÅÎÉÅ ÐÏÒÑÄËÁ. éÎÔÅÒ-

ÐÒÅÔÁÃÉÑ: ÃÅÌÙÅ ÞÉÓÌÁ. îÅ×ÙÒÁÚÉÍÙÊ ÐÒÅÄÉËÁÔ: x = 0. á×ÔÏÍÏÒÆÉÚÍ:

x 7→ x + 1.

• (Q, =, <, +) óÉÇÎÁÔÕÒÁ ÓÏÄÅÒÖÉÔ ÒÁ×ÅÎÓÔ×Ï, ÏÔÎÏÛÅÎÉÅ ÐÏÒÑÄËÁ É ÏÐÅ-

ÒÁÃÉÀ ÓÌÏÖÅÎÉÑ. éÎÔÅÒÐÒÅÔÁÃÉÑ: ÒÁÃÉÏÎÁÌØÎÙÅ ÞÉÓÌÁ. îÅ×ÙÒÁÚÉÍÙÊ

ÐÒÅÄÉËÁÔ: x = 1. á×ÔÏÍÏÒÆÉÚÍ: x 7→ 2x.

úÁÍÅÔÉÍ, ÞÔÏ ÓÌÏÖÅÎÉÅ ÐÏÚ×ÏÌÑÅÔ ×ÙÒÁÚÉÔØ ÐÒÅÄÉËÁÔ x = 0. ëÒÏÍÅ

ÔÏÇÏ, ÏÔÍÅÔÉÍ, ÞÔÏ ×ÍÅÓÔÏ ÒÁÃÉÏÎÁÌØÎÙÈ ÞÉÓÅÌ ÍÏÖÎÏ ×ÚÑÔØ ÄÅÊÓÔ×É-

ÔÅÌØÎÙÅ (ÎÏ ÎÅ ÃÅÌÙÅ, ÔÁË ËÁË × ÜÔÏÍ ÓÌÕÞÁÅ ÅÄÉÎÉÃÁ ÏÐÉÓÙ×ÁÅÔÓÑ ËÁË

ÎÁÉÍÅÎØÛÅÅ ÞÉÓÌÏ, ÂÏÌØÛÅÅ ÎÕÌÑ).

• (R, =, <, 0, 1) óÉÇÎÁÔÕÒÁ ÓÏÄÅÒÖÉÔ ÒÁ×ÅÎÓÔ×Ï, ÐÏÒÑÄÏË É ËÏÎÓÔÁÎÔÙ 0

É 1. éÎÔÅÒÐÒÅÔÁÃÉÑ: ÄÅÊÓÔ×ÉÔÅÌØÎÙÅ ÞÉÓÌÁ. îÅ×ÙÒÁÚÉÍÙÊ ÐÒÅÄÉËÁÔ:

x = 1/2. (á×ÔÏÍÏÒÆÉÚÍ ÕÐÏÒÑÄÏÞÅÎÎÏÇÏ ÍÎÏÖÅÓÔ×Á R, ÓÏÈÒÁÎÑÀÝÉÊ 0

É 1, ÎÏ ÎÅ 1/2, ÐÏÓÔÒÏÉÔØ ÌÅÇËÏ.)

• (R, =, +, 0, 1) óÉÇÎÁÔÕÒÁ ÓÏÄÅÒÖÉÔ ÒÁ×ÅÎÓÔ×Ï, ÓÌÏÖÅÎÉÅ, ËÏÎÓÔÁÎÔÙ 0

É 1. éÎÔÅÒÐÒÅÔÁÃÉÑ: ÄÅÊÓÔ×ÉÔÅÌØÎÙÅ ÞÉÓÌÁ. ïÄÎÏÍÅÓÔÎÙÊ ÐÒÅÄÉËÁÔ

x = γ ×ÙÒÁÚÉÍ ÄÌÑ ÒÁÃÉÏÎÁÌØÎÙÈ γ É ÎÅ×ÙÒÁÚÉÍ ÄÌÑ ÉÒÒÁÃÉÏÎÁÌØ-

ÎÙÈ γ.

÷ ÓÁÍÏÍ ÄÅÌÅ, ×ÙÒÁÚÉÍÏÓÔØ ÄÌÑ ÒÁÃÉÏÎÁÌØÎÙÈ γ ÏÞÅ×ÉÄÎÁ. îÅ×ÙÒÁ-

ÚÉÍÏÓÔØ ÄÌÑ ÉÒÒÁÃÉÏÎÁÌØÎÙÈ γ ÓÌÅÄÕÅÔ ÉÚ ÔÏÇÏ, ÞÔÏ ÄÌÑ ÌÀÂÙÈ Ä×ÕÈ

ÉÒÒÁÃÉÏÎÁÌØÎÙÈ γ

É γ

ÓÕÝÅÓÔ×ÕÅÔ Á×ÔÏÍÏÒÆÉÚÍ, ÐÅÒÅ×ÏÄÑÝÉÊ γ

× γ

. (÷ ÓÁÍÏÍ ÄÅÌÅ, ÒÁÓÓÍÏÔÒÉÍ R ËÁË ÂÅÓËÏÎÅÞÎÏÍÅÒÎÏÅ ×ÅËÔÏÒÎÏÅ

ÐÒÏÓÔÒÁÎÓÔ×Ï ÎÁÄ Q. ÷ÅËÔÏÒÙ 1, γ

ÌÉÎÅÊÎÏ ÎÅÚÁ×ÉÓÉÍÙ É ÐÏÔÏÍÕ ÉÈ

ÍÏÖÎÏ ÄÏÐÏÌÎÉÔØ ÄÏ ÂÁÚÉÓÁ çÁÍÅÌÑ (ÐÏÄÒÏÂÎÏÓÔÉ ÓÍÏÔÒÉ × ËÎÉÖËÅ ÐÏ

ÔÅÏÒÉÉ ÍÎÏÖÅÓÔ× [1]). óÄÅÌÁÅÍ ÔÏ ÖÅ ÓÁÍÏÅ Ó ×ÅËÔÏÒÁÍÉ 1, γ

. ðÏÌÕÞÁÔ-

ÓÑ ÒÁ×ÎÏÍÏÝÎÙÅ ÂÁÚÉÓÙ, ÐÏÓÌÅ ÞÅÇÏ ÍÙ ÂÅÒ¾Í Q-ÌÉÎÅÊÎÙÊ ÏÐÅÒÁÔÏÒ,

ÐÅÒÅ×ÏÄÑÝÉÊ 1 × 1 É γ

× γ

• (C, =, +, ×, 0, 1) ÷ ÓÉÇÎÁÔÕÒÕ ×ÈÏÄÑÔ ÐÒÅÄÉËÁÔ ÒÁ×ÅÎÓÔ×Á, ÏÐÅÒÁÃÉÉ

ÓÌÏÖÅÎÉÑ É ÕÍÎÏÖÅÎÉÑ, Á ÔÁËÖÅ ËÏÎÓÔÁÎÔÙ 0 É 1. éÎÔÅÒÐÒÅÔÁÃÉÑ: ËÏÍ-

ÐÌÅËÓÎÙÅ ÞÉÓÌÁ. ðÒÅÄÉËÁÔ x = γ, ÇÄÅ γ ¡ ÎÅËÏÔÏÒÏÅ ËÏÍÐÌÅËÓÎÏÅ ÞÉ-

ÓÌÏ, ×ÙÒÁÚÉÍ ÄÌÑ ÒÁÃÉÏÎÁÌØÎÙÈ γ É ÎÅ×ÙÒÁÚÉÍ ÄÌÑ ÉÒÒÁÃÉÏÎÁÌØÎÙÈ

γ.

÷ ÓÁÍÏÍ ÄÅÌÅ, ÅÓÌÉ γ ÉÒÒÁÃÉÏÎÁÌØÎÏ, ÔÏ ÏÎÏ ÍÏÖÅÔ ÂÙÔØ ÁÌÇÅÂÒÁ-

§5. îÅ×ÙÒÁÚÉÍÙÅ ÐÒÅÄÉËÁÔÙ: Á×ÔÏÍÏÒÆÉÚÍÙ 115

ÉÞÅÓËÉÍ ÉÌÉ ÔÒÁÎÓÃÅÎÄÅÎÔÎÙÍ. ÷ ÐÅÒ×ÏÍ ÓÌÕÞÁÅ ÒÁÓÓÍÏÔÒÉÍ ÍÎÏÇÏ-

ÞÌÅÎ ÉÚ Q[x] ÍÉÎÉÍÁÌØÎÏÊ ÓÔÅÐÅÎÉ, ÏÂÒÁÝÁÀÝÉÊÓÑ × 0 × ÔÏÞËÅ γ; ÐÏ

ÐÒÅÄÐÏÌÏÖÅÎÉÀ ÏÎ ÉÍÅÅÔ ÓÔÅÐÅÎØ ÂÏÌØÛÅ 1 É ÐÏÔÏÍÕ ÉÍÅÅÔ ÄÒÕÇÏÊ ËÏ-

ÒÅÎØ γ

. ÷ ÁÌÇÅÂÒÅ ÄÏËÁÚÙ×ÁÅÔÓÑ, ÞÔÏ ÓÕÝÅÓÔ×ÕÅÔ Á×ÔÏÍÏÒÆÉÚÍ C ÎÁÄ

Q, ÐÅÒÅ×ÏÄÑÝÉÊ γ × γ

÷ ÓÌÕÞÁÅ ÔÒÁÎÓÃÅÎÄÅÎÔÎÏÇÏ γ ÍÙ ÉÓÐÏÌØÚÕÅÍ ÔÁËÏÊ ÆÁËÔ: ÄÌÑ ÌÀ-

ÂÙÈ ÔÒÁÎÓÃÅÎÄÅÎÔÎÙÈ γ

, γ

∈ C ÓÕÝÅÓÔ×ÕÅÔ Á×ÔÏÍÏÒÆÉÚÍ ÐÏÌÑ C ÎÁÄ

Q, ËÏÔÏÒÙÊ ÐÅÒÅ×ÏÄÉÔ γ

× γ

ïÔÍÅÔÉÍ, ÞÔÏ ÄÌÑ ÐÏÌÑ R ×ÍÅÓÔÏ C ÔÁËÏÅ ÒÁÓÓÕÖÄÅÎÉÅ ÎÅ ÐÒÏÈÏÄÉÔ,

ÔÁË ËÁË ÜÔÏ ÐÏÌÅ ÎÅ ÉÍÅÅÔ ÎÅÔÒÉ×ÉÁÌØÎÙÈ Á×ÔÏÍÏÒÆÉÚÍÏ×. (ïÔÎÏÛÅ-

ÎÉÅ ÐÏÒÑÄËÁ ×ÙÒÁÚÉÍÏ: ÐÏÌÏÖÉÔÅÌØÎÙÅ ÞÉÓÌÁ ÓÕÔØ Ë×ÁÄÒÁÔÙ, ÐÏÜÔÏÍÕ

ÌÀÂÏÊ Á×ÔÏÍÏÒÆÉÚÍ ÓÏÈÒÁÎÑÅÔ ÐÏÒÑÄÏË. ðÏÓËÏÌØËÕ Á×ÔÏÍÏÒÆÉÚÍ ÏÓÔÁ-

×ÌÑÅÔ ÎÁ ÍÅÓÔÅ ×ÓÅ ÒÁÃÉÏÎÁÌØÎÙÅ ÞÉÓÌÁ, ÏÎ ÄÏÌÖÅÎ ÂÙÔØ ÔÏÖÄÅÓÔ×ÅÎ-

ÎÙÍ.)

(÷ ÜÔÏÍ ÓÌÕÞÁÅ ÐÒÅÄÉËÁÔ x = γ ×ÙÒÁÚÉÍ ÔÏÇÄÁ É ÔÏÌØËÏ ÔÏÇÄÁ,

ËÏÇÄÁ γ ¡ ÁÌÇÅÂÒÁÉÞÅÓËÏÅ ÞÉÓÌÏ.)

úÁÄÁÞÁ 148. ðÏËÁÖÉÔÅ, ÞÔÏ ÐÒÅÄÉËÁÔ y = x + 1 ÎÅ×ÙÒÁÚÉÍ × ÉÎÔÅÒ-

ÐÒÅÔÁÃÉÉ (Z, =, f), ÇÄÅ f ¡ ÏÄÎÏÍÅÓÔÎÁÑ ÆÕÎËÃÉÑ x 7→ (x + 2).

úÁÄÁÞÁ 149. ðÏËÁÖÉÔÅ, ÞÔÏ ÐÒÅÄÉËÁÔ x = 2 ÎÅ×ÙÒÁÚÉÍ × ÍÎÏÖÅÓÔ×Å

ÃÅÌÙÈ ÐÏÌÏÖÉÔÅÌØÎÙÈ ÞÉÓÅÌ Ó ÐÒÅÄÉËÁÔÁÍÉ ÒÁ×ÅÎÓÔ×Á É ¥x ÄÅÌÉÔ y¥.

çìá÷á VI

éÓÞÉÓÌÅÎÉÅ ÐÒÅÄÉËÁÔÏ×

§1. ïÂÝÅÚÎÁÞÉÍÙÅ ÆÏÒÍÕÌÙ

éÓÞÉÓÌÅÎÉÅ ×ÙÓËÁÚÙ×ÁÎÉÊ (ÇÌÁ×Á IV) ÐÏÚ×ÏÌÑÌÏ ×Ù×ÏÄÉÔØ ×ÓÅ ÔÁ×ÔÏÌÏ-

ÇÉÉ ÉÚ ÎÅËÏÔÏÒÏÇÏ ÎÁÂÏÒÁ ÂÁÚÉÓÎÙÈ ÔÁ×ÔÏÌÏÇÉÊ (ÎÁÚ×ÁÎÎÙÈ ÁËÓÉÏÍÁÍÉ) Ó

ÐÏÍÏÝØÀ ÎÅËÏÔÏÒÙÈ ÐÒÁ×ÉÌ ×Ù×ÏÄÁ (ÎÁ ÓÁÍÏÍ ÄÅÌÅ ÅÄÉÎÓÔ×ÅÎÎÏÇÏ ÐÒÁ×ÉÌÁ

modus ponens). óÅÊÞÁÓ ÍÙ ÈÏÔÉÍ ÒÅÛÉÔØ ÁÎÁÌÏÇÉÞÎÕÀ ÚÁÄÁÞÕ ÄÌÑ ÆÏÒ-

ÍÕÌ ÐÅÒ×ÏÇÏ ÐÏÒÑÄËÁ. óÏÏÔ×ÅÔÓÔ×ÕÀÝÅÅ ÉÓÞÉÓÌÅÎÉÅ ÎÁÚÙ×ÁÅÔÓÑ ÉÓÞÉÓÌÅÎÉ-

ÅÍ ÐÒÅÄÉËÁÔÏ×.

ðÕÓÔØ ÆÉËÓÉÒÏ×ÁÎÁ ÎÅËÏÔÏÒÁÑ ÓÉÇÎÁÔÕÒÁ σ. æÏÒÍÕÌÁ ϕ ÜÔÏÊ ÓÉÇÎÁÔÕÒÙ

(×ÏÚÍÏÖÎÏ, Ó ÐÁÒÁÍÅÔÒÁÍÉ) ÎÁÚÙ×ÁÅÔÓÑ ÏÂÝÅÚÎÁÞÉÍÏÊ, ÅÓÌÉ ÏÎÁ ÉÓÔÉÎÎÁ ×

ÌÀÂÏÊ ÉÎÔÅÒÐÒÅÔÁÃÉÉ ÓÉÇÎÁÔÕÒÙ σ ÎÁ ÌÀÂÏÊ ÏÃÅÎËÅ.

ïÂÝÅÚÎÁÞÉÍÙÅ ÆÏÒÍÕÌÙ × ÌÏÇÉËÅ ÐÒÅÄÉËÁÔÏ× ÉÇÒÁÀÔ ÔÕ ÖÅ ÒÏÌØ, ÞÔÏ

ÔÁ×ÔÏÌÏÇÉÉ × ÌÏÇÉËÅ ×ÙÓËÁÚÙ×ÁÎÉÊ. íÅÖÄÕ ÎÉÍÉ ÅÓÔØ É ÆÏÒÍÁÌØÎÁÑ Ó×ÑÚØ:

ÅÓÌÉ ×ÚÑÔØ ÌÀÂÕÀ ÔÁ×ÔÏÌÏÇÉÀ É ×ÍÅÓÔÏ ×ÈÏÄÑÝÉÈ × ÎÅ¾ ÐÒÏÐÏÚÉÃÉÏÎÁÌØÎÙÈ

ÐÅÒÅÍÅÎÎÙÈ ÐÏÄÓÔÁ×ÉÔØ ÐÒÏÉÚ×ÏÌØÎÙÅ ÆÏÒÍÕÌÙ ÓÉÇÎÁÔÕÒÙ σ, ÐÏÌÕÞÉÔÓÑ ÏÂ-

ÝÅÚÎÁÞÉÍÁÑ ÆÏÒÍÕÌÁ. ÷ ÓÁÍÏÍ ÄÅÌÅ, ÐÕÓÔØ ÅÓÔØ ÎÅËÏÔÏÒÁÑ ÉÎÔÅÒÐÒÅÔÁÃÉÑ

ÓÉÇÎÁÔÕÒÙ σ É ÎÅËÏÔÏÒÁÑ ÏÃÅÎËÁ (ÔÏ ÅÓÔØ ÆÉËÓÉÒÏ×ÁÎÙ ÚÎÁÞÅÎÉÑ ÉÎÄÉ×ÉÄ-

ÎÙÈ ÐÅÒÅÍÅÎÎÙÈ). ôÏÇÄÁ ËÁÖÄÁÑ ÉÚ ÐÏÄÓÔÁ×ÌÅÎÎÙÈ ÆÏÒÍÕÌ ÓÔÁÎÅÔ ÉÓÔÉÎÎÏÊ

ÉÌÉ ÌÏÖÎÏÊ, Á ÚÎÁÞÅÎÉÅ ×ÓÅÊ ÆÏÒÍÕÌÙ ÏÐÒÅÄÅÌÑÅÔÓÑ Ó ÐÏÍÏÝØÀ ÔÁÂÌÉÃ ÉÓ-

ÔÉÎÎÏÓÔÉ ÄÌÑ ÌÏÇÉÞÅÓËÉÈ Ó×ÑÚÏË, ÔÏ ÅÓÔØ ÐÏ ÔÅÍ ÖÅ ÐÒÁ×ÉÌÁÍ, ÞÔÏ × ÌÏÇÉËÅ

×ÙÓËÁÚÙ×ÁÎÉÊ.

ëÏÎÅÞÎÏ, ÂÙ×ÁÀÔ É ÄÒÕÇÉÅ ÏÂÝÅÚÎÁÞÉÍÙÅ ÆÏÒÍÕÌÙ, ÎÅ Ñ×ÌÑÀÝÉÅÓÑ ÞÁÓÔ-

ÎÙÍ ÓÌÕÞÁÑÍÉ ÐÒÏÐÏÚÉÃÉÏÎÁÌØÎÙÈ ÔÁ×ÔÏÌÏÇÉÊ. îÁÐÒÉÍÅÒ, ÆÏÒÍÕÌÁ

∀x A(x) → ∃yA(y)

ÏÂÝÅÚÎÁÞÉÍÁ (ÚÄÅÓØ ÓÕÝÅÓÔ×ÅÎÎÏ, ÞÔÏ ÎÏÓÉÔÅÌØ ÌÀÂÏÊ ÉÎÔÅÒÐÒÅÔÁÃÉÉ ÎÅ-

ÐÕÓÔ). äÒÕÇÉÅ ÐÒÉÍÅÒÙ ÏÂÝÅÚÎÁÞÉÍÙÈ ÆÏÒÍÕÌ (×Ï ×ÔÏÒÏÍ ÓÌÕÞÁÅ ϕ ¡ ÐÒÏ-

ÉÚ×ÏÌØÎÁÑ ÆÏÒÍÕÌÁ):

∃y ∀x B(x, y) → ∀x ∃y B(x, y), ¬∀x ¬ϕ → ∃x ϕ.

úÁÄÁÞÁ 150. âÕÄÅÔ ÌÉ ÏÂÝÅÚÎÁÞÉÍÁ ÆÏÒÍÕÌÁ

( Á) ∀x ∃y B(x, y) → ∃y ∀x B(x, y);

( Â) ¬∀x ∃y B(x, y) → ∃x ∀y ¬B(x, y)?

116

§1. ïÂÝÅÚÎÁÞÉÍÙÅ ÆÏÒÍÕÌÙ 117

íÎÏÇÉÅ ×ÏÐÒÏÓÙ ÍÏÖÎÏ ÓÆÏÒÍÕÌÉÒÏ×ÁÔØ ËÁË ×ÏÐÒÏÓÙ ÏÂ ÏÂÝÅÚÎÁÞÉÍÏÓÔÉ

ÎÅËÏÔÏÒÙÈ ÆÏÒÍÕÌ. îÁÐÒÉÍÅÒ, ÍÏÖÎÏ ÚÁÐÉÓÁÔØ Ó×ÏÊÓÔ×Á ÒÅÆÌÅËÓÉ×ÎÏÓÔÉ,

ÔÒÁÎÚÉÔÉ×ÎÏÓÔÉ É ÁÎÔÉÓÉÍÍÅÔÒÉÞÎÏÓÔÉ × ×ÉÄÅ ÆÏÒÍÕÌ R, T É A ÓÉÇÎÁÔÕÒÙ

(=, <) É ÚÁÔÅÍ ÎÁÐÉÓÁÔØ ÆÏÒÍÕÌÕ

R ∧ T ∧ A → ∃x ∀y ((y < x) ∨ (y = x)).

ïÂÝÅÚÎÁÞÉÍÏÓÔØ ÜÔÏÊ ÆÏÒÍÕÌÙ ÏÚÎÁÞÁÌÁ ÂÙ, ÞÔÏ ÌÀÂÏÅ ÌÉÎÅÊÎÏ ÕÐÏÒÑÄÏ-

ÞÅÎÎÏÅ ÍÎÏÖÅÓÔ×Ï ÉÍÅÅÔ ÎÁÉÂÏÌØÛÉÊ ÜÌÅÍÅÎÔ, ÔÁË ÞÔÏ ÏÎÁ ÎÅ ÏÂÝÅÚÎÁÞÉÍÁ.

úÁÄÁÞÁ 151. îÁÐÉÛÉÔÅ ÆÏÒÍÕÌÙ R, T, A É ÐÒÏ×ÅÒØÔÅ, ÞÔÏ ÐÒÉ×ÅÄ¾Î-

ÎÁÑ ÎÁÍÉ ÆÏÒÍÕÌÁ ÎÅ ÏÂÝÅÚÎÁÞÉÍÁ, ÈÏÔÑ ÉÓÔÉÎÎÁ ×Ï ×ÓÅÈ ËÏÎÅÞÎÙÈ ÉÎ-

ÔÅÒÐÒÅÔÁÃÉÑÈ.

úÁÄÁÞÁ 152. éÚ×ÅÓÔÎÏ, ÞÔÏ ÆÏÒÍÕÌÁ ÉÓÔÉÎÎÁ ×Ï ×ÓÅÈ ËÏÎÅÞÎÙÈ É

ÓÞ¾ÔÎÙÈ ÉÎÔÅÒÐÒÅÔÁÃÉÑÈ. íÏÖÎÏ ÌÉ ÉÚ ÜÔÏÇÏ ÚÁËÌÀÞÉÔØ, ÞÔÏ ÏÎÁ ÏÂ-

ÝÅÚÎÁÞÉÍÁ? (õËÁÚÁÎÉÅ: ×ÏÓÐÏÌØÚÕÊÔÅÓØ ÔÅÏÒÅÍÏÊ ìÅ×ÅÎÇÅÊÍÁ  óËÏÌÅÍÁ

ÏÂ ÜÌÅÍÅÎÔÁÒÎÏÊ ÐÏÄÍÏÄÅÌÉ.)

ä×Å ÆÏÒÍÕÌÙ ϕ É ψ (Ó ÐÁÒÁÍÅÔÒÁÍÉ ÉÌÉ ÂÅÚ) ÎÁÚÙ×ÁÀÔÓÑ ÜË×É×ÁÌÅÎÔ-

ÎÙÍÉ, ÅÓÌÉ × ÌÀÂÏÊ ÉÎÔÅÒÐÒÅÔÁÃÉÉ É ÎÁ ÌÀÂÏÊ ÏÃÅÎËÅ, ÎÁ ËÏÔÏÒÏÊ ÉÓÔÉÎÎÁ

ÏÄÎÁ ÉÚ ÎÉÈ, ÉÓÔÉÎÎÁ É ÄÒÕÇÁÑ. üÔÏ ÏÐÒÅÄÅÌÅÎÉÅ ÒÁ×ÎÏÓÉÌØÎÏ ÔÁËÏÍÕ: ÆÏÒ-

ÍÕÌÁ ϕ ↔ ψ ÏÂÝÅÚÎÁÞÉÍÁ. úÄÅÓØ, ÎÁÐÏÍÎÉÍ, ϕ ↔ ψ ÅÓÔØ ÓÏËÒÁÝÅÎÉÅ ÄÌÑ

((ϕ → ψ) ∧ (ψ → ϕ)).

ïÂÝÅÚÎÁÞÉÍÏÓÔØ ÌÀÂÏÊ ÆÏÒÍÕÌÙ ϕ ÏÞÅ×ÉÄÎÏ ÒÁ×ÎÏÓÉÌØÎÁ ÏÂÝÅÚÎÁÞÉÍÏ-

ÓÔÉ Å¾ ÚÁÍÙËÁÎÉÑ ¡ ÆÏÒÍÕÌÙ, ËÏÔÏÒÁÑ ÐÏÌÕÞÉÔÓÑ, ÅÓÌÉ ÓÌÅ×Á Ë ϕ ÐÒÉÐÉÓÁÔØ

Ë×ÁÎÔÏÒÙ ×ÓÅÏÂÝÎÏÓÔÉ ÐÏ ×ÓÅÍ ÐÁÒÁÍÅÔÒÁÍ.

ä×ÏÊÓÔ×ÅÎÎÏÅ Ë ÏÂÝÅÚÎÁÞÉÍÏÓÔÉ ÐÏÎÑÔÉÅ ¡ ×ÙÐÏÌÎÉÍÏÓÔØ. æÏÒÍÕÌÁ ÎÁ-

ÚÙ×ÁÅÔÓÑ ×ÙÐÏÌÎÉÍÏÊ, ÅÓÌÉ ÏÎÁ ÉÓÔÉÎÎÁ × ÎÅËÏÔÏÒÏÊ ÉÎÔÅÒÐÒÅÔÁÃÉÉ ÎÁ ÎÅ-

ËÏÔÏÒÏÊ ÏÃÅÎËÅ. ïÞÅ×ÉÄÎÏ, ÆÏÒÍÕÌÁ ϕ ÏÂÝÅÚÎÁÞÉÍÁ ÔÏÇÄÁ É ÔÏÌØËÏ ÔÏÇÄÁ,

ËÏÇÄÁ ÆÏÒÍÕÌÁ ¬ϕ ÎÅ Ñ×ÌÑÅÔÓÑ ×ÙÐÏÌÎÉÍÏÊ.

úÁÄÁÞÁ 153. úÁËÏÎÞÉÔÅ ÕÔ×ÅÒÖÄÅÎÉÅ: ×ÙÐÏÌÎÉÍÏÓÔØ ÆÏÒÍÕÌÙ Ó ÐÁÒÁ-

ÍÅÔÒÁÍÉ ÒÁ×ÎÏÓÉÌØÎÁ ×ÙÐÏÌÎÉÍÏÓÔÉ ÚÁÍËÎÕÔÏÊ ÆÏÒÍÕÌÙ, ËÏÔÏÒÁÑ ÐÏÌÕ-

ÞÉÔÓÑ, ÅÓÌÉ . . .

þÔÏÂÙ ÐÒÏ×ÅÒÉÔØ, Ñ×ÌÑÅÔÓÑ ÌÉ ÆÏÒÍÕÌÁ ÔÁ×ÔÏÌÏÇÉÅÊ, ÄÏÓÔÁÔÏÞÎÏ ÐÏÄÓÔÁ-

×ÉÔØ × ÎÅ¾ ×ÓÅ ×ÏÚÍÏÖÎÙÅ ÎÁÂÏÒÙ ÚÎÁÞÅÎÉÊ ÐÅÒÅÍÅÎÎÙÈ. èÏÔÑ ÜÔÏÔ ÐÒÏÃÅÓÓ

ÍÏÖÅÔ ÂÙÔØ ÎÁ ÐÒÁËÔÉËÅ ÎÅ×ÙÐÏÌÎÉÍ (ÎÁÂÏÒÏ× ÓÌÉÛËÏÍ ÍÎÏÇÏ), ÔÅÏÒÅÔÉ-

ÞÅÓËÉ ÍÙ ÉÍÅÅÍ ÐÒÏÓÔÏÊ ÁÌÇÏÒÉÔÍ ÐÒÏ×ÅÒËÉ, Ñ×ÌÑÅÔÓÑ ÌÉ ÆÏÒÍÕÌÁ ÔÁ×ÔÏ-

ÌÏÇÉÅÊ. äÌÑ ÏÂÝÅÚÎÁÞÉÍÙÈ ÆÏÒÍÕÌ × ÏÂÝÅÍ ÓÌÕÞÁÅ ÔÁËÏÇÏ ÁÌÇÏÒÉÔÍÁ ÎÅ

ÓÕÝÅÓÔ×ÕÅÔ (ÔÅÏÒÅÍÁ þ¾ÒÞÁ; Å¾ ÄÏËÁÚÁÔÅÌØÓÔ×Ï ÍÏÖÎÏ ÐÒÏÞÅÓÔØ × [3]); ÏÎ

ÅÓÔØ ÔÏÌØËÏ ÄÌÑ ÏÞÅÎØ ÏÇÒÁÎÉÞÅÎÎÙÈ ËÌÁÓÓÏ× ÆÏÒÍÕÌ. îÁÐÒÉÍÅÒ, ÅÓÌÉ ÓÉÇ-

ÎÁÔÕÒÁ ÓÏÄÅÒÖÉÔ ÔÏÌØËÏ ÎÕÌØÍÅÓÔÎÙÅ ÐÒÅÄÉËÁÔÎÙÅ ÓÉÍ×ÏÌÙ, ÔÏ ÚÁÄÁÞÁ ÐÏ

118 çÌÁ×Á VI. éÓÞÉÓÌÅÎÉÅ ÐÒÅÄÉËÁÔÏ×

ÓÕÝÅÓÔ×Õ Ó×ÏÄÉÔÓÑ Ë ÐÒÏ×ÅÒËÅ ÔÁ×ÔÏÌÏÇÉÞÎÏÓÔÉ (× ÜÔÏÍ ÓÌÕÞÁÅ Ë×ÁÎÔÏÒÙ

ÆÉËÔÉ×ÎÙ). þÕÔØ ÂÏÌÅÅ ÓÌÏÖÅÎ ÓÌÕÞÁÊ Ó ÏÄÎÏÍÅÓÔÎÙÍÉ ÐÒÅÄÉËÁÔÁÍÉ.

úÁÄÁÞÁ 154. ðÕÓÔØ ÓÉÇÎÁÔÕÒÁ σ ÓÏÄÅÒÖÉÔ ÔÏÌØËÏ ÏÄÎÏÍÅÓÔÎÙÅ ÐÒÅ-

ÄÉËÁÔÙ. äÏËÁÖÉÔÅ, ÞÔÏ ×ÓÑËÁÑ ×ÙÐÏÌÎÉÍÁÑ ÆÏÒÍÕÌÁ ÜÔÏÊ ÓÉÇÎÁÔÕÒÙ,

ÓÏÄÅÒÖÁÝÁÑ n ÒÁÚÌÉÞÎÙÈ ÐÒÅÄÉËÁÔÏ×, ×ÙÐÏÌÎÉÍÁ × ÎÅËÏÔÏÒÏÊ ËÏÎÅÞÎÏÊ

ÉÎÔÅÒÐÒÅÔÁÃÉÉ, ÓÏÄÅÒÖÁÝÅÊ ÎÅ ÂÏÌÅÅ 2

ÜÌÅÍÅÎÔÏ×. ëÁË ÉÓÐÏÌØÚÏ×ÁÔØ

ÜÔÏÔ ÆÁËÔ ÄÌÑ ÁÌÇÏÒÉÔÍÉÞÅÓËÏÊ ÐÒÏ×ÅÒËÉ ×ÙÐÏÌÎÉÍÏÓÔÉ ÆÏÒÍÕÌ ÔÁËÏÊ

ÓÉÇÎÁÔÕÒÙ?

§2. áËÓÉÏÍÙ É ÐÒÁ×ÉÌÁ ×Ù×ÏÄÁ

÷ÏÚ×ÒÁÔÉÍÓÑ Ë ÎÁÛÅÊ ÚÁÄÁÞÅ: ËÁËÉÅ ÁËÓÉÏÍÙ É ÐÒÁ×ÉÌÁ ×Ù×ÏÄÁ ÎÁÍ ÎÕÖ-

ÎÙ, ÞÔÏÂÙ ÐÏÌÕÞÉÔØ ×ÓÅ ÏÂÝÅÚÎÁÞÉÍÙÅ ÆÏÒÍÕÌÙ ÎÅËÏÔÏÒÏÊ ÓÉÇÎÁÔÕÒÙ σ?

åÓÔÅÓÔ×ÅÎÎÏ ÉÓÐÏÌØÚÏ×ÁÔØ ×ÓÅ ÓÈÅÍÙ ÁËÓÉÏÍ (1)  (11) ÉÓÞÉÓÌÅÎÉÑ ×ÙÓËÁÚÙ-

×ÁÎÉÊ (ÒÁÚÄÅÌ 1), ÎÏ ÔÏÌØËÏ ×ÍÅÓÔÏ ÂÕË× A, B É C ÔÅÐÅÒØ ÍÏÖÎÏ ÐÏÄÓÔÁ×ÌÑÔØ

ÐÒÏÉÚ×ÏÌØÎÙÅ ÆÏÒÍÕÌÙ ÓÉÇÎÁÔÕÒÙ σ. ôÅÏÒÅÍÁ Ï ÐÏÌÎÏÔÅ ÉÓÞÉÓÌÅÎÉÑ ×ÙÓËÁ-

ÚÙ×ÁÎÉÊ ÇÁÒÁÎÔÉÒÕÅÔ, ÞÔÏ ÐÏÓÌÅ ÜÔÏÇÏ ÍÙ ÓÍÏÖÅÍ ×Ù×ÅÓÔÉ ÌÀÂÏÊ ÞÁÓÔÎÙÊ

ÓÌÕÞÁÊ ÌÀÂÏÊ ÐÒÏÐÏÚÉÃÉÏÎÁÌØÎÏÊ ÔÁ×ÔÏÌÏÇÉÉ (ÔÏ ÅÓÔØ ÌÀÂÕÀ ÆÏÒÍÕÌÕ, ËÏ-

ÔÏÒÁÑ ÐÏÌÕÞÁÅÔÓÑ ÉÚ ÐÒÏÐÏÚÉÃÉÏÎÁÌØÎÏÊ ÔÁ×ÔÏÌÏÇÉÉ ÚÁÍÅÎÏÊ ÐÒÏÐÏÚÉÃÉÏ-

ÎÁÌØÎÙÈ ÐÅÒÅÍÅÎÎÙÈ ÎÁ ÆÏÒÍÕÌÙ ÓÉÇÎÁÔÕÒÙ σ). ÷ ÓÁÍÏÍ ÄÅÌÅ, ×ÏÚØÍ¾Í

×Ù×ÏÄ ÜÔÏÊ ÔÁ×ÔÏÌÏÇÉÉ × ÉÓÞÉÓÌÅÎÉÉ ×ÙÓËÁÚÙ×ÁÎÉÊ (ËÏÔÏÒÏÅ, ËÁË ÍÙ ÚÎÁ-

ÅÍ, ÐÏÌÎÏ) É ×ÙÐÏÌÎÉÍ ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÕÀ ÚÁÍÅÎÕ ×Ï ×ÓÅÈ ÆÏÒÍÕÌÁÈ ÜÔÏÇÏ

×Ù×ÏÄÁ.

ðÏÞÔÉ ÓÔÏÌØ ÖÅ ÐÒÏÓÔÏ ÐÏÎÑÔØ, ÞÔÏ ÎÉÞÅÇÏ ÄÒÕÇÏÇÏ ÔÁËÉÅ ÁËÓÉÏÍÙ ÎÅ

ÄÁÄÕÔ: ÅÓÌÉ ÐÏÌØÚÏ×ÁÔØÓÑ ÌÉÛØ ÓÈÅÍÁÍÉ ÁËÓÉÏÍ (1)  (11), ÒÁÚÒÅÛÁÑ ÂÒÁÔØ ×

ÎÉÈ × ËÁÞÅÓÔ×Å A, B, C ÐÒÏÉÚ×ÏÌØÎÙÅ ÆÏÒÍÕÌÙ ÓÉÇÎÁÔÕÒÙ σ, Á × ËÁÞÅÓÔ×Å

ÐÒÁ×ÉÌÁ ×Ù×ÏÄÁ ÉÓÐÏÌØÚÏ×ÁÔØ modus ponens, ÔÏ ×ÓÅ ×Ù×ÏÄÉÍÙÅ ÆÏÒÍÕÌÙ

ÂÕÄÕÔ ÞÁÓÔÎÙÍÉ ÓÌÕÞÁÑÍÉ ÐÒÏÐÏÚÉÃÉÏÎÁÌØÎÙÈ ÔÁ×ÔÏÌÏÇÉÊ. ÷ ÓÁÍÏÍ ÄÅÌÅ,

ÅÓÌÉ ËÁËÁÑ-ÔÏ ÐÏÄÆÏÒÍÕÌÁ ÎÁÞÉÎÁÅÔÓÑ Ó Ë×ÁÎÔÏÒÁ, ÔÏ × ×Ù×ÏÄÅ ÏÎÁ ÍÏÖÅÔ

×ÓÔÒÅÞÁÔØÓÑ ÔÏÌØËÏ ËÁË ÅÄÉÎÏÅ ÃÅÌÏÅ, ÔÏ ÅÓÔØ ÔÁËÁÑ ÐÏÄÆÏÒÍÕÌÁ ×ÅÄ¾Ô ÓÅÂÑ

ËÁË ÐÒÏÐÏÚÉÃÉÏÎÁÌØÎÁÑ ÐÅÒÅÍÅÎÎÁÑ.

úÁÄÁÞÁ 155. ðÒÏ×ÅÄÉÔÅ ÜÔÏ ÒÁÓÓÕÖÄÅÎÉÅ ÁËËÕÒÁÔÎÏ.

üÔÏ ÎÁÂÌÀÄÅÎÉÅ ÓËÏÒÅÅ ÔÒÉ×ÉÁÌØÎÏ, ÞÅÍ ÕÄÉ×ÉÔÅÌØÎÏ ¡ ÅÓÌÉ ÓÒÅÄÉ ÎÁ-

ÛÉÈ ÁËÓÉÏÍ É ÐÒÁ×ÉÌ ×Ù×ÏÄÁ ÎÅÔ ÎÉÞÅÇÏ Ï ÓÍÙÓÌÅ Ë×ÁÎÔÏÒÏ×, ÔÏ ÆÏÒÍÕÌÙ,

ÎÁÞÉÎÁÀÝÉÅÓÑ Ó Ë×ÁÎÔÏÒÏ×, ÂÕÄÕÔ ×ÅÓÔÉ ÓÅÂÑ ËÁË ÎÅÄÅÌÉÍÙÅ ÂÌÏËÉ. ôÁËÉÍ

ÏÂÒÁÚÏÍ, ÎÁÍ ÎÕÖÎÙ ÁËÓÉÏÍÙ É ÐÒÁ×ÉÌÁ ×Ù×ÏÄÁ, ÏÔÒÁÖÁÀÝÉÅ ÉÎÔÕÉÔÉ×ÎÙÊ

ÓÍÙÓÌ Ë×ÁÎÔÏÒÏ×.

÷ÓÐÏÍÎÉÍ, ËÁË ×ÙÇÌÑÄÅÌÉ ÁËÓÉÏÍÙ ÉÓÞÉÓÌÅÎÉÑ ×ÙÓËÁÚÙ×ÁÎÉÊ. õ ÎÁÓ ÂÙ-

ÌÏ Ä×Á ÔÉÐÁ ÁËÓÉÏÍ ÄÌÑ ËÏÎßÀÎËÃÉÉ É ÄÉÚßÀÎËÃÉÉ: ÏÄÎÉ ÇÏ×ÏÒÉÌÉ, ÞÔÏ ÉÚ

§2. áËÓÉÏÍÙ É ÐÒÁ×ÉÌÁ ×Ù×ÏÄÁ 119

ÎÉÈ ÓÌÅÄÕÅÔ (ÎÁÐÒÉÍÅÒ, ÉÚ A ∧ B ÓÌÅÄÏ×ÁÌÏ B), Á ÄÒÕÇÉÅ ¡ ËÁË ÉÈ ÍÏÖ-

ÎÏ ÄÏËÁÚÁÔØ (ÎÁÐÒÉÍÅÒ, ÁËÓÉÏÍÁ (A → (B → (A ∧ B))) ÇÏ×ÏÒÉÌÁ, ÞÔÏ ÄÌÑ

ÄÏËÁÚÁÔÅÌØÓÔ×Á (A ∧ B) ÎÁÄÏ ÄÏËÁÚÁÔØ A É B). ë×ÁÎÔÏÒÙ ×ÓÅÏÂÝÎÏÓÔÉ É ÓÕ-

ÝÅÓÔ×Ï×ÁÎÉÑ × ÎÅËÏÔÏÒÏÍ ÓÍÙÓÌÅ ÁÎÁÌÏÇÉÞÎÙ ËÏÎßÀÎËÃÉÉ É ÄÉÚßÀÎËÃÉÉ,

É ÁËÓÉÏÍÙ ÄÌÑ ÎÉÈ ÔÏÖÅ ÂÕÄÕÔ ÐÏÈÏÖÉÍÉ. îÁÐÒÉÍÅÒ, ÓÒÅÄÉ ÁËÓÉÏÍ ÂÕÄÅÔ

ÆÏÒÍÕÌÁ

∀x A(x) → A(t),

ÇÄÅ A ¡ ÏÄÎÏÍÅÓÔÎÙÊ ÐÒÅÄÉËÁÔÎÙÊ ÓÉÍ×ÏÌ ÎÁÛÅÊ ÓÉÇÎÁÔÕÒÙ, Á t ¡ ËÏÎ-

ÓÔÁÎÔÁ, ÐÅÒÅÍÅÎÎÁÑ ÉÌÉ ×ÏÏÂÝÅ ÌÀÂÏÊ ÔÅÒÍ. (åÓÌÉ A ×ÅÒÎÏ ÄÌÑ ×ÓÅÈ x, ÔÏ

ÏÎÏ ÄÏÌÖÎÏ ÂÙÔØ ×ÅÒÎÏ É ÄÌÑ ÎÁÛÅÇÏ ËÏÎËÒÅÔÎÏÇÏ t. íÏÖÎÏ ÓËÁÚÁÔØ É ÔÁË:

ÉÚ ¥ÂÅÓËÏÎÅÞÎÏÊ ËÏÎßÀÎËÃÉÉ¥ ×ÓÅÈ A(x) ×ÙÔÅËÁÅÔ ÏÄÉÎ ÉÚ Å¾ ÞÌÅÎÏ×.)

ëÏÎÅÞÎÏ, ÔÁËÕÀ ÁËÓÉÏÍÕ ÎÁÄÏ ÉÍÅÔØ ÎÅ ÔÏÌØËÏ ÄÌÑ ÏÄÎÏÍÅÓÔÎÏÇÏ ÐÒÅÄÉ-

ËÁÔÎÏÇÏ ÓÉÍ×ÏÌÁ A, ÎÏ ÄÌÑ ÌÀÂÏÊ ÆÏÒÍÕÌÙ ϕ, ÌÀÂÏÊ ÐÅÒÅÍÅÎÎÏÊ ξ É ÌÀÂÏÇÏ

ÔÅÒÍÁ t. åÓÔÅÓÔ×ÅÎÎÏ ÓËÁÚÁÔØ, ÞÔÏ ÅÓÌÉ ϕ ¡ ÌÀÂÁÑ ÆÏÒÍÕÌÁ, Á t ¡ ÌÀÂÏÊ

ÔÅÒÍ, ÔÏ ÆÏÒÍÕÌÁ

∀ξ ϕ → ϕ(t/ξ),

ÇÄÅ ϕ(t/ξ) ÏÂÏÚÎÁÞÁÅÔ ÒÅÚÕÌØÔÁÔ ÐÏÄÓÔÁÎÏ×ËÉ t ×ÍÅÓÔÏ ×ÓÅÈ ×ÈÏÖÄÅÎÉÊ ÐÅ-

ÒÅÍÅÎÎÏÊ ξ × ÆÏÒÍÕÌÕ ϕ, Ñ×ÌÑÅÔÓÑ ÁËÓÉÏÍÏÊ. (úÁÐÉÓØ ϕ(t/ξ) ÍÏÖÎÏ ÞÉÔÁÔØ

ËÁË ¥ÆÉ ÏÔ ÔÜ ×ÍÅÓÔÏ ËÓÉ¥.)

ë ÓÏÖÁÌÅÎÉÀ, ×Ó¾ ÎÅ ÔÁË ÐÒÏÓÔÏ. îÁÐÒÉÍÅÒ, ÅÓÌÉ ÆÏÒÍÕÌÁ ϕ ÉÍÅÅÔ ×ÉÄ

A(x) ∧ ∃x B(x, x),

ÔÏ ÐÏÄÓÔÁÎÏ×ËÁ ÔÅÒÍÁ f(y) ×ÍÅÓÔÏ x ÄÁÓÔ ÁÂÓÕÒÄÎÏÅ ×ÙÒÁÖÅÎÉÅ

A(f(y)) ∧ ∃f(y) B(f(y), f (y)),

×ÏÏÂÝÅ ÎÅ Ñ×ÌÑÀÝÅÅÓÑ ÆÏÒÍÕÌÏÊ. á ÅÓÌÉ ÐÏÄÓÔÁ×ÉÔØ f(y) ÔÏÌØËÏ ×ÎÕÔÒÉ A

É B, ÔÏ ÐÏÌÕÞÉÔÓÑ ×ÙÒÁÖÅÎÉÅ

A(f(y)) ∧ ∃x B(f(y), f (y)),

ËÏÔÏÒÏÅ ÈÏÔÑ É ÂÕÄÅÔ ÆÏÒÍÕÌÏÊ, ÎÏ ÉÍÅÅÔ ÓÏ×ÓÅÍ ÎÅ ÔÏÔ ÓÍÙÓÌ, ËÏÔÏÒÙÊ ÎÁÍ

ÎÕÖÅÎ.

ëÏÎÅÞÎÏ, × ÄÁÎÎÏÍ ÓÌÕÞÁÅ ÐÏ ÓÍÙÓÌÕ ÑÓÎÏ, ÞÔÏ ÐÏÄÓÔÁ×ÌÑÔØ f(y) ÎÁÄÏ

ÌÉÛØ ×ÍÅÓÔÏ ÓÁÍÏÇÏ ÐÅÒ×ÏÇÏ ×ÈÏÖÄÅÎÉÑ ÐÅÒÅÍÅÎÎÏÊ x. îÏ ÅÓÌÉ ÍÙ ÈÏÔÉÍ

ÏÐÒÅÄÅÌÉÔØ ÆÏÒÍÁÌØÎÕÀ ÓÉÓÔÅÍÕ ÁËÓÉÏÍ É ÐÒÁ×ÉÌ ×Ù×ÏÄÁ, ÔÏ ÎÁÄÏ ÄÁÔØ

ÆÏÒÍÁÌØÎÙÅ ÏÐÒÅÄÅÌÅÎÉÑ.

äÌÑ ËÁÖÄÏÇÏ Ë×ÁÎÔÏÒÁ × ÆÏÒÍÕÌÅ ÒÁÓÓÍÏÔÒÉÍ ÅÇÏ ÏÂÌÁÓÔØ ÄÅÊÓÔ×ÉÑ ¡

ÎÁÞÉÎÁÀÝÕÀÓÑ Ó ÎÅÇÏ ÐÏÄÆÏÒÍÕÌÕ. ó×ÏÂÏÄÎÙÍ ×ÈÏÖÄÅÎÉÅÍ ÉÎÄÉ×ÉÄÎÏÊ ÐÅ-

ÒÅÍÅÎÎÏÊ × ÆÏÒÍÕÌÕ ÎÁÚÙ×ÁÅÔÓÑ ×ÈÏÖÄÅÎÉÅ, ÎÅ ÐÏÐÁÄÁÀÝÅÅ × ÏÂÌÁÓÔØ ÄÅÊ-

ÓÔ×ÉÑ ÏÄÎÏÉÍ¾ÎÎÏÇÏ Ë×ÁÎÔÏÒÁ. ìÅÇËÏ ÐÏÎÑÔØ, ÞÔÏ ÜÔÏ ÏÐÒÅÄÅÌÅÎÉÅ ÍÏÖÎÏ

ÐÅÒÅÆÏÒÍÕÌÉÒÏ×ÁÔØ ÉÎÄÕËÔÉ×ÎÏ:

120 çÌÁ×Á VI. éÓÞÉÓÌÅÎÉÅ ÐÒÅÄÉËÁÔÏ×

• ÌÀÂÏÅ ×ÈÏÖÄÅÎÉÅ ÐÅÒÅÍÅÎÎÏÊ × ÔÅÒÍ Ó×ÏÂÏÄÎÏ;

• Ó×ÏÂÏÄÎÙÅ ×ÈÏÖÄÅÎÉÑ ÐÅÒÅÍÅÎÎÏÊ × ÆÏÒÍÕÌÕ ϕ Ñ×ÌÑÀÔÓÑ Å¾ Ó×ÏÂÏÄÎÙ-

ÍÉ ×ÈÏÖÄÅÎÉÑÍÉ × ÆÏÒÍÕÌÕ ¬ϕ;

• Ó×ÏÂÏÄÎÙÅ ×ÈÏÖÄÅÎÉÑ ÌÀÂÏÊ ÐÅÒÅÍÅÎÎÏÊ × ÏÄÎÕ ÉÚ ÆÏÒÍÕÌ ϕ É ψ Ñ×ÌÑ-

ÀÔÓÑ Ó×ÏÂÏÄÎÙÍÉ ×ÈÏÖÄÅÎÉÑÍÉ × (ϕ ∧ ψ), (ϕ ∨ ψ) É (ϕ → ψ);

• ÐÅÒÅÍÅÎÎÁÑ ξ ÎÅ ÉÍÅÅÔ Ó×ÏÂÏÄÎÙÈ ×ÈÏÖÄÅÎÉÊ × ÆÏÒÍÕÌÙ ∀ξ ϕ É ∃ξ ϕ;

Ó×ÏÂÏÄÎÙÅ ×ÈÏÖÄÅÎÉÑ ÏÓÔÁÌØÎÙÈ ÐÅÒÅÍÅÎÎÙÈ × ϕ Ñ×ÌÑÀÔÓÑ Ó×ÏÂÏÄÎÙ-

ÍÉ ×ÈÏÖÄÅÎÉÑÍÉ × ÜÔÉ Ä×Å ÆÏÒÍÕÌÙ.

óÒÁ×ÎÉ×ÁÑ ÜÔÏ ÏÐÒÅÄÅÌÅÎÉÅ Ó ÉÎÄÕËÔÉ×ÎÙÍ ÏÐÒÅÄÅÌÅÎÉÅÍ ÐÁÒÁÍÅÔÒÏ×

ÆÏÒÍÕÌÙ × ÒÁÚÄÅÌÅ 2, ÍÙ ×ÉÄÉÍ, ÞÔÏ ÐÁÒÁÍÅÔÒÙ ¡ ÜÔÏ ÐÅÒÅÍÅÎÎÙÅ, ÉÍÅÀ-

ÝÉÅ Ó×ÏÂÏÄÎÙÅ ×ÈÏÖÄÅÎÉÑ × ÆÏÒÍÕÌÕ.

÷ÈÏÖÄÅÎÉÑ ÐÅÒÅÍÅÎÎÏÊ, ÎÅ Ñ×ÌÑÀÝÉÅÓÑ Ó×ÏÂÏÄÎÙÍÉ (× ÔÏÍ ÞÉÓÌÅ ÓÔÏÑ-

ÝÉÅ ÒÑÄÏÍ Ó Ë×ÁÎÔÏÒÏÍ) ÎÁÚÙ×ÁÀÔ Ó×ÑÚÁÎÎÙÍÉ. îÁÐÒÉÍÅÒ, ÐÅÒÅÍÅÎÎÁÑ x

ÉÍÅÅÔ ÏÄÎÏ Ó×ÏÂÏÄÎÏÅ É ÔÒÉ Ó×ÑÚÁÎÎÙÈ ×ÈÏÖÄÅÎÉÑ × ÆÏÒÍÕÌÕ A(x) ∧ ∃x

B(x, x).

ôÅÐÅÒØ ÍÏÖÎÏ ×ÎÅÓÔÉ ÐÏÐÒÁ×ËÕ × ÓËÁÚÁÎÎÏÅ ×ÙÛÅ É ÓÞÉÔÁÔØ, ÞÔÏ ÁËÓÉÏ-

ÍÁÍÉ Ñ×ÌÑÀÔÓÑ ÆÏÒÍÕÌÙ

∀ξ ϕ → ϕ(t/ξ),

ÇÄÅ ϕ(t/ξ) ÅÓÔØ ÒÅÚÕÌØÔÁÔ ÐÏÄÓÔÁÎÏ×ËÉ t ×ÍÅÓÔÏ ×ÓÅÈ Ó×ÏÂÏÄÎÙÈ ×ÈÏÖÄÅÎÉÊ

ÐÅÒÅÍÅÎÎÏÊ ξ. ïÄÎÁËÏ ÔÁËÏÊ ÏÇÏ×ÏÒËÉ ÎÅÄÏÓÔÁÔÏÞÎÏ, ËÁË ÐÏËÁÚÙ×ÁÅÔ ÓÌÅÄÕ-

ÀÝÉÊ ÐÒÉÍÅÒ.

ðÏÄÓÔÁ×ÌÑÑ f(y) ×ÍÅÓÔÏ x × ÆÏÒÍÕÌÕ ∀z B(x, z), ÍÙ ÐÏÌÕÞÁÅÍ (× ÐÏÌÎÏÍ

ÓÏÇÌÁÓÉÉ Ó ÎÁÛÅÊ ÉÎÔÕÉÃÉÅÊ) ÆÏÒÍÕÌÕ ∀z B(f(y), z). ôÅÐÅÒØ ÒÁÓÓÍÏÔÒÉÍ

ÆÏÒÍÕÌÕ ∀y B(x, y), ËÏÔÏÒÁÑ ÏÔÌÉÞÁÅÔÓÑ ÏÔ ∀z B(x, z) ÌÉÛØ ÉÍÅÎÅÍ Ó×ÑÚÁÎ-

ÎÏÊ ÐÅÒÅÍÅÎÎÏÊ É ÄÏÌÖÎÁ ÉÍÅÔØ ÔÏÔ ÖÅ ÓÍÙÓÌ. ðÅÒÅÍÅÎÎÁÑ x × ÎÅÊ ÐÏ-ÐÒÅÖ-

ÎÅÍÕ Ó×ÏÂÏÄÎÁ, ÎÏ ÐÏÄÓÔÁÎÏ×ËÁ f(y) ×ÍÅÓÔÏ x ÄÁ¾Ô ÆÏÒÍÕÌÕ ∀y B(f(y), y)),

× ËÏÔÏÒÏÊ f(y) ÎÅÏÖÉÄÁÎÎÏ ÄÌÑ ÓÅÂÑ ÐÏÐÁÄÁÅÔ × ÏÂÌÁÓÔØ ÄÅÊÓÔ×ÉÑ Ë×ÁÎÔÏÒÁ

ÐÏ y. ôÁËÏÅ Ñ×ÌÅÎÉÅ ÉÎÏÇÄÁ ÎÁÚÙ×ÁÀÔ ËÏÌÌÉÚÉÅÊ ÐÅÒÅÍÅÎÎÙÈ; ÐÒÉ ÜÔÏÍ ÐÏÄ-

ÓÔÁÎÏ×ËÁ ÄÁ¾Ô ÆÏÒÍÕÌÕ, ÉÍÅÀÝÕÀ ÓÏ×ÓÅÍ ÎÅ ÔÏÔ ÓÍÙÓÌ, ËÁËÏÊ ÍÙ ÈÏÔÅÌÉ.

úÁÄÁÞÁ 156. ðÒÉ×ÅÄÉÔÅ ÐÒÉÍÅÒ ÆÏÒÍÕÌÙ ×ÉÄÁ ∀ξ ϕ → ϕ(t/ξ), × ËÏÔÏ-

ÒÏÊ ÐÒÏÉÓÈÏÄÉÔ ËÏÌÌÉÚÉÑ ÐÅÒÅÍÅÎÎÙÈ É ËÏÔÏÒÁÑ ÎÅ Ñ×ÌÑÅÔÓÑ ÏÂÝÅÚÎÁÞÉ-

ÍÏÊ. (ïÔ×ÅÔ: ∀x ∃y A(x, y) → ∃yA(y, y).)

ðÏÜÔÏÍÕ ÎÁÍ ÐÒÉÄ¾ÔÓÑ ÐÒÉÎÑÔØ ÅÝ¾ ÏÄÎÕ ÍÅÒÕ ÐÒÅÄÏÓÔÏÒÏÖÎÏÓÔÉ É ÆÏÒ-

ÍÁÌØÎÏ ÏÐÒÅÄÅÌÉÔØ ÐÏÎÑÔÉÅ ËÏÒÒÅËÔÎÏÊ ÐÏÄÓÔÁÎÏ×ËÉ ÔÅÒÍÁ ×ÍÅÓÔÏ ÐÅÒÅ-

ÍÅÎÎÏÊ. íÙ ÂÕÄÅÍ ÇÏ×ÏÒÉÔØ, ÞÔÏ ÐÏÄÓÔÁÎÏ×ËÁ ÔÅÒÍÁ t ×ÍÅÓÔÏ ÐÅÒÅÍÅÎÎÏÊ ξ

ËÏÒÒÅËÔÎÁ, ÅÓÌÉ × ÐÒÏÃÅÓÓÅ ÔÅËÓÔÕÁÌØÎÏÊ ÚÁÍÅÎÙ ×ÓÅÈ Ó×ÏÂÏÄÎÙÈ ×ÈÏÖÄÅ-

ÎÉÊ ÐÅÒÅÍÅÎÎÏÊ ξ ÎÁ ÔÅÒÍ t ÎÉËÁËÁÑ ÐÅÒÅÍÅÎÎÁÑ ÉÚ t ÎÅ ÐÏÐÁÄÁÅÔ × ÏÂÌÁÓÔØ

ÄÅÊÓÔ×ÉÑ ÏÄÎÏÉÍ¾ÎÎÏÇÏ Ë×ÁÎÔÏÒÁ.