[이산수학] 1.4 중첩된 한정기호

중첩된 한정기호는 ∀x∃y (x + y = 0) 와 같이 여러개의 한정기호가 한 명제 안에 쓰인 것을 말합니다.

중첩된 한정기호를 이해하는데 프래그래밍의 중첩된 루프와 비교하면 이해가 쉽다.

중첩된 루프는 반복을 반복한다는 뜻입니다.

예를 들어 ∀x∀y P(x, y) 가 참인지 알아보기 위해서 변수 x 의 루프 안에 변수 y 에 대한 루프가 중첩되어 있다는걸 생각할 수 있다.

각각의 x 값에 대하여 y의 값을 변화 시킬때 모든 값들이 참이라면 ∀x∀y P(x, y) 는 참이다.

∀x∃y P(x, y) 는 모든 변수 x의 각각의 값에 대하여 P(x, y)가 참이 되는 y 값을 찾을때까지 y값을 변화시키면서 루프를 실행한다.

찾으면 ∀x∃y P(x, y) 는 참이다.

∃x∀y P(x, y) 는 어떤 x 값이 주어졌을때 y가 가질 수 있는 모든 값에 대하여 루프를 돌려서
P(x, y)가 참이 되는 x 가 하나라도 존재하면 ∃x∀y P(x, y) 는 참이다.

마지막으로 ∃x∃y P(x, y) 는 x, y의 루프를 각각의 값을 변화시켜 수행하다가 P(x, y)를 참이 되는 x, y 값을 찾으면 ∃x∃y P(x, y) 는 참이 된다.

한정기호는 앞에 있는 순서대로 해야한다.

표현	참	거짓
∀x∀y P(x, y) ∀y∀x P(x, y)	모든 x, y의 쌍에 대하여 P(x, y)가 참이다.	P(x, y)가 거짓이 되는 x, y의 쌍이 있다.
∀x∃y P(x, y)	모든 x에 대하여 P(x, y)가 참이되는 y가 있다.	어떤 x 가 있고 모든 y에 대하여 P(x, y) 가 거짓이다.
∃x∀y P(x, y)	어떤 x가 있고 모든 y에 대하여 P(x, y)가 참이다.	모든 x에 대하여 P(x, y)가 거짓이 되는 y 가 있다.
∃x∃y P(x, y) ∃y∃x P(x, y)	P(x, y)가 참이 되는 x, y의 쌍이 있다.	모든 x, y의 쌍에 대하여 P(x, y)가 거짓이다.

중첩된 한정기호를 영어문장으로 변환하고 영어문장을 논리표현으로 바꿀 수 있지만 나는 수학과가 아니고, 어렵고 귀찮아서 안하렵니다.

중첩 한정기호의 부정은 되게 간단하다.

저번 글에 일반 한정기호의 부정을 썻는데 중첩된 한정기호의 부정은 그걸 꼬리에 꼬리를 물고 따라가는 것이다.

예를 들어서 ∀x∃y (x y = 1) 의 부정은 ￢∀x∃y (x y = 1) 인데 부정 기호를 안으로 집어 넣으면
∃x￢∃y (x y = 1)이고, 한번더 넣으면 ∃x∀y￢ (x y = 1) 로 쓸 수 있다.

끝