이산수학 담당교수 : 박미경 1.

Presentation on theme: "이산수학 담당교수 : 박미경 1."— Presentation transcript:

1 이산수학 담당교수 : 박미경 1

2 1주차 논리와 명제 1차시: 논리의 기본 개념과 논리연산자
1주차 논리와 명제 1차시: 논리의 기본 개념과 논리연산자

3 들어가기_학습목표 및 내용 학습내용 학습목표 1. 논리와 명제의 기본개념 2. 논리연산 3. 항진명제와 모순명제
1. 논리와 명제의 기본개념을 이해한다. 2. 논리연산을 이해한다. 3. 항진명제와 모순명제를 이해한다.

4 1. 논리와 명제 논리(logic) : 주어진 문제를 객관적으로 명확하게, 그리고 사고의 법칙을 체계적으로 추구하여 분석하는지의 여부로 결정된다. 논리의 응용분야 알고리즘의 설계나 증명 디지털 논리회로의 설계 논리 프로그램 관련 분야 관계형 데이터베이스 이론 오토마타와 계산이론 인공지능 등

5 1. 논리와 명제 논리는 크게 명제논리(propositional logic)와 술어논리(predicate logic)로 구분된다. 명제논리 : 주어진 명제를 주어와 술어로 구분하지 않고 전체를 하나의 식으로 처리하여 참 또는 거짓을 판별하는 법칙을 다루는 논리 술어논리 :주어진 명제를 주어와 술어로 구분하여 참 또는 거짓을 판별하는 법칙을 다루는 논리

6 1. 논리와 명제 참(true) 또는 거짓(false)을 명확히 구분할 수 있는 문장(statement)이나
수식을 명제(proposition)라고 한다. 명제(proposition) 일반적으로 영어 소문자(p,q,r,…)로 나타냄 진리값(truth value) 명제의 진리값이 참이면 T(true), 진리값이 거짓이면 F(false)로 나타냄

7 1. 논리와 명제

8 1. 논리와 명제

9 2. 논리 연산 2 논리연산자(logical operators) : 단순명제를 연결시켜주는 역할을 하는 ∨,∧,~ 과 같은 연결자를 의미 합성명제의 진리값은 그 명제를 구성하는 단순명제의 진리값과 논리연산자의 특성에 따라 값이 정해진다. 따라서 진리표(truth table)를 사용한다. 단순명제의 진리값은 그 명제가 참이냐 거짓이냐에 따라 T 또는 F로 나타낸다.

10 2. 논리연산

11 2. 논리연산

12 2. 논리연산

13 2. 논리연산

14 2. 논리연산

15 2. 논리연산 명제 p, q에 대해 ~q∧p의 집리값을 구하여라.
합성명제의 진리값을 구할 때는 전체명제의 진리값을 한 번에 구하는 것 보다 각 부분의 진리값을 구한 뒤 전체 합성명제의 진리값을 구하는 편이 낫다. 따라서 ~q∧p의 진리값을 구하는 진리표를 작성하려면 먼저 ~q의 진리값을 구한 뒤 ~q∧p의 진리값을 구한다.

16 2. 논리 연산 진리표(Truth Table)를 작성하는 방법
논리기호 ∨, ∧, ~등을 여러 번 사용하여 합성명제를 구성할 경우 합성명제 P(p, q, r, …)의 부분명제 p, q, r 등을 변수(variable)라고 하고, 합성명제의 진리값을 각 변수들의 진리값에 의해 구할 수 있다. 진리표(Truth Table)를 작성하는 방법 진리표의 처음 n개의 열에 단순 명제 변수로 표제를 붙인다. 주어진 합성명제를 구성하는 중간 단계의 합성명제 각각에 대하여 하나의 열을 그 다음에 첨가하여 결국 주어진 합성명제에 대한 열까지 포함시킨다. 처음 n 개의 표제 밑에 합성명제의 단순 명제에 대한 2n개의 가능한 n-순서쌍 (n-tuple) 진리값을 나열한다. 각 n-순서쌍을 각각의 행에 나열한다. 나머지 열에 진리값을 계산하여 기입한다.

17 2. 논리 연산 합성명제 (p∧q)∨(~p)의 진리표를 만들어라.
사용된 단순명제의 수가 2개이므로, 진리표는 22, 즉 4행으로 구성된다. 처음 2개의 열에는 단순명제 p와 q가 취할 수 있는 모든 가능한 진리값의 순서쌍을 나열한다. 나머지 열의 바닥에 쓰인 번호가 해당 열이 채워진 순서를 나타낸다.

18 2. 논리연산

19 2. 논리연산

20 2. 논리연산

21 2. 논리연산

22 2. 논리연산

23 2. 논리연산 명제 p, q에 대하여 의 진리값을 구하여라. 진리표를 이용하여 명제의 진리값을 구한다.

24 2. 논리연산

25 2. 논리연산

26 2. 논리연산 명제 p, q에 대하여 (p → q)∧(q → p)의 진리표을 구하여라.
(p → q)∧(q → p)의 진리표를 작성하기 위해 먼저 (p → q)와(q → p)의 진리값을 각각 구한다. 주어진 합성명제 (p → q)∧(q → p)는 함축 (p → q)와 (q → p)를 논리곱으로 연결하고 있다. 논리곱은 각각의 명제가 모두 참일 때 진리값이 참이다. 결국 다음과 같은 진리표를 작성할 수 있다.

27 2. 논리연산

28 2. 논리연산

29 2. 논리연산 명제 p, q가 주어졌을 때 (p→q)↔(q↔p)의 진리표를 구하여라.
구한다.

30 2. 논리연산 역(comverse), 이(inverse), 대우(contraposition)

31 2. 논리연산

32 2. 논리연산

33 3. 항진명제와 모순명제 2

34 3. 항진명제와 모순명제 명제 p와 항진 명제 t에 대해 다음 명제들의 진리값을 구하여라.
(1) p∧t (2)~p∨t (3) ~p→~t 항진명제 t는 진리값이 항상 참인 명제이다. 진리표를 이용하여 주어진 명제의 진리값을 구한다.

35 3. 항진명제와 모순명제

36 3. 항진명제와 모순명제 다음 명제의 진리값을 구하여라. (1) [p∧(p → q)] → q (2)~p↔(p∨~p)
진리표를 이용하여 주어진 명제의 진리값을 구한다.

37 3. 항진명제와 모순명제 진리표를 이용하여 주어진 명제의 진리값을 구한다.
주어진 명제의 진리값이 모두 참이 아니므로 항진명제가 아니다.

38 생각해보기 생각해보기 주제 38

39 생각해보기 교수님 의견 39

40 평가하기_퀴즈 1 다음 문장 중에서 명제가 아닌 것을 모두 고르시오. 답 해설 1, 3 x + y = 5
혜영이의 키는 162Cm이다. 과제물을 빨리 제출하시오. 9는 3의 배수이다. 답 1, 3 해설 명제는 참이거나 혹은 거짓인 단언 혹은 단정적인 문장을 말합니다. 단, 참가 거짓이 모두 될 수 있는 단언은 명제에서 제외합니다. 따라서 ①은 x와y에 주어진 값을 알 수 없기 때문에 참과 거짓을 판별할 수 없는 문장이므로 명제가 아닙니다. ②는 명제이다. 이 문장이 참인지 거짓인지는 실제 혜영이의 키를 재었을 때 162Cm이면 명제는 참이고 그렇지 않으면 거짓인 명제라고 할 수 있기 때문이다. ③은 명제가 아니라 명령문 입니다. ④는 참인 문장이므로 명제이다.

41 평가하기_퀴즈 2 답 2 해설

42 평가하기_퀴즈 3 답 4 해설

43 평가하기_퀴즈 4 답 1 해설

44 평가하기_퀴즈 4 해설

45 정리하기 1. 논리와 명제 논리(Logic)란 인간이 어떻게 사고하는가를 표현하는 사고의 규칙을 말한다. 명제(proposition)는 논리의 기초이며, 어떤 사고를 나타내는 문장 중에서 참(true)이나 거짓(false)을 객관적이고 명확하게 구분할 수 있는 문장이나 수학적 사실을 말한다 일반적으로 명제는 영어 소문자(p, q, r, …)로 나타낸다. 명제의 진리값이 참이면 T(true)로 나타내고, 진리값이 거짓이면 F(false)로 나타낸다. 이때 . 명제를 참 또는 거짓으로 나타내는 값을 진리값(truth value)이라고 한다. 2. 논리 연산 하나의 문장이나 식으로 구성되어 있는 명제를 단순 명제(simple proposition)이라 하고, 여러 개의 단순 명제들이 논리 연산자들로 연결되어 만들어진 명제를 합성 명제(composition proposition)라고 한다. 단순명제들을 연결시켜주는 역할을 하는 V, ^, ~과 같은 연결자들을 논리 연산자(logical operators)라고 한다. 합성 명제의 진리값은 그 명제를 구성하는 단순 명제의 진리값과 논리 연산자의 특성에 따라 값이 정해진다.

46 정리하기 3. 항진명제와 모순명제 합성명제에서 그 명제를 구성하는 단순명제들의 집리값에 관계없이 그 합성 명제의 진리값이 항상 참(T)의 값을 가질 때 그 명제를 항진명제(tautology)라고 한다. 이와는 반대로 합성명제의 진리값이 항상 거짓(F)의 값을 가질 때 그 명제를 모순 명제(Contradiction)라고 한다.

47 정리하기_차시 예고 논리적 동치관계 논리적 동치를 이용하여 명제를 단순화하는 방법을 배운다.
논의영역을 통해 명제함수의 참과 거짓을 판별한다.