Handbook : propositions and logical operation, equivalences

사실은...

기호논리학의 또 다른 거장, 버트런드 러셀Bertrand Russell와 화이트 헤드Whitehead는 그들의 공동 저서 수학원리principia mathematica에서 세상의 수학들을 기호논리로 다루려고 노력했습니다. 그들은 수학원리에서 다음과 같이 기호논리를 사용합니다.

논리곱logical product은 . 로 표현했습니다. 따라서 p.q는 "p and q"를 뜻합니다. 그러나 때로 .는 괄호parentheses를 표현하기도 하는데요. 다음의 명제를 봅시다.

⊦ :p∨q.⊃.q∨p

우선, ⊦ 는 다음이 반드시 참이라고 주장하는 것입니다. 이는 정리theorem 이거나 공리axiom일 수 있습니다. 그리고 :는 . 보다 한 단계 더 높은 중괄호라고 봅니다. 

⊦ [p∨q.⊃.q∨p]

⊦ 이후의 콜론 : 의 범위는, 즉 중괄호의 범위는 시작한 곳에서 부터 끝까지 또는 다음의 콜론을 만날 때 까지 계속됩니다. 그다음 ⊃는 조건문 "if ~, then ~"을 뜻합니다. 조건문 ⊃ 주변의 점 .은 전항과 후항을 나누는 괄호의 역할을 합니다. 따라서 다음과 같습니다.

⊦ [(p∨q)→(q∨p)]

축약형은 다음과 같습니다

⊦ (p∨q)→(q∨p)

이는 교환법칙commutative law입니다. 자 다음의 명제를 살펴봅시다. 

⊦ :.p⊃q.⊃:q⊃r.⊃.p⊃r

천천히 해석해봅시다. :. 는 대괄호로 볼 수 있습니다. 다음과 같이 변환합니다.

⊦ {p⊃q.⊃[q⊃r.⊃.p⊃r]}

그리고 조건문 ⊃의 근처 . 는 괄호를 뜻합니다. 다음과 같이 변환해줍니다.

⊦ {(p→q)→[(q→r)→(p→r)]}

축약형은 다음과 같습니다.

⊦ (p→q)→[(q→r)→(p→r)]

해석은 다음과 같습니다. 

p이면 q라면 다음을 의미한다. q이면 r이라면, p이면 r이다.

마지막으로 다음 명제를 살펴봅시다.

⊦ ::p∨q.⊃:.p.∨.q⊃r:⊃.p∨r

⊦ ::p∨q.⊃{p.∨.q⊃r:⊃.p∨r}

⊦ ::p∨q.⊃{[p.∨.q⊃r]⊃.p∨r}

⊦ ::(p∨q)→{[(p)∨(q→r)]→(p∨r)}

⊦ ::(p∨q)→{[p∨(q→r)]→(p∨r)}

이번에는 :: 도 등장합니다. 이는 대괄호보다 더 높은 우선순위의 괄호이겠죠. 하지만, 대체할 방법이 없으므로 그냥 두겠습니다. 하지만 독자들은 반드시 인지하고 계셔야합니다. 이는 다음과 같이 해석될 수 있습니다.

p 또는 q 라면 다음을 의미한다. p 또는 q이면 r이라면, p 또는 r이다. 또는

p 또는 q가 참이라면 다음을 의미한다. p 또는 q이면 r이다가 참이라면 p 또는 r이 참이다.

서론이 너무 길었네요. 이제는 이제까지 배운 기호논리학을 한번 정리하고 문제를 살펴봅시다.

용어 정의 Definitions 

진리값truth value : 참 또는 거짓, T 또는 F로 표현 가능함.

명제proposition : 진리값으로 표현될 수 있는 진술.

명제 변수propositional variable : 수학 변수, p, q, r 등이 종종 명제를 표현하기 위해 변수로 사용된다.

명제 논리propositional logic(명제 연산propositional calculus) : 명제 변수와 논리 연산자를 이용하여 조합하는 것에 관한 연구

명제 연결사logical connective(논리 연산자logical operator) : 단순한 명제들로부터 복잡한 논리 표현식을 만들기 위한 연산자, 이 때 진리값은 더 단순한 명제들에 의해 결정됨. 이 때 더 단순한 명제들로 분해할 수 없을 때 이를 원자atmoic, 단순simple 명제라고 한다. 보통 이 명제들은 명제 변수 한 개로 표현된다. 

복합 명제compound proposition : 논리 연산자를 하나 이상을 포함하고 있는 명제

진리표truth value : 논리 연산을 하기위해 표를 이용하는 것. 즉, 연산에 있어서 각 진리값 조합을 표를 이용하여 수행하는 것

부정negation : 명제의 부정은 해당 명제의 진리값을 부정한다. 기호로는 ¬, ~, 또는 위첨자 -를 사용

항진(명제)tautology : 원자 명제의 임의의 진리값에 대해서 항상 참인 복합 명제

모순(명제)contradiction : 원자 명제의 임의의 진리값에 대해서 항상 거짓인 복합 명제

P⇒Q : 임의의 복합명제 P가 참일 때,  항상 Q가 참이면 이와 같이 표현한다. 이 때, P는 Q보다 강하다 라고 한다. (조건문인 경우 하위 복합명제 P가 거짓이면 그 상위 복합명제는 항상 참이다. 따라서 P가 참일 때 Q가 항상 참인지 고려하면 된다. 이 경우 P의 조건이 Q보다 강하다 라고 한다.)

P⇔Q : 임의의 복합명제 P와 Q가 그들의 변수들이 임의의 진리값을 가질 때 항상 같은 진리값일 경우 동치라고 한다. 또는 다음과 같이 표현할 수 있다. P≡Q 동치를 "논리적으로 같다"라고 표현하기도 한다.

converse : 조건문 p→q의 converse는 q→p이다.

contrapositive : 조건문 p→q의 contrapositive는 ~q→~p이다.

inverse: 조건문 p→q의 inverse는 ~p→~q이다.

기본적인 명제연산자는 아래와 같다.

p∧q "p and q"                 conjunction (logical product, 논리곱)  

p∨q "p or q"                   disjunction (logical sum, 논리합) 

p→q "if p, then q", "q if p" conditional (조건문) 

p↔q"p if and only if q"     biconditional (쌍방 조건문) 

----- 만약 필요시 사용할 때 타인에게 반드시 설명이 필요함 ----

p⊕q "p xor q"                 exclusive or (배타적 논리합) 

p↓q "p nor q"                 not or (부정 논리곱)    //이는 p or q 진리값의 부정

p | q 또는 p↑q "p nand q" not and (부정 논리합)  //이는 p and q 진리값의 부정

p	q	p ∧ q	p∨q	p→q	p↔q	p⊕q	p↓q	p↑q
T	T	T	T	T	T	F	F	F
T	F	F	T	F	F	T	F	T
F	T	F	T	T	F	T	F	T
F	F	F	F	T	T	F	T	T

조건문 p → q 에서 p는 전제premise, q는 결론conclusion 이라고 합니다. p → q는 "p는 q를 의미한다" 라고 표현하기도 합니다.

Facts 사실들

1 조건 연산자 p → q는 다음과 같이 표현 가능합니다 :

   "p 이면 q이다."    "p는 q를 의미한다"    "p는 q의 충분조건이다."    "q는 p의 필요조건이다."

   "if p, then q"    "q if p"    "p implies q"    "p is a sufficient condition for q"    "q is a necessary condition for q"

2 쌍방 조건문 p↔q는 다음과 같이 표현 가능합니다 :

   "p 이면 q이고, q이면 p이다."    "p는 q의 필요충분조건이다."     "q는 p의 필요충분조건이다."

   "p와 q는 동치이다"(단, 이 경우는 p↔q가 항진tautology 여야합니다.)

   "p if and only if q"    "p is a necessary and sufficient condition for q"    

   "p and q are equivalent"(only p↔q is tautology) 

3 컴퓨터 프로그래밍과 회로 디자인에서, 다음과 같은 논리 연산자가 사용됩니다. 

   "p AND q p∧q" "p OR q p∨q" "NOT p ¬p" "p XOR q p⊕q" "p NOR q p↓q" "p NAND q p|q"

4 연산자의 우선순위 : 5개의 연산자들 ¬, ∧, ∨, →, ↔ 은 앞서 나열된 순으로 우선순위를 가집니다. 따라서 때에 따라 괄호를 생략가능합니다. 다음과 비슷하게 괄호가 생략 가능합니다. 2+(3x6)는 2+3x6

5 n개의 변수와 논리 연결자를 이용하여 2^(2^n) 개의 가능한 진리값 경우가 가능합니다. n개의 변수로 진리표는 2^n 개의 행이 생성되며, 각 값이 참이거나 부정이거나 경우의 수이므로 2^(2^n) 개 입니다.

6 p⇔q는 p⇒q이고 q⇒p일 때 참이다.

7 p⇔q는 p↔q가 항진tautology일 때 참이다.

8 논리적 동치를 증명하는 방법은 여러가지다. 1 진리표 2 이미 알고 있는 복합명제를 이용 3 논리적 쌍대를 이용(다른 챕터에서 다룰 예정)

9 논리적 동치는 논리 회로를 단순화하는데 사용된다.

Examples

1 "1 + 1 = 3"과 "대한민국 제 18대 대통령은 최순실이다." 라는 명제는 거짓입니다.

2 "1 + 1 = 2"과 "대한민국의 수도는 서울이다." 라는 명제는 참입니다.

3 "x>5"는 명제가 아닙니다. 왜냐하면 진리값은 x의 변수에 값이 결정되기 전에 알 수 없습니다.

4 "이 명제는 거짓이다." 는 명제가 아닙니다. 왜냐하면 진리값을 지정할 때마다 모순이 발생합니다.

5 복합명제는 왼항부터 우선순위로 연산됩니다. 아래는 그 예입니다. 우측에는 우선순위에 따라 모두 괄호 처리한 것입니다.

p∨q∧r             ((p∨q)∧r)

p↔q→r            (p↔(q→r)) 

¬q∨¬r→s∧t     (((¬q)∨(¬r))→(s∧t))

6 p∨¬p는 항진이다.

7 p∧¬p는 자기-모순self-contradiction이다.

8 p↔q가 (p∧q)∨(¬p∧¬q)와 동치임은 진리표를 사용하여 증명할 수 있습니다.

p	q	p↔q	¬p	¬q	p∧q	¬p∧¬q	(p∧q)∨(¬p∧¬q)
T	T	T	F	F	T	F	T
T	F	F	F	T	F	F	F
F	T	F	T	F	F	F	F
F	F	T	T	T	F	T	T

3번째 열과 8번째 열의 진리값이 동일 하므로, 두 복합 명제는 동치입니다.

9 p↔q가 (p∧q)∨(¬p∧¬q)와 동치임은 논리적 동치들을 제시하여 증명할 수 있습니다.

p↔q  ≡ (p→q)∧(q→p)                            //쌍방 조건문이 조건문으로 대체됨

  ≡ (¬p∨q)∧(¬q∨p)                          //조건문이 or로 대체됨

  ≡ [(¬p∨q)∧¬q]∨[(¬p∨q)∧p]             //(¬p∨q)를 유지하며 분배법칙

  ≡ [(¬p∧¬q)∨(q∧¬q)]∨[(¬p∧p)∨(q∧p)] //(¬p∨q)를 분해하며 분배법칙

  ≡ [(¬p∧¬q)∨F]∨[F∨(q∧p)]                 //모순명제 contradiction * ¬p∧p≡F

  ≡ (¬p∧¬q)∨(q∧p)                           //identity law * F∨p≡p

  ≡ (¬p∧¬q)∨(p∧q)                           //교환법칙 commutative law

  ≡ (p∧q)∨(¬p∧¬q)                            //교환법칙 commutative law

이제 까지는 앞서 배웠던 명제, 논리 연산자, 동치에 대해서 빠르게 정리해보았습니다.

다음 포스팅에서는 관련 문제들과 응용 문제들을 포스팅 하겠습니다 그럼 다음에 봐요 빠잉~