[Mathematics for Computer Science] 스터디 06

Logical Deductions

Logical Deductions는 논리적 추론이라고 할 수 있는데 여기 중요한 기호들이 나온다.

One fundamental inference rule is modus ponens. This rule says that if P is true and P ⇒ Q is true, then Q is also true. Inference rules are sometimes written in a funny notation.

P

P ⇒ Q

---------------

Q

점선은 원래 실선으로 되어 있어야 한다. 풀어보자면 P가 true이고 P ⇒ Q가 true이면 Q도 true라는 뜻이다. 이것을 modus ponens(논리 긍정식)이라 한다.

Modus ponens is closely related to the proposition (P ∧(P ⇒ Q)) ⇒ Q. Both in some sense say, "if P and P ⇒ Q are true, then Q is true". This proposition is an example of tautology, because it is true for eery setting of P and Q. The difference is that this tautology is a single proposition, whereas modus ponens is an inference rule that allows us to deduce new propositions from old ones. However, if we accept modus ponens then a eneral theorem of logic says that for each tautological implication there is an associated inference rule.

예를들어 ((P ⇒ Q) ∧ (Q ⇒ R)) ⇒ (P ⇒ R) and ((P ⇒ Q) ∧ ¬Q) ⇒ ¬P 둘다 tautologies(동어반복, 항진식)이다. 말로 풀어쓰면 P가 Q이고, Q가 R이라면, P는 R이다. 은 P가 Q이고 Q가 R이 아니라면(false라면) P는 R이 아니다(false다)라는 말과 동일하다.

여기서 ¬이것은 not을 나타낸다.