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

§4. ÷Ù×ÏÄÙ × ÉÓÞÉÓÌÅÎÉÉ ÐÒÅÄÉËÁÔÏ×                                  131

   úÁÄÁÞÁ 158. ðÕÓÔØ • ¡ ÍÎÏÖÅÓÔ×Ï ÐÒÏÉÚ×ÏÌØÎÙÈ (ÎÅ ÏÂÑÚÁÔÅÌØÎÏ ÚÁ-
ÍËÎÕÔÙÈ) ÆÏÒÍÕÌ. (Á) ðÕÓÔØ ÓÕÝÅÓÔ×ÕÅÔ ¥×Ù×ÏÄ¥ ÎÅËÏÔÏÒÏÊ ÆÏÒÍÕÌÙ ϕ,
× ËÏÔÏÒÏÍ ÎÁÒÁ×ÎÅ Ó ÁËÓÉÏÍÁÍÉ ÉÓÐÏÌØÚÕÀÔÓÑ ÆÏÒÍÕÌÙ ÉÚ •, ÐÒÉ ÜÔÏÍ
×ÓÅ ÐÒÉÍÅÎÅÎÉÑ ÐÒÁ×ÉÌ âÅÒÎÁÊÓÁ ÐÒÅÄÛÅÓÔ×ÕÀÔ ÐÏÑ×ÌÅÎÉÀ ÆÏÒÍÕÌ ÉÚ •.
ðÏËÁÖÉÔÅ, ÞÔÏ • ` ϕ. ðÏËÁÖÉÔÅ, ÞÔÏ ×ÅÒÎÏ É ÏÂÒÁÔÎÏÅ ÕÔ×ÅÒÖÄÅÎÉÅ.
(Â) ðÏËÁÖÉÔÅ, ÅÓÌÉ × ¥×Ù×ÏÄÅ¥ ÆÏÒÍÕÌÙ ϕ ÎÁÒÁ×ÎÅ Ó ÁËÓÉÏÍÁÍÉ ÉÓÐÏÌØÚÕ-
ÀÔÓÑ ÆÏÒÍÕÌÙ ÉÚ •, ÎÏ ÐÒÁ×ÉÌÁ âÅÒÎÁÊÓÁ ÎÅ ÐÒÉÍÅÎÑÀÔÓÑ ÐÏ ÐÅÒÅÍÅÎÎÙÍ,
Ó×ÏÂÏÄÎÙÍ × •, ÔÏ • ` ϕ.
  úÁÄÁÞÁ 159. ðÏËÁÖÉÔÅ, ÞÔÏ ÐÒÁ×ÉÌÁ âÅÒÎÁÊÓÁ ÍÏÖÎÏ ÐÅÒÅÐÉÓÁÔØ
ÔÁË:

                        •, A ` B     •, B ` A
                                              ,
                       •, A ` ∀ξ B  •, ∃ξ ` A
ÇÄÅ ÐÅÒÅÍÅÎÎÁÑ ξ ÎÅ Ñ×ÌÑÅÔÓÑ ÐÁÒÁÍÅÔÒÏÍ ÆÏÒÍÕÌÙ A, Á ÔÁËÖÅ ÐÁÒÁÍÅ-
ÔÒÏÍ ÆÏÒÍÕÌ ÉÚ •. (÷ ÐÅÒ×ÏÍ ÐÒÁ×ÉÌÅ ÍÙ ÄÌÑ ÓÉÍÍÅÔÒÉÉ ×ÙÄÅÌÉÌÉ ÆÏÒ-
ÍÕÌÕ A, ÈÏÔÑ ÏÎÁ ÎÉÞÅÍ ÎÅ ÏÔÌÉÞÁÅÔÓÑ ÏÔ ÆÏÒÍÕÌ ÉÚ •.)

4.3. ðÅÒÅÍÅÎÎÙÅ É ËÏÎÓÔÁÎÔÙ

   ïÔÍÅÔÉÍ Åݾ ÎÅÓËÏÌØËÏ ÐÒÏÓÔÙÈ Ó×ÏÊÓÔ× ×Ù×ÏÄÉÍÏÓÔÉ, ËÏÔÏÒÙÅ ÎÁÍ ÐÏ-
ÔÒÅÂÕÀÔÓÑ:
   ìÅÍÍÁ Ï Ó×ÅÖÉÈ ËÏÎÓÔÁÎÔÁÈ. ðÕÓÔØ ×Ù×ÏÄÉÍÁ ÆÏÒÍÕÌÁ ϕ(c/ξ), ÇÄÅ ϕ ¡
ÐÒÏÉÚ×ÏÌØÎÁÑ ÆÏÒÍÕÌÁ, ξ ¡ ÐÅÒÅÍÅÎÎÁÑ, c ¡ ËÏÎÓÔÁÎÔÁ, ÎÅ ×ÈÏÄÑÝÁÑ × ÆÏÒ-
ÍÕÌÕ ϕ. ôÏÇÄÁ ×Ù×ÏÄÉÍÁ É ÆÏÒÍÕÌÁ ϕ.
   éÎÔÕÉÔÉ×ÎÙÊ ÓÍÙÓÌ ÌÅÍÍÙ: ÅÓÌÉ ÍÙ ÄÏËÁÚÁÌÉ ÞÔÏ-ÔÏ ÐÒÏ ¥Ó×ÅÖÕÀ¥ ËÏÎ-
ÓÔÁÎÔÕ c (ÎÅ ÚÁÐÑÔÎÁ×ÛÕÀ ÓÅÂÑ ÕÞÁÓÔÉÅÍ × ÆÏÒÍÕÌÅ ϕ), ÔÏ ÆÁËÔÉÞÅÓËÉ ÍÙ
ÄÏËÁÚÁÌÉ ÆÏÒÍÕÌÕ ϕ ÄÌÑ ÐÒÏÉÚ×ÏÌØÎÙÈ ÚÎÁÞÅÎÉÊ ÐÅÒÅÍÅÎÎÏÊ.
   äÏËÁÚÁÔÅÌØÓÔ×Ï ÌÅÍÍÙ. ðÏ ÕÓÌÏ×ÉÀ ÓÕÝÅÓÔ×ÕÅÔ ×Ù×ÏÄ ÆÏÒÍÕÌÙ ϕ(c/ξ).
÷ÏÚØÍ¾Í ¥Ó×ÅÖÕÀ¥ ÐÅÒÅÍÅÎÎÕÀ η, ÎÅ ×ÓÔÒÅÞÁÀÝÕÀÓÑ × ÜÔÏÍ ×Ù×ÏÄÅ, É ×ÓÀ-
ÄÕ ÚÁÍÅÎÉÍ × Î¾Í ËÏÎÓÔÁÎÔÕ c ÎÁ ÜÔÕ ÐÅÒÅÍÅÎÎÕÀ. ðÒÉ ÜÔÏÍ ×Ù×ÏÄ ÏÓÔÁÎÅÔÓÑ
×Ù×ÏÄÏÍ, ÔÁË ËÁË ÐÒÁ×ÉÌÁ ÏÂÒÁÝÅÎÉÑ Ó ÐÅÒÅÍÅÎÎÙÍÉ É ËÏÎÓÔÁÎÔÁÍÉ ÎÉÞÅÍ
ÎÅ ÏÔÌÉÞÁÀÔÓÑ (Ë×ÁÎÔÏÒÏ× ÐÏ ÎÏ×ÏÊ ÐÅÒÅÍÅÎÎÏÊ × Î¾Í ÎÅÔ, ÔÁË ÞÔÏ ËÏÒÒÅËÔ-
ÎÙÅ ÐÏÄÓÔÁÎÏ×ËÉ ÏÓÔÁÎÕÔÓÑ ËÏÒÒÅËÔÎÙÍÉ É ÐÒÉÍÅÎÅÎÉÑ ÐÒÁ×ÉÌ âÅÒÎÁÊÓÁ
ÏÓÔÁÎÕÔÓÑ ÄÏÐÕÓÔÉÍÙÍÉ). ôÁËÉÍ ÏÂÒÁÚÏÍ, ×Ù×ÏÄÉÍÁ ÆÏÒÍÕÌÁ ϕ(η/ξ).
   ðÏ ÐÒÁ×ÉÌÕ ÏÂÏÂÝÅÎÉÑ ×Ù×ÏÄÉÍÁ ÆÏÒÍÕÌÁ ∀η ϕ(η/ξ). ïÓÔÁÌÏÓØ ÐÒÉÍÅ-
ÎÉÔØ ÁËÓÉÏÍÕ ∀η ϕ(η/ξ) → ϕ(η/ξ)(ξ/η); ÐÏÄÓÔÁÎÏ×ËÁ × ÐÒÁ×ÏÊ ÞÁÓÔÉ ËÏÒ-
ÒÅËÔÎÁ É ÄÁ¾Ô ÆÏÒÍÕÌÕ ϕ, ÔÁË ËÁË ÓÎÁÞÁÌÁ ÍÙ ÚÁÍÅÎÉÌÉ Ó×ÏÂÏÄÎÙÅ ×ÈÏÖÄÅ-
ÎÉÑ ξ ÎÁ η, Á ÚÁÔÅÍ ÏÂÒÁÔÎÏ (ÔÁË ÞÔÏ × ÚÏÎÕ ÄÅÊÓÔ×ÉÑ Ë×ÁÎÔÏÒÏ× ÐÏ ξ ÏÎÉ
ÐÏÐÁÓÔØ ÎÅ ÍÏÇÌÉ). ìÅÍÍÁ ÄÏËÁÚÁÎÁ.