Foundation: propositional logic

논리학logic은 주어져있는 사실들로부터 사실인 것을 추론해내는 기초적인 활동입니다. 우리는 이제, 수학적 진술mathematical statement에 관한 명제proposition들을 살펴볼 것 입니다. "모든 정수 n에 대해, n을 넘지 않는 모든 정수의 합은 n(n+1)/2이다." 논리학은 모든 수학적 추론mathematical reasoning과 자동화 추론automated reasoning의 기초입니다. 논리학은 computing machines, specification of systems, artificial intelligence, computer programming, programming languages, 그 외 여러 computer science 분야에 응용되고 있습니다.

 자, 수학을 이해하기 위해서는 어떻게 반드시 정확한 수학적 논증을 만드는 지 이해해야합니다. 그게 바로 증명proof 입니다. 만약 우리가 수학적 진술이 참임을 증명한다면, 우리는 그것을 정리theorem라고 부릅니다. 한 주제에 대한 정리theorem들을 모은다면 우리는 그 주제에 대해 무엇을 알고있는지 정리organize할 수 있습니다. 필기노트 처럼요. 수학적인 주제들에 대해 배우려고 한다면, 해당 주제에 대한 수리적 논증을 활발하게 세워나가야합니다. 단순히 설명을 읽는것 만해서는 안됩니다. 그리고 정리theorem의 증명을 안다는 것은 새로운 상황에 적용하기 위해 결과를 수정하여 사용할 수 있기도 합니다. 

 수학 전반적으로 증명이 매우 중요하다는 것은 이제 대충 가늠하셨을 겁니다. 개인적으로 기독교는 별로 안 좋아하지만, 성경에는 단단한 반석 위에 옳은 증명들만 올려놓으면 우리는 항상 강한, 옳은, 밝은 진리에 가까워 질것이라는 표현이 나옵니다. 이는 공리 위의 정리 또한 그런 느낌입니다. 제가 성경을 잘 몰라서 이렇게 느꼈을 수도 있습니다. 하하; 물론 괴델의 불완전성 정리에 의해 그런 기대감은 무너졌지만요. 어려운 이야기는 그만합시다. 서론이 길었습니다. 이제 꽤 무식하게 해결하러 가봅시다.

명제Propositions

명제는 선언적인 문장입니다. 즉, 사실을 말하려고 하는 문장입니다. 그러므로 참 또는 거짓일 수 있습니다. 이 때 참, 거짓 두 성질을 동시에 가지지는 않습니다.

예제1 다음의 문장들을 확인합시다.

1. Seoul는 대한민국의 수도이다.                2. Toronto는 캐나다의 수도이다.

3. 1+1 =2                                             4. 2+2 =3

명제 1,3 은 참이고, 명제 2, 4는 거짓입니다.

예제2 다음의 문장들을 살펴봅시다.

1. 현재 몇 시입니까?                               2. 주의깊게 읽어보세요.

3. x+1 = 2                                            4. x+y = z

문장 1, 2는 명제가 아닙니다. 왜냐하면 참, 거짓을 판단하려는 문장이 아니기 때문입니다. 문장 3, 4는 명제가 아닙니다. 왜냐하면 참, 거짓 둘다 아니기 때문입니다. 문장 3, 4는 변수variable에 어떠한 값이 결정된다면 명제로 볼 수 있을 겁니다. 이에 관해서는 곧 다룰 예정입니다.

명제 변수propositional variable란 명제를 변수로 나타낸 것입니다. 위에서 보았던 산수를 위한 변수와 유사한 형식입니다. 대개 명제 변수는 p, q, r, s 등으로 사용됩니다.

notice: 수에관한 변수numerical variable는 보통 x, y, z로 표현됩니다. 함수 변수는 f, g, φ, χ, θ 등이 사용됩니다. 

명제 변수의 진리 값truth value는 명제가 참일 때 T, 거짓일 때 F를 가집니다. 이제 우리는 명제들을 다루는 논리학에 대해서 배울 것입니다. 이를 명제 연산propositional calculus 또는 명제 논리(논증)propositional logic라고 부릅니다. 

정의1

p를 명제라고하자. 그렇다면 p의 부정은 ¬p라고 표기되며, "p가 아닌 경우에" 라고 읽는다. 영어로는 "not p"라고 읽는다. p의 부정의 진리값은, 항상 p의 진리값의 반대이다.

notice: 이때 p는 반드시 명제라고 전제해야합니다. 

예제3 다음 명제의 부정형을 써보세요. 예슬의 휴대전화기는 아이폰이다. 

*** 예슬의 휴대전화기는 아이폰이 아니다.

notice: 만약 명제 p의 진리값이 T인 경우, 그 부정형 ¬p의 진리값은 F입니다. 만약 명제 p의 진리값이 F인 경우, 그 부정형 ¬p의 진리값은 T입니다. 명제 변수p는 그 외의 값을 가지지 않습니다. 모든 명제는 참 아니면 거짓입니다.(물론 ㅎㅎ, fuzzy logic이 나오기전에는요~)

정의2

p와 q를 명제라고 하자. p와 q의 논리곱은 p∧q로 표현하며, "p 그리고 q"를 뜻하는 명제이다. p∧q는 p와 q가 동시에 참일 때만 참입니다. 그 외에는 거짓입니다.

notice: p∧q의 진리값은 p와 q 진리값 네가지 조합으로 값이 결정됩니다. 다음과 같습니다. TT, TF, FT, FF 입니다. TT인 경우에만 p∧q는 T가 됩니다. 논리곱은, T를 1 F를 0이라 하였을 때 TT, 즉 1*1=1을 만족하므로 논리곱이라고 합니다. 영어로는 논리곱을 conjunction이라고 표현합니다.

예제4 명제 p와 q의 논리곱을 찾으세요. 여기서 명제 p는 예슬이는 와인을 좋아한다. 명제 q는 예슬이는 소주를 싫어한다.

*** 명제 p와 q의 논리곱 p∧q는 다음과 같은 명제가 됩니다. "예슬이는 와인을 좋아하지만, 소주는 싫어한다." 그 외에도 다른 여러 방법으로 표현할 수 있습니다. "예슬이는 와인을 좋아한다. 그리고 소주를 싫어한다." 뜻만 같으면 됩니다.

notice: 앞으로 p∧q, p∨q, p→q와 같이 가장 작은 명제들을 논리연산자로 결합한 형태의 명제들을 자주 보게 될 것입니다. 이들을 복합 명제compound proposition이라고 부릅니다. 19세기 조지 불George Boole이 그의 저서 도입했습니다. 교양이니 기억해두세요. 기저에는 어려운 개념이 존재할지라도, 계산하는 방법은 굉장히 단순하며 자명합니다. 계속 살펴봅시다

정의3

p와 q를 명제라고 하자. p와 q의 논리합은 p∨q로 표현하며, "p 또는 q"를 뜻하는 명제이다. p∨q는 p와 q가 모두 거짓일 때 거짓입니다. 그외에는 항상 참입니다.

notice: p∨q의 진리값은 p와 q 진리값 네가지 조합으로 값이 결정됩니다. 다음과 같습니다. TT, TF, FT, FF 입니다. FF인 경우에만 p∨q는 F가 됩니다. 논리합은, T를 1 F를 0이라 하였을때 TT, 즉 1+1=2 (0이 아니므로 T) 이므로 논리합이라고 합니다. 영어로는 논리합을 disjucntion이라고 표현합니다. 제가 여러분에게 바라는 점은 논리곱, 논리합을 배우는 동시에 conjunction, disjunction으로 외우길 바랍니다.

예제5 명제 p와 q의 논리합을 찾으세요. 여기서 명제는 예제4와 같습니다.

*** 명제 p와 q의 논리합 p∨q는 다음과 같은 명제가 됩니다. "예슬이는 와인을 좋아하거나, 소주를 싫어한다." 그 외에도 다른 여러 방법으로 표현할 수 있습니다. "예슬이는 와인을 좋아한다. 또는 소주를 싫어한다." 뜻만 같으면 됩니다.

notice: 이제부터 복합 명제compound proposition의 진리값을 연산하기 위해 진리표truth table를 적극적으로 활용할 것입니다. 진리표는 가장 작은 명제atomic proposition의 진리값 경우를 고려하여 작성합니다. 아래는 논리곱, 논리합에 대한 진리표입니다.

p	q	p∧q	p∨q
T	T	T	T
T	F	F	T
F	T	F	T
F	F	F	F

정의4

p와 q를 명제라고 하자. p와 q의 배타적 논리합은 p⊕q로 표현하며, "p 또는 q"를 뜻하는 명제이다. p⊕q는 p와 q가 모두 참이거나 모두 거짓일 때 거짓입니다. p와 q가 서로 다른 진리값을 가질 때에만 참입니다.

notice: 배타적 논리합은 영어로 exclusive or, XOR이라고 표현됩니다. 진리값은 p와 q 진리값 네가지 조합으로 값이 결정됩니다. 다음과 같습니다. TT, TF, FT, FF 입니다. TF, FT인 경우에 p⊕q는 T가 됩니다. 논리합과 배타적 논리합의 사용 상황에 대해서 예를 들어 설명합시다. 일상생활에서 살펴봅시다. 어떤 사람이 음식점에 가서 음식을 주문한 뒤 디저트로 무엇을 고를 것인지 웨이터가 설명해줍니다. "디저트로는 플레인 요거트 또는 마카롱이 가능합니다."  "오, 그렇다면 두 개 다 부탁드려요." "죄송합니다, 손님. 제가 말씀 드린 이유는 플레인 요거트 또는 마카롱 둘 중 하나만 가능합니다." "아, 저는 or로 이해했었는데 exclusive or이였군요!" 

정의5

p와 q를 명제라고 하자. 조건문conditional statement은 p→q로 표현하며, "p이면 q이다"를 뜻하는 명제이다. 조건문 p→q는 p가 참의 값이지만 q가 거짓일 때 거짓입니다. 그 외에는 모두 참입니다. 조건문 p→q에서, p를 가설hypothesis 또는 전제premise라고 하고 q를 결론conclusion 이라고합니다.

notice: 진술 p→q가 조건문이라고 불리는 이유는, p→q는 p의 조건에 의해 q의 값이 참임을 주장하기 때문입니다. 이런 조건문을 보고 함의implication이라고 합니다. 함의란 말이 한문이라 이해하기 어렵죠. 그래서 전 implication이라고 외웁니다. 아래의 진리표를 확인합시다. p→q는 p와 q가 모두 참일때, 또는 p가 거짓일 때 참입니다. 꼭 확인하고 넘어가세요.

p	q	p⊕q	p→q
T	T	F	T
T	F	T	F
F	T	T	T
F	F	F	T

notice: 조건문은 수학적 추론mathematical reasoning에서 아주 중요한 역할을 합니다. p→q를 자연 언어로 표현하는데 다양한 용어가 사용됩니다. 다음을 확인합시다:

"만약 p이면, q이다." "p는 q를 함의한다." "p이면, q이다." "p는 q에 대한 충분조건이다." "q는 p에 대한 필요조건이다." "p뒤에 q가 따라온다." "¬p가 아닌경우 q이다." "if p, then q" "q if p" "p only if q"

notice: 조건문conditional statement은 처음 배울때 꽤 헷갈리는 연산자입니다. 자, 다음 예를 확인합시다. 1) 한 정치인이 선거운동을 할 때 다음과 같이 말합니다. "만약 내가 당선된다면, 세금을 낮추겠습니다." 이 경우, 그 정치인이 당선된 경우 세금은 반드시 낮춰질 것입니다. 또, 만약 정치인이 당선되지 않는다면 사람들은 세금이 낮춰질 것을 기대하지 않습니다. 그가 당선된게 아니니까요. 오직 정치인이 당선되었으나 세금을 낮추지 않은 경우, 그 경우는 p가 참이지만 q가 거짓인 경우입니다. 2) "만약 기말시험에서 100점을 맞으면, A학점을 받을것이다." 만약 100점을 받는다면, A를 받을 것을 기대할 수 있습니다. 만약 100점을 받지 않더라도 다른 요인에 영향을 받아 A를 받을수도 있다고 기대할 수 있습니다. 그러나, 만약 100점을 받았지만 A를 받지 않았다면 정말 기분이 나쁠것입니다. 

예제6

p를 "재균이는 이산 수학을 공부한다.", q는 "재균이는 좋은 직장을 구할것이다." 라는 명제라고 하자. 명제 p→q를 표현해보시오.

*** "재균이는 이산 수학을 공부한다면, 좋은 직장을 구할것이다."

notice: 조건문이 일상 생활에서 사용되는 조건문과는 조금 다른 것을 느끼실겁니다. 예로, 다음을 살펴봅시다. 명제 "내가 여자라면, 2+3=6이다." 는 조건문의 정의에 따라 참입니다. 저는 여자도 아니고, 2+3=5이기 때문이지요. 일상생활에서는 앞과 같은 문장을 말하면 이상한 놈 취급을 받습니다. 가설hypothesis과 결론conclusion이 전혀 관계가 없기 때문입니다. 수학적 추론mathematical reasoning에서는, 조건문을 일상생활 언어에서 쓰는것 보단 조금 관대합니다. 이미 눈치채신 분들도 있겠지만, 조건문의 수학적 개념은 가설과 결론의 인과관계에서 독립적입니다. 명제는 자연언어에 기저를 둔 것이 아니라 체계가 잡혀진 인공적으로 만들어진 언어임을 기억합시다. 우리는 그저 사용하기 쉽고 기억하기 쉽기에 자연언어를 차용해서 쓰는것입니다.  ... -.ㅡ

"앞 뒤를 바꾼 CONVERSE, 앞 뒤 그리고 내용을 바꾼 CONTRAPOSITIVE, 내용을 뒤집은 INVERSE"

notice: 조건문 p→q로 부터 새로운 조건문을 만들 수 있습니다. 특히, 자주 사용되는 관련있는 조건문 세 개가 있습니다. q→p는 p→q의 converse 라고 불립니다. p→q의 contrapositive는 ¬q→¬p 입니다. p→q의 inverse는 ¬p→¬q입니다. 

먼저 contrapositive인 ¬q→¬p는 원 명제 p→q와 항상 같은 진리값을 가집니다. contrapositive 명제는 ¬p가 거짓이고 ¬q가 참일 때 거짓입니다. 즉, p가 참이고 q가 거짓일 때입니다. 이제 converse, inverse를 살펴봅시다. 이 둘은 모든 atomic proposition의 경우에 대해 p→q의 값과 항상 반대입니다.  p가 참이고 q가 거짓일 때 원 명제는 거짓입니다. 그러나 converse와 inverse는 이 때 참입니다. 

두 복합명제가 모든 atomic proposition 진리값 경우에 대해 항상 같은 진리값을 가질 때 우리는 그 둘을 동치equivalent라고 부릅니다. 그래서 조건문과 그 대우contrapositive는 동치입니다. 그리고 converse와 inverse는 서로 동치입니다. converse는 inverse의 contrapositive 이니까요, 반드시 확인하세요. 그러나 둘은 원 명제와 동치이지 않습니다. 

예제7 다음 명제의 converse, contrapositive, inverse를 기술하시오. "비가 내리면 항상 홈팀이 이긴다."

*** 원 명제의 contrapositive는 다음과 같습니다. "홈팀이 이기지 않았다면, 비가 오지 않는 것이다." converse는 다음과 같습니다. "홈팀이 이긴다면, 비가 오는 것이다." inverse, "비가 내리지 않는다면, 홈팀이 이기지 않는다." 원 명제와 그 contrapositive는 동치equivalent입니다.

자, 이제 거의 마지막에 왔습니다. 조금만 더 인내하고 살펴봅시다.

정의6

p와 q를 명제라고 하자. 양방향 조건문biconditional statement는 p↔q이며 "p이면 q이고, q이면 p이다."라고 표현한다. 양방향 조건문biconditional statement p↔q는 p와 q가 같은 진리값일 때만 참이고 다른 경우는 거짓입니다. biconditional statemnet는 bi-implications라고도 불립니다.

notice: p↔q가 참이기 위해서는 p→q와 q→p가 모두 참이어야 합니다. 그 외에는 거짓입니다. 따라서 다음과 같이 표현합니다. "p if and only if q" "p는 q의 필요충분 조건이다." "(p→q)∧(q→p)"

p	q	p↔q	p→q	q→p	(p→q)∧(q→p)
T	T	T	T	T	T
T	F	F	F	T	F
F	T	F	T	F	F
F	F	T	T	T	T

notice: 사실, 양방향 조건문은 가끔씩 자연언어에서 눈치 채기 힘들만큼 은밀하게 사용됩니다. 예로, "너가 숙제를 끝내지 않는다면, 컴퓨터 게임은 못 할줄 알아라." 라는 어머니의 말씀(자연언어가 있다)고 합시다. 꽤 무섭죠 -ㅡ.ㅡ ㅋㅋㅋ,, 자, 그렇다면 조건문의 정의에 따라 숙제를 끝내더라도, 컴퓨터 게임을 못 할까요? 아닙니다. 사실은 이는 양방향 조건문을 써야 적절합니다. 원 명제는 다음과 같이 표현할 수 있습니다. "너가 숙제를 끝내지 않는다면, 컴퓨터 게임은 못 한다. 그리고 컴퓨터 게임을 못한다는 것은 너가 숙제를 끝내지 않았다는 거야."

복합 명제의 진리표 사용

이제까지 중요한 논리 연산자 다섯 개를 알아보았습니다. 논리곱conjunction, 논리합disjunction, 조건문conditional, 양방향 조건문biconditional statements 그리고 부정형negation이었습니다. 이제 이들을 이용하여 나온 명제, 복합명제의 진리값을 연산하는데 유용한 진리표truth table을 소개해드리려고합니다. 아래를 확인합시다.

예제8 다음 명제의 진리표를 만들어봅시다. (p∨¬q)→(p∧q)

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

논리 연산자의 우선순위

연산자	우선순위
¬	1
∧	2
∨	3
→	4
↔	5

notice: 복합 명제를 만들어나갈 때 우선순위를 알면 괄호를 줄일 수 있습니다. 예로,  (p∨q)∧(¬r)는 다음의 (p∨q)∧¬r와 같은의미입니다. 또, ¬p∧q는 (¬p)∧q와 같은의미입니다. ¬(p∧q)와는 다릅니다. p∧q∨r는 헷갈릴 여지가 있으므로 괄호를 사용하는 것을 원칙으로 합니다.

논리학과 비트 연산자

컴퓨터는 정보를 비트를 이용하여 표현합니다. 비트는 가능한 두개의 값 0 또는 1을 가지는 기호입니다. bit의 어원은 이진수binary digit로 부터 왔습니다. 컴퓨터 비트 연산자는 논리 연산자와 일치합니다. OR, AND, XOR은 각각 ∨, ∧, ⊕ 입니다. 또한 진리값 T, F는 비트값 1, 0과 일치합니다.

다음 포스팅은 일상생활에서의 logic의 사용에 대한 간단한 내용과 명제 동치에 대한 내용이 있겠습니다.