[이산구조 개념-05] 한정자의 순서·부정·동치 — 술어 논리 심화

1. 한정자의 순서가 왜 중요한가

같은 술어 P(x, y)에 같은 한정자 ∀, ∃를 써도 순서를 바꾸면 의미가 완전히 달라진다. 이 차이를 정확히 이해하는 것이 5강의 출발점이다.

핵심 원칙: 안전 구역과 위험 구역

구분패턴순서 변경 가능?

안전 구역	∀∀ 또는 ∃∃ (같은 종류)	⭕ 가능
위험 구역	∀∃ 또는 ∃∀ (다른 종류)	❌ 절대 불가

---

2. 안전 구역 — 같은 종류의 한정자

같은 종류의 한정자가 연속될 때는 순서를 바꿔도 의미가 동일하다.

동치 관계의미

∀x ∀y P(x,y) ≡ ∀y ∀x P(x,y)	"모든 x, 모든 y에 대해" — 순서 무관
∃x ∃y P(x,y) ≡ ∃y ∃x P(x,y)	"어떤 x, 어떤 y가 존재" — 순서 무관

예시

∀x ∀y (x + y = y + x) ≡ ∀y ∀x (x + y = y + x)

→ 두 식 모두 "덧셈의 교환법칙"을 의미한다. 순서를 바꿔도 동일.

💡 같은 종류의 한정자는 "전부 다" 또는 "어떤 것이라도"라는 동일한 강도의 조건이므로 순서가 의미에 영향을 주지 않는다.

---

3. 위험 구역 — 다른 종류의 한정자 ⭐ 시험 빈출

∀와 ∃가 섞이면 순서가 의미를 결정한다. 다음 두 식의 차이를 보자.

비교 분석

식의미진리값 (실수 정의역)

∀x ∃y (x + y = 0)	모든 x마다 그에 맞는 y가 따로 존재	참(True)
∃y ∀x (x + y = 0)	단 하나의 y가 모든 x를 만족시킴	거짓(False)

왜 이런 차이가 나는가?

∀x ∃y (x + y = 0) — "각 x에 대해 따로따로 y를 찾을 수 있다"

x만족하는 y결과

3	-3	3 + (-3) = 0 ✅
5	-5	5 + (-5) = 0 ✅
-7	7	-7 + 7 = 0 ✅

각 x마다 다른 y를 사용해도 OK. → 항상 가능 → 참

∃y ∀x (x + y = 0) — "단 하나의 y가 모든 x에 대해 작동해야 한다"

가정한 y모든 x에 대해 성립?

y = 0	x=3일 때 3+0=3 ≠ 0 ❌
y = -3	x=5일 때 5+(-3)=2 ≠ 0 ❌
어떤 y든	단일 y로는 모든 x 불가능 ❌

→ 그런 마법의 y는 존재하지 않음 → 거짓

💡 핵심 직관: ∀∃는 "각자 다른 답 OK", ∃∀는 "하나의 답이 전부를 책임져야 함". 후자가 훨씬 강력한 조건이다.

---

4. 한정자 조합 4가지의 강도 — 논리 함정 판독기

중첩 한정자 4가지 패턴을 조건의 엄격함(강도) 순으로 정리하면 시험에서 절대 헷갈리지 않는다.

강도패턴의미만족 조건

⭐⭐⭐⭐⭐ 가장 빡빡	∀x∀y P(x,y)	모든 x, y 쌍이 P 만족	한 쌍이라도 안 되면 거짓
⭐⭐⭐⭐	∀x∃y P(x,y)	각 x마다 그에 맞는 y 존재	어떤 x에 대해 y 못 찾으면 거짓
⭐⭐⭐	∃x∀y P(x,y)	모든 y에 대해 작동하는 x 존재	그런 강력한 x가 1개라도 있으면 참
⭐⭐ 가장 느슨	∃x∃y P(x,y)	P를 만족하는 x, y 쌍 1개라도 존재	한 쌍이라도 있으면 참

실생활 비유

패턴비유

∀x∀y	"회사의 모든 직원이 모든 부서와 협업한다"
∀x∃y	"모든 직원에게는 각자의 멘토가 있다"
∃x∀y	"모든 부서를 총괄하는 단 한 명의 CEO가 있다"
∃x∃y	"어떤 직원이 어떤 부서와 협업한 적이 있다"

💡 시험 팁: 문제에서 "단 하나의", "유일한", "공통의" 같은 표현이 나오면 ∃∀ 패턴을 의심하자.

---

5. '오직 하나(Exactly One)' 표현법 ⭐ 고난도

"오직 하나"는 ∃보다 강한 조건이다. 단순히 "존재한다"가 아니라 "적어도 하나 존재 + 두 개 이상은 없음" 을 동시에 만족해야 한다.

두 가지 조건의 결합

조건표현

존재성: 하나는 있다	∃y P(x, y)
유일성: 다른 것은 없다	∀z ((z ≠ y) → ¬P(x, z))

두 조건을 결합한 완전한 식

"모든 사람은 오직 한 명의 절친이 있다." (B(x, y) = "y는 x의 절친")

∀x ∃y (B(x, y) ∧ ∀z ((z ≠ y) → ¬B(x, z)))

단계별 분해

단계내용의미

Step 1	∀x ∃y B(x, y)	모두에게 절친이 있다
Step 2	(그런데 잠깐!)	절친이 2명이면 안 된다
Step 3	∀z ((z ≠ y) → ¬B(x, z))	다른 누군가 z가 절친이라면, z는 사실 y와 같은 사람이어야 함

💡 응용 분야: 데이터베이스의 UNIQUE 키, 프로그래밍의 싱글턴 패턴, 수학에서 "유일한 해의 존재" 증명 등 — 모두 이 '오직 하나' 표현이 기반이다.

---

6. 중첩 한정자의 부정 — 도미노 플립 법칙 ⭐⭐⭐ 핵심

중첩 한정자가 포함된 명제 전체에 부정(¬)을 걸 때, 부정 기호가 한정자를 통과하면서 한정자의 종류를 뒤집는 규칙이다. 도미노가 줄줄이 넘어가듯 부정이 안쪽으로 퍼져나간다고 해서 도미노 플립(Domino Flip) 이라 부른다.

핵심 변환 규칙

변환 전변환 후의미

¬∀x P(x)	∃x ¬P(x)	"모든 x가 P" 의 부정 = "어떤 x는 P가 아님"
¬∃x P(x)	∀x ¬P(x)	"어떤 x가 P" 의 부정 = "모든 x가 P가 아님"

직관적 이해

원문부정

"모든 학생이 합격했다"	"어떤 학생은 합격하지 못했다" (한 명만 떨어져도 부정 성립)
"어떤 학생이 만점을 받았다"	"모든 학생이 만점을 못 받았다" (전부 만점이 아니어야 부정 성립)

💡 드모르간 법칙과의 관계: 3강에서 배운 ¬(P∧Q) ≡ ¬P∨¬Q와 똑같은 원리다. 한정자 버전이라고 보면 된다.

---

7. 도미노 플립 실전 풀이 ⭐ 시험 단골

여러 한정자가 중첩된 식의 부정을 단계별로 풀어보자.

예제

식: ¬(∀x ∃y (xy = 1))

원래 의미: "모든 x에 대해, xy=1을 만드는 y가 존재한다."

풀이 단계 (Cut 단위로 진행)

Cut변환 과정적용 규칙

시작	¬(∀x ∃y (xy = 1))	—
Cut 1	∃x ¬(∃y (xy = 1))	¬∀x → ∃x¬
Cut 2	∃x ∀y ¬(xy = 1)	¬∃y → ∀y¬
Cut 3	∃x ∀y (xy ≠ 1)	¬(xy=1) → (xy≠1)

최종 해석

"어떤 x가 존재하여, 모든 y에 대해 xy ≠ 1이다."

즉, "어떤 x는 절대로 곱해서 1이 되는 y를 찾을 수 없다." (예: x=0이면 어떤 y와 곱해도 0이지 1이 되지 않음)

💡 풀이 패턴: 부정 기호를 한 단계씩 안으로 밀어넣으면서 만나는 한정자를 뒤집는다. 마지막에는 술어 자체에 부정이 적용되어 P → ¬P 또는 = → ≠로 변환된다.

---

8. 한정자와 동치 법칙 — 분배의 한계

3강에서 배운 분배 법칙이 한정자에도 적용되지만, 조심해야 할 함정이 있다.

분배가 가능한 경우 (찰떡궁합)

동치 관계별명

∀x (P(x) ∧ Q(x)) ≡ ∀x P(x) ∧ ∀x Q(x)	∀와 ∧는 찰떡궁합
∃x (P(x) ∨ Q(x)) ≡ ∃x P(x) ∨ ∃x Q(x)	∃와 ∨는 찰떡궁합

분배가 불가능한 경우 (절대 금지)

잘못된 식왜 안 되는가?

∀x (P(x) ∨ Q(x)) ≢ ∀x P(x) ∨ ∀x Q(x)	"모두 P이거나 Q"는 ⊃ "모두 P이거나 모두 Q"
∃x (P(x) ∧ Q(x)) ≢ ∃x P(x) ∧ ∃x Q(x)	"P이면서 Q인 x 존재"는 ⊃ "P인 x 존재 ∧ Q인 x 존재"

반례로 이해하기

∀x (P(x) ∨ Q(x)) 의 경우:

사람P(x): 안경 씀Q(x): 안경 안 씀

철수	✅	❌
영희	❌	✅

→ ∀x (P(x) ∨ Q(x)): "모두가 안경을 쓰거나 안 쓴다" → 참 → ∀x P(x) ∨ ∀x Q(x): "모두 안경을 쓴다 또는 모두 안 쓴다" → 거짓 (둘 다 거짓이므로)

따라서 둘은 동치가 아니다.

💡 암기 비법: ∀는 AND와 친구, ∃는 OR와 친구. 친구끼리만 분배 가능. 다른 조합은 함부로 분배하지 말 것.

---

9. 자연어 → 논리식 변환 표준 4단계 절차 ★ 신규 보강

지금까지 예제 위주로 변환을 다뤘지만, 시험에서 다양한 문장을 만났을 때 항상 적용 가능한 표준 절차를 정리해두면 실수가 줄어든다. 교수님 원래 교안 p.3~4에서 강조된 4단계 인코딩 방식이다.

표준 4단계 절차

단계작업확인 포인트

Step 1	주요 개념 식별 — 주어·객체·관계 분리	누가 행위 주체? 객체는 무엇? 어떤 관계?
Step 2	변수 도메인 설정 — 변수의 범위 명확화	모든 사람? 모든 실수? 특정 그룹?
Step 3	한정자 적용 — '모든', '어떤', '정확히 하나'	"모든" → ∀, "어떤" → ∃, "정확히 하나" → ∃ + ∀ 결합
Step 4	논리 연산자 연결 — ∧·∨·→·¬ 결정	"그리고" / "또는" / "만약~이면" / "아니다"

4단계 적용 예시

문장: "모든 학생은 정확히 한 명의 가장 친한 친구를 가진다."

Step 1 — 주요 개념 식별

요소식별

주어	학생 (변수 x)
객체	가장 친한 친구 (변수 y)
관계	"y는 x의 가장 친한 친구다" → B(x, y)

Step 2 — 변수 도메인 설정

변수 x, y의 도메인 = 모든 사람

Step 3 — 한정자 적용

자연어한정자

"모든 학생"	∀x
"정확히 한 명"	∃y + ∀z 결합 (오직 하나 표현)

Step 4 — 논리 연산자 연결

부분연결

존재성 + 유일성	∧ (둘 다 만족해야 함)
유일성 조건	→ (z ≠ y라면 절친이 아님)

최종 조립

∀x ∃y (B(x, y) ∧ ∀z ((z ≠ y) → ¬B(x, z)))

시험에서 자주 등장하는 한국어 → 한정자 매핑

한국어 표현한정자

모든 / 모두 / 임의의	∀
어떤 / 어느 / 적어도 하나	∃
어떠한 ~도 없다	¬∃ = ∀¬
정확히 하나	∃ + ∀ (유일성)
적어도 두 개	∃x ∃y (x ≠ y ∧ ...)

💡 시험 팁: "모든 [조건]은 [결과]이다" 패턴은 거의 100% ∀x (조건 → 결과) 형태다. ∀x (조건 ∧ 결과)로 쓰면 "모든 x가 조건과 결과를 동시에 만족"이 되어 의미가 완전히 달라진다 (4강 예상문제 2번 참고).

---

10. 종합 인코딩 예제 — 문장을 수식으로

지금까지 배운 것을 모두 활용한 종합 예제를 풀어보자.

문제

"모든 사람 x에 대해, 만약 x가 여성이고 부모라면, x가 y의 어머니인 사람 y가 존재한다."

1단계 — 술어 정의

술어의미

F(x)	x는 여성이다
P(x)	x는 부모이다
M(x, y)	x는 y의 어머니다

2단계 — 구조 분석

구성분해

주어 범위	"모든 사람 x" → ∀x
조건 (전제)	"x가 여성이고 부모라면" → (F(x) ∧ P(x))
함축	"라면" → →
결과	"x가 y의 어머니인 y가 존재" → ∃y M(x, y)

3단계 — 최종 조립

∀x ((F(x) ∧ P(x)) → ∃y M(x, y))

검증 해석

"모든 사람 x에 대해, x가 여성이고 부모라면, x가 어머니인 어떤 y가 존재한다."

원문과 일치 ✅

---

📌 한눈에 보는 핵심정리

개념핵심 공식 / 규칙

순서 무관 (안전)	∀x∀y ≡ ∀y∀x, ∃x∃y ≡ ∃y∃x
순서 중요 (위험)	∀x∃y ≢ ∃y∀x
∀∃ 의미	각 x마다 다른 y OK
∃∀ 의미	단 하나의 y가 모든 x 책임
'오직 하나' 표현	∃y (P(x,y) ∧ ∀z ((z≠y) → ¬P(x,z)))
도미노 플립 ①	¬∀x P(x) ≡ ∃x ¬P(x)
도미노 플립 ②	¬∃x P(x) ≡ ∀x ¬P(x)
분배 가능 ①	∀x (P∧Q) ≡ ∀x P ∧ ∀x Q
분배 가능 ②	∃x (P∨Q) ≡ ∃x P ∨ ∃x Q
분배 금지 ①	∀x (P∨Q) ≢ ∀x P ∨ ∀x Q
분배 금지 ②	∃x (P∧Q) ≢ ∃x P ∧ ∃x Q
자연어 변환 4단계 ⭐	개념 식별 → 도메인 → 한정자 → 연산자

---

🧠 예상문제 2제

문제 1. 한정자 순서와 진리값

다음 두 명제 중 참(True) 인 것을 모두 고르시오. (단, 정의역은 모든 실수)

명제 A: ∀x ∃y (x · y = 1) 명제 B: ∃y ∀x (x · y = 1)

① A만 참 ② B만 참 ③ A, B 모두 참 ④ A, B 모두 거짓

👉 정답: ④

A 분석

"모든 x에 대해 xy=1을 만드는 y가 존재"

x만족하는 y결과

2	1/2	✅
5	1/5	✅
0	불가능	❌ (어떤 y도 0·y=0이지 1이 될 수 없음)

따라서 거짓.

B 분석

"단 하나의 y가 모든 x에 대해 xy=1"

y=1이면 x=2일 때 2·1=2 ≠ 1 ❌ 그런 y는 존재하지 않음 → 거짓.

⚠️ 함정 주의: 만약 정의역에서 0이 빠진 0이 아닌 실수라면 A는 참이 된다. 정의역 확인이 필수임을 보여주는 문제다.

---

문제 2. 도미노 플립 단계별 적용

다음 명제의 부정을 도미노 플립 법칙으로 변환했을 때, 최종 형태로 옳은 것은?

¬(∀x ∃y (P(x) → Q(y)))

① ∀x ∃y ¬(P(x) → Q(y)) ② ∃x ∀y ¬(P(x) → Q(y)) ③ ∃x ∀y (P(x) ∧ ¬Q(y)) ④ ∃x ∀y (¬P(x) ∨ Q(y))

👉 정답: ③

단계별 풀이

Cut변환규칙

시작	¬(∀x ∃y (P(x) → Q(y)))	—
Cut 1	∃x ¬(∃y (P(x) → Q(y)))	¬∀x → ∃x¬
Cut 2	∃x ∀y ¬(P(x) → Q(y))	¬∃y → ∀y¬
Cut 3	∃x ∀y ¬(¬P(x) ∨ Q(y))	함축 변환 (3강): P→Q ≡ ¬P∨Q
Cut 4	∃x ∀y (P(x) ∧ ¬Q(y))	드모르간 + 이중부정

💡 추가 학습: 이 문제는 5강의 도미노 플립 + 3강의 함축 변환 + 드모르간 법칙을 모두 결합한 종합 문제다. 시험에서 이런 멀티 스텝 문제가 자주 출제되니 단계별 풀이 패턴을 반드시 익혀두자.