왜 명제논리만으로는 부족한가

03편의 명제논리는 $p$, $q$처럼 이미 완성된 문장 단위로만 다룬다. 그런데 “모든 사람은 죽는다”, “어떤 정수는 소수다”처럼 범위가 있는 대상에 대한 주장은 $p$, $q$ 하나로 표현할 수 없다. “모든”과 “어떤”이라는 표현이 명제 안에 숨어 있기 때문이다. 이 표현을 정확히 기호로 다루는 것이 이 편에서 배우는 술어논리(predicate logic)다.

쉽게 말하면: 명제논리가 완성된 문장 하나하나를 다룬다면, 술어논리는 “빈칸이 있는 문장”에 “모든” 또는 “어떤”을 붙여 완성된 명제로 만드는 방법을 다룬다.

술어와 개체 영역

술어(predicate)는 변수를 포함해서 그 변수 값이 정해지기 전까지는 참·거짓을 판정할 수 없는 문장이다. “$x$는 짝수다”를 $P(x)$로 표기하면, $x$에 어떤 값을 넣느냐에 따라 참·거짓이 달라진다. $P(4)$는 참이고, $P(5)$는 거짓이다.

술어가 다루는 변수 $x$가 가질 수 있는 값의 범위를 개체 영역(domain of discourse, 논의 영역)이라 부른다. 예를 들어 $x$가 정수 전체를 범위로 한다고 정하면, $P(x)$: “$x$는 짝수다”라는 술어는 정수 전체 중 짝수인지 아닌지를 판정하는 규칙이 된다. 개체 영역을 명시하지 않으면 정량자를 붙인 명제의 참·거짓이 애매해지므로, 문제에서 항상 개체 영역이 무엇인지 먼저 확인해야 한다.

변수가 두 개 이상인 술어도 가능하다. $Q(x, y)$: “$x$는 $y$보다 크다”처럼 변수를 여러 개 받는 술어는 각 변수의 개체 영역을 각각 정해 주어야 한다.

전칭 정량자와 존재 정량자

술어 앞에 정량자(quantifier)를 붙이면 비로소 참·거짓이 정해지는 완전한 명제가 된다.

전칭 정량자(universal quantifier) $\forall x\, P(x)$는 “개체 영역의 모든 $x$에 대해 $P(x)$가 참이다”라는 뜻이다. 개체 영역이 유한집합 $\{1, 2, 3\}$이라면, $\forall x\, P(x)$는 $P(1) \land P(2) \land P(3)$과 같은 뜻이 되어, 개체 영역의 원소 개수만큼 논리곱으로 연결한 것과 같다.

존재 정량자(existential quantifier) $\exists x\, P(x)$는 “개체 영역에 $P(x)$가 참이 되는 $x$가 적어도 하나 존재한다”라는 뜻이다. 같은 개체 영역 $\{1, 2, 3\}$에서 $\exists x\, P(x)$는 $P(1) \lor P(2) \lor P(3)$과 같은 뜻이 되어, 개체 영역의 원소 개수만큼 논리합으로 연결한 것과 같다.

쉽게 말하면: $\forall$는 “예외 없이 전부 통과해야 참”, $\exists$는 “하나라도 통과하면 참”이라는 검사 방식이다.

예를 들어 개체 영역을 $\{2, 4, 6\}$으로 두고 $P(x)$: “$x$는 짝수다”라 하면, $2$, $4$, $6$ 모두 짝수이므로 $\forall x\, P(x)$는 참이다. 반면 개체 영역을 $\{2, 3, 4\}$로 바꾸면 $3$이 짝수가 아니므로 $\forall x\, P(x)$는 거짓이 된다. 이렇게 개체 영역이 무엇인지에 따라 같은 술어라도 전칭 명제의 참·거짓이 완전히 달라진다.

정량자의 부정 — 드모르간 법칙의 확장판

03편에서 배운 드모르간 법칙 $\neg(p \land q) \equiv \neg p \lor \neg q$을 개체 영역 전체로 확장하면, 정량자의 부정 규칙을 자연스럽게 이해할 수 있다.

이 두 규칙을 말로 풀면 다음과 같다. “모든 $x$에 대해 $P(x)$가 성립한다”의 부정은 “$P(x)$가 성립하지 않는 $x$가 적어도 하나 존재한다”이다. 반대로 “$P(x)$가 성립하는 $x$가 존재한다”의 부정은 “모든 $x$에 대해 $P(x)$가 성립하지 않는다”이다. 부정을 씌우면 전칭과 존재 정량자가 서로 바뀐다는 점이 드모르간 법칙과 정확히 같은 구조다.

이를 유한집합 $\{a_1, a_2\}$로 구체적으로 검산해 보자. $\forall x\, P(x)$는 $P(a_1) \land P(a_2)$와 같으므로, 이 전체를 부정하면 드모르간 법칙에 의해 다음과 같다.

그런데 $\neg P(a_1) \lor \neg P(a_2)$는 “$P$가 거짓인 원소가 적어도 하나 존재한다”는 뜻이므로, 정확히 $\exists x\, \neg P(x)$와 같은 의미다. 이렇게 정량자의 부정 규칙은 유한한 경우 드모르간 법칙을 그대로 적용한 결과임을 확인할 수 있다.

정량자 부정 예제 — 문장으로 직접 확인

개체 영역을 “이 반의 모든 학생”으로 두고, $P(x)$: “$x$는 숙제를 했다”라 하자.

• $\forall x\, P(x)$: “이 반의 모든 학생이 숙제를 했다.”
• $\neg \forall x\, P(x)$: “이 반의 모든 학생이 숙제를 한 것은 아니다” = “숙제를 하지 않은 학생이 적어도 한 명 존재한다” = $\exists x\, \neg P(x)$

여기서 흔히 저지르는 실수는 $\neg \forall x\, P(x)$를 “모든 학생이 숙제를 하지 않았다”($\forall x\, \neg P(x)$)로 잘못 바꾸는 것이다. “전부 다 한 것은 아니다”와 “전부 다 안 했다”는 전혀 다른 뜻이며, 앞의 것만 옳은 부정이다.

정량자 순서를 바꾸면 뜻이 달라진다

정량자가 두 개 이상 겹칠 때, 같은 종류의 정량자끼리는 순서를 바꿔도 뜻이 같지만, 서로 다른 종류의 정량자는 순서를 바꾸면 뜻이 달라진다. 이는 독학사에서 변별력이 큰 함정 유형이다.

개체 영역을 정수 전체로 두고 $Q(x, y)$: "$x + y = 0$"이라 하자.

이는 “모든 정수 $x$에 대해, $x + y = 0$을 만족하는 $y$가 존재한다”는 뜻이다. 이는 참이다. 어떤 정수 $x$를 고르든 $y = -x$로 두면 항상 $x + y = 0$이 성립하기 때문이다.

이는 ”$y$ 하나를 고정하면, 모든 정수 $x$에 대해 $x + y = 0$이 성립한다”는 뜻이다. 이는 거짓이다. $y$를 어떤 값으로 고정하더라도, $x$가 그 값과 다른 정수라면 $x + y = 0$이 성립하지 않기 때문이다(예를 들어 $y = 3$으로 고정하면 $x = 3$일 때만 성립하고 $x = 5$일 때는 성립하지 않는다).

이렇게 정량자 순서만 바꿨을 뿐인데 참·거짓이 뒤바뀌었다. $\forall x\, \exists y$는 “$x$마다 그에 맞는 $y$를 새로 골라도 된다”는 뜻이고, $\exists y\, \forall x$는 ”$y$ 하나로 모든 $x$를 동시에 만족시켜야 한다”는 훨씬 강한 조건이다.

쉽게 말하면: “모든 학생에게 각자 맞는 선생님이 있다”($\forall x\, \exists y$)와 “모든 학생을 동시에 맡는 선생님 한 명이 있다”($\exists y\, \forall x$)는 전혀 다른 주장이다.

논리적 추론과 타당성

논증(argument)은 몇 개의 전제(premise)로부터 하나의 결론(conclusion)을 이끌어내는 구조다. 논증이 타당하다(valid)는 것은 “모든 전제가 참이라고 가정했을 때, 결론도 반드시 참이 되는” 논리 구조를 가졌다는 뜻이다. 여기서 중요한 것은 타당성이 전제의 실제 내용이 사실인지와는 무관하다는 점이다. 전제가 실제로는 거짓이더라도, 그 전제들이 참이라고 가정했을 때 결론이 논리적으로 반드시 따라 나오면 그 논증은 타당하다.

자주 쓰이는 기본 추론 규칙은 다음과 같다.

전건긍정은 이름 그대로 “전건(가정) $p$를 긍정(참으로 확인)해서 결론 $q$를 얻는다”는 뜻이다. 예를 들어 “비가 오면 땅이 젖는다”($p \rightarrow q$)와 “비가 온다”($p$)가 모두 참이면, “땅이 젖는다”($q$)라는 결론이 타당하게 따라 나온다.

후건부정은 “후건(결론) $q$를 부정해서 전건 $p$의 부정을 얻는다”는 뜻이며, 이는 03편에서 배운 대우가 원래 명제와 등가라는 성질에 정확히 근거한다. “비가 오면 땅이 젖는다”인데 “땅이 젖지 않았다”($\neg q$)면, 대우($\neg q \rightarrow \neg p$)에 의해 “비가 오지 않았다”($\neg p$)가 타당하게 따라 나온다.

타당한 논증과 부당한 논증 구분하기

추론 규칙과 겉모습이 비슷하지만 타당하지 않은 추론도 있다. 대표적으로 다음 두 가지 오류를 구분해야 한다.

“비가 오면 땅이 젖는다”($p \rightarrow q$)를 예로 들면, “땅이 젖었다”($q$)고 해서 반드시 “비가 왔다”($p$)고 결론지을 수 없다. 스프링클러 때문에 땅이 젖었을 수도 있기 때문이다. 이것이 후건긍정의 오류다. 이 두 오류는 진리표로도 확인할 수 있다. $p \rightarrow q$, $q$가 모두 참이지만 $p$가 거짓인 조합(표에서 $p$가 F, $q$가 T인 행)이 실제로 존재하므로, 전제가 모두 참이어도 결론이 반드시 참이 되지는 않는다. 즉 타당하지 않다.

논증의 타당성을 진리표로 판정하기

논증 ”$p \rightarrow q$, $\neg p$, 따라서 $\neg q$“(전건부정의 오류)가 실제로 부당한지 진리표로 확인해 보자.

논증이 타당하려면, 전제인 $p \rightarrow q$와 $\neg p$가 모두 참인 모든 행에서 결론 $\neg q$도 반드시 참이어야 한다. 표에서 $p \rightarrow q$가 참이고 $\neg p$도 참인 행은 세 번째 행($p$=F, $q$=T)과 네 번째 행($p$=F, $q$=F) 두 개다. 그런데 세 번째 행에서는 $\neg q$가 거짓이다. 즉 전제가 모두 참인데 결론이 거짓인 경우가 존재하므로, 이 논증은 타당하지 않다.

이 절차를 일반화하면 다음과 같다.

자주 틀리는 점

• $\neg \forall x\, P(x)$를 $\forall x\, \neg P(x)$로 잘못 바꾸는 실수: 옳은 부정은 $\exists x\, \neg P(x)$다. “전부 다 그런 것은 아니다”와 “전부 다 그렇지 않다”는 다른 뜻이다.
• $\forall x\, \exists y$와 $\exists y\, \forall x$를 같은 뜻으로 취급하는 실수: 정량자의 종류가 다를 때 순서를 바꾸면 참·거짓이 달라질 수 있다. 순서를 바꿀 수 있는 것은 같은 종류의 정량자끼리뿐이다.
• 후건긍정·전건부정의 오류를 타당한 추론으로 착각하는 실수: 이 두 형태는 전건긍정·후건부정과 겉모양이 비슷하지만 진리표로 확인하면 명백히 부당하다.
• 논증의 타당성을 전제의 실제 사실 여부로 판단하는 실수: 타당성은 “전제가 참이라고 가정했을 때 결론이 반드시 참인가”를 따지는 논리 구조의 문제이지, 전제가 실제 세계에서 사실인지와는 별개다.

핵심 정리

• 술어 $P(x)$는 변수가 정해지기 전까지 참·거짓이 정해지지 않으며, 개체 영역을 함께 정해야 정량자를 붙인 명제의 참·거짓이 정해진다.
• 전칭 정량자 $\forall x\, P(x)$는 개체 영역 전체를 논리곱으로, 존재 정량자 $\exists x\, P(x)$는 논리합으로 묶은 것과 같다.
• 정량자의 부정은 $\neg \forall x\, P(x) \equiv \exists x\, \neg P(x)$, $\neg \exists x\, P(x) \equiv \forall x\, \neg P(x)$로, 부정을 씌우면 정량자 종류가 서로 바뀐다.
• 서로 다른 종류의 정량자가 겹칠 때는 순서를 바꾸면 뜻이 달라질 수 있다($\forall x\, \exists y$와 $\exists y\, \forall x$는 다르다).
• 전건긍정·후건부정·가언삼단논법·선언삼단논법은 타당한 추론 규칙이고, 후건긍정의 오류·전건부정의 오류는 겉모습만 비슷한 부당한 추론이다. 타당성은 진리표로 전제가 모두 참인 행에서 결론도 참인지 확인해 판정한다.

마무리 복습

참고 자료

• 국가평생교육진흥원 독학학위제 - 이산수학 출제기준  — 술어논리·정량자·논리적 추론 항목이 출제기준에서 어떻게 다뤄지는지 확인할 수 있는 공식 자료.