집합 이미지, 동치 관계 및 논리적 부정
도입됨| English | 의미 |
|---|---|
| preimage/ˌpriːˈɪmɪdʒ/ | 원상 |
| equivalence relation/ɪˈkwɪvələns rɪˈleɪʃn/ | 동치 관계 |
답에 앞서 결정하기
- 서로 다른 레코드에는 같은 라벨이 할당될 수 있다. 이러한 단순한 충돌로 인해 교집합의 이미지와 두 이미지의 교집합이 다를 수 있다.
- 목표: 이미지恒等式(image identities)를 증명하고 포함관계와 동등함을 구별하라.
관계 파악하기
- f:X→Y이고 A⊆X일 때, 이미지 f(A)는 A에 속하는 모든 a에 대한 출력 f(a)의 모음이다. 한 점이 f(A∪B)에 속할 정확히는 A 또는 B에서 기원할 때이며, 따라서 f(A∪B)=f(A)∪f(B)이다. A⊆B이면 f(A)⊆f(B)이다. 교집합에 대해서는 오직 f(A∩B)⊆f(A)∩f(B)가 자동적으로 성립한다: 동일한 출력이 서로 다른 입력에서 올 수 있기 때문이다. f(x)=x², A={−1}, B={1}를 사용하라; 왼쪽 이미지는 공집합이지만 오른쪽 교집합은 {1}이다.
- 반사성, 대칭성과 추이성을 구체적인 사례로 확인하라.
Which identity holds for every function f and subsets A,B of its domain?
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
An output of an input in the union comes from at least one subset. Intersection equality can fail when distinct inputs share an output.
정의 규칙 활용하기
- 역像(preimages)은 다른 거동을 보인다. C⊆Y에 대해, f⁻¹(C)는 f에 역함수가 없더라도 C로 매핑되는 모든 입력의 집합을 의미한다. 두 역像에 membership한다는 것은 동일한 입력이 두 표적 집합 모두로 매핑됨을 뜻한다. consequently 역像은 명시된 도메인/코도메인-relative로 합집합, 교집합, 그리고 보집합을 보존한다. 역像에 대한 정리를 이미지로 옮겨서 적용하지 말라. f가 단조이면 이미지 교집합이 실제로 같아지는데, 이는 동일한 출력은 공유된 입력을 강요하기 때문이다.
- 함의와 양적화 statements을 negation하되 scope는 변경하지 말라.
What is the negation of P⇒(Q∧R)?
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
Failure of the implication requires a true premise and a false conjunction. De Morgan changes the latter into a disjunction.
조건 확인
- X 위의 관계 R은 모든 x에 대해 xRx이면 반사적이고, xRy implies yRx이면 대칭적이며, xRy and yRz imply xRz이면 추이적이다. 이 세 가지가 equivalence relation을 구성하며, 그 classes는 X를 partition한다. 정수에서 x와 y가 4로 나눈 나머지가 같을 때 xRy를 정의하면 네 개의 classes가 생긴다. 관계 |x−y|≤1은 반사적이고 대칭적이지만 추이적이지 않다: 0R1이고 1R2이지만 0은 2과 관련되어 있지 않다. 도표 하나나 성질 두 개만 체크하는 것은 불충분하다.
- 함의와 양적화 statements을 negation하되 scope는 변경하지 말라.
f가 a와 b를 모두 라벨 L에 매핑한다고 하자. A={a}, B={b}이라 하면, f(A∩B)=∅이지만 f(A)∩f(B)={L}이다. R에서 x=y 또는 x=−y로 정의된 xRy는 반사성과 대칭성이 직접 따르며, 두 번의 부호 변경을 해도 z=±x이 되어 추이성을 증명한 다. classes는 {x,−x}이며, {0}는aban singleton이다. “저장된 모든 파일에는 해시가 있다”라는 명제가 거짓이라는 것은 적어도 하나의 저장된 파일에는 해시가 없다는 것을 의미하며, 모든 파일에 해시가 없다는 것을 의미하지는 않는다.
How many equivalence classes are there on Z for equality of remainders modulo four?
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
Each integer belongs to exactly one of the remainder classes 0, 1, 2 or 3.
문제 형식 적용하기
- 함의 P⇒Q는 P가 참이고 Q가 거짓일 때에만 거짓이다. 따라서 P⇒(Q∧R)의 negation은 ¬P⇒(¬Q∧¬R)가 아니라 P∧(¬Q∨¬R)이다. “모든 x는 성질 A를 가진다”를 negation하면 “A를 가지지 않는 x가 존재한다”가 되고, “존재하는 x가 있다”를 negation하면 “모든 x는 그렇지 않다”가 된다. counterexample은 universal claim을证伪할 수 있지만, examples는 proof할 수 없다. 양적자들은 개별적으로 negation될 때 순서를 유지한다: ¬(∀x∃y S(x,y))는 x∀y ¬S(x,y)이다.
- 함의와 양적화 statements을 negation하되 scope는 변경하지 말라.
f⁻¹(C)는 역함수 없이 역像 set을 의미할 수 있다. 반사적이고 대칭적인 관계도 여전히 추이성을 실패할 수 있다. parts를 simplify하기 전에 전체 statement를 negation하라.
다음 중 이 사례에 부합하는 답안은 무엇입니까?
像恒等式를 증명하고 포함 관계와 동치를 구분함
The relation |x−y|≤1 on R is transitive.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
Use x=0,y=1,z=2: the first two pairs satisfy the relation, but the pair (0,2) does not.
구분을 유지하기
- preimage —的输出이 명시된 target set에 속하는 inputs의 집합.
- equivalence relation — 반사적이고 대칭적이며 추이적인 관계.
- 이미지 등식 증명 및 포함 관계와 동등함 구분
- 반사성, 대칭성과 추이성을 구체적인 사례로 확인하라.
- 함의와 양적화 statements을 negation하되 scope는 변경하지 말라.
Match each term with its precise meaning in this lesson.
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
Keep the distinctions stated in the teaching example.
Put this lesson’s reasoning or event sequence in order.
난이도 3/5 · 200 코인 + 오늘 첫 완료 시 소액 보너스
The order follows the stated process; check each stage before the next.