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

UptoLike

ВУЗ: 

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

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

Рубрика: 

34 çÌÁ×Á I. íÎÏÖÅÓÔ×Á É ÍÏÝÎÏÓÔÉ
÷ ÓÁÍÏÍ ÄÅÌÅ, ÐÕÓÔØ ÎÁÌÏÖÅÎÉÅ f : A → B ÓÕÝÅÓÔ×ÕÅÔ. äÌÑ ËÁÖÄÏÇÏ
ÜÌÅÍÅÎÔÁ b ∈ B ÎÁÊľÔÓÑ ÈÏÔÑ ÂÙ ÏÄÉÎ ÜÌÅÍÅÎÔ a ∈ A, ÄÌÑ ËÏÔÏÒÏÇÏ f(a) =
= b. ÷ÙÂÒÁ× ÐÏ ÏÄÎÏÍÕ ÔÁËÏÍÕ ÜÌÅÍÅÎÔÕ, ÍÙ ÐÏÌÕÞÉÍ ÐÏÄÍÎÏÖÅÓÔ×Ï A
0
⊂ A,
ËÏÔÏÒÏÅ ÎÁÈÏÄÉÔÓÑ ×Ï ×ÚÁÉÍÎÏ ÏÄÎÏÚÎÁÞÎÏÍ ÓÏÏÔ×ÅÔÓÔ×ÉÉ Ó ÍÎÏÖÅÓÔ×ÏÍ B.
(úÄÅÓØ ÓÎÏ×Á ÉÓÐÏÌØÚÕÅÔÓÑ ÁËÓÉÏÍÁ ×ÙÂÏÒÁ, Ï ËÏÔÏÒÏÊ ÍÙ ÇÏ×ÏÒÉÌÉ ÎÁ Ó. 15.)
÷ ÏÂÒÁÔÎÕÀ ÓÔÏÒÏÎÕ: ÅÓÌÉ ËÁËÏÅ-ÔÏ ÐÏÄÍÎÏÖÅÓÔ×Ï A
0
ÍÎÏÖÅÓÔ×Á A ÒÁ×-
ÎÏÍÏÝÎÏ ÍÎÏÖÅÓÔ×Õ B É ÉÍÅÅÔÓÑ ÂÉÅËÃÉÑ g : A
0
→ B, ÔÏ ÎÁÌÏÖÅÎÉÅ A ÎÁ B
ÍÏÖÎÏ ÐÏÌÕÞÉÔØ, ÄÏÏÐÒÅÄÅÌÉ× ÜÔÕ ÂÉÅËÃÉÀ ÎÁ ÜÌÅÍÅÎÔÁÈ ×ÎÅ A
0
ËÁËÉÍ ÕÇÏÄ-
ÎÏ ÏÂÒÁÚÏÍ.
úÁÄÁÞÁ 56. îÁÊÄÉÔÅ ÏÛÉÂËÕ × ÜÔÏÍ ÒÁÓÓÕÖÄÅÎÉÉ, ÎÅ ÞÉÔÁÑ ÄÁÌØÛÅ.
îÁ ÓÁÍÏÍ ÄÅÌÅ ÔÁËÏÅ ÐÒÏÄÏÌÖÅÎÉÅ ×ÏÚÍÏÖÎÏ, ÔÏÌØËÏ ÅÓÌÉ B ÎÅÐÕÓÔÏ, ÔÁË
ÞÔÏ ÐÒÁ×ÉÌØÎÏÅ ÕÔ×ÅÒÖÄÅÎÉÅ Ú×ÕÞÉÔ ÔÁË: ÎÁÌÏÖÅÎÉÅ A ÎÁ B ÓÕÝÅÓÔ×ÕÅÔ
ÔÏÌØËÏ É ÔÏÌØËÏ ÔÏÇÄÁ, ËÏÇÄÁ B ÎÅÐÕÓÔÏ É ÒÁ×ÎÏÍÏÝÎÏ ÎÅËÏÔÏÒÏÍÕ ÐÏÄÍÎÏ-
ÖÅÓÔ×Õ A, ÉÌÉ ËÏÇÄÁ ÏÂÁ ÍÎÏÖÅÓÔ×Á ÐÕÓÔÙ.
÷ ÎÁÛÅÍ ÉÚÌÏÖÅÎÉÉ ÏÓÔÁ¾ÔÓÑ Åݾ ÏÄÉÎ ÎÅ ×ÐÏÌÎÅ ÐÏÎÑÔÎÙÊ ÍÏÍÅÎÔ: ÞÔÏ
ÔÁËÏÅ ÕÐÏÒÑÄÏÞÅÎÎÁÑ ÐÁÒÁ? îÅÆÏÒÍÁÌØÎÏ ÇÏ×ÏÒÑ, ÜÔÏ ÓÐÏÓÏ ÉÚ Ä×ÕÈ ÏÂßÅË-
ÔÏ× x É y ÏÂÒÁÚÏ×ÁÔØ ÏÄÉÎ ÏÂßÅËÔ hx, yi, ÐÒÉÞ¾Í ÜÔÏÔ ÓÐÏÓÏ ÏÂÌÁÄÁÅÔ ÔÁËÉÍ
Ó×ÏÊÓÔ×ÏÍ:
hx
1
, y
1
i = hx
2
, y
2
i ⇔ x
1
= x
2
É y
1
= y
2
.
÷ ÐÒÉÎÃÉÐÅ, ÍÏÖÎÏ ÔÁË É ÓÞÉÔÁÔØ ÐÏÎÑÔÉÅ ÕÐÏÒÑÄÏÞÅÎÎÏÊ ÐÁÒÙ ÎÅÏÐÒÅÄÅ-
ÌÑÅÍÙÍ, Á ÜÔÏ Ó×ÏÊÓÔ×Ï ¡ ÁËÓÉÏÍÏÊ. ïÄÎÁËÏ ÐÒÉ ÆÏÒÍÁÌØÎÏÍ ÐÏÓÔÒÏÅÎÉÉ
ÔÅÏÒÉÉ ÍÎÏÖÅÓÔ× ÕÄÏÂÎÏ ÉÓÐÏÌØÚÏ×ÁÔØ ÔÒÀË, ÐÒÉÄÕÍÁÎÎÙÊ ÐÏÌØÓËÉÍ ÍÁ-
ÔÅÍÁÔÉËÏÍ ëÕÒÁÔÏ×ÓËÉÍ, É ÉÚÂÅÖÁÔØ ÐÏÑ×ÌÅÎÉÑ ÏÔÄÅÌØÎÏÇÏ ÐÏÎÑÔÉÑ ÕÐÏÒÑ-
ÄÏÞÅÎÎÏÊ ÐÁÒÙ. (îÁÐÏÍÎÉÍ, ÞÔÏ {x} ÏÂÏÚÎÁÞÁÅÔ ÍÎÏÖÅÓÔ×Ï, ÅÄÉÎÓÔ×ÅÎÎÙÍ
ÜÌÅÍÅÎÔÏÍ ËÏÔÏÒÏÇÏ Ñ×ÌÑÅÔÓÑ x, Á {x, y} ÏÂÏÚÎÁÞÁÅÔ ÍÎÏÖÅÓÔ×Ï, ËÏÔÏÒÏÅ ÓÏ-
ÄÅÒÖÉÔ x É y É ÎÅ ÓÏÄÅÒÖÉÔ ÄÒÕÇÉÈ ÜÌÅÍÅÎÔÏ×. ôÅÍ ÓÁÍÙÍ {x, y} = {x} =
= {y}, ÅÓÌÉ x = y.)
ôÅÏÒÅÍÁ 9 (õÐÏÒÑÄÏÞÅÎÎÁÑ ÐÁÒÁ ÐÏ ëÕÒÁÔÏ×ÓËÏÍÕ). ïÐÒÅÄÅÌÉÍ hx, yi
ËÁË {{x}, {x, y}}. ôÏÇÄÁ ×ÙÐÏÌÎÅÎÏ ÕËÁÚÁÎÎÏÅ ×ÙÛÅ Ó×ÏÊÓÔ×Ï:
hx
1
, y
1
i = hx
2
, y
2
i ⇔ x
1
= x
2
É y
1
= y
2
.
äÏËÁÚÁÔÅÌØÓÔ×Ï. ðÕÓÔØ hx
1
, y
1
i = hx
2
, y
2
i. ðÏ ÏÐÒÅÄÅÌÅÎÉÀ ÜÔÏ ÏÚÎÁÞÁÅÔ,
ÞÔÏ
{{x
1
}, {x
1
, y
1
}} = {{x
2
}, {x
2
, y
2
}}.
ôÅÐÅÒØ ÎÕÖÎÏ ÁËËÕÒÁÔÎÏ ÒÁÚÏÂÒÁÔØ ÓÌÕÞÁÉ (ÎÅ ÐÕÔÁÑ ÐÒÉ ÜÔÏÍ x Ó {x}).
üÔÏ ÕÄÏÂÎÏ ÄÅÌÁÔØ × ÓÌÅÄÕÀÝÅÍ ÐÏÒÑÄËÅ. ðÕÓÔØ ÓÎÁÞÁÌÁ x
1
6= y
1
. ôÏÇÄÁ
ÍÎÏÖÅÓÔ×Ï {x
1
, y
1
} ÓÏÓÔÏÉÔ ÉÚ Ä×ÕÈ ÜÌÅÍÅÎÔÏ×. òÁÚ ÏÎÏ ÐÒÉÎÁÄÌÅÖÉÔ ÌÅ×ÏÊ
ÞÁÓÔÉ ÒÁ×ÅÎÓÔ×Á, ÔÏ ÐÒÉÎÁÄÌÅÖÉÔ É ÐÒÁ×ÏÊ. úÎÁÞÉÔ, ÏÎÏ ÒÁ×ÎÏ ÌÉÂÏ {x
2
},
34                                        çÌÁ×Á I. íÎÏÖÅÓÔ×Á É ÍÏÝÎÏÓÔÉ

   ÷ ÓÁÍÏÍ ÄÅÌÅ, ÐÕÓÔØ ÎÁÌÏÖÅÎÉÅ f : A → B ÓÕÝÅÓÔ×ÕÅÔ. äÌÑ ËÁÖÄÏÇÏ
ÜÌÅÍÅÎÔÁ b ∈ B ÎÁÊľÔÓÑ ÈÏÔÑ ÂÙ ÏÄÉÎ ÜÌÅÍÅÎÔ a ∈ A, ÄÌÑ ËÏÔÏÒÏÇÏ f (a) =
= b. ÷ÙÂÒÁ× ÐÏ ÏÄÎÏÍÕ ÔÁËÏÍÕ ÜÌÅÍÅÎÔÕ, ÍÙ ÐÏÌÕÞÉÍ ÐÏÄÍÎÏÖÅÓÔ×Ï A0 ⊂ A,
ËÏÔÏÒÏÅ ÎÁÈÏÄÉÔÓÑ ×Ï ×ÚÁÉÍÎÏ ÏÄÎÏÚÎÁÞÎÏÍ ÓÏÏÔ×ÅÔÓÔ×ÉÉ Ó ÍÎÏÖÅÓÔ×ÏÍ B.
(úÄÅÓØ ÓÎÏ×Á ÉÓÐÏÌØÚÕÅÔÓÑ ÁËÓÉÏÍÁ ×ÙÂÏÒÁ, Ï ËÏÔÏÒÏÊ ÍÙ ÇÏ×ÏÒÉÌÉ ÎÁ Ó. 15.)
   ÷ ÏÂÒÁÔÎÕÀ ÓÔÏÒÏÎÕ: ÅÓÌÉ ËÁËÏÅ-ÔÏ ÐÏÄÍÎÏÖÅÓÔ×Ï A0 ÍÎÏÖÅÓÔ×Á A ÒÁ×-
ÎÏÍÏÝÎÏ ÍÎÏÖÅÓÔ×Õ B É ÉÍÅÅÔÓÑ ÂÉÅËÃÉÑ g : A0 → B, ÔÏ ÎÁÌÏÖÅÎÉÅ A ÎÁ B
ÍÏÖÎÏ ÐÏÌÕÞÉÔØ, ÄÏÏÐÒÅÄÅÌÉ× ÜÔÕ ÂÉÅËÃÉÀ ÎÁ ÜÌÅÍÅÎÔÁÈ ×ÎÅ A0 ËÁËÉÍ ÕÇÏÄ-
ÎÏ ÏÂÒÁÚÏÍ.
     úÁÄÁÞÁ 56. îÁÊÄÉÔÅ ÏÛÉÂËÕ × ÜÔÏÍ ÒÁÓÓÕÖÄÅÎÉÉ, ÎÅ ÞÉÔÁÑ ÄÁÌØÛÅ.
   îÁ ÓÁÍÏÍ ÄÅÌÅ ÔÁËÏÅ ÐÒÏÄÏÌÖÅÎÉÅ ×ÏÚÍÏÖÎÏ, ÔÏÌØËÏ ÅÓÌÉ B ÎÅÐÕÓÔÏ, ÔÁË
ÞÔÏ ÐÒÁ×ÉÌØÎÏÅ ÕÔ×ÅÒÖÄÅÎÉÅ Ú×ÕÞÉÔ ÔÁË: ÎÁÌÏÖÅÎÉÅ A ÎÁ B ÓÕÝÅÓÔ×ÕÅÔ
ÔÏÌØËÏ É ÔÏÌØËÏ ÔÏÇÄÁ, ËÏÇÄÁ B ÎÅÐÕÓÔÏ É ÒÁ×ÎÏÍÏÝÎÏ ÎÅËÏÔÏÒÏÍÕ ÐÏÄÍÎÏ-
ÖÅÓÔ×Õ A, ÉÌÉ ËÏÇÄÁ ÏÂÁ ÍÎÏÖÅÓÔ×Á ÐÕÓÔÙ.
   ÷ ÎÁÛÅÍ ÉÚÌÏÖÅÎÉÉ ÏÓÔÁ¾ÔÓÑ Åݾ ÏÄÉÎ ÎÅ ×ÐÏÌÎÅ ÐÏÎÑÔÎÙÊ ÍÏÍÅÎÔ: ÞÔÏ
ÔÁËÏÅ ÕÐÏÒÑÄÏÞÅÎÎÁÑ ÐÁÒÁ? îÅÆÏÒÍÁÌØÎÏ ÇÏ×ÏÒÑ, ÜÔÏ ÓÐÏÓÏ ÉÚ Ä×ÕÈ ÏÂßÅË-
ÔÏ× x É y ÏÂÒÁÚÏ×ÁÔØ ÏÄÉÎ ÏÂßÅËÔ hx, yi, ÐÒÉÞ¾Í ÜÔÏÔ ÓÐÏÓÏ ÏÂÌÁÄÁÅÔ ÔÁËÉÍ
Ó×ÏÊÓÔ×ÏÍ:
                  hx1 , y1i = hx2 , y2i ⇔ x1 = x2 É y1 = y2 .
÷ ÐÒÉÎÃÉÐÅ, ÍÏÖÎÏ ÔÁË É ÓÞÉÔÁÔØ ÐÏÎÑÔÉÅ ÕÐÏÒÑÄÏÞÅÎÎÏÊ ÐÁÒÙ ÎÅÏÐÒÅÄÅ-
ÌÑÅÍÙÍ, Á ÜÔÏ Ó×ÏÊÓÔ×Ï ¡ ÁËÓÉÏÍÏÊ. ïÄÎÁËÏ ÐÒÉ ÆÏÒÍÁÌØÎÏÍ ÐÏÓÔÒÏÅÎÉÉ
ÔÅÏÒÉÉ ÍÎÏÖÅÓÔ× ÕÄÏÂÎÏ ÉÓÐÏÌØÚÏ×ÁÔØ ÔÒÀË, ÐÒÉÄÕÍÁÎÎÙÊ ÐÏÌØÓËÉÍ ÍÁ-
ÔÅÍÁÔÉËÏÍ ëÕÒÁÔÏ×ÓËÉÍ, É ÉÚÂÅÖÁÔØ ÐÏÑ×ÌÅÎÉÑ ÏÔÄÅÌØÎÏÇÏ ÐÏÎÑÔÉÑ ÕÐÏÒÑ-
ÄÏÞÅÎÎÏÊ ÐÁÒÙ. (îÁÐÏÍÎÉÍ, ÞÔÏ {x} ÏÂÏÚÎÁÞÁÅÔ ÍÎÏÖÅÓÔ×Ï, ÅÄÉÎÓÔ×ÅÎÎÙÍ
ÜÌÅÍÅÎÔÏÍ ËÏÔÏÒÏÇÏ Ñ×ÌÑÅÔÓÑ x, Á {x, y} ÏÂÏÚÎÁÞÁÅÔ ÍÎÏÖÅÓÔ×Ï, ËÏÔÏÒÏÅ ÓÏ-
ÄÅÒÖÉÔ x É y É ÎÅ ÓÏÄÅÒÖÉÔ ÄÒÕÇÉÈ ÜÌÅÍÅÎÔÏ×. ôÅÍ ÓÁÍÙÍ {x, y} = {x} =
= {y}, ÅÓÌÉ x = y.)
  ôÅÏÒÅÍÁ 9 (õÐÏÒÑÄÏÞÅÎÎÁÑ ÐÁÒÁ ÐÏ ëÕÒÁÔÏ×ÓËÏÍÕ). ïÐÒÅÄÅÌÉÍ hx, yi
ËÁË {{x}, {x, y}}. ôÏÇÄÁ ×ÙÐÏÌÎÅÎÏ ÕËÁÚÁÎÎÏÅ ×ÙÛÅ Ó×ÏÊÓÔ×Ï:
                  hx1, y1i = hx2 , y2i ⇔ x1 = x2 É y1 = y2 .
  äÏËÁÚÁÔÅÌØÓÔ×Ï. ðÕÓÔØ hx1 , y1i = hx2 , y2i. ðÏ ÏÐÒÅÄÅÌÅÎÉÀ ÜÔÏ ÏÚÎÁÞÁÅÔ,
ÞÔÏ
                     {{x1}, {x1, y1}} = {{x2}, {x2, y2}}.
ôÅÐÅÒØ ÎÕÖÎÏ ÁËËÕÒÁÔÎÏ ÒÁÚÏÂÒÁÔØ ÓÌÕÞÁÉ (ÎÅ ÐÕÔÁÑ ÐÒÉ ÜÔÏÍ x Ó {x}).
üÔÏ ÕÄÏÂÎÏ ÄÅÌÁÔØ × ÓÌÅÄÕÀÝÅÍ ÐÏÒÑÄËÅ. ðÕÓÔØ ÓÎÁÞÁÌÁ x1 6= y1 . ôÏÇÄÁ
ÍÎÏÖÅÓÔ×Ï {x1, y1} ÓÏÓÔÏÉÔ ÉÚ Ä×ÕÈ ÜÌÅÍÅÎÔÏ×. òÁÚ ÏÎÏ ÐÒÉÎÁÄÌÅÖÉÔ ÌÅ×ÏÊ
ÞÁÓÔÉ ÒÁ×ÅÎÓÔ×Á, ÔÏ ÐÒÉÎÁÄÌÅÖÉÔ É ÐÒÁ×ÏÊ. úÎÁÞÉÔ, ÏÎÏ ÒÁ×ÎÏ ÌÉÂÏ {x 2},

Страницы