[Automata] Prove Statements

Prove Statements

---

포스트 난이도: HOO_Junior

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

---

 

# Prove Statement

Statement에 대한 정의까지 알아봤으니, Statement를 증명하는 것에 대해서 알아보도록 하자.

Statement를 보다 쉽게 증명하기 위해서는 2가지 방법을 사용해볼 수 있다.

우선적으로는 Tree structure를 사용하여 시각적으로 특정 Statement가 어떤 구조인지를 파악한다.

이후에 Tree structure를 참고하여 Statement 증명 Process를 진행한다.

여기서 말하는 Tree structure는 아래와 같은 구조를 의미한다.

---

Fig01.

---

Fig02.

---

Tree structure에 대한 구체적인 설명은 생략하고 Statement 증명하는 과정으로 넘어가도록 하겠다.

---

# Prove Statement Conditions

Statement를 증명하기 위해서는 조건이 있다.

물론 해당 조건을 따르지 않고도 충분히 Algorithm에 대한 증명이 가능할 수 있지만 해당 조건을 따르면 보다 더 쉽게 증명이 가능하다.

첫 번째로는 앞서 이야기한 Tree structure를 활용한다.

Tree structure를 통해 시각적 참고를 하여 구조에 대한 이해를 돕는다.

두 번째로는 working backwards이다.

Working backwards는 증명하는 과정 자체를 반대로 수행한다는 걸 의미한다.

한마디로 산출된 결과를 하나하나 되짚어 보면서 증명하는 걸 의미한다.

Fig01.

위의 Fig01. Tree structure를 보면, 최종 산출되는 statement는 Amy가 James의 부모님인지에 대한 것이다.

한마디로 Is Amy a parent of James?라는 것에 대한 근거가 필요한데 Tree 구조의 하위 단계를 보면 Mother이거나 Father이라는 조건이 나온다.

다만 위의 Tree 구조만 놓고 보면 엄마나 아빠가 아닌 경우에도 부모가 될 수 없다.

왜냐하면 statement를 정의하기 위한 구성 요소 중 하나인 logical symbol로 if를 사용하고 있기 때문이다.

따라서 위의 Tree structure만 놓고 본다면, Amy가 엄마나 아빠는 아니면 부모가 될 수 없고, 반대로 Amy가 엄마나 아빠 중에 하나이면 부모가 될 수 있다는 결과가 나오며 이것이 참인 결과로 산출될 수 있다.

따라서 특정 문제에서나 원하는 결과값이 아빠나 엄마가 아니지만 부모가 될 수 있다는 결과를 산출하고 싶다면 위의 Tree 구조는 잘못된 것이다.

하지만 엄마나 아빠이면 부모다라는 전제 조건이라면 위의 Tree 구조는 맞는 것이다.

이제 Backward를 통해서 해당 statement를 증명해보도록 하자.

Prove: Amy is a parent of James
Proof:
1. Amy is the mother of James
2. Amy is the mother of James or Amy is the father of James
3. Amy is a parent of James if Amy is the mother of James or Amy is the father or James
4. Amy is a parent of James
QED

위의 code block에 있는 증명 방식이 backward를 사용한 증명 방식이다.

Tree 구조에서 하위 단계부터 하나하나 차례대로 증명하는 방식이 바로 Backward인 것이다.

Backward 방식을 통해 Statement 증명이 가능하다.

---