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

§4. ÷Ù×ÏÄÙ × ÉÓÞÉÓÌÅÎÉÉ ÐÒÅÄÉËÁÔÏ×                                  127

     → (ϕ∧ψ))) Ñ×ÌÑÅÔÓÑ ÞÁÓÔÎÙÍ ÓÌÕÞÁÅÍ ÐÒÏÐÏÚÉÃÉÏÎÁÌØÎÏÊ ÔÁ×ÔÏÌÏÇÉÉ
     (Á ÎÁ ÓÁÍÏÍ ÄÅÌÅ É ÁËÓÉÏÍÏÊ) É Ä×ÁÖÄÙ ÐÒÉÍÅÎÑÅÍ ÐÒÁ×ÉÌÏ MP.
   • äÒÕÇÏÊ ÐÒÉÍÅÒ ÔÁËÏÇÏ ÖÅ ÒÏÄÁ: ÅÓÌÉ ÆÏÒÍÕÌÁ ϕ → ψ ×Ù×ÏÄÉÍÁ, ÔÏ
     ×Ù×ÏÄÉÍÁ É ÆÏÒÍÕÌÁ ¬ψ → ¬ϕ, ÐÏÓËÏÌØËÕ ÉÍÐÌÉËÁÃÉÑ
                        (ϕ → ψ) → (¬ψ → ¬ϕ)
     Ñ×ÌÑÅÔÓÑ ÞÁÓÔÎÙÍ ÓÌÕÞÁÅÍ ÐÒÏÐÏÚÉÃÉÏÎÁÌØÎÏÊ ÔÁ×ÔÏÌÏÇÉÉ.
   • åݾ ÏÄÉÎ ÐÒÉÍÅÒ: ÅÓÌÉ ×Ù×ÏÄÉÍÙ ÆÏÒÍÕÌÙ ϕ → ψ É ψ → τ , ÔÏ ×Ù×Ï-
     ÄÉÍÁ É ÆÏÒÍÕÌÁ ϕ → τ , ÐÏÓËÏÌØËÕ ÆÏÒÍÕÌÁ
                    (ϕ → ψ) → ((ψ → τ ) → (ϕ → τ ))
     Ñ×ÌÑÅÔÓÑ ÞÁÓÔÎÙÍ ÓÌÕÞÁÅÍ ÐÒÏÐÏÚÉÃÉÏÎÁÌØÎÏÊ ÔÁ×ÔÏÌÏÇÉÉ.
   • äÌÑ ÐÒÏÉÚ×ÏÌØÎÏÊ ÆÏÒÍÕÌÙ ϕ ×Ù×ÅÄÅÍ ÆÏÒÍÕÌÕ
                             ∀x ϕ → ∃x ϕ.
     ÷ ÓÁÍÏÍ ÄÅÌÅ, ÐÏÄÓÔÁÎÏ×ËÁ ÐÅÒÅÍÅÎÎÏÊ ×ÍÅÓÔÏ ÓÅÂÑ ×ÓÅÇÄÁ ÄÏÐÕÓÔÉ-
     ÍÁ, ÐÏÜÔÏÍÕ ÆÏÒÍÕÌÙ ∀x ϕ → ϕ É ϕ → ∃x ϕ Ñ×ÌÑÀÔÓÑ ÁËÓÉÏÍÁÍÉ.
     ïÓÔÁ¾ÔÓÑ ×ÏÓÐÏÌØÚÏ×ÁÔØÓÑ ÐÒÅÄÙÄÕÝÉÍ ÚÁÍÅÞÁÎÉÅÍ.
   • äÌÑ ÐÒÏÉÚ×ÏÌØÎÏÊ ÆÏÒÍÕÌÙ ϕ ×Ù×ÅÄÅÍ ÆÏÒÍÕÌÕ
                           ∃y ∀x ϕ → ∀x ∃y ϕ.
     æÏÒÍÕÌÙ ∀x ϕ → ϕ É ϕ → ∃y ϕ Ñ×ÌÑÀÔÓÑ ÁËÓÉÏÍÁÍÉ. ó ÉÈ ÐÏÍÏÝØÀ
     ×Ù×ÏÄÉÍ ÆÏÒÍÕÌÕ ∀x ϕ → ∃y ϕ. ôÅÐÅÒØ ÚÁÍÅÔÉÍ, ÞÔÏ ÌÅ×ÁÑ ÞÁÓÔØ ÉÍ-
     ÐÌÉËÁÃÉÉ ÎÅ ÉÍÅÅÔ ÐÁÒÁÍÅÔÒÁ x, Á ÐÒÁ×ÁÑ ÞÁÓÔØ ÎÅ ÉÍÅÅÔ ÐÁÒÁÍÅÔÒÁ y,
     ÔÁË ÞÔÏ ÍÏÖÎÏ ÐÒÉÍÅÎÉÔØ Ä×Á ÐÒÁ×ÉÌÁ âÅÒÎÁÊÓÁ (× ÌÀÂÏÍ ÐÏÒÑÄËÅ) É
     ÄÏÂÁ×ÉÔØ ÓÐÒÁ×Á Ë×ÁÎÔÏÒ ∀x, Á ÓÌÅ×Á ¡ Ë×ÁÎÔÏÒ ∃y.
   • ðÒÅÄÐÏÌÏÖÉÍ, ÞÔÏ ÆÏÒÍÕÌÁ ϕ → ψ ×Ù×ÏÄÉÍÁ, Á ξ ¡ ÐÒÏÉÚ×ÏÌØÎÁÑ ÐÅ-
     ÒÅÍÅÎÎÁÑ. ðÏËÁÖÅÍ, ÞÔÏ × ÜÔÏÍ ÓÌÕÞÁÅ ×Ù×ÏÄÉÍÁ ÆÏÒÍÕÌÁ ∀ξ ϕ → ∀ξ ψ.
     ÷ ÓÁÍÏÍ ÄÅÌÅ, ÆÏÒÍÕÌÁ ∀ξ ϕ → ϕ Ñ×ÌÑÅÔÓÑ ÁËÓÉÏÍÏÊ. äÁÌÅÅ ×Ù×ÏÄÉÍ
     (Ó ÐÏÍÏÝØÀ ÐÒÏÐÏÚÉÃÉÏÎÁÌØÎÙÈ ÔÁ×ÔÏÌÏÇÉÊ É ÐÒÁ×ÉÌÁ MP) ÆÏÒÍÕÌÕ
     ∀ξ ϕ → ψ; ÏÓÔÁ¾ÔÓÑ ×ÏÓÐÏÌØÚÏ×ÁÔØÓÑ ÐÒÁ×ÉÌÏÍ âÅÒÎÁÊÓÁ (ÌÅ×ÁÑ ÞÁÓÔØ
     ÎÅ ÉÍÅÅÔ ÐÁÒÁÍÅÔÒÁ ξ).
   • áÎÁÌÏÇÉÞÎÙÍ ÏÂÒÁÚÏÍ ÉÚ ×Ù×ÏÄÉÍÏÓÔÉ ÆÏÒÍÕÌÙ ϕ → ψ ÓÌÅÄÕÅÔ ×Ù-
     ×ÏÄÉÍÏÓÔØ ÆÏÒÍÕÌÙ ∃ξ ϕ → ∃ξ ψ, ÔÏÌØËÏ ÎÁÄÏ ÎÁÞÁÔØ Ó ÁËÓÉÏÍÙ
     ψ → ∃ξ ψ, ÚÁÔÅÍ ÐÏÌÕÞÉÔØ ϕ → ∃ξ ψ, Á ÐÏÔÏÍ ÐÒÉÍÅÎÉÔØ ÐÒÁ×ÉÌÏ
     âÅÒÎÁÊÓÁ.
   • ôÁËÉÍ ÏÂÒÁÚÏÍ, ÅÓÌÉ ÆÏÒÍÕÌÙ ϕ É ψ ÄÏËÁÚÕÅÍÏ ÜË×É×ÁÌÅÎÔÎÙ (ÜÔÏ ÚÎÁ-
     ÞÉÔ, ÞÔÏ ÉÍÐÌÉËÁÃÉÉ ϕ → ψ É ψ → ϕ ×Ù×ÏÄÉÍÙ), ÔÏ ÆÏÒÍÕÌÙ ∀ξ ϕ É
     ∀ξ ψ ÔÁËÖÅ ÄÏËÁÚÕÅÍÏ ÜË×É×ÁÌÅÎÔÎÙ. (áÎÁÌÏÇÉÞÎÏÅ ÕÔ×ÅÒÖÄÅÎÉÅ ×ÅÒ-
     ÎÏ É ÄÌÑ ÆÏÒÍÕÌ ∃ξ ϕ É ∃ξ ψ.)