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

UptoLike

ВУЗ: 

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

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

Рубрика: 

§3. ÷ÙÒÁÚÉÍÙÅ ÐÒÅÄÉËÁÔÙ 107
úÁÄÁÞÁ 135. äÏËÁÖÉÔÅ, ÞÔÏ ÐÅÒÅÓÅÞÅÎÉÅ, ÏÂßÅÄÉÎÅÎÉÅ É ÒÁÚÎÏÓÔØ
Ä×ÕÈ ×ÙÒÁÚÉÍÙÈ ÍÎÏÖÅÓÔ× Ñ×ÌÑÀÔÓÑ ×ÙÒÁÚÉÍÙÍÉ. äÏËÁÖÉÔÅ, ÞÔÏ ÐÒÏ-
ÅËÃÉÑ k-ÍÅÒÎÏÇÏ ×ÙÒÁÚÉÍÏÇÏ ÍÎÏÖÅÓÔ×Á ×ÄÏÌØ ÏÄÎÏÊ ÉÚ ¥ÏÓÅÊ ËÏÏÒÄÉÎÁÔ¥
Ñ×ÌÑÅÔÓÑ (k − 1)-ÍÅÒÎÙÍ ×ÙÒÁÚÉÍÙÍ ÍÎÏÖÅÓÔ×ÏÍ.
ðÒÉÍÅÒ. óÉÇÎÁÔÕÒÁ ÓÏÄÅÒÖÉÔ ÏÄÎÏÍÅÓÔÎÙÊ ÆÕÎËÃÉÏÎÁÌØÎÙÊ ÓÉÍ×ÏÌ S
É Ä×ÕÍÅÓÔÎÙÊ ÐÒÅÄÉËÁÔÎÙÊ ÓÉÍ×ÏÌ ÒÁ×ÅÎÓÔ×Á (=). òÁÓÓÍÏÔÒÉÍ ÉÎÔÅÒÐÒÅ-
ÔÁÃÉÀ ÜÔÏÊ ÓÉÇÎÁÔÕÒÙ. ÷ ËÁÞÅÓÔ×Å ÎÏÓÉÔÅÌÑ ×ÙÂÅÒÅÍ ÎÁÔÕÒÁÌØÎÙÊ ÒÑÄ N.
óÉÍ×ÏÌ S ÂÕÄÅÔ ÏÂÏÚÎÁÞÁÔØ ÆÕÎËÃÉÀ ÐÒÉÂÁ×ÌÅÎÉÑ ÅÄÉÎÉÃÙ (ÍÏÖÎÏ ÓÞÉ-
ÔÁÔØ S ÓÏËÒÁÝÅÎÉÅÍ ÏÔ ÓÌÏ×Á successor ¡ ÐÏÓÌÅÄÏ×ÁÔÅÌØ). úÎÁË ÒÁ×ÅÎÓÔ×Á
ÉÎÔÅÒÐÒÅÔÉÒÕÅÔÓÑ ËÁË ÓÏ×ÐÁÄÅÎÉÅ ÜÌÅÍÅÎÔÏ×.
ìÅÇËÏ ÐÒÏ×ÅÒÉÔØ, ÞÔÏ ÏÄÎÏÍÅÓÔÎÙÊ ÐÒÅÄÉËÁÔ ¥ÂÙÔØ ÎÕ̾ͥ ×ÙÒÁÚÉÍ ×
ÜÔÏÊ ÉÎÔÅÒÐÒÅÔÁÃÉÉ, ÎÅÓÍÏÔÒÑ ÎÁ ÔÏ, ÞÔÏ ËÏÎÓÔÁÎÔÙ ÄÌÑ ÎÕÌÑ × ÓÉÇÎÁÔÕÒÅ
ÎÅ ÐÒÅÄÕÓÍÏÔÒÅÎÏ. ÷ ÓÁÍÏÍ ÄÅÌÅ, ÏÎ ×ÙÒÁÖÁÅÔÓÑ ÆÏÒÍÕÌÏÊ
¬∃y(x = S(y))
Ó ÅÄÉÎÓÔ×ÅÎÎÙÍ ÐÁÒÁÍÅÔÒÏÍ x.
åݾ ÐÒÏÝÅ ×ÙÒÁÚÉÔØ × ÜÔÏÊ ÓÉÇÎÁÔÕÒÅ Ä×ÕÍÅÓÔÎÙÊ ÐÒÅÄÉËÁÔ ¥ÂÙÔØ ÂÏÌØ-
ÛÅ ÎÁ 2¥, ÐÒÉ ÜÔÏÍ ÄÁÖÅ ÎÅ ÎÕÖÎÙ Ë×ÁÎÔÏÒÙ: y = S(S(x)).
ìÀÂÏÐÙÔÎÏ, ÞÔÏ ÕÖÅ × ÔÁËÏÊ ÐÒÏÓÔÏÊ ÓÉÔÕÁÃÉÉ ÍÏÖÎÏ ÓÆÏÒÍÕÌÉÒÏ×ÁÔØ
ÓÏÄÅÒÖÁÔÅÌØÎÕÀ ÚÁÄÁÞÕ: ×ÙÒÁÚÉÔØ ÐÒÅÄÉËÁÔ y = x + N, ÇÄÅ N ¡ ÂÏÌØÛÏÅ
ÞÉÓÌÏ (ÓËÁÖÅÍ, ÍÉÌÌÉÁÒÄ), Ó ÐÏÍÏÝØÀ ÓÕÝÅÓÔ×ÅÎÎÏ ÂÏÌÅÅ ËÏÒÏÔËÏÊ ÆÏÒÍÕ-
ÌÙ, ÞÅÍ y = S(S(. . . (S(x)) . . . )). ëÁË ÎÉ ÕÄÉ×ÉÔÅÌØÎÏ, ÜÔÏ ×ÐÏÌÎÅ ×ÏÚÍÏÖÎÏ,
É ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÕÀ ÆÏÒÍÕÌÕ ×ÐÏÌÎÅ ÍÏÖÎÏ ÕÍÅÓÔÉÔØ ÎÁ ÌÉÓÔÅ ÂÕÍÁÇÉ.
úÁÄÁÞÁ 136. äÏËÁÖÉÔÅ, ÞÔÏ ÐÒÅÄÉËÁÔ y = x + N ÍÏÖÎÏ ×ÙÒÁÚÉÔØ
ÆÏÒÍÕÌÏÊ ÕËÁÚÁÎÎÏÊ ÓÉÇÎÁÔÕÒÙ, ÄÌÉÎÁ ËÏÔÏÒÏÊ ÅÓÔØ O(log N). (õËÁÚÁÎÉÅ.
åÓÌÉ ÍÙ ÎÁÕÞÉÌÉÓØ ×ÙÒÁÖÁÔØ y = x + n, ÍÏÖÎÏ ×ÙÒÁÚÉÔØ y = x + 2n Ó
ÐÏÍÏÝØÀ ÆÏÒÍÕÌÙ
∃z ((z = x + n) ∧ (y = z + n))
(× ËÏÔÏÒÏÊ ÞÅÒÅÚ z = x + n É y = z + n ÏÂÏÚÎÁÞÅÎÙ ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÉÅ
ÆÏÒÍÕÌÙ). üÔÏ ÓÁÍÏ ÐÏ ÓÅÂÅ ÎÉÞÅÇÏ ÎÅ ÄÁ¾Ô, ÔÁË ËÁË ÄÌÉÎÁ ÆÏÒÍÕÌÙ Õ×Å-
ÌÉÞÉÌÁÓØ ×Ä×ÏÅ, ÎÏ ÍÏÖÎÏ ÉÓÐÏÌØÚÏ×ÁÔØ ÔÁËÏÊ ÔÒÀË:
∃z ∀u ∀v(((u = x ∧ v = z) ∨ (u = z ∧ v = y)) → (v = u + n)).
äÁÌÅÅ ÍÏÖÎÏ ×ÏÓÐÏÌØÚÏ×ÁÔØÓÑ ÚÁÐÉÓØÀ ÞÉÓÌÁ N × Ä×ÏÉÞÎÏÊ ÓÉÓÔÅÍÅ ÓÞÉ-
ÓÌÅÎÉÑ.)
íÏÖÎÏ ÄÏËÁÚÁÔØ, ÞÔÏ × ÜÔÏÊ ÓÉÇÎÁÔÕÒÅ Ë×ÁÎÔÏÒÙ ÐÏÞÔÉ ÎÅ Õ×ÅÌÉÞÉ×Á-
ÀÔ ÎÁÂÏÒ ×ÙÒÁÚÉÍÙÈ ÐÒÅÄÉËÁÔÏ×: ×ÓÑËÉÊ ×ÙÒÁÚÉÍÙÊ ÐÒÅÄÉËÁÔ ÂÕÄÅÔ ×ÙÒÁ-
ÖÁÔØÓÑ ÂÅÓË×ÁÎÔÏÒÎÏÊ ÆÏÒÍÕÌÏÊ (×ÏÚÍÏÖÎÏ, ÇÏÒÁÚÄÏ ÂÏÌÅÅ ÄÌÉÎÎÏÊ), ÅÓÌÉ
ÄÏÂÁ×ÉÔØ Ë ÓÉÇÎÁÔÕÒÅ ËÏÎÓÔÁÎÔÕ 0.
§3. ÷ÙÒÁÚÉÍÙÅ ÐÒÅÄÉËÁÔÙ                                                    107

   úÁÄÁÞÁ 135. äÏËÁÖÉÔÅ, ÞÔÏ ÐÅÒÅÓÅÞÅÎÉÅ, ÏÂßÅÄÉÎÅÎÉÅ É ÒÁÚÎÏÓÔØ
Ä×ÕÈ ×ÙÒÁÚÉÍÙÈ ÍÎÏÖÅÓÔ× Ñ×ÌÑÀÔÓÑ ×ÙÒÁÚÉÍÙÍÉ. äÏËÁÖÉÔÅ, ÞÔÏ ÐÒÏ-
ÅËÃÉÑ k-ÍÅÒÎÏÇÏ ×ÙÒÁÚÉÍÏÇÏ ÍÎÏÖÅÓÔ×Á ×ÄÏÌØ ÏÄÎÏÊ ÉÚ ¥ÏÓÅÊ ËÏÏÒÄÉÎÁÔ¥
Ñ×ÌÑÅÔÓÑ (k − 1)-ÍÅÒÎÙÍ ×ÙÒÁÚÉÍÙÍ ÍÎÏÖÅÓÔ×ÏÍ.
   ðÒÉÍÅÒ. óÉÇÎÁÔÕÒÁ ÓÏÄÅÒÖÉÔ ÏÄÎÏÍÅÓÔÎÙÊ ÆÕÎËÃÉÏÎÁÌØÎÙÊ ÓÉÍ×ÏÌ S
É Ä×ÕÍÅÓÔÎÙÊ ÐÒÅÄÉËÁÔÎÙÊ ÓÉÍ×ÏÌ ÒÁ×ÅÎÓÔ×Á (=). òÁÓÓÍÏÔÒÉÍ ÉÎÔÅÒÐÒÅ-
ÔÁÃÉÀ ÜÔÏÊ ÓÉÇÎÁÔÕÒÙ. ÷ ËÁÞÅÓÔ×Å ÎÏÓÉÔÅÌÑ ×ÙÂÅÒÅÍ ÎÁÔÕÒÁÌØÎÙÊ ÒÑÄ N.
óÉÍ×ÏÌ S ÂÕÄÅÔ ÏÂÏÚÎÁÞÁÔØ ÆÕÎËÃÉÀ ÐÒÉÂÁ×ÌÅÎÉÑ ÅÄÉÎÉÃÙ (ÍÏÖÎÏ ÓÞÉ-
ÔÁÔØ S ÓÏËÒÁÝÅÎÉÅÍ ÏÔ ÓÌÏ×Á successor ¡ ÐÏÓÌÅÄÏ×ÁÔÅÌØ). úÎÁË ÒÁ×ÅÎÓÔ×Á
ÉÎÔÅÒÐÒÅÔÉÒÕÅÔÓÑ ËÁË ÓÏ×ÐÁÄÅÎÉÅ ÜÌÅÍÅÎÔÏ×.
   ìÅÇËÏ ÐÒÏ×ÅÒÉÔØ, ÞÔÏ ÏÄÎÏÍÅÓÔÎÙÊ ÐÒÅÄÉËÁÔ ¥ÂÙÔØ ÎÕ̾ͥ ×ÙÒÁÚÉÍ ×
ÜÔÏÊ ÉÎÔÅÒÐÒÅÔÁÃÉÉ, ÎÅÓÍÏÔÒÑ ÎÁ ÔÏ, ÞÔÏ ËÏÎÓÔÁÎÔÙ ÄÌÑ ÎÕÌÑ × ÓÉÇÎÁÔÕÒÅ
ÎÅ ÐÒÅÄÕÓÍÏÔÒÅÎÏ. ÷ ÓÁÍÏÍ ÄÅÌÅ, ÏÎ ×ÙÒÁÖÁÅÔÓÑ ÆÏÒÍÕÌÏÊ
                                ¬∃y(x = S(y))
Ó ÅÄÉÎÓÔ×ÅÎÎÙÍ ÐÁÒÁÍÅÔÒÏÍ x.
   åݾ ÐÒÏÝÅ ×ÙÒÁÚÉÔØ × ÜÔÏÊ ÓÉÇÎÁÔÕÒÅ Ä×ÕÍÅÓÔÎÙÊ ÐÒÅÄÉËÁÔ ¥ÂÙÔØ ÂÏÌØ-
ÛÅ ÎÁ 2¥, ÐÒÉ ÜÔÏÍ ÄÁÖÅ ÎÅ ÎÕÖÎÙ Ë×ÁÎÔÏÒÙ: y = S(S(x)).
   ìÀÂÏÐÙÔÎÏ, ÞÔÏ ÕÖÅ × ÔÁËÏÊ ÐÒÏÓÔÏÊ ÓÉÔÕÁÃÉÉ ÍÏÖÎÏ ÓÆÏÒÍÕÌÉÒÏ×ÁÔØ
ÓÏÄÅÒÖÁÔÅÌØÎÕÀ ÚÁÄÁÞÕ: ×ÙÒÁÚÉÔØ ÐÒÅÄÉËÁÔ y = x + N, ÇÄÅ N ¡ ÂÏÌØÛÏÅ
ÞÉÓÌÏ (ÓËÁÖÅÍ, ÍÉÌÌÉÁÒÄ), Ó ÐÏÍÏÝØÀ ÓÕÝÅÓÔ×ÅÎÎÏ ÂÏÌÅÅ ËÏÒÏÔËÏÊ ÆÏÒÍÕ-
ÌÙ, ÞÅÍ y = S(S(. . . (S(x)) . . . )). ëÁË ÎÉ ÕÄÉ×ÉÔÅÌØÎÏ, ÜÔÏ ×ÐÏÌÎÅ ×ÏÚÍÏÖÎÏ,
É ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÕÀ ÆÏÒÍÕÌÕ ×ÐÏÌÎÅ ÍÏÖÎÏ ÕÍÅÓÔÉÔØ ÎÁ ÌÉÓÔÅ ÂÕÍÁÇÉ.
   úÁÄÁÞÁ 136. äÏËÁÖÉÔÅ, ÞÔÏ ÐÒÅÄÉËÁÔ y = x + N ÍÏÖÎÏ ×ÙÒÁÚÉÔØ
ÆÏÒÍÕÌÏÊ ÕËÁÚÁÎÎÏÊ ÓÉÇÎÁÔÕÒÙ, ÄÌÉÎÁ ËÏÔÏÒÏÊ ÅÓÔØ O(log N). (õËÁÚÁÎÉÅ.
åÓÌÉ ÍÙ ÎÁÕÞÉÌÉÓØ ×ÙÒÁÖÁÔØ y = x + n, ÍÏÖÎÏ ×ÙÒÁÚÉÔØ y = x + 2n Ó
ÐÏÍÏÝØÀ ÆÏÒÍÕÌÙ
                      ∃z ((z = x + n) ∧ (y = z + n))
(× ËÏÔÏÒÏÊ ÞÅÒÅÚ z = x + n É y = z + n ÏÂÏÚÎÁÞÅÎÙ ÓÏÏÔ×ÅÔÓÔ×ÕÀÝÉÅ
ÆÏÒÍÕÌÙ). üÔÏ ÓÁÍÏ ÐÏ ÓÅÂÅ ÎÉÞÅÇÏ ÎÅ ÄÁ¾Ô, ÔÁË ËÁË ÄÌÉÎÁ ÆÏÒÍÕÌÙ Õ×Å-
ÌÉÞÉÌÁÓØ ×Ä×ÏÅ, ÎÏ ÍÏÖÎÏ ÉÓÐÏÌØÚÏ×ÁÔØ ÔÁËÏÊ ÔÒÀË:
        ∃z ∀u ∀v(((u = x ∧ v = z) ∨ (u = z ∧ v = y)) → (v = u + n)).
äÁÌÅÅ ÍÏÖÎÏ ×ÏÓÐÏÌØÚÏ×ÁÔØÓÑ ÚÁÐÉÓØÀ ÞÉÓÌÁ N × Ä×ÏÉÞÎÏÊ ÓÉÓÔÅÍÅ ÓÞÉ-
ÓÌÅÎÉÑ.)
   íÏÖÎÏ ÄÏËÁÚÁÔØ, ÞÔÏ × ÜÔÏÊ ÓÉÇÎÁÔÕÒÅ Ë×ÁÎÔÏÒÙ ÐÏÞÔÉ ÎÅ Õ×ÅÌÉÞÉ×Á-
ÀÔ ÎÁÂÏÒ ×ÙÒÁÚÉÍÙÈ ÐÒÅÄÉËÁÔÏ×: ×ÓÑËÉÊ ×ÙÒÁÚÉÍÙÊ ÐÒÅÄÉËÁÔ ÂÕÄÅÔ ×ÙÒÁ-
ÖÁÔØÓÑ ÂÅÓË×ÁÎÔÏÒÎÏÊ ÆÏÒÍÕÌÏÊ (×ÏÚÍÏÖÎÏ, ÇÏÒÁÚÄÏ ÂÏÌÅÅ ÄÌÉÎÎÏÊ), ÅÓÌÉ
ÄÏÂÁ×ÉÔØ Ë ÓÉÇÎÁÔÕÒÅ ËÏÎÓÔÁÎÔÕ 0.

Страницы