이산수학을 배우면서 헷갈렸던 것입니다.

검색이 되도록 글 전체를 그대로 가져왔습니다.

================== 원글 ===================

교수님께서 주신 답변과 교재, 참고자료를 살펴보고 이렇게 해석하였습니다.

∀x, ∃y , x < y (x, y ∈ N)  T : 모든 x에 대해서 x<y를 만족하는 y가 존재한다.

∃x, ∀y, x > y (x, y ∈ N)  F : 어떤 y가 존재한다. 그것은 모든 x에 대해서 x<y를 만족하는 것이다.

첫 번째 것은 모든 x에 대해 x<y인 y의 값이 달라도 되지만,

두 번째 것은 모든 x에 대해 x<y인 y가 고정되어 있다는 뜻이라 생각합니다.

그렇기에 첫 번째 것은 x + 1이 있으므로 True가 되지만,

모든 자연수에 대해 그보다 큰 자연수는 존재하지 않으므로 False라 생각합니다.

교재를 보니 ∃one plate ∀students는 학생들이 하나의 접시를 가지고 있고,

∀students ∃one plate는 학생들이 각자 하나의 접시를 들고 있는 모습이 보입니다.

다른 참고자료에서도 A를 미국인 집합, D를 꿈의 집합, H(a, d)를 "American a has dream d"라고 할 때,

∃d ∈ D ∀a ∈ A. H(a,d)와 ∀a ∈ A ∃d ∈ D. H(a,d)의 차이점으로

전자는 'There is a single dream that every American shares.'라고 적혀있고,

후자는 'Every American has their personal dream.'이라 적혀있습니다.

이처럼 앞에 ∃가 나오면 그것을 뒤에 나오는 것들이 공유(share)하는 것으로 생각하면 괜찮습니까?

네 맞습니다.

마찬가지로 ∃c1, ∃c2, ∃n0, ∀(n ≥ n0, 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n)) 의 경우

'어떤 c1, c2, n0가 존재한다. 그것은 n0보다 큰 모든 n에 대해서 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n)를 만족한다.'라고 하여

c1, c2, n0는 모든 n(n ≥ n0)에 따라 변하지 않는 각 n들이 공유하는 그런 값입니까?

(생각해보니 만약 공유하지 않는다면 n이 변할 때마다 각각의 값들이 변할 것이니 이상할 듯...)

마지막으로 ∃c1, ∃c2, ∃n0, ∀(n ≥ n0, 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n))라고 적어주셨는데,

마지막에 ∀은 predicate를 감싸도 문제 없습니까?(표기를 실수했습니다. 아래와 같이 표기합니다)

∃c1, ∃c2, ∃n0, ∀n(n ≥ n0), 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n)

예전에 관련 내용을 공부하였지만 정작 쓰려고 할 때 그 정의가 명확하지 못해 제대로 쓰지 못한적이 있어

이번에 확실히 이해하고자 질문이 길어졌습니다.

제 표현이나 생각에 오류가 있다면 지적해주시면 감사드립니다.

================== 원글 ===================

================== 원글 ===================

1. 교수님께서 주신 자료 문제 11번의 (a)와 (b)의 답이 무엇인가요?

11. Fro each of the following sentences, write down the sentence in logical notation, negate the sentence, and say whether the sentence or its negation is true.

(a) Given any integer, there is a larger integer.

∀x, ∃y , x < y (x, y ∈ N)  T

(b) There is an integer greater than all other integers.

∃x, ∀y, x > y (x, y ∈ N)  F

2. 만약 b의 답을 ∃y ∀x, x < y (x, y ∈ N)라고 적어도 문제가 없습니까?

즉, x와 y의 자리를 바꾸어도 괜찮습니까?

자리를 바꾸면 의미가 달라집니다.

3. 다음과 같은 글이 있다면 이는 이렇게 바꿀 수 있습니까?

Θ(g(n)) = {f(n) : there exist positive constants c1, c2, and n0 such that 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n)
for all n ≥ n0}.

∃c1, ∃c2, ∃n0, ∀(n ≥ n0, 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n))

== there exist positive constants c1, c2, and n0 such that 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n)
for all n ≥ n0

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.