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

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.”이고, 이는 실수의 덧셈에 있어서 결합법칙을 나타낸다.

Nested Quantifiers  Statements (2/3) 예제 2 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.”

Nested Quantifiers  Statements (3/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.”

Statements  Nested Quantifiers (1/2) 예제 5 “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 y 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))

Statements  Nested Quantifiers (2/2) 예제 7 “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)))

Negating Nested Quantifiers 예제 11 다음 식의 부정을 표현하라. 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) [refer to $1.3]  xy¬(xy = 1) [refer to $1.3]  xy(xy  1) “어떤 x에 대해서 모든 y가 xy  1을 만족하는 x가 존재한다.” T or F? x와 y의 domain에 따라서 진리 값이 달라질 수 있다.

Order of Quantifiers (1/3) 1.4 Nested Quantifiers 예제 14 술어 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의 순서는 진리 값에 영향을 주지 않는다.

Order of Quantifiers (2/3) 1.4 Nested Quantifiers 예제 15 술어 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의 순서는 진리 값에 영향을 준다.

Order of Quantifiers (3/3) 1.4 Nested Quantifiers 변수가 두 개인 경우의 Quantifier 순서의 영향 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가 된다.

유용한 Equivalence Laws xP(x)  ¬x¬P(x) xP(x)  ¬x¬P(x) 1.4 Nested Quantifiers xP(x)  ¬x¬P(x) xP(x)  ¬x¬P(x) 상기 두 표현 식은 $1.3에서 소개한 Quantifier 정의를 이용해 증명이 가능하다.(try it!) (Remind) Quantifier의 정의: xP(x)  P(x1)  P(x2)  ....  P(xn) xP(x)  P(x1)  P(x2)  ....  P(xn) x(P(x)  Q(x))  (xP(x))  (xQ(x)) x(P(x)  Q(x))  (xP(x))  (xQ(x)) 상기 표현 식 역시 Quantifier 정의를 이용해 증명이 가능하다.(try it!)