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

§2. ðÏÌÎÙÅ ÓÉÓÔÅÍÙ Ó×ÑÚÏË                                            67

  ÷ ÐÒÉÎÃÉÐÅ ÍÙ ÎÅ ÏÂÑÚÁÎÙ ÏÇÒÁÎÉÞÉ×ÁÔØÓÑ ÞÅÔÙÒØÍÑ ÒÁÓÓÍÏÔÒÅÎÎÙ-
ÍÉ Ó×ÑÚËÁÍÉ. ìÀÂÁÑ ÂÕÌÅ×Á ÆÕÎËÃÉÑ ÍÏÖÅÔ ÉÇÒÁÔØ ÒÏÌØ Ó×ÑÚËÉ. îÁÐÒÉÍÅÒ,
ÍÏÖÎÏ ÒÁÓÓÍÏÔÒÅÔØ Ó×ÑÚËÕ (p notand q), ÚÁÄÁ×ÁÅÍÕÀ ÜË×É×ÁÌÅÎÔÎÏÓÔØÀ
                       (p notand q) ↔ ¬(p ∧ q)
(ÓÌÏ×ÁÍÉ: (p notand q) ÌÏÖÎÏ, ÌÉÛØ ÅÓÌÉ p É q ÉÓÔÉÎÎÙ). þÅÒÅÚ Îž ×ÙÒÁ-
ÖÁÅÔÓÑ ÏÔÒÉÃÁÎÉÅ (p notand p), ÐÏÓÌÅ ÞÅÇÏ ÍÏÖÎÏ ×ÙÒÁÚÉÔØ ËÏÎßÀÎËÃÉÀ,
Á ÚÁÔÅÍ, ËÁË ÍÙ ÚÎÁÅÍ, É ×ÏÏÂÝÅ ÌÀÂÕÀ ÆÕÎËÃÉÀ. (úÎÁËÏÍÙÅ Ó ÃÉÆÒÏ×ÙÍÉ
ÌÏÇÉÞÅÓËÉÍÉ ÓÈÅÍÁÍÉ ÍÁÌÏÇÏ ÕÒÏ×ÎÑ ÉÎÔÅÇÒÁÃÉÉ ÈÏÒÏÛÏ ÚÎÁËÏÍÙ Ó ÜÔÉÍ
ÕÔ×ÅÒÖÄÅÎÉÅÍ: ÄÏÓÔÁÔÏÞÎÏ ÂÏÌØÛÏÊ ÚÁÐÁÓ ÓÈÅÍ é-îå ÐÏÚ×ÏÌÑÅÔ ÒÅÁÌÉÚÏ-
×ÁÔØ ÌÀÂÕÀ ÔÒÅÂÕÅÍÕÀ ÚÁ×ÉÓÉÍÏÓÔØ ×ÙÈÏÄÁ ÏÔ ×ÈÏÄÏ×.)
   äÒÕÇÁÑ ÉÎÔÅÒÅÓÎÁÑ ÐÏÌÎÁÑ ÓÉÓÔÅÍÁ Ó×ÑÚÏË ¡ ÓÌÏÖÅÎÉÅ ÐÏ ÍÏÄÕÌÀ 2,
ËÏÎßÀÎËÃÉÑ É ËÏÎÓÔÁÎÔÁ 1 (ËÏÔÏÒÕÀ ÍÏÖÎÏ ÓÞÉÔÁÔØ 0-ÁÒÎÏÊ Ó×ÑÚËÏÊ, ÚÁ-
ÄÁÀÝÅÊ ÆÕÎËÃÉÀ ÏÔ ÎÕÌÑ ÁÒÇÕÍÅÎÔÏ×). ðÒÅÄÓÔÁ×ÌÅÎÎÙÅ × ÜÔÏÊ ÓÉÓÔÅÍÅ
ÂÕÌÅ×Ù ÆÕÎËÃÉÉ ÓÔÁÎÏ×ÑÔÓÑ ÐÏÌÉÎÏÍÁÍÉ Ó ËÏÜÆÆÉÃÉÅÎÔÁÍÉ × ËÏÌØÃÅ ×Ù-
ÞÅÔÏ× ÐÏ ÍÏÄÕÌÀ 2. éÄÅÑ ÒÁÓÓÍÁÔÒÉ×ÁÔØ ÂÕÌÅ×Ù ÆÕÎËÃÉÉ ËÁË ÐÏÌÉÎÏÍÙ
(ÏËÁÚÁ×ÛÁÑÓÑ ÎÅÏÖÉÄÁÎÎÏ ÐÌÏÄÏÔ×ÏÒÎÏÊ × ÐÏÓÌÅÄÎÉÅ ÇÏÄÙ) ÂÙÌÁ ×ÙÓËÁÚÁÎÁ
× 1927 Ç. ÒÏÓÓÉÊÓËÉÍ ÍÁÔÅÍÁÔÉËÏÍ é×ÁÎÏÍ é×ÁÎÏ×ÉÞÅÍ öÅÇÁÌËÉÎÙÍ.
   îÁÚÏ×¾Í ÍÏÎÏÍÏÍ ËÏÎßÀÎËÃÉÀ ÌÀÂÏÇÏ ÎÁÂÏÒÁ ÐÅÒÅÍÅÎÎÙÈ ÉÌÉ ËÏÎÓÔÁÎ-
ÔÕ 1 (ËÏÔÏÒÕÀ ÅÓÔÅÓÔ×ÅÎÎÏ ÒÁÓÓÍÁÔÒÉ×ÁÔØ ËÁË ËÏÎßÀÎËÃÉÀ ÎÕÌÑ ÐÅÒÅÍÅÎ-
ÎÙÈ). îÁÚ×ÁÎÉÅ ÜÔÏ ÅÓÔÅÓÔ×ÅÎÎÏ, ÔÁË ËÁË ÐÒÉ ÎÁÛÉÈ ÓÏÇÌÁÛÅÎÉÑÈ (1 ÏÂÏÚÎÁ-
ÞÁÅÔ ÉÓÔÉÎÕ, 0 ¡ ÌÏÖØ) ËÏÎßÀÎËÃÉÑ ÓÏÏÔ×ÅÔÓÔ×ÕÅÔ ÕÍÎÏÖÅÎÉÀ.
   îÁÚÏ×¾Í ÐÏÌÉÎÏÍÏÍ ÓÕÍÍÕ ÔÁËÉÈ ÍÏÎÏÍÏ× ÐÏ ÍÏÄÕÌÀ 2 (ÜÔÏ ÚÎÁÞÉÔ, ÞÔÏ
0 ⊕ 0 = 0, 0 ⊕ 1 = 1 ⊕ 0 = 1 É 1 ⊕ 1 = 0). ñÓÎÏ, ÞÔÏ Ä×Á ÐÏ×ÔÏÒÑÀÝÉÈ-
ÓÑ ÍÏÎÏÍÁ ÍÏÖÎÏ ÓÏËÒÁÔÉÔØ (×ÅÄØ ÓÌÏÖÅÎÉÅ ÐÏ ÍÏÄÕÌÀ 2), ÔÁË ÞÔÏ ÂÕÄÅÍ
ÒÁÓÓÍÁÔÒÉ×ÁÔØ ÔÏÌØËÏ ÐÏÌÉÎÏÍÙ ÂÅÚ ÐÏ×ÔÏÒÑÀÝÉÈÓÑ ÍÏÎÏÍÏ×. ðÒÉ ÜÔÏÍ,
ÅÓÔÅÓÔ×ÅÎÎÏ, ÐÏÒÑÄÏË ÞÌÅÎÏ× × ÍÏÎÏÍÅ (ËÁË É ÐÏÒÑÄÏË ÍÏÎÏÍÏ× × ÐÏÌÉÎÏÍÅ)
ÒÏÌÉ ÎÅ ÉÇÒÁÅÔ, ÉÈ ÍÏÖÎÏ ÐÅÒÅÓÔÁ×ÌÑÔØ.
   ôÅÏÒÅÍÁ 21 (Ï ÐÏÌÉÎÏÍÁÈ öÅÇÁÌËÉÎÁ). ÷ÓÑËÁÑ ÂÕÌÅ×Á ÆÕÎËÃÉÑ ÏÄÎÏ-
ÚÎÁÞÎÏ ÐÒÅÄÓÔÁ×ÌÑÅÔÓÑ ÔÁËÉÍ ÐÏÌÉÎÏÍÏÍ.
   äÏËÁÚÁÔÅÌØÓÔ×Ï. óÕÝÅÓÔ×Ï×ÁÎÉÅ ÉÓËÏÍÏÇÏ ÐÏÌÉÎÏÍÁ ÓÌÅÄÕÅÔ ÉÚ ÔÅÏÒÅ-
ÍÙ 20, ÔÁË ËÁË ËÏÎßÀÎËÃÉÑ ÅÓÔØ ÕÍÎÏÖÅÎÉÅ, ÏÔÒÉÃÁÎÉÅ ¡ ÐÒÉÂÁ×ÌÅÎÉÅ
ÅÄÉÎÉÃÙ, Á ÄÉÚßÀÎËÃÉÀ ÍÏÖÎÏ ÞÅÒÅÚ ÎÉÈ ×ÙÒÁÚÉÔØ (ÐÏÌÕÞÉÔÓÑ p + q + pq).
îÁÄÏ ÔÏÌØËÏ ÚÁÍÅÔÉÔØ, ÞÔÏ ÓÔÅÐÅÎÉ ÎÅ ÎÕÖÎÙ: ÐÅÒÅÍÅÎÎÙÅ ÐÒÉÎÉÍÁÀÔ ÚÎÁ-
ÞÅÎÉÑ 0 É 1, ÔÁË ÞÔÏ xn ÍÏÖÎÏ ÚÁÍÅÎÉÔØ ÎÁ x.
   íÏÖÎÏ ÔÁËÖÅ ÓÏÓÌÁÔØÓÑ ÎÁ ÉÚ×ÅÓÔÎÏÅ ÉÚ ÁÌÇÅÂÒÙ ÕÔ×ÅÒÖÄÅÎÉÅ Ï ÔÏÍ,
ÞÔÏ ×ÓÑËÁÑ ÆÕÎËÃÉÑ Ó ÁÒÇÕÍÅÎÔÁÍÉ ÉÚ ËÏÎÅÞÎÏÇÏ ÐÏÌÑ (× ÄÁÎÎÏÍ ÓÌÕÞÁÅ ÜÔÏ
Ä×ÕÈÜÌÅÍÅÎÔÎÏÅ ÐÏÌÅ ×ÙÞÅÔÏ× ÐÏ ÍÏÄÕÌÀ 2) ÚÁÄÁ¾ÔÓÑ ÐÏÌÉÎÏÍÏÍ. (ïÔÓÀÄÁ,
ËÓÔÁÔÉ, ÐÏÌÕÞÁÅÔÓÑ ÎÏ×ÏÅ ÄÏËÁÚÁÔÅÌØÓÔ×Ï ÔÅÏÒÅÍÙ 19.)