[이산수학] 중첩된 한정자

중첩된 한정자

∀x ∀y P(x,y)

임의의 양의 두 실수의 합은 양수이다.

 

L(x, y)를 'x가 y를 사랑한다' 라고 하자. 다음 문장을 기호로 표현.

 

모든 사람은 어떤 사람을 사랑한다. 

∀ x ∃ y L(x, y)

-모든 사람 x에 대하여, x가 y를 사랑하는 어떤 사람 y가 존재한다. 

 

∃x ∀y L(x, y)

-어떤 사람 x가 존재하는데, 모든 y에 대해서 x가 y를 사랑한다.

-어떤 사람은 모든 사람을 사랑한다.

 

한정 기호의 순서는 중요합니다. 한정 기호의 순서를 바꾸면 의미 또한 바뀝니다.

 

∀x ∀y P(x, y)

∀y ∀x P(x, y)

 

∀x ∃y P(x,y)

∃x ∀y P(x,y)

 

∃x ∃x P(x,y)

∃y ∃x P(x,y)

 

모든 x에 대하여 P(x,y)를 true로 하는 적어도 하나의 y가 존재하면, 해당 식은 true가 됩니다. 어떤 x에 대하여 모든 y가 p(x,y)를 true하면 해당 식은 true가 됩니다.

---

∃x ∀y (x <= y)

x y는 각각 양의 정수의 집합일 때 이 명제함수가 참이냐 거짓이냐 판단할 수 있어야 합니다. 

 

해석을 해보면 한정자가 y에 대해서는 전칭한정자가 붙었기에 모든 y에 대해서 작거나 같은 x가 존재하느냐? 를 생각해보면 됩니다. 결국 이것은 야의 정수의 집합에서 최소값이 있는지를 생각해보면 됩니다. 

 

양의 정수들 집합에서 가장 작은 원소가 되는 x가 있느냐를 생각하면 됩니다. 1은 모든 양의 정수들보다 항상 작거나 같죠. 그런 원소 x가 존재하기에 이 명제함수는 참이 됩니다. 

 

∃x ∀y (x >= y)

x, y 둘 다 양의 정수라고 할 때, 해당 값은 존재할까요? 최대값을 구해야 하는데 우리는 양의 정수의 최대값을 알지 못합니다. 무한히 있기 때문에 x는 어떤 값이라고 특정할 수 없기 때문에 이 명제함수는 거짓이 됩니다. 

 

---

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; 이는 덧 셈에 있어서 결합법칙을 의미합니다. 

 

중첩 한정 기호를 영어로 표현 

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) U ∃y((C(y) ^ F(x, y)))

풀이 : 

For every students x in your school, x has a computer, or there is a student y such that y has a computer and x and y are friends.

 

영어 문장의 논리 표현으로 번역

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 a 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) -> ∃y M(x, y);]