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

§3. óÈÅÍÙ ÉÚ ÆÕÎËÃÉÏÎÁÌØÎÙÈ ÜÌÅÍÅÎÔÏ×                                   71

   ïÄÎÏÊ ÉÚ ÔÉÐÉÞÎÙÈ ÓÈÅÍ Ñ×ÌÑÅÔÓÑ ÓÈÅÍÁ é-îå, ÏÎÁ ÉÍÅÅÔ Ä×Á ×ÈÏÄÁ É
ÏÄÉÎ ×ÙÈÏÄ. óÉÇÎÁÌ ÎÁ ×ÙÈÏÄÅ Ñ×ÌÑÅÔÓÑ ÏÔÒÉÃÁÎÉÅÍ ËÏÎßÀÎËÃÉÉ ÓÉÇÎÁÌÏ×
ÎÁ ×ÈÏÄÅ. äÒÕÇÉÍÉ ÓÌÏ×ÁÍÉ, ÎÁ ×ÙÈÏÄÅ ÐÏÑ×ÌÑÅÔÓÑ ×ÙÓÏËÉÊ ÐÏÔÅÎÃÉÁÌ (ÓÉÇ-
ÎÁÌ 1) ÔÏÇÄÁ É ÔÏÌØËÏ ÔÏÇÄÁ, ËÏÇÄÁ ÎÁ ÏÄÎÏÍ ÉÚ ×ÈÏÄÏ× ÐÏÔÅÎÃÉÁÌ ÎÉÚËÉÊ (0).
éÚ ÔÁËÏÊ ÓÈÅÍÙ ÌÅÇËÏ ÐÏÌÕÞÉÔØ ÓÈÅÍÕ îå (ÉÚÍÅÎÑÀÝÕÀ ÕÒÏ×ÅÎØ ÓÉÇÎÁÌÁ
ÎÁ ÐÒÏÔÉ×ÏÐÏÌÏÖÎÙÊ), ÓÏÅÄÉÎÉ× ÐÒÏ×ÏÄÏÍ Ä×Á ×ÈÏÄÁ. ðÒÉ ÜÔÏÍ ÎÁ ÏÂÁ ×ÈÏÄÁ
ÐÏÓÔÕÐÁÅÔ ÏÄÉÎ É ÔÏÔ ÖÅ ÓÉÇÎÁÌ, É ÏÐÅÒÁÃÉÑ é ÅÇÏ ÎÅ ÍÅÎÑÅÔ (p∧p = p), Á îå
ÍÅÎÑÅÔ ÎÁ ÐÒÏÔÉ×ÏÐÏÌÏÖÎÙÊ. ÷ÚÑ× Ä×Á ÜÌÅÍÅÎÔÁ é-îå É ÉÓÐÏÌØÚÕÑ ×ÔÏÒÏÊ
ÉÚ ÎÉÈ × ËÁÞÅÓÔ×Å ÜÌÅÍÅÎÔÁ îå, ÉÎ×ÅÒÔÉÒÕÀÝÅÇÏ ÓÉÇÎÁÌ Ó ×ÙÈÏÄÁ ÐÅÒ×ÏÇÏ
ÜÌÅÍÅÎÔÁ, ÐÏÌÕÞÁÅÍ ÓÈÅÍÕ, ËÏÔÏÒÁÑ ÒÅÁÌÉÚÕÅÔ ÆÕÎËÃÉÀ é. á ÅÓÌÉ ÐÏÓÔÁ×ÉÔØ
Ä×Á ÜÌÅÍÅÎÔÁ îå ÐÅÒÅÄ ËÁÖÄÙÍ ÉÚ ×ÈÏÄÏ× ÜÌÅÍÅÎÔÁ é-îå, ÐÏÌÕÞÉÍ ÓÈÅÍÕ,
ÒÅÁÌÉÚÕÀÝÕÀ ÆÕÎËÃÉÀ éìé: ¬(¬p ∧ ¬q) ↔ (p ∨ q).
   ôÅÏÒÅÍÁ 19 Ï ÐÏÌÎÏÔÅ ÓÉÓÔÅÍÙ Ó×ÑÚÏË ÔÅÐÅÒØ ÇÁÒÁÎÔÉÒÕÅÔ, ÞÔÏ ÌÀÂÕÀ
ÂÕÌÅ×Õ ÆÕÎËÃÉÀ ÍÏÖÎÏ ÒÅÁÌÉÚÏ×ÁÔØ × ×ÉÄÅ ÓÈÅÍÙ. îÁÄÏ ÉÍÅÔØ × ×ÉÄÕ, ÏÄ-
ÎÁËÏ, ÞÔÏ ÐÒÅÄÌÁÇÁÅÍÁÑ × Å¾ ÄÏËÁÚÁÔÅÌØÓÔ×Å ËÏÎÓÔÒÕËÃÉÑ (ÄÉÚßÀÎËÔÉ×ÎÁÑ
ÎÏÒÍÁÌØÎÁÑ ÆÏÒÍÁ) ÉÍÅÅÔ ÓËÏÒÅÅ ÔÅÏÒÅÔÉÞÅÓËÉÊ ÉÎÔÅÒÅÓ, ÐÏÓËÏÌØËÕ ÐÒÉ×Ï-
ÄÉÔ Ë ÓÈÅÍÁÍ ÏÞÅÎØ ÂÏÌØÛÏÇÏ ÒÁÚÍÅÒÁ ÄÁÖÅ ÄÌÑ ÐÒÏÓÔÙÈ ÆÕÎËÃÉÊ (ÅÓÌÉ
ÞÉÓÌÏ ÁÒÇÕÍÅÎÔÏ× ×ÅÌÉËÏ). îÁÐÒÉÍÅÒ, ÓÈÅÍÁ, ÓÒÁ×ÎÉ×ÁÀÝÁÑ Ä×Á 16-ÂÉÔÎÙÈ
ÞÉÓÌÁ, ÄÏÌÖÎÁ ÉÍÅÔØ 32 ×ÈÏÄÁ É ÐÏÜÔÏÍÕ × Å¾ ÒÅÁÌÉÚÁÃÉÉ Ó ÐÏÍÏÝØÀ ÄÉÚß-
ÀÎËÔÉ×ÎÏÊ ÎÏÒÍÁÌØÎÏÊ ÆÏÒÍÙ ÂÕÄÅÔ ÐÏÒÑÄËÁ 232 ÜÌÅÍÅÎÔÏ× ¡ ÞÔÏ ÍÁÌÏ
ÒÅÁÌØÎÏ. (íÅÖÄÕ ÔÅÍ ÔÁËÕÀ ÓÈÅÍÕ ÍÏÖÎÏ ÐÏÓÔÒÏÉÔØ ÇÏÒÁÚÄÏ ÐÒÏÝÅ, ÉÚ ÎÅ-
ÓËÏÌØËÉÈ ÓÏÔÅÎ ÜÌÅÍÅÎÔÏ×.)
   ðÏÜÔÏÍÕ ×ÏÐÒÏÓ Ï ÔÏÍ, ÓËÏÌØËÏ ÜÌÅÍÅÎÔÏ× ÎÕÖÎÏ ÄÌÑ ÒÅÁÌÉÚÁÃÉÉ ÔÏÊ ÉÌÉ
ÉÎÏÊ ÆÕÎËÃÉÉ, ÐÒÅÄÓÔÁ×ÌÑÅÔ ÂÏÌØÛÏÊ ÉÎÔÅÒÅÓ ¡ ËÁË ÐÒÁËÔÉÞÅÓËÉÊ, ÔÁË É
ÆÉÌÏÓÏÆÓËÉÊ. (ïÄÎÁ ÉÚ ÃÅÎÔÒÁÌØÎÙÈ ÐÒÏÂÌÅÍ ÍÁÔÅÍÁÔÉËÉ É ÉÎÆÏÒÍÁÔÉËÉ,
ÔÁË ÎÁÚÙ×ÁÅÍÁÑ ¥ÐÒÏÂÌÅÍÁ ÐÅÒÅÂÏÒÁ¥, ÍÏÖÅÔ ÂÙÔØ ÓÆÏÒÍÕÌÉÒÏ×ÁÎÁ × ÜÔÉÈ
ÔÅÒÍÉÎÁÈ.)
   íÙ ÓÅÊÞÁÓ ÄÁÄÉÍ ÂÏÌÅÅ ÆÏÒÍÁÌØÎÏÅ ÏÐÒÅÄÅÌÅÎÉÅ ÓÈÅÍÙ É ÒÅÁÌÉÚÕÅÍÏÊ
ÅÊ ÂÕÌÅ×ÏÊ ÆÕÎËÃÉÉ. îÏ ÐÒÅÖÄÅ ×ÓÅÇÏ ÏÔ×ÅÔÉÍ ÎÁ ÔÁËÏÊ ×ÏÐÒÏÓ ¡ ÐÏÞÅÍÕ
ÍÙ ×ÏÏÂÝÅ ÇÏ×ÏÒÉÍ Ï ÓÈÅÍÁÈ? ÷ÅÄØ ÍÏÖÎÏ ÚÁÐÉÓÁÔØ ËÏÍÐÏÚÉÃÉÀ ÂÕÌÅ×ÙÈ
ÆÕÎËÃÉÊ × ×ÉÄÅ ÆÏÒÍÕÌÙ, ÎÅ ÂÕÄÅÔ ÌÉ ÜÔÏ ÔÏ ÖÅ ÓÁÍÏÅ?
   ïËÁÚÙ×ÁÅÔÓÑ, ÎÅ ÓÏ×ÓÅÍ, É ÒÁÚÎÉÃÕ ÌÅÇËÏ Õ×ÉÄÅÔØ ÎÁ ÐÒÉÍÅÒÅ (ÒÉÓ. 2).

                                g1
                           f          h    h(g1 (f (x)), g2(f (x)))
                                g2

              òÉÓ. 2. üÌÅÍÅÎÔ ×ÈÏÄÉÔ × ÆÏÒÍÕÌÕ Ä×ÁÖÄÙ.

  úÄÅÓØ ÏÄÉÎ É ÔÏÔ ÖÅ ÜÌÅÍÅÎÔ ÓÈÅÍÙ (f ) ÐÒÉÈÏÄÉÔÓÑ ÕËÁÚÙ×ÁÔØ × ÆÏÒÍÕÌÅ