본문으로 건너뛰기
SuanLab

양화사·증인과 반례

모든 입력마다 다른 답을 고를 수 있는 것과 공통 답 하나가 존재하는 것은 다릅니다.

02 / LOGIC LAB
먼저 알아두면 좋아요 · 기본 정수 계산과 연결된 앞 단원의 표기
명제·조건과 논리적 함의 →
단원 목록 (103) · 양화사·증인과 반례
이해하는 속도로 읽으세요.개념도이론실험확인 문제
BUILD YOUR INTUITION

먼저 그림으로 이해하기

한 번에 한 단계씩 살펴보세요.

모든 입력마다 다른 답을 고를 수 있는 것과 공통 답 하나가 존재하는 것은 다릅니다.

행: x · 열: yT00F1F2F1TFF2FT파랑: 참 · 주황: 거짓
고정한 유한 기준 모형입니다. 단계별 설명과 별도의 일반 논증을 구분해 읽으세요. 고정된 기준 예제이며 아래 실험의 설정과 독립적입니다.
1 / 4

정의역

x와 y의 범위 D={0,1,2}를 먼저 정합니다.

R(x,y): y=x

실험에서 확인하기 →
이 단원 목차

누가 먼저 선택하는가

‘모든 과제마다 좋은 모형이 있다’와 ‘모든 과제에 좋은 모형 하나가 있다’는 다릅니다. 앞 문장은 과제마다 모형을 바꿀 수 있고 뒤 문장은 공통 선택을 요구합니다. 양화사는 이런 의존성을 표현하며 최적화 보장과 연구 주장을 읽는 핵심 도구입니다.

술어 R(x,y)R(x,y)는 입력을 선택하면 참·거짓이 정해집니다. 양화한 문장에는 입력 범위도 필요합니다. 실험에서 두 변수는 모두 D={0,…,N−1}D=\{0,\ldots,N-1\}에 속합니다.

네 가지 기본 형태

공식 읽기
∀x∈D ∃y∈D:R(x,y)\forall x\in D\,\exists y\in D:R(x,y) 각 x마다 적어도 하나의 적절한 y
∃y∈D ∀x∈D:R(x,y)\exists y\in D\,\forall x\in D:R(x,y) 모든 x에 통하는 공통 y 하나
∀x∈D ∀y∈D:R(x,y)\forall x\in D\,\forall y\in D:R(x,y) 모든 쌍이 성립
∃x∈D ∃y∈D:R(x,y)\exists x\in D\,\exists y\in D:R(x,y) 적어도 한 쌍이 성립

독립적으로 고정한 정의역에서 전칭끼리 또는 존재끼리는 순서를 바꿀 수 있습니다. 전칭·존재가 섞이면 일반적으로 안 됩니다. 괄호와 의존성이 어떤 선택을 바꿀 수 있는지 정합니다.

모두 볼 수 있는 기준 예제

N=3, 술어를 y=xy=x로 둡니다.

x\y 0 1 2
0 참 거짓 거짓
1 거짓 참 거짓
2 거짓 거짓 참

각 행에 참이 하나 있어 ∀x∃yR\forall x\exists y R는 참입니다. y=x를 고르면 됩니다. 모든 칸이 참인 열은 없어 ∃y∀xR\exists y\forall x R는 거짓입니다. 존재의 증인은 그 뒤 범위 전체를 만족해야 합니다. 성공한 한 쌍만으로 전칭 요구를 만족하지는 않습니다.

공통 증인이 있으면 각 입력에서 재사용하면 되므로 두 번째 문장은 첫 번째를 함의합니다. 등호 예제는 반대 방향이 실패함을 보여줍니다.

문장 전체를 부정하기

전칭을 부정하려면 반례, 존재를 부정하려면 모든 후보의 실패가 필요합니다.

¬∀x P(x)≡∃x ¬P(x),¬∃y Q(y)≡∀y ¬Q(y).\neg\forall x\,P(x)\equiv\exists x\,\neg P(x),\qquad \neg\exists y\,Q(y)\equiv\forall y\,\neg Q(y).

연속 적용하면

¬(∀x∃y R(x,y))≡∃x∀y ¬R(x,y)\neg\bigl(\forall x\exists y\,R(x,y)\bigr) \equiv\exists x\forall y\,\neg R(x,y)

입니다. 실패한 쌍 하나로 ‘모든 x마다 어떤 y가 있다’를 반박할 수 없습니다. 모든 허용 y가 실패하는 x 하나를 보여야 합니다. 실험은 그런 행을 실패 증인으로 반환합니다.

정의역이 달라지면 정리도 달라진다

R(x,y):y>xR(x,y):y>x를 고르세요. D={0,1,2}에서 x=2보다 큰 y는 D 안에 없어 전칭·존재 문장은 거짓입니다. 자연수 전체에서는 y=x+1을 고를 수 있어 참입니다.

그래도 모든 자연수 x보다 큰 공통 y는 없습니다. 어떤 y를 제안해도 x=y를 고르면 실패합니다. 유한 검색에서 충분히 큰 수를 못 찾았다는 것이 아니라 일반 반박입니다.

AI 보장도 마찬가지입니다. 제한된 입력 집합의 모든 대상과 임의의 모든 입력은 다릅니다. 유한 벤치마크만으로 무제한 분포나 모든 미래 과제의 주장을 검증할 수는 없습니다.

빈 정의역과 공허한 참

실험은 집합으로 제한한 양화에서 빈 D를 허용합니다. 전칭을 위반하는 x가 없으므로 ∀x∈D∃y∈DR\forall x\in D\exists y\in D R는 참입니다. 증인 y는 없으므로 ∃y∈D∀x∈DR\exists y\in D\forall x\in D R는 거짓입니다.

명시적 빈 집합에 관한 규약입니다. 일차 논리 구조의 기저 영역을 비어 있지 않게 요구하는 교재 규약과 섞지 마세요. 빈 집합 위의 전칭이 증인을 새로 만드는 것은 아닙니다.

평가의 빈 하위집단도 보편 조건을 공허하게 만족할 수 있습니다. 집단 크기를 보고하여 관측된 보장 범위로 오해하지 않게 해야 합니다.

증인은 구성적 정보다

유한 모형에서는 성공 후보를 돌려주어 존재를, 실패 원소를 돌려주어 전칭 실패를 확인할 수 있습니다. 무한 정의역의 모든 문장을 후보 열거로 결정할 수는 없습니다. 구성이나 불가능 논증이 검색창 밖의 정보를 제공합니다.

y(x)=x는 등호의 입력별 증인 함수입니다. 공통 스칼라 y는 다른 종류의 대상입니다. 관측에 따라 달라지는 정책과 미리 고정한 행동 하나를 구분하는 데도 같은 관점이 유용합니다.

그림 읽기

행은 x, 열은 y입니다. T/F가 술어를 직접 표시합니다. 표에는 각 행의 가장 작은 증인이 나오고 공통 증인에는 모두 참인 열만 나옵니다. 빈 격자는 빈 집합이라고 표시하며 성공 칸을 꾸며내지 않습니다.

술어 코드 0은 등호, 1은 초과, 2는 이상입니다. y를 x와 비교합니다. 값을 해석하기 전에 R을 다시 적어보세요.

연습과 근거

  1. D={0,1}, 등호의 혼합 양화 문장은? 답: ∀x∃y\forall x\exists y만 참입니다.
  2. ∃y∀xR\exists y\forall xR를 부정하세요. 답: ∀y∃x¬R\forall y\exists x\neg R입니다.
  3. 비어 있지 않은 유한 D에서 y≥xy\ge x의 공통 증인은? 답: 최대 원소입니다.
  4. ‘모든 허용 오차마다 충분한 표본 크기가 있다’를 양화하고 어떤 선택이 다른 값에 의존하는지 설명하세요.

보충은 MIT Mathematics for Computer Science 읽기 자료를 참고하세요. 이 유한 모형은 무제한 정의역에 대한 증명이 아닙니다.

CHECK YOUR UNDERSTANDING

설명할 수 있나요?

실험 설정과 무관한 기준 예제를 묻습니다. 답을 고르고 설명을 확인해보세요.

1. D={0,1,2}, R는 y=x일 때 참인 것은?
2. ¬∀x P(x)는?

선택한 답과 학습 표시는 이 브라우저에 저장됩니다. 다시 풀거나 표시를 해제할 수 있습니다.