DeMorgan의 법칙 증명 R iff 소개 :

자연 공제 시스템 의 10 가지 추론을 사용하면 DeMorgan의 법칙이 입증 됩니다.

자연 공제 규칙

  • 부정 소개 : {(P → Q), (P → ¬Q)} ⊢ ¬P

  • 부정 제거 : {(¬P → Q), (¬P → ¬Q)} ⊢ P

  • 그리고 소개 : {P, Q} ⊢ P ʌ Q

  • 그리고 제거 : P ʌ Q ⊢ {P, Q}

  • 또는 소개 : P ⊢ {(P ∨ Q),(Q ∨ P)}

  • 또는 제거 : {(P ∨ Q), (P → R), (Q → R)} ⊢ R

  • iff 소개 : {(P → Q), (Q → P)} ⊢ (P ≡ Q)

  • iff 제거 : (P ≡ Q) ⊢ {(P → Q), (Q → P)}

  • 소개하는 경우 : (P ⊢ Q) ⊢ (P → Q)

  • 제거하는 경우 : {(P → Q), P} ⊢ Q

증거 구조

증거의 각 진술은 이전에 도출 된 일부 명제 (원형 논리 없음) 또는 가정 (아래 설명)에 적용된 10 가지 규칙 중 하나의 결과 여야합니다. 각 규칙은 ⊢(논리적 결과 연산자) 왼쪽의 일부 제안에서 작동 하며 오른쪽에서 수많은 제안을 생성합니다. If Introduction은 나머지 연산자와 약간 다르게 작동합니다 (아래에 자세히 설명). 다른 명령문의 논리적 결과 인 한 명령문에서 작동합니다.

실시 예 1

다음과 같은 진술이 있습니다.

{(P → R), Q}

And Introduction을 사용하여 다음을 만들 수 있습니다.

(P → R) ʌ Q

실시 예 2

다음과 같은 진술이 있습니다.

{(P → R), P}

If Elimination을 사용하여 다음을 수행 할 수 있습니다.

R

실시 예 3

다음과 같은 진술이 있습니다.

(P ʌ Q)

And Elimination을 사용하여 다음을 수행 할 수 있습니다.

P

또는 만들기 :

Q

가정 전파

당신은 언제든지 당신이 원하는 진술을 가정 할 수 있습니다. 이러한 가정에서 도출 된 진술은 “의존적”입니다. 진술은 또한 부모 진술에 의존하는 가정에 의존합니다. 가정을 제거하는 유일한 방법은 If Introduction입니다. If 소개의 경우 명령문 Q에 의존 하는 Statement로 시작하여로 P끝납니다 (P → Q). 새로운 진술은 가정 Q을 제외한 모든 가정에 의존 한다 P. 최종 진술은 가정에 의존해서는 안됩니다.

세부 사항 및 점수

Natural Deduction Calculus의 10 가지 추론 만 사용하여 DeMorgan의 두 가지 법률 각각에 대해 하나의 증거를 구성합니다.

두 가지 규칙은 다음과 같습니다.

¬(P ∨ Q) ≡ ¬P ʌ ¬Q

¬(P ʌ Q) ≡ ¬P ∨ ¬Q

당신의 점수는 사용 된 추론의 수와 가정의 수를 더한 것입니다. 최종 진술은 어떤 가정에도 의존해서는 안됩니다 (즉, 정리이어야 함).

적합하다고 생각되면 증명을 자유롭게 포맷 할 수 있습니다.

점수를 매기 지 않고 한 증거에서 다른 증거로 Lemma를 양도 할 수 있습니다.

증거 예

나는 그것을 증명할 것이다 (P and not(P)) implies Q

(각 글 머리 기호는 +1 포인트입니다)

  • 취하다 not (Q)

  • 취하다 (P and not(P))

  • (P and not(P))파생 할 때 And Elim 사용{P, not(P)}

  • 에 대한 사용 및 소개 P및 not(Q)파생(P and not(Q))

  • 사용하기 위해 파생 된 진술에 And And Elim 사용 P

새로운 P제안은 이전에 도출 한 다른 제안과 다릅니다. 즉 그것은 가정에 의존 not(Q)하고 (P and not(P)). 원래의 진술은에 의존하는 반면 (P and not(P)). 이를 통해 다음을 수행 할 수 있습니다.

  • 소개에 대한 P소개 not(Q) implies P(여전히 (P and not(P))가정에 의존 )

  • 에 대한 사용 및 소개 not(P)및 not(Q)파생 (3 단계)(not(P) and not(Q))

  • And Elim을 방금 파생 한 진술에 사용하십시오 not(P)
    (현재는 의지합니다 not(Q)).

  • 새로운 소개에 대한 not(P)소개not(Q) implies not(P)

  • 우리는 지금에 부정 제거를 사용 not(Q) implies not(P)하고 not(Q) implies P도출Q

이것은 Q가정에만 의존 (P and not(P))하므로 증명을 마무리 할 수 ​​있습니다.

  • Q파생을 소개하는 경우(P and not(P)) implies Q

이 증거는 총 11 점입니다.

답변

점수 : 81

각 줄의 가치는 1 점입니다. 드 모건의 법칙은 진술 (3)과 (6)에 있습니다. 괄호 안의 레이블은 바로 앞에 있지 않은 경우 줄이 의존하는 이전 문장을 나타냅니다.

(a) assume P {
    (aa) P ^ P
    (ab) P
    (ac) P v Q
} (a1) P -> P
  (a2) P -> P v Q
(1) assume ~P ^ ~Q {
    (1a) assume P v Q {
        (1aa) assume Q {
            (1aaa) assume ~P {
                (1aaaa) Q ^ Q [1aa]
                (1aaab) Q
                (1aaac) ~Q [1]
            } (1aaa1) ~P -> Q
              (1aaa2) ~P -> ~Q
            (1aab) P
        } (1aa1) Q -> P
        P [1a, a1, 1aa1]
        ~P [1]
    } (1a1) P v Q -> P
      (1a2) P v Q -> ~P
    (1b) ~(P v Q)
} (11) ~P ^ ~Q -> ~(P v Q)
(2) assume ~(P v Q) {
    (2a) ~(P v Q) ^ ~(P v Q)
    (2b) assume P {
        (2aa) ~(P v Q) [2a]
    } (2b1) P -> ~(P v Q)
    (2c) ~P [a2, 2b1]
    (2d) assume Q {
        (2da) ~(P v Q) [2a]
        (2db) P v Q
    } (2d1) Q -> ~(P v Q)
      (2d2) Q -> P v Q
    (2e) ~Q
    (2f) ~P ^ ~Q
} (21) ~(P v Q) -> ~P ^ ~Q
(3) ~(P v Q) == ~P ^ ~Q [11, 21]
(4) assume ~P v ~Q {
    (4a) assume ~P {
        (4aa) assume P ^ Q {
            (4aaa) P
            (4aab) ~P ^ ~P [4a]
            (4aac) ~P
        } (4aa1) P ^ Q -> P
          (4aa2) P ^ Q -> ~P
        (4ab) ~(P ^ Q)
    } (4a1) ~P -> ~(P ^ Q)
    (4b) assume ~Q {
        (4ba) assume P ^ Q {
            (4baa) Q
            (4bab) ~Q ^ ~Q [4b]
            (4bac) ~Q
        } (4ba1) P ^ Q -> Q
          (4ba2) P ^ Q -> ~Q
        (4bb) ~(P ^ Q)
    } (4b1) ~P -> ~(P ^ Q)
    (4c) ~(P ^ Q) [4, 4a1, 4b1]
} (41) ~P v ~Q -> ~(P ^ Q)
(5) assume ~(P ^ Q) {
    (5a) assume ~(~P v ~Q) {
        (5aa) ~(~P v ~Q) ^ ~(P ^ Q) [5, 5a]
        (5ab) assume ~P {
            (5aba) ~P v ~Q
            (5abb) ~(~P v ~Q) [5aa]
        } (5ab1) ~P -> ~P v ~Q
          (5ab2) ~P -> ~(~P v ~Q)
        (5ac) P
        (5ad) assume ~Q {
            (5ada) ~P v ~Q
            (5adb) ~(~P v ~Q) [5aa]
        } (5ad1) ~Q -> ~P v ~Q
          (5ad2) ~Q -> ~(~P v ~Q)
        (5ae) Q
        (5af) P ^ Q [5ac, 5ae]
        (5ag) ~(P ^ Q) [5aa]
    } (5a1) ~(~P v ~Q) -> P ^ Q
      (5a2) ~(~P v ~Q) -> ~(P ^ Q)
    (5b) ~P v ~Q
} (51) ~(P ^ Q) -> ~P v ~Q
(6) ~(P ^ Q) == ~P v ~Q [41, 51]

답변

점수 : 59

설명

이 스타일을 읽을 수있을 때 증명 용으로 구조와 같은 트리를 사용합니다. 각 줄에는 사용 된 규칙의 수가 주석으로 표시됩니다. 예를 들어, 챌린지의 “예제 1″은이 트리로 표시됩니다 (아래에서 위로).

소개

알 수없는 계수 A, B 및 가정 Γ에 유의하십시오. 따라서 이것은 정리가 아닙니다. 정리 증명 방법을 설명하기 위해 다음과 같이 A를 가정 하고 Or 소개를 사용합니다.

소개

이제 이것은 여전히 ​​가정 A 에 달려 있지만 If-introduction을 적용하여 정리를 도출 할 수 있습니다.

소개

그래서 우리는 정리 steps A → ( A ∨ B )를 총 3 단계 (1 가정 및 2 적용 규칙) 로 도출 할 수있었습니다 .

이를 통해 DeMorgan의 법칙을 증명하는 데 도움이되는 몇 가지 새로운 규칙을 계속 증명할 수 있습니다.

추가 규칙

먼저 폭발 의 원리를 도출하고 추가 증거에서 PE 로 표시 합시다 .

체육

이것에서 우리는 또 다른 형태를 파생시킵니다 : A ⊢ ¬ A → X- 우리는 그것을 CPE 라고 부릅니다 :

체육

우리는 부정 용어 (¬) 가정이 또 다른 하나를 필요로 참조합니다 CPE – :

NCPE

우리가 (파생 된 두 가지 규칙에서 CPE 및 CPE – ), 우리는 중요한 규칙 유도 할 수있다 이중 부정을 :

DN

할 다음 일은 같은 것을 증명하는 것입니다 후건 부정의 형식 – 따라서 MT를 :

MT

렘마

렘마 A

렘마 A1

다음과 같은 규칙이 두 번 필요합니다.

LA1

렘마 A

방금 입증 된 보조 정리를 두 번 인스턴스화하면 동등성의 한 방향을 보여줄 수 있으므로 최종 증명에 필요합니다.

라

렘마 B

다른 방향을 보여주기 위해, 우리는 ( A ∨ B의 인수 A 와 B 모두에 대해) 아주 반복적 인 것들을 두 번 수행해야합니다. 이것은 여기서 증거를 더 골프화 할 수 있음을 의미합니다.

렘마 B1 ‘

LB1_

렘마 B1

LB1

렘마 B2 ‘

LB2_

렘마 B2

LB2

렘마 B

마지막으로 B1 과 B2 의 결론 :

LB

실증

일단 우리가이 두 진술을 증명하면 :

  • Lemma A : ⊢ ( A ∨ B ) → ¬ (¬ A ʌ ¬ B )
  • Lemma B : ⊢ ¬ ( A ∨ B ) → (¬ A ʌ ¬ B )

첫 번째 등가 (¬ ( A ∨ B ) ≡ ¬ A ʌ ¬ B )를 다음과 같이 증명할 수 있습니다 .

P1

그리고 Iff-Elimination과 함께 방금 입증 된 규칙으로 우리는 두 번째 동등성을 증명할 수 있습니다.

P2

점수에 대해 잘 모르겠습니다. 내가 올바르게했다면 문제가 있는지 알려주세요.

설명

출처

누군가가 tex 소스를 원한다면 ( mathpartir 필요 ) :

In the following a rule \textbf{XYZ'} will denote the rule XYZ's second last
step, for example \textbf{PE'} will be $ A \land \lnot A \vdash X $.

\section*{Principle of Explosion [PE]}

\begin{mathpar}
  \inferrule*[Left=$\to$-Intro,Right=10]
    {\inferrule*[Left=$\lnot$-Elim,Right=9]
      {\inferrule*[Left=$\to$-Intro,Right=4]
        {\inferrule*[Left=$\land$-Elim,Right=3]
          {\inferrule*[Left=Axiom,Right=2]
            { }
            { A \land \lnot A, \lnot X \vdash A \land \lnot A }
          }
          { A \land \lnot A, \lnot X \vdash A }
        }
        { A \land \lnot A \vdash \lnot X \to A } \\
       \inferrule*[Right=$\to$-Intro,Left=4]
          {\inferrule*[Right=$\land$-Elim,Left=3]
            {\inferrule*[Right=Axiom,Left=2]
              { }
              { A \land \lnot A, \lnot X \vdash A \land \lnot A }
            }
            { A \land \lnot A, \lnot X \vdash \lnot A }
          }
        { A \land \lnot A \vdash \lnot X \to \lnot A }
      }
      { A \land \lnot A \vdash X }
    }
    { \vdash (A \land \lnot A) \to X }
\end{mathpar}

\section*{Conditioned PE [CPE]}

\begin{mathpar}
  \inferrule*[Left=$\to$-Intro,Right=5]
  {\inferrule*[Left=$\to$-Elim,Right=4]
    {\inferrule*[Left=$\land$-Intro,Right=3]
      {\inferrule*[Left=Axiom,Right=1]
        { } { A \vdash A } \\
       \inferrule*[Right=Axiom,Left=1]
        { } { \lnot A \vdash \lnot A }
      }
      { A, \lnot A \vdash A \land \lnot A } \\
     \inferrule*[Right=PE,Left=0]
      { } { \vdash (A \land \lnot A) \to X }
    }
    { A, \lnot A \vdash X }
  }
  { A \vdash \lnot A \to X }
\end{mathpar}

to get \textbf{CPE$^-$}:

\begin{mathpar}
  \inferrule*[Left=$\to$-Intro,Right=1]
    {\inferrule*[Left=CPE',Right=0]
      { }
      { A, \lnot A \vdash X }
    }
    { \lnot A \vdash A \to X }
\end{mathpar}

\section*{Double Negation [DN]}

\begin{mathpar}
  \inferrule*[Left=$\equiv$-Intro,Right=5]
    {\inferrule*[Left=$\to$-Intro,Right=2]
      {\inferrule*[Left=$\lnot$-Elim,Right=1]
        {\inferrule*[Left=CPE$^-$,Right=0]
          { }
          { \lnot\lnot A \vdash \lnot A \to X } \\
          \inferrule*[Right=CPE$^-$,Left=0]
          { }
          { \lnot\lnot A \vdash \lnot A \to \lnot X }
        }
        { \lnot\lnot A \vdash A }
      }
      { \vdash \lnot\lnot A \to A } \\ \\ \\
      \inferrule*[Left=$\to$-Intro,Right=2]
        {\inferrule*[Left=$\lnot$-Intro,Right=1]
          {\inferrule*[Left=CPE,Right=0]
            { }
            {  A \vdash \lnot A \to X } \\
            \inferrule*[Right=CPE,Left=0]
            { }
            { A \vdash \lnot A \to \lnot X }
          }
          { A \vdash \lnot\lnot A }
        }
        { \vdash A \to \lnot\lnot A }
    }
    { \vdash \lnot\lnot A \equiv A  }
\end{mathpar}

\section*{Modus Tollens [MT]}

\begin{mathpar}
  \inferrule*[Left=$\to$-Intro,Right=6]
    {\inferrule*[Left=$\lnot$-Intro,Right=5]
      {\inferrule*[Left=Axiom,Right=1]
       { }
       { A \to \lnot B \vdash A \to \lnot B } \\
       \inferrule*[Right=$\to$-Intro,Left=3]
         {\inferrule*[Right=Axiom,Left=2]
           { }
           { A, B \vdash B }
         }
         { B \vdash A \to B }
       }
      { A \to \lnot B, B \vdash \lnot A }
    }
    { A \to \lnot B \vdash B \to \lnot A }
\end{mathpar}

\section*{Lemma A}

\textbf{Lemma A1}:

\begin{mathpar}
  \inferrule*[Left=$\to$-Intro,Right=9]
    {\inferrule*[Left=$\lor$-Elim,Right=8]
       { \inferrule*[Left=CPE,Right=3]
          {\inferrule*[Left=$\land$-Elim,Right=2]
            {\inferrule*[Left=Axiom,Right=1]
              { }
              { A \land B \vdash A \land B }
            }
            { A \land B \vdash B}
          }
          { A \land B \vdash \lnot B \to X } \\
         \inferrule*[Right=CPE,Left=3]
          {\inferrule*[Right=$\land$-Elim,Left=2]
            {\inferrule*[Right=Axiom,Left=1]
              { }
              { A \land B \vdash A \land B }
            }
            { A \land B \vdash A }
          }
          { A \land B \vdash \lnot A \to X } \\ \\ \\
         \inferrule*[Right=Axiom,Left=1]
          { }
          { \lnot A \lor \lnot B \vdash \lnot A \lor \lnot B }
       }
       { A \land B, \lnot A \lor \lnot B \vdash X }
    }
    { \lnot A \lor \lnot B \vdash (A \land B) \to X }
\end{mathpar}

\textbf{Lemma A}:

답변

점수 : 65

드 모건 법률은 30 행과 65 행입니다.

(예를 들어 처음에 추상화 할 수있는 반복 된 증거가 있는지 확인하기 위해 골프를 치는 데 특별한 노력을 기울이지 않았습니다.)

 1. assume ~(P\/Q)
 2.   assume P
 3.     P\/Q  by or-introl, 2
 4.   P -> P\/Q  by impl-intro, 2, 3
 5.   P -> ~(P\/Q)  by impl-intro, 2, 1
 6.   ~P  by neg-intro, 4, 5
 7.   assume Q
 8.     P\/Q  by or-intror, 7
 9.   Q -> P\/Q  by impl-intro, 7, 8
10.   Q -> ~(P\/Q) by impl-intro, 7, 1
11.   ~Q  by neg-intro, 9, 10
12.   ~P /\ ~Q  by and-intro, 6, 11
13. ~(P\/Q) -> ~P/\~Q  by impl-intro, 1, 12
14. assume ~P /\ ~Q
15.   ~P, ~Q  by and-elim, 14
16.   assume P \/ Q
17.     assume P
18.     P -> P  by impl-intro, 17, 17
19.     assume Q
20.       assume ~P
21.       ~P -> Q  by impl-intro, 20, 19
22.       ~P -> ~Q  by impl-intro, 20, 15
23.       P  by neg-elim, 21, 22
24.     Q -> P  by impl-intro, 19, 23
25.     P  by or-elim, 16, 18, 24
26.   P\/Q -> P  by impl-elim, 16, 25
27.   P\/Q -> ~P  by impl-elim, 16, 15
28.   ~(P\/Q)  by neg-intro, 26, 27
29. ~P/\~Q -> ~(P\/Q)  by impl-intro, 14, 28
30. ~(P\/Q) <-> ~P/\~Q  by iff-intro, 13, 29
31. assume ~(P/\Q)
32.   assume ~(~P\/~Q)
33.     assume ~P
34.       ~P\/~Q  by or-introl, 33
35.     ~P -> ~P\/~Q  by impl-intro, 33, 34
36.     ~P -> ~(~P\/~Q)  by impl-intro, 33, 32
37.     P  by neg-elim, 35, 36
38.     assume ~Q
39.       ~P\/~Q  by or-intror, 38
40.     ~Q -> ~P\/~Q  by impl-intro, 38, 39
41.     ~Q -> ~(~P\/~Q)  by impl-intro, 38, 32
42.     Q  by neg-elim, 40, 41
43.     P /\ Q  by and-intro, 37, 42
44.   ~(~P\/~Q) -> P /\ Q  by impl-intro, 32, 43
45.   ~(~P\/~Q) -> ~(P /\ Q)  by impl-intro, 32, 31
46.   ~P \/ ~Q  by neg-elim, 44, 45
47. ~(P/\Q) -> ~P\/~Q  by impl-intro, 31, 46
48. assume ~P\/~Q
49.   assume ~P
50.     assume P/\Q
51.       P, Q  by and-elim, 50
52.     P/\Q -> P  by impl-intro, 50, 51
53.     P/\Q -> ~P  by impl-intro, 50, 49
54.     ~(P/\Q)  by neg-intro, 52, 53
55.   ~P -> ~(P/\Q)  by impl-intro, 49, 54
56.   assume ~Q
57.     assume P/\Q
58.       P, Q  by and-elim, 57
59.     P/\Q -> Q  by impl-intro, 57, 58
60.     P/\Q -> ~Q  by impl-intro, 57, 56
61.     ~(P/\Q)  by neg-intro, 59, 60
62.   ~Q -> ~(P/\Q)  by impl-intro, 56, 61
63.   ~(P/\Q)  by or-elim, 48, 55, 62
64. ~P\/~Q -> ~(P/\Q)  by impl-intro, 48, 63
65. ~(P/\Q) <-> ~P\/~Q  by iff-intro, 47, 64

답변