주요 내용 명제 조건 명제와 쌍조건 명제 술어와 한정사 논리적 기호로 문장을 표현

명제(proposition) 명제(proposition) 참(true) 혹은 거짓(false)을 판명할 수 있는 선언적인 문장 (declarative statement)을 명제라고 한다. 예: “어제 비가 내렸다.” (명제) “물은 100도에서 끊는다.”(명제) “1 + 2 = 4” (명제) “지금 시간이 몇 시에요?” (명제가 아님) “내일까지 레포트를 내세요.” (명제가 아님) “x+1 = 2” (명제가 아님)

명제의 조합 다른 명제의 조합으로 만들어지는 명제를 복합 명제(compound proposition)라고 한다. 명제의 합(disjunction): p  q 두 명제 p와 q 중 둘 중 하나 이상이 참일 때 참이고, 둘 다 거짓일 때 거짓이 되는 명제이다. 명제의 곱(conjunction): p  q 두 명제 p, q가 모두 참일 때 참이고, 명제 p와 q 중 하나가 거짓이거나 p, q가 모두 거짓일 때 거짓인 명제다. 명제의 부정(negation): p p가 거짓일 때 참이고 p가 참일 때 거짓인 명제이다.

진리표(truth table) 진리표는 복합 명제를 표시하는데 유용한 방법이다. p q p  q p q p  q p p T T T T T T T F T F F T F T F T F T F F T T F F F F F F

주요 내용 명제 조건 명제와 쌍조건 명제 술어와 한정사 논리적 기호로 문장을 표현

조건 명제(implication) p  q 조건 명제: p  q (if p, then q) T T T 가정(조건) 결론(결과) Hypothesis conclusion Antecedent consequence premise T F F F T T F F T

예제1: “네가 시험에서 100점을 받으면, 성적 A를 받는다.” p: 네가 시험에서 100점을 받는다. q: 네가 성적 A를 받는다. <주의> 조건 명제의 진위에서 이해하기 힘든 부분은 p가 거짓이고 q가 참일 때 결과는 참이 된다는 것이다. 위 예제에서 “네가 시험에서 100점을 받지 않으면, 성적 A를 받는다.” 라는 명제의 결과가 참이 된다는 것이다. 따라서 조건 명제에서 주의할 점은 이 명제는 우리의 언어 사용에서의 원인과 결과(cause-and-effect)의 논리로 해석하지 말고 조건 명제를 정의하는 진리표에 의해서 이 명제의 수학적 논리를 이해해야 한다는 점이다.

예제2: “해가 동쪽에서 뜨면, 4 + 4 = 8이다.” p: 해가 동쪽에서 뜬다. q: 4+4=8 이 조건 명제는 참이다. 그리고 p와 q 사이에는 우리가 일상 언어의 조건문에서 전제하는 원인과 결과의 상관 관계는 없다. 예제3: “해가 서쪽에서 뜨면, 4 + 4 = 10이다.” p: 해가 서쪽에서 뜬다. q: 4+4=10 이 조건 명제는 진리표에 의해서 참이다. 조건 명제의 진위는 진리표의 정의에 의해서 결정되기 때문이다.

쌍조건(biconditional) 명제 쌍조건 명제: p  q 명제 p와 q가 모두 참이거나 모두 거짓일 때 참이고 하나가 참이고 하나가 거짓일 때 거짓인 명제 p  q p q T T T T F F F T F F F T

예제: 한 섬에 두 개의 부족이 있다고 하자. 그 중 한 부족 사람은 항상 진실만을 말하고, 다른 한 부족 사람은 항상 거짓말만 한다고 한다. 이때 만일 당신이 그 섬에 가서 그 섬에 금이 있는지를 물었을 때 한 사람이 다음과 같이 말했다고 하자. “내가 항상 진실만을 말하는 것과 섬에 금이 있다는 사실은 필요충분(if and only if) 조건이다.” 이 문장을 쌍조건 문장으로 생각하면, 쌍조건 명제의 성질에 의하여 이 문장을 말한 사람이 어느 부족 사람이든지 섬에는 금이 있다는 사실을 유추할 수 있다. p: “내가 항상 진실만을 말한다.” q: “섬에 금이 있다.”라는 명제를 r: “내가 항상 진실만을 말하는 것과 섬에 금이 있다는 사실은 필요충분(if and only if) 조건이다.”

예제(계속) 만일 그 사람이 진실만을 말하는 부족 사람이라고 하자. 그러면 명제 r은 참이 되고, 명제 p도 역시 참이다. 따라서 명제 q도 쌍조건 명제의 성질에 의하여 참이어야 한다. 만일 그 사람이 거짓을 말하는 부족 사람이라고 하자. 이 경우에는 명제 p는 거짓이 되고, 명제 r도 거짓이 된다. 따라서 명제 q는 쌍조건 명제의 성질에 의하여 참이어야 한다. 따라서 어떤 경우에도 명제 q는 참이므로 섬에는 금이 있다.

필요 충분 조건 p  q 에서 p가 참이고 q가 참이면, q를 p이기위한 필요 조건(necessary condition), 충분 조건(sufficient condition)이라고 한다. p  q 와 동시에 q  p 가 성립하면 p는 q이기 위한 필요 충분 조건 이라고 한다. 이 경우 p와 q는 동치(equivalence)라고 한다. A와 B의 집합 관계가 A  B이면 B는 A이기 위한 필요 조건, A는 B이기 위한 충분 조건이다.

예제1: A; 정삼각형, B:이등변 삼각형 B는 A이기 위한 필요 조건이고, A는 B이기 위한 충분 조건이다. 예제2: x ≥1 이고 y ≥1 인 것은 x + y ≥2 이기 위한 ( ) 조건이다. 답: 충분 조건

역, 이, 대우 명제 p  q가 있을 때, 역(converse): q  p 이(contrapositive): p  q 대우(inverse) q  p

복합 명제와 값 복합 명제는 원자 명제(atomic proposition)들이 조합되어 생성될 수 있다. 복합 명제의 값은 진리표로 구할 수 있다. 예: ((p  q)v(p  q))  q p q p  q p  q (p  q)v(p  q) ((p  q)v(p  q))  q T F

두 명제의 진리표의 값이 같으면 두 명제는 동일한 명제이다. 예제: 다음 두 명제가 같음을 보여라. ((p  q)v(p  r))  s, ((p  (q  r))  s

주요 내용 명제 조건 명제와 쌍조건 명제 술어와 한정사 논리적 기호로 문장을 표현

술어(predicate) 문장(statement)은 주어(subject)와 술어(predicate)로 구성되어 있다. “3은 6보다 작다.” 주어 술어 명제는 흔히 변수를 포함한 함수로서 표현하기도 한다. p(x) : x+2=3 p(x)는 주어 x를 변수로 하여 함수로 표현한 것이다. 이 때 x의 값에 따라서 이 명제의 진위가 결정된다.

한정사(quantifier) 명제 함수 p(x)는 한정사를 사용하여 표현할 수 있다. 한정사에는 다음의 두 가지 종류가 존재한다. 전체 한정(universal quantification) x가 갖는 모든 값에 대해서 p(x)가 참인 명제를 p(x)의 전체 한정이라고 한다. 기호로는 x p(x) 로 표시한다.

예제1: p(x) : x2+2x+1  0, x의 정의 구역: 실수 그러면 x p(x)는 참이다. 예제2: p(x) : x2+2x+1 > 0, x의 정의 구역: 실수 그러면 x p(x)는 거짓이다. (x=-1이면 p(x)는 거짓이기 때문이다.)

존재 한정 존재 한정(existential quantification) x가 갖는 값 중에서 p(x)가 참이 되게 하는 x가 존재하는 명제를 p(x)의 존재 한정이라고 한다. 기호로는 x p(x) 로 표시한다.

예제1: p(x) : x2+1  1, x의 정의 구역: 실수 그러면 x p(x)는 참이다.(x=0일 때 p(x)가 참이 되기 때문) 예제2: p(x) : x2+1 < 1, x의 정의 구역: 실수 그러면 x p(x)는 거짓이다. (p(x)가 참이 되는 x의 값이 x의 정의 구역에서는 존재하지 않는다.)

한정사를 이용한 명제의 부정 “모든 컴퓨터학과 학생들은 이산 수학을 듣는다.” 이것을 한정사를 이용하여 표현하면, p(x): x는 이산 수학을 듣는다. x의 정의 구역: 모든 컴퓨터학과 학생들  x p(x) 이 문장의 부정은 “컴퓨터학과 학생이면서 이산 수학을 듣지 않는 학생도 있다.”  x p(x) = x p(x)

“컴퓨터 학과 학생들 중 이산 수학을 듣는 사람이 존재한다.” p(x): “x는 이산 수학을 듣는다.” x의 정의 구역: 컴퓨터 학과 학생들  x p(x) 이 문장의 부정은, “모든 컴퓨터 학과 학생은 이산 수학을 듣지 않는다.”   x p(x) = x p(x)

주요 내용 명제 조건 명제와 쌍조건 명제 술어와 한정사 논리적 기호로 문장을 표현

문장의 논리적 표현 주어진 문장을 논리적 기호로 표현하는 것은 수학이나, 논리 프로그래밍, 인공 지능 등의 분야에서 매우 중요하다. 지금까지 설명한 명제 함수, 한정사는 문장을 논리적 기호로 표현하는데 사용될 수 있다. 예제1: “이 클라스의 모든 학생은 C 언어 인증 시험을 통과하였다.” 함수 C(x): “학생 x는 C언어 인증 시험을 통과하였다.” x의 정의 구역: 이 클라스의 학생들  x C(x)

예제2: 예제1의 문장은 다음과 같이 쓸 수 있다. “모든 사람 x에 대하여, 만일 x가 이 클라스의 학생이면 x는 C언어 인증 시험을 통과하였다.” 함수 S(x): “x가 이 클라스의 학생이다.” 함수 C(x): “학생 x는 C언어 인증 시험을 통과하였다.” x의 정의 구역: 이 클라스의 학생들  x (S(x)  C(x)) 예제3: 위의 예제의 문장을 다음과 같은 함수를 정의하여 표현하면, 함수 Q(x,y) : “사람 x가 y를 통과하였다.”  x (S(x)  Q(x, C언어 인증시험))

예제4: “이 클라스를 듣는 어떤 학생은 독일을 방문한 적이 있다.” 이 문장은 다음과 같이 다시 쓸 수 있다. “이 클라스에는 x라는 학생이 있는데 그 x라는 학생은 독일 을 방문한 적이 있다.” 함수 D(x): “x는 독일을 방문한 적이 있다.” 함수 S(x): “x가 이 클라스의 학생이다.” x의 정의 구역: 이 클라스의 학생들  x (S(x)  D(x))

중첩 한정사 하나의 한정사의 범위 안에 다른 한정사가 존재하는 중첩 한정사를 사용할 수 있다. 예 x y (x+y=0) 예제1: “모든 실수에 대해서 x+y=y+x가 성립한다.(교환 법칙)” 이 명제는 다음과 같이 표현할 수 있다. x  y (x+y=y+x)

예제2: 덧셈에 있어서 결합 법칙은 다음과 같이 표현할 수 있다. x  y  z (x+(y+z))=((x+y)+z) 예제3: 논리식 x  y ((x>0)  (y<0)  (xy<0)) “모든 실수 x,y에 대해서 x가 양수이고 y가 음수이면, x와 y의 곱은 음수이다.”

예제4: 논리식 x (M(x) V y(M(y)  F(x,y)))을 문장으로 표현하라. M(x): “x가 MP3 폰을 가지고 있다.” F(x,y): “x와 y가 친구이다.” x,y의 정의 구역: 한 학교의 학생들 “한 학교의 모든 학생 x에 대해서 x가 MP3 폰을 가지고 있거나, x의 친구 y가 mp3 폰을 가지고 있다.” 예제5: “전 세계 모든 항공사의 비행기를 타 본 사람이 존재한다.” p(x,f): “x가 비행기 f를 탄다.” Q(f,a): “비행기 f가 a 항공사의 비행기이다.” x: 모든 사람의 집합, a: 모든 항공사의 집합, f: 모든 비행기의 집합  x a f(p(x,f)  Q(f,a))

예제6: “한 사람이 남자이면서 부모이면, 이 사람은 어떤 사람의 아버지이다.” 이 문장은 다음과 같이 변형할 수 있다. “모든 사람 x에 대해서, 만일 x가 남자이고 x가 부모이면, y의 아버지가 x인 y가 존재한다.” M(x): “x가 남자이다.” P(x): “x가 부모이다.” F(x,y):”x가 y의 아버지이다.”  x ((M(x)  P(x))  y F(x,y)) 또는  x y ((M(x)  P(x))  F(x,y))