Самохин А.В. Математическая логика и теория алгоритмов
Подождите немного. Документ загружается.
§6. æÕÎËÃÉÉ ÁÌÇÅÂÒÙ ÌÏÇÉËÉ 231
415. ðÕÓÔØ ÏÔÏÂÒÁÖÅÎÉÅ f : R → R ÄÅÊÓÔ×ÕÅÔ ÐÏ ÐÒÁ×ÉÌÕ
f(x) =
1 + x ÐÒÉ x > 0,
1 − x ÐÒÉ x < 0.
îÁÊÔÉ f ([0; 1]), f ([−1; 2]), f
−1
([0; 1]), f
−1
([−1; 2]).
416. ðÕÓÔØ ÚÁÄÁÎÏ ÏÔÏÂÒÁÖÅÎÉÅ f : R → R, ÇÄÅ f(x) = sin x. îÁÊÔÉ
f((0; π)), f
π
4
;
5π
6
, f
−1
−
1
2
;
1
2
, f
−1
([0; 2]).
417. ñ×ÌÑÅÔÓÑ ÌÉ ÏÔÏÂÒÁÖÅÎÉÅ
f
n
: N → N, f
n
(k) =
n − k ÐÒÉ k < n,
n + k ÐÒÉ k > n
ÉÎßÅËÔÉ×ÎÙÍ, ÓÀÒßÅËÔÉ×ÎÙÍ, ÂÉÅËÔÉ×ÎÙÍ?
ðÕÓÔØ C(R) ¡ ÍÎÏÖÅÓÔ×Ï ×ÓÅÈ ×ÅÝÅÓÔ×ÅÎÎÙÈ ÎÅÐÒÅÒÙ×ÎÙÈ ÆÕÎËÃÉÊ.
ðÒÏ×ÅÒÉÔØ, Ñ×ÌÑÀÔÓÑ ÌÉ ÓÌÅÄÕÀÝÉÅ ÏÔÏÂÒÁÖÅÎÉÑ F : C(R) → C(R) ÉÎß-
ÅËÔÉ×ÎÙÍ, ÓÀÒßÅËÔÉ×ÎÙÍ, ÂÉÅËÔÉ×ÎÙÍ. îÁÊÔÉ ÏÂÒÁÔÎÙÅ Ë ÎÉÍ Ó ÓÏÏÔ×ÅÔ-
ÓÔ×ÕÀÝÅÊ ÓÔÏÒÏÎÙ.
418. [F (f )](x) = f (e
x
); 419. [F (f)](x) = e
f(x)
; 420. [F (f)](x) = (x
2
−1)f (x);
421. [F (f)](x) = (x
2
+ 1)f (x); 422. [F (f)](x) = f(2x − 1);
423. [F (f )](x) = f
3
(x); 424. [F (f )](x) = f(x
1
3
).
425. îÁÊÔÉ ËÏÍÐÏÚÉÉÃÉÀ ÏÔÏÂÒÁÖÅÎÉÊ ÉÚ ÚÁÄÁÞ 420, 421, 423 É 424.
§6. æÕÎËÃÉÉ ÁÌÇÅÂÒÙ ÌÏÇÉËÉ
îÁÐÏÍÎÉÍ, ÞÔÏ ÂÕÌÅ×Ù ÏÐÅÒÁÃÉÉ ¬, ∧, ∨ ÏÂÒÁÚÕÀÔ ÐÏÌÎÕÀ ÓÉÓÔÅÍÕ ÆÕÎË-
ÃÉÊ. üÔÏ ÏÚÎÁÞÁÅÔ, ÞÔÏ ÌÀÂÁÑ ÆÕÎËÃÉÑ ÁÌÇÅÂÒÙ ÌÏÇÉËÉ (⇔ ÂÕÌÅ×Á ÆÕÎËÃÉÑ)
ÍÏÖÅÔ ÂÙÔØ ÚÁÄÁÎÁ ÆÏÒÍÕÌÏÊ ÎÁÄ ¬, ∧, ∨.
÷ ÞÁÓÔÎÏÓÔÉ, x | y ≡ x · y, x ↑ y ≡ x ∨ y, x ⊕ y ≡ xy ∨ xy.
åݾ ÏÄÎÏÊ ÐÏÌÎÏÊ ÓÉÓÔÅÍÏÊ ÆÕÎËÃÉÊ Ñ×ÌÑÅÔÓÑ {0, 1, ⊕, ∧}. æÏÒÍÕÌÙ ÎÁÄ
{0, 1, ⊕, &w} ÎÁÚÙ×ÁÀÔ ÍÎÏÇÏÞÌÅÎÁÍÉ öÅÇÁÌËÉÎÁ.
ëÁÎÏÎÉÞÅÓËÉÍ ÍÎÏÇÏÞÌÅÎÏÍ öÅÇÁÌËÉÎÁ ÎÁÚÙ×ÁÀÔ ÍÎÏÇÏÞÌÅÎ öÅÇÁÌËÉ-
ÎÁ, × ËÏÔÏÒÏÍ ÒÁÓËÒÙÔÙ ÓËÏÂËÉ É ÐÒÉ×ÅÄÅÎÙ ÐÏÄÏÂÎÙÅ.
ðÅÒÅÍÅÎÎÁÑ x
i
ÆÕÎËÃÉÉ ÎÁÚÙ×ÁÅÔÓÑ ÆÉËÔÉ×ÎÏÊ, ÅÓÌÉ
f(x
1
, . . . , x
i−1
, 0, x
i+1
, . . . , x
n
) = f(x
1
, . . . , x
i−1
, 1, x
i+1
, . . . , x
n
).
ðÅÒÅÍÅÎÎÁÑ x
i
× ÆÕÎËÃÉÉ f (x
1
, . . . , x
n
) ÆÉËÔÉ×ÎÁ ÔÏÇÄÁ É ÔÏÌØËÏ ÔÏÇÄÁ, ËÏ-
ÇÄÁ ËÁÎÏÎÉÞÅÓËÉÊ ÍÎÏÇÏÞÌÅÎ öÅÇÁÌËÉÎÁ ÆÕÎËÃÉÉ f ÎÅ ÓÏÄÅÒÖÉÔ ÐÅÒÅÍÅÎ-
ÎÏÊ x
i
.
426. îÁÊÔÉ ËÁÎÏÎÉÞÅÓËÉÅ ÍÎÏÇÏÞÌÅÎÙ öÅÇÁÌËÉÎÁ ÓÌÅÄÕÀÝÉÈ ÂÕÌÅ×ÙÈ
ÆÕÎËÃÉÊ:
232 úÁÄÁÞÉ
Á) ×ÓÅÈ ÂÕÌÅ×ÙÈ ÆÕÎËÃÉÊ ÉÚ P
2
(1), P
2
(2); Â) (x
1
→ x
2
) ∼ (x
2
∼ x
3
);
×) (x
1
→ x
3
) · (x
2
⊕ x
3
); Ç) x
1
· x
3
∨ x
2
· x
4
; Ä) (x
1
∼ x
2
) → x
3
;
Å) (10101100) ¡ ÓÔÏÌÂÅà ÚÎÁÞÅÎÉÊ ÆÕÎËÃÉÉ f × Å¾ ÔÁÂÌÉÃÅ; Ö) (11000100);
Ú) (x
1
| x
2
) ↑ x
3
.
427. îÁÊÔÉ ×ÓÅ ÆÉËÔÉ×ÎÙÅ ÐÅÒÅÍÅÎÎÙÅ ÓÌÅÄÕÀÝÉÈ ÂÕÌÅ×ÙÈ ÆÕÎËÃÉÊ:
Á) x
1
x
2
∨ x
1
x
2
; Â) x
1
x
2
∨ x
2
; ×) x
1
x
2
∨ x
1
; Ç) (x
1
→ (x
2
→
→ x
3
)) → ((x
1
→ x
2
) → (x
1
→ x
3
)); Ä) (x
1
→ x
2
)((x
2
→ x
3
) → (x
1
→ x
3
));
Å) (x
1
→ x
2
) → (x
2
→ x
1
); Ö) (x
1
→ x
2
) → x
1
.
428. óËÏÌØËÏ ÆÕÎËÃÉÊ ÓÏÄÅÒÖÉÔÓÑ ×Ï ÍÎÏÖÅÓÔ×Å:
Á) P
0
(n) ∩ P
1
(n); Â) P
0
(n) ∪ P
1
(n); ×) P
0
(n)\P
1
(n); Ç) P
0
(n) ∩ S(n);
Ä) P
0
(n) ∪ S(n); Å) P
0
(n)\S(n); Ö) S(n)\P
0
(n).
429. óÒÅÄÉ ÆÕÎËÃÉÊ ÐÒÉÍÅÒÏ× 426 É 427 ÎÁÊÔÉ ×ÓÅ ÆÕÎËÃÉÉ, ×ÈÏÄÑÝÉÅ:
Á) × P
0
; Â) × P
1
.
430. ëÁËÉÅ ÉÚ ÓÌÅÄÕÀÝÉÈ ÆÕÎËÃÉÊ ÓÁÍÏÄ×ÏÊÓÔ×ÅÎÎÙ:
Á) (x
1
→ x
2
) → x
1
x
3
; Â) (x
1
∨ x
2
∨ x
1
)x
4
∨ x
1
x
2
x
3
; ×) x
1
x
2
⊕ x
1
x
3
⊕ x
2
x
3
;
Ç) (0001001001100111); Ä) f(x
1
, x
2
, . . . , x
2m+1
) = x
1
⊕ x
2
⊕ . . . ⊕ x
2m+1
⊕ δ,
δ ∈ {0, 1}; Å) (x
1
∨ x
2
)(x
1
∨ x
3
)(x
2
∨ x
3
); Ö) (x
1
| x
1
) ↑ x
2
.
431. éÚ ÎÅÓÁÍÏÄ×ÏÊÓÔ×ÅÎÎÏÊ ÆÕÎËÃÉÉ f Ó ÐÏÍÏÝØÀ ÏÔÏÖÄÅÓÔ×ÌÅÎÉÑ ÐÅ-
ÒÅÍÅÎÎÙÈ É ÏÐÅÒÁÃÉÉ ¬ ÐÏÌÕÞÉÔØ ËÏÎÓÔÁÎÔÕ:
Á) (00111001); Â) (x
1
| x
2
) → (x
1
⊕ x
3
); ×) (x
1
∨ x
2
∨ x
3
) ⊕ x
1
x
2
x
3
;
Ç) x
1
x
2
∨ x
1
x
3
∨ x
2
x
4
∨ x
3
x
4
.
432. ëÁËÉÅ ÉÚ ÆÕÎËÃÉÊ ÐÒÉÍÅÒÏ× 426, 427, 430 ÍÏÎÏÔÏÎÎÙ?
433. éÚ ÎÅÍÏÎÏÔÏÎÎÙÈ ÆÕÎËÃÉÊ ÐÒÉÍÅÒÏ× 430 É 431 Ó ÐÏÍÏÝØÀ ÐÏÄÓÔÁ-
ÎÏ×ËÉ ËÏÎÓÔÁÎÔ ÐÏÌÕÞÉÔØ ¬x.
434. ëÁËÉÅ ÉÚ ÓÌÅÄÕÀÝÉÈ ÆÕÎËÃÉÊ ÍÏÎÏÔÏÎÎÙ:
Á) x
1
→ (x
2
→ x
3
); Â) (00110111); ×) x
1
x
3
· (x
1
⊕ x
3
);
Ç) x
1
x
2
⊕ x
1
x
3
⊕ x
2
x
3
⊕ x
1
; Ä) (01100111).
435. ëÁËÉÅ ÉÚ ÆÕÎËÃÉÊ ÐÒÉÍÅÒÏ× 426, 427, 430, 434 ÌÉÎÅÊÎÙ?
436. éÚ ÎÅÌÉÎÅÊÎÙÈ ÆÕÎËÃÉÊ ÐÒÉÍÅÒÁ 435 Ó ÐÏÍÏÝØÀ ËÏÎÓÔÁÎÔ 0, 1 É
ÏÐÅÒÁÃÉÉ ¬ ÐÏÌÕÞÉÔØ ∧.
437. ÷ÙÒÁÚÉÔØ Ó ÐÏÍÏÝØÀ ÓÕÐÅÒÐÏÚÉÃÉÊ:
Á) ∧ É → ÞÅÒÅÚ ¬, ∨; Â) ∨ É → ÞÅÒÅÚ ¬, ∧; ×) ∧ É ∨ ÞÅÒÅÚ ¬, →;
Ç) ¬ ÞÅÒÅÚ 0, →; Ä) ¬ ÞÅÒÅÚ 1, ⊕; Å) ∨ ÞÅÒÅÚ →; Ö) ¬, ∨, ∧, →, ∼
ÞÅÒÅÚ ↑; Ú) ¬, ∨, ∧, →, ⊕ ÞÅÒÅÚ |; É) ↑ ÞÅÒÅÚ |; Ë) | ÞÅÒÅÚ ↑.
438. äÏËÁÚÁÔØ ÐÏÌÎÏÔÕ ÓÌÅÄÕÀÝÉÈ ÓÉÓÔÅÍ ÆÕÎËÃÉÊ Ó×ÅÄÅÎÉÅÍ Ë ÚÁ×ÅÄÏÍÏ
ÐÏÌÎÙÍ ÓÉÓÔÅÍÁÍ:
Á) {x
1
↑ x
2
}; Â) {x
1
| x
2
}; ×) {x
1
→ x
2
, x
1
⊕ x
2
⊕ x
3
};
Ç) {(1011), (1100001100111100)}.
439. ó ÐÏÍÏÝØÀ ÔÅÏÒÅÍÙ ðÏÓÔÁ ÐÒÏ×ÅÒÉÔØ ÎÁ ÐÏÌÎÏÔÕ ÓÌÅÄÕÀÝÉÅ ÓÉÓÔÅ-
§6. æÕÎËÃÉÉ ÁÌÇÅÂÒÙ ÌÏÇÉËÉ 233
ÍÙ ÆÕÎËÃÉÊ:
Á) x
1
x
2
, x
1
∨ x
2
; Â) x
1
→ x
2
, x
1
→ x
2
x
3
; ×) x
1
x
2
, x
1
∼ x
2
x
3
;
Ç) 0, 1, x
1
(x
2
∼ x
3
) ∨ x
1
(x
2
⊕ x
3
); Ä) ¬x, (0010), (0101110011100011);
Å) 1, x
1
⊕ x
2
, (x
1
→ x
2
) ↑ (x
2
∼ x
3
), (x
3
| (x
1
· x
2
)) → x
3
; Ö) x
1
→ x
2
, x
1
;
Ú) x
1
x
2
, x
1
∨ x
2
, x
1
→ x
2
; É) x
1
∼ x
2
, x
1
, x
1
→ x
2
; Ë) x
1
→ x
2
, 0, x
1
∼ x
2
;
Ì) x
1
⊕ x
2
, x
1
; Í) x
1
x
2
∨ x
1
x
3
∨ x
2
x
3
, 0, 1; Î) x
1
x
2
∨ x
1
x
3
∨ x
2
x
3
, x
1
,
x
1
→ x
2
;
440. éÚ ÐÏÌÎÙÈ ÓÉÓÔÅÍ ÐÒÉÍÅÒÁ 439 ×ÙÄÅÌÉÔØ ×ÓÅ ×ÏÚÍÏÖÎÙÅ ÂÁÚÉÓÙ, ÔÏ
ÅÓÔØ ÔÁËÉÅ ÐÏÌÎÙÅ ÐÏÄÓÉÓÔÅÍÙ, Õ ËÏÔÏÒÙÈ ÎÉ ÏÄÎÁ ÓÏÂÓÔ×ÅÎÎÁÑ ÐÏÄÓÉÓÔÅÍÁ
ÎÅ Ñ×ÌÑÅÔÓÑ ÐÏÌÎÏÊ.
441. äÏËÁÚÁÔØ, ÞÔÏ ÅÓÌÉ ÓÉÓÔÅÍÁ ÆÕÎËÃÉÊ {f
1
, f
2
, . . . , f
m
} ÐÏÌÎÁ, ÔÏ É
ÓÉÓÔÅÍÁ ÆÕÎËÃÉÊ {f
∗
1
, f
∗
2
, . . . , f
∗
m
} ÔÁËÖÅ ÐÏÌÎÁ.
442. ëÁËÉÅ ÉÚ ÓÌÅÄÕÀÝÉÈ ÓÉÓÔÅÍ ÆÕÎËÃÉÊ Ñ×ÌÑÀÔÓÑ ÚÁÍËÎÕÔÙÍÉ:
Á) P
2
(1); Â) P
2
(2); ×) P
2
; Ç) P
0
∩ P
1
; Ä) P
0
∪ P
1
; Å) P
0
\P
1
.
443. äÏËÁÚÁÔØ, ÞÔÏ ÐÅÒÅÓÅÞÅÎÉÅ ÆÕÎËÃÉÏÎÁÌØÎÏ ÚÁÍËÎÕÔÙÈ ËÌÁÓÓÏ× Ñ×ÌÑ-
ÅÔÓÑ ÆÕÎËÃÉÏÎÁÌØÎÏ ÚÁÍËÎÕÔÙÍ ËÌÁÓÓÏÍ.
444. äÏËÁÚÁÔØ, ÞÔÏ ÅÓÌÉ ÍÎÏÖÅÓÔ×Ï M ÆÕÎËÃÉÏÎÁÌØÎÏ ÚÁÍËÎÕÔÙÊ ËÌÁÓÓ,
ÔÏ ÍÎÏÖÅÓÔ×Ï M
∗
, ÓÏÓÔÏÑÝÅÅ ÉÚ ÆÕÎËÃÉÊ, Ä×ÏÊÓÔ×ÅÎÎÙÈ Ë ÆÕÎËÃÉÑÍ ÉÚ M,
ÔÁËÖÅ Ñ×ÌÑÅÔÓÑ ÆÕÎËÃÉÏÎÁÌØÎÏ ÚÁÍËÎÕÔÙÍ ËÌÁÓÓÏÍ.
445. äÏËÁÚÁÔØ, ÞÔÏ ÅÓÌÉ M 6= ∅, M 6= P
2
É [M] = M, ÔÏ P
2
\M ÎÅÚÁ-
ÍËÎÕÔÏ.
446. ïÂÏÚÎÁÞÉÍ ÞÅÒÅÚ M
−
ÍÎÏÖÅÓÔ×Ï ÍÏÎÏÔÏÎÎÏ ÕÂÙ×ÁÀÝÉÈ ÂÕÌÅ×ÙÈ
ÆÕÎËÃÉÊ. äÏËÁÚÁÔØ, ÞÔÏ ÍÎÏÖÅÓÔ×Á M
−
É M ∪ M
−
ÎÅÚÁÍËÎÕÔÙ.
447. äÏËÁÚÁÔØ, ÞÔÏ ÄÌÑ ÍÏÎÏÔÏÎÎÏÓÔÉ ÆÕÎËÃÉÉ, ÏÔÌÉÞÎÏÊ ÏÔ ËÏÎÓÔÁÎÔÙ,
ÎÅÏÂÈÏÄÉÍÏ É ÄÏÓÔÁÔÏÞÎÏ, ÞÔÏÂÙ ÏÎÁ ÐÒÅÄÓÔÁ×ÌÑÌÁÓØ × ×ÉÄÅ ÓÕÐÅÒÐÏÚÉÃÉÉ
ËÏÎßÀÎËÃÉÊ É ÄÉÚßÀÎËÃÉÊ (⇔ f ∈ [∨, ∧]).
448. äÏËÁÚÁÔØ, ÞÔÏ f ∈ M ⇔ f
∗
∈ M.
449. îÁÊÔÉ M ∩ (P
2
\P
0
), M ∩ (P
2
\P
1
).
450. ë ËÁËÏÍÕ ÎÁÉÍÅÎØÛÅÍÕ ÞÉÓÌÕ ÐÅÒÅÍÅÎÎÙÈ ÍÏÖÎÏ Ó×ÅÓÔÉ ÎÅÍÏÎÏÔÏÎ-
ÎÕÀ ÆÕÎËÃÉÀ Ó ÓÏÈÒÁÎÅÎÉÅÍ ÎÅÍÏÎÏÔÏÎÎÏÓÔÉ, ÏÔÏÖÄÅÓÔ×ÌÑÑ Å¾ ÐÅÒÅÍÅÎÎÙÅ?
451. îÁÊÔÉ P
2
(2)\(P
0
∪ P
1
∪ L ∪ S ∪ M).
452. îÁÊÔÉ ×ÓÅ ÆÕÎËÃÉÉ, ËÏÔÏÒÙÅ ÍÏÖÎÏ ÐÏÌÕÞÉÔØ, ÏÔÏÖÄÅÓÔ×ÌÑÑ ÐÅÒÅ-
ÍÅÎÎÙÅ, ÉÚ ÓÌÅÄÕÀÝÉÈ ÆÕÎËÃÉÊ:
Á) (10010110); Â) (11111101); ×) x
1
x
2
∨ x
2
x
3
∨ x
1
x
3
;
Ç) x
1
x
2
x
3
⊕ x
2
x
3
⊕ x
3
x
1
⊕ x
2
⊕ 1.
234 úÁÄÁÞÉ
§7. íÁÛÉÎÁ ôØÀÒÉÎÇÁ
÷ ÜÔÏÍ ÒÁÚÄÅÌÅ ÓÏÄÅÒÖÁÔÓÑ ÚÁÄÁÞÉ Ä×ÕÈ ÔÉÐÏ×:
¡ ÐÏ ÚÁÄÁÎÎÏÊ ÍÁÛÉÎÅ ôØÀÒÉÎÇÁ ÎÁÊÔÉ ÒÅÚÕÌØÔÁÔ Å¾ ÐÒÉÍÅÎÅÎÉÑ Ë
ÚÁÄÁÎÎÏÍÕ ÓÌÏ×Õ u, ÔÏ ÅÓÔØ ÎÁÊÔÉ T (u);
¡ ÐÏÓÔÒÏÉÔØ ÍÁÛÉÎÕ, ÒÅÛÁÀÝÕÀ ÄÁÎÎÙÊ ËÌÁÓÓ ÚÁÄÁÞ.
ðÒÉ ÒÅÛÅÎÉÉ ÚÁÄÁÞ ×ÔÏÒÏÇÏ ÔÉÐÁ ÒÅËÏÍÅÎÄÕÅÔÓÑ ÄÏ ÓÏÓÔÁ×ÌÅÎÉÑ ÐÒÏÇÒÁÍ-
ÍÙ ÍÁÛÉÎÙ, ÔÏ ÅÓÔØ ÄÏ ÚÁÐÏÌÎÅÎÉÑ ÔÁÂÌÉÃÙ, ÚÁÄÁÀÝÅÊ ÐÒÏÇÒÁÍÍÕ, ÔÝÁ-
ÔÅÌØÎÏ ÐÒÏÄÕÍÁÔØ ÁÌÇÏÒÉÔÍ, ËÏÔÏÒÙÊ ÄÏÌÖÅÎ ÂÙÔØ ÒÅÁÌÉÚÏ×ÁÎ ÐÒÏÇÒÁÍÍÏÊ.
÷ ËÏÎÃÅ ÒÅÛÅÎÉÑ (ËÏÇÄÁ ÐÒÏÇÒÁÍÍÁ ÓÏÓÔÁ×ÌÅÎÁ) ÎÅ ÚÁÂÕÄØÔÅ ÐÒÉÍÅÎÉÔØ Å¾
Ë ÔÅÓÔÏ×ÏÍÕ ÐÒÉÍÅÒÕ.
ðÏ ÚÁÄÁÎÎÏÊ ÍÁÛÉÎÅ T Ó ×ÎÅÛÎÉÍ ÁÌÆÁ×ÉÔÏÍ A = {|, ∧} É ÓÌÏ×Õ u ÎÁÊÔÉ
ÓÌÏ×Ï T (u):
453.
q
1
q
2
| ∧q
2
+ 1 | q
2
− 1
∧ | q
0
0 ∧q
1
+ 1
u
1
=||||
u
2
=| ∧∧ |
454.
q
1
q
2
q
3
| | q
3
+ 1 | q
2
0 | q
1
+ 1
∧ | q
2
+ 1 | q
3
+ 1 | q
0
0
u
1
=|||
u
2
=| ∧∧ |
u
3
=|| ∧ ∧ ∧ |
÷ÙÑÓÎÉÔØ, ÐÒÉÍÅÎÉÍÁ ÌÉ ÍÁÛÉÎÁ T Ó ×ÎÅÛÎÉÍ ÁÌÆÁ×ÉÔÏÍ {|, ∧} Ë ÓÌÏ×Õ
u, É × ÓÌÕÞÁÅ ÐÒÉÍÅÎÉÍÏÓÔÉ ÎÁÊÔÉ ÒÅÚÕÌØÔÁÔ:
455.
q
1
q
2
| ∧q
1
+ 1 ∧q
2
− 1
∧ ∧q
2
− 1 | q
0
+ 1
u
1
=|||
u
2
=|| ∧ |
456.
q
1
q
2
q
3
| ∧q
1
+ 1 | q
1
− 1 | q
2
+ 1
∧ ∧q
2
+ 1 ∧q
3
+ 1 ∧q
0
0
u
1
=|| ∧ |
u
2
=| ∧ ||||
457. ðÏÓÔÒÏÉÔØ ÍÁÛÉÎÕ K
2
ÎÁÄ ÁÌÆÁ×ÉÔÏÍ {|}.
458. ðÏÓÔÒÏÉÔØ ÍÁÛÉÎÕ K
1
ÎÁÄ ÁÌÆÁ×ÉÔÏÍ {α, β}.
459. ëÁËÕÀ ÆÕÎËÃÉÀ ÎÁÔÕÒÁÌØÎÏÇÏ ÁÒÇÕÍÅÎÔÁ ×ÙÞÉÓÌÑÅÔ ÍÁÛÉÎÁ, ÚÁ-
ÄÁÎÎÁÑ ÐÒÏÇÒÁÍÍÏÊ:
§7. íÁÛÉÎÁ ôØÀÒÉÎÇÁ 235
q
1
q
2
| | q
2
+ 1 | q
2
+ 1
∧ | q
0
0 | q
0
0
õÐÒÏÓÔÉÔØ ÜÔÕ ÍÁÛÉÎÕ.
460. ðÏÓÔÒÏÉÔØ ÍÁÛÉÎÕ, ÒÁÓÐÏÚÎÁÀÝÕÀ Þ¾ÔÎÏÓÔØ ÎÁÔÕÒÁÌØÎÏÇÏ ÞÉÓÌÁ.
461. ðÏÓÔÒÏÉÔØ ÍÁÛÉÎÕ R
m
, ×ÙÞÉÓÌÑÀÝÕÀ ÏÓÔÁÔÏË ÏÔ ÄÅÌÅÎÉÑ ÎÁÔÕ-
ÒÁÌØÎÏÇÏ ÞÉÓÌÁ ÎÁ m.
462. ðÏÓÔÒÏÉÔØ ÍÁÛÉÎÙ ôØÀÒÉÎÇÁ, ×ÙÞÉÓÌÑÀÝÉÅ ÓÌÅÄÕÀÝÉÅ ÆÕÎËÃÉÉ,
ÚÁÄÁÎÎÙÅ ÎÁ N × N:
Á) x + y; Â) x + 2y; ×) x · y; Ç) x
2
+ 3y.
463. ðÏÓÔÒÏÉÔØ ÍÁÛÉÎÙ ôØÀÒÉÎÇÁ, ×ÙÞÉÓÌÑÀÝÉÅ ÓÌÅÄÕÀÝÉÅ ÆÕÎËÃÉÉ,
ÏÐÒÅÄÅ̾ÎÎÙÅ ÎÁ N:
Á) 3x; Â) x
2
; ×) f (x) =
x + 1 ÐÒÉ x = 2n,
2x ÐÒÉ x = 2n + 1.
464. ðÏÓÔÒÏÉÔØ ÍÁÛÉÎÕ ÎÁÄ ÁÌÆÁ×ÉÔÏÍ {|}, ÐÒÉÍÅÎÉÍÕÀ Ë ÌÀÂÏÍÕ ÓÌÏ×Õ
Þ¾ÔÎÏÊ ÄÌÉÎÙ É ÎÅ ÐÒÉÍÅÎÉÍÕÀ Ë ÓÌÏ×ÁÍ ÎÅÞ¾ÔÎÏÊ ÄÌÉÎÙ.
ðÏÓÔÒÏÉÔØ × ÁÌÆÁ×ÉÔÅ {0, 1} ÍÁÛÉÎÕ T , ÒÁÂÏÔÁÀÝÕÀ ÐÏ ÐÒÁ×ÉÌÕ:
465. T (1
n
) = 1
n
01
n
, n ∈ N, a
n
def
= aa . . . a
| {z }
n
;
466. T (0
n
1
n
) = (01)
n
, n ∈ N;
467. T (1
n
) = 1
n
01
2n
01
3n
, n ∈ N;
468. T (1
n
01
m
) = 1
m
01
n
, n, m ∈ N;
469. T (1
n
0
m
) =
1
2n
ÐÒÉ n > m,
(01)
n
ÐÒÉ n = m,
0
m
ÐÒÉ n < m.
470. ëÁËÕÀ ÆÕÎËÃÉÀ ÎÁÔÕÒÁÌØÎÏÇÏ ÁÒÇÕÍÅÎÔÁ ×ÙÞÉÓÌÑÅÔ ÍÁÛÉÎÁ T ?
Á)
q
1
q
2
q
3
q
4
q
5
| | q
1
+ 1 0q
3
+ 1 0q
3
+ 1 | q
5
− 1 | q
5
− 1
∧ ∧q
2
+ 1 ∧q
1
− 1 ∧q
4
− 1 ∧q
4
− 1 ∧q
0
+ 1
Â)
q
1
q
2
q
3
q
4
q
5
q
6
q
7
q
8
q
9
| ∧q
2
+1 |q
4
+1 |q
3
−1 |q
4
+1 |q
6
+1 |q
6
+1 ∧q
8
−1 |q
8
−1 |q
9
+1
∧ ∧q
2
+1 ∧q
3
+1 |q
0
0 ∧q
5
+1 ∧q
3
−1 ∧q
7
−1 ∧q
9
−1 ∧q
1
+1
471. ëÁËÉÅ ÏÄÎÏÍÅÓÔÎÙÅ ÆÕÎËÃÉÉ ÎÁÔÕÒÁÌØÎÏÇÏ ÁÒÇÕÍÅÎÔÁ × ÁÌÆÁ×ÉÔÅ
{|, ∧} ÍÏÇÕÔ ×ÙÞÉÓÌÑÔØ ÍÁÛÉÎÙ, ÐÒÏÇÒÁÍÍÙ ËÏÔÏÒÙÈ ÓÏÄÅÒÖÁÔ ÔÏÌØËÏ ËÏ-
ÍÁÎÄÙ q
0
É q
1
?
236 úÁÄÁÞÉ
ðÏ ÓÌÏ×ÅÓÎÏÍÕ ÏÐÉÓÁÎÉÀ ÍÁÛÉÎ T
3
, T
4
, . . . ÐÏÓÔÒÏÉÔØ ÉÈ ÐÒÏÇÒÁÍÍÙ c
×ÎÅÛÎÉÍ ÁÌÆÁ×ÉÔÏÍ {0, 1, ∧}:
472. T
3
¡ ÎÁÞÉÎÁÑ Ó ÐÏÓÌÅÄÎÅÊ ÅÄÉÎÉÃÙ ÍÁÓÓÉ×Á ÉÚ ÅÄÉÎÉÃ, ¤ÓÄ×ÉÇÁÅÔ¥
ÅÇÏ ÎÁ ÏÄÎÕ ÑÞÅÊËÕ ×ÌÅ×Ï É ÏÓÔÁÎÁ×ÌÉ×ÁÅÔÓÑ ÎÁ ÐÅÒ×ÏÊ ÅÄÉÎÉÃÅ;
473. T
4
¡ ÐÒÉ ÚÁÄÁÎÎÏÍ l > 1 óúõ ÍÁÛÉÎÙ, ÎÁÞÁ× Ó ÐÒÏÉÚ×ÏÌØÎÏÊ ÑÞÅÊËÉ,
ÚÁÐÏÌÎÅÎÎÏÊ ÅÄÉÎÉÃÅÊ, Ä×ÉÖÅÔÓÑ ×ÐÒÁ×Ï, ÎÅ ÍÅÎÑÑ ÓÏÄÅÒÖÉÍÏÇÏ ÑÞÅÅË, ÄÏ
ÔÅÈ ÐÏÒ ÐÏËÁ ÎÅ ÐÒÏÊÄ¾Ô ÍÁÓÓÉ× ÉÚ l + 1 ÎÕÌÑ; óúõ ÏÓÔÁÎÁ×ÌÉ×ÁÅÔÓÑ ÎÁ
ÓÌÅÄÕÀÝÅÊ ÑÞÅÊËÅ, ÐÏÍÅÓÔÉ× ÔÕÄÁ ÅÄÉÎÉÃÕ;
474. T
5
¡ ÐÒÉ ÚÁÄÁÎÎÏÍ l > 1 óúõ, ÎÁÞÁ× Ó ÐÒÏÉÚ×ÏÌØÎÏÊ ÑÞÅÊËÉ É Ä×É-
ÇÁÑÓØ ×ÐÒÁ×Ï, ÐÒÏÓÔÁ×ÌÑÅÔ ÐÏÄÒÑÄ l ÅÄÉÎÉÃ É ÏÓÔÁÎÁ×ÌÉ×ÁÅÔÓÑ ÎÁ ÐÏÓÌÅÄÎÅÊ
ÉÚ ÎÉÈ;
475. T
6
¡ ÍÁÛÉÎÁ ÎÁÞÉÎÁÅÔ ÒÁÂÏÔÕ Ó ËÒÁÊÎÅÊ ÓÌÅ×Á ÎÅÐÕÓÔÏÊ ÑÞÅÊËÉ
ÐÒÏÉÚ×ÏÌØÎÏÇÏ ÓÌÏ×Á, ÐÒÉ ÚÁÄÁÎÎÏÍ l > 1 ÏÔÙÓËÉ×ÁÅÔ × ÓÌÏ×Å ÐÅÒ×ÙÊ ÓÌÅ×Á
ÍÁÓÓÉ× ÉÚ l + 1 ÎÕÌÑ É ÏÓÔÁÎÁ×ÌÉ×ÁÅÔÓÑ ÎÁ ÐÏÓÌÅÄÎÅÍ ÉÚ ÎÉÈ (ÓÏÄÅÒÖÉÍÏÅ
ÑÞÅÅË ÎÅ ÍÅÎÑÅÔÓÑ);
476. T
7
¡ ÎÁÞÁ× ÒÁÂÏÔÕ Ó ÓÁÍÏÊ ÌÅ×ÏÊ ÎÅÐÕÓÔÏÊ ÑÞÅÊËÉ, ÍÁÛÉÎÁ ÏÔÙÓËÉ-
×ÁÅÔ ÅÄÉÎÉÃÕ, ÐÒÉÍÙËÁÀÝÕÀ ÓÌÅ×Á Ë ÐÅÒ×ÏÍÕ ÓÌÅ×Á ÍÁÓÓÉ×Õ ÉÚ ÔÒ¾È ÎÕÌÅÊ,
¤ÏËÁÊÍ̾ÎÎÏÍÕ¥ ÅÄÉÎÉÃÁÍÉ, óúõ ÏÓÔÁÎÁ×ÌÉ×ÁÅÔÓÑ ÎÁ ÎÁÊÄÅÎÎÏÊ ÅÄÉÎÉÃÅ
(ÓÏÄÅÒÖÉÍÏÅ ÑÞÅÅË ÎÅ ÍÅÎÑÅÔÓÑ);
477. T
8
¡ × ÉÓÈÏÄÎÏÊ ÑÞÅÊËÅ ÐÅÞÁÔÁÅÔ ÎÕÌØ, óúõ ÓÄ×ÉÇÁÅÔÓÑ ÎÁ ÏÄÎÕ
ÑÞÅÊËÕ ×ÌÅ×Ï É ÍÁÛÉÎÁ ÏÓÔÁÎÁ×ÌÉ×ÁÅÔÓÑ.
478. T
9
¡ óúõ ÍÁÛÉÎÙ ÓÄ×ÉÇÁÅÔÓÑ ÎÁ Ä×Å ÑÞÅÊËÉ ×ÐÒÁ×Ï ÏÔ ÎÁÞÁÌØÎÏÊ,
ÍÁÛÉÎÁ ÏÓÔÁÎÁ×ÌÉ×ÁÅÔÓÑ × ÓÏÓÔÏÑÎÉÉ q
0
, ÅÓÌÉ ÜÔÁ ÑÞÅÊËÁ ÓÏÄÅÒÖÉÔ ÎÕÌØ, ×
ÓÏÓÔÏÑÎÉÉ q
0
0
, ÅÓÌÉ ÜÔÁ ÑÞÅÊËÁ ÓÏÄÅÒÖÉÔ ÅÄÉÎÉÃÕ.
479. T
10
¡ óúõ ÐÅÒÅÄ×ÉÇÁÅÔÓÑ ÎÁ ÏÄÎÕ ÑÞÅÊËÕ ×ÌÅ×Ï É ÍÁÛÉÎÁ ÏÓÔÁÎÁ-
×ÌÉ×ÁÅÔÓÑ;
480. T
11
¡ ÏÔÐÒÁ×ÌÑÑÓØ ÏÔ ÎÁÞÁÌØÎÏÊ ÑÞÅÊËÉ, ÎÁÈÏÄÉÔ ÐÅÒ×ÕÀ ÅÄÉÎÉÃÕ
É ÏÓÔÁÎÁ×ÌÉ×ÁÅÔÓÑ ÎÁ ÓÌÅÄÕÀÝÅÊ ÚÁ ÎÅÊ ÑÞÅÊËÅ.
481. îÁÊÄÉÔÅ ËÏÍÐÏÚÉÃÉÉ ÍÁÛÉÎ: T
4
◦ T
3
, T
6
◦ T
7
, T
11
◦ T
10
◦ T
5
. (íÁÛÉÎÙ
T
3
, T
4
, . . . ÓÍ. × ÐÒÉÍÅÒÁÈ 472 ¡ 480.)
óÐÉÓÏË ÌÉÔÅÒÁÔÕÒÙ
[1] î. ë. ÷ÅÒÅÝÁÇÉÎ, á. ûÅÎØ. ìÅËÃÉÉ ÐÏ ÍÁÔÅÍÁÔÉÞÅÓËÏÊ ÌÏÇÉËÅ É ÔÅÏÒÉÉ
ÁÌÇÏÒÉÔÍÏ×. þÁÓÔØ 1. îÁÞÁÌÁ ÔÅÏÒÉÉ ÍÎÏÖÅÓÔ×. í.: íãîíï, 1999.
128 Ó.
[2] î. ë. ÷ÅÒÅÝÁÇÉÎ, á. ûÅÎØ. ìÅËÃÉÉ ÐÏ ÍÁÔÅÍÁÔÉÞÅÓËÏÊ ÌÏÇÉËÅ É ÔÅÏÒÉÉ
ÁÌÇÏÒÉÔÍÏ×. þÁÓÔØ 2. ñÚÙËÉ É ÉÓÞÉÓÌÅÎÉÑ. í.: íãîíï, 2000. 288 Ó.
[3] î. ë. ÷ÅÒÅÝÁÇÉÎ, á. ûÅÎØ. ìÅËÃÉÉ ÐÏ ÍÁÔÅÍÁÔÉÞÅÓËÏÊ ÌÏÇÉËÅ É ÔÅÏÒÉÉ
ÁÌÇÏÒÉÔÍÏ×. þÁÓÔØ 3. ÷ÙÞÉÓÌÉÍÙÅ ÆÕÎËÃÉÉ. í.: íãîíï, 1999. 176 Ó.
[4] ñ. í. åÒÕÓÁÌÉÍÓËÉÊ, äÉÓËÒÅÔÎÁÑ ÍÁÔÅÍÁÔÉËÁ: ÔÅÏÒÉÑ, ÚÁÄÁÞÉ, ÐÒÉÌÏ-
ÖÅÎÉÑ. 4-Å ÉÚÄÁÎÉÅ - í.: ÷ÕÚÏ×ÓËÁÑ ËÎÉÇÁ, 2001. 280 Ó.
[5] à. é. íÁÎÉÎ. äÏËÁÚÕÅÍÏÅ É ÎÅÄÏËÁÚÕÅÍÏÅ. í.: óÏ×ÅÔÓËÏÅ ÒÁÄÉÏ, 1979.
168 Ó.
[6] à. é. íÁÎÉÎ, ÷ÙÞÉÓÌÉÍÏÅ É ÎÅ×ÙÞÉÓÌÉÍÏÅ. í.: óÏ×ÅÔÓËÏÅ ÒÁÄÉÏ, 1980.
128 Ó.
237