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

UptoLike

ВУЗ: 

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

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

Рубрика: 

§2. ïÐÒÅÄÅÌÅÎÉÅ ÉÓÔÉÎÎÏÓÔÉ 105
ÄÁÎÎÏÊ ÉÎÔÅÒÐÒÅÔÁÃÉÉ (ÎÁÐÏÍÎÉÍ, × ÉÎÔÅÒÐÒÅÔÁÃÉÉ Ó ËÁÖÄÏÊ ËÏÎ-
ÓÔÁÎÔÏÊ ÓÏÐÏÓÔÁ×ÌÑÅÔÓÑ ÎÅËÏÔÏÒÙÊ ÜÌÅÍÅÎÔ ÎÏÓÉÔÅÌÑ).
• åÓÌÉ t ÉÍÅÅÔ ×ÉÄ f(t
1
, . . . , t
m
), ÇÄÅ f ¡ ÆÕÎËÃÉÏÎÁÌØÎÙÊ ÓÉÍ×ÏÌ ×Á-
ÌÅÎÔÎÏÓÔÉ m, Á t
1
, . . . , t
m
¡ ÔÅÒÍÙ, ÔÏ [t](π) ÅÓÔØ [f]([t
1
](π), . . . , [t
m
](π)),
ÇÄÅ [f] ÅÓÔØ ÆÕÎËÃÉÑ, ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÁÑ ÓÉÍ×ÏÌÕ f × ÎÁÛÅÊ ÉÎÔÅÒÐÒÅ-
ÔÁÃÉÉ, Á [t
i
](π) ÅÓÔØ ÚÎÁÞÅÎÉÅ ÔÅÒÍÁ t
i
ÐÒÉ ÏÃÅÎËÅ π.
ôÅÐÅÒØ ÍÏÖÎÏ ÏÐÒÅÄÅÌÉÔØ ÚÎÁÞÅÎÉÅ ÆÏÒÍÕÌÙ ϕ ÐÒÉ ÄÁÎÎÏÊ ÏÃÅÎËÅ π ×
ÄÁÎÎÏÊ ÉÎÔÅÒÐÒÅÔÁÃÉÉ, ËÏÔÏÒÏÅ ÏÂÏÚÎÁÞÁÅÔÓÑ [ϕ](π) É ÍÏÖÅÔ ÂÙÔØ ÒÁ×ÎÏ
é ÉÌÉ ì; × ÐÅÒ×ÏÍ ÓÌÕÞÁÅ ÆÏÒÍÕÌÁ ÎÁÚÙ×ÁÅÔÓÑ ÉÓÔÉÎÎÏÊ, ×Ï ×ÔÏÒÏÍ ¡
ÌÏÖÎÏÊ. üÔÏ ÏÐÒÅÄÅÌÅÎÉÅ ÔÁËÖÅ ÉÎÄÕËÔÉ×ÎÏ:
• úÎÁÞÅÎÉÅ ÁÔÏÍÁÒÎÏÊ ÆÏÒÍÕÌÙ A(t
1
, . . . , t
m
) ÏÐÒÅÄÅÌÑÅÔÓÑ ËÁË
[A]([t
1
](π), . . . , [t
m
](π)),
ÇÄÅ [A] ¡ ÐÒÅÄÉËÁÔ, ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÉÊ ÐÒÅÄÉËÁÔÎÏÍÕ ÓÉÍ×ÏÌÕ A ×
ÒÁÓÓÍÁÔÒÉ×ÁÅÍÏÊ ÉÎÔÅÒÐÒÅÔÁÃÉÉ. åÓÌÉ ÆÏÒÍÕÌÁ ÐÒÅÄÓÔÁ×ÌÑÅÔ ÓÏÂÏÊ
ÎÕÌØÍÅÓÔÎÙÊ ÐÒÅÄÉËÁÔÎÙÊ ÓÉÍ×ÏÌ, ÔÏ Å¾ ÚÎÁÞÅÎÉÅ ÎÅ ÚÁ×ÉÓÉÔ ÏÔ ÏÃÅÎ-
ËÉ É ÅÓÔØ ÚÎÁÞÅÎÉÅ ÜÔÏÇÏ ÓÉÍ×ÏÌÁ.
• [¬ϕ](π) ÏÐÒÅÄÅÌÑÅÔÓÑ ËÁË ¬[ϕ(π)], ÇÄÅ ¬ ÐÏÎÉÍÁÅÔÓÑ ËÁË ÏÐÅÒÁÃÉÑ × B.
äÒÕÇÉÍÉ ÓÌÏ×ÁÍÉ, ÆÏÒÍÕÌÁ ¬ϕ ÉÓÔÉÎÎÁ ÐÒÉ ÏÃÅÎËÅ π ÔÏÇÄÁ É ÔÏÌØËÏ
ÔÏÇÄÁ, ËÏÇÄÁ ÆÏÒÍÕÌÁ ϕ ÌÏÖÎÁ ÐÒÉ ÜÔÏÊ ÏÃÅÎËÅ.
• [ϕ ∧ ψ](π) ÏÐÒÅÄÅÌÑÅÔÓÑ ËÁË [ϕ](π) ∧ [ψ](π), ÇÄÅ ∧ × ÐÒÁ×ÏÊ ÞÁÓÔÉ ÐÏÎÉ-
ÍÁÅÔÓÑ ËÁË ÏÐÅÒÁÃÉÑ × B. (äÒÕÇÉÍÉ ÓÌÏ×ÁÍÉ, ÆÏÒÍÕÌÁ (ϕ ∧ ψ) ÉÓÔÉÎÎÁ
ÐÒÉ ÏÃÅÎËÅ π ÔÏÇÄÁ É ÔÏÌØËÏ ÔÏÇÄÁ, ËÏÇÄÁ ÏÂÅ ÆÏÒÍÕÌÙ ϕ É ψ ÉÓÔÉÎÎÙ
ÐÒÉ ÜÔÏÊ ÏÃÅÎËÅ.) áÎÁÌÏÇÉÞÎÙÍ ÏÂÒÁÚÏÍ [ϕ ∨ ψ](π) ÏÐÒÅÄÅÌÑÅÔÓÑ ËÁË
[ϕ](π) ∨ [ψ](π), Á [ϕ → ψ](π) ¡ ËÁË [ϕ](π) → [ψ](π).
• æÏÒÍÕÌÁ ∀ξ ϕ ÉÓÔÉÎÎÁ ÎÁ ÏÃÅÎËÅ π ÔÏÇÄÁ É ÔÏÌØËÏ ÔÏÇÄÁ, ËÏÇÄÁ ÆÏÒÍÕ-
ÌÁ ϕ ÉÓÔÉÎÎÁ ÎÁ ÌÀÂÏÊ ÏÃÅÎËÅ π
0
, ËÏÔÏÒÁÑ ÓÏ×ÐÁÄÁÅÔ Ó π ×ÓÀÄÕ, ËÒÏÍÅ
ÚÎÁÞÅÎÉÑ ÐÅÒÅÍÅÎÎÏÊ ξ (ËÏÔÏÒÏÅ × ÏÃÅÎËÅ π
0
ÍÏÖÅÔ ÂÙÔØ ÌÀÂÙÍ). äÒÕ-
ÇÉÍÉ ÓÌÏ×ÁÍÉ, ÅÓÌÉ ÏÂÏÚÎÁÞÉÔØ ÞÅÒÅÚ π +(ξ 7→ m) ÏÃÅÎËÕ, ÐÒÉ ËÏÔÏÒÏÊ
ÚÎÁÞÅÎÉÅ ÐÅÒÅÍÅÎÎÏÊ ξ ÒÁ×ÎÏ m, Á ÏÓÔÁÌØÎÙÅ ÐÅÒÅÍÅÎÎÙÅ ÐÒÉÎÉÍÁÀÔ
ÔÅ ÖÅ ÚÎÁÞÅÎÉÑ, ÞÔÏ É × ÏÃÅÎËÅ π, ÔÏ
[∀ξ ϕ](π) =
^
m∈M
[ϕ](π + (ξ 7→ m)).
(÷ ÐÒÁ×ÏÊ ÞÁÓÔÉ ÓÔÏÉÔ ÂÅÓËÏÎÅÞÎÁÑ ËÏÎßÀÎËÃÉÑ, ËÏÔÏÒÁÑ ÉÓÔÉÎÎÁ, ÅÓ-
ÌÉ ×ÓŠž ÞÌÅÎÙ ÉÓÔÉÎÎÙ.)
• æÏÒÍÕÌÁ ∃ξ ϕ ÉÓÔÉÎÎÁ ÎÁ ÏÃÅÎËÅ π ÔÏÇÄÁ É ÔÏÌØËÏ ÔÏÇÄÁ, ËÏÇÄÁ ÆÏÒ-
ÍÕÌÁ ϕ ÉÓÔÉÎÎÁ ÎÁ ÎÅËÏÔÏÒÏÊ ÏÃÅÎËÅ π
0
, ËÏÔÏÒÁÑ ÓÏ×ÐÁÄÁÅÔ Ó π ×ÓÀÄÕ,
ËÒÏÍÅ ÚÎÁÞÅÎÉÑ ÐÅÒÅÍÅÎÎÏÊ ξ (ËÏÔÏÒÏÅ × ÏÃÅÎËÅ π
0
ÍÏÖÅÔ ÂÙÔØ ÌÀÂÙÍ).
§2. ïÐÒÅÄÅÌÅÎÉÅ ÉÓÔÉÎÎÏÓÔÉ                                                             105

     ÄÁÎÎÏÊ ÉÎÔÅÒÐÒÅÔÁÃÉÉ (ÎÁÐÏÍÎÉÍ, × ÉÎÔÅÒÐÒÅÔÁÃÉÉ Ó ËÁÖÄÏÊ ËÏÎ-
     ÓÔÁÎÔÏÊ ÓÏÐÏÓÔÁ×ÌÑÅÔÓÑ ÎÅËÏÔÏÒÙÊ ÜÌÅÍÅÎÔ ÎÏÓÉÔÅÌÑ).
   • åÓÌÉ t ÉÍÅÅÔ ×ÉÄ f (t1, . . . , tm), ÇÄÅ f ¡ ÆÕÎËÃÉÏÎÁÌØÎÙÊ ÓÉÍ×ÏÌ ×Á-
     ÌÅÎÔÎÏÓÔÉ m, Á t1 , . . . , tm ¡ ÔÅÒÍÙ, ÔÏ [t](π) ÅÓÔØ [f ]([t1](π), . . . , [tm ](π)),
     ÇÄÅ [f ] ÅÓÔØ ÆÕÎËÃÉÑ, ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÁÑ ÓÉÍ×ÏÌÕ f × ÎÁÛÅÊ ÉÎÔÅÒÐÒÅ-
     ÔÁÃÉÉ, Á [ti](π) ÅÓÔØ ÚÎÁÞÅÎÉÅ ÔÅÒÍÁ ti ÐÒÉ ÏÃÅÎËÅ π.
  ôÅÐÅÒØ ÍÏÖÎÏ ÏÐÒÅÄÅÌÉÔØ ÚÎÁÞÅÎÉÅ ÆÏÒÍÕÌÙ ϕ ÐÒÉ ÄÁÎÎÏÊ ÏÃÅÎËÅ π ×
ÄÁÎÎÏÊ ÉÎÔÅÒÐÒÅÔÁÃÉÉ, ËÏÔÏÒÏÅ ÏÂÏÚÎÁÞÁÅÔÓÑ [ϕ](π) É ÍÏÖÅÔ ÂÙÔØ ÒÁ×ÎÏ
é ÉÌÉ ì; × ÐÅÒ×ÏÍ ÓÌÕÞÁÅ ÆÏÒÍÕÌÁ ÎÁÚÙ×ÁÅÔÓÑ ÉÓÔÉÎÎÏÊ, ×Ï ×ÔÏÒÏÍ ¡
ÌÏÖÎÏÊ. üÔÏ ÏÐÒÅÄÅÌÅÎÉÅ ÔÁËÖÅ ÉÎÄÕËÔÉ×ÎÏ:
   • úÎÁÞÅÎÉÅ ÁÔÏÍÁÒÎÏÊ ÆÏÒÍÕÌÙ A(t1, . . . , tm) ÏÐÒÅÄÅÌÑÅÔÓÑ ËÁË
                                [A]([t1](π), . . . , [tm](π)),
      ÇÄÅ [A] ¡ ÐÒÅÄÉËÁÔ, ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÉÊ ÐÒÅÄÉËÁÔÎÏÍÕ ÓÉÍ×ÏÌÕ A ×
      ÒÁÓÓÍÁÔÒÉ×ÁÅÍÏÊ ÉÎÔÅÒÐÒÅÔÁÃÉÉ. åÓÌÉ ÆÏÒÍÕÌÁ ÐÒÅÄÓÔÁ×ÌÑÅÔ ÓÏÂÏÊ
      ÎÕÌØÍÅÓÔÎÙÊ ÐÒÅÄÉËÁÔÎÙÊ ÓÉÍ×ÏÌ, ÔÏ Å¾ ÚÎÁÞÅÎÉÅ ÎÅ ÚÁ×ÉÓÉÔ ÏÔ ÏÃÅÎ-
      ËÉ É ÅÓÔØ ÚÎÁÞÅÎÉÅ ÜÔÏÇÏ ÓÉÍ×ÏÌÁ.
    • [¬ϕ](π) ÏÐÒÅÄÅÌÑÅÔÓÑ ËÁË ¬[ϕ(π)], ÇÄÅ ¬ ÐÏÎÉÍÁÅÔÓÑ ËÁË ÏÐÅÒÁÃÉÑ × B.
      äÒÕÇÉÍÉ ÓÌÏ×ÁÍÉ, ÆÏÒÍÕÌÁ ¬ϕ ÉÓÔÉÎÎÁ ÐÒÉ ÏÃÅÎËÅ π ÔÏÇÄÁ É ÔÏÌØËÏ
      ÔÏÇÄÁ, ËÏÇÄÁ ÆÏÒÍÕÌÁ ϕ ÌÏÖÎÁ ÐÒÉ ÜÔÏÊ ÏÃÅÎËÅ.
    • [ϕ ∧ ψ](π) ÏÐÒÅÄÅÌÑÅÔÓÑ ËÁË [ϕ](π) ∧ [ψ](π), ÇÄÅ ∧ × ÐÒÁ×ÏÊ ÞÁÓÔÉ ÐÏÎÉ-
      ÍÁÅÔÓÑ ËÁË ÏÐÅÒÁÃÉÑ × B. (äÒÕÇÉÍÉ ÓÌÏ×ÁÍÉ, ÆÏÒÍÕÌÁ (ϕ ∧ ψ) ÉÓÔÉÎÎÁ
      ÐÒÉ ÏÃÅÎËÅ π ÔÏÇÄÁ É ÔÏÌØËÏ ÔÏÇÄÁ, ËÏÇÄÁ ÏÂÅ ÆÏÒÍÕÌÙ ϕ É ψ ÉÓÔÉÎÎÙ
      ÐÒÉ ÜÔÏÊ ÏÃÅÎËÅ.) áÎÁÌÏÇÉÞÎÙÍ ÏÂÒÁÚÏÍ [ϕ ∨ ψ](π) ÏÐÒÅÄÅÌÑÅÔÓÑ ËÁË
      [ϕ](π) ∨ [ψ](π), Á [ϕ → ψ](π) ¡ ËÁË [ϕ](π) → [ψ](π).
    • æÏÒÍÕÌÁ ∀ξ ϕ ÉÓÔÉÎÎÁ ÎÁ ÏÃÅÎËÅ π ÔÏÇÄÁ É ÔÏÌØËÏ ÔÏÇÄÁ, ËÏÇÄÁ ÆÏÒÍÕ-
      ÌÁ ϕ ÉÓÔÉÎÎÁ ÎÁ ÌÀÂÏÊ ÏÃÅÎËÅ π 0 , ËÏÔÏÒÁÑ ÓÏ×ÐÁÄÁÅÔ Ó π ×ÓÀÄÕ, ËÒÏÍÅ
      ÚÎÁÞÅÎÉÑ ÐÅÒÅÍÅÎÎÏÊ ξ (ËÏÔÏÒÏÅ × ÏÃÅÎËÅ π 0 ÍÏÖÅÔ ÂÙÔØ ÌÀÂÙÍ). äÒÕ-
      ÇÉÍÉ ÓÌÏ×ÁÍÉ, ÅÓÌÉ ÏÂÏÚÎÁÞÉÔØ ÞÅÒÅÚ π + (ξ 7→ m) ÏÃÅÎËÕ, ÐÒÉ ËÏÔÏÒÏÊ
      ÚÎÁÞÅÎÉÅ ÐÅÒÅÍÅÎÎÏÊ ξ ÒÁ×ÎÏ m, Á ÏÓÔÁÌØÎÙÅ ÐÅÒÅÍÅÎÎÙÅ ÐÒÉÎÉÍÁÀÔ
      ÔÅ ÖÅ ÚÎÁÞÅÎÉÑ, ÞÔÏ É × ÏÃÅÎËÅ π, ÔÏ
                                    ^
                        [∀ξ ϕ](π) =   [ϕ](π + (ξ 7→ m)).
                                        m∈M

      (÷ ÐÒÁ×ÏÊ ÞÁÓÔÉ ÓÔÏÉÔ ÂÅÓËÏÎÅÞÎÁÑ ËÏÎßÀÎËÃÉÑ, ËÏÔÏÒÁÑ ÉÓÔÉÎÎÁ, ÅÓ-
      ÌÉ ×ÓŠž ÞÌÅÎÙ ÉÓÔÉÎÎÙ.)
    • æÏÒÍÕÌÁ ∃ξ ϕ ÉÓÔÉÎÎÁ ÎÁ ÏÃÅÎËÅ π ÔÏÇÄÁ É ÔÏÌØËÏ ÔÏÇÄÁ, ËÏÇÄÁ ÆÏÒ-
      ÍÕÌÁ ϕ ÉÓÔÉÎÎÁ ÎÁ ÎÅËÏÔÏÒÏÊ ÏÃÅÎËÅ π 0 , ËÏÔÏÒÁÑ ÓÏ×ÐÁÄÁÅÔ Ó π ×ÓÀÄÕ,
      ËÒÏÍÅ ÚÎÁÞÅÎÉÑ ÐÅÒÅÍÅÎÎÏÊ ξ (ËÏÔÏÒÏÅ × ÏÃÅÎËÅ π 0 ÍÏÖÅÔ ÂÙÔØ ÌÀÂÙÍ).

Страницы