[Automata] Automata Prove: Examples of Proving Sets

Examples of Proving Sets

---

포스트 난이도: HOO_Junior

[Notice] 포스트 난이도에 대한 설명

---

 

# Examples

Automat에서 Set을 증명하는 방법에 대한 예제를 살펴보도록 하자.

# Prove 
For any two sets A and B, A ∩ B ⊆ B ∩ A.

위와 같은 예제는 흔히 Set 관련 내용에서 쉽게 확인할 수 있는 문장이다.

우선은 For any two sets이기 때문에 Automata에서는 for every나 for all이 아닌 exist인 것을 확인할 수 있다.

다음으로 A와 B라는 set이 존재하며, A와 B는 서로가 교집합이면서 A n B는 B n A에 속하면서 동일하다는 걸 확인할 수 있다.

Automata에서 증명은 backward 방식을 기본적으로 따르기 때문에 이 역시도 backward 방식을 사용하여 증명이 가능하다.

1. ∀x
2. if(assume) x ∈ A n B
3. x ∈ A and x ∈ B
4. x ∈ A
5. x ∈ B
6. x ∈ B and x ∈ A
7. x ∈ B n A
8. x ∈ A n B implies x ∈ B n A
9. ∀x, x ∈ A n B implies x ∈ B n A
10. A n B ⊆ B n A, if ∀x, x ∈ A n B implies x ∈ B n A
11. A n B ⊆ B n A
12. QED

위와 같은 방법으로 Backward를 통해서 set의 경우도 증명이 가능하다.

Backward 방식의 증명에서 중요한 점은 하위 단계이면서 작은 단위부터 하나씩 증명해 나가는 것이다.

마치 최종 보스를 처리하러 가듯이 단계별 증명이 필요하다.

각 단계별 증명이 이루어지지 않을 경우 증명에 대한 전체적인 참, 거짓 여부의 판단이 되지 않는 모호한 상황이 발생할 수 있으니 꼭 단계별로 작은 단위부터 정의를 해준다.

 

---