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

UptoLike

ВУЗ: 

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

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

Рубрика: 

§5. îÅ×ÙÒÁÚÉÍÙÅ ÐÒÅÄÉËÁÔÙ: Á×ÔÏÍÏÒÆÉÚÍÙ 115
ÉÞÅÓËÉÍ ÉÌÉ ÔÒÁÎÓÃÅÎÄÅÎÔÎÙÍ. ÷ ÐÅÒ×ÏÍ ÓÌÕÞÁÅ ÒÁÓÓÍÏÔÒÉÍ ÍÎÏÇÏ-
ÞÌÅÎ ÉÚ Q[x] ÍÉÎÉÍÁÌØÎÏÊ ÓÔÅÐÅÎÉ, ÏÂÒÁÝÁÀÝÉÊÓÑ × 0 × ÔÏÞËÅ γ; ÐÏ
ÐÒÅÄÐÏÌÏÖÅÎÉÀ ÏÎ ÉÍÅÅÔ ÓÔÅÐÅÎØ ÂÏÌØÛÅ 1 É ÐÏÔÏÍÕ ÉÍÅÅÔ ÄÒÕÇÏÊ ËÏ-
ÒÅÎØ γ
0
. ÷ ÁÌÇÅÂÒÅ ÄÏËÁÚÙ×ÁÅÔÓÑ, ÞÔÏ ÓÕÝÅÓÔ×ÕÅÔ Á×ÔÏÍÏÒÆÉÚÍ C ÎÁÄ
Q, ÐÅÒÅ×ÏÄÑÝÉÊ γ × γ
0
.
÷ ÓÌÕÞÁÅ ÔÒÁÎÓÃÅÎÄÅÎÔÎÏÇÏ γ ÍÙ ÉÓÐÏÌØÚÕÅÍ ÔÁËÏÊ ÆÁËÔ: ÄÌÑ ÌÀ-
ÂÙÈ ÔÒÁÎÓÃÅÎÄÅÎÔÎÙÈ γ
1
, γ
2
∈ C ÓÕÝÅÓÔ×ÕÅÔ Á×ÔÏÍÏÒÆÉÚÍ ÐÏÌÑ C ÎÁÄ
Q, ËÏÔÏÒÙÊ ÐÅÒÅ×ÏÄÉÔ γ
1
× γ
2
.
ïÔÍÅÔÉÍ, ÞÔÏ ÄÌÑ ÐÏÌÑ R ×ÍÅÓÔÏ C ÔÁËÏÅ ÒÁÓÓÕÖÄÅÎÉÅ ÎÅ ÐÒÏÈÏÄÉÔ,
ÔÁË ËÁË ÜÔÏ ÐÏÌÅ ÎÅ ÉÍÅÅÔ ÎÅÔÒÉ×ÉÁÌØÎÙÈ Á×ÔÏÍÏÒÆÉÚÍÏ×. (ïÔÎÏÛÅ-
ÎÉÅ ÐÏÒÑÄËÁ ×ÙÒÁÚÉÍÏ: ÐÏÌÏÖÉÔÅÌØÎÙÅ ÞÉÓÌÁ ÓÕÔØ Ë×ÁÄÒÁÔÙ, ÐÏÜÔÏÍÕ
ÌÀÂÏÊ Á×ÔÏÍÏÒÆÉÚÍ ÓÏÈÒÁÎÑÅÔ ÐÏÒÑÄÏË. ðÏÓËÏÌØËÕ Á×ÔÏÍÏÒÆÉÚÍ ÏÓÔÁ-
×ÌÑÅÔ ÎÁ ÍÅÓÔÅ ×ÓÅ ÒÁÃÉÏÎÁÌØÎÙÅ ÞÉÓÌÁ, ÏÎ ÄÏÌÖÅÎ ÂÙÔØ ÔÏÖÄÅÓÔ×ÅÎ-
ÎÙÍ.)
(÷ ÜÔÏÍ ÓÌÕÞÁÅ ÐÒÅÄÉËÁÔ x = γ ×ÙÒÁÚÉÍ ÔÏÇÄÁ É ÔÏÌØËÏ ÔÏÇÄÁ,
ËÏÇÄÁ γ ¡ ÁÌÇÅÂÒÁÉÞÅÓËÏÅ ÞÉÓÌÏ.)
úÁÄÁÞÁ 148. ðÏËÁÖÉÔÅ, ÞÔÏ ÐÒÅÄÉËÁÔ y = x + 1 ÎÅ×ÙÒÁÚÉÍ × ÉÎÔÅÒ-
ÐÒÅÔÁÃÉÉ (Z, =, f), ÇÄÅ f ¡ ÏÄÎÏÍÅÓÔÎÁÑ ÆÕÎËÃÉÑ x 7→ (x + 2).
úÁÄÁÞÁ 149. ðÏËÁÖÉÔÅ, ÞÔÏ ÐÒÅÄÉËÁÔ x = 2 ÎÅ×ÙÒÁÚÉÍ × ÍÎÏÖÅÓÔ×Å
ÃÅÌÙÈ ÐÏÌÏÖÉÔÅÌØÎÙÈ ÞÉÓÅÌ Ó ÐÒÅÄÉËÁÔÁÍÉ ÒÁ×ÅÎÓÔ×Á É ¥x ÄÅÌÉÔ y¥.
§5. îÅ×ÙÒÁÚÉÍÙÅ ÐÒÅÄÉËÁÔÙ: Á×ÔÏÍÏÒÆÉÚÍÙ                           115

    ÉÞÅÓËÉÍ ÉÌÉ ÔÒÁÎÓÃÅÎÄÅÎÔÎÙÍ. ÷ ÐÅÒ×ÏÍ ÓÌÕÞÁÅ ÒÁÓÓÍÏÔÒÉÍ ÍÎÏÇÏ-
    ÞÌÅÎ ÉÚ Q[x] ÍÉÎÉÍÁÌØÎÏÊ ÓÔÅÐÅÎÉ, ÏÂÒÁÝÁÀÝÉÊÓÑ × 0 × ÔÏÞËÅ γ; ÐÏ
    ÐÒÅÄÐÏÌÏÖÅÎÉÀ ÏÎ ÉÍÅÅÔ ÓÔÅÐÅÎØ ÂÏÌØÛÅ 1 É ÐÏÔÏÍÕ ÉÍÅÅÔ ÄÒÕÇÏÊ ËÏ-
    ÒÅÎØ γ 0. ÷ ÁÌÇÅÂÒÅ ÄÏËÁÚÙ×ÁÅÔÓÑ, ÞÔÏ ÓÕÝÅÓÔ×ÕÅÔ Á×ÔÏÍÏÒÆÉÚÍ C ÎÁÄ
    Q, ÐÅÒÅ×ÏÄÑÝÉÊ γ × γ 0.
       ÷ ÓÌÕÞÁÅ ÔÒÁÎÓÃÅÎÄÅÎÔÎÏÇÏ γ ÍÙ ÉÓÐÏÌØÚÕÅÍ ÔÁËÏÊ ÆÁËÔ: ÄÌÑ ÌÀ-
    ÂÙÈ ÔÒÁÎÓÃÅÎÄÅÎÔÎÙÈ γ1 , γ2 ∈ C ÓÕÝÅÓÔ×ÕÅÔ Á×ÔÏÍÏÒÆÉÚÍ ÐÏÌÑ C ÎÁÄ
    Q, ËÏÔÏÒÙÊ ÐÅÒÅ×ÏÄÉÔ γ1 × γ2.
       ïÔÍÅÔÉÍ, ÞÔÏ ÄÌÑ ÐÏÌÑ R ×ÍÅÓÔÏ C ÔÁËÏÅ ÒÁÓÓÕÖÄÅÎÉÅ ÎÅ ÐÒÏÈÏÄÉÔ,
    ÔÁË ËÁË ÜÔÏ ÐÏÌÅ ÎÅ ÉÍÅÅÔ ÎÅÔÒÉ×ÉÁÌØÎÙÈ Á×ÔÏÍÏÒÆÉÚÍÏ×. (ïÔÎÏÛÅ-
    ÎÉÅ ÐÏÒÑÄËÁ ×ÙÒÁÚÉÍÏ: ÐÏÌÏÖÉÔÅÌØÎÙÅ ÞÉÓÌÁ ÓÕÔØ Ë×ÁÄÒÁÔÙ, ÐÏÜÔÏÍÕ
    ÌÀÂÏÊ Á×ÔÏÍÏÒÆÉÚÍ ÓÏÈÒÁÎÑÅÔ ÐÏÒÑÄÏË. ðÏÓËÏÌØËÕ Á×ÔÏÍÏÒÆÉÚÍ ÏÓÔÁ-
    ×ÌÑÅÔ ÎÁ ÍÅÓÔÅ ×ÓÅ ÒÁÃÉÏÎÁÌØÎÙÅ ÞÉÓÌÁ, ÏÎ ÄÏÌÖÅÎ ÂÙÔØ ÔÏÖÄÅÓÔ×ÅÎ-
    ÎÙÍ.)
       (÷ ÜÔÏÍ ÓÌÕÞÁÅ ÐÒÅÄÉËÁÔ x = γ ×ÙÒÁÚÉÍ ÔÏÇÄÁ É ÔÏÌØËÏ ÔÏÇÄÁ,
    ËÏÇÄÁ γ ¡ ÁÌÇÅÂÒÁÉÞÅÓËÏÅ ÞÉÓÌÏ.)
  úÁÄÁÞÁ 148. ðÏËÁÖÉÔÅ, ÞÔÏ ÐÒÅÄÉËÁÔ y = x + 1 ÎÅ×ÙÒÁÚÉÍ × ÉÎÔÅÒ-
ÐÒÅÔÁÃÉÉ (Z, =, f ), ÇÄÅ f ¡ ÏÄÎÏÍÅÓÔÎÁÑ ÆÕÎËÃÉÑ x 7→ (x + 2).
   úÁÄÁÞÁ 149. ðÏËÁÖÉÔÅ, ÞÔÏ ÐÒÅÄÉËÁÔ x = 2 ÎÅ×ÙÒÁÚÉÍ × ÍÎÏÖÅÓÔ×Å
ÃÅÌÙÈ ÐÏÌÏÖÉÔÅÌØÎÙÈ ÞÉÓÅÌ Ó ÐÒÅÄÉËÁÔÁÍÉ ÒÁ×ÅÎÓÔ×Á É ¥x ÄÅÌÉÔ y¥.

Страницы