Math Logic Examples

DoMath
Parha (토론 | 기여)님의 2007년 4월 18일 (수) 13:47 판
(차이) ← 이전 판 | 최신판 (차이) | 다음 판 → (차이)
수리논리의 세계 로 돌아가기


현실에서 직접 응용


현실 세계에서 결론 도출

현실적으로 발생할 수 있는 상황을 논리 계산의 도움을 받아 해결하는 예를 마련해본다.[1]

선생님의 다음 말은 ?

졸업식날 민국이 아버지는 기분이 나빴다. 민국이는 공부도 가장 잘하고 축구도 아주 잘한다. 그런데 '우수학생상'을 받지 못한 것이다. 그걸 수도 있겠다 싶었지만 한편으로는 서운한 마음을 이기지 못했다. 그러다가 선생님과 단둘이 있게 되자, 슬쩍 말을 건넸다. - 우리 민국이가 우수학생상을 못받았데요. 공부도 1 등이고 축구도 잘해서 지난 가을 학교 대항전에서도 학교를 위해 공헌했는데 말이죠. 선생님 왈. " - 아, 그랬나요 ? 저희 학교에서주는 '우수 학생상'은 공부 잘하는 것은 물론이고, 다른 학생을 잘 돕고, 학예회에도 열심히 참여하는 학생 중에서 뽑아요. 그 중에서도 말썽을 덜 부렸거나 운동을 잘해서 건강하거나 하면 더 낫죠. 그런데, 민국이는요 ... " . 선생님은 무슨 말을 이어서 했을까?

기호로 바꾸어보자. 우수학생을 P 라 하자. 그리고 '공부를 잘한다 (A) , 다른 학생을 잘 돕는다 (B), 학예회에 열심히 참여한다 (C) , 말썽을 자주 부리다. (D) 운동을 잘한다 (E)' 로 놓자. 그렇다면 선생님의 요지는 다음과 같이 바꿀 수 있다. P 는 와 같다. 민국이는 받지 못했기 때문에, 라는 말이므로 . 고전논리의 법칙에 따라 민국이의 성향을 아래와 같이 바꿔 쓸 수 있다.
그런데 민국이는 A 이고 E 인 학생이라는 것은 알려진 사실이다. 이것을 적용하면,
이고 결국
다. 민국이는 다른 학생을 잘 돕지 않았거나, 학예회 활동을 열심히 않은 것이다. (민국이는 말썽을 많이 피운 학생이었을까? )

누가 거짓말을 하고 있느냐?

도난 사건이 있었다. 이 사건을 해결해야하는 M 씨는 그 집안에 사는 K, J, D 이 바로 도둑질을 했을 것이라고 믿었다. "분명히 이 중 범인이 있을 거야"다. 그리고 범인은 거짓말을 할 것이라고 확신했다. 용의자들을 불러 놓고 다른 것은 묻지 않고, "당신들은 거짓말 해서는 안됩니다. 알겠어요?" 라고 물었다. 물론 그들은 고개를 끄덕였다. 세 명에게 사건이나 알리바이에 대해 이것저것 묻고 났다. 다 묻기도 전에 K 는 M 에게 귓속말을 했다. " J 가 하는 말은 다 거짓말예요." M 은 J 에게 다른 사람 몰래 물어보았다. "누가 거짓말하는 것 같아요?" 그러자 J 는 " D 가 거짓말을 하는게 틀림없어요.", 이번엔 D 에게 물었다. 그러자 D 는 " K 도 J 도 모두 거짓말하는 게 틀림없어요." 이 말은 듣고 곰곰히 생각하던 M 은 무릎을 탁치며 " 바로 당신이 범인이군!" 이라고 지적했다. 거짓말 한 사람이 도둑질을 했다고 가정한다면 누가 범인일까?

문제의 상황을 군더더기 없이 파악하기 위해 기호로 바꾸어보자. K , J, D 가 참말이면 K , J, D 로, 거짓말이면 그 앞에 를 쓰자.
K 가 참말이고 J 는 거짓말이거나, K 가 거짓말이라면 J 가 거짓말 했다는 것이 잘못이므로 J 는 참말이다 :
J 가 참말이고 D 는 거짓말이거나, J 가 거짓말이라면 D 가 거짓말 했다는 것이 잘못이므로 D는 참말이다 :
D 가 참말이고 K 도 J 도 거짓말이거나, D 가 거짓말이고 K 나 J 중 한 명은 참말이다 :
위의 세 명제식과 논리적으로 등가인 것은, 다시 말해 위의 세 경우가 모두 참이면 아래도 참이고 아래가 참이면 위 세문장 모두 참이다. 따라서 '기계적으로' 논리 계산을 해보면 M 의 마음 속에 누가 있는지 금방 드러난다. (직접 해보라.)
결론적으로 J 만 참말을 한 것이다.

무슨 질문을 해야 살아날까?

탐험을 좋아하는 수학자가 밀림 속을 혼자 탐험하다가 낯선 사람들에게 붙들렸다. 어둠 밖에 없는 동굴 속에서 하루가 지났다. 다음 날 아침 머리기름을 반짝반짝 가지런히 바르고 깨끗하게 차려 입은 왠 사내가 다가왔다. 그는 이렇게 말을 건넸다.

" 당신은 지금 풀려날 것이오. 두 갈래 길까지는 우리의 병사가 함께 할 것이오. 두갈래 길에 이르면 당신은 혼자 갈 수 있습니다. 하지만, 한 쪽은 살아나가는 길이고, 다른 쪽 길로가면 당신은 틀림없이 잔혹하게 죽게 됩니다. 알겠소? 당신이 선택하는 것에 따라 사느냐, 죽느냐가 갈리는 거지. 난 이런 게임을 좋아한다오. 내 당신이 수학자라니 특별히 은전을 베풀기로 했소. 우리 병사는 어느 쪽이 사는 길이고 어느 쪽이 죽는 길인지 알고 있소. 당신은 그에게 단 하나의 질문을 던질 수 있습니다. 좋죠? 그가 만약 거기서 기분이 괜찮다면 참말을 할 것이고 기분이 별로면 거짓말을 할 것입니다. 그는 예, 아니오 한마디만 답할 것이오. 자, 이제 곧 밀림에서 가장 좋은 음식이 나올 것이고. 당신이 태어나서 한번도 먹어본 적 없는 맛있는 것이오. 점심 맛있게 먹고, 어쨌건 잘 가시오. " 갈림길에 서서 수학자는 이렇게 물었다. "?" 그리고 제 갈길을 갔고, 살아서 집으로 돌아왔다. 그 후로 그와 만나는 친구들이란 친구들은 모두 그 수학자만 만나면 얼굴에 홍조를 띠며 신이 나서 떠벌이는 이 이야기를 몇 번이고 들어야 했다. 과연 그는 어떤 질문을 했을까?
수학자는 다음과 같이 상황을 단순하게 만들었다. '왼쪽 길이 살길이다' 를 A 로, "당신(병사)은 지금 기분이 좋다" 를 B 로. 그리고 생각했다. 내가 살길은 B 이고 A 면 된다. 잠깐만, 내가 "당신은 기분이 좋고 왼쪽 길이 살길이냐?" 고 물으면 그가 "예" 라고 답했는데 만약에 그가 기분이 안좋다면 어떻게 되는거지? 억 ! 위험하다. 꼭 그것만 있나? 아니다. 다시 생각해보자. 그렇군, 네 경우가 있군.
그가 기분이 좋고 왼쪽 길이 살 길일 때 그가 "예" 할 경우
그가 기분이 좋고 왼쪽 길이 살 길이 아닐 때 그가 "예" 할 경우
그가 기분이 안좋고 왼쪽이 살 길일 때, 그가 "아니오" 라고 할 경우
그가 기분이 안좋고 왼쪽이 살 길이 아닐 때, 그가 " 아니오" 라고 할 경우,
첫번째, 네번째 경우를 유도하는 질문을 던져야 하는군. "당신은 지금 기분이 좋고 왼쪽 길은 살길이 아닌가?" 라고 물었는데 그가 예 한다면 ? 만약 그가 진짜로 기분이 좋았다면 그 말을 믿고 난 오른쪽 길로 가면 되지만, 만약 그가 기분이 나빴다면? 억 ! ... 이 질문도 충분하지 않네, 자 어떻게 하지? 자, 이럴때 그가, 다음과 같은 질문을 던진다면, " 왼쪽 길이 살 길이고 당신은 지금 기분이 좋거나, 왼쪽 길이 살 길이 아니고 당신은 기분이 좋지 않다. 제 말이 맞습니까?" 살아났을까? (그런데, 점심은 어떤 음식이 나왔을까?)

수학의 기초를 다지는 역할

수학에서 증명, 증명하는데, 도대체 증명이란 무엇일까?


실제로 대수학에서 공리로 받아들여지는 문장들이다. 여기서 p, q, r 은 모두 변수다. 따라서 어떤 값을 대입해도 참인 문장이다.

처음 두 공리는 덧셈의 교환과 결합에 대한 규칙이고, 다음 둘은 0 에 대한 규칙, 그리고 나머지들은 비교 관계인 '같음'에 대한 성격을 분명하게 드러내는 규칙들이다. 이 공리들과 대입 규칙, 모더스 포넌스를 써서 아래의 '정리'를 유도할 것이다.

(정리 1)

8 번 공리의 틀에 변수 p 에 x + z 를, q 에 y + z 를, r 에 (-z)를 대입해도 참이다. 그 결과

(정리 2)

라는 새로운 정리를 얻는다. (물론 위의 문장은 대입 규칙을 세 번 적용한 결과다.) 이제 공리 2 번(결합 법칙)에서 p 대신 x , q 대신 z , r 대신 (-z) 를 대입한다.

(정리 3)

이고 공리 3 번에 p 대신 z 를 대입하여

(정리 4)

이라는 문장을 유도한다. 다시 7 번 공리 부분에, p 대신 z + (-z) 를, q 대신 0 을 r 대신 x 를 대입하여

(정리 5)

를 유도한다. MP 를 적용하여

(정리 6)

라는 새로운 정리를 유도한다. 공리 6 에 p 대신 (z + (-z)) + x 를, q 대신 0 + x 를, r 대신 x 를 대입한다.

(정리 7)

명제논리의 규칙으로 받아들인 를 적용하여 P 대신 (z + (-z)) + x = 0 + x 를, Q 대신 0 + x = x 를 대입하면

(정리 8)

를 얻는다. 앞에서 얻은 정리 중 (z + (-z)) + x = 0 + x 는 이미 있고, 공리 4 에서 p 대신 x 를 대입하면 0 + x = x 도 참이므로, MP 를 두번 적용하여

(정리 9)

를 얻는다. (정리 7) 은 이미 유도한 정리이므로 (정리 9)와 연결하여 MP 를 적용하면, 결과적으로

(정리 10)

를 유도할 수 있다. 공리 7 에 적당히 대입하여

(정리 11)

를 얻는다. 공리 2 번 교환 법칙에 p 대신 x 를, q 대신 (z + (-z)) 를 대입하면

(정리 12)

를 유도한다. 다시 위에서 쓰인 명제 논리의 규칙에 P 대신 (정리 12)를, Q 대신 (정리 11) 을 적용하고 MP 를 두 번 적용하면,

(정리 13)

여기에 앞에서 이미 유도한 (정리 11) 와 연결하여 MP 를 적용하여 다음의 결과를 얻는다.

(정리 14)

정리 11에서 했던 것처럼 이번에도 공리 7 에 적당한 대입을 하여 새로운 정리를 얻어보자.

(정리 15)

앞의 정리 13-14 을 유도할 때와 마찬가지로 과정을 되풀이 하면

(정리 16)

방금 얻은 정리에 x 대신 y 를 대입하면

(정리 17)

명제 논리의 정리 중 하나인

에 P 대신 y = x , Q 대신 x = y , R 대신 y = z, S 대신 x = z 를 대입한다. 그러면 부분은 공리 6 , 부분은 공리 7 에 적당한 대입을 한 것과 같으므로 MP 를 두 번 적용하면,

(정리 18)

라는 정리를 얻는다. 이 정리에 y 대신 (x + z) + (-z) 를, z 에 (y + z) + (-z) 를 대입하면

(정리 19)

가 된다. 여기에 (정리 17) 과 연결하여 MP 를 적용하면,

(정리 20)

이다. 이번에는 명제 논리의 정리 중 하나인,

에 P 대신 (x + y) = (y + z) 를, Q 에 (x + z) + (-z) = (y + z) + (-z) 를, R 에 x = (y + z) + (-z) 를 대입하고, (정리 2)와 연결하여 MP 를 적용하고, 그 결과에 다시 (정리 20) 과 연결하여 MP 를 적용하면,

(정리 21)

다. 다시 공리 7 에 r 대신 y 를, q 대신 (y + z) + (-z) 를, p 대신 x 를 대입하면

(정리 22)

명제 논리의 정리인

에 P 대신 (y + z) + (-z) = y 를, Q 대신 x = y 를 , R 대신 x = (y + z) + (-z) 를 대입하고 (정리 17), (정리 22) 를 차례로 MP 규칙에 따라 새로운 정리를 얻으면 최종적이 결론으로 드디어 얻고 싶었던 (정리 1)

를 유도하였다. 이 문장은 위의 과정에서 보듯 분명히 '정리'로 받아들여진다. 위의 지루한 과정이 '증명'이다. 물론 실제 수학의 세계에서는 이런 과정을 따르지 않는다. 네 단계면 충분하다.

단계를 줄이는 것은 우리의 '직관' 덕분이다. 그럴 것이라고 믿고서 한다. 여기서 굳이 위의 지루한 과정을 예로 들어보인 것은 '기계적인 과정'을 통해 증명에 도달할 수 있다는 것을 보이기 위해서다. 2 차 방정식의 해를 구하는 문제도 결국은

이라는 수학적 문장을 '유도하는' 과정이다. 이 과정도 '기계적인 과정을 통해서 증명할 수 있다.

전기 전자 회로도

문제 모음

  • ‘A 가 가면 B 는 안 간다.’ 가 참일 경우 ‘B가 간다면 A가 간다.’ 참이라고 말할 수 있을까 ?
  • x 가 동아리에 들어 있으면 y 도 꼭 동아리에 들어간다.’라는 문장이 참이고 ‘x 가 동아리에 들어가면 z 도 동아리에 들어간다.’ 가 참이라면 x 가 동아리에 들어갔다고 해보자. 어떤 일을 최소한 우리가 믿을 수 있을까?
  • x 가 녹차를 마시면 z도 녹차를 마신다.' 그리고 ’y 가 녹차를 마시면 z 도 녹차를 마신다.‘ 자, 우리 앞에 z 가 녹차를 마시고 있다. 그렇다면 x 가 녹차를 마시고 있다고 반드시 말할 수 있을까? 우리가 반드시 참이라고 할 수 있는 것은 어떤 상태일까 ?


  • 스위치 p , q 가 두개 있는 회로도를 논리적 연산으로 써보았다. 이럴 때 " 회로는 어떻게 작동할까? "
 : 두 개를 동시에 켜야 불이 켜진다.
 :. 둘 중 하나만 켜도 불이 켜진다.
 : p 스위치를 누르면 전구가 꺼진다.
  • 복도에 전구가 하나 있다. 두 곳에 전기를 켜고 끄는 곳이 있고 그 곳마다 두 개의 단추가 있다. 어떤 단추를 누르든 전구의 상태는 그 전과 달라진다. 그 복도의 전기기설이 그것만 있다고 했을 때 그것을 논리적 그림으로 그려보라.


아래 문제에서 주어진 문장들이 참일 때 문제에 결론을 이끌어보라.

  • "손으로 걷지 않은 사람은 어떻게 될까 ? "
모든 정상적인 사람은 발로 걷는다.
모든 비정상적 사람은 손을 걷는다.
  • " 모든 삶아져서 죽어 있는 가재는 빨간색이다."
모든 빨갛고 죽은 가재는 삶은 것이다.
모든 빨갛고 삶은 가재는 죽은 것이다.
  • "‘꼬마들은 악어를 길들이지 않는다.’ 라는 문장은 믿을만한가? "
꼬마들은 이성적이지 않다.
악어를 길들이는 사람은 존경받는다.
이성적이지 못한 사람은 존경받지 못한다.
  • " 참이라고 할 수 있는 문장들을 뽑아보라. "
철수가 내게 준 것은 뭐든 나는 소중히 한다.
이 뼈다귀 말고는 내 개가 맛있어 하는 것이 없어.
나는 소중한 것은 뭐든 아껴.
이 뼈다귀는 철수의 선물이야.
내가 아끼는 건 내 개에게 나는 주지 않아.


  • 음악선생님의 고민을 해결해주기.

합창연습이 한창 진행 중이던 어느 날 음악선생님에게 아주 복잡한 문제가 생겼다. 지금까지 합창대회를 열심히 준비하고 있었는데 예년처럼 치르는 줄 알고 9명을 한 조로 해서 준비를 하고 있었다. 그런데 올해는 5명이 한 조가 되어 합창대회를 치른다고 한다. 선생님은 누구도 기분이 나빠지는 것을 원하지 않았다. 아니 기분이 나빠진다고 해도 그것을 최대한 줄이고 싶었다. 그리고 무엇보다 합창 한 조가 잘 어울려야 하기 때문에 아이들에게 서로 자기의 뜻을 밝혀서 그것을 반영해서 결정을 내리기로 하였다. 아이들에게 물었더니 다행히 아이들은 서로 많이 친하고 이해하고 있었기 때문에 스스럼없이 이야기를 했다. 그것으로 상대방을 질시하지 않고 무엇보다 좋은 합창을 보여주기 위해 더 어울리는 사람들이 모여야 한다고 서로 마음이 맞은 것이다. 자 다음의 답을 들어보자.

아람 : “유리는 꼭 들어가야 해요. 우리 중에 노래를 가장 잘하잖아요. 전 뭐 그것만 지켜진다면 아무래도 좋아요.”
보성 : “나라가 안들어가면 난 안들어가요. 우린 항상 함께 해왔구, 집에도 함께 간단 말예요.”
별 : “전 동석이가 들어가야 들어가겠어요. 동석이랑 제가 화음이 가장 맞는 것 같이 생각되거든요.”
동석 : “ 지연만 아니면 되요. 전 지연이랑 한번 크게 싸웠는데 우린 서로 화해가 안될 것 같고 그래서 지연 목소리가 들리면 제 노래가 잘 안되거든요. 이게 제 잘못인지는 알지만 그리고 시간이 지나서 화해할 수 도 있을 거예요. 하지만 지금 우리 합창단을 위해서는 어쩔 수 없는 것 같아요.”
상호 : “저도 지연이 좋지는 않아요. 지연이랑 싸운 건 아니구요, 단지 지연 목소리가 좀 제게는 이상하게 걸려요. 하지만... 하지만 별이가 들어간다면 상관없어요. 별이 목소리가 들어가면 지연이랑 또 어울리는 것 같거든요.”
지연 : “전 별이만 아니면 돼요.” 단 한마디만 하고 지연은 무뚝뚝하게 앉았다.
규리 : “ 전 별이하고 동석이만 들어가면 전 함께 일하고 싶어요. 그런데 지연은 저도 싫어요. 그리고 아람이도 싫어요. 꼭 제들 둘이는 목소리는 아름답지만 저랑은 화음이 잘 안 어울리는 것 같아요.”
나라 : “전 별이나 동석이가 들어가면 안들어갈래요. 규리가 말한 사정과 비슷해요.”
상호 : “규리없인 전 노래할 수 없어요. 그리고 보성이랑 함께 합창단에 들어가는 건 싫어요.” (상호는, 사실, 규리를 몰래 좋아하고 있었는데 보성이랑 규리에게 장난질 치는 것이 싫었던 것이다.) “그리고 보성이 없이 동석이가 오는 것도 싫어요. 보성이까지는 참을 수 있을지도 모르지만 보성이 없이 동석이는 너무 저 혼자 목소리를 키우거든요.”
나라 : “ 제가 들어간다면 꼭 별이나 상호 중 하나가 들어와야 해요. 그래야 제 가 합창단에 들어간 의미가 있거든요. 제 목소리와 어울리려면 둘 중 하나는 꼭 있어야 하거든요, 규리가 없이 동석이가 들어가 있지 않았으면 좋겠어요. 그러면 전 들어갈 수 없어요.”

자 이런 일이 있고 나서 합창대회는 하루하루 다가오는데 우리 음악선생님은 아이들의 뜻을 고루 반영하기 위해 며칠을 끙끙 앓다가 점심시간에 평소 친하게 진해던 수학선생님과 이에 대해 이야기를 나누게 되었다. 수학 선생님은 점심 시간이 지나고 다시 자세히 들으시며 무언가 끄적끄적 적으시더니 잠시 후에 그럼 이렇게 하는게 가장 좋겠군요. 하고 조언을 하였다. 수학 선생님은 어떤 답을 찾아낸 것일까요?




Note

  1. 아래 세 예제는 Kvant 잡지,71 년 4 호에서 인용하여 약간 변형하였다.