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

UptoLike

ВУЗ: 

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

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

Рубрика: 

154 çÌÁ×Á VIII. õÎÉ×ÅÒÓÁÌØÎÙÅ ÆÕÎËÃÉÉ É ÎÅÒÁÚÒÅÛÉÍÏÓÔØ
ÐÒÉÍÅÎÑÅÔ ÐÅÒ×ÙÊ ÁÒÇÕÍÅÎÔ ËÏ ×ÔÏÒÏÍÕ, ÅÓÌÉ ÏÔÏÖÄÅÓÔ×ÉÔØ ÐÒÏÇÒÁÍÍÕ É
ž ÎÏÍÅÒ).
úÁÄÁÞÁ 180. ÷ÓÅ ÓÅÞÅÎÉÑ U
n
ÎÅËÏÔÏÒÏÊ ÆÕÎËÃÉÉ U Ä×ÕÈ ÁÒÇÕÍÅÎÔÏ×
×ÙÞÉÓÌÉÍÙ. óÌÅÄÕÅÔ ÌÉ ÏÔÓÀÄÁ, ÞÔÏ ÆÕÎËÃÉÑ U ×ÙÞÉÓÌÉÍÁ?
úÁÄÁÞÁ 181. äÁÊÔÅ (ÅÓÔÅÓÔ×ÅÎÎÏÅ) ÏÐÒÅÄÅÌÅÎÉÅ ÐÏÎÑÔÉÑ ×ÙÞÉÓÌÉÍÏÊ
ÆÕÎËÃÉÉ ÔÒ¾È ÁÒÇÕÍÅÎÔÏ×, ÕÎÉ×ÅÒÓÁÌØÎÏÊ ÄÌÑ ËÌÁÓÓÁ ×ÙÞÉÓÌÉÍÙÈ ÆÕÎËÃÉÊ
Ä×ÕÈ ÁÒÇÕÍÅÎÔÏ×, É ÄÏËÁÖÉÔŠž ÓÕÝÅÓÔ×Ï×ÁÎÉÅ.
äÌÑ ÍÎÏÖÅÓÔ× ÉÓÐÏÌØÚÕÅÔÓÑ ÁÎÁÌÏÇÉÞÎÁÑ ÔÅÒÍÉÎÏÌÏÇÉÑ: ÍÎÏÖÅÓÔ×Ï W ⊂
⊂ N × N ÎÁÚÙ×ÁÀÔ ÕÎÉ×ÅÒÓÁÌØÎÙÍ ÄÌÑ ÎÅËÏÔÏÒÏÇÏ ËÌÁÓÓÁ ÍÎÏÖÅÓÔ× ÎÁÔÕ-
ÒÁÌØÎÙÈ ÞÉÓÅÌ, ÅÓÌÉ ×ÓÅ ÓÅÞÅÎÉÑ
W
n
= {x | hn, xi ∈ W }
ÍÎÏÖÅÓÔ×Á W ÐÒÉÎÁÄÌÅÖÁÔ ÜÔÏÍÕ ËÌÁÓÓÕ É ÄÒÕÇÉÈ ÍÎÏÖÅÓÔ× × ËÌÁÓÓÅ ÎÅÔ.
ôÅÏÒÅÍÁ 53. óÕÝÅÓÔ×ÕÅÔ ÐÅÒÅÞÉÓÌÉÍÏÅ ÍÎÏÖÅÓÔ×Ï ÐÁÒ ÎÁÔÕÒÁÌØÎÙÈ
ÞÉÓÅÌ, ÕÎÉ×ÅÒÓÁÌØÎÏÅ ÄÌÑ ËÌÁÓÓÁ ×ÓÅÈ ÐÅÒÅÞÉÓÌÉÍÙÈ ÍÎÏÖÅÓÔ× ÎÁÔÕÒÁÌØ-
ÎÙÈ ÞÉÓÅÌ.
äÏËÁÚÁÔÅÌØÓÔ×Ï. òÁÓÓÍÏÔÒÉÍ ÏÂÌÁÓÔØ ÏÐÒÅÄÅÌÅÎÉÑ ÕÎÉ×ÅÒÓÁÌØÎÏÊ ÆÕÎË-
ÃÉÉ U. ïÎÁ ÂÕÄÅÔ ÕÎÉ×ÅÒÓÁÌØÎÙÍ ÐÅÒÅÞÉÓÌÉÍÙÍ ÍÎÏÖÅÓÔ×ÏÍ, ÐÏÓËÏÌØËÕ
×ÓÑËÏÅ ÐÅÒÅÞÉÓÌÉÍÏÅ ÍÎÏÖÅÓÔ×Ï Ñ×ÌÑÅÔÓÑ ÏÂÌÁÓÔØÀ ÏÐÒÅÄÅÌÅÎÉÑ ÎÅËÏÔÏÒÏÊ
×ÙÞÉÓÌÉÍÏÊ ÆÕÎËÃÉÉ U
n
.
úÁÄÁÞÁ 182. ëÁË ÐÏÓÔÒÏÉÔØ ÕÎÉ×ÅÒÓÁÌØÎÏÅ ÍÎÏÖÅÓÔ×Ï, ÉÓÈÏÄÑ ÉÚ ÔÏ-
ÇÏ, ÞÔÏ ×ÓÑËÏÅ ÐÅÒÅÞÉÓÌÉÍÏÅ ÍÎÏÖÅÓÔ×Ï ÅÓÔØ ÍÎÏÖÅÓÔ×Ï ÚÎÁÞÅÎÉÊ ÎÅËÏ-
ÔÏÒÏÊ ÆÕÎËÃÉÉ U
n
?
úÁÄÁÞÁ 183. óÕÝÅÓÔ×ÕÅÔ ÌÉ ÒÁÚÒÅÛÉÍÏÅ ÍÎÏÖÅÓÔ×Ï ÐÁÒ ÎÁÔÕÒÁÌØ-
ÎÙÈ ÞÉÓÅÌ, ÕÎÉ×ÅÒÓÁÌØÎÏÅ ÄÌÑ ËÌÁÓÓÁ ×ÓÅÈ ÒÁÚÒÅÛÉÍÙÈ ÍÎÏÖÅÓÔ× ÎÁÔÕ-
ÒÁÌØÎÙÈ ÞÉÓÅÌ?
§2. äÉÁÇÏÎÁÌØÎÁÑ ËÏÎÓÔÒÕËÃÉÑ
÷ ÐÒÅÄÙÄÕÝÅÍ ÒÁÚÄÅÌÅ ÍÙ ÐÏÓÔÒÏÉÌÉ ÕÎÉ×ÅÒÓÁÌØÎÕÀ ÆÕÎËÃÉÀ ÄÌÑ ËÌÁÓ-
ÓÁ ×ÓÅÈ ×ÙÞÉÓÌÉÍÙÈ ÆÕÎËÃÉÊ ÏÄÎÏÇÏ ÁÒÇÕÍÅÎÔÁ. íÏÖÎÏ ÌÉ ÓÄÅÌÁÔØ ÔÏ ÖÅ
ÓÁÍÏÅ ÄÌÑ ËÌÁÓÓÁ ×ÓÀÄÕ ÏÐÒÅÄÅ̾ÎÎÙÈ ×ÙÞÉÓÌÉÍÙÈ ÆÕÎËÃÉÊ? ïËÁÚÙ×ÁÅÔÓÑ,
ÞÔÏ ÎÅÔ.
ôÅÏÒÅÍÁ 54. îÅ ÓÕÝÅÓÔ×ÕÅÔ ×ÙÞÉÓÌÉÍÏÊ ×ÓÀÄÕ ÏÐÒÅÄÅ̾ÎÎÏÊ ÆÕÎËÃÉÉ
Ä×ÕÈ ÁÒÇÕÍÅÎÔÏ×, ÕÎÉ×ÅÒÓÁÌØÎÏÊ ÄÌÑ ËÌÁÓÓÁ ×ÓÅÈ ×ÙÞÉÓÌÉÍÙÈ ×ÓÀÄÕ ÏÐÒÅ-
ÄÅ̾ÎÎÙÈ ÆÕÎËÃÉÊ ÏÄÎÏÇÏ ÁÒÇÕÍÅÎÔÁ.
154             çÌÁ×Á VIII. õÎÉ×ÅÒÓÁÌØÎÙÅ ÆÕÎËÃÉÉ É ÎÅÒÁÚÒÅÛÉÍÏÓÔØ

ÐÒÉÍÅÎÑÅÔ ÐÅÒ×ÙÊ ÁÒÇÕÍÅÎÔ ËÏ ×ÔÏÒÏÍÕ, ÅÓÌÉ ÏÔÏÖÄÅÓÔ×ÉÔØ ÐÒÏÇÒÁÍÍÕ É
ž ÎÏÍÅÒ).
  úÁÄÁÞÁ 180. ÷ÓÅ ÓÅÞÅÎÉÑ Un ÎÅËÏÔÏÒÏÊ ÆÕÎËÃÉÉ U Ä×ÕÈ ÁÒÇÕÍÅÎÔÏ×
×ÙÞÉÓÌÉÍÙ. óÌÅÄÕÅÔ ÌÉ ÏÔÓÀÄÁ, ÞÔÏ ÆÕÎËÃÉÑ U ×ÙÞÉÓÌÉÍÁ?
   úÁÄÁÞÁ 181. äÁÊÔÅ (ÅÓÔÅÓÔ×ÅÎÎÏÅ) ÏÐÒÅÄÅÌÅÎÉÅ ÐÏÎÑÔÉÑ ×ÙÞÉÓÌÉÍÏÊ
ÆÕÎËÃÉÉ ÔÒ¾È ÁÒÇÕÍÅÎÔÏ×, ÕÎÉ×ÅÒÓÁÌØÎÏÊ ÄÌÑ ËÌÁÓÓÁ ×ÙÞÉÓÌÉÍÙÈ ÆÕÎËÃÉÊ
Ä×ÕÈ ÁÒÇÕÍÅÎÔÏ×, É ÄÏËÁÖÉÔŠž ÓÕÝÅÓÔ×Ï×ÁÎÉÅ.
  äÌÑ ÍÎÏÖÅÓÔ× ÉÓÐÏÌØÚÕÅÔÓÑ ÁÎÁÌÏÇÉÞÎÁÑ ÔÅÒÍÉÎÏÌÏÇÉÑ: ÍÎÏÖÅÓÔ×Ï W ⊂
⊂ N × N ÎÁÚÙ×ÁÀÔ ÕÎÉ×ÅÒÓÁÌØÎÙÍ ÄÌÑ ÎÅËÏÔÏÒÏÇÏ ËÌÁÓÓÁ ÍÎÏÖÅÓÔ× ÎÁÔÕ-
ÒÁÌØÎÙÈ ÞÉÓÅÌ, ÅÓÌÉ ×ÓÅ ÓÅÞÅÎÉÑ
                        Wn = {x | hn, xi ∈ W }
ÍÎÏÖÅÓÔ×Á W ÐÒÉÎÁÄÌÅÖÁÔ ÜÔÏÍÕ ËÌÁÓÓÕ É ÄÒÕÇÉÈ ÍÎÏÖÅÓÔ× × ËÌÁÓÓÅ ÎÅÔ.
  ôÅÏÒÅÍÁ 53. óÕÝÅÓÔ×ÕÅÔ ÐÅÒÅÞÉÓÌÉÍÏÅ ÍÎÏÖÅÓÔ×Ï ÐÁÒ ÎÁÔÕÒÁÌØÎÙÈ
ÞÉÓÅÌ, ÕÎÉ×ÅÒÓÁÌØÎÏÅ ÄÌÑ ËÌÁÓÓÁ ×ÓÅÈ ÐÅÒÅÞÉÓÌÉÍÙÈ ÍÎÏÖÅÓÔ× ÎÁÔÕÒÁÌØ-
ÎÙÈ ÞÉÓÅÌ.
   äÏËÁÚÁÔÅÌØÓÔ×Ï. òÁÓÓÍÏÔÒÉÍ ÏÂÌÁÓÔØ ÏÐÒÅÄÅÌÅÎÉÑ ÕÎÉ×ÅÒÓÁÌØÎÏÊ ÆÕÎË-
ÃÉÉ U. ïÎÁ ÂÕÄÅÔ ÕÎÉ×ÅÒÓÁÌØÎÙÍ ÐÅÒÅÞÉÓÌÉÍÙÍ ÍÎÏÖÅÓÔ×ÏÍ, ÐÏÓËÏÌØËÕ
×ÓÑËÏÅ ÐÅÒÅÞÉÓÌÉÍÏÅ ÍÎÏÖÅÓÔ×Ï Ñ×ÌÑÅÔÓÑ ÏÂÌÁÓÔØÀ ÏÐÒÅÄÅÌÅÎÉÑ ÎÅËÏÔÏÒÏÊ
×ÙÞÉÓÌÉÍÏÊ ÆÕÎËÃÉÉ Un.
   úÁÄÁÞÁ 182. ëÁË ÐÏÓÔÒÏÉÔØ ÕÎÉ×ÅÒÓÁÌØÎÏÅ ÍÎÏÖÅÓÔ×Ï, ÉÓÈÏÄÑ ÉÚ ÔÏ-
ÇÏ, ÞÔÏ ×ÓÑËÏÅ ÐÅÒÅÞÉÓÌÉÍÏÅ ÍÎÏÖÅÓÔ×Ï ÅÓÔØ ÍÎÏÖÅÓÔ×Ï ÚÎÁÞÅÎÉÊ ÎÅËÏ-
ÔÏÒÏÊ ÆÕÎËÃÉÉ Un?
  úÁÄÁÞÁ 183. óÕÝÅÓÔ×ÕÅÔ ÌÉ ÒÁÚÒÅÛÉÍÏÅ ÍÎÏÖÅÓÔ×Ï ÐÁÒ ÎÁÔÕÒÁÌØ-
ÎÙÈ ÞÉÓÅÌ, ÕÎÉ×ÅÒÓÁÌØÎÏÅ ÄÌÑ ËÌÁÓÓÁ ×ÓÅÈ ÒÁÚÒÅÛÉÍÙÈ ÍÎÏÖÅÓÔ× ÎÁÔÕ-
ÒÁÌØÎÙÈ ÞÉÓÅÌ?

  §2. äÉÁÇÏÎÁÌØÎÁÑ ËÏÎÓÔÒÕËÃÉÑ
   ÷ ÐÒÅÄÙÄÕÝÅÍ ÒÁÚÄÅÌÅ ÍÙ ÐÏÓÔÒÏÉÌÉ ÕÎÉ×ÅÒÓÁÌØÎÕÀ ÆÕÎËÃÉÀ ÄÌÑ ËÌÁÓ-
ÓÁ ×ÓÅÈ ×ÙÞÉÓÌÉÍÙÈ ÆÕÎËÃÉÊ ÏÄÎÏÇÏ ÁÒÇÕÍÅÎÔÁ. íÏÖÎÏ ÌÉ ÓÄÅÌÁÔØ ÔÏ ÖÅ
ÓÁÍÏÅ ÄÌÑ ËÌÁÓÓÁ ×ÓÀÄÕ ÏÐÒÅÄÅ̾ÎÎÙÈ ×ÙÞÉÓÌÉÍÙÈ ÆÕÎËÃÉÊ? ïËÁÚÙ×ÁÅÔÓÑ,
ÞÔÏ ÎÅÔ.
   ôÅÏÒÅÍÁ 54. îÅ ÓÕÝÅÓÔ×ÕÅÔ ×ÙÞÉÓÌÉÍÏÊ ×ÓÀÄÕ ÏÐÒÅÄÅ̾ÎÎÏÊ ÆÕÎËÃÉÉ
Ä×ÕÈ ÁÒÇÕÍÅÎÔÏ×, ÕÎÉ×ÅÒÓÁÌØÎÏÊ ÄÌÑ ËÌÁÓÓÁ ×ÓÅÈ ×ÙÞÉÓÌÉÍÙÈ ×ÓÀÄÕ ÏÐÒÅ-
ÄÅ̾ÎÎÙÈ ÆÕÎËÃÉÊ ÏÄÎÏÇÏ ÁÒÇÕÍÅÎÔÁ.

Страницы