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

UptoLike

ВУЗ: 

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

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

Рубрика: 

62 çÌÁ×Á III. ìÏÇÉËÁ ×ÙÓËÁÚÙ×ÁÎÉÊ
ÎÅÓÏ×ÅÒÛÅÎÎÏ¥ ÒÁ×ÎÏÓÉÌØÎÙ. èÏÔÑ ÏÎÏ É ÏÞÅ×ÉÄÎÏ ÐÒÏ×ÅÒÑÅÔÓÑ Ó ÐÏÍÏÝØÀ
ÔÁÂÌÉà ÉÓÔÉÎÎÏÓÔÉ, Ó ÎÉÍ Ó×ÑÚÁÎÙ ÌÀÂÏÐÙÔÎÙÅ ÐÁÒÁÄÏËÓÙ. ÷ÏÔ ÏÄÉÎ ÉÚ
ÎÉÈ.
âÉÏÌÏÇ á ×ÙÄ×ÉÎÕÌ ÇÉÐÏÔÅÚÕ: ×ÓÅ ×ÏÒÏÎÙ Þ¾ÒÎÙÅ. ðÒÏ×ÅÒÑÑ Å¾, ÏÎ ×ÙÛÅÌ
×Ï Ä×ÏÒ É ÏÂÎÁÒÕÖÉÌ ÎÁ ÄÅÒÅ×Å ×ÏÒÏÎÕ. ïÎÁ ÏËÁÚÁÌÏÓØ Þ¾ÒÎÏÊ. âÉÏÌÏÇ á ÒÁ-
ÄÕÅÔÓÑ ¡ ÇÉÐÏÔÅÚÁ ÐÏÄÔ×ÅÒÖÄÁÅÔÓÑ. âÉÏÌÏÇ â ÐÅÒÅÆÏÒÍÕÌÉÒÏ×ÁÌ ÇÉÐÏÔÅÚÕ
ÔÁË: ×ÓÅ ÎÅ-Þ¾ÒÎÙÅ ÐÒÅÄÍÅÔÙ ¡ ÎÅ ×ÏÒÏÎÙ (ÐÒÉÍÅÎÉ× ÎÁÛÅ ÐÒÁ×ÉÌÏ ËÏÎ-
ÔÒÁÐÏÚÉÃÉÉ) É ÎÅ ÓÔÁÌ ×ÙÈÏÄÉÔØ ×Ï Ä×ÏÒ, Á ÏÔËÒÙÌ ÈÏÌÏÄÉÌØÎÉË É ÎÁÛ¾Ì
ÔÁÍ ÏÒÁÎÖÅ×ÙÊ ÐÒÅÄÍÅÔ. ïÎ ÏËÁÚÁÌÓÑ ÁÐÅÌØÓÉÎÏÍ, Á ÎÅ ×ÏÒÏÎÏÊ. âÉÏÌÏÇ â
ÏÂÒÁÄÏ×ÁÌÓÑ ¡ ÇÉÐÏÔÅÚÁ ÐÏÄÔ×ÅÒÖÄÁÅÔÓÑ ¡ É ÐÏÚ×ÏÎÉÌ ÂÉÏÌÏÇÕ á. ôÏÔ ÕÄÉ-
×ÌÑÅÔÓÑ ¡ Õ ÎÅÇÏ ÔÏÖÅ ÅÓÔØ ÁÐÅÌØÓÉÎ × ÈÏÌÏÄÉÌØÎÉËÅ, ÎÏ Ó ÅÇÏ ÔÏÞËÉ ÚÒÅÎÉÑ
ÎÉËÁËÏÇÏ ÏÔÎÏÛÅÎÉÑ Ë ÅÇÏ ÇÉÐÏÔÅÚÅ ÁÐÅÌØÓÉÎ ÎÅ ÉÍÅÅÔ . . .
äÒÕÇÏÊ ÐÁÒÁÄÏËÓ: Ó ÔÏÞËÉ ÚÒÅÎÉÑ ÆÏÒÍÁÌØÎÏÊ ÌÏÇÉËÉ ÕÔ×ÅÒÖÄÅÎÉÑ ¥ËÔÏ
ÎÅ Ó ÎÁÍÉ, ÔÏÔ ÐÒÏÔÉ× ÎÁÓ¥ É ¥ËÔÏ ÎÅ ÐÒÏÔÉ× ÎÁÓ, ÔÏÔ Ó ÎÁÍÉ¥ ÒÁ×ÎÏÓÉÌØÎÙ.
ðÏÓÌÅÄÎÅÅ (É ÏÞÅ×ÉÄÎÏÅ) ÐÒÁ×ÉÌÏ p ↔ ¬¬p ÎÁÚÙ×ÁÅÔÓÑ ÓÎÑÔÉÅÍ Ä×ÏÊÎÏÇÏ
ÏÔÒÉÃÁÎÉÑ.
úÁÄÁÞÁ 103. ðÅÒÅÞÉÓÌÅÎÎÙÅ ÜË×É×ÁÌÅÎÔÎÏÓÔÉ ÓÏÏÔ×ÅÔÓÔ×ÕÀÔ ÒÁ×ÅÎ-
ÓÔ×ÁÍ ÄÌÑ ÍÎÏÖÅÓÔ×: ÎÁÐÒÉÍÅÒ, ÐÅÒ×ÁÑ ÇÁÒÁÎÔÉÒÕÅÔ, ÞÔÏ P ∩ Q = Q ∩
∩ P ÄÌÑ ÌÀÂÙÈ ÍÎÏÖÅÓÔ× P É Q. ëÁËÉÅ ÕÔ×ÅÒÖÄÅÎÉÑ ÓÏÏÔ×ÅÔÓÔ×ÕÀÔ
ÏÓÔÁÌØÎÙÍ ÜË×É×ÁÌÅÎÔÎÏÓÔÑÍ?
úÁÄÁÞÁ 104. ä×Å ÆÏÒÍÕÌÙ, ÓÏÄÅÒÖÁÝÉÅ ÔÏÌØËÏ ÐÅÒÅÍÅÎÎÙÅ É Ó×ÑÚËÉ ∧,
∨ É ¬, ÜË×É×ÁÌÅÎÔÎÙ. äÏËÁÖÉÔÅ, ÞÔÏ ÏÎÉ ÏÓÔÁÎÕÔÓÑ ÜË×É×ÁÌÅÎÔÎÙÍÉ,
ÅÓÌÉ ×ÓÀÄÕ ÚÁÍÅÎÉÔØ ∧ ÎÁ ∨ É ÎÁÏÂÏÒÏÔ.
äÁÌÅËÏ ÎÅ ×ÓÅ ÔÁ×ÔÏÌÏÇÉÉ ÉÍÅÀÔ ÑÓÎÙÊ ÉÎÔÕÉÔÉ×ÎÙÊ ÓÍÙÓÌ. îÁÐÒÉÍÅÒ,
ÆÏÒÍÕÌÁ (p → q)∨(q → p) Ñ×ÌÑÅÔÓÑ ÔÁ×ÔÏÌÏÇÉÅÊ (ÅÓÌÉ ÏÄÎÏ ÉÚ ÕÔ×ÅÒÖÄÅÎÉÊ
p É q ÌÏÖÎÏ, ÔÏ ÉÚ ÎÅÇÏ ÓÌÅÄÕÅÔ ×Ó¾, ÞÔÏ ÕÇÏÄÎÏ; ÅÓÌÉ ÏÂÁ ÉÓÔÉÎÎÙ, ÔÏ ÔÅÍ
ÂÏÌÅÅ ÆÏÒÍÕÌÁ ÉÓÔÉÎÎÁ), ÈÏÔÑ É ÏÔÞÁÓÔÉ ÐÒÏÔÉ×ÏÒÅÞÉÔ ÎÁÛÅÊ ÉÎÔÕÉÃÉÉ ¡
ÐÏÞÅÍÕ, ÓÏÂÓÔ×ÅÎÎÏ, ÉÚ Ä×ÕÈ ÎÉËÁË ÎÅ Ó×ÑÚÁÎÎÙÈ ÕÔ×ÅÒÖÄÅÎÉÊ ÏÄÎÏ ×ÌÅÞ¾Ô
ÄÒÕÇÏÅ? åݾ ÂÏÌÅÅ ÚÁÇÁÄÏÞÎÁ ÔÁ×ÔÏÌÏÇÉÑ
((p → q) → p) → p
(ÈÏÔÑ Å¾ ÎÉÞÅÇÏ ÎÅ ÓÔÏÉÔ ÐÒÏ×ÅÒÉÔØ Ó ÐÏÍÏÝØÀ ÔÁÂÌÉà ÉÓÔÉÎÎÏÓÔÉ).
ïÔÓÔÕÐÌÅÎÉÅ Ï ÐÏÌØÚÅ ÓËÏÂÏË. îÁ ÓÁÍÏÍ ÄÅÌÅ ÎÁÛÅ ÏÐÒÅÄÅÌÅÎÉÅ ÉÓÔÉÎ-
ÎÏÓÔÉ ÓÏÄÅÒÖÉÔ ÓÅÒؾÚÎÙÊ ÐÒÏÂÅÌ. þÔÏÂÙ ÏÂÎÁÒÕÖÉÔØ ÅÇÏ, ÚÁÄÁÄÉÍ ÓÅÂÅ
×ÏÐÒÏÓ: ÚÁÞÅÍ ÎÕÖÎÙ ÓËÏÂËÉ × ÆÏÒÍÕÌÁÈ? ðÒÅÄÓÔÁ×ÉÍ ÓÅÂÅ, ÞÔÏ ÍÙ ÉÚÍÅ-
ÎÉÍ ÏÐÒÅÄÅÌÅÎÉÅ ÆÏÒÍÕÌÙ, É ÂÕÄÅÍ ÇÏ×ÏÒÉÔØ, ÞÔÏ P ∧ Q É P ∨ Q Ñ×ÌÑÀÔÓÑ
ÆÏÒÍÕÌÁÍÉ ÄÌÑ ÌÀÂÙÈ P É Q. ïÓÔÁÎÕÔÓÑ ÌÉ ÎÁÛÉ ÒÁÓÓÕÖÄÅÎÉÑ × ÓÉÌÅ?
62                                      çÌÁ×Á III. ìÏÇÉËÁ ×ÙÓËÁÚÙ×ÁÎÉÊ

ÎÅÓÏ×ÅÒÛÅÎÎÏ¥ ÒÁ×ÎÏÓÉÌØÎÙ. èÏÔÑ ÏÎÏ É ÏÞÅ×ÉÄÎÏ ÐÒÏ×ÅÒÑÅÔÓÑ Ó ÐÏÍÏÝØÀ
ÔÁÂÌÉà ÉÓÔÉÎÎÏÓÔÉ, Ó ÎÉÍ Ó×ÑÚÁÎÙ ÌÀÂÏÐÙÔÎÙÅ ÐÁÒÁÄÏËÓÙ. ÷ÏÔ ÏÄÉÎ ÉÚ
ÎÉÈ.
   âÉÏÌÏÇ á ×ÙÄ×ÉÎÕÌ ÇÉÐÏÔÅÚÕ: ×ÓÅ ×ÏÒÏÎÙ Þ¾ÒÎÙÅ. ðÒÏ×ÅÒÑÑ Å¾, ÏÎ ×ÙÛÅÌ
×Ï Ä×ÏÒ É ÏÂÎÁÒÕÖÉÌ ÎÁ ÄÅÒÅ×Å ×ÏÒÏÎÕ. ïÎÁ ÏËÁÚÁÌÏÓØ Þ¾ÒÎÏÊ. âÉÏÌÏÇ á ÒÁ-
ÄÕÅÔÓÑ ¡ ÇÉÐÏÔÅÚÁ ÐÏÄÔ×ÅÒÖÄÁÅÔÓÑ. âÉÏÌÏÇ â ÐÅÒÅÆÏÒÍÕÌÉÒÏ×ÁÌ ÇÉÐÏÔÅÚÕ
ÔÁË: ×ÓÅ ÎÅ-Þ¾ÒÎÙÅ ÐÒÅÄÍÅÔÙ ¡ ÎÅ ×ÏÒÏÎÙ (ÐÒÉÍÅÎÉ× ÎÁÛÅ ÐÒÁ×ÉÌÏ ËÏÎ-
ÔÒÁÐÏÚÉÃÉÉ) É ÎÅ ÓÔÁÌ ×ÙÈÏÄÉÔØ ×Ï Ä×ÏÒ, Á ÏÔËÒÙÌ ÈÏÌÏÄÉÌØÎÉË É ÎÁÛ¾Ì
ÔÁÍ ÏÒÁÎÖÅ×ÙÊ ÐÒÅÄÍÅÔ. ïÎ ÏËÁÚÁÌÓÑ ÁÐÅÌØÓÉÎÏÍ, Á ÎÅ ×ÏÒÏÎÏÊ. âÉÏÌÏÇ â
ÏÂÒÁÄÏ×ÁÌÓÑ ¡ ÇÉÐÏÔÅÚÁ ÐÏÄÔ×ÅÒÖÄÁÅÔÓÑ ¡ É ÐÏÚ×ÏÎÉÌ ÂÉÏÌÏÇÕ á. ôÏÔ ÕÄÉ-
×ÌÑÅÔÓÑ ¡ Õ ÎÅÇÏ ÔÏÖÅ ÅÓÔØ ÁÐÅÌØÓÉÎ × ÈÏÌÏÄÉÌØÎÉËÅ, ÎÏ Ó ÅÇÏ ÔÏÞËÉ ÚÒÅÎÉÑ
ÎÉËÁËÏÇÏ ÏÔÎÏÛÅÎÉÑ Ë ÅÇÏ ÇÉÐÏÔÅÚÅ ÁÐÅÌØÓÉÎ ÎÅ ÉÍÅÅÔ . . .
   äÒÕÇÏÊ ÐÁÒÁÄÏËÓ: Ó ÔÏÞËÉ ÚÒÅÎÉÑ ÆÏÒÍÁÌØÎÏÊ ÌÏÇÉËÉ ÕÔ×ÅÒÖÄÅÎÉÑ ¥ËÔÏ
ÎÅ Ó ÎÁÍÉ, ÔÏÔ ÐÒÏÔÉ× ÎÁÓ¥ É ¥ËÔÏ ÎÅ ÐÒÏÔÉ× ÎÁÓ, ÔÏÔ Ó ÎÁÍÉ¥ ÒÁ×ÎÏÓÉÌØÎÙ.
   ðÏÓÌÅÄÎÅÅ (É ÏÞÅ×ÉÄÎÏÅ) ÐÒÁ×ÉÌÏ p ↔ ¬¬p ÎÁÚÙ×ÁÅÔÓÑ ÓÎÑÔÉÅÍ Ä×ÏÊÎÏÇÏ
ÏÔÒÉÃÁÎÉÑ.
  úÁÄÁÞÁ 103. ðÅÒÅÞÉÓÌÅÎÎÙÅ ÜË×É×ÁÌÅÎÔÎÏÓÔÉ ÓÏÏÔ×ÅÔÓÔ×ÕÀÔ ÒÁ×ÅÎ-
ÓÔ×ÁÍ ÄÌÑ ÍÎÏÖÅÓÔ×: ÎÁÐÒÉÍÅÒ, ÐÅÒ×ÁÑ ÇÁÒÁÎÔÉÒÕÅÔ, ÞÔÏ P ∩ Q = Q ∩
∩ P ÄÌÑ ÌÀÂÙÈ ÍÎÏÖÅÓÔ× P É Q. ëÁËÉÅ ÕÔ×ÅÒÖÄÅÎÉÑ ÓÏÏÔ×ÅÔÓÔ×ÕÀÔ
ÏÓÔÁÌØÎÙÍ ÜË×É×ÁÌÅÎÔÎÏÓÔÑÍ?
   úÁÄÁÞÁ 104. ä×Å ÆÏÒÍÕÌÙ, ÓÏÄÅÒÖÁÝÉÅ ÔÏÌØËÏ ÐÅÒÅÍÅÎÎÙÅ É Ó×ÑÚËÉ ∧,
∨ É ¬, ÜË×É×ÁÌÅÎÔÎÙ. äÏËÁÖÉÔÅ, ÞÔÏ ÏÎÉ ÏÓÔÁÎÕÔÓÑ ÜË×É×ÁÌÅÎÔÎÙÍÉ,
ÅÓÌÉ ×ÓÀÄÕ ÚÁÍÅÎÉÔØ ∧ ÎÁ ∨ É ÎÁÏÂÏÒÏÔ.
   äÁÌÅËÏ ÎÅ ×ÓÅ ÔÁ×ÔÏÌÏÇÉÉ ÉÍÅÀÔ ÑÓÎÙÊ ÉÎÔÕÉÔÉ×ÎÙÊ ÓÍÙÓÌ. îÁÐÒÉÍÅÒ,
ÆÏÒÍÕÌÁ (p → q)∨ (q → p) Ñ×ÌÑÅÔÓÑ ÔÁ×ÔÏÌÏÇÉÅÊ (ÅÓÌÉ ÏÄÎÏ ÉÚ ÕÔ×ÅÒÖÄÅÎÉÊ
p É q ÌÏÖÎÏ, ÔÏ ÉÚ ÎÅÇÏ ÓÌÅÄÕÅÔ ×Ó¾, ÞÔÏ ÕÇÏÄÎÏ; ÅÓÌÉ ÏÂÁ ÉÓÔÉÎÎÙ, ÔÏ ÔÅÍ
ÂÏÌÅÅ ÆÏÒÍÕÌÁ ÉÓÔÉÎÎÁ), ÈÏÔÑ É ÏÔÞÁÓÔÉ ÐÒÏÔÉ×ÏÒÅÞÉÔ ÎÁÛÅÊ ÉÎÔÕÉÃÉÉ ¡
ÐÏÞÅÍÕ, ÓÏÂÓÔ×ÅÎÎÏ, ÉÚ Ä×ÕÈ ÎÉËÁË ÎÅ Ó×ÑÚÁÎÎÙÈ ÕÔ×ÅÒÖÄÅÎÉÊ ÏÄÎÏ ×ÌÅÞ¾Ô
ÄÒÕÇÏÅ? åݾ ÂÏÌÅÅ ÚÁÇÁÄÏÞÎÁ ÔÁ×ÔÏÌÏÇÉÑ
                           ((p → q) → p) → p
(ÈÏÔÑ Å¾ ÎÉÞÅÇÏ ÎÅ ÓÔÏÉÔ ÐÒÏ×ÅÒÉÔØ Ó ÐÏÍÏÝØÀ ÔÁÂÌÉà ÉÓÔÉÎÎÏÓÔÉ).

   ïÔÓÔÕÐÌÅÎÉÅ Ï ÐÏÌØÚÅ ÓËÏÂÏË. îÁ ÓÁÍÏÍ ÄÅÌÅ ÎÁÛÅ ÏÐÒÅÄÅÌÅÎÉÅ ÉÓÔÉÎ-
ÎÏÓÔÉ ÓÏÄÅÒÖÉÔ ÓÅÒؾÚÎÙÊ ÐÒÏÂÅÌ. þÔÏÂÙ ÏÂÎÁÒÕÖÉÔØ ÅÇÏ, ÚÁÄÁÄÉÍ ÓÅÂÅ
×ÏÐÒÏÓ: ÚÁÞÅÍ ÎÕÖÎÙ ÓËÏÂËÉ × ÆÏÒÍÕÌÁÈ? ðÒÅÄÓÔÁ×ÉÍ ÓÅÂÅ, ÞÔÏ ÍÙ ÉÚÍÅ-
ÎÉÍ ÏÐÒÅÄÅÌÅÎÉÅ ÆÏÒÍÕÌÙ, É ÂÕÄÅÍ ÇÏ×ÏÒÉÔØ, ÞÔÏ P ∧ Q É P ∨ Q Ñ×ÌÑÀÔÓÑ
ÆÏÒÍÕÌÁÍÉ ÄÌÑ ÌÀÂÙÈ P É Q. ïÓÔÁÎÕÔÓÑ ÌÉ ÎÁÛÉ ÒÁÓÓÕÖÄÅÎÉÑ × ÓÉÌÅ?

Страницы