이산수학 () 1.3 술어와한정기호 (Predicates and Quantifiers) 2006 년봄학기 문양세강원대학교컴퓨터과학과 술어 (Predicate), 명제함수 (Propositional Function) 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개의변수 x 1, x 2, x 3,, x n 을포함하는명제함수는 P(x 1, x 2, x 3,, x n ) 으로표기한다. Page 2 1
한정기호 (Quantifiers) 명제함수를명제로만드는방법 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가된다. The collection of values that a variable x can take is called x s domain or universal of discourse. Page 3 Universal Quantifier (1/3) 정의 P(x) 의 Universal Quantifier란 정의역 (domain) 에속하는모든값 x에대하여p(x) 가참이다. 라는명제이다. Universal Quantifier 의표기및읽기 표기 : xp(x) 읽기 : for all x in P(x) 혹은 for every x in P(x) Page 4 2
Universal Quantifier (2/3) Universal Quantifier 의개념적이해 Domain의모든값을x 1, x 2,, x n 으로나열할수있다면, xp(x) 는다음과동일하다. P(x 1 ) P(x 2 )... P(x n ) Universal Quantifier 의사용예 예 1: P(x) 가 x < 2 이고 domain 이모든실수라할때, xp(x) 의진리값은? 답 : 거짓 예 2: Q(x) 가 x 2 0 이고 domain 이모든실수라할때, xq(x) 의진리값은? 답 : 참 Page 5 Universal Quantifier (3/3) 반례 (counterexample) P(x) 가명제함수라할때, xp(x) 가거짓임을보이기위해서는 domain에속하는값중단지하나의값이라도 P(x) 를거짓으로만드는예를보이면된다. 이와같이 P(x) 를거짓으로만드는예를반례 (counterexample) 이라한다. Counterexample 사용의예 P(x) 가 x 2 > 0 이고 domain이모든실수라할때, xp(x) 의 counterexample은? x = 0이면 x 2 = 0이되어, x 2 > 0를만족하지않는다. 따라서, xp(x) 는거짓이되고, 이때 x = 0을 counterexample이라한다. Page 6 3
Existential Quantifier (1/2) 정의 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) Page 7 Existential Quantifier (2/2) Existential Quantifier 의개념적이해 Domain의모든값을x 1, x 2,, x n 으로나열할수있다면, xp(x) 는다음과동일하다. P(x 1 ) P(x 2 )... P(x n ) Existential Quantifier 의사용예 예 1: P(x) 가 x > 3 이고 domain이모든실수라할때, xp(x) 의진리값은? 답 : 참 예 2: Q(x) 가 x = x+1 이고 domain이모든실수라할때, xq(x) 의진리값은? 답 : 거짓 Page 8 4
Quantifier 개념요약 Statement xp(x) xp(x) When true? P(x) is true for every x. There is an x for which P(x) is true. When false? There is an x for which P(x) is false. P(x) is false for every x. Page 9 Binding Variables 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 Page 10 5
Negation with Quantifiers (1/2) 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) Page 11 Negation with Quantifiers (2/2) Negation 관련법칙 xp(x) x P(x) xp(x) x P(x) Negation 관련예제 x(x 2 > x) 의부정 x(x 2 > x) x (x 2 > x) x(x 2 x) x(x 2 = 2) 의부정 x(x 2 = 2) x (x 2 = 2) x(x 2 2) Page 12 6