[how to prove it] 2장(2)

2.3.2 모순 찾기

Givens	Goal
a	c
!b

=> contradiction을 적용하면?

Givens	Goal
a	Contradiction
!b
!c

• contradiction을 사용(결론이 false라고 가정했을 때)하면 증명에 이용할 수 있는 다른 단서를 얻을 수 있지만 => !c가 Givens에 추가됨
• goal이 모호해진다는 단점이 있다. => Goal이 a와 !b, !c를 가지고 모순을 증명해내는 것으로 바뀜

그러면 이런 단점을 극복하는 방법은? Given 중에 negation이 붙어있는 것을 negation을 빼고 Goal로 채택한다. 그러면 Goal이 분명해진다.

=> Goal을 분명하게 만들기

Givens	Goal
a	b
!c

Given !b를 negation을 빼서 Goal로 채택한다.

• 이 전략은 given의 논리 형식을 이요한 첫번째 전략이다.
• 다른 전략을 적용할 수 있다면 다른 전략을 먼저 적용하는 것이 좋지만 방법이 없다면 contradiction을 사용해라

3.2.3

• 많은 경우에, statement의 논리구조는 해당 statement의 수학적인 단어나 심볼의 정의를 적는 과정에서 드러난다.

• Givens

1. A 차집합 B는 C에 속한다.
2. x는 A 차집합 C에 속한다.

• Goal: x는 B에 속한다.

=> Goal은 논리연산을 포함하지 않는다. 해볼 수 있는 것이 없기 때문에 Contradiction을 시도한다.

Givens	Goal
A 차집합 B는 C에 속한다.	Contradiction
x는 A 차집합 C에 속한다.
x는 B에 속하지 않는다.

• 이 상태에서 Goal을 분명히 만들기 위해 부정형으로 쓰인 Givens중 하나를 Goal로 채택할 수 있다.

• 그런데 마지막 항목은 방금 Goal에서 Given으로 바꾸기 위해 negation을 붙인 것이므로 이것은 사용할 수 없다.

• 나머지 중 하나인 'x는 A 차집합 C에 속한다'를 풀어쓰면 negation이 붙은 Given을 만들 수 있다.

  • x는 A에 속한다. x는 C에 속하지 않는다.

• 이것을 새로운 Goal로 채택하면 Goal이 분명해진다.

• 새로운 Goal: "x는 C에 속한다."

3.2.4 긍정형으로 표현하기

• 방금 한것(Givens에서 negation이 포함된 표현을 찾아 negation을 제거하고 Goal로 삼는 것)은 Contradiction을 전략으로 채택했을 때만 적용할 수 있다.

• 다른 종류의 증명에서는 긍정형으로 statement를 표현함으로써 일을 쉽게 만들 수 있다.

1. Givens가 부정형인 경우에는 긍정형으로 만든다.

2. Given가 P -> Q의 형식인 경우에는 ?

   • 지금까지 Givens와 Goals가 !P인 경우에 대해서 살펴보았고
   • Goals의 form이 P -> Q인 경우(논리 연산을 포함하는 경우)에 대해서 살펴보았다.
   • 이제 Givens의 form이 P -> Q인 경우에 대해서 살펴본다.

P -> Q(!Q -> !P)

• P가 Givens로 주어졌거나 P가 옳다는 사실을 증명할 수 있다면 결론 Q에 대한 Givens로 활용할 수 있다. => "modus poenes"
• Q가 틀렸다는 사실을 증명할 수 있다면 P가 틀렸다고 추론할 수 있다. => "modus tollens"