이산수학(Discrete Mathematics)  술어와 한정기호 (Predicates and Quantifiers) 2013년 봄학기 강원대학교 컴퓨터과학전공 문양세

“x is greater than 3.” 술어(Predicate), 명제 함수(Propositional Function) 1.3 Predicates and Quantifiers “x is greater than 3.” 변수(variable) = x 술어(predicate) = P 명제 함수 (propositional function) P(x) = “x is greater than 3.” Q(x, y) = “x = y + 3” R(x, y, z) = “x + y = z” 일반적으로 n개의 변수 x1, x2, x3, …, xn을 포함하는 명제 함수는 P(x1, x2, x3, …, xn) 으로 표기한다.

한정기호(Quantifiers) 명제 함수를 명제로 만드는 방법 (1) 변수에 특정 값을 할당하는 방법 1.3 Predicates and Quantifiers 명제 함수를 명제로 만드는 방법 1. 변수에 특정 값을 할당하는 방법 2. 한정(quantification)을 적용하는 방법 (1) 변수에 특정 값을 할당하는 방법 P(x) = “x > 3” 만일 x = 4라면 P(x)는 true가 되고, x = 2라면 P(x)는 false가 된다. (2) Quantification을 적용하는 방법 x의 정의역(domain)이 “4 이상인 모든 실수”라면, P(x)는 true가 된다. The collection of values that a variable x can take is called x’s domain or universal of discourse.

Universal Quantifier  (1/3) 1.3 Predicates and Quantifiers 정의 P(x)의 Universal Quantifier란 “정의역(domain)에 속하는 모든 값 x에 대하여 P(x)가 참이다.”라는 명제이다. Universal Quantifier의 표기 및 읽기 표기: xP(x) 읽기: “for all x in P(x)” 혹은 “for every x in P(x)”

Universal Quantifier  (2/3) 1.3 Predicates and Quantifiers Universal Quantifier의 개념적 이해 Domain의 모든 값을 x1, x2, …, xn으로 나열할 수 있다면, xP(x)는 다음과 동일하다. P(x1)  P(x2)  ....  P(xn) Universal Quantifier의 사용 예 예 1: P(x)가 “x < 2”이고 domain이 모든 실수라 할 때, xP(x)의 진리 값은?  거짓 예 2: Q(x)가 “x2  0”이고 domain이 모든 실수라 할 때, xQ(x)의 진리 값은?  참

Universal Quantifier  (3/3) 1.3 Predicates and Quantifiers 반례(counterexample) P(x)가 명제 함수라 할 때, xP(x)가 거짓임을 보이기 위해서는 domain에 속하는 값 중 단지 하나의 값이라도 P(x)를 거짓으로 만드는 예를 보이면 된다. 이와 같이 P(x)를 거짓으로 만드는 예를 반례(counterexample)이라 한다. Counterexample 사용의 예 P(x)가 “x2 > 0”이고 domain이 모든 실수라 할 때, xP(x)의 counterexample은? x = 0이면 x2 = 0이 되어, x2 > 0를 만족하지 않는다. 따라서, xP(x)는 거짓이 되고, 이때 x = 0을 counterexample이라 한다.

Existential Quantifier  (1/2) 1.3 Predicates and Quantifiers 정의 P(x)의 Existential Quantifier란 “Domain에 속하는 적어도 하나의 값 x에 대하여 P(x)가 참이다.”라는 명제이다. Existential Quantifier의 표기 및 읽기 표기: xP(x) 읽기: “for some x in P(x)” 혹은 “there is an x such that P(x)”

Existential Quantifier  (2/2) 1.3 Predicates and Quantifiers Existential Quantifier의 개념적 이해 Domain의 모든 값을 x1, x2, …, xn으로 나열할 수 있다면, xP(x)는 다음과 동일하다. P(x1)  P(x2)  ....  P(xn) Existential Quantifier의 사용 예 예 1: P(x)가 “x > 3”이고 domain이 모든 실수라 할 때, xP(x)의 진리 값은?  참 예 2: Q(x)가 “x = x+1”이고 domain이 모든 실수라 할 때, xQ(x)의 진리 값은?  거짓

Quantifier 개념 요약 Statement When true? When false? xP(x) 1.3 Predicates and Quantifiers Statement When true? When false? xP(x) P(x) is true for every x. There is an x for which P(x) is false. xP(x) There is an x for which P(x) is true. P(x) is false for every x.

x(P(x)Q(x))  xR(x) Binding Variables 1.3 Predicates and Quantifiers Binding Variables vs. Free Variables 변수 x에 quantifier가 적용되거나 특정 값이 할당되면, x를 binding variable이라 한다. 변수 x에 quantifier가 적용되지 않거나 특정 값이 할당되지 않았으면, x를 free variable이라 한다. Quantifier가 적용되는 부분을 quantifier의 범위(scope)라 한다. binding variable xP(x, y) free variable x(P(x)Q(x))  xR(x) scope of x scope of x

Negation with Quantifiers (1/2) 1.3 Predicates and Quantifiers Negation 예제 x = student, P(x) = “x in the class has taken a course in calculus.” xP(x) = “Every student in the class has taken a course in calculus.” ¬xP(x) = “It is not the case that every student in the class has taken a course in calculus.” = “There is a student in the class who has not taken a course in calculus.” = x¬P(x)

Negation with Quantifiers (2/2) 1.3 Predicates and Quantifiers Negation 관련 법칙 Negation 관련 예제 x(x2 > x)의 부정  ¬x(x2 > x)  x¬(x2 > x)  x(x2  x) x(x2 = 2)의 부정  ¬x(x2 = 2)  x¬(x2 = 2)  x(x2  2) ¬xP(x)  x¬P(x) ¬xP(x)  x¬P(x)