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

UptoLike

ВУЗ: 

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

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

Рубрика: 

196 çÌÁ×Á XIII. òÅËÕÒÓÉ×ÎÙÅ ÆÕÎËÃÉÉ
ÏÐÒÅÄÅÌÉÔØ ÔÁË:
x
‘
− 0 = x; (7)
x
‘
− (y + 1) = (x
‘
− y)
‘
− 1. (8)
§3. ðÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÙÅ ÍÎÏÖÅÓÔ×Á
âÕÄÅÍ ÎÁÚÙ×ÁÔØ ÍÎÏÖÅÓÔ×Ï ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÙÍ, ÅÓÌÉ ÅÇÏ ÈÁÒÁËÔÅ-
ÒÉÓÔÉÞÅÓËÁÑ ÆÕÎËÃÉÑ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÁ. (÷ÁÒÉÁÎÔ: ÅÓÌÉ ÏÎÏ Ñ×ÌÑÅÔÓÑ
ÍÎÏÖÅÓÔ×ÏÍ ÎÕÌÅÊ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÏÊ ÆÕÎËÃÉÉ; ÜÔÏ ÔÏ ÖÅ ÓÁÍÏÅ, ÔÁË
ËÁË ÍÏÖÎÏ ÓÄÅÌÁÔØ ÐÏÄÓÔÁÎÏ×ËÕ × ÆÕÎËÃÉÀ x 7→ 1
‘
− x.)
ðÅÒÅÓÅÞÅÎÉÅ É ÏÂßÅÄÉÎÅÎÉÅ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÙÈ ÍÎÏÖÅÓÔ× ÐÒÉÍÉ-
ÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÙ (ÓÌÏÖÉÍ ÉÌÉ ÐÅÒÅÍÎÏÖÉÍ ÆÕÎËÃÉÉ, ÍÎÏÖÅÓÔ×ÁÍÉ ÎÕÌÅÊ
ËÏÔÏÒÙÈ ÏÎÉ Ñ×ÌÑÀÔÓÑ). äÏÐÏÌÎÅÎÉÅ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÏÇÏ ÍÎÏÖÅÓÔ×Á
ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÏ. ïÔÏÖÄÅÓÔ×ÌÑÑ ÍÎÏÖÅÓÔ×Á ÓÏ Ó×ÏÊÓÔ×ÁÍÉ, ÍÏÖÎÏ
ÓËÁÚÁÔØ, ÞÔÏ ËÏÎßÀÎËÃÉÉ, ÄÉÚßÀÎËÃÉÉ É ÏÔÒÉÃÁÎÉÑ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×-
ÎÙÈ Ó×ÏÊÓÔ× ÂÕÄÕÔ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÙ.
ó×ÏÊÓÔ×Á x = y É x 6= y ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÙ (x = y ÔÏÇÄÁ É ÔÏÌØËÏ
ÔÏÇÄÁ, ËÏÇÄÁ (x
‘
− y) + (y
‘
− x) = 0).
æÕÎËÃÉÑ f(x), ÚÁÄÁÎÎÁÑ ÓÏÏÔÎÏÛÅÎÉÅÍ
f(x) = [ if (R(x)) g(x); else h(x); ],
ÂÕÄÅÔ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÏÊ, ÅÓÌÉ ÔÁËÏ×Ù ÆÕÎËÃÉÉ g É h É Ó×ÏÊÓÔ×Ï R.
÷ ÓÁÍÏÍ ÄÅÌÅ, f (x) ÍÏÖÎÏ ÚÁÐÉÓÁÔØ ËÁË r(x)g(x) + (1
‘
− r(x))h(x), ÇÄÅ r ¡
ÈÁÒÁËÔÅÒÉÓÔÉÞÅÓËÁÑ ÆÕÎËÃÉÑ Ó×ÏÊÓÔ×Á R.
ôÅÐÅÒØ ÍÏÖÎÏ ÚÁÐÉÓÁÔØ ÆÏÒÍÕÌÕ ÄÌÑ ÐÒÉÂÁ×ÌÅÎÉÑ ÅÄÉÎÉÃÙ ÐÏ ÍÏÄÕÌÀ n
(ÄÌÑ ÞÉÓÅÌ, ÍÅÎØÛÉÈ n):
x + 1 mod n = [ if (x + 1 == n) 0; else x + 1; ]
ðÏÓÌÅ ÜÔÏÇÏ ÆÕÎËÃÉÀ x mod n (ÏÓÔÁÔÏË ÏÔ ÄÅÌÅÎÉÑ ÎÁ n) ÍÏÖÎÏ ÏÐÒÅÄÅÌÉÔØ
ÒÅËÕÒÓÉ×ÎÏ:
0 mod n = 0; (1)
(x + 1) mod n = (x mod n) + 1 mod n. (2)
ðÏËÁÖÅÍ, ÞÔÏ ÏÇÒÁÎÉÞÅÎÎÙÅ Ë×ÁÎÔÏÒÙ, ÐÒÉÍÅξÎÎÙÅ Ë ÐÒÉÍÉÔÉ×ÎÏ ÒÅ-
ËÕÒÓÉ×ÎÙÍ Ó×ÏÊÓÔ×ÁÍ (ÍÎÏÖÅÓÔ×ÁÍ), ÄÁÀÔ ÓÎÏ×Á ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÙÅ
Ó×ÏÊÓÔ×Á. üÔÏ ÏÚÎÁÞÁÅÔ, ÎÁÐÒÉÍÅÒ, ÞÔÏ ÅÓÌÉ Ó×ÏÊÓÔ×Ï R(x, y) ÐÒÉÍÉÔÉ×ÎÏ
ÒÅËÕÒÓÉ×ÎÏ, ÔÏ Ó×ÏÊÓÔ×Á
S(x, z) = (∃y 6 z) R(x, y)
196                                     çÌÁ×Á XIII. òÅËÕÒÓÉ×ÎÙÅ ÆÕÎËÃÉÉ

ÏÐÒÅÄÅÌÉÔØ ÔÁË:
                             x−‘ 0 = x;                               (7)
                         ‘ (y + 1) = (x −
                        x−                   ‘ 1.
                                        ‘ y) −                        (8)


  §3. ðÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÙÅ ÍÎÏÖÅÓÔ×Á
   âÕÄÅÍ ÎÁÚÙ×ÁÔØ ÍÎÏÖÅÓÔ×Ï ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÙÍ, ÅÓÌÉ ÅÇÏ ÈÁÒÁËÔÅ-
ÒÉÓÔÉÞÅÓËÁÑ ÆÕÎËÃÉÑ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÁ. (÷ÁÒÉÁÎÔ: ÅÓÌÉ ÏÎÏ Ñ×ÌÑÅÔÓÑ
ÍÎÏÖÅÓÔ×ÏÍ ÎÕÌÅÊ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÏÊ ÆÕÎËÃÉÉ; ÜÔÏ ÔÏ ÖÅ ÓÁÍÏÅ, ÔÁË
ËÁË ÍÏÖÎÏ ÓÄÅÌÁÔØ ÐÏÄÓÔÁÎÏ×ËÕ × ÆÕÎËÃÉÀ x 7→ 1 −
                                               ‘ x.)
   ðÅÒÅÓÅÞÅÎÉÅ É ÏÂßÅÄÉÎÅÎÉÅ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÙÈ ÍÎÏÖÅÓÔ× ÐÒÉÍÉ-
ÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÙ (ÓÌÏÖÉÍ ÉÌÉ ÐÅÒÅÍÎÏÖÉÍ ÆÕÎËÃÉÉ, ÍÎÏÖÅÓÔ×ÁÍÉ ÎÕÌÅÊ
ËÏÔÏÒÙÈ ÏÎÉ Ñ×ÌÑÀÔÓÑ). äÏÐÏÌÎÅÎÉÅ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÏÇÏ ÍÎÏÖÅÓÔ×Á
ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÏ. ïÔÏÖÄÅÓÔ×ÌÑÑ ÍÎÏÖÅÓÔ×Á ÓÏ Ó×ÏÊÓÔ×ÁÍÉ, ÍÏÖÎÏ
ÓËÁÚÁÔØ, ÞÔÏ ËÏÎßÀÎËÃÉÉ, ÄÉÚßÀÎËÃÉÉ É ÏÔÒÉÃÁÎÉÑ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×-
ÎÙÈ Ó×ÏÊÓÔ× ÂÕÄÕÔ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÙ.
   ó×ÏÊÓÔ×Á x = y É x 6= y ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÙ (x = y ÔÏÇÄÁ É ÔÏÌØËÏ
ÔÏÇÄÁ, ËÏÇÄÁ (x −
                ‘ y) + (y −
                          ‘ x) = 0).
   æÕÎËÃÉÑ f (x), ÚÁÄÁÎÎÁÑ ÓÏÏÔÎÏÛÅÎÉÅÍ
                   f (x) = [ if (R(x)) g(x); else h(x); ],
ÂÕÄÅÔ ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÏÊ, ÅÓÌÉ ÔÁËÏ×Ù ÆÕÎËÃÉÉ g É h É Ó×ÏÊÓÔ×Ï R.
÷ ÓÁÍÏÍ ÄÅÌÅ, f (x) ÍÏÖÎÏ ÚÁÐÉÓÁÔØ ËÁË r(x)g(x) + (1 −
                                                     ‘ r(x))h(x), ÇÄÅ r ¡
ÈÁÒÁËÔÅÒÉÓÔÉÞÅÓËÁÑ ÆÕÎËÃÉÑ Ó×ÏÊÓÔ×Á R.
   ôÅÐÅÒØ ÍÏÖÎÏ ÚÁÐÉÓÁÔØ ÆÏÒÍÕÌÕ ÄÌÑ ÐÒÉÂÁ×ÌÅÎÉÑ ÅÄÉÎÉÃÙ ÐÏ ÍÏÄÕÌÀ n
(ÄÌÑ ÞÉÓÅÌ, ÍÅÎØÛÉÈ n):
              x + 1 mod n = [ if (x + 1 == n) 0; else x + 1; ]
ðÏÓÌÅ ÜÔÏÇÏ ÆÕÎËÃÉÀ x mod n (ÏÓÔÁÔÏË ÏÔ ÄÅÌÅÎÉÑ ÎÁ n) ÍÏÖÎÏ ÏÐÒÅÄÅÌÉÔØ
ÒÅËÕÒÓÉ×ÎÏ:
                        0 mod n = 0;                                  (1)
                  (x + 1) mod n = (x mod n) + 1 mod n.                (2)
   ðÏËÁÖÅÍ, ÞÔÏ ÏÇÒÁÎÉÞÅÎÎÙÅ Ë×ÁÎÔÏÒÙ, ÐÒÉÍÅξÎÎÙÅ Ë ÐÒÉÍÉÔÉ×ÎÏ ÒÅ-
ËÕÒÓÉ×ÎÙÍ Ó×ÏÊÓÔ×ÁÍ (ÍÎÏÖÅÓÔ×ÁÍ), ÄÁÀÔ ÓÎÏ×Á ÐÒÉÍÉÔÉ×ÎÏ ÒÅËÕÒÓÉ×ÎÙÅ
Ó×ÏÊÓÔ×Á. üÔÏ ÏÚÎÁÞÁÅÔ, ÎÁÐÒÉÍÅÒ, ÞÔÏ ÅÓÌÉ Ó×ÏÊÓÔ×Ï R(x, y) ÐÒÉÍÉÔÉ×ÎÏ
ÒÅËÕÒÓÉ×ÎÏ, ÔÏ Ó×ÏÊÓÔ×Á
                        S(x, z) = (∃y 6 z) R(x, y)

Страницы