[Automata] Proof Statements by using Backward [Temp]

Proof Statements by using Backward

---

포스트 난이도: HOO_Junior

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

---

# Working Backwards

 

# Poof Statements

Backwards는 시스템 디자인에 적용하기 좋은 prove 방식이다. 문제를 해결하는데 있어서 결과부터 시작하여 문제의 원인을 도출해내기 좋은 방식이기 때문이다. working backward 는 개발자로써 단계별 시스템 개발 및 유지보수를 할때 실질적으로 도움이 되는 개념이기에 statements 증명에 backward를 적용하여 backward를 익히기에 좋다. Backward를 하는 과정의 첫번째는 최종 결과를 마지막에 작성해준다. QED 다음에 오는 마지막 statements가 증명하고자 하는 결과인 셈이다. 다음으로 순서대로 문장을 decompose해가면서 하나하나 증명해주는 과정을 거친다. 모든 statement는 true라고 가정을 하고 증명이 이루어지는 방식이 backward 방식이다. 각 단계별 증명은 다음 단계, 또는 이전 단계 증명과 연속적으로 연결되어 있어서 최종적으로 산출하고자하는 결과의 statments를 증명할 수 있다.

공식화가 되지 않은 Statement 자체를 알고리즘이나 프로그래밍을 하기 위해서는 Statements 자체를 우선적으로 분석해야 한다. 분석한 문장을 통해 각 문장이 가진 특징을 알고리즘 화가 가능하다. 이것을 우리는 Proof statements 과정이라고 한다. 모든 Satements는 definition과 logical symbol로 구성되어 있으며 proof 과정을 통해 확인이 가능하다.

Proof statements는 backward 방식을 통해서 쉽게 단계별 증명이 가능하다. 이때 중점적으로 살펴볼 부분이 definition과 logical symbol에 해당하는 primal concept과 primal operator이다. primal concept과 primal operator만 statements 안에서 잘 찾아내도 backward 증명 과정을 거의 다 끝난 것이나 다름이 없다.

Backward proof을 할때는 항상 최종 statement를 마지막에 작성을 해주고 시작하면 단계별 증명하기에 좋다. 한마디로 최종적으로 증명하고자 하는 문장을 마지막에 작성하고 하나씩 문장을 분해해준다고 생각하면 된다. 이때 문장이 나눠지는 기준이 바로 primal concept과 primal operator이다. 우선 and나 or과 같은 primal operator가 statement에 있다면 이것을 2개의 statement로 나누어준다. 그다음에 각 문장에 있는 primal concept을 정의해주면 backward proof이 이루어진다. 이것을 우리는 one step backward 또는 decomposition이라고 한다. 여기서 유의할 점은 or의 경우는 한 가지 조건만 충족되면 결과가 산출되는 logical symbol에 해당한다. 따라서 backward proof에서도 or로 이루어진 statements의 경우에는 하나의 primal concept만 증명이 이루어져도 상관이 없다. 하지만 and의 경우에도 모든 primal concept의 증명이 이루어져야 한다.

If then의 경우에는 if의 primal concept과 then의 primal concept 모두 backward proof가 이루어져야 한다. 이때도 backward의 방식에 따라 마지막에서부터 반대로 하나씩 statement를 분해해가면서 증명을 해주면 된다. 한마디로 then 부분의 primal concept을 먼저 증명해주고 제일 위에는 if statement에 대한 부분의 primal concept을 증명해주면 된다.

If and only if는 if then statement과 다소 다르다. if and only if는 모든 조건이 충족이 되어야 결과가 산출되기 때문에 backward proof에서도 이러한 특징을 증명해줘야 한다. If라는 조건이 2개가 포함되어 있는 statement이다보니 첫 번째 if일 때와 두 번째 if일인 경우가 모두 포함되는 특징을 backward proof 방식으로 증명을 해줘야 한다는 것이다.

Exist와 for every는 backward proof에 있어서 중요한 부분 중에 하나이다. 우선 for every는 모든 값을 의미하기에 backward proof에서 for every에 대한 조건을 제시해줘야 한다. 예를 들어 consider any x와 같이 조건 없는 모든 x 값이라는 걸 backward proof에서 나타내 줘야 한다. 반면에 exist의 경우에는 몇 가지의 사례만 있어도 충족되기 때문에 모든 값을 대변하지는 않는다. 따라서 exist를 증명할 때는 한두 가지의 사례를 들면 exist 증명이 이루어진다.

 

---

# subTitle

wirting

 

---

# subTitle

wirting

 

---