논리와 명제:추론, 술어 논리,항진 모순 명제,prolog(논리용 언어)
myPPT
2013. 4. 5. 04:55
CONTENTS CONTENTS 2.1 논리와 명제 2.2 논리 연산 2.3 항진 명제와 모순 명제 2.4 논리적 동치 관계 2.5 추론 2.6 술어 논리 2.7 논리용 언어 -Prolog 개요 .논리와명제와관련된전반적인논제들을고찰함 .명제를정의하고, 단순명제와합성명제를통한논리연산을다룸 .주요6가지논리연산자, 즉부정, 논리합, 논리곱, 배타적논리합, 조건, 쌍방조건들을진리표를통하여살펴봄 .어떤명제의역, 이, 대우를고찰하며, 항진명제와모순명제를정의함 .논리적동치관계와주요성질들을고찰함 .추론을정의하여그것과관련된몇가지예를살펴보며전체한정자와존재한정자를다룸개요 .논리와명제와관련된전반적인논제들을고찰함 .명제를정의하고, 단순명제와합성명제를통한논리연산을다룸 .주요6가지논리연산자, 즉부정, 논리합, 논리곱, 배타적논리합, 조건, 쌍방조건들을진리표를통하여살펴봄 .어떤명제의역, 이, 대우를고찰하며, 항진명제와모순명제를정의함 .논리적동치관계와주요성질들을고찰함 .추론을정의하여그것과관련된몇가지예를살펴보며전체한정자와존재한정자를다룸 2. 논리와명제2. 논리와명제 . 논리 (logic) 인간의 사고가 논리적인지를 판단하는 것은 사고하는 사람이 주어진 문제를 객관적으로 명확한지의 여부와 사고의 법칙을 체계적으로 추구하여 분석하는지의 여부로 결정함 . 인간이 어떻게 사고하는가를 표현하는 사고의 규칙을 말함 . 수학적 표현의 의미를 정확하게 기술할 수 있게 함 . 논리의 연구와 응용 . 알고리즘의 설계나 증명 , 디지털 논리 회로의 설계 , 논리 프로그램 관련 분야 , 관계형 데이터베이스 이론 , 오토마타와 계산 이론, 인공지능 등에 필요한 이론적 기반을 제공함 Discrete Mathematics Chapter 2. 논리와 명제 3 2.1 논리와명제 . 논리의 종류 . 명제 논리 (Propositional Logic) . 주어와 술어를 구분하지 않고 전체를 하나의 식으로 처리하여 참 또는 거짓을 판별하는 법칙임 . 술어 논리 (Predicate Logic) . 주어와 술어로 구분하여 참 또는 거짓에 관한 법칙임 Discrete Mathematics Chapter 2. 논리와 명제 4 2.1 논리와명제2.1 논리와명제 . 명제는 통상 영문 소문자 p, q, r, … 등으로 표기함 . 명제가 참 또는 거짓의 값을 가질 때 그 값을 명제의 진리값(truth value) 이라고 함 . 명제의 진리 값은 참일 때는 T(true), 거짓일 때는 F(false) 로 각각 표시함 . 명제는 T와 F의 2가지의 진리 값만을 가지므로 이진 논리라고 함 Discrete Mathematics Chapter 2. 논리와 명제 5 2.1 논리와명제2.1 논리와명제 A proposition (p, q, r, s, …) is a declarative statement that is either true (T) or false (F), but not both. Who is there? (not declarative, question) Just do it! (command) x + 2 = 5. (non-constant value, variable) Discrete Mathematics Chapter 2. 논리와 명제 6 2.1 논리와명제2.1 논리와명제 Discrete Mathematics Chapter 2. 논리와 명제 7 2.2 논리연산2.2 논리연산 . 단순 명제 (simple proposition) . 하나의 문장이나 식으로 구성되어 참이나 거짓을 구분하는 것 . 합성 명제 (composition proposition) . 여러 개의 단순 명제가 연결되어 만들어진 명제 . 논리 연산자 (logical operators) . 단순 명제들을 연결시켜 주는 역할을 하는 연결자(connectives) . 진리표 (truth table) . 단순 명제들의 진리값에서부터 논리 연산자에 따라 단계적으로 진리값을 나타내준표 Discrete Mathematics Chapter 2. 논리와 명제 8 2.2 논리연산2.2 논리연산 Discrete Mathematics Chapter 2. 논리와 명제 9 2.2 논리연산2.2 논리연산 Discrete Mathematics Chapter 2. 논리와 명제 10 2.2 논리연산2.2 논리연산 Discrete Mathematics Chapter 2. 논리와 명제 11 2.2 논리연산2.2 논리연산 (1) 부정(Negation) . 임의의 명제 p가 주어졌을 때 그 명제에 대한 부정 (negation) 은 명제 p의 반대되는 진리값을 가짐 . 기호로는 ~p라 쓰고‘ not p 또는 p가 아니다 라고 함 . p의 진리값이 참이면 ~p의 진리 값은 거짓임 . p의 진리값이 거짓이면 ~p의 진리 값은 참임 p ¬p T F F T Operand column Result column Discrete Mathematics Chapter 2. 논리와 명제 12 2.2 논리연산2.2 논리연산 Discrete Mathematics Chapter 2. 논리와 명제 13 2.2 논리연산2.2 논리연산 (2) 논리곱(Conjunction) . 임의의 두 명제 p, q 가‘그리고(AND)’로 연결되어 있을 때 명제 p, q 의 은 p∧q로 표시함 . ‘ p and q 또는 p 그리고 q’라고 함 . 두 명제의 논리곱 p∧q는 두 명제가 모두 참인 경우에만 참이라고 함 . 그렇지 않으면 거짓의 진리 값을 가짐 Discrete Mathematics Chapter 2. 논리와 명제 14 2.2 논리연산2.2 논리연산 Discrete Mathematics Chapter 2. 논리와 명제 15 2.2 논리연산2.2 논리연산 (3) 논리합(Disjunction) . 임의의 두 명제 p, q 가‘또는(OR) ’으로 연결되어 있을 때 명제 p, q 의 은 p∨q로 표시함 . ‘ p or q나 p 또는 q’라고 표현함 . 두 명제의 논리합 p∨q는 두 명제가 모두 거짓인 경우에만 거짓의 진리값을 가짐 Discrete Mathematics Chapter 2. 논리와 명제 16 2.2 논리연산2.2 논리연산 Discrete Mathematics Chapter 2. 논리와 명제 17 2.2 논리연산2.2 논리연산 (4) 배타적 논리합 (Exclusive OR) . 임의의 두 명제 p, q의 p q로 표시함 . ‘익스클루시브 OR(Exclusive OR) 또는 XOR’이라고 읽음 . 진리 값은 p와q 두 명제 중에서 하나의 명제가 참이고 다른 하 나의 명제가 거짓일 때 참의 진리 값을 가지고 , 그렇지 않으면 거짓의 진리 값을 가짐 . XOR: 논리회로 구성 , 패러티비트 등에 활용 Discrete Mathematics Chapter 2. 논리와 명제 18 2.2 논리연산2.2 논리연산 (5) 조건(Implication) . 조건 연산자를 함축(implication) 이라고 함 . 임의의 명제 p, q의 조건 연산자는 p →q로 표시함 . ‘p이면 q이다’라고 읽음 Discrete Mathematics Chapter 2. 논리와 명제 19 2.2 논리연산2.2 논리연산 조건연산자 → 는‘ p이면 q이다’뿐만 아니라 , 똑같은 진리 값을 가지는 다양한 표현 (a) p이면 q이다. (if p, then q) (b) p는 q의 충분조건이다 . (p is sufficient for q) (c) q는 p의 필요조건이다 . (q is necessary for p) (d) p는 q를 함축한다 . (p implies q) Discrete Mathematics Chapter 2. 논리와 명제 20 2.2 논리연산2.2 논리연산 Discrete Mathematics Chapter 2. 논리와 명제 21 2.2 논리연산2.2 논리연산 Discrete Mathematics Chapter 2. 논리와 명제 22 2.2 논리연산2.2 논리연산 쌍방 조건도 조건 연산자의 경우와 마찬가지로 같은 의미를 가진 다른 표현임 (1) p이면 q이고, q이면 p이다. (p if and only if q) (2) p는 q의 필요충분조건이다 . (p is necessary and sufficient for q) Discrete Mathematics Chapter 2. 논리와 명제 23 2.2 논리연산2.2 논리연산 Discrete Mathematics Chapter 2. 논리와 명제 24 2.2 논리연산2.2 논리연산 Discrete Mathematics Chapter 2. 논리와 명제 25 2.2 논리연산2.2 논리연산 Discrete Mathematics Chapter 2. 논리와 명제 26 2.2 논리연산2.2 논리연산 Discrete Mathematics Chapter 2. 논리와 명제 27 2.2 논리연산2.2 논리연산 (명제의 역 , 이, 대우의 상호 관계 ) Discrete Mathematics Chapter 2. 논리와 명제 28 2.2 논리연산2.2 논리연산 동치(equivalent) Discrete Mathematics Chapter 2. 논리와 명제 29 2.2 논리연산2.2 논리연산 Discrete Mathematics Chapter 2. 논리와 명제 30 2.3 항진명제와모순명제2.3 항진명제와모순명제 Discrete Mathematics Chapter 2. 논리와 명제 31 2.3 항진명제와모순명제2.3 항진명제와모순명제 Discrete Mathematics Chapter 2. 논리와 명제 32 2.3 항진명제와모순명제2.3 항진명제와모순명제 Discrete Mathematics Chapter 2. 논리와 명제 33 2.4 논리적동치관계2.4 논리적동치관계 . 두 명제가 논리적 동치일 경우는 두 명제의 논리값이 서로 같으므로 하나의 명제가 다른 명제를 대신할 수 있음 . 어떤 복잡한 명제를 좀 더 간단한 명제로 만들어 주기 위해서 논리적 동치 관계인 다른 명제를 사용하여 간소화함 Discrete Mathematics Chapter 2. 논리와 명제 34 2.4 논리적동치관계2.4 논리적동치관계 . 예제 2-15 풀이 : Discrete Mathematics Chapter 2. 논리와 명제 35 2.4 논리적동치관계2.4 논리적동치관계 Discrete Mathematics Chapter 2. 논리와 명제 36 2.4 논리적동치관계2.4 논리적동치관계 흡수법칙 : (집합의 Venn Diagram 으로 생각하면 쉽게 이해됨 ) Discrete Mathematics Chapter 2. 논리와 명제 37 2.4 논리적동치관계2.4 논리적동치관계 . 두 명제가 논리적 동치 관계임을 입증하는 방법 . 두 명제에 대한 진리표를 구하고 두 명제의 진리 값이 같음을 증명함 . 하나의 명제로부터 논리적 동치 관계의 기본 법칙을 이용하여 다른 명 제로 유도해 냄 . 이 중 문제에 적당한 방법을 선택하여 문제를 해결함 Discrete Mathematics Chapter 2. 논리와 명제 38 2.4 논리적동치관계2.4 논리적동치관계 Discrete Mathematics Chapter 2. 논리와 명제 39 2.4 논리적동치관계2.4 논리적동치관계 Discrete Mathematics Chapter 2. 논리와 명제 40 2.4 논리적동치관계2.4 논리적동치관계 Discrete Mathematics Chapter 2. 논리와 명제 41 2.5 추론2.5 추론 전제 (premise) : 주어진 명제들 p1, p2, ..., pn 결론 (conclusion) : 새로이 유도된 명제 q p1, p2, ..., pn ├ q Discrete Mathematics Chapter 2. 논리와 명제 42 2.5 추론2.5 추론 Discrete Mathematics Chapter 2. 논리와 명제 43 2.5 추론2.5 추론 Discrete Mathematics Chapter 2. 논리와 명제 44 2.5 추론2.5 추론 Discrete Mathematics Chapter 2. 논리와 명제 45 2.5 추론2.5 추론 Discrete Mathematics Chapter 2. 논리와 명제 46 2.5 추론2.5 추론 가장 많이 사용되고 잘 알려진 3가지 논리 법칙 (a) 긍정 법칙 : p, p → q├ q (b) 부정 법칙 : ~q, p → q├ ~p (c) 삼단 법칙 : p → q, q → r├ p → r Discrete Mathematics Chapter 2. 논리와 명제 47 2.5 추론2.5 추론 Discrete Mathematics Chapter 2. 논리와 명제 48 2.5 추론2.5 추론 Discrete Mathematics Chapter 2. 논리와 명제 49 2.5 추론2.5 추론 . 추론법칙 . 삼단논법: 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: 그러므로 땅이 젖지 않았을 것이다 (물을 뿌려서 땅이 젖은 경우가 있다 ) 2.6 술어논리2.6 술어논리 Discrete Mathematics Chapter 2. 논리와 명제 51 2.6 술어논리2.6 술어논리 . 명제술어 : 주어와 술어로 구분하여 서술되는 명제 . 술어논리 : 명제 술어에 대한 논리 . 객체 : x 명제 : p(x) x 에 대한 명제술어 “x is greater than 3.” 변수(=객체)(variable) = x 술어(predicate) = P P(x) = “x is greater than 3.” 명제함수(propositional function) 2.6 술어논리2.6 술어논리 Discrete Mathematics Chapter 2. 논리와 명제 53 2.6 술어논리2.6 술어논리 명제 함수를 명제로 만드는 방법 1. 변수에 특정 값을 할당하는 방법 2. 한정(quantification) 을 적용하는 방법 변수에 특정 값을 할당하는 방법 . P(x) = “x > 3” . 만일 x = 4라면 P(x)는 true가 되고 , x = 2 라면 P(x)는 false가 된다 . Quantification 을 적용하는 방법 . P(x) =“x > 3” . x의 정의역(domain)이“ 4 이상인 모든 실수”라면 , P(x)는 true가 된다 . 54 2.6 술어논리2.6 술어논리 Discrete Mathematics Chapter 2. 논리와 명제 55 2.6 술어논리2.6 술어논리 Discrete Mathematics Chapter 2. 논리와 명제 56 2.6 술어논리2.6 술어논리 . 전체 한정자 (universal quantifier) . 변수 x가가질수있는 모든값에대하여 p(x) 의 전체 한정은 다음과 같이 나타내는 명제를 말한다 . ‘모든 x에 대하여 p(x) 는 참이다(=성립한다)’ . 전체 한정자의 기호는 ‘.’로 표기하고 , p(x) 에 대한 전체 한정은 . x p(x) 로 나타낸다 . . 읽기: “for all x in P(x)” 혹은 “for every x in P(x)” . . x p(x) 이참이되기 위한필요충분 조건은 술어 p(x)가 x의 전체 집합 U에 대하여 성립하여야 한다 . . Domain 의 모든 값을 x1, x2, …, xn으로 나열할 수 있다면 , .xP(x)는 다음과 동일하다 . P(x1) . P(x2) . .... . P(xn) 57 2.6 술어논리2.6 술어논리 Discrete Mathematics Chapter 2. 논리와 명제 58 2.6 술어논리2.6 술어논리 . 존재 한정자 (existential quantifier) . 변수 x가 가질수 있는 모든 값에 대하여 p(x) 의 존재 한정은 다음과 같이 나타내는 명제를 말한다. ‘어떤 x에 대하여 p(x) 가 참인 x가 존재한다 ’ ‘p(x) 가 성립하는 x가 존재한다 ’ . 존재 수량자의 기호는 ‘.’로 표기하고 , p(x)에 대한 존재 한정은 . x p(x) 로 나타낸다. . 읽기: “for some x in P(x)” 혹은 “there is an x such that P(x)” . . x p(x) 이 참이 되기 위한 필요 충분 조건은 전체 집합 U안에 p(x)를 만족시키는 x가 적어도 한 개 존재하여야 한다. . Domain 의 모든 값을 x1, x2, …, xn으로 나열할 수 있다면 , .xP(x)는 다음과 동일하다 . P(x1) . P(x2) . .... . P(xn) 59 2.6 술어논리2.6 술어논리 Discrete Mathematics Chapter 2. 논리와 명제 60 2.6 술어논리2.6 술어논리 Discrete Mathematics Chapter 2. 논리와 명제 61 2.6 술어논리2.6 술어논리 Discrete Mathematics Chapter 2. 논리와 명제 62 2.7 논리용언어-Prolog 2.7 논리용언어-Prolog . 프롤로그 (Prolog) 논리와 명제를 컴퓨터 프로그램을 통해 보다 빠르고 쉽게 구현할 수 있는 프로그래밍 언어임 . Prolog 의 특징 . 사실(fact), 규칙(rule), 질문(question) 들로 프로그램이 구성됨 . 사실과 규칙들을 데이터베이스로 구성하였으며 , 프로그램 실행은 자료에 대한 질문의 응답 형식임 . 대화식의 명령 방식을 사용함 . 사용자의 질문에 답하기 위해 추론 엔진 (inference engine) 을사 용하고 사용자가 사실과 규칙 등을 입력함 Discrete Mathematics Chapter 2. 논리와 명제 63 2.7 논리용언어-Prolog 2.7 논리용언어-Prolog . Prolog 프로그램 . 우리가 쉽게 접하기 드문 색다른 형태의 언어임 . 논리적 연산과 인공지능 분야에서의 논리 판단을 위한 프로그램의 구현에 있어서 매우 중요한 역할을 담당함 . 사실과 규칙들만 기술하고 프로그램의 실행 순서는 명시하지 않으 므로‘제 5세대 컴퓨터 언어’라고도 함 Discrete Mathematics Chapter 2. 논리와 명제 64 2.7 논리용언어-Prolog 2.7 논리용언어-Prolog Discrete Mathematics Chapter 2. 논리와 명제 65 요약요약 Discrete Mathematics Chapter 2. 논리와 명제 66 요약요약 Discrete Mathematics Chapter 2. 논리와 명제 67 요약요약 Discrete Mathematics Chapter 2. 논리와 명제 68 요약요약 Discrete Mathematics Chapter 2. 논리와 명제 69 응용응용 . 논리 분야 응용들 . 알고리즘의 설계나 증명 . 디지털 논리 회로 설계 . 논리 프로그램 관련 분야 . 관계형 데이터베이스 이론 . 오토마타와 계산 이론 . 인공지능 등 다양한 분야에 필요한 이론적 기반을 제공함 Discrete Mathematics Chapter 2. 논리와 명제 70 Some Alternative Notations Some Alternative Notations Logic and Bit Operations Logic and Bit Operations 비트(bit)란 binary digit(이진수)에서 따온 단어임 . 비트는 1(true) 과 0(false) 의 값을 가짐 . True 혹은 false 를 값으로 갖는 변수 (variable)를 Boolean variable 이라 함 Bit operator(OR, AND, XOR) 의 truth table P q p.q p.q p.q 0 0 0 0 0 0 1 1 0 1 1 0 1 0 1 1 1 1 1 0 Bit operation 의 예제 01 1011 0110 11 0001 1101 11 1011 1111 bitwise OR 01 0001 0100 bitwise AND 10 1010 1011 bitwise XOR 72
'myPPT' 카테고리의 다른 글
논리의 유형과 논증으로 무엇을 할 수 있는가? (4) | 2013.04.06 |
---|---|
이자율 변동:채권 및 화폐시장에 대한 수요 공급 모형,일본 사례 (0) | 2013.04.05 |
총수요와 총공급 균형:거시경제 정책,인플레이션과 동태적 관계 (2) | 2013.04.04 |
Speed to Market 시장에서 스피드 높이기 위해: ZARA 사례 (0) | 2013.03.30 |
금융시스템과 위기:거래비용문제,역선택,도덕적 해이,정보비대칭 문제 (0) | 2013.03.30 |