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

UptoLike

ВУЗ: 

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

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

Рубрика: 

§3. îÅÓËÏÌØËÏ ÚÁÍÅÞÁÎÉÊ 173
ÔÁËÉÍ Ó×ÏÊÓÔ×ÏÍ: ÐÒÉ ËÁÖÄÏÍ p ÌÉÂÏ ÆÕÎËÃÉÑ h
p
ÎÅ ÏÐÒÅÄÅÌÅÎÁ × ÔÏÞËÅ n(p),
ÌÉÂÏ n(p) Ñ×ÌÑÅÔÓÑ ÎÅÐÏÄ×ÉÖÎÏÊ ÔÏÞËÏÊ ÆÕÎËÃÉÉ h
p
.
úÁÄÁÞÁ 199. õÂÅÄÉÔÅÓØ, ÞÔÏ ÐÒÉ×ÅľÎÎÁÑ × ÄÏËÁÚÁÔÅÌØÓÔ×Å ÔÅÏÒÅ-
ÍÙ 68 ËÏÎÓÔÒÕËÃÉÑ ËÁË ÒÁÚ É ÄÁ¾Ô ÆÕÎËÃÉÀ n(p) Ó ÔÁËÉÍ Ó×ÏÊÓÔ×ÏÍ.
úÁÄÁÞÁ 200. ïÂßÅÄÉÎÑÑ ÓÄÅÌÁÎÎÙÅ ×ÙÛÅ ÚÁÍÅÞÁÎÉÑ, ÐÏËÁÖÉÔÅ, ÞÔÏ
ÐÏ ÌÀÂÏÊ ×ÙÞÉÓÌÉÍÏÊ ÆÕÎËÃÉÉ h (ÚÁÄÁÎÎÏÊ Ó×ÏÉÍ ÎÏÍÅÒÏÍ ÏÔÎÏÓÉÔÅÌØÎÏ
ÆÉËÓÉÒÏ×ÁÎÎÏÊ ÇÌÁ×ÎÏÊ ÕÎÉ×ÅÒÓÁÌØÎÏÊ ÆÕÎËÃÉÉ) ÍÏÖÎÏ ÜÆÆÅËÔÉ×ÎÏ ÕËÁ-
ÚÁÔØ ÂÅÓËÏÎÅÞÎÏ ÍÎÏÇÏ ÞÉÓÅÌ, ËÁÖÄÏÅ ÉÚ ËÏÔÏÒÙÈ ÌÉÂÏ ÂÕÄÅÔ ÎÅÐÏÄ×ÉÖ-
ÎÏÊ ÔÏÞËÏÊ ÄÌÑ ÆÕÎËÃÉÉ h, ÌÉÂÏ ÔÏÞËÏÊ, ÇÄÅ ÜÔÁ ÆÕÎËÃÉÑ ÎÅ ÏÐÒÅÄÅÌÅÎÁ.
3.3. îÅÐÏÄ×ÉÖÎÁÑ ÔÏÞËÁ ÄÌÑ ÐÅÒÅÞÉÓÌÉÍÙÈ ÍÎÏÖÅÓÔ×
÷Ó¾ ÓËÁÚÁÎÎÏÅ ÐÏÞÔÉ ÂÅÚ ÉÚÍÅÎÅÎÉÊ ÐÅÒÅÎÏÓÉÔÓÑ ÎÁ ÇÌÁ×ÎÙÅ ÎÕÍÅÒÁÃÉÉ
ÐÅÒÅÞÉÓÌÉÍÙÈ ÍÎÏÖÅÓÔ× (ÅÓÌÉ W ¡ ÇÌÁ×ÎÏÅ ÕÎÉ×ÅÒÓÁÌØÎÏÅ ÐÅÒÅÞÉÓÌÉÍÏÅ
ÍÎÏÖÅÓÔ×Ï, ÔÏ ×ÓÑËÁÑ ×ÙÞÉÓÌÉÍÁÑ ×ÓÀÄÕ ÏÐÒÅÄÅ̾ÎÎÁÑ ÆÕÎËÃÉÑ h ÉÍÅÅÔ
ÎÅÐÏÄ×ÉÖÎÕÀ ÔÏÞËÕ n, ÄÌÑ ËÏÔÏÒÏÊ W
n
= W
h(n)
).
÷ ÓÁÍÏÍ ÄÅÌÅ, ÅÓÌÉ W ¡ ÇÌÁ×ÎÏÅ ÕÎÉ×ÅÒÓÁÌØÎÏÅ ÐÅÒÅÞÉÓÌÉÍÏÅ ÍÎÏÖÅÓÔ-
×Ï, ÔÏ Ë ÏÔÎÏÛÅÎÉÀ ÜË×É×ÁÌÅÎÔÎÏÓÔÉ
a ≡ b ⇔ W
a
= W
b
ÐÒÉÍÅÎÉÍÏ ÒÁÓÓÕÖÄÅÎÉÅ ÉÚ ÄÏËÁÚÁÔÅÌØÓÔ×Á ÔÅÏÒÅÍÙ 65, ÐÏÓËÏÌØËÕ ÌÀÂÁÑ
×ÙÞÉÓÌÉÍÁÑ ÆÕÎËÃÉÑ f ÉÍÅÅÔ ×ÙÞÉÓÌÉÍÏÅ ×ÓÀÄÕ ÏÐÒÅÄÅ̾ÎÎÏÅ ≡-ÐÒÏÄÏÌ-
ÖÅÎÉÅ.
ðÒÏ×ÅÒÉÍ ÜÔÏ. äÌÑ ÜÔÏÇÏ ÒÁÓÓÍÏÔÒÉÍ ÍÎÏÖÅÓÔ×Ï
V = {hp, xi | f(p) ÏÐÒÅÄÅÌÅÎÏ É hf(p), xi ∈ W }.
ìÅÇËÏ ÐÏÎÑÔØ, ÞÔÏ ÜÔÏ ÍÎÏÖÅÓÔ×Ï ÐÅÒÅÞÉÓÌÉÍÏ (ÎÁÐÒÉÍÅÒ, ÏÎÏ ÅÓÔØ ÏÂÌÁÓÔØ
ÏÐÒÅÄÅÌÅÎÉÑ ×ÙÞÉÓÌÉÍÏÊ ÆÕÎËÃÉÉ hp, xi 7→ w(f(p), x), ÇÄÅ w ¡ ×ÙÞÉÓÌÉÍÁÑ
ÆÕÎËÃÉÑ Ó ÏÂÌÁÓÔØÀ ÏÐÒÅÄÅÌÅÎÉÑ W ). ðÒÉ ÜÔÏÍ V
p
= W
f(p)
, ÅÓÌÉ f(p) ÏÐÒÅ-
ÄÅÌÅÎÏ, É V
p
= ∅, ÅÓÌÉ f(p) ÎÅ ÏÐÒÅÄÅÌÅÎÏ. ÷ÓÐÏÍÉÎÁÑ, ÞÔÏ W Ñ×ÌÑÅÔÓÑ ÇÌÁ×-
ÎÙÍ ÕÎÉ×ÅÒÓÁÌØÎÙÍ ÍÎÏÖÅÓÔ×ÏÍ, ÍÙ ÎÁÈÏÄÉÍ ×ÓÀÄÕ ÏÐÒÅÄÅ̾ÎÎÕÀ ÆÕÎË-
ÃÉÀ s, ÄÌÑ ËÏÔÏÒÏÊ V
p
= W
s(p)
. ôÁËÉÍ ÏÂÒÁÚÏÍ, W
s(p)
= W
f(p)
ÄÌÑ ÔÅÈ p, ÄÌÑ
ËÏÔÏÒÙÈ f(p) ÏÐÒÅÄÅÌÅÎÏ, ÞÔÏ É ÔÒÅÂÏ×ÁÌÏÓØ.
úÁÄÁÞÁ 201. ðÕÓÔØ W ¡ ÇÌÁ×ÎÏÅ ÕÎÉ×ÅÒÓÁÌØÎÏÅ ÍÎÏÖÅÓÔ×Ï (ÄÌÑ ËÌÁÓ-
ÓÁ ×ÓÅÈ ÐÅÒÅÞÉÓÌÉÍÙÈ ÐÏÄÍÎÏÖÅÓÔ× ÎÁÔÕÒÁÌØÎÏÇÏ ÒÑÄÁ). (Á) ðÏËÁÖÉÔÅ,
ÞÔÏ ÎÁÊľÔÓÑ ÞÉÓÌÏ x, ÄÌÑ ËÏÔÏÒÏÇÏ W
x
= {x}. (Â) ðÏËÁÖÉÔÅ, ÞÔÏ ÎÁÊ-
ÄÕÔÓÑ ÒÁÚÌÉÞÎÙÅ ÞÉÓÌÁ x É y, ÄÌÑ ËÏÔÏÒÙÈ W
x
= {y} É W
y
= {x}.
§3. îÅÓËÏÌØËÏ ÚÁÍÅÞÁÎÉÊ                                                 173

ÔÁËÉÍ Ó×ÏÊÓÔ×ÏÍ: ÐÒÉ ËÁÖÄÏÍ p ÌÉÂÏ ÆÕÎËÃÉÑ hp ÎÅ ÏÐÒÅÄÅÌÅÎÁ × ÔÏÞËÅ n(p),
ÌÉÂÏ n(p) Ñ×ÌÑÅÔÓÑ ÎÅÐÏÄ×ÉÖÎÏÊ ÔÏÞËÏÊ ÆÕÎËÃÉÉ hp .
  úÁÄÁÞÁ 199. õÂÅÄÉÔÅÓØ, ÞÔÏ ÐÒÉ×ÅľÎÎÁÑ × ÄÏËÁÚÁÔÅÌØÓÔ×Å ÔÅÏÒÅ-
ÍÙ 68 ËÏÎÓÔÒÕËÃÉÑ ËÁË ÒÁÚ É ÄÁ¾Ô ÆÕÎËÃÉÀ n(p) Ó ÔÁËÉÍ Ó×ÏÊÓÔ×ÏÍ.
   úÁÄÁÞÁ 200. ïÂßÅÄÉÎÑÑ ÓÄÅÌÁÎÎÙÅ ×ÙÛÅ ÚÁÍÅÞÁÎÉÑ, ÐÏËÁÖÉÔÅ, ÞÔÏ
ÐÏ ÌÀÂÏÊ ×ÙÞÉÓÌÉÍÏÊ ÆÕÎËÃÉÉ h (ÚÁÄÁÎÎÏÊ Ó×ÏÉÍ ÎÏÍÅÒÏÍ ÏÔÎÏÓÉÔÅÌØÎÏ
ÆÉËÓÉÒÏ×ÁÎÎÏÊ ÇÌÁ×ÎÏÊ ÕÎÉ×ÅÒÓÁÌØÎÏÊ ÆÕÎËÃÉÉ) ÍÏÖÎÏ ÜÆÆÅËÔÉ×ÎÏ ÕËÁ-
ÚÁÔØ ÂÅÓËÏÎÅÞÎÏ ÍÎÏÇÏ ÞÉÓÅÌ, ËÁÖÄÏÅ ÉÚ ËÏÔÏÒÙÈ ÌÉÂÏ ÂÕÄÅÔ ÎÅÐÏÄ×ÉÖ-
ÎÏÊ ÔÏÞËÏÊ ÄÌÑ ÆÕÎËÃÉÉ h, ÌÉÂÏ ÔÏÞËÏÊ, ÇÄÅ ÜÔÁ ÆÕÎËÃÉÑ ÎÅ ÏÐÒÅÄÅÌÅÎÁ.

3.3. îÅÐÏÄ×ÉÖÎÁÑ ÔÏÞËÁ ÄÌÑ ÐÅÒÅÞÉÓÌÉÍÙÈ ÍÎÏÖÅÓÔ×

   ÷Ó¾ ÓËÁÚÁÎÎÏÅ ÐÏÞÔÉ ÂÅÚ ÉÚÍÅÎÅÎÉÊ ÐÅÒÅÎÏÓÉÔÓÑ ÎÁ ÇÌÁ×ÎÙÅ ÎÕÍÅÒÁÃÉÉ
ÐÅÒÅÞÉÓÌÉÍÙÈ ÍÎÏÖÅÓÔ× (ÅÓÌÉ W ¡ ÇÌÁ×ÎÏÅ ÕÎÉ×ÅÒÓÁÌØÎÏÅ ÐÅÒÅÞÉÓÌÉÍÏÅ
ÍÎÏÖÅÓÔ×Ï, ÔÏ ×ÓÑËÁÑ ×ÙÞÉÓÌÉÍÁÑ ×ÓÀÄÕ ÏÐÒÅÄÅ̾ÎÎÁÑ ÆÕÎËÃÉÑ h ÉÍÅÅÔ
ÎÅÐÏÄ×ÉÖÎÕÀ ÔÏÞËÕ n, ÄÌÑ ËÏÔÏÒÏÊ Wn = Wh(n) ).
   ÷ ÓÁÍÏÍ ÄÅÌÅ, ÅÓÌÉ W ¡ ÇÌÁ×ÎÏÅ ÕÎÉ×ÅÒÓÁÌØÎÏÅ ÐÅÒÅÞÉÓÌÉÍÏÅ ÍÎÏÖÅÓÔ-
×Ï, ÔÏ Ë ÏÔÎÏÛÅÎÉÀ ÜË×É×ÁÌÅÎÔÎÏÓÔÉ
                             a ≡ b ⇔ W a = Wb
ÐÒÉÍÅÎÉÍÏ ÒÁÓÓÕÖÄÅÎÉÅ ÉÚ ÄÏËÁÚÁÔÅÌØÓÔ×Á ÔÅÏÒÅÍÙ 65, ÐÏÓËÏÌØËÕ ÌÀÂÁÑ
×ÙÞÉÓÌÉÍÁÑ ÆÕÎËÃÉÑ f ÉÍÅÅÔ ×ÙÞÉÓÌÉÍÏÅ ×ÓÀÄÕ ÏÐÒÅÄÅ̾ÎÎÏÅ ≡-ÐÒÏÄÏÌ-
ÖÅÎÉÅ.
  ðÒÏ×ÅÒÉÍ ÜÔÏ. äÌÑ ÜÔÏÇÏ ÒÁÓÓÍÏÔÒÉÍ ÍÎÏÖÅÓÔ×Ï
              V = {hp, xi | f (p) ÏÐÒÅÄÅÌÅÎÏ É hf (p), xi ∈ W }.
ìÅÇËÏ ÐÏÎÑÔØ, ÞÔÏ ÜÔÏ ÍÎÏÖÅÓÔ×Ï ÐÅÒÅÞÉÓÌÉÍÏ (ÎÁÐÒÉÍÅÒ, ÏÎÏ ÅÓÔØ ÏÂÌÁÓÔØ
ÏÐÒÅÄÅÌÅÎÉÑ ×ÙÞÉÓÌÉÍÏÊ ÆÕÎËÃÉÉ hp, xi 7→ w(f (p), x), ÇÄÅ w ¡ ×ÙÞÉÓÌÉÍÁÑ
ÆÕÎËÃÉÑ Ó ÏÂÌÁÓÔØÀ ÏÐÒÅÄÅÌÅÎÉÑ W ). ðÒÉ ÜÔÏÍ Vp = Wf (p), ÅÓÌÉ f (p) ÏÐÒÅ-
ÄÅÌÅÎÏ, É Vp = ∅, ÅÓÌÉ f (p) ÎÅ ÏÐÒÅÄÅÌÅÎÏ. ÷ÓÐÏÍÉÎÁÑ, ÞÔÏ W Ñ×ÌÑÅÔÓÑ ÇÌÁ×-
ÎÙÍ ÕÎÉ×ÅÒÓÁÌØÎÙÍ ÍÎÏÖÅÓÔ×ÏÍ, ÍÙ ÎÁÈÏÄÉÍ ×ÓÀÄÕ ÏÐÒÅÄÅ̾ÎÎÕÀ ÆÕÎË-
ÃÉÀ s, ÄÌÑ ËÏÔÏÒÏÊ Vp = Ws(p) . ôÁËÉÍ ÏÂÒÁÚÏÍ, Ws(p) = Wf (p) ÄÌÑ ÔÅÈ p, ÄÌÑ
ËÏÔÏÒÙÈ f (p) ÏÐÒÅÄÅÌÅÎÏ, ÞÔÏ É ÔÒÅÂÏ×ÁÌÏÓØ.
   úÁÄÁÞÁ 201. ðÕÓÔØ W ¡ ÇÌÁ×ÎÏÅ ÕÎÉ×ÅÒÓÁÌØÎÏÅ ÍÎÏÖÅÓÔ×Ï (ÄÌÑ ËÌÁÓ-
ÓÁ ×ÓÅÈ ÐÅÒÅÞÉÓÌÉÍÙÈ ÐÏÄÍÎÏÖÅÓÔ× ÎÁÔÕÒÁÌØÎÏÇÏ ÒÑÄÁ). (Á) ðÏËÁÖÉÔÅ,
ÞÔÏ ÎÁÊľÔÓÑ ÞÉÓÌÏ x, ÄÌÑ ËÏÔÏÒÏÇÏ Wx = {x}. (Â) ðÏËÁÖÉÔÅ, ÞÔÏ ÎÁÊ-
ÄÕÔÓÑ ÒÁÚÌÉÞÎÙÅ ÞÉÓÌÁ x É y, ÄÌÑ ËÏÔÏÒÙÈ Wx = {y} É Wy = {x}.

Страницы