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

UptoLike

ВУЗ: 

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

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

Рубрика: 

§1. üË×É×ÁÌÅÎÔÎÏÓÔØ É ÐÏÒÑÄÏË 45
ÍÎÏÖÅÓÔ×Å ÉÚ n ÜÌÅÍÅÎÔÏ×?
úÁÄÁÞÁ 80. äÏËÁÖÉÔÅ, ÞÔÏ ×ÓÑËÉÊ ÞÁÓÔÉÞÎÙÊ ÐÏÒÑÄÏË ÎÁ ËÏÎÅÞÎÏÍ
ÍÎÏÖÅÓÔ×Å ÍÏÖÎÏ ÐÒÏÄÏÌÖÉÔØ ÄÏ ÌÉÎÅÊÎÏÇÏ (ÐÒÏÄÏÌÖÉÔØ ÏÚÎÁÞÁÅÔ,
ÞÔÏ ÅÓÌÉ x 6 y × ÉÓÈÏÄÎÏÍ ÐÏÒÑÄËÅ, ÔÏ É × ÎÏ×ÏÍ ÜÔÏ ÏÓÔÁÎÅÔÓÑ ÔÁË).
úÁÄÁÞÁ 81. äÁÎÏ ÂÅÓËÏÎÅÞÎÏÅ ÞÁÓÔÉÞÎÏ ÕÐÏÒÑÄÏÞÅÎÎÏÅ ÍÎÏÖÅÓÔ×Ï X.
äÏËÁÖÉÔÅ, ÞÔÏ × Î¾Í ×ÓÅÇÄÁ ÎÁÊľÔÓÑ ÌÉÂÏ ÂÅÓËÏÎÅÞÎÏÅ ÐÏÄÍÎÏÖÅÓÔ×Ï
ÐÏÐÁÒÎÏ ÎÅÓÒÁ×ÎÉÍÙÈ ÜÌÅÍÅÎÔÏ×, ÌÉÂÏ ÂÅÓËÏÎÅÞÎÏÅ ÐÏÄÍÎÏÖÅÓÔ×Ï, ÎÁ ËÏ-
ÔÏÒÏÍ ÉÎÄÕÃÉÒÏ×ÁÎÎÙÊ ÐÏÒÑÄÏË ÌÉÎÅÅÎ.
úÁÄÁÞÁ 82. (ëÏÎÅÞÎÙÊ ×ÁÒÉÁÎÔ ÐÒÅÄÙÄÕÝÅÊ ÚÁÄÁÞÉ.) äÁÎÙ ÃÅÌÙÅ ÐÏ-
ÌÏÖÉÔÅÌØÎÙÅ ÞÉÓÌÁ m É n. äÏËÁÖÉÔÅ, ÞÔÏ ×Ï ×ÓÑËÏÍ ÞÁÓÔÉÞÎÏ ÕÐÏÒÑÄÏ-
ÞÅÎÎÏÍ ÍÎÏÖÅÓÔ×Å ÍÏÝÎÏÓÔÉ mn + 1 ÍÏÖÎÏ ÕËÁÚÁÔØ ÌÉÂÏ m + 1 ÐÏÐÁÒÎÏ
ÎÅÓÒÁ×ÎÉÍÙÈ ÜÌÅÍÅÎÔÏ×, ÌÉÂÏ n + 1 ÐÏÐÁÒÎÏ ÓÒÁ×ÎÉÍÙÈ.
úÁÄÁÞÁ 83. ÷ ÓÔÒÏÞËÕ ÎÁÐÉÓÁÎÙ mn + 1 ÒÁÚÌÉÞÎÙÈ ÞÉÓÅÌ. äÏËÁÖÉÔÅ,
ÞÔÏ ÍÏÖÎÏ ÞÁÓÔØ ÉÚ ÎÉÈ ×ÙÞÅÒËÎÕÔØ ÔÁË, ÞÔÏÂÙ ÏÓÔÁÌÁÓØ ÌÉÂÏ ×ÏÚÒÁ-
ÓÔÁÀÝÁÑ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ ÄÌÉÎÙ m + 1, ÌÉÂÏ ÕÂÙ×ÁÀÝÁÑ ÐÏÓÌÅÄÏ×Á-
ÔÅÌØÎÏÓÔØ ÄÌÉÎÙ n + 1. (õËÁÚÁÎÉÅ: ÍÏÖÎÏ ×ÏÓÐÏÌØÚÏ×ÁÔØÓÑ ÐÒÅÄÙÄÕÝÅÊ
ÚÁÄÁÞÅÊ.)
úÁÄÁÞÁ 84. òÁÓÓÍÏÔÒÉÍ ÓÅÍÅÊÓÔ×Ï ×ÓÅÈ ÐÏÄÍÎÏÖÅÓÔ× ÎÁÔÕÒÁÌØÎÏÇÏ
ÒÑÄÁ, ÕÐÏÒÑÄÏÞÅÎÎÏÅ ÐÏ ×ËÌÀÞÅÎÉÀ. óÕÝÅÓÔ×ÕÅÔ ÌÉ Õ ÎÅÇÏ ÌÉÎÅÊÎÏ ÕÐÏ-
ÒÑÄÏÞÅÎÎÏÅ (× ÉÎÄÕÃÉÒÏ×ÁÎÎÏÍ ÐÏÒÑÄËÅ) ÐÏÄÓÅÍÅÊÓÔ×Ï ÍÏÝÎÏÓÔÉ ËÏÎÔÉ-
ÎÕÕÍ? óÕÝÅÓÔ×ÕÅÔ ÌÉ Õ ÎÅÇÏ ÐÏÄÓÅÍÅÊÓÔ×Ï ÍÏÝÎÏÓÔÉ ËÏÎÔÉÎÕÕÍ, ÌÀÂÙÅ
Ä×Á ÜÌÅÍÅÎÔÁ ËÏÔÏÒÏÇÏ ÎÅÓÒÁ×ÎÉÍÙ?
üÌÅÍÅÎÔ ÞÁÓÔÉÞÎÏ ÕÐÏÒÑÄÏÞÅÎÎÏÇÏ ÍÎÏÖÅÓÔ×Á ÎÁÚÙ×ÁÀÔ ÎÁÉÂÏÌØÛÉÍ, ÅÓ-
ÌÉ ÏÎ ÂÏÌØÛÅ ÌÀÂÏÇÏ ÄÒÕÇÏÇÏ ÜÌÅÍÅÎÔÁ, É ÍÁËÓÉÍÁÌØÎÙÍ, ÅÓÌÉ ÎÅ ÓÕÝÅÓÔ×Õ-
ÅÔ ÂÏÌØÛÅÇÏ ÜÌÅÍÅÎÔÁ. åÓÌÉ ÍÎÏÖÅÓÔ×Ï ÎÅ Ñ×ÌÑÅÔÓÑ ÌÉÎÅÊÎÏ ÕÐÏÒÑÄÏÞÅÎ-
ÎÙÍ, ÔÏ ÜÔÏ ÎÅ ÏÄÎÏ É ÔÏ ÖÅ: ÎÁÉÂÏÌØÛÉÊ ÜÌÅÍÅÎÔ Á×ÔÏÍÁÔÉÞÅÓËÉ Ñ×ÌÑÅÔÓÑ
ÍÁËÓÉÍÁÌØÎÙÍ, ÎÏ ÎÅ ÎÁÏÂÏÒÏÔ. (ïÄÎÏ ÄÅÌÏ ËÏÒÏÂËÁ, × ËÏÔÏÒÕÀ ÐÏÍÅÝÁÅÔÓÑ
ÌÀÂÁÑ ÄÒÕÇÁÑ, ÄÒÕÇÏÅ ¡ ËÏÒÏÂËÁ, ËÏÔÏÒÁÑ ÎÉËÕÄÁ ÂÏÌØÛÅ ÎÅ ÐÏÍÅÝÁÅÔÓÑ.)
áÎÁÌÏÇÉÞÎÙÍ ÏÂÒÁÚÏÍ ÏÐÒÅÄÅÌÑÀÔÓÑ ÎÁÉÍÅÎØÛÉÅ É ÍÉÎÉÍÁÌØÎÙÅ ÜÌÅ-
ÍÅÎÔÙ.
ìÅÇËÏ ÐÏÎÑÔØ, ÞÔÏ ÎÁÉÂÏÌØÛÉÊ ÜÌÅÍÅÎÔ × ÄÁÎÎÏÍ ÞÁÓÔÉÞÎÏ ÕÐÏÒÑÄÏÞÅÎ-
ÎÏÍ ÍÎÏÖÅÓÔ×Å ÍÏÖÅÔ ÂÙÔØ ÔÏÌØËÏ ÏÄÉÎ, × ÔÏ ×ÒÅÍÑ ËÁË ÍÁËÓÉÍÁÌØÎÙÈ
ÜÌÅÍÅÎÔÏ× ÍÏÖÅÔ ÂÙÔØ ÍÎÏÇÏ.
úÁÄÁÞÁ 85. äÏËÁÖÉÔÅ, ÞÔÏ ÌÀÂÙÅ Ä×Á ÍÁËÓÉÍÁÌØÎÙÈ ÜÌÅÍÅÎÔÁ ÎÅ
ÓÒÁ×ÎÉÍÙ. äÏËÁÖÉÔÅ, ÞÔÏ × ËÏÎÅÞÎÏÍ ÞÁÓÔÉÞÎÏ ÕÐÏÒÑÄÏÞÅÎÎÏÍ ÍÎÏ-
ÖÅÓÔ×Å X ÄÌÑ ÌÀÂÏÇÏ ÜÌÅÍÅÎÔÁ x ÎÁÊľÔÓÑ ÍÁËÓÉÍÁÌØÎÙÊ ÜÌÅÍÅÎÔ y,
ÂÏÌØÛÉÊ ÉÌÉ ÒÁ×ÎÙÊ x.
§1. üË×É×ÁÌÅÎÔÎÏÓÔØ É ÐÏÒÑÄÏË                                       45

ÍÎÏÖÅÓÔ×Å ÉÚ n ÜÌÅÍÅÎÔÏ×?
  úÁÄÁÞÁ 80. äÏËÁÖÉÔÅ, ÞÔÏ ×ÓÑËÉÊ ÞÁÓÔÉÞÎÙÊ ÐÏÒÑÄÏË ÎÁ ËÏÎÅÞÎÏÍ
ÍÎÏÖÅÓÔ×Å ÍÏÖÎÏ ÐÒÏÄÏÌÖÉÔØ ÄÏ ÌÉÎÅÊÎÏÇÏ (ÐÒÏÄÏÌÖÉÔØ ÏÚÎÁÞÁÅÔ,
ÞÔÏ ÅÓÌÉ x 6 y × ÉÓÈÏÄÎÏÍ ÐÏÒÑÄËÅ, ÔÏ É × ÎÏ×ÏÍ ÜÔÏ ÏÓÔÁÎÅÔÓÑ ÔÁË).
  úÁÄÁÞÁ 81. äÁÎÏ ÂÅÓËÏÎÅÞÎÏÅ ÞÁÓÔÉÞÎÏ ÕÐÏÒÑÄÏÞÅÎÎÏÅ ÍÎÏÖÅÓÔ×Ï X.
äÏËÁÖÉÔÅ, ÞÔÏ × Î¾Í ×ÓÅÇÄÁ ÎÁÊľÔÓÑ ÌÉÂÏ ÂÅÓËÏÎÅÞÎÏÅ ÐÏÄÍÎÏÖÅÓÔ×Ï
ÐÏÐÁÒÎÏ ÎÅÓÒÁ×ÎÉÍÙÈ ÜÌÅÍÅÎÔÏ×, ÌÉÂÏ ÂÅÓËÏÎÅÞÎÏÅ ÐÏÄÍÎÏÖÅÓÔ×Ï, ÎÁ ËÏ-
ÔÏÒÏÍ ÉÎÄÕÃÉÒÏ×ÁÎÎÙÊ ÐÏÒÑÄÏË ÌÉÎÅÅÎ.
   úÁÄÁÞÁ 82. (ëÏÎÅÞÎÙÊ ×ÁÒÉÁÎÔ ÐÒÅÄÙÄÕÝÅÊ ÚÁÄÁÞÉ.) äÁÎÙ ÃÅÌÙÅ ÐÏ-
ÌÏÖÉÔÅÌØÎÙÅ ÞÉÓÌÁ m É n. äÏËÁÖÉÔÅ, ÞÔÏ ×Ï ×ÓÑËÏÍ ÞÁÓÔÉÞÎÏ ÕÐÏÒÑÄÏ-
ÞÅÎÎÏÍ ÍÎÏÖÅÓÔ×Å ÍÏÝÎÏÓÔÉ mn + 1 ÍÏÖÎÏ ÕËÁÚÁÔØ ÌÉÂÏ m + 1 ÐÏÐÁÒÎÏ
ÎÅÓÒÁ×ÎÉÍÙÈ ÜÌÅÍÅÎÔÏ×, ÌÉÂÏ n + 1 ÐÏÐÁÒÎÏ ÓÒÁ×ÎÉÍÙÈ.
   úÁÄÁÞÁ 83. ÷ ÓÔÒÏÞËÕ ÎÁÐÉÓÁÎÙ mn + 1 ÒÁÚÌÉÞÎÙÈ ÞÉÓÅÌ. äÏËÁÖÉÔÅ,
ÞÔÏ ÍÏÖÎÏ ÞÁÓÔØ ÉÚ ÎÉÈ ×ÙÞÅÒËÎÕÔØ ÔÁË, ÞÔÏÂÙ ÏÓÔÁÌÁÓØ ÌÉÂÏ ×ÏÚÒÁ-
ÓÔÁÀÝÁÑ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ ÄÌÉÎÙ m + 1, ÌÉÂÏ ÕÂÙ×ÁÀÝÁÑ ÐÏÓÌÅÄÏ×Á-
ÔÅÌØÎÏÓÔØ ÄÌÉÎÙ n + 1. (õËÁÚÁÎÉÅ: ÍÏÖÎÏ ×ÏÓÐÏÌØÚÏ×ÁÔØÓÑ ÐÒÅÄÙÄÕÝÅÊ
ÚÁÄÁÞÅÊ.)
   úÁÄÁÞÁ 84. òÁÓÓÍÏÔÒÉÍ ÓÅÍÅÊÓÔ×Ï ×ÓÅÈ ÐÏÄÍÎÏÖÅÓÔ× ÎÁÔÕÒÁÌØÎÏÇÏ
ÒÑÄÁ, ÕÐÏÒÑÄÏÞÅÎÎÏÅ ÐÏ ×ËÌÀÞÅÎÉÀ. óÕÝÅÓÔ×ÕÅÔ ÌÉ Õ ÎÅÇÏ ÌÉÎÅÊÎÏ ÕÐÏ-
ÒÑÄÏÞÅÎÎÏÅ (× ÉÎÄÕÃÉÒÏ×ÁÎÎÏÍ ÐÏÒÑÄËÅ) ÐÏÄÓÅÍÅÊÓÔ×Ï ÍÏÝÎÏÓÔÉ ËÏÎÔÉ-
ÎÕÕÍ? óÕÝÅÓÔ×ÕÅÔ ÌÉ Õ ÎÅÇÏ ÐÏÄÓÅÍÅÊÓÔ×Ï ÍÏÝÎÏÓÔÉ ËÏÎÔÉÎÕÕÍ, ÌÀÂÙÅ
Ä×Á ÜÌÅÍÅÎÔÁ ËÏÔÏÒÏÇÏ ÎÅÓÒÁ×ÎÉÍÙ?
   üÌÅÍÅÎÔ ÞÁÓÔÉÞÎÏ ÕÐÏÒÑÄÏÞÅÎÎÏÇÏ ÍÎÏÖÅÓÔ×Á ÎÁÚÙ×ÁÀÔ ÎÁÉÂÏÌØÛÉÍ, ÅÓ-
ÌÉ ÏÎ ÂÏÌØÛÅ ÌÀÂÏÇÏ ÄÒÕÇÏÇÏ ÜÌÅÍÅÎÔÁ, É ÍÁËÓÉÍÁÌØÎÙÍ, ÅÓÌÉ ÎÅ ÓÕÝÅÓÔ×Õ-
ÅÔ ÂÏÌØÛÅÇÏ ÜÌÅÍÅÎÔÁ. åÓÌÉ ÍÎÏÖÅÓÔ×Ï ÎÅ Ñ×ÌÑÅÔÓÑ ÌÉÎÅÊÎÏ ÕÐÏÒÑÄÏÞÅÎ-
ÎÙÍ, ÔÏ ÜÔÏ ÎÅ ÏÄÎÏ É ÔÏ ÖÅ: ÎÁÉÂÏÌØÛÉÊ ÜÌÅÍÅÎÔ Á×ÔÏÍÁÔÉÞÅÓËÉ Ñ×ÌÑÅÔÓÑ
ÍÁËÓÉÍÁÌØÎÙÍ, ÎÏ ÎÅ ÎÁÏÂÏÒÏÔ. (ïÄÎÏ ÄÅÌÏ ËÏÒÏÂËÁ, × ËÏÔÏÒÕÀ ÐÏÍÅÝÁÅÔÓÑ
ÌÀÂÁÑ ÄÒÕÇÁÑ, ÄÒÕÇÏÅ ¡ ËÏÒÏÂËÁ, ËÏÔÏÒÁÑ ÎÉËÕÄÁ ÂÏÌØÛÅ ÎÅ ÐÏÍÅÝÁÅÔÓÑ.)
   áÎÁÌÏÇÉÞÎÙÍ ÏÂÒÁÚÏÍ ÏÐÒÅÄÅÌÑÀÔÓÑ ÎÁÉÍÅÎØÛÉÅ É ÍÉÎÉÍÁÌØÎÙÅ ÜÌÅ-
ÍÅÎÔÙ.
   ìÅÇËÏ ÐÏÎÑÔØ, ÞÔÏ ÎÁÉÂÏÌØÛÉÊ ÜÌÅÍÅÎÔ × ÄÁÎÎÏÍ ÞÁÓÔÉÞÎÏ ÕÐÏÒÑÄÏÞÅÎ-
ÎÏÍ ÍÎÏÖÅÓÔ×Å ÍÏÖÅÔ ÂÙÔØ ÔÏÌØËÏ ÏÄÉÎ, × ÔÏ ×ÒÅÍÑ ËÁË ÍÁËÓÉÍÁÌØÎÙÈ
ÜÌÅÍÅÎÔÏ× ÍÏÖÅÔ ÂÙÔØ ÍÎÏÇÏ.
   úÁÄÁÞÁ 85. äÏËÁÖÉÔÅ, ÞÔÏ ÌÀÂÙÅ Ä×Á ÍÁËÓÉÍÁÌØÎÙÈ ÜÌÅÍÅÎÔÁ ÎÅ
ÓÒÁ×ÎÉÍÙ. äÏËÁÖÉÔÅ, ÞÔÏ × ËÏÎÅÞÎÏÍ ÞÁÓÔÉÞÎÏ ÕÐÏÒÑÄÏÞÅÎÎÏÍ ÍÎÏ-
ÖÅÓÔ×Å X ÄÌÑ ÌÀÂÏÇÏ ÜÌÅÍÅÎÔÁ x ÎÁÊľÔÓÑ ÍÁËÓÉÍÁÌØÎÙÊ ÜÌÅÍÅÎÔ y,
ÂÏÌØÛÉÊ ÉÌÉ ÒÁ×ÎÙÊ x.

Страницы