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

§1. éÓÞÉÓÌÅÎÉÅ ×ÙÓËÁÚÙ×ÁÎÉÊ                                                91

   úÁÄÁÞÁ 123. äÏËÁÖÉÔÅ, ÞÔÏ ÆÏÒÍÕÌÁ (¬B → ¬A) → (A → B) Ñ×ÌÑ-
ÅÔÓÑ ÔÅÏÒÅÍÏÊ ÉÓÞÉÓÌÅÎÉÑ ×ÙÓËÁÚÙ×ÁÎÉÊ. (õËÁÚÁÎÉÅ: ÉÓÐÏÌØÚÕÊÔÅ ÚÁËÏÎ
ÉÓËÌÀÞ¾ÎÎÏÇÏ ÔÒÅÔØÅÇÏ.)
  úÁÄÁÞÁ 124. éÓËÌÀÞÉÍ ÉÚ ÞÉÓÌÁ ÁËÓÉÏÍ ÉÓÞÉÓÌÅÎÉÑ ×ÙÓËÁÚÙ×ÁÎÉÊ ÚÁ-
ËÏÎ ÉÓËÌÀÞ¾ÎÎÏÇÏ ÔÒÅÔØÅÇÏ, ÚÁÍÅÎÉ× ÅÇÏ ÎÁ ÚÁËÏÎ ÓÎÑÔÉÑ Ä×ÏÊÎÏÇÏ ÏÔÒÉ-
ÃÁÎÉÑ. ðÏËÁÖÉÔÅ, ÞÔÏ ÏÔ ÜÔÏÇÏ ËÌÁÓÓ ×Ù×ÏÄÉÍÙÈ ÆÏÒÍÕÌ ÎÅ ÉÚÍÅÎÉÔÓÑ.
   úÁÄÁÞÁ 125. äÏËÁÖÉÔÅ, ÞÔÏ ÐÒÉ ÎÁÌÉÞÉÉ ÁËÓÉÏÍÙ ÉÓËÌÀÞ¾ÎÎÏÇÏ ÔÒÅ-
ÔØÅÇÏ (11) ÁËÓÉÏÍÁ (10) Ñ×ÌÑÅÔÓÑ ÌÉÛÎÅÊ ¡ ž (ÔÏÞÎÅÅ ÓÌÅÄÏ×ÁÌÏ ÂÙ
ÓËÁÚÁÔØ: ÌÀÂÏÊ ÞÁÓÔÎÙÊ ÓÌÕÞÁÊ ÜÔÏÊ ÓÈÅÍÙ ÁËÓÉÏÍ) ÍÏÖÎÏ ×Ù×ÅÓÔÉ ÉÚ
ÏÓÔÁÌØÎÙÈ ÁËÓÉÏÍ.
   ôÅÐÅÒØ ÕÖÅ ÍÏÖÎÏ ÄÏËÁÚÁÔØ ÔÅÏÒÅÍÕ Ï ÐÏÌÎÏÔÅ: ×ÓÑËÁÑ ÔÁ×ÔÏÌÏÇÉÑ ×Ù×Ï-
ÄÉÍÁ × ÉÓÞÉÓÌÅÎÉÉ ×ÙÓËÁÚÙ×ÁÎÉÊ. éÄÅÑ ÄÏËÁÚÁÔÅÌØÓÔ×Á ÓÏÓÔÏÉÔ × ÒÁÚÂÏÒÅ
ÓÌÕÞÁÅ×. ðÏÑÓÎÉÍ Å¾ ÎÁ ÐÒÉÍÅÒÅ. ðÕÓÔØ A ¡ ÐÒÏÉÚ×ÏÌØÎÁÑ ÆÏÒÍÕÌÁ, ÓÏ-
ÄÅÒÖÁÝÁÑ ÐÅÒÅÍÅÎÎÙÅ p, q, r. ðÒÅÄÐÏÌÏÖÉÍ, ÞÔÏ A ÉÓÔÉÎÎÁ, ËÏÇÄÁ ×ÓÅ ÔÒÉ
ÐÅÒÅÍÅÎÎÙÅ ÉÓÔÉÎÎÙ. ôÏÇÄÁ, ËÁË ÍÙ ÄÏËÁÖÅÍ,
                                 p, q, r ` A.
÷ÏÏÂÝÅ ËÁÖÄÏÊ ÓÔÒÏËÅ ÔÁÂÌÉÃÙ ÉÓÔÉÎÎÏÓÔÉ ÄÌÑ ÆÏÒÍÕÌÙ A ÓÏÏÔ×ÅÔÓÔ×ÕÅÔ
ÕÔ×ÅÒÖÄÅÎÉÅ Ï ×Ù×ÏÄÉÍÏÓÔÉ. îÁÐÒÉÍÅÒ, ÅÓÌÉ A ÌÏÖÎÁ, ËÏÇÄÁ p É q ÌÏÖÎÙ,
Á r ÉÓÔÉÎÎÏ, ÔÏ
                                ¬p, ¬q, r ` ¬A.
åÓÌÉ ÆÏÒÍÕÌÁ A Ñ×ÌÑÅÔÓÑ ÔÁ×ÔÏÌÏÇÉÅÊ, ÔÏ ÏËÁÖÅÔÓÑ, ÞÔÏ ÏÎÁ ×Ù×ÏÄÉÍÁ ÉÚ
×ÓÅÈ ×ÏÓØÍÉ ×ÏÚÍÏÖÎÙÈ ×ÁÒÉÁÎÔÏ× ÐÏÓÙÌÏË. ðÏÌØÚÕÑÓØ ÚÁËÏÎÏÍ ÉÓËÌÀÞ¾Î-
ÎÏÇÏ ÔÒÅÔØÅÇÏ, ÍÏÖÎÏ ÐÏÓÔÅÐÅÎÎÏ ÉÚÂÁ×ÌÑÔØÓÑ ÏÔ ÐÏÓÙÌÏË. îÁÐÒÉÍÅÒ, ÉÚ
p, q, r ` A É p, q, ¬r ` A ÍÏÖÎÏ ÐÏÌÕÞÉÔØ p, q, (r ∨ ¬r) ` A, ÔÏ ÅÓÔØ p, q ` A
(ÐÏÓËÏÌØËÕ (r ∨ ¬r) Ñ×ÌÑÅÔÓÑ ÁËÓÉÏÍÏÊ).
    ðÒÏ×ÅÄ¾Í ÜÔÏ ÒÁÓÓÕÖÄÅÎÉÅ ÐÏÄÒÏÂÎÏ. äÌÑ ÎÁÞÁÌÁ ÄÏËÁÖÅÍ ÔÁËÕÀ ÌÅÍÍÕ:
    ìÅÍÍÁ 3. äÌÑ ÐÒÏÉÚ×ÏÌØÎÙÈ ÆÏÒÍÕÌ P É Q
              P, Q ` (P ∧ Q);                     P, Q ` (P ∨ Q);
            P, ¬Q ` ¬(P ∧ Q);                    P, ¬Q ` (P ∨ Q);
            ¬P, Q ` ¬(P ∧ Q);                    ¬P, Q ` (P ∨ Q);
           ¬P, ¬Q; ` ¬(P ∧ Q)                   ¬P, ¬Q ` ¬(P ∨ Q);

              P, Q ` (P → Q);
             P, ¬Q ` ¬(P → Q);                      P ` ¬(¬P );
             ¬P, Q ` (P → Q);                      ¬P ` ¬P.
            ¬P, ¬Q ` (P → Q);