2012 년 봄학기 강원대학교 컴퓨터과학전공 문양세 이산수학 (Discrete Mathematics)  중첩된 한정기호 (Nested Quantifiers)

Discrete Mathematics by Yang-Sae Moon Page 2 Nested Quantifiers  Statements (1/3) Variable x 와 y 의 domain 이 실수 (all real numbers) 라 했을 때,  x  y(x + y = y + x) 를 번역하면, “For every real number x and for every real number y, x + y = y + x.” 이고, 이는 실수의 덧셈에 있어서 교환법칙을 의미한다.  x  y(x + y = 0) 를 번역하면, “For every real number x, there is a real number y such that x + y = 0.” ( 항등원과 역원을 의미한다.)  x  y  z(x + (y + z) = (x + y) + z) 를 번역하면, “For every real number x, for every real number y, and for every real number z, x + (y + z) = (x + y) + z.” 이고, 이는 실수의 덧셈에 있어서 결합법칙을 나타낸다. 1.4 Nested Quantifiers

Discrete Mathematics by Yang-Sae Moon Page 3 Nested Quantifiers  Statements (2/3) 예제 Variable 의 domain 이 모두 실수일 때, 다음을 번역하라.  x  y((x > 0)  (y < 0)  (xy < 0)) 풀이 : “For every real number x and for every real number y, if x > 0 and y < 0, then xy < 0.” 1.4 Nested Quantifiers

Discrete Mathematics by Yang-Sae Moon Page 4 Nested Quantifiers  Statements (3/3) 예제 C(x) = “x has a computer.”, F(x, y) = “x and y are friends.” 이고, x 와 y 의 domain 이 “all students in your school.” 일 때, 다음을 번역하라.  x(C(x)   y((C(y)  F(x, y))) 풀이 : “For every student x in your school, x has a computer, or there is a student y (in your school) such that y has a computer and x and y are friends.” 1.4 Nested Quantifiers

Discrete Mathematics by Yang-Sae Moon Page 5 Statements  Nested Quantifiers (1/2) 예제 “If a person is female and is a parent, this person is someone’s mother.” 를 predicate, domain = “all people” 인 quantifier, logic operator 로 표현하라. 풀이 − 상기 문장은 다음과 같이 다시 쓸 수 있다. “For every person x, if person x is female and person x is a parent, then there exists a person y such that person x is the mother of person y.” − 명제 함수로 표현 : F(x) = “x is female.” P(x) = “x is a parent.” M(x, y) = “x is the mother of y.” − 상기 명제 함수를 사용하여 표현하면 다음과 같다.  x((F(x)  P(x))   yM(x, y)) 1.4 Nested Quantifiers

Discrete Mathematics by Yang-Sae Moon Page 6 Statements  Nested Quantifiers (2/2) 예제 “Everyone has exactly one best friend.” 를 predicate, domain = “all people” 인 quantifier, logic operator 로 표현하라. 풀이 − 상기 문장은 다음과 같이 다시 쓸 수 있다. “For every person x, person x has exactly one best friend.” = “  x(person x has exactly one best friend)” − 명제 함수로 표현 : B(x, y) = “y is the best friend of x.” −“person x has exactly one best friend.” 를 명제 함수를 사용하여 표현 :  y(B(x, y)   z((z  y)  ¬B(x, z)))  상기 명제 함수를 사용하여 표현하면 다음과 같다.  x  y(B(x, y)   z((z  y)  ¬B(x, z))) 1.4 Nested Quantifiers

Discrete Mathematics by Yang-Sae Moon Page 7 Negating Nested Quantifiers 예제 다음 식의 부정을 표현하라.  x  y(xy = 1) 풀이 Negation of  x  y(xy = 1) “ 모든 x 에 대해서 xy = 1 을 만족하는 y 가 존재한다.” T or F?  ¬(  x  y(xy = 1))  ¬  x  y(xy = 1)   x¬  y(xy = 1)   x  y¬(xy = 1)   x  y(xy  1) “ 어떤 x 에 대해서 모든 y 가 xy  1 을 만족하는 x 가 존재한다.” T or F? −x 와 y 의 domain 에 따라서 진리 값이 달라질 수 있다. 1.4 Nested Quantifiers

Discrete Mathematics by Yang-Sae Moon Page 8 Order of Quantifiers (1/3) 예제 술어 P(x, y) = “x+y = y+x” 이고 x 와 y 의 domain 이 실수일 때,  x  yP(x, y) 의 진리 값은 ? 그리고,  y  xP(x, y) 의 진리 값은 ? 풀이 − 모든 실수에 대하여 덧셈의 교환법칙이 성립하므로,  x  yP(x, y) 의 진리 값 은 true 이다. 마찬가지로,  y  xP(x, y) 의 진리 값 역시 참이다.   x  y 와  y  x 에 있어서,  x 와  y 의 순서는 진리 값에 영향을 주지 않는다. 1.4 Nested Quantifiers

Discrete Mathematics by Yang-Sae Moon Page 9 Order of Quantifiers (2/3) 예제 술어 Q(x, y) = “x + y = 0” 이고 x 와 y 의 domain 이 실수일 때,  y  xQ(x, y) 와  x  yQ(x, y) 의 진리 값은 ? 풀이 −  y  xQ(x, y): 어떤 y 에 대해 모든 x 가 “x + y = 0” 을 만족하는 y 가 존재한다.  false ( 어떤 y 값을 취하여도, 모든 x 에 대해 x + y = 0 를 만족하지는 않는다.) −  x  yQ(x, y): 모든 x 에 대해 “x + y = 0” 을 만족하는 y 가 존재한다.  true   y  x 와  x  y 에 있어서,  x 와  y 의 순서는 진리 값에 영향을 준다. 1.4 Nested Quantifiers

Discrete Mathematics by Yang-Sae Moon Page 10 Order of Quantifiers (3/3) 변수가 두 개인 경우의 Quantifier 순서의 영향 1.4 Nested Quantifiers Statement When true?  x  yP(x, y)  y  xP(x, y) P(x, y) is true for every pair x and y.  x  yP(x, y) For every x, there is a y for which P(x, y) is true.  x  yP(x, y) There is an x for which P(x, y) is true for every y.  x  yP(x, y)  y  xP(x, y) There is a pair x and y for which P(x, y) is true. 모든 x 에 대해서 적어도 P(x, y) 를 true 로 하는 y 가 존재하면, 해당 식은 true 가 된다. 어떤 x 에 대해 모든 y 가 P(x, y) 를 true 로 하면, 해당 식은 true 가 된다.

Discrete Mathematics by Yang-Sae Moon Page 11 유용한 Equivalence Laws  xP(x)  ¬  x ¬ P(x)  xP(x)  ¬  x ¬ P(x) 상기 두 표현 식은 노트 03 에서 소개한 Quantifier 정의를 이용해 증명이 가능하다.(try it!) (Remind) Quantifier 의 정의 :  xP(x)  P(x 1 )  P(x 2 ) ....  P(x n )  xP(x)  P(x 1 )  P(x 2 ) ....  P(x n )  x(P(x)  Q(x))  (  xP(x))  (  xQ(x))  x(P(x)  Q(x))  (  xP(x))  (  xQ(x)) 상기 표현 식 역시 Quantifier 정의를 이용해 증명이 가능하다.(try it!) 1.4 Nested Quantifiers