명제논리(Propositional Logic)

 몇몇 논리퍼즐들을 풀기 위해서는 논리 법칙들을 잘 알고 있어야 한다. 주어진 명제가 참인지 거짓인지 밝혀내는 과정에서 일련의 법칙을 모른다면 복잡하게 구성된 명제들의 참과 거짓을 이상하게 해석할 수 있기 때문이다. 이 글에서는 주로 쓰이는 부정(negation)과 여러 연결사(connectives)들을 볼 것이다. 이를 위해 [1]를 참고했다.


 1.부정(Negation)
 어떤 명제 p가 있을 때, 'p가 아니다 (not p)'를 p의 부정이라하고 기호로는 ~p혹은 ¬p로 나타낸다. ~p의 진리치는 p와 반대이다. 즉, p가 참일때 ~p는 거짓이고, p가 거짓일때 ~p는 참이다. 이를 진리표로 나타내면,

 2. 연언문(Conjunction)
 어떤 명제 p와 q가 있을 때, 'p 그리고 q (p and q)'를 p와 q의 연언이라 하고, 기호로는 p∧q로 나타낸다. p∧q의 진리치는 p와 q가 모두 참일때만 참이고, 다른 때는 모두 거짓이다. 이를 진리표로 나타내면,

따라서 한 문장이라고 거짓이면 연언문 전체는 거짓이 된다.


 3. 선언문(Disjunction)
 어떤 명제 p와 q가 있을 때, 'p 혹은 q (p or q)'를 p와 q의 선언이라 하고, 기호로는 p∨q로 나타낸다. p∨q의 진리치는 p와 q가 보두 거짓일때만 거짓이고, 다른 때는 모두 참이다. 이를 진리표로 나타내면,

따라서 한 문장이라도 참이면 선언문 전체는 참이 된다.
 '혹은'에 대해서는 일상생활 속 말과 좀 다른 부분이 있다. 가령 '술을 마시거나 담배를 피우는 것은 몸에 좋지않다.'에서는 분명 술, 담배 모두 좋지 않다는 말을 하고 있다. 허나, '커피 혹은 녹차가 후식으로 나온다.'에서는 분명 커피와 녹차를 모두 마실 수는 없다. 일상에서는 이렇게 '혹은'이 포괄적으로 쓰일 수 있지만, 여기에선 전자의 방식으로만 쓰기로 한다.


 4. 조건문 (Conditional statement)
 어떤 명제 p와 q가 있을 때, 조건문 'p이면 q이다 (if p, then q)'를 기호로 p→q로 나타낸다.  p→q는 p가 참이고, q가 거짓일 때만 거짓이고, 다른 때는 모두 참이다. 이를 진리표로 나타내면,

조건이라는 말처럼, 조건문에서는 p일때를 주목해야 한다. p인데, q이면, 조건문은 참이고, p인데, q가 아니면, 조건문은 거짓이다. 가령, '제가 당선되면, 이러저러 하겠습니다.'라고 말한 당선자가 공약을 지키면 진실한 사람이고, 안지키면 위선자(거짓말쟁이)가 된다.
 문제는 p가 아닐때이다. p가 아니면 더이상 조건문에 왈가왈부할 이야기가 없으므로 q의 진위에 상관없이 조건문은 다 참으로 본다.


 5. 쌍조건문 (Biconditional statement)
 어떤 명제 p와 q가 있을 때, 쌍조건문 'p이고 오직 그 경우에 한해 q (p if and only if)'를 기호로 p↔q로 나타낸다. p↔q는 p와 q가 같은 진리치를 가질 때 참이고, 다른 진리치를 가질 때는 거짓이다. 이를 진리표로 나타내면,

 쌍조건문이라는 말 처럼 이 복합명제는 'p이면 q이다.'와 'q이면 p이다.'가 and로 연결된 명제, (p→q)∧(q→p)로 생각할 수 있다. 실제로 진리표를 만들어서 (p→q)∧(q→p)의 진리치를 살펴보면 p↔q와 진리치가 같음을 알 수 있다. 
 쌍조건문은 연결된 두 명제가 진리치가 같을 때만 참이기 때문에, 동치(同値)의 개념으로 사용할 수 있다. 따라서 참인 명제와 동치인 명제는 참이고, 거짓인 명제와 동치인 명제는 거짓이다.



참고
1. Rosen, Discrete Mathematics and its applications (6th)