이산수학 Discrete Mathematics 이산수학기본구조 인천대학교컴퓨터공학과공학시인이숙이철호교수 개인메일 : Jullio@chol.com 인천대메일 :zullio@inu.ac.kr 빠른연락 : 010 3957 6683 모바일컴퓨팅연구실 07 401 호
배우고때때로익히면, 또한기쁘지아니한가 배우고익힘의시간을통해서삶이기쁨으로이르는것이아니겠는가? 2
오늘의강의목표 논리와증명에대하여 명제논리 명제의동치 한정기호 추론규칙 증명 3
지난주에 1 3 3 5 4 5 6 8 7? 4 3 5 2 1? 에들어가는적당한숫자는무엇일까? 4
지난주에 1 3 3 5 4 5 6 8 7? 4 3 5 2 1 A B C? 에들어가는적당한숫자는무엇일까? A + C = B 1 + 4 = 5, 3 + 3 = 6, 3 + 8 = 5, 5 + 2 = 7 4 + 1 =? ==> 5 5
명제논리 (Propositional logic) 명제 : 참또는거짓중하나의값을가진선언적문장 명제변수 : p, q, r, s 명제진리값 : T(True), F(False) 복합명제 : 하나또는여러개의조합명제 진리표 (Truth Table), 진리값 (Truth Value) 논리연산자 (Logical Operators) 부정 (Negation Operator) : NOT,, 논리곱 (Conjunction) : AND, 논리합 (Disjunction) : OR, 조건문 (Conditional Statement) : 상호조건문 (Biconditional Statement) : 배타적논리합 (Exclusive Or) : XOR, Inclusive OR 포괄적논리합 6
논리연산자 1 순위 2 순위 3 순위 3 순위 4 순위 5 순위 7
명제논리 (Propositional Logic) 부정 (Negation) 논리곱 (Conjunction) 논리합 (Disjunction) 배타적논리합 (Exclusive OR) 8
명제논리 (Propositional logic) 조건문 (Conditional Statement) 상호조건문 (Biconditional Statement) 조건문 : 함축 (Implement) p q는조건 p가설립할때, q가참 p => 가정, 전제, 전항 q => 결론, 결과 p는 q의 p q 를 p 이면 q 이다 충분조건이다. q 는 p 의 필요조건이다. 상호조건문 : 상호함축명제 p q 는 p, q가동일한진리값일때만참 => if and only if => p if and only if q => 배타적논리합의역수 p 는 q 의 필요충분조건 9
명제논리 (Propositional logic) 역, 이, 대우간의관계진리표 동치 (equivalent) 10
명제논리 (Propositional logic) 논리연산자의우선순위 비트연산자 OR, AND, XOR 의진리표 11
논리게이트 (Logic Gates) NAND Gate NOR Gate 12
논리회로 Half Adder Full Adder 13
항진명제, 모순, 불확정명제 항진명제 (Tautology) : 복합명제의값이항상참일때 모순 (Contradiction) : 복합명제의값이항상거짓일때 불확정명제 (Contingency) : 항진명제도모순도아닌복합명제경우에따라참또는거짓을가질경우 14
동치관계 논리적동치식 (Page 33) 15
동치관계 16
한정기호 술어논리 (Predicate Logic) 변수값에따라그명제가참이되거나거짓이되는논리 명제함수 (Propositional Function) 변수에대하여명제가되고진리값이판정되는명제를갖는함수 전조건 (Preconditions) 올바른입력을기술하는문장 후조건 (Postconditions) 프로그램이수행되었을때출력이만족해야할조건 한정기호 (Quantifier) 술어가원소들의어떤영역에서참이되는범위 all, some, many, none, few 전칭한정기호 (Universal Quantifier) for all, for every, for each, all of, given any 특정영역에속하는모든값에대하여참일때 존재기호 (Existential Quantifier) For some, there exists, there is 적어도하나의값에대하여명제함수에대하여참일때 17
전칭한정기호 Universal Quantifier 정의역에속하는 x 의모든값에대하여 P(x) 이다. for all x P(x), 또는 for every x P(x) 로읽음. 모든 x에대하여 P(x) 는참 P(x) 가거짓이되는 x가있다. 18
존재기호 Existential Quantifier 정의역에속하는적어도하나의값 x 에대하여 P(x) 이다. for some x P(x) 로읽음 P(x) 가참이되는x가있다. 모든 x에대하여 P(x) 가거짓이다. 19
한정기호 구속변수 (Binding Variable) 한정기호가적용된변수 x 자유변수 (Free Variable) 한정기호가적용되지않거나, 값이할당되지않은변수 20
2 변수의한정화 표현참거짓 모든 x, y 의쌍에대하여 P(x, y) 가참 모든 x 에대하여 P(x, y) 가참이되는 y 가있다. 어떤 x 가있어서모든 y 에대하여 P(x, y) 가참 P(x, y) 가참이되는 X, y 의쌍이있다. P(x, y) 가거짓이되는 x, y 의쌍이있다. 어떤 x 가있어서모든 y 에대하여 P(x, y) 가거짓 모든 x 에대하여 P(x, y) 가거짓이되는 y 가있다. 모든 x, y 의쌍에대하여 P(x, y) 가거짓 21
추론 오류 : 부당한논증 전제 (premise) : ( 명제들의순열 ) 주어진명제들 p 1, p 2,..., p n 결론 (conclusion) : ( 최종명제 ) 새로이유도된명제 q (p 1, p 2,..., p n ) -> q 22
추론 수학적증명 수학적진술의참을입증하는정당한논증 논증 하나의결론으로끝나는진술들의순서적배열 ( 순열 ) 정당하다는것 결론, 즉논증의최종진술이전제 ( 논증의앞에오는진술들 ) 들의참값으로부터유도될수있는것 논증이정당하다는것의필요, 충분조건은그논증의모든전제가참이면서동시에그결론이것짓일수없다는것 논증의형식정당 23
추론규칙 논증 : 명제의순열 긍정논법 부정논법 전제 : 그논증의최종명제를제외한명제 결론 : 최종명제 가설적삼단논법 논리합삼단논법 가산논법 단순화논법 논리곱논법 용해법 24
추론의규칙들 삼단논법 : p q, q r p r 삼단논법 (Hypothetical syllogism) 예 ) p q : 소크라테스는사람이다 q r : 사람은죽는다. p r : 그러므로소크라테스는죽는다. 긍정논법 : p q, p q 긍정논법 (Modus ponens, Method of Affirming ) 예 ) p q : 비가오면땅이젖는다 p : 비가왔다 q : 그러므로땅이젖었을것이다 부정논법 : p q, q p 부정논법 (Modus tollens, Method of Denying ) 예 ) p q : 비가오면땅이젖는다 q: 땅이젖지않았다. p: 그러므로비가오지않았을것이다. Converse Error ( 역오류 ) 예 ) p q : 비가오면땅이젖는다 q: 땅이젖었다 p : 그러므로비가왔을것이다 ( 물을뿌려서땅이젖은경우가있다 ) Inverse Error ( 이오류 ) 예 ) p q : 비가오면땅이젖는다 p : 비가오지않았다 q : 그러므로땅이젖지않았을것이다 ( 물을뿌려서땅이젖은경우가있다 ) 25
한정기호를사용한명제추론규칙 임의의 c 에대하여 P(c) 전칭예시화 전칭일반화 어떤원소 c 에대하여 P(c) 어떤원소 c 에대하여 P(c) 존재예시화 존재일반화 26
증명 직접증명 : p 가참이라는가정으로부터 q 가참이된다는결론을직접유도 반증법 : p->q 가거짓인을보이는증명 대우증명법 : ~q 라고가정하면 ~p 에도달함을보이는방법 모순증명법 : 가설이참이고, 결론이거짓이라고하면, 모순이됨을보이는방법 수학적귀납법 : 기본단계, 귀납단계를거처귀납적으로증명하는방법 27
연역추론 ( 演繹推論,deductive reasoning) 일반적인원리를근거로구체적개별적문제에대한결론을추론하는방법 전제가참이면결론도반듯이참임을추론하는논증 새로운지식이아니며, 결론이대전제의일부임 대전제 : 모든동물은죽는다 소전제 : 사람은동물이다 결론 : 그러므로사람도죽는다. 28
귀납법 ( 歸納法, induction) 여러가지구체적개별적사실을관찰을통하여공통적으로나타나는현상을일반적인원리로추론하는방법 전제가참이면결론도참일가능성이있음을논증 전제가참이어도결론이거짓일수있음 수학적귀납법의예참고 29
변증법 ( 辨證法 ) 전제된하나의명제가모순인것을증명하여전제를제거하는추론방법 철학적인자기주장을펼쳐가는과정 정반합 ( 正, 反, 合 ) 을통하여논증하는토론의방법 30
공리, 정리, 법칙, 정의 공리 (axiom) 증명과정없이참이라고간주하는명제 증명불가능한자명한명제 ) 공준 (postulate) 누구도의심없이받아드릴수있는학문적원리 정리 (theorem) 참이라고증명된명제 보조정리 (lemma) 다른정리를증명하는데유용하게사용되는정리 법칙 (principle) 관찰된현상으로주어진전체에서모든구체적인현상에항상참이라고증명된수학적추론 정의 (definition) 기존의개념을이용하여만들어진새로운개념 31
직접증명법 홀수의곱은홀수임을직접증명법으로증명하라 홀수 : 짝수보다 1 많거나적은수 짝수 : 2 의배수 A = 2k +1 (k Z) B = 2 l + 1 (l Z) AxB = (2k+1)(2l +1) = 4kl+2k + 2l+1 = 2(2kl+k + l)+1 = 2 m +1 홀수의곱은홀수이다 32
수학적귀납법 Ex) 연속한세자연수의곱은 6의배수이다. P(k) = k (k+1) (k+2) ( 단 k N) 6의배수 증명 1) 기본단계 - p(i) 가참 2) 귀납단계 p(k+1) 가참 6 의배수 + 6 의배수는 6 의배수이다. 연속하는세자연수의곱은 6 의배수이다. 증명끝 1) P(1) 1 x 2 x 3 = 6 2) P(2) 2 x 3 x 4 = 24 3) P(3) 3 x 4 x 5 = 60 p(k) = k (k+1) (k+2) 가 6의배수라면 P(k+1) = (k+1) (k+2) (k+3) K (k+1) (k+2) + 3(k+1) (k+2) 6의배수 6의배수 33
증명방법과전략 전수증명 경우에의한증명 존재증명 : => for some x P(x) 유일성증명 존재성 : x 가쥬어진특성을가지고있지않음을보임 유일성 : 만약 y x 이면 y 는주어진특성을가지지않음을보임 34
전향추론 (forward reasoning) 공리들과알려진정리들을가정과함께사용하여중간단계를이용증명하는추론방법 비교적간단한증명에사용 직접증명방식 35
후향추론 (backward reasoning) 공리들과알려진정리들을가정하여, 결론으로부터중간단계를이용하여증명하는추론방법 인공지능에서전향후향추론방법복합화하여들을사용 36
쉬어가는시간 무거운공찾기??? 크기가같은공이 8개가있다. 7개는무개가같고, 8개중하나는조금더무겁다. 천칭 (Balance) 를사용하여무거운공하나를찾는방법은? 37
쉬어가는시간 무거운공찾기??? 크기가같은공이 8개가있다. 7개는무개가같고, 8개중하나는조금더무겁다. 천칭저울 (Balance) 을사용하여무거운공하나를찾는방법은? 이것을 2번만에찾는방법은??? 이름, 학번, 답이라고생각하는이유 다음주 3월 14일수업내용은 2장이산수학의기본구조 - 집합, 함수, 수열, 행렬 38