1 기초: 논리와 증명 2

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

1.2 명제 논리의 응용

문장 번역하기

문장을 명제 변수와 논리 연결자로 이루어진 수식으로 바꾸는데 많은 이유들이 있습니다. 특히, 많은 자연 언어들이 모호합니다. 문장을 복합 명제와 논리 표현식으로 바꾸면 모호함이 없어집니다. 이런 과정은 문장의 의도된 의미에 근거하여 합리적인 가정을 포함할 수 있습니다. 더, 문장을 논리 표현식으로 바꾸면 사용자는 진리값을 구하기위해 논리 표현식을 분석하고, 진리값을 다룰 수 있고, 추론 규칙을 이용할 수 있습니다.

문장을 논리표현식으로 바꾸는 절차는 아래에서 확인할 수 있습니다.

예제 1

"캠퍼스에서 인터넷에 접근할 수 있다면 당신은 컴퓨터 과학이 전공이거나 신입생이 아니다"

정답

문장을 논리적 표현식으로 변환하는데는 다양한 방법이 있습니다. 한 문장을 명제 변수 p로 표현할 수 있지만 의미를 해석하는데 있어서 크게 도움되지 않습니다. 그 대신에 문장 부분과 그 사이의 논리연결사에대해 명제변수를 사용할 것입니다. 특히, a,c 그리고 f 각각 "캠퍼스에서 인터넷을 접속할 수 있다.", "너는 컴퓨터 과학이 전공이다." 그리고 "너는 신입생이다." 를 표현합니다. 그러면 다음과 같이 표현할 수 있습니다. 

a -> (c v ~f ) 

예제 2

"키가 120cm보다 작고 나이가 16보다어리면 롤러코스터에 탈 수 없습니다" 

(You cannot ride the roller coaster if you are under 4 feet tall unless you are older than 16 years old)

정답

q, r 그리고 s는 각각 "롤러코스터에 탈 수 있습니다" "키가 120cm보다 작습니다" 그리고 "16살 보다 나이가 많습니다" 표현합니다. 그러면 문장은 다음과 같이 표현됩니다.

(r ^ ~s) -> ~q

물론, 위의 문장을 논리적 표현으로 바꾸는데에 많은 방법이 있지만, 앞서 사용한 표현으로도 충분히 목적을 달성했습니다.

시스템 요구사항

자연언어를 논리적 표현식으로 변환하는 것은 하드웨어와 소프트웨어 시스템을 설계하는데 반드시 필요합니다. 시스템과 소프트웨어 엔지니어는 자연언어를 통해 요구사항을 받고 시스템 개발 기초에 이용되는 정확하고 분명한 시스템사양을 생산해야합니다.

예제 3

"자동 응답은 파일 시스템이 꽉 찼을때 전송될 수 없습니다."

정답

이 문장을 변환하는 방법은 p를 "자동 응답은 전송 될 수 있습니다"로 표현하고 q를 "파일 시스템은 꽉 찼습니다" 로 표현합니다. 그다음 ~p는 "자동 응답은 전송 될 수 없습니다"를 표현할 것입니다. 결과적으로, 우리의 요구사항은 다음과 같은 조건문으로 표현됩니다. 

q -> ~p

시스템 요구사항은 일관적이여야합니다. 즉, 자칫 모순을 일으킬 수 있는 대립하는 요구사항들을 담고 있어선 안됩니다. 요구사항들이 일관적이지 않으면, 모든 요구사항들을 만족시킬 수 있는 시스템을 개발하기란 불가능합니다.

예제 4

"상태 진단 메세지는 버퍼에 담겨있거나 재전송됩니다."

"상태 진단 메세지는 버퍼에 담겨있어선 안 됩니다."

"상태 진단 메세지가 버퍼에 담겨있을 경우, 재전송됩니다."

정답

요구사항들이 일관적인지 판단하기 위해선, 먼저 논리적 표현식을 이용하여 표현하여야합니다. p를 "상태 진단 메세지는 버퍼에 담겨있습니다"로 q를 "상태 진단 메세지는 재전송됩니다"로 표현한다고 합시다. 요구사항은 다음과 같이 쓸 수 있습니다. p v q, ~p, p->q. 앞선 세 논리적 표현식을 모두 참인 진리값으로 만들기 위해 우선적으로 ~p가 참이 되기위해 p는 반드시 거짓인 진리값을 가지고 있어야합니다. 그리고 p v q 가 참이 되기위해서는 p는 거짓이어야하므로 q는 반드시 참인 진리값을 가지고 있어야합니다. 그다음 p->q는 p가 거짓이고 q가 참일 때 진리값 참을 가지고, p가 거짓이고 q가 참일 때 요구사항들은 참을 가집니다. 따라서 위 요구사항들이 일관적이라고 결론 내릴 수 있습니다. 진리표를 이용해서도 똑같은 결론에 도달할 수 있습니다.

예제 5

예제에 "상태메세지는 재전송되지 않습니다"라는 명제가 추가되면 요구사항들은 여전히 일관적입니까?

정답

예제 4에서 p가 거짓이고 q가 참일 때 요구사항들은 일관적입니다. 하지만, 새로 추가된 명제는 ~q 이이고, q가 참일때 ~q는 거짓입니다. 결과적으로, 명제가 4개일 때는 요구사항들이 일관적이지 않습니다.

불린 검색

웹페이지처럼, 방대한 정보 모음집을 검색할 때 논리적 연결사는 널리 사용됩니다. 이 검색법은 명제 논리에서 쓰이는 기술들을 쓰기 때문에, 불린 검색(Boolean searches)이라고 불립니다. 

불린검색에서, AND 연결사는 두 검색어 모두 담고 있는 기록을 찾아 줄 때 사용되고, 연결사 OR는 두 검색어 중 하나 또는 둘다를 포함한 기록을 찾아 줄 때 사용합니다. 연결자 NOT는 특정 검색어를 배제할 때 사용됩니다. (AND NOT으로 쓰이기도 합니다)

예제 6

대부분의 웹 검색엔진은 특정한 주제에 관한 웹 페이지를 찾아주는 불 검색 기술을 지원합니다. 예로, 뉴 멕시코내에 위치한 대학교들에 관한 웹페이지들을 찾기 위해 불린 검색을 사용하면 사용자는 NEW AND MEXICO AND UNIVERSITIES와 일치하는 페이지들을 찾습니다. 이 검색의 결과는 세 단어 NEW, MEXICO 그리고 UNIVERSITIES를 담고있는 페이지들을 포함하고 있습니다. 멕시코에 있는 새 대학교와 같은 다른 결과들과 원래 관심있는 모든 페이지들을 포함할 것입니다. (구글을 포함한 다른 검색 엔진은,”AND” 단어를 이해하기는 하지만 이 단어를 필요로 하지 않습니다. 검색어가 기본적으로 포함되기 때문입니다. 이런 검색 엔진은 또한 특정 문구 검색에 대한 따옴표를 지원합니다. 그러므로, “New Mexico” AND UNIVERSITIES와 일치하는 페이지를 검색하는 것이 더욱 효율적일 것입니다.)

다음으로, 뉴 멕시코나 애리조나에 위치한 대학교들에 관한 페이지를 검색하기 위해선, 사용자는 다음과 일치하는 페이지를 찾을 수 있습니다. (NEW AND MEXICO OR ARIZONA) AND UNIVERSITIES. (주의: 여기서 AND 연산자는 OR 연산자보다 선행처리 됩니다. 구글에서는, 이 검색을 위해 사용되는 용어는 NEW MEXICO OR ARIZONA일 것입니다.) 이 검색의 결과는 UNIVERSITIES 단어와 NEW와 MEXICO 또는 ARIZONA 단어를 담고있는 페이지들을 포함할 것입니다. 마지막으로 뉴 멕시코가 아닌 멕시코 내에 위치한 대학을 검색하기 위해선 MEXICO AND UNIVERSITIES와 일치하는 페이지들을 찾을 것입니다. 그러나 결과가 뉴 멕시코내의 대학교들에 관한 페이지도 포함하기 때문에 다음과 일치하는 페이지를 검색하는 것이 더 낫습니다. (MEXICO AND UNIVERSITIES) NOT NEW. 검색 결과는 MEXICO 와 UNIVERSITIES를 모두 포함하였지만 NEW 제외한 단어를 담고있는 모든 페이지들을 포함할 것입니다.(구글을 포함한 다른 검색엔진들은, “NOT” 단어는 기호 “-“로 대체됩니다. 구글에서는 다음과 같은 검색어를 사용할 수 있습니다. MEXICO UNIVERSITIES -NEW)

논리 퍼즐

예제 7

논리 퍼즐의 대가 스멀리언은 항상 진실을 말하는 기사와 항상 거짓을 말하는 깡패에 관한 섬에 대한 퍼즐을 많이 다뤘습니다. 당신은 두 사람 A와 B를 마주쳤습니다. A가 “B는 기사입니다” 라고 말했고 B가 “우리는 서로 다른 직업입니다.” 라고 말했다면 A와 B의 직업은 무엇일까요?

정답

p와 q를 각각 “A는 기사입니다”와 “B는 기사입니다” 라고 합시다. 그렇다면 ~p와 ~q는 다음의 명제와 같습니다. “A는 깡패입니다”와 “B는 깡패입니다”

우선 A가 기사인 경우를 가정합니다. 그렇다면 명제 p는 진실입니다. 만약 기사이면, 그가 진술한 B가 기사라는 것이 참입니다. 그러므로 q도 참입니다. 그리고 A와 B가 같은 직업입니다. 그러나, B는 기사이므로 B의 진술 “우리는 서로 다른 직업입니다” (p ^ ~q) v (~p ^ q) 또한 참이 되어야합니다. 그러나 A와 B가 모두 기사이므로 해당 명제는 참이 될 수 없습니다. 따라서, A는 기사가 아니고 명제 p는 거짓으로 결론 맺을 수 있습니다.

A가 깡패이라면, A의 진술은 모두 거짓입니다. B가 기사라는 그의 진술 – q가 참-은 거짓말이 됩니다. 따라서 q는 거짓이고 B 또한 깡패가 됩니다. 더, B가 깡패라면 A와 B가 다른 직업이라는 그의 진술 또한 거짓이 되므로 A와 B 모두 깡패라는 진술은 일관적입니다. 따라서 우리는 A와 B모두 깡패라고 할 수 있습니다.

 

예제 8

아버지는 딸과 아들에게 마당에서 놀지만 더러워지지 말라고 했습니다. 그러나 두 아이들은 놀다가 이마에 흙을 묻혔습니다. 아이들이 다 놀고나서 아버지는 다음과 같이 말했습니다. “적어도 한 명은 이마에 흙을 묻혔구나” 그리고 아이들에게 다음 질문에 “예”, “아니오”로 답하라고 하였습니다. .”네 이마에 흙이 묻었는지 알고 있니?” 아버지는 이 질문을 두 번 했습니다. 두 번의 질문에 대해 아이들의 각각 답변은 어떨까요? 단, 아이들은 자신들의 이마에 묻은 흙은 볼 수 없지만 서로의 이마는 볼 수 있습니다. 두 아이들의 답변은 동시에 발설한다고 가정합시다.

정답

s를 “아들의 이마에 흙이 있다”와 d를 “딸의 이마에 흙이 있다”로 합시다. 아빠가 한 말인 “두 아이들 중 적어도 한 아이에게 흙이 묻어 있다”는 논리합인 s v d 가 참이라는 것입니다. 두 아이들은 서로의 이마를 보았기 때문에 자신의 이마에 흙이 묻었냐는 아버지의 첫 질문에 ‘아니요’ 라고 답할 것입니다. 아들은 d가 참인 것을 알지만 s가 참인지는 모르고, 딸은 s가 참인 것을 알지만 d가 참인지는 모르기 때문입니다.

아들이 첫 번째 질문에 ‘아니요’ 라고 답한 뒤, 딸은 명제 d가 참인 것을 알 것입니다. 아들은 s v d가 참인 것은 알았지만 s가 참인지는 몰랐기 때문입니다. 이 정보를 이용하여 딸은 d가 반드시 참이라고 결론 내렸습니다. d가 거짓이라면 아들은 s v d가 참인 것을 알았기 때문에 s가 반드시 참이라고 결론 내렸고 첫 질문에 “예” 라고 답했을 겁니다. 아들은 딸과 유사한 방법으로 s가 반드시 참이라고 결론 내렸을 겁니다. 따라서, 두 아이들은 두번째 질문에서 “예” 라고 답했을 겁니다.