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

UptoLike

ВУЗ: 

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

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

Рубрика: 

150 çÌÁ×Á VII. ÷ÙÞÉÓÌÉÍÏÓÔØ, ÒÁÚÒÅÛÉÍÏÓÔØ É ÐÅÒÅÞÉÓÌÉÍÏÓÔØ
ÍÎÏÖÅÓÔ×Á Q ÐÁÒ ÎÁÔÕÒÁÌØÎÙÈ ÞÉÓÅÌ. (ðÒÏÅËÃÉÑ ÐÏÌÕÞÁÅÔÓÑ, ÅÓÌÉ ÏÔ ÐÁÒ
ÏÓÔÁ×ÉÔØ ÉÈ ÐÅÒ×ÙÅ ËÏÍÐÏÎÅÎÔÙ: x ∈ P ⇔ ∃y(hx, yi ∈ Q).)
äÏËÁÚÁÔÅÌØÓÔ×Ï. ðÒÏÅËÃÉÑ ÌÀÂÏÇÏ ÐÅÒÅÞÉÓÌÉÍÏÇÏ ÍÎÏÖÅÓÔ×Á ÐÅÒÅÞÉÓÌÉ-
ÍÁ (ÐÅÒÅÞÉÓÌÑÀÝÉÊ ÁÌÇÏÒÉÔÍ ÄÏÌÖÅÎ ÌÉÛØ ÕÄÁÌÑÔØ ×ÔÏÒÙÅ ÞÌÅÎÙ ÐÁÒ),
ÔÁË ÞÔÏ ÐÒÏÅËÃÉÑ ÒÁÚÒÅÛÉÍÏÇÏ ÍÎÏÖÅÓÔ×Á ÔÅÍ ÂÏÌÅÅ ÐÅÒÅÞÉÓÌÉÍÁ.
îÁÐÒÏÔÉ×, ÅÓÌÉ P ¡ ÐÅÒÅÞÉÓÌÉÍÏÅ ÍÎÏÖÅÓÔ×Ï, ÐÅÒÅÞÉÓÌÑÅÍÏÅ ÁÌÇÏÒÉÔ-
ÍÏÍ A, ÔÏ ÏÎÏ ÅÓÔØ ÐÒÏÅËÃÉÑ ÒÁÚÒÅÛÉÍÏÇÏ ÍÎÏÖÅÓÔ×Á Q, ÓÏÓÔÏÑÝÅÇÏ ÉÚ ×ÓÅÈ
ÔÁËÉÈ ÐÁÒ hx, ni, ÞÔÏ x ÐÏÑ×ÌÑÅÔÓÑ × ÔÅÞÅÎÉÉ ÐÅÒ×ÙÈ n ÛÁÇÏ× ÒÁÂÏÔÙ ÁÌÇÏ-
ÒÉÔÍÁ A. (üÔÏ Ó×ÏÊÓÔ×Ï, ÏÞÅ×ÉÄÎÏ, ÒÁÚÒÅÛÉÍÏ.)
§5. ðÅÒÅÞÉÓÌÉÍÏÓÔØ É ×ÙÞÉÓÌÉÍÏÓÔØ
íÙ ×ÉÄÅÌÉ, ÞÔÏ ÐÅÒÅÞÉÓÌÉÍÏÅ ÍÎÏÖÅÓÔ×Ï ÍÏÖÎÏ ÏÐÒÅÄÅÌÉÔØ × ÔÅÒÍÉ-
ÎÁÈ ×ÙÞÉÓÌÉÍÙÈ ÆÕÎËÃÉÊ (ÎÁÐÒÉÍÅÒ, ËÁË ÏÂÌÁÓÔØ ÏÐÒÅÄÅÌÅÎÉÑ ×ÙÞÉÓÌÉÍÏÊ
ÆÕÎËÃÉÉ). íÏÖÎÏ ÓÄÅÌÁÔØ É ÎÁÏÂÏÒÏÔ:
ôÅÏÒÅÍÁ 50. æÕÎËÃÉÑ f Ó ÎÁÔÕÒÁÌØÎÙÍÉ ÁÒÇÕÍÅÎÔÁÍÉ É ÚÎÁÞÅÎÉÑÍÉ
×ÙÞÉÓÌÉÍÁ ÔÏÇÄÁ É ÔÏÌØËÏ ÔÏÇÄÁ, ËÏÇÄÁ ž ÇÒÁÆÉË
F = {hx, yi | f(x) ÏÐÒÅÄÅÌÅÎÏ É ÒÁ×ÎÏ y}
Ñ×ÌÑÅÔÓÑ ÐÅÒÅÞÉÓÌÉÍÙÍ ÍÎÏÖÅÓÔ×ÏÍ ÐÁÒ ÎÁÔÕÒÁÌØÎÙÈ ÞÉÓÅÌ.
äÏËÁÚÁÔÅÌØÓÔ×Ï. ðÕÓÔØ f ×ÙÞÉÓÌÉÍÁ. ôÏÇÄÁ ÓÕÝÅÓÔ×ÕÅÔ ÁÌÇÏÒÉÔÍ, ÐÅÒÅ-
ÞÉÓÌÑÀÝÉÊ Å¾ ÏÂÌÁÓÔØ ÏÐÒÅÄÅÌÅÎÉÑ, ÔÏ ÅÓÔØ ÐÅÞÁÔÁÀÝÉÊ ×ÓÅ x, ÎÁ ËÏÔÏÒÙÈ
f ÏÐÒÅÄÅÌÅÎÁ. åÓÌÉ ÔÅÐÅÒØ ÄÌÑ ËÁÖÄÏÇÏ ÉÚ ÔÁËÉÈ x ×ÙÞÉÓÌÑÔØ Åݾ É ÚÎÁÞÅ-
ÎÉÅ f(x), ÐÏÌÕÞÉÍ ÁÌÇÏÒÉÔÍ, ÐÅÒÅÞÉÓÌÑÀÝÉÊ ÍÎÏÖÅÓÔ×Ï F .
îÁÐÒÏÔÉ×, ÅÓÌÉ ÉÍÅÅÔÓÑ ÁÌÇÏÒÉÔÍ, ÐÅÒÅÞÉÓÌÑÀÝÉÊ F , ÔÏ ÆÕÎËÃÉÑ f ×Ù-
ÞÉÓÌÑÅÔÓÑ ÔÁËÉÍ ÁÌÇÏÒÉÔÍÏÍ: ÉÍÅÑ ÎÁ ×ÈÏÄÅ n, ÖÄ¾Í ÐÏÑ×ÌÅÎÉÑ × F ÐÁÒÙ,
ÐÅÒ×ÙÊ ÞÌÅÎ ËÏÔÏÒÏÊ ÒÁ×ÅÎ n; ËÁË ÔÏÌØËÏ ÔÁËÁÑ ÐÁÒÁ ÐÏÑ×ÉÌÁÓØ, ÐÅÞÁÔÁÅÍ
ž ×ÔÏÒÏÊ ÞÌÅÎ É ËÏÎÞÁÅÍ ÒÁÂÏÔÕ.
ðÕÓÔØ f ¡ ÞÁÓÔÉÞÎÁÑ ÆÕÎËÃÉÑ Ó ÎÁÔÕÒÁÌØÎÙÍÉ ÁÒÇÕÍÅÎÔÁÍÉ É ÚÎÁÞÅÎÉ-
ÑÍÉ. ïÂÒÁÚ ÍÎÏÖÅÓÔ×Á A ÐÒÉ f ÏÐÒÅÄÅÌÑÅÔÓÑ ËÁË ÍÎÏÖÅÓÔ×Ï ×ÓÅÈ ÞÉÓÅÌ f(n),
ÄÌÑ ËÏÔÏÒÙÈ n ∈ A É f(n) ÏÐÒÅÄÅÌÅÎÏ. ðÒÏÏÂÒÁÚ ÍÎÏÖÅÓÔ×Á A ÐÒÉ f ÏÐÒÅ-
ÄÅÌÑÅÔÓÑ ËÁË ÍÎÏÖÅÓÔ×Ï ×ÓÅÈ ÔÅÈ n, ÐÒÉ ËÏÔÏÒÙÈ f(n) ÏÐÒÅÄÅÌÅÎÏ É ÐÒÉÎÁÄ-
ÌÅÖÉÔ A.
ôÅÏÒÅÍÁ 51. ðÒÏÏÂÒÁÚ É ÏÂÒÁÚ ÐÅÒÅÞÉÓÌÉÍÏÇÏ ÍÎÏÖÅÓÔ×Á ÐÒÉ ×ÙÞÉ-
ÓÌÉÍÏÊ ÆÕÎËÃÉÉ ÐÅÒÅÞÉÓÌÉÍÙ.
150          çÌÁ×Á VII. ÷ÙÞÉÓÌÉÍÏÓÔØ, ÒÁÚÒÅÛÉÍÏÓÔØ É ÐÅÒÅÞÉÓÌÉÍÏÓÔØ

ÍÎÏÖÅÓÔ×Á Q ÐÁÒ ÎÁÔÕÒÁÌØÎÙÈ ÞÉÓÅÌ. (ðÒÏÅËÃÉÑ ÐÏÌÕÞÁÅÔÓÑ, ÅÓÌÉ ÏÔ ÐÁÒ
ÏÓÔÁ×ÉÔØ ÉÈ ÐÅÒ×ÙÅ ËÏÍÐÏÎÅÎÔÙ: x ∈ P ⇔ ∃y(hx, yi ∈ Q).)

  äÏËÁÚÁÔÅÌØÓÔ×Ï. ðÒÏÅËÃÉÑ ÌÀÂÏÇÏ ÐÅÒÅÞÉÓÌÉÍÏÇÏ ÍÎÏÖÅÓÔ×Á ÐÅÒÅÞÉÓÌÉ-
ÍÁ (ÐÅÒÅÞÉÓÌÑÀÝÉÊ ÁÌÇÏÒÉÔÍ ÄÏÌÖÅÎ ÌÉÛØ ÕÄÁÌÑÔØ ×ÔÏÒÙÅ ÞÌÅÎÙ ÐÁÒ),
ÔÁË ÞÔÏ ÐÒÏÅËÃÉÑ ÒÁÚÒÅÛÉÍÏÇÏ ÍÎÏÖÅÓÔ×Á ÔÅÍ ÂÏÌÅÅ ÐÅÒÅÞÉÓÌÉÍÁ.
  îÁÐÒÏÔÉ×, ÅÓÌÉ P ¡ ÐÅÒÅÞÉÓÌÉÍÏÅ ÍÎÏÖÅÓÔ×Ï, ÐÅÒÅÞÉÓÌÑÅÍÏÅ ÁÌÇÏÒÉÔ-
ÍÏÍ A, ÔÏ ÏÎÏ ÅÓÔØ ÐÒÏÅËÃÉÑ ÒÁÚÒÅÛÉÍÏÇÏ ÍÎÏÖÅÓÔ×Á Q, ÓÏÓÔÏÑÝÅÇÏ ÉÚ ×ÓÅÈ
ÔÁËÉÈ ÐÁÒ hx, ni, ÞÔÏ x ÐÏÑ×ÌÑÅÔÓÑ × ÔÅÞÅÎÉÉ ÐÅÒ×ÙÈ n ÛÁÇÏ× ÒÁÂÏÔÙ ÁÌÇÏ-
ÒÉÔÍÁ A. (üÔÏ Ó×ÏÊÓÔ×Ï, ÏÞÅ×ÉÄÎÏ, ÒÁÚÒÅÛÉÍÏ.)


  §5. ðÅÒÅÞÉÓÌÉÍÏÓÔØ É ×ÙÞÉÓÌÉÍÏÓÔØ
  íÙ ×ÉÄÅÌÉ, ÞÔÏ ÐÅÒÅÞÉÓÌÉÍÏÅ ÍÎÏÖÅÓÔ×Ï ÍÏÖÎÏ ÏÐÒÅÄÅÌÉÔØ × ÔÅÒÍÉ-
ÎÁÈ ×ÙÞÉÓÌÉÍÙÈ ÆÕÎËÃÉÊ (ÎÁÐÒÉÍÅÒ, ËÁË ÏÂÌÁÓÔØ ÏÐÒÅÄÅÌÅÎÉÑ ×ÙÞÉÓÌÉÍÏÊ
ÆÕÎËÃÉÉ). íÏÖÎÏ ÓÄÅÌÁÔØ É ÎÁÏÂÏÒÏÔ:

  ôÅÏÒÅÍÁ 50. æÕÎËÃÉÑ f Ó ÎÁÔÕÒÁÌØÎÙÍÉ ÁÒÇÕÍÅÎÔÁÍÉ É ÚÎÁÞÅÎÉÑÍÉ
×ÙÞÉÓÌÉÍÁ ÔÏÇÄÁ É ÔÏÌØËÏ ÔÏÇÄÁ, ËÏÇÄÁ ž ÇÒÁÆÉË
                 F = {hx, yi | f (x) ÏÐÒÅÄÅÌÅÎÏ É ÒÁ×ÎÏ y}
Ñ×ÌÑÅÔÓÑ ÐÅÒÅÞÉÓÌÉÍÙÍ ÍÎÏÖÅÓÔ×ÏÍ ÐÁÒ ÎÁÔÕÒÁÌØÎÙÈ ÞÉÓÅÌ.

   äÏËÁÚÁÔÅÌØÓÔ×Ï. ðÕÓÔØ f ×ÙÞÉÓÌÉÍÁ. ôÏÇÄÁ ÓÕÝÅÓÔ×ÕÅÔ ÁÌÇÏÒÉÔÍ, ÐÅÒÅ-
ÞÉÓÌÑÀÝÉÊ Å¾ ÏÂÌÁÓÔØ ÏÐÒÅÄÅÌÅÎÉÑ, ÔÏ ÅÓÔØ ÐÅÞÁÔÁÀÝÉÊ ×ÓÅ x, ÎÁ ËÏÔÏÒÙÈ
f ÏÐÒÅÄÅÌÅÎÁ. åÓÌÉ ÔÅÐÅÒØ ÄÌÑ ËÁÖÄÏÇÏ ÉÚ ÔÁËÉÈ x ×ÙÞÉÓÌÑÔØ Åݾ É ÚÎÁÞÅ-
ÎÉÅ f (x), ÐÏÌÕÞÉÍ ÁÌÇÏÒÉÔÍ, ÐÅÒÅÞÉÓÌÑÀÝÉÊ ÍÎÏÖÅÓÔ×Ï F .
   îÁÐÒÏÔÉ×, ÅÓÌÉ ÉÍÅÅÔÓÑ ÁÌÇÏÒÉÔÍ, ÐÅÒÅÞÉÓÌÑÀÝÉÊ F , ÔÏ ÆÕÎËÃÉÑ f ×Ù-
ÞÉÓÌÑÅÔÓÑ ÔÁËÉÍ ÁÌÇÏÒÉÔÍÏÍ: ÉÍÅÑ ÎÁ ×ÈÏÄÅ n, ÖÄ¾Í ÐÏÑ×ÌÅÎÉÑ × F ÐÁÒÙ,
ÐÅÒ×ÙÊ ÞÌÅÎ ËÏÔÏÒÏÊ ÒÁ×ÅÎ n; ËÁË ÔÏÌØËÏ ÔÁËÁÑ ÐÁÒÁ ÐÏÑ×ÉÌÁÓØ, ÐÅÞÁÔÁÅÍ
ž ×ÔÏÒÏÊ ÞÌÅÎ É ËÏÎÞÁÅÍ ÒÁÂÏÔÕ.

   ðÕÓÔØ f ¡ ÞÁÓÔÉÞÎÁÑ ÆÕÎËÃÉÑ Ó ÎÁÔÕÒÁÌØÎÙÍÉ ÁÒÇÕÍÅÎÔÁÍÉ É ÚÎÁÞÅÎÉ-
ÑÍÉ. ïÂÒÁÚ ÍÎÏÖÅÓÔ×Á A ÐÒÉ f ÏÐÒÅÄÅÌÑÅÔÓÑ ËÁË ÍÎÏÖÅÓÔ×Ï ×ÓÅÈ ÞÉÓÅÌ f (n),
ÄÌÑ ËÏÔÏÒÙÈ n ∈ A É f (n) ÏÐÒÅÄÅÌÅÎÏ. ðÒÏÏÂÒÁÚ ÍÎÏÖÅÓÔ×Á A ÐÒÉ f ÏÐÒÅ-
ÄÅÌÑÅÔÓÑ ËÁË ÍÎÏÖÅÓÔ×Ï ×ÓÅÈ ÔÅÈ n, ÐÒÉ ËÏÔÏÒÙÈ f (n) ÏÐÒÅÄÅÌÅÎÏ É ÐÒÉÎÁÄ-
ÌÅÖÉÔ A.

   ôÅÏÒÅÍÁ 51. ðÒÏÏÂÒÁÚ É ÏÂÒÁÚ ÐÅÒÅÞÉÓÌÉÍÏÇÏ ÍÎÏÖÅÓÔ×Á ÐÒÉ ×ÙÞÉ-
ÓÌÉÍÏÊ ÆÕÎËÃÉÉ ÐÅÒÅÞÉÓÌÉÍÙ.

Страницы