명제논리의 기초(4) - 연역추론의 규칙들

 

모든 명제들의 관계는 원칙적으로 진리표로 나타내고, 그에 대한 T/F를 결정할 수 있습니다. 하지만, 진리표가 번거로운 경우가 있습니다.

 

가령, p q r s를 복합하여 만들어지는 진리표의 T/F의 개수는 총 2 x 2 x 2 x 2 = 16개입니다. 만약 이게, n개의 명제들의 관계라면 2^n개가 되어버리게 됩니다.

 

이런 번거로움을 제거하기 위해서 연역추론을 사용하게 됩니다.

 

연역추론을 위해서 사용되는 몇가지 정리들이 있습니다.

 

p ⇔ ~(~p)

p→q ⇔ (~p ∨ q)

p∧q ⇒ p

p∧q ⇒ q

p∧p ⇔ p

p∨p ⇔ p

p∧q ⇔ q∧p (commutative law)

p∨q ⇔ q∨p (commutative law)

p∧t ⇔ p (t = tautology. t ⇔ p∨~p) 

p∨t ⇔ t

p∧c ⇔ c (c = contradiction. c⇔ p∧~p)

p∨c ⇔ p

p∧(q∧r) ⇔ (p∧q)∧r (associative law)

p∨(q∨r) ⇔ (p∨q)∨r (associative law)

p∧(q∨r) ⇔ (p∧q)∨(p∧r) (distributive law)

p∨(q∧r) ⇔ (p∨q)∧(p∨r) (distributive law)

(p→q)∧p ⇒ q (Modus Ponens)

(p→q)∧~q ⇒ ~p (Modus Tollens)

~(p∧q) ⇔ ~p∨~q (De morgan's law)

~(p∨q)⇔ ~p∧~q (De morgan's law)

(p→q)∧(q→r) ⇒ (p→r) (Transitive Law)

(p∨q)∧~q ⇒ p

 

 

당...당황하셨나요? 수만 많지 기본적으로 많은 사람들이 알고 있는 정리들입니다. p→q ⇔ (~p ∨ q)랑 modus랑 맨 아래 것만 빼고는 대부분의 사람들이 아는 정리라고 생각합니다.

 

위의 모든 것들은 진리표로 증명될 수 있는 것들이구요, 필요하시다면 직접 증명해보는 것이 좋습니다.

 

위의 것들이 증명되었다는 전제 하에서 연역추론들을 사용하여 명제의 관계를 살펴볼 수 있습니다.

(Modus와 Transitive같은 것들은 연역추론들로부터 이끌어 낼 수 있지만, 자주 사용하는 정리들이라 연역추론을 하는데 사용되는 규칙으로 넣어봤습니다)

 

다음 포스트부터는 위의 것들이 진리표로 증명되었다는 가정하에서 글을 쓰겠습니다

(혹시나 저것들의 진리표를 구하는데 어려움이 있다면 댓글을 남기시면 증명해드리겠습니다)