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

§2. ÷ÔÏÒÏÅ ÄÏËÁÚÁÔÅÌØÓÔ×Ï ÔÅÏÒÅÍÙ Ï ÐÏÌÎÏÔÅ                           93

  §2. ÷ÔÏÒÏÅ ÄÏËÁÚÁÔÅÌØÓÔ×Ï ÔÅÏÒÅÍÙ Ï ÐÏÌÎÏÔÅ
   üÔÏ ÄÏËÁÚÁÔÅÌØÓÔ×Ï, × ÏÔÌÉÞÉÅ ÏÔ ÐÒÅÄÙÄÕÝÅÇÏ, ÏÂÏÂÝÁÅÔÓÑ ÎÁ ÂÏÌÅÅ
ÓÌÏÖÎÙÅ ÓÌÕÞÁÉ (ÉÓÞÉÓÌÅÎÉÅ ÐÒÅÄÉËÁÔÏ×, ÉÎÔÕÉÃÉÏÎÉÓÔÓËÏÅ ÉÓÞÉÓÌÅÎÉÅ ×Ù-
ÓËÁÚÙ×ÁÎÉÊ). îÁÞÎ¾Í Ó ÔÁËÏÇÏ ÏÐÒÅÄÅÌÅÎÉÑ: ÍÎÏÖÅÓÔ×Ï ÆÏÒÍÕÌ • ÎÁÚÙ×ÁÅÔ-
ÓÑ ÓÏ×ÍÅÓÔÎÙÍ, ÅÓÌÉ ÓÕÝÅÓÔ×ÕÅÔ ÎÁÂÏÒ ÚÎÁÞÅÎÉÊ ÐÅÒÅÍÅÎÎÙÈ, ÐÒÉ ËÏÔÏÒÙÈ
×ÓÅ ÆÏÒÍÕÌÙ ÉÚ • ÉÓÔÉÎÎÙ. úÁÍÅÔÉÍ, ÞÔÏ ÆÏÒÍÕÌÁ ϕ Ñ×ÌÑÅÔÓÑ ÔÁ×ÔÏÌÏ-
ÇÉÅÊ ÔÏÇÄÁ É ÔÏÌØËÏ ÔÏÇÄÁ, ËÏÇÄÁ ÍÎÏÖÅÓÔ×Ï, ÓÏÓÔÏÑÝÅÅ ÉÚ ÅÄÉÎÓÔ×ÅÎÎÏÊ
ÆÏÒÍÕÌÙ ¬ϕ, ÎÅ Ñ×ÌÑÅÔÓÑ ÓÏ×ÍÅÓÔÎÙÍ. äÌÑ ÓÌÕÞÁÑ ÏÄÎÏÊ ÆÏÒÍÕÌÙ ÅÓÔØ
ÓÐÅÃÉÁÌØÎÙÊ ÔÅÒÍÉÎ: ÆÏÒÍÕÌÁ τ ×ÙÐÏÌÎÉÍÁ, ÅÓÌÉ ÓÕÝÅÓÔ×ÕÀÔ ÚÎÁÞÅÎÉÑ ÐÅ-
ÒÅÍÅÎÎÙÈ, ÐÒÉ ËÏÔÏÒÙÈ ÏÎÁ ÉÓÔÉÎÎÁ, ÔÏ ÅÓÔØ ÅÓÌÉ ÍÎÏÖÅÓÔ×Ï {τ } ÓÏ×ÍÅÓÔÎÏ.
ôÁ×ÔÏÌÏÇÉÉ ¡ ÜÔÏ ÆÏÒÍÕÌÙ, ÏÔÒÉÃÁÎÉÑ ËÏÔÏÒÙÈ ÎÅ ×ÙÐÏÌÎÉÍÙ.
   íÎÏÖÅÓÔ×Ï ÆÏÒÍÕÌ • ÎÁÚÙ×ÁÅÔÓÑ ÐÒÏÔÉ×ÏÒÅÞÉ×ÙÍ, ÅÓÌÉ ÉÚ ÎÅÇÏ ÏÄÎÏ-
×ÒÅÍÅÎÎÏ ×Ù×ÏÄÑÔÓÑ ÆÏÒÍÕÌÙ A É ¬A. íÙ ÚÎÁÅÍ, ÞÔÏ × ÜÔÏÍ ÓÌÕÞÁÅ ÉÚ ÎÅÇÏ
×Ù×ÏÄÑÔÓÑ ×ÏÏÂÝÅ ×ÓÅ ÆÏÒÍÕÌÙ, ÓÍ 1. (÷ ÐÒÏÔÉ×ÎÏÍ ÓÌÕÞÁÅ • ÎÁÚÙ×ÁÅÔÓÑ
ÎÅÐÒÏÔÉ×ÏÒÅÞÉ×ÙÍ.)
  ôÅÏÒÅÍÁ 34 (ËÏÒÒÅËÔÎÏÓÔØ ÉÓÞÉÓÌÅÎÉÑ ×ÙÓËÁÚÙ×ÁÎÉÊ, ×ÔÏÒÁÑ ÆÏÒÍÁ).
÷ÓÑËÏÅ ÓÏ×ÍÅÓÔÎÏÅ ÍÎÏÖÅÓÔ×Ï ÆÏÒÍÕÌ ÎÅÐÒÏÔÉ×ÏÒÅÞÉ×Ï.
   äÏËÁÚÁÔÅÌØÓÔ×Ï. ÷ ÓÁÍÏÍ ÄÅÌÅ, ÐÕÓÔØ ÓÏ×ÍÅÓÔÎÏÅ ÍÎÏÖÅÓÔ×Ï • ÐÒÏÔÉ-
×ÏÒÅÞÉ×Ï. ôÁË ËÁË ÏÎÏ ÓÏ×ÍÅÓÔÎÏ, ÓÕÝÅÓÔ×ÕÀÔ ÚÎÁÞÅÎÉÑ ÐÅÒÅÍÅÎÎÙÈ, ÐÒÉ
ËÏÔÏÒÙÈ ×ÓÅ ÆÏÒÍÕÌÙ ÉÚ • ÉÓÔÉÎÎÙ. ó ÄÒÕÇÏÊ ÓÔÏÒÏÎÙ, ÉÚ • ×Ù×ÏÄÉÔÓÑ
ÎÅËÏÔÏÒÁÑ ÆÏÒÍÕÌÁ B É Å¾ ÏÔÒÉÃÁÎÉÅ. íÏÖÅÔ ÌÉ ÔÁË ÂÙÔØ?
   ïËÁÚÙ×ÁÅÔÓÑ, ÞÔÏ ÎÅÔ. íÙ ÕÖÅ ×ÉÄÅÌÉ, ÞÔÏ ×ÓÑËÁÑ ×Ù×ÏÄÉÍÁÑ ÆÏÒÍÕÌÁ
ÉÓÔÉÎÎÁ ÐÒÉ ×ÓÅÈ ÚÎÁÞÅÎÉÑÈ ÐÅÒÅÍÅÎÎÙÈ (Ñ×ÌÑÅÔÓÑ ÔÁ×ÔÏÌÏÇÉÅÊ). óÐÒÁ×ÅÄ-
ÌÉ×Ï É ÎÅÓËÏÌØËÏ ÂÏÌÅÅ ÏÂÝÅÅ ÕÔ×ÅÒÖÄÅÎÉÅ: ÅÓÌÉ • ` A É ÐÒÉ ÎÅËÏÔÏÒÙÈ
ÚÎÁÞÅÎÉÑÈ ÐÅÒÅÍÅÎÎÙÈ ×ÓÅ ÆÏÒÍÕÌÙ ÉÚ • ÉÓÔÉÎÎÙ, ÔÏ É ÆÏÒÍÕÌÁ A ÉÓÔÉÎÎÁ
ÐÒÉ ÜÔÉÈ ÚÎÁÞÅÎÉÑÈ ÐÅÒÅÍÅÎÎÙÈ. (ëÁË É ÒÁÎØÛÅ, ÜÔÏ ÌÅÇËÏ ÄÏËÁÚÙ×ÁÅÔÓÑ
ÉÎÄÕËÃÉÅÊ ÐÏ ÐÏÓÔÒÏÅÎÉÀ ×Ù×ÏÄÁ A ÉÚ •.)
   ÷ ÎÁÛÅÊ ÓÉÔÕÁÃÉÉ ÜÔÏ ÐÒÉ×ÏÄÉÔ Ë ÔÏÍÕ, ÞÔÏ ÎÁ ×ÙÐÏÌÎÑÀÝÅÍ ÎÁÂÏÒÅ
ÚÎÁÞÅÎÉÊ ÐÅÒÅÍÅÎÎÙÈ ÄÌÑ • ÄÏÌÖÎÙ ÂÙÔØ ÉÓÔÉÎÎÙ ÏÂÅ ÆÏÒÍÕÌÙ B É ¬B,
ÞÔÏ, ÒÁÚÕÍÅÅÔÓÑ, ÎÅ×ÏÚÍÏÖÎÏ.
   íÙ ÎÁÚÙ×ÁÅÍ ÜÔÏ ÕÔ×ÅÒÖÄÅÎÉÅ ÄÒÕÇÏÊ ÆÏÒÍÏÊ ÔÅÏÒÅÍÙ Ï ËÏÒÒÅËÔÎÏÓÔÉ
ÉÓÞÉÓÌÅÎÉÑ ×ÙÓËÁÚÙ×ÁÎÉÊ, ÐÏÓËÏÌØËÕ ÉÚ ÎÅÇÏ ÆÏÒÍÁÌØÎÏ ÍÏÖÎÏ ×Ù×ÅÓÔÉ,
ÞÔÏ ×ÓÑËÁÑ ÔÅÏÒÅÍÁ Ñ×ÌÑÅÔÓÑ ÔÁ×ÔÏÌÏÇÉÅÊ: ÅÓÌÉ A ¡ ÔÅÏÒÅÍÁ, ÔÏ ÍÎÏÖÅÓÔ-
×Ï {¬A} ÐÒÏÔÉ×ÏÒÅÞÉ×Ï (ÉÚ ÎÅÇÏ ×Ù×ÏÄÑÔÓÑ A É ¬A), ÐÏÔÏÍÕ ÎÅÓÏ×ÍÅÓÔÎÏ,
ÚÎÁÞÉÔ, ¬A ×ÓÅÇÄÁ ÌÏÖÎÁ, ÐÏÜÔÏÍÕ A ×ÓÅÇÄÁ ÉÓÔÉÎÎÁ.
   ôÅÏÒÅÍÁ 35 (ÐÏÌÎÏÔÁ ÉÓÞÉÓÌÅÎÉÑ ×ÙÓËÁÚÙ×ÁÎÉÊ, ×ÔÏÒÁÑ ÆÏÒÍÁ). ìÀ-
ÂÏÅ ÎÅÐÒÏÔÉ×ÏÒÅÞÉ×ÏÅ ÍÎÏÖÅÓÔ×Ï ÓÏ×ÍÅÓÔÎÏ.