1 기초: 논리와 증명

//이 자료는 Discrete mathmatics and its application 7th edition에서 나오는 예제를 간추린 것입니다. 저는 코딩에 관심 있는 학생이며, 타인의 지적재산을 단지 학습을 위해 사용할 뿐 개인의 금리적 이윤을 위한 상업적인 용도로 쓰지 않습니다. 만약 저작권 관련 문제가 될 시 즉시 문서를 삭제하겠습니다.//

1.1 명제 Proposition

예제 2. 아래의 문장들에 대해 생각해보세요

1. 지금이 몇 시 인가요?

2. 주의 깊게 읽어보시오

3. x+1 = 2

4. x+y = z

정답

문장 1과 2는 참 거짓을 가릴 수 없으므로 명제가 아닙니다. 문장 3과 4는 참 거짓 모두 아니기 때문에 명제가 아닙니다. 이런 경우 변수에 값을 할당하면 명제가 될 수 있습니다. 

명제변수 proposition variable 명제논리 propositional calculus (propositional logic)

복합명제 compound propositions

수학에서 변수를 쓰는 것 처럼 명제를 표현하기위해 명제변수라는 것을 사용합니다. 명제변수로 자주 쓰이는 문자들은 p, q, r, s... 등입니다. 명제변수의 값이 참일 때는 true의 T를 거짓일 때는 false의 F를 통해 표현합니다. 

명제를 다루는 논리영역을 명제논리라고 합니다. 이미 2300년보다 전, 그리스인 철학자 아리스토 텔레스에 의해 시스템적으로 개발되었습니다. 지금부터는 기존에 가지고 있는 명제들을 이용하여 새로운 명제들을 만들어 내는 방법에 대해 배울 것입니다. 이 방법은 영국 수학자 George Boole의 저서 The Laws of Thought에서 논의되었습니다. 많은 수학 명제들은 하나 이상의 명제들로 구성되어있습니다. 논리 연산자와 기존의 명제들을 이용하여 생성된 새로운 명제들을 복합명제라고 부릅니다.

 예제 4. 아래 명제의 부정형을 답하시오.

"나의 스마트폰은 최소 32GB의 메모리를 가지고 있다."

정답

"나의 스마트폰은 32GB 메모리보다 적다."

정의 2

p와 q를 명제라고 하자. p와 q의 논리곱은 "p 와 q"이며 p^q로 표현한다. p와 q가 모두 참일 때 p^q는 참이 되고 그 외에는 거짓이다.

정의 3

p와 q를 명제라고 하자. p와 q의 논리합은 "p 또는 q"이며 p v q로 표현한다. p와 q가 모두 거짓일 때 p v q는 거짓이 되고 그 외에는 참이다.

접속사 "또는"(영어로 or)은 논리곱에서 두 가지의 의미가 있는데 그 중 하나는 포괄적 또는(inclusive or)입니다. 논리곱은 두 명제중 하나만 참이여도 참입니다. 예를 들어, 포괄적 또는은 아래의 문장처럼 사용가능합니다.

"대학수학 또는 컴퓨터 과학을 수강하였던 학생들이 이 수업을 신청할 수 있습니다."

 반면에 배타적 또는(exclusive or)는 아래와 같이 사용할 수 있습니다.

"대학수학 또는 컴퓨터 과학을 수강하였던 학생들이 이 수업을 신청할 수 있습니다. 단, 두 강의 모두 수강한 학생은 신청할 수 있습니다." 

여기서는, 대학수학과 컴퓨터과학을 모두 수강한 학생들은 본 강의를 수강할 수 없다고 뜻합니다. 정확하게 두 강의 중 단 하나의 강의만을 수강한 학생들이 본 수업을 수강할 수 있습니다. 비슷하게는, 음식점의 메뉴판에 적혀있는 문장을 볼 때 "수프 또는 샐러드가 앙트레로 제공됩니다." 가 있습니다. 손님은 주 코스요리 사이에 나오는 앙트레를 수프 또는 샐러드로 선택할 수 있지만, 두 개 다는 선택할 수 없습니다. 이런 뜻이기에, 배타적인 또는입니다.

정의 5

p와 q를 명제라고 하자. 조건문 p -> q 는 "만약 p이면 q이다" 라는 명제다. 조건문 p->q는 p가 참이고 q가 거짓일 때 거짓이고 그 외에는 모두 참이다. 조건문 p -> q 에서, p는 가설(또는 전제) q는 결론(또는 결과)이라고 부른다.

선언문 p ->q는 p의 조건에 의해 q가 참임을 주장하기 때문에 조건문이라고 부릅니다. 조건문은 함의(implication)이라고도 불립니다. p -> q 조건문은 p와 q 모두 참일 때와 p가 거짓일 때 참입니다. 

예로, 선거를 위해 많은 정치인들이 출마를 위해 내놓는 공약입니다.

"저가 당선이 되면, 저는 세금을 낮추겠습니다."

만약 정치인이 당선되면, 투표자들은 당선인이 세금을 낮추길 기대합니다. 그리고, 정치인이 낙선한다면, 투표자들은 정치인이 사실 세금을 낮출만한 충분한 능력이 있더라도 그가 세금을 낮출 것이라고는 기대하지 않을 겁니다. 정치인이 당선되었으나 세금을 낮추지 않았을 때 투표자들은 정치인이 공약을 파기했다고 말할 것입니다. 이 경우가 p -> q 에서 p가 참이지만 q가 거짓일 때에 대응합니다.

예제 7

p를 "마리아는 이산수학을 배운다."와 q를 "마리아는 좋은 직장을 구할 것이다." 라고 하자. p -> q를 표현해봅시다.

정답

"마리아가 이산수학을 배운다면, 마리아는 좋은 직장을 구할겁니다."

"마리아가 좋은 직장을 구하기 위해서는, 마리아는 이산수학을 배우는 것만으로도 충분합니다."

"마리아가 이산수학을 배우지 않는 경우가 아니라면 마리아는 좋은 직장을 구할겁니다."

예제 8

아래의 선언을 통해 x의 값은 무엇입니까? 이 선언 전에 x의 값은 0이라고 가정합니다. ( := 는 할당을 뜻하는 기호입니다.)

if 2+2 = 4 then x := x+1

정답

2+2 = 4가 참이므로, 할당문은 수행됩니다. 그러므로 x의 값은 0에서 1 증가한 1이 됩니다.

CONVERSE, CONTRAPOSITIVE, AND INVERSE

p->q 조건문을 이용하여 새로운 조건문을 생성할 수 있습니다. q -> p는 p ->q의 converse라고 합니다. ~q -> ~p 는 p->q의 contrapositive라고 합니다. ~p->~q는 p->q의 inverse입니다. 

p->q의 contrapositive인 ~q->~p는 항상 같은 진리값을 가집니다. 확인을 위해서, ~p가 거짓이고 ~q가 참일 때 contrapositive는 거짓입니다. 즉, p가 참이고 q가 거짓일 때입니다. 이제 converse인 q->p와 inverse인 ~p->~q 모두 p->q의 진리값과 다르다는 것을 볼 것입니다. p가 참이고 q가 거짓일 때, 기존 조건문은 거짓이지만 converse문과 inverse문은 둘 다 참입니다.

두 복합명제가 항상 같은 진리값을 가질 때, 조건문과 조건문의 contrapositive관계처럼, 그 둘을 같다라고 표현합니다.

예제 9

다음 문장의 contrapositive, converse, inverse를 표현해봅시다.

"비가올 때는 언제나 홈 팀이 이깁니다." (The home team wins whenever it is raining?)

정답

"비가오면, 홈팀이 이깁니다."(If it is raining, then the home team wins)로 간단히 할 수 있습니다. 결과적으로 contrapositive는 다음과 같습니다. "홈팀이 졌다면, 비가 오지 않는 것입니다." converse는 "홈팀이 이겼다면, 비가 오는 것입니다." 입니다. inverse는 "비가 오지 않으면, 홈팀은 졌습니다." 입니다.

상호조건

정의 6

p와 q를 명제라고 하자. 상호조건문 p<->q는 "q인 경우 p이고 p인 경우에 p이다"를 뜻하는 명제입니다. 상호조건문 p<->q는 p와 q가 같은 진리값을 가지고 있을 때 참이며 그 외에는 거짓입니다. 

아래는 p<->q의 진리표입니다. p<->q는 p->q와 q->p가 모두 참인 경우에 참이며 반대의 경우 거짓입니다. 그래서 "if and only if" 를 쓰는 것과 ->, <-의 기호가 동시에 쓰입니다. 

 * q if p : p인 경우 q이다. * p only if q : p인 경우에 q이다. 그러므로 if and only if 입니다.

예제 10

p를 "당신은 비행기를 탈 수 있다", q를 "당신은 표를 구매한다"라고 하자. 그런경우 p<->q 문은 "당신이 표를 구매했을 때 비행기를 탈 수 있다 또는 비행기를 탈 수 있는 경우에 표를 구매한다 이다.

p와 q 모두 참이거나 거짓일 때 명제는 참입니다. 즉, 당신이 표를 구매한다면 비행기를 탈 수 있다 또는 티켓을 사지 않으면 비행기를 탈 수 없다 입니다. 반대로 복합명제는 p와 q가 반대의 진리값을 가질 때 거짓입니다. 즉, 티켓을 사지 않지만 당신은 비행기를 탈 수 있습니다 와 티켓을 샀지만 비행기를 탈 수 없습니다 인 경우입니다.

암묵적인 상호조건문의 사용

자연언어를 사용할 때 상호조건문은 뚜렷하게 표현되는 점이 아니라는 것을 알고 있어야합니다. 특히, "if and only if"는 자연언어에서 거의 사용되지 않습니다. 대신에 상호조건문은 "if, then" 또는 "only if" 구조로 자주 표현됩니다. "if and only if"는 암묵적입니다. 즉, converse는 함축되며 진술되지 않습니다. 예로, 다음 문장을 봅시다. "식사를 끝내면, 디저트를 먹을 수 있어" 진짜 말하는 바는 "너는 디저트 먹을 수 있어 if and only if 너가 식사를 마치면" 입니다. 앞의 명제는 논리적으로 다음의 두 명제와 같습니다. "너가 식사를 끝낸경우, 디저트를 먹을 수 있어" 그리고 "디저트를 먹을 수 있는 경우에 너는 식사를 끝낸다" 자연언어에서 이런 부정확함 때문에, 자연언어에서 조건문은 해당 조건문의 converse도 같이 포함하느냐 아닌가 가정해야합니다.

복합명제의 진리표

다음 복합 명제의 진리표를 그려라. (p v~q) -> (p ^ q)

정답

진리표는 두 명제 변수 p 와 q를 포함하고 있으므로, 진리표의 행은 4개가 됩니다. 진리값의 쌍은 TT, TF, FT 그리고 FF 입니다. 첫 두 열은 p 와 q를 표현했습니다. 세번째 열에서는 (p v ~q)에서 사용되는 ~q를 표현했습니다. 네번째 열에서는 p v ~q를 표현했습니다. 다섯번째 열에서는 p ^ q를 표현했습니다. 마지막 컬럼에서는 전체 복합명제의 진리값을 표현했습니다. 아래는 표입니다.

EXERCISE

퍼지논리는 인공지능에서 사용됩니다. 퍼지논리에서, 명제는 0과 1을 포함한 그 사이의 수가 진리값을 가집니다. 진리값 0을 가진 명제는 거짓이고 1을 가진 명제는 참입니다. 0과 1사이의 값은 다양한 수준의 진리값을 가집니다. 예로, 진리값 0.8은 다음 명제에 적용될 수 있습니다. "철수는 행복합니다." 프레드는 대부분 시간에 행복하기 때문입니다. 그리고 0.4의 진리값이 다음 명제에 적용될 수 있습니다. "존은 행복합니다." 존은 평소에 덜 행복하니까요. 45, 47 문제를 퍼지 논리 진리값을 이용해 풀어봅시다. 

문제 45

퍼지논리에서 명제의 부정 진리값은 명제의 진리값에서 1을 뺀 것 입니다. "프레드는 행복하지 않습니다" 와 "존은 행복하지 않습니다" 의 진리값은 무엇인가요? 

정답: "프레드는 행복하지 않습니다" 0.2, "존은 행복하지 않습니다" 0.6

문제 47

퍼지논리에서 두 명제 논리합의 진리값은 두 명제의 진리값 중에 최대값을 가집니다. "프레드는 행복하거나 존은 행복합니다" 와 "프레드는 행복하지 않거나 존은 행복하지 않습니다" 두 복합 명제의 진리값은 무엇인가요?

정답: "프레드는 행복하거나 존은 행복합니다." 0.8, "프레드는 행복하지 않거나 존은 행복하지 않습니다." 0.6

문제 49

100개의 명제 리스트 안에 n번 째 명제는 다음과 같습니다. "정확하게 리스트의 명제들 중 n개가 거짓이다"

a) 이 명제들로부터 도출해낼 수 있는 결론은 무엇입니까?

b) n번째 명제가 "리스트의 명제들 중 적어도 n개가 거짓이다." 인 경우에 a)를 답해보시오.

c) 리스트가 99개의 명제를 가지고 있을 경우 b)를 답해보시오.

정답: a) 99번째 명제가 참이며, 나머지는 거짓입니다. b)1부터 50개의 명제가 참이며 51부터 100번째가 거짓입니다. c)이 것은 패러독스이며 발생할 수 없습니다.

명제1: 1개의 명제가 거짓이다.

명제2: 2개의 명제가 거짓이다.

명제3: 3개의 명제가 거짓이다. ....생략....

명제99: 99개의 명제가 거짓이다.

명제100: 100개의 명제가 거짓이다.

그렇다면 (a) 명제 99만이 참이 될 수 있습니다. 명제 100이 참이 될 수는 없습니다. 패러독스입니다.