술어와 양화사

'모든 사용자에게 추천 상품이 있다'와 '모든 사용자가 좋아하는 상품이 있다'는 서로 다른 요구사항입니다. 명제와 논리 연산을 바탕으로 변수의 범위와 양화사 순서가 의미를 어떻게 바꾸는지 익힙니다.

정의역부터 정하기

$P(x)$를 'x는 짝수이다'라 합시다. x=4이면 참이고 x=5이면 거짓입니다. 정의역을 정수로 잡는지, 자연수로 잡는지에 따라 '모든 x'가 가리키는 대상이 달라집니다. 자유변수는 값을 정하지 않은 변수이고, 양화사에 묶이면 해당 범위의 원소를 뜻합니다.

$\forall x\,P(x)$는 정의역의 모든 원소에서 P가 참이라는 뜻입니다. $\exists x\,P(x)$는 적어도 하나에서 참이라는 뜻입니다. 존재가 '정확히 하나'는 아닙니다. 유일성을 말하려면 하나가 존재하고 그 성질을 가진 모든 원소가 그 하나와 같다고 별도로 주장해야 합니다.

순서는 요구사항을 바꾼다

정수에서 $R(x,y)$를 $y=x+1$이라 두면 $\forall x\exists y R(x,y)$는 참입니다. x를 정한 뒤 그보다 1 큰 y를 고르면 됩니다. $\exists y\forall x R(x,y)$는 거짓입니다. 하나의 y가 모든 정수의 다음 수가 될 수는 없습니다. x=0에서 y=1이어야 하지만 x=1에서 y=2이어야 해서 충돌합니다.

같은 종류의 양화사 두 개는 순서를 바꿔도 의미가 같지만, 전체와 존재를 섞으면 함부로 바꾸지 않습니다. 검색이나 데이터베이스 질의에서도 '모든 조건마다 다른 결과가 존재'와 '한 결과가 모든 조건을 만족'을 구분해야 합니다.

부정은 양화사까지 뒤집는다

$$\neg\forall x P(x)\equiv\exists x\neg P(x),\qquad \neg\exists x P(x)\equiv\forall x\neg P(x).$$

'모든 요청이 성공했다'의 부정은 '실패한 요청이 적어도 하나 있다'입니다. '모든 요청이 실패했다'가 아닙니다. '어떤 요청이 성공했다'의 부정은 '성공한 요청이 하나도 없다'입니다.

$\neg\forall x\exists y R(x,y)$를 순서대로 부정하면 $\exists x\forall y\neg R(x,y)$입니다. 정수 덧셈 예에서는 '어떤 x에 대해서는 아무 y도 x의 다음 수가 아니다'라는 거짓 명제가 됩니다.

조건이 붙은 전체 명제 $\forall x(P(x)\to Q(x))$의 반례는 P가 참이고 Q가 거짓인 x입니다. P가 거짓인 x를 고르면 반례가 되지 않습니다. 이는 조건명제의 진리표와 같은 원리입니다.

스스로 풀어보기

문제 1. '모든 파일에 대해 그 파일을 읽을 수 있는 사용자가 있다'의 부정을 쓰세요.

힌트: 전체 파일 중 한 파일을 찾고, 모든 사용자에게 읽기 불가를 요구합니다.

풀이: '읽을 수 있는 사용자가 하나도 없는 파일이 있다'입니다. $\forall f\exists u R(u,f)$의 부정은 $\exists f\forall u\neg R(u,f)$입니다. 사용자마다 읽지 못하는 파일이 다르다는 주장과 구분합니다.

문제 2. 정의역이 정수일 때 $\exists x(x^2=2)$와 $\forall x(x^2\ge0)$를 판단하고, 정의역을 실수로 바꾸면 무엇이 달라지는지 쓰세요.

풀이: 정수에서 제곱이 2인 정수는 없으므로 첫 식은 거짓이고 제곱은 항상 0 이상이라 두 번째는 참입니다. 실수로 바꾸면 $x=\sqrt2$가 있으므로 첫 식도 참입니다. 기호가 같아도 정의역이 다르면 명제의 진릿값이 달라집니다.

존재·전체 판단이 헷갈리면 실제 원소 두세 개로 요구조건을 풀어 쓴 뒤 존재증명과 반례에서 증명 방법을 익힙니다.