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

UptoLike

ВУЗ: 

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

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

Рубрика: 

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.)
236                                                                  úÁÄÁÞÉ

   ðÏ ÓÌÏ×ÅÓÎÏÍÕ ÏÐÉÓÁÎÉÀ ÍÁÛÉÎ T3, T4, . . . ÐÏÓÔÒÏÉÔØ ÉÈ ÐÒÏÇÒÁÍÍÙ c
×ÎÅÛÎÉÍ ÁÌÆÁ×ÉÔÏÍ {0, 1, ∧}:
   472. T3 ¡ ÎÁÞÉÎÁÑ Ó ÐÏÓÌÅÄÎÅÊ ÅÄÉÎÉÃÙ ÍÁÓÓÉ×Á ÉÚ ÅÄÉÎÉÃ, ¤ÓÄ×ÉÇÁÅÔ¥
ÅÇÏ ÎÁ ÏÄÎÕ ÑÞÅÊËÕ ×ÌÅ×Ï É ÏÓÔÁÎÁ×ÌÉ×ÁÅÔÓÑ ÎÁ ÐÅÒ×ÏÊ ÅÄÉÎÉÃÅ;
   473. T4 ¡ ÐÒÉ ÚÁÄÁÎÎÏÍ l > 1 óúõ ÍÁÛÉÎÙ, ÎÁÞÁ× Ó ÐÒÏÉÚ×ÏÌØÎÏÊ ÑÞÅÊËÉ,
ÚÁÐÏÌÎÅÎÎÏÊ ÅÄÉÎÉÃÅÊ, Ä×ÉÖÅÔÓÑ ×ÐÒÁ×Ï, ÎÅ ÍÅÎÑÑ ÓÏÄÅÒÖÉÍÏÇÏ ÑÞÅÅË, ÄÏ
ÔÅÈ ÐÏÒ ÐÏËÁ ÎÅ ÐÒÏÊÄ¾Ô ÍÁÓÓÉ× ÉÚ l + 1 ÎÕÌÑ; óúõ ÏÓÔÁÎÁ×ÌÉ×ÁÅÔÓÑ ÎÁ
ÓÌÅÄÕÀÝÅÊ ÑÞÅÊËÅ, ÐÏÍÅÓÔÉ× ÔÕÄÁ ÅÄÉÎÉÃÕ;
   474. T5 ¡ ÐÒÉ ÚÁÄÁÎÎÏÍ l > 1 óúõ, ÎÁÞÁ× Ó ÐÒÏÉÚ×ÏÌØÎÏÊ ÑÞÅÊËÉ É Ä×É-
ÇÁÑÓØ ×ÐÒÁ×Ï, ÐÒÏÓÔÁ×ÌÑÅÔ ÐÏÄÒÑÄ l ÅÄÉÎÉÃ É ÏÓÔÁÎÁ×ÌÉ×ÁÅÔÓÑ ÎÁ ÐÏÓÌÅÄÎÅÊ
ÉÚ ÎÉÈ;
   475. T6 ¡ ÍÁÛÉÎÁ ÎÁÞÉÎÁÅÔ ÒÁÂÏÔÕ Ó ËÒÁÊÎÅÊ ÓÌÅ×Á ÎÅÐÕÓÔÏÊ ÑÞÅÊËÉ
ÐÒÏÉÚ×ÏÌØÎÏÇÏ ÓÌÏ×Á, ÐÒÉ ÚÁÄÁÎÎÏÍ l > 1 ÏÔÙÓËÉ×ÁÅÔ × ÓÌÏ×Å ÐÅÒ×ÙÊ ÓÌÅ×Á
ÍÁÓÓÉ× ÉÚ l + 1 ÎÕÌÑ É ÏÓÔÁÎÁ×ÌÉ×ÁÅÔÓÑ ÎÁ ÐÏÓÌÅÄÎÅÍ ÉÚ ÎÉÈ (ÓÏÄÅÒÖÉÍÏÅ
ÑÞÅÅË ÎÅ ÍÅÎÑÅÔÓÑ);
   476. T7 ¡ ÎÁÞÁ× ÒÁÂÏÔÕ Ó ÓÁÍÏÊ ÌÅ×ÏÊ ÎÅÐÕÓÔÏÊ ÑÞÅÊËÉ, ÍÁÛÉÎÁ ÏÔÙÓËÉ-
×ÁÅÔ ÅÄÉÎÉÃÕ, ÐÒÉÍÙËÁÀÝÕÀ ÓÌÅ×Á Ë ÐÅÒ×ÏÍÕ ÓÌÅ×Á ÍÁÓÓÉ×Õ ÉÚ ÔÒ¾È ÎÕÌÅÊ,
¤ÏËÁÊÍ̾ÎÎÏÍÕ¥ ÅÄÉÎÉÃÁÍÉ, óúõ ÏÓÔÁÎÁ×ÌÉ×ÁÅÔÓÑ ÎÁ ÎÁÊÄÅÎÎÏÊ ÅÄÉÎÉÃÅ
(ÓÏÄÅÒÖÉÍÏÅ ÑÞÅÅË ÎÅ ÍÅÎÑÅÔÓÑ);
   477. T8 ¡ × ÉÓÈÏÄÎÏÊ ÑÞÅÊËÅ ÐÅÞÁÔÁÅÔ ÎÕÌØ, óúõ ÓÄ×ÉÇÁÅÔÓÑ ÎÁ ÏÄÎÕ
ÑÞÅÊËÕ ×ÌÅ×Ï É ÍÁÛÉÎÁ ÏÓÔÁÎÁ×ÌÉ×ÁÅÔÓÑ.
   478. T9 ¡ óúõ ÍÁÛÉÎÙ ÓÄ×ÉÇÁÅÔÓÑ ÎÁ Ä×Å ÑÞÅÊËÉ ×ÐÒÁ×Ï ÏÔ ÎÁÞÁÌØÎÏÊ,
ÍÁÛÉÎÁ ÏÓÔÁÎÁ×ÌÉ×ÁÅÔÓÑ × ÓÏÓÔÏÑÎÉÉ q0 , ÅÓÌÉ ÜÔÁ ÑÞÅÊËÁ ÓÏÄÅÒÖÉÔ ÎÕÌØ, ×
ÓÏÓÔÏÑÎÉÉ q00 , ÅÓÌÉ ÜÔÁ ÑÞÅÊËÁ ÓÏÄÅÒÖÉÔ ÅÄÉÎÉÃÕ.
   479. T10 ¡ óúõ ÐÅÒÅÄ×ÉÇÁÅÔÓÑ ÎÁ ÏÄÎÕ ÑÞÅÊËÕ ×ÌÅ×Ï É ÍÁÛÉÎÁ ÏÓÔÁÎÁ-
×ÌÉ×ÁÅÔÓÑ;
   480. T11 ¡ ÏÔÐÒÁ×ÌÑÑÓØ ÏÔ ÎÁÞÁÌØÎÏÊ ÑÞÅÊËÉ, ÎÁÈÏÄÉÔ ÐÅÒ×ÕÀ ÅÄÉÎÉÃÕ
É ÏÓÔÁÎÁ×ÌÉ×ÁÅÔÓÑ ÎÁ ÓÌÅÄÕÀÝÅÊ ÚÁ ÎÅÊ ÑÞÅÊËÅ.
   481. îÁÊÄÉÔÅ ËÏÍÐÏÚÉÃÉÉ ÍÁÛÉÎ: T4 ◦ T3 , T6 ◦ T7 , T11 ◦ T10 ◦ T5. (íÁÛÉÎÙ
T3, T4, . . . ÓÍ. × ÐÒÉÍÅÒÁÈ 472 ¡ 480.)

Страницы