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

UptoLike

ВУЗ: 

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

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

Рубрика: 

§2. áËÓÉÏÍÙ É ÐÒÁ×ÉÌÁ ×Ù×ÏÄÁ 121
ðÅÄÁÎÔÉÞÎÙÊ ÞÉÔÁÔÅÌØ ÍÏÇ ÂÙ ÐÏÐÒÏÓÉÔØ ÄÏËÁÚÁÔØ, ÞÔÏ ÒÅÚÕÌØÔÁÔ ÔÁËÏÊ
ÐÏÄÓÔÁÎÏ×ËÉ ÂÕÄÅÔ ÆÏÒÍÕÌÏÊ. üÔÏ ÐÒÏÝÅ ×ÓÅÇÏ ÓÄÅÌÁÔØ ÔÁË: ÄÁÔØ ÉÎÄÕËÔÉ×-
ÎÏÅ ÏÐÒÅÄÅÌÅÎÉÅ ËÏÒÒÅËÔÎÏÊ ÐÏÄÓÔÁÎÏ×ËÉ, ÒÁ×ÎÏÓÉÌØÎÏÅ ÉÓÈÏÄÎÏÍÕ.
óÎÁÞÁÌÁ ÏÐÒÅÄÅÌÉÍ ÉÎÄÕËÔÉ×ÎÏ ÒÅÚÕÌØÔÁÔ ÐÏÄÓÔÁÎÏ×ËÉ ÔÅÒÍÁ t ×ÍÅÓÔÏ
ÐÅÒÅÍÅÎÎÏÊ ξ × ÔÅÒÍ u; ÜÔÏÔ ÒÅÚÕÌØÔÁÔ ÂÕÄÅÍ ÏÂÏÚÎÁÞÁÔØ u(t/ξ):
• ξ(t/ξ) ÅÓÔØ t; ÄÌÑ ÌÀÂÏÊ ÐÅÒÅÍÅÎÎÏÊ η, ÏÔÌÉÞÎÏÊ ÏÔ ξ, ÍÙ ÐÏÌÁÇÁÅÍ
η(t/ξ) ÒÁ×ÎÙÍ η.
• ÅÓÌÉ f ÅÓÔØ k-ÍÅÓÔÎÙÊ ÆÕÎËÃÉÏÎÁÌØÎÙÊ ÓÉÍ×ÏÌ, Á t
1
, . . . , t
k
¡ ÔÅÒÍÙ,
ÔÏ
f(t
1
, . . . , t
k
)(t/ξ) = f(t
1
(t/ξ), . . . , t
k
(t/ξ)).
ôÅÐÅÒØ ÉÎÄÕËÔÉ×ÎÏÅ ÏÐÒÅÄÅÌÅÎÉÅ ÐÒÏÄÏÌÖÁÅÔÓÑ ÄÌÑ ÆÏÒÍÕÌ:
• ÄÌÑ ÁÔÏÍÁÒÎÙÈ ÆÏÒÍÕÌ: ÅÓÌÉ R ÅÓÔØ k-ÍÅÓÔÎÙÊ ÐÒÅÄÉËÁÔÎÙÊ ÓÉÍ×ÏÌ,
Á t
1
, . . . , t
k
¡ ÔÅÒÍÙ, ÔÏ
R(t
1
, . . . , t
k
)(t/ξ) = R(t
1
(t/ξ), . . . , t
k
(t/ξ))
É ÐÏÄÓÔÁÎÏ×ËÁ Ñ×ÌÑÅÔÓÑ ËÏÒÒÅËÔÎÏÊ;
• ÐÏÄÓÔÁÎÏ×ËÁ ÔÅÒÍÁ t ×ÍÅÓÔÏ ÐÅÒÅÍÅÎÎÏÊ ξ × ÆÏÒÍÕÌÕ ¬ϕ ËÏÒÒÅËÔÎÁ,
ÅÓÌÉ ÏÎÁ ËÏÒÒÅËÔÎÁ ÄÌÑ ÆÏÒÍÕÌÙ ϕ, ÐÒÉ ÜÔÏÍ
[¬ϕ](t/ξ) = ¬[ϕ(t/ξ)]
(Ë×ÁÄÒÁÔÎÙÅ ÓËÏÂËÉ ÕËÁÚÙ×ÁÀÔ ÐÏÒÑÄÏË ÄÅÊÓÔ×ÉÊ, ÎÅ Ñ×ÌÑÑÓØ ÞÁÓÔØÀ
ÆÏÒÍÕÌÙ);
• ÐÏÄÓÔÁÎÏ×ËÁ ÔÅÒÍÁ t ×ÍÅÓÔÏ ÐÅÒÅÍÅÎÎÏÊ ξ × ÆÏÒÍÕÌÕ (ϕ∧ψ) ËÏÒÒÅËÔÎÁ,
ÅÓÌÉ ÏÎÁ ËÏÒÒÅËÔÎÁ ÄÌÑ ÏÂÅÉÈ ÆÏÒÍÕÌ ϕ É ψ, ÐÒÉ ÜÔÏÍ
(ϕ ∧ ψ)(t/ξ) = (ϕ(t/ξ) ∧ ψ(t/ξ));
ÁÎÁÌÏÇÉÞÎÏ ÄÌÑ ÆÏÒÍÕÌ (ϕ ∨ ψ) É (ϕ → ψ);
• ÎÁËÏÎÅÃ, ÐÏÄÓÔÁÎÏ×ËÁ t ×ÍÅÓÔÏ ξ × ÆÏÒÍÕÌÕ ∀η ϕ ËÏÒÒÅËÔÎÁ × Ä×ÕÈ
ÓÌÕÞÁÑÈ:
(1) ÅÓÌÉ ξ ÎÅ Ñ×ÌÑÅÔÓÑ ÐÁÒÁÍÅÔÒÏÍ ÆÏÒÍÕÌÙ ∀η ϕ (ÜÔÏ ×ÏÚÍÏÖÎÏ,
ËÏÇÄÁ ξ ÎÅ Ñ×ÌÑÅÔÓÑ ÐÁÒÁÍÅÔÒÏÍ ϕ ÉÌÉ ËÏÇÄÁ ξ ÓÏ×ÐÁÄÁÅÔ Ó η); ÐÒÉ
ÜÔÏÍ ÐÏÄÓÔÁÎÏ×ËÁ ÎÉÞÅÇÏ ÎÅ ÍÅÎÑÅÔ × ÆÏÒÍÕÌÅ;
(2) ÐÅÒÅÍÅÎÎÁÑ ξ Ñ×ÌÑÅÔÓÑ ÐÁÒÁÍÅÔÒÏÍ ÆÏÒÍÕÌÙ ∀η ϕ, ÎÏ ÐÅÒÅÍÅÎ-
ÎÁÑ η ÎÅ ×ÈÏÄÉÔ × ÔÅÒÍ t É ÐÏÄÓÔÁÎÏ×ËÁ ϕ(t/ξ) ËÏÒÒÅËÔÎÁ; ÐÒÉ ÜÔÏÍ
[∀η ϕ](t/ξ) = ∀η [ϕ(t/ξ)].
áÎÁÌÏÇÉÞÎÏ ÏÐÒÅÄÅÌÑÅÔÓÑ ËÏÒÒÅËÔÎÁÑ ÐÏÄÓÔÁÎÏ×ËÁ × ÆÏÒÍÕÌÕ ∃ξϕ.
§2. áËÓÉÏÍÙ É ÐÒÁ×ÉÌÁ ×Ù×ÏÄÁ                                                 121

   ðÅÄÁÎÔÉÞÎÙÊ ÞÉÔÁÔÅÌØ ÍÏÇ ÂÙ ÐÏÐÒÏÓÉÔØ ÄÏËÁÚÁÔØ, ÞÔÏ ÒÅÚÕÌØÔÁÔ ÔÁËÏÊ
ÐÏÄÓÔÁÎÏ×ËÉ ÂÕÄÅÔ ÆÏÒÍÕÌÏÊ. üÔÏ ÐÒÏÝÅ ×ÓÅÇÏ ÓÄÅÌÁÔØ ÔÁË: ÄÁÔØ ÉÎÄÕËÔÉ×-
ÎÏÅ ÏÐÒÅÄÅÌÅÎÉÅ ËÏÒÒÅËÔÎÏÊ ÐÏÄÓÔÁÎÏ×ËÉ, ÒÁ×ÎÏÓÉÌØÎÏÅ ÉÓÈÏÄÎÏÍÕ.
   óÎÁÞÁÌÁ ÏÐÒÅÄÅÌÉÍ ÉÎÄÕËÔÉ×ÎÏ ÒÅÚÕÌØÔÁÔ ÐÏÄÓÔÁÎÏ×ËÉ ÔÅÒÍÁ t ×ÍÅÓÔÏ
ÐÅÒÅÍÅÎÎÏÊ ξ × ÔÅÒÍ u; ÜÔÏÔ ÒÅÚÕÌØÔÁÔ ÂÕÄÅÍ ÏÂÏÚÎÁÞÁÔØ u(t/ξ):
   • ξ(t/ξ) ÅÓÔØ t; ÄÌÑ ÌÀÂÏÊ ÐÅÒÅÍÅÎÎÏÊ η, ÏÔÌÉÞÎÏÊ ÏÔ ξ, ÍÙ ÐÏÌÁÇÁÅÍ
     η(t/ξ) ÒÁ×ÎÙÍ η.
   • ÅÓÌÉ f ÅÓÔØ k-ÍÅÓÔÎÙÊ ÆÕÎËÃÉÏÎÁÌØÎÙÊ ÓÉÍ×ÏÌ, Á t1 , . . . , tk ¡ ÔÅÒÍÙ,
     ÔÏ
                 f (t1, . . . , tk )(t/ξ) = f (t1(t/ξ), . . . , tk (t/ξ)).
  ôÅÐÅÒØ ÉÎÄÕËÔÉ×ÎÏÅ ÏÐÒÅÄÅÌÅÎÉÅ ÐÒÏÄÏÌÖÁÅÔÓÑ ÄÌÑ ÆÏÒÍÕÌ:
   • ÄÌÑ ÁÔÏÍÁÒÎÙÈ ÆÏÒÍÕÌ: ÅÓÌÉ R ÅÓÔØ k-ÍÅÓÔÎÙÊ ÐÒÅÄÉËÁÔÎÙÊ ÓÉÍ×ÏÌ,
     Á t1, . . . , tk ¡ ÔÅÒÍÙ, ÔÏ
                 R(t1 , . . . , tk )(t/ξ) = R(t1(t/ξ), . . . , tk (t/ξ))
     É ÐÏÄÓÔÁÎÏ×ËÁ Ñ×ÌÑÅÔÓÑ ËÏÒÒÅËÔÎÏÊ;
   • ÐÏÄÓÔÁÎÏ×ËÁ ÔÅÒÍÁ t ×ÍÅÓÔÏ ÐÅÒÅÍÅÎÎÏÊ ξ × ÆÏÒÍÕÌÕ ¬ϕ ËÏÒÒÅËÔÎÁ,
     ÅÓÌÉ ÏÎÁ ËÏÒÒÅËÔÎÁ ÄÌÑ ÆÏÒÍÕÌÙ ϕ, ÐÒÉ ÜÔÏÍ
                              [¬ϕ](t/ξ) = ¬[ϕ(t/ξ)]

     (Ë×ÁÄÒÁÔÎÙÅ ÓËÏÂËÉ ÕËÁÚÙ×ÁÀÔ ÐÏÒÑÄÏË ÄÅÊÓÔ×ÉÊ, ÎÅ Ñ×ÌÑÑÓØ ÞÁÓÔØÀ
     ÆÏÒÍÕÌÙ);
   • ÐÏÄÓÔÁÎÏ×ËÁ ÔÅÒÍÁ t ×ÍÅÓÔÏ ÐÅÒÅÍÅÎÎÏÊ ξ × ÆÏÒÍÕÌÕ (ϕ∧ψ) ËÏÒÒÅËÔÎÁ,
     ÅÓÌÉ ÏÎÁ ËÏÒÒÅËÔÎÁ ÄÌÑ ÏÂÅÉÈ ÆÏÒÍÕÌ ϕ É ψ, ÐÒÉ ÜÔÏÍ
                      (ϕ ∧ ψ)(t/ξ) = (ϕ(t/ξ) ∧ ψ(t/ξ));
     ÁÎÁÌÏÇÉÞÎÏ ÄÌÑ ÆÏÒÍÕÌ (ϕ ∨ ψ) É (ϕ → ψ);
   • ÎÁËÏÎÅÃ, ÐÏÄÓÔÁÎÏ×ËÁ t ×ÍÅÓÔÏ ξ × ÆÏÒÍÕÌÕ ∀η ϕ ËÏÒÒÅËÔÎÁ × Ä×ÕÈ
     ÓÌÕÞÁÑÈ:
        (1) ÅÓÌÉ ξ ÎÅ Ñ×ÌÑÅÔÓÑ ÐÁÒÁÍÅÔÒÏÍ ÆÏÒÍÕÌÙ ∀η ϕ (ÜÔÏ ×ÏÚÍÏÖÎÏ,
     ËÏÇÄÁ ξ ÎÅ Ñ×ÌÑÅÔÓÑ ÐÁÒÁÍÅÔÒÏÍ ϕ ÉÌÉ ËÏÇÄÁ ξ ÓÏ×ÐÁÄÁÅÔ Ó η); ÐÒÉ
     ÜÔÏÍ ÐÏÄÓÔÁÎÏ×ËÁ ÎÉÞÅÇÏ ÎÅ ÍÅÎÑÅÔ × ÆÏÒÍÕÌÅ;
        (2) ÐÅÒÅÍÅÎÎÁÑ ξ Ñ×ÌÑÅÔÓÑ ÐÁÒÁÍÅÔÒÏÍ ÆÏÒÍÕÌÙ ∀η ϕ, ÎÏ ÐÅÒÅÍÅÎ-
     ÎÁÑ η ÎÅ ×ÈÏÄÉÔ × ÔÅÒÍ t É ÐÏÄÓÔÁÎÏ×ËÁ ϕ(t/ξ) ËÏÒÒÅËÔÎÁ; ÐÒÉ ÜÔÏÍ
                            [∀η ϕ](t/ξ) = ∀η [ϕ(t/ξ)].
       áÎÁÌÏÇÉÞÎÏ ÏÐÒÅÄÅÌÑÅÔÓÑ ËÏÒÒÅËÔÎÁÑ ÐÏÄÓÔÁÎÏ×ËÁ × ÆÏÒÍÕÌÕ ∃ξϕ.

Страницы