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

UptoLike

ВУЗ: 

МГТУ ГА | Москва

Составители: 

Рубрика: 

122 çÌÁ×Á VI. éÓÞÉÓÌÅÎÉÅ ÐÒÅÄÉËÁÔÏ×
çÌÁ×ÎÁÑ ÞÁÓÔØ × ÜÔÏÍ ÏÐÒÅÄÅÌÅÎÉÉ ¡ ÐÏÓÌÅÄÎÉÊ ÅÇÏ ÐÕÎËÔ, ËÏÔÏÒÙÊ, ×Ï-
ÐÅÒ×ÙÈ, ÇÏ×ÏÒÉÔ, ÞÔÏ ×ÍÅÓÔÏ Ó×ÑÚÁÎÎÙÈ ×ÈÏÖÄÅÎÉÊ ÐÅÒÅÍÅÎÎÙÈ ÎÉÞÅÇÏ ÐÏÄ-
ÓÔÁ×ÌÑÔØ ÎÅ ÎÁÄÏ, Á ×Ï-×ÔÏÒÙÈ, ÔÒÅÂÕÅÔ, ÞÔÏÂÙ ÐÒÉ ËÏÒÒÅËÔÎÏÊ ÐÏÄÓÔÁÎÏ×ËÅ
ÐÅÒÅÍÅÎÎÙÅ ÉÚ ÔÅÒÍÁ t ÎÅ ÐÏÄÐÁÄÁÌÉ ÐÏÄ ÄÅÊÓÔ×ÉÅ ÏÄÎÏÉ;ÎÎÙÈ Ë×ÁÎÔÏÒÏ×.
ðÏÓÌÅ ×ÓÅÈ ÜÔÉÈ ÐÒÉÇÏÔÏ×ÌÅÎÉÊ ÍÙ ÍÏÖÅÍ ÓÆÏÒÍÕÌÉÒÏ×ÁÔØ Ä×Å ÏÓÔÁ×ÛÉ-
ÅÓÑ ÓÈÅÍÙ ÁËÓÉÏÍ ÉÓÞÉÓÌÅÎÉÑ ÐÒÅÄÉËÁÔÏ×: ÆÏÒÍÕÌÁ
(12) ∀ξ ϕ → ϕ(t/ξ)
É Ä×ÏÊÓÔ×ÅÎÎÁÑ ÅÊ ÆÏÒÍÕÌÁ
(13) ϕ(t/ξ) → ∃ξ ϕ
ÂÕÄÕÔ ÁËÓÉÏÍÁÍÉ ÉÓÞÉÓÌÅÎÉÑ ÐÒÅÄÉËÁÔÏ×, ÅÓÌÉ ÕËÁÚÁÎÎÙÅ × ÎÉÈ ÐÏÄÓÔÁÎÏ×ËÉ
ËÏÒÒÅËÔÎÙ.
ä×Á ÞÁÓÔÎÙÈ ÓÌÕÞÁÑ, ËÏÇÄÁ ÐÏÄÓÔÁÎÏ×ËÁ ÚÁ×ÅÄÏÍÏ ËÏÒÒÅËÔÎÁ: ×Ï-ÐÅÒ×ÙÈ,
ÍÏÖÎÏ ÂÅÚÏÐÁÓÎÏ ÐÏÄÓÔÁ×ÌÑÔØ ËÏÎÓÔÁÎÔÕ (ÉÌÉ ÌÀÂÏÊ ÔÅÒÍ ÂÅÚ ÐÁÒÁÍÅÔÒÏ×),
×Ï-×ÔÏÒÙÈ, ÐÏÄÓÔÁÎÏ×ËÁ ÐÅÒÅÍÅÎÎÏÊ ×ÍÅÓÔÏ ÓÅÂÑ ×ÓÅÇÄÁ ËÏÒÒÅËÔÎÁ (É ÎÉÞÅÇÏ
ÎÅ ÍÅÎÑÅÔ × ÆÏÒÍÕÌÅ).
ïÔÓÀÄÁ ÓÌÅÄÕÅÔ, ÞÔÏ ÆÏÒÍÕÌÙ ∀ξ ϕ → ϕ É ϕ → ∃ξ ϕ ÂÕÄÕÔ ÁËÓÉÏÍÁÍÉ
ÉÓÞÉÓÌÅÎÉÑ ÐÒÅÄÉËÁÔÏ× (ÄÌÑ ÌÀÂÏÊ ÆÏÒÍÕÌÙ ϕ É ÐÅÒÅÍÅÎÎÏÊ ξ).
îÕÖÎÙ ÌÉ ÎÁÍ Åݾ ËÁËÉÅ-ÎÉÂÕÄØ ÁËÓÉÏÍÙ É ÐÒÁ×ÉÌÁ ×Ù×ÏÄÁ? ëÏÎÅÞÎÏ,
ÎÕÖÎÙ, ÐÏÓËÏÌØËÕ ÕÖÅ ÓÆÏÒÍÕÌÉÒÏ×ÁÎÎÙÅ ÁËÓÉÏÍÙ ÎÅ ÐÏÌÎÏÓÔØÀ ÏÔÒÁÖÁÀÔ
ÓÍÙÓÌ Ë×ÁÎÔÏÒÏ×. (îÁÐÒÉÍÅÒ, ÏÎÉ ×ÐÏÌÎÅ ÓÏÇÌÁÓÕÀÔÓÑ Ó ÔÁËÉÍ ÐÏÎÉÍÁÎÉÅÍ
ÜÔÏÇÏ ÓÍÙÓÌÁ: ÆÏÒÍÕÌÁ ∀ξ ϕ ×ÓÅÇÄÁ ÌÏÖÎÁ, Á ÆÏÒÍÕÌÁ ∃ξ ϕ ×ÓÅÇÄÁ ÉÓÔÉÎÎÁ.)
ðÏÜÔÏÍÕ ÍÙ ××ÅÄ¾Í × ÎÁÛÅ ÉÓÞÉÓÌÅÎÉÅ Ä×Á ÐÒÁ×ÉÌÁ ×Ù×ÏÄÁ, ÎÁÚÙ×ÁÅÍÙÅ
ÐÒÁ×ÉÌÁÍÉ âÅÒÎÁÊÓÁ, É ÎÁ ÜÔÏÍ ÏÐÒÅÄÅÌÅÎÉÅ ÉÓÞÉÓÌÅÎÉÑ ÐÒÅÄÉËÁÔÏ× ÂÕÄÅÔ
ÚÁ×ÅÒÛÅÎÏ.
åÓÌÉ ÐÅÒÅÍÅÎÎÁÑ ξ ÎÅ Ñ×ÌÑÅÔÓÑ ÐÁÒÁÍÅÔÒÏÍ ÆÏÒÍÕÌÙ ψ, ÔÏ ÐÒÁ×ÉÌÁ âÅÒ-
ÎÁÊÓÁ ÒÁÚÒÅÛÁÀÔ ÔÁËÉÅ ÐÅÒÅÈÏÄÙ:
ψ → ϕ
ψ → ∀ξ ϕ
ϕ → ψ
∃ξ ϕ → ψ
íÙ ÇÏ×ÏÒÉÍ, ÞÔÏ ÓÔÏÑÝÁÑ ÓÎÉÚÕ ÏÔ ÞÅÒÔÙ (× ËÁÖÄÏÍ ÉÚ ÐÒÁ×ÉÌ) ÆÏÒÍÕÌÁ
ÐÏÌÕÞÁÅÔÓÑ ÐÏ ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÅÍÕ ÐÒÁ×ÉÌÕ ÉÚ ×ÅÒÈÎÅÊ. óÏÏÔ×ÅÔÓÔ×ÅÎÎÏ ÄÏ-
ÐÏÌÎÑÅÔÓÑ É ÏÐÒÅÄÅÌÅÎÉÅ ×Ù×ÏÄÁ ËÁË ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÉ ÆÏÒÍÕÌ, × ËÏÔÏÒÏÊ
ËÁÖÄÁÑ ÆÏÒÍÕÌÁ ÌÉÂÏ Ñ×ÌÑÅÔÓÑ ÁËÓÉÏÍÏÊ, ÌÉÂÏ ÐÏÌÕÞÁÅÔÓÑ ÉÚ ÐÒÅÄÙÄÕÝÉÈ
ÐÏ ÏÄÎÏÍÕ ÉÚ ÐÒÁ×ÉÌ ×Ù×ÏÄÁ (ÒÁÎØÛÅ ÂÙÌÏ ÔÏÌØËÏ ÐÒÁ×ÉÌÏ MP, ÔÅÐÅÒØ ÄÏ-
ÂÁ×ÉÌÉÓØ Ä×Á ÎÏ×ÙÈ ÐÒÁ×ÉÌÁ).
ðÏÑÓÎÉÍ ÉÎÔÕÉÔÉ×ÎÙÊ ÓÍÙÓÌ ÜÔÉÈ ÐÒÁ×ÉÌ. ðÅÒ×ÏÅ ÇÏ×ÏÒÉÔ, ÞÔÏ ÅÓÌÉ
ÉÚ ψ ÓÌÅÄÕÅÔ ϕ, ÐÒÉÞ¾Í × ϕ ÅÓÔØ ÐÁÒÁÍÅÔÒ ξ, ËÏÔÏÒÏÇÏ ÎÅÔ × ψ, ÔÏ ÜÔÏ
ÏÚÎÁÞÁÅÔ, ÞÔÏ ÆÏÒÍÕÌÁ ϕ ÉÓÔÉÎÎÁ ÐÒÉ ×ÓÅÈ ÚÎÁÞÅÎÉÑÈ ÐÁÒÁÍÅÔÒÁ ξ, ÅÓÌÉ
122                                   çÌÁ×Á VI. éÓÞÉÓÌÅÎÉÅ ÐÒÅÄÉËÁÔÏ×

   çÌÁ×ÎÁÑ ÞÁÓÔØ × ÜÔÏÍ ÏÐÒÅÄÅÌÅÎÉÉ ¡ ÐÏÓÌÅÄÎÉÊ ÅÇÏ ÐÕÎËÔ, ËÏÔÏÒÙÊ, ×Ï-
ÐÅÒ×ÙÈ, ÇÏ×ÏÒÉÔ, ÞÔÏ ×ÍÅÓÔÏ Ó×ÑÚÁÎÎÙÈ ×ÈÏÖÄÅÎÉÊ ÐÅÒÅÍÅÎÎÙÈ ÎÉÞÅÇÏ ÐÏÄ-
ÓÔÁ×ÌÑÔØ ÎÅ ÎÁÄÏ, Á ×Ï-×ÔÏÒÙÈ, ÔÒÅÂÕÅÔ, ÞÔÏÂÙ ÐÒÉ ËÏÒÒÅËÔÎÏÊ ÐÏÄÓÔÁÎÏ×ËÅ
ÐÅÒÅÍÅÎÎÙÅ ÉÚ ÔÅÒÍÁ t ÎÅ ÐÏÄÐÁÄÁÌÉ ÐÏÄ ÄÅÊÓÔ×ÉÅ ÏÄÎÏÉ;ÎÎÙÈ Ë×ÁÎÔÏÒÏ×.
   ðÏÓÌÅ ×ÓÅÈ ÜÔÉÈ ÐÒÉÇÏÔÏ×ÌÅÎÉÊ ÍÙ ÍÏÖÅÍ ÓÆÏÒÍÕÌÉÒÏ×ÁÔØ Ä×Å ÏÓÔÁ×ÛÉ-
ÅÓÑ ÓÈÅÍÙ ÁËÓÉÏÍ ÉÓÞÉÓÌÅÎÉÑ ÐÒÅÄÉËÁÔÏ×: ÆÏÒÍÕÌÁ
   (12) ∀ξ ϕ → ϕ(t/ξ)
É Ä×ÏÊÓÔ×ÅÎÎÁÑ ÅÊ ÆÏÒÍÕÌÁ
   (13) ϕ(t/ξ) → ∃ξ ϕ
ÂÕÄÕÔ ÁËÓÉÏÍÁÍÉ ÉÓÞÉÓÌÅÎÉÑ ÐÒÅÄÉËÁÔÏ×, ÅÓÌÉ ÕËÁÚÁÎÎÙÅ × ÎÉÈ ÐÏÄÓÔÁÎÏ×ËÉ
ËÏÒÒÅËÔÎÙ.
   ä×Á ÞÁÓÔÎÙÈ ÓÌÕÞÁÑ, ËÏÇÄÁ ÐÏÄÓÔÁÎÏ×ËÁ ÚÁ×ÅÄÏÍÏ ËÏÒÒÅËÔÎÁ: ×Ï-ÐÅÒ×ÙÈ,
ÍÏÖÎÏ ÂÅÚÏÐÁÓÎÏ ÐÏÄÓÔÁ×ÌÑÔØ ËÏÎÓÔÁÎÔÕ (ÉÌÉ ÌÀÂÏÊ ÔÅÒÍ ÂÅÚ ÐÁÒÁÍÅÔÒÏ×),
×Ï-×ÔÏÒÙÈ, ÐÏÄÓÔÁÎÏ×ËÁ ÐÅÒÅÍÅÎÎÏÊ ×ÍÅÓÔÏ ÓÅÂÑ ×ÓÅÇÄÁ ËÏÒÒÅËÔÎÁ (É ÎÉÞÅÇÏ
ÎÅ ÍÅÎÑÅÔ × ÆÏÒÍÕÌÅ).
   ïÔÓÀÄÁ ÓÌÅÄÕÅÔ, ÞÔÏ ÆÏÒÍÕÌÙ ∀ξ ϕ → ϕ É ϕ → ∃ξ ϕ ÂÕÄÕÔ ÁËÓÉÏÍÁÍÉ
ÉÓÞÉÓÌÅÎÉÑ ÐÒÅÄÉËÁÔÏ× (ÄÌÑ ÌÀÂÏÊ ÆÏÒÍÕÌÙ ϕ É ÐÅÒÅÍÅÎÎÏÊ ξ).
   îÕÖÎÙ ÌÉ ÎÁÍ Åݾ ËÁËÉÅ-ÎÉÂÕÄØ ÁËÓÉÏÍÙ É ÐÒÁ×ÉÌÁ ×Ù×ÏÄÁ? ëÏÎÅÞÎÏ,
ÎÕÖÎÙ, ÐÏÓËÏÌØËÕ ÕÖÅ ÓÆÏÒÍÕÌÉÒÏ×ÁÎÎÙÅ ÁËÓÉÏÍÙ ÎÅ ÐÏÌÎÏÓÔØÀ ÏÔÒÁÖÁÀÔ
ÓÍÙÓÌ Ë×ÁÎÔÏÒÏ×. (îÁÐÒÉÍÅÒ, ÏÎÉ ×ÐÏÌÎÅ ÓÏÇÌÁÓÕÀÔÓÑ Ó ÔÁËÉÍ ÐÏÎÉÍÁÎÉÅÍ
ÜÔÏÇÏ ÓÍÙÓÌÁ: ÆÏÒÍÕÌÁ ∀ξ ϕ ×ÓÅÇÄÁ ÌÏÖÎÁ, Á ÆÏÒÍÕÌÁ ∃ξ ϕ ×ÓÅÇÄÁ ÉÓÔÉÎÎÁ.)
ðÏÜÔÏÍÕ ÍÙ ××ÅÄ¾Í × ÎÁÛÅ ÉÓÞÉÓÌÅÎÉÅ Ä×Á ÐÒÁ×ÉÌÁ ×Ù×ÏÄÁ, ÎÁÚÙ×ÁÅÍÙÅ
ÐÒÁ×ÉÌÁÍÉ âÅÒÎÁÊÓÁ, É ÎÁ ÜÔÏÍ ÏÐÒÅÄÅÌÅÎÉÅ ÉÓÞÉÓÌÅÎÉÑ ÐÒÅÄÉËÁÔÏ× ÂÕÄÅÔ
ÚÁ×ÅÒÛÅÎÏ.
   åÓÌÉ ÐÅÒÅÍÅÎÎÁÑ ξ ÎÅ Ñ×ÌÑÅÔÓÑ ÐÁÒÁÍÅÔÒÏÍ ÆÏÒÍÕÌÙ ψ, ÔÏ ÐÒÁ×ÉÌÁ âÅÒ-
ÎÁÊÓÁ ÒÁÚÒÅÛÁÀÔ ÔÁËÉÅ ÐÅÒÅÈÏÄÙ:
                       ψ→ϕ               ϕ→ψ
                      ψ → ∀ξ ϕ          ∃ξ ϕ → ψ
íÙ ÇÏ×ÏÒÉÍ, ÞÔÏ ÓÔÏÑÝÁÑ ÓÎÉÚÕ ÏÔ ÞÅÒÔÙ (× ËÁÖÄÏÍ ÉÚ ÐÒÁ×ÉÌ) ÆÏÒÍÕÌÁ
ÐÏÌÕÞÁÅÔÓÑ ÐÏ ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÅÍÕ ÐÒÁ×ÉÌÕ ÉÚ ×ÅÒÈÎÅÊ. óÏÏÔ×ÅÔÓÔ×ÅÎÎÏ ÄÏ-
ÐÏÌÎÑÅÔÓÑ É ÏÐÒÅÄÅÌÅÎÉÅ ×Ù×ÏÄÁ ËÁË ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔÉ ÆÏÒÍÕÌ, × ËÏÔÏÒÏÊ
ËÁÖÄÁÑ ÆÏÒÍÕÌÁ ÌÉÂÏ Ñ×ÌÑÅÔÓÑ ÁËÓÉÏÍÏÊ, ÌÉÂÏ ÐÏÌÕÞÁÅÔÓÑ ÉÚ ÐÒÅÄÙÄÕÝÉÈ
ÐÏ ÏÄÎÏÍÕ ÉÚ ÐÒÁ×ÉÌ ×Ù×ÏÄÁ (ÒÁÎØÛÅ ÂÙÌÏ ÔÏÌØËÏ ÐÒÁ×ÉÌÏ MP, ÔÅÐÅÒØ ÄÏ-
ÂÁ×ÉÌÉÓØ Ä×Á ÎÏ×ÙÈ ÐÒÁ×ÉÌÁ).
   ðÏÑÓÎÉÍ ÉÎÔÕÉÔÉ×ÎÙÊ ÓÍÙÓÌ ÜÔÉÈ ÐÒÁ×ÉÌ. ðÅÒ×ÏÅ ÇÏ×ÏÒÉÔ, ÞÔÏ ÅÓÌÉ
ÉÚ ψ ÓÌÅÄÕÅÔ ϕ, ÐÒÉÞ¾Í × ϕ ÅÓÔØ ÐÁÒÁÍÅÔÒ ξ, ËÏÔÏÒÏÇÏ ÎÅÔ × ψ, ÔÏ ÜÔÏ
ÏÚÎÁÞÁÅÔ, ÞÔÏ ÆÏÒÍÕÌÁ ϕ ÉÓÔÉÎÎÁ ÐÒÉ ×ÓÅÈ ÚÎÁÞÅÎÉÑÈ ÐÁÒÁÍÅÔÒÁ ξ, ÅÓÌÉ

Страницы