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

UptoLike

ВУЗ: 

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

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

Рубрика: 

128 çÌÁ×Á VI. éÓÞÉÓÌÅÎÉÅ ÐÒÅÄÉËÁÔÏ×
ôÅÐÅÒØ ÎÅÓÌÏÖÎÏ ÄÏËÁÚÁÔØ É É ÂÏÌÅÅ ÏÂÝÉÊ ÆÁËÔ: ÚÁÍÅÎÁ ÐÏÄÆÏÒÍÕ-
ÌÙ ÎÁ ÄÏËÁÚÕÅÍÏ ÜË×É×ÁÌÅÎÔÎÕÀ ÄÁ¾Ô ÄÏËÁÚÕÅÍÏ ÜË×É×ÁÌÅÎÔÎÕÀ ÆÏÒ-
ÍÕÌÕ.
• ÷Ù×ÅÄÅÍ ÆÏÒÍÕÌÕ ∀x A(x) → ∀y A(y) (ÚÄÅÓØ A ¡ ÏÄÎÏÍÅÓÔÎÙÊ ÐÒÅ-
ÄÉËÁÔÎÙÊ ÓÉÍ×ÏÌ). üÔÏ ÎÅÓÌÏÖÎÏ: ÎÁÞÎ¾Í Ó ÁËÓÉÏÍÙ ∀x A(x) → A(y),
× ÎÅÊ ÌÅ×ÁÑ ÞÁÓÔØ ÎÅ ÉÍÅÅÔ ÐÁÒÁÍÅÔÒÁ y É ÐÏÔÏÍÕ ÐÏ ÐÒÁ×ÉÌÕ âÅÒ-
ÎÁÊÓÁ ÉÚ Îž ÐÏÌÕÞÁÅÔÓÑ ÉÓËÏÍÁÑ ÆÏÒÍÕÌÁ. üÔÏÔ ÐÒÉÍÅÒ ÐÏËÁÚÙ×ÁÅÔ,
ÞÔÏ Ó×ÑÚÁÎÎÙÅ ÐÅÒÅÍÅÎÎÙÅ ÍÏÖÎÏ ÐÅÒÅÉÍÅÎÏ×Ù×ÁÔØ, ÎÅ ÍÅÎÑÑ ÓÍÙÓÌÁ
ÆÏÒÍÕÌÙ
• ÷Ù×ÅÄÅÍ ÆÏÒÍÕÌÙ, Ó×ÑÚÙ×ÁÀÝÉÅ Ë×ÁÎÔÏÒÙ ×ÓÅÏÂÝÎÏÓÔÉ É ÓÕÝÅÓÔ×Ï-
×ÁÎÉÑ:
∀ξ ϕ ↔ ¬∃ξ ¬ϕ;
∃ξ ϕ ↔ ¬∀ξ ¬ϕ.
îÁÐÏÍÎÉÍ, ÞÔÏ α ↔ β ÍÙ ÓÞÉÔÁÅÍ ÓÏËÒÁÝÅÎÉÅÍ ÄÌÑ (α → β)∧(β → α),
ÔÁË ÞÔÏ ÎÁÍ ÎÁÄÏ ×Ù×ÅÓÔÉ ÞÅÔÙÒÅ ÆÏÒÍÕÌÙ.
îÁÞÎ¾Í Ó ÆÏÒÍÕÌÙ ∃ξ ϕ → ¬∀ξ ¬ϕ. éÍÅÑ × ×ÉÄÕ ÐÒÁ×ÉÌÏ âÅÒÎÁÊÓÁ,
ÄÏÓÔÁÔÏÞÎÏ ×Ù×ÅÓÔÉ ÆÏÒÍÕÌÕ ϕ → ¬∀ξ ¬ϕ. ôÁ×ÔÏÌÏÇÉÑ (B → ¬A) →
→ (A → ¬B) ÐÏÚ×ÏÌÑÅÔ ×ÍÅÓÔÏ ÜÔÏÇÏ ×Ù×ÏÄÉÔØ ÆÏÒÍÕÌÕ ∀ξ ¬ϕ → ¬ϕ,
ËÏÔÏÒÁÑ Ñ×ÌÑÅÔÓÑ ÁËÓÉÏÍÏÊ.
÷ ÔÏÌØËÏ ÞÔÏ ×Ù×ÅÄÅÎÎÏÊ ÆÏÒÍÕÌÅ ∃ξ ϕ → ¬∀ξ ¬ϕ ÍÏÖÎÏ × ËÁÞÅÓÔ×Å
ϕ ×ÚÑÔØ ÌÀÂÕÀ ÆÏÒÍÕÌÕ, × ÔÏÍ ÞÉÓÌÅ ÎÁÞÉÎÁÀÝÕÀÓÑ Ó ÏÔÒÉÃÁÎÉÑ.
ðÏÄÓÔÁ×É× ¬ϕ ×ÍÅÓÔÏ ϕ, ÐÏÌÕÞÉÍ
∃ξ ¬ϕ → ¬∀ξ ¬¬ϕ,
ÇÄÅ ¬¬ϕ ÄÏËÁÚÕÅÍÏ ÜË×É×ÁÌÅÎÔÎÁ ϕ É ÐÏÔÏÍÕ ÍÏÖÅÔ ÂÙÔØ ÚÁÍÅÎÅÎÁ ÎÁ
ϕ. ðÏÓÌÅ ÜÔÏÇÏ ÐÒÁ×ÉÌÏ ËÏÎÔÒÁÐÏÚÉÃÉÉ (ÅÓÌÉ ÉÚ A ÓÌÅÄÕÅÔ ¬B, ÔÏ ÉÚ B
ÓÌÅÄÕÅÔ ¬A) ÄÁ¾Ô
∀ξ ϕ → ¬∃ξ ¬ϕ.
÷Ù×ÅÄÅÍ ÔÒÅÔØÀ ÆÏÒÍÕÌÕ: ¬∃ξ ¬ϕ → ∀ξ ϕ. ðÏ ÐÒÁ×ÉÌÕ âÅÒÎÁÊÓÁ
ÄÏÓÔÁÔÏÞÎÏ ×Ù×ÅÓÔÉ ¬∃ξ ¬ϕ → ϕ, ÞÔÏ ÐÏÓÌÅ ËÏÎÔÒÁÐÏÚÉÃÉÉ ÐÒÅ×ÒÁÝÁ-
ÅÔÓÑ × ÁËÓÉÏÍÕ ¬ϕ → ∃ξ ¬ϕ.
þÅÔ×¾ÒÔÁÑ ÆÏÒÍÕÌÁ ÐÏÌÕÞÉÔÓÑ, ÅÓÌÉ ÚÁÍÅÎÉÔØ × ÔÒÅÔØÅÊ ϕ ÎÁ ¬ϕ É
ÐÒÉÍÅÎÉÔØ ËÏÎÔÒÁÐÏÚÉÃÉÀ.
4.2. ÷Ù×ÏÄÉÍÏÓÔØ ÉÚ ÐÏÓÙÌÏË
÷ ÉÓÞÉÓÌÅÎÉÉ ×ÙÓËÁÚÙ×ÁÎÉÊ ×ÁÖÎÕÀ ÒÏÌØ ÉÇÒÁÌÏ ÐÏÎÑÔÉÅ ×Ù×ÏÄÉÍÏÓÔÉ
ÉÚ ÐÏÓÙÌÏË É Ó×ÑÚÁÎÎÁÑ Ó ÎÉÍ ÌÅÍÍÁ Ï ÄÅÄÕËÃÉÉ (Ó. 87). äÌÑ ÉÓÞÉÓÌÅÎÉÑ ÐÒÅ-
ÄÉËÁÔÏ× ÓÉÔÕÁÃÉÑ ÎÅÍÎÏÇÏ ÍÅÎÑÅÔÓÑ. åÓÌÉ ÒÁÚÒÅÛÉÔØ ÉÓÐÏÌØÚÏ×ÁÔØ ÐÏÓÙÌËÉ
128                                     çÌÁ×Á VI. éÓÞÉÓÌÅÎÉÅ ÐÒÅÄÉËÁÔÏ×

           ôÅÐÅÒØ ÎÅÓÌÏÖÎÏ ÄÏËÁÚÁÔØ É É ÂÏÌÅÅ ÏÂÝÉÊ ÆÁËÔ: ÚÁÍÅÎÁ ÐÏÄÆÏÒÍÕ-
        ÌÙ ÎÁ ÄÏËÁÚÕÅÍÏ ÜË×É×ÁÌÅÎÔÎÕÀ ÄÁ¾Ô ÄÏËÁÚÕÅÍÏ ÜË×É×ÁÌÅÎÔÎÕÀ ÆÏÒ-
        ÍÕÌÕ.
      • ÷Ù×ÅÄÅÍ ÆÏÒÍÕÌÕ ∀x A(x) → ∀y A(y) (ÚÄÅÓØ A ¡ ÏÄÎÏÍÅÓÔÎÙÊ ÐÒÅ-
        ÄÉËÁÔÎÙÊ ÓÉÍ×ÏÌ). üÔÏ ÎÅÓÌÏÖÎÏ: ÎÁÞÎ¾Í Ó ÁËÓÉÏÍÙ ∀x A(x) → A(y),
        × ÎÅÊ ÌÅ×ÁÑ ÞÁÓÔØ ÎÅ ÉÍÅÅÔ ÐÁÒÁÍÅÔÒÁ y É ÐÏÔÏÍÕ ÐÏ ÐÒÁ×ÉÌÕ âÅÒ-
        ÎÁÊÓÁ ÉÚ Îž ÐÏÌÕÞÁÅÔÓÑ ÉÓËÏÍÁÑ ÆÏÒÍÕÌÁ. üÔÏÔ ÐÒÉÍÅÒ ÐÏËÁÚÙ×ÁÅÔ,
        ÞÔÏ Ó×ÑÚÁÎÎÙÅ ÐÅÒÅÍÅÎÎÙÅ ÍÏÖÎÏ ÐÅÒÅÉÍÅÎÏ×Ù×ÁÔØ, ÎÅ ÍÅÎÑÑ ÓÍÙÓÌÁ
        ÆÏÒÍÕÌÙ
      • ÷Ù×ÅÄÅÍ ÆÏÒÍÕÌÙ, Ó×ÑÚÙ×ÁÀÝÉÅ Ë×ÁÎÔÏÒÙ ×ÓÅÏÂÝÎÏÓÔÉ É ÓÕÝÅÓÔ×Ï-
        ×ÁÎÉÑ:
                              ∀ξ ϕ ↔ ¬∃ξ ¬ϕ;
                              ∃ξ ϕ ↔ ¬∀ξ ¬ϕ.
       îÁÐÏÍÎÉÍ, ÞÔÏ α ↔ β ÍÙ ÓÞÉÔÁÅÍ ÓÏËÒÁÝÅÎÉÅÍ ÄÌÑ (α → β)∧(β → α),
       ÔÁË ÞÔÏ ÎÁÍ ÎÁÄÏ ×Ù×ÅÓÔÉ ÞÅÔÙÒÅ ÆÏÒÍÕÌÙ.
          îÁÞÎ¾Í Ó ÆÏÒÍÕÌÙ ∃ξ ϕ → ¬∀ξ ¬ϕ. éÍÅÑ × ×ÉÄÕ ÐÒÁ×ÉÌÏ âÅÒÎÁÊÓÁ,
       ÄÏÓÔÁÔÏÞÎÏ ×Ù×ÅÓÔÉ ÆÏÒÍÕÌÕ ϕ → ¬∀ξ ¬ϕ. ôÁ×ÔÏÌÏÇÉÑ (B → ¬A) →
       → (A → ¬B) ÐÏÚ×ÏÌÑÅÔ ×ÍÅÓÔÏ ÜÔÏÇÏ ×Ù×ÏÄÉÔØ ÆÏÒÍÕÌÕ ∀ξ ¬ϕ → ¬ϕ,
       ËÏÔÏÒÁÑ Ñ×ÌÑÅÔÓÑ ÁËÓÉÏÍÏÊ.
          ÷ ÔÏÌØËÏ ÞÔÏ ×Ù×ÅÄÅÎÎÏÊ ÆÏÒÍÕÌÅ ∃ξ ϕ → ¬∀ξ ¬ϕ ÍÏÖÎÏ × ËÁÞÅÓÔ×Å
       ϕ ×ÚÑÔØ ÌÀÂÕÀ ÆÏÒÍÕÌÕ, × ÔÏÍ ÞÉÓÌÅ ÎÁÞÉÎÁÀÝÕÀÓÑ Ó ÏÔÒÉÃÁÎÉÑ.
       ðÏÄÓÔÁ×É× ¬ϕ ×ÍÅÓÔÏ ϕ, ÐÏÌÕÞÉÍ
                             ∃ξ ¬ϕ → ¬∀ξ ¬¬ϕ,
       ÇÄÅ ¬¬ϕ ÄÏËÁÚÕÅÍÏ ÜË×É×ÁÌÅÎÔÎÁ ϕ É ÐÏÔÏÍÕ ÍÏÖÅÔ ÂÙÔØ ÚÁÍÅÎÅÎÁ ÎÁ
       ϕ. ðÏÓÌÅ ÜÔÏÇÏ ÐÒÁ×ÉÌÏ ËÏÎÔÒÁÐÏÚÉÃÉÉ (ÅÓÌÉ ÉÚ A ÓÌÅÄÕÅÔ ¬B, ÔÏ ÉÚ B
       ÓÌÅÄÕÅÔ ¬A) ÄÁ¾Ô
                               ∀ξ ϕ → ¬∃ξ ¬ϕ.
          ÷Ù×ÅÄÅÍ ÔÒÅÔØÀ ÆÏÒÍÕÌÕ: ¬∃ξ ¬ϕ → ∀ξ ϕ. ðÏ ÐÒÁ×ÉÌÕ âÅÒÎÁÊÓÁ
       ÄÏÓÔÁÔÏÞÎÏ ×Ù×ÅÓÔÉ ¬∃ξ ¬ϕ → ϕ, ÞÔÏ ÐÏÓÌÅ ËÏÎÔÒÁÐÏÚÉÃÉÉ ÐÒÅ×ÒÁÝÁ-
       ÅÔÓÑ × ÁËÓÉÏÍÕ ¬ϕ → ∃ξ ¬ϕ.
          þÅÔ×¾ÒÔÁÑ ÆÏÒÍÕÌÁ ÐÏÌÕÞÉÔÓÑ, ÅÓÌÉ ÚÁÍÅÎÉÔØ × ÔÒÅÔØÅÊ ϕ ÎÁ ¬ϕ É
       ÐÒÉÍÅÎÉÔØ ËÏÎÔÒÁÐÏÚÉÃÉÀ.

4.2. ÷Ù×ÏÄÉÍÏÓÔØ ÉÚ ÐÏÓÙÌÏË

   ÷ ÉÓÞÉÓÌÅÎÉÉ ×ÙÓËÁÚÙ×ÁÎÉÊ ×ÁÖÎÕÀ ÒÏÌØ ÉÇÒÁÌÏ ÐÏÎÑÔÉÅ ×Ù×ÏÄÉÍÏÓÔÉ
ÉÚ ÐÏÓÙÌÏË É Ó×ÑÚÁÎÎÁÑ Ó ÎÉÍ ÌÅÍÍÁ Ï ÄÅÄÕËÃÉÉ (Ó. 87). äÌÑ ÉÓÞÉÓÌÅÎÉÑ ÐÒÅ-
ÄÉËÁÔÏ× ÓÉÔÕÁÃÉÑ ÎÅÍÎÏÇÏ ÍÅÎÑÅÔÓÑ. åÓÌÉ ÒÁÚÒÅÛÉÔØ ÉÓÐÏÌØÚÏ×ÁÔØ ÐÏÓÙÌËÉ

Страницы