명제 논리

명제 논리(수리 논리)는 수학의 표현 수단으로, 여러 용어와 온갖 수학 정리에서 만날 수 있다.

논리는 무엇을 다루는가

논리학은 추론, 참과 거짓, 증명할 수 있는지와 반박할 수 있는지를 다루는 학문이다. 이때 논리가 관심을 두는 것은 말의 형식뿐이다. 구체적으로 무엇을 말하는지, 심리적으로 어떻게 해석되는지 같은 것은 다루지 않는다.

예를 들어 “2는 짝수이고 홀수이다”라는 문장이 있으면, 2는 홀수가 아니므로 문장 전체가 참이 아니라고 판단할 수 있다. 일반적으로 논리는 이런 문제를 다룬다.

명제

명제 논리의 기본은 당연히 명제이다. 참인지 거짓인지를 판별할 수 있는 문장을 명제라고 한다. 간단한 명제의 예는 다음과 같다.

• 에베레스트산은 세계에서 가장 높은 산이다.
• 자연수 5는 홀수이다.
• HTML은 프로그래밍 언어이다.
• 2 더하기 3은 6이다.

모두 명제이다. 앞의 두 문장은 참이고 뒤의 두 문장은 거짓이지만, 어느 쪽이든 명제이다. 반면 의문문이나 참, 거짓을 하나로 정할 수 없는 문장은 명제가 아니다. 예를 들면 다음과 같다.

• 내년에도 에베레스트산이 세계에서 가장 높은 산일까?
• 초록색이 가장 아름다운 색이다.

첫 번째 문장은 의문문이므로 명제가 될 수 없다. 두 번째 문장은 참인 명제인지 거짓인 명제인지 판별할 수 없다. 이런 문장을 가설(추측)이라고 한다.

고전적인 수리 논리는 “민준이는 키가 크다”나 “철수는 노래를 잘 부른다”처럼 모호한 문장을 잘 다루지 못한다. 이런 문장은 모호함을 다루도록 만들어진 퍼지 논리 같은 분야에서 다루는 편이 낫다.

원자 명제

첫 번째 절에서 “2는 짝수이고 홀수이다”라는 명제를 예로 들었다. 이 명제는 실제로는 두 개의 짧은 명제 “2는 짝수이다”와 “2는 홀수이다”를 이은 것이므로 합성 명제라고 할 수 있다. 두 명제는 논리 연결사 “그리고”로 이어져 있다.

원자 명제는 더 이상 나눌 수 없는 명제, 어떤 의미에서 가장 단순한 진술이다. 앞에서 든 명제의 예는 사실 모두 원자 명제였다.

• 에베레스트산은 세계에서 가장 높은 산이다.
• 자연수 5는 홀수이다.
• HTML은 프로그래밍 언어이다.
• 2 더하기 3은 6이다.

앞으로 원자 명제는 알파벳 소문자, 흔히 p, q, r, … 같은 문자로 나타내고 명제 변수라고 부른다.

논리 연결사

수리 논리에서는 몇 가지 논리 연결사를 쓴다. 기본이 되는 것은 다음 네 가지 이항 연결사이다.

• p ∧ q는 두 명제의 논리곱이고, “명제 p 그리고 명제 q”라고 읽는다.
• p ∨ q는 두 명제의 논리합이고, “명제 p 또는 명제 q”라고 읽는다.
• p ⇒ q는 조건문(함의)이고, “명제 p이면 명제 q이다”라고 읽는다.
• p ⇔ q는 동치이고, “명제 p일 때, 그리고 그때에만 명제 q”라고 읽는다(p는 q이기 위한 필요충분조건이다).

논리 연결사를 쓴 구체적인 예는 다음과 같다.

• 서울 도심에 비가 오고 동시에 해가 비친다. (논리곱)
• 서울 도심에 비가 오거나 또는 해가 비친다. (논리합)
• 우리 학교 급식은 세계 최고이고 우리 담임 선생님은 최고의 선생님이다. (논리곱)
• 아이스크림을 너무 많이 먹으면 곧 배탈이 난다. (조건문)
• 수 x가 4로 나누어떨어지면 2로도 나누어떨어진다. (조건문)
• 영희는 친절하고 똑똑하다. (논리곱)
• 가수는 노래를 잘할 때 그리고 그때에만 성공한다. (동치)
• 비가 오지 않으면 젖지 않는다. (조건문)
• 철수가 노래를 잘 부른다면 나는 웃음의 신이다. (조건문)

흔히 쓰는 논리 연결사로 부정도 있다. 부정은 프라임을 붙여 p′으로 쓰거나 기호 ¬p로 나타낸다(한국 교과서에서는 ∼ p로 쓴다).

논리식

명제 변수(원자 명제)와 논리 연결사를 이용하면 더 복잡한 명제를 만들 수 있는데, 이를 논리식이라고 한다. 앞의 목록에 있던 예는 사실 모두 논리식이었다. 예를 들어 “서울 도심에 비가 온다”와 “해가 비친다”라는 두 원자 논리식을 논리 연결사로 이었기 때문이다. 첫 번째 예에서는 “그리고”로 이어 “서울 도심에 비가 오고 동시에 해가 비친다”라는 논리식을 얻었고, 두 번째 예에서는 “또는”을 써서 “서울 도심에 비가 오거나 또는 해가 비친다”라는 논리식을 얻었다.

논리식은 형식적으로 다음과 같이 정의한다.

• 모든 명제 변수(원자 명제)는 논리식이다(더 정확히 말하면 원자 논리식이다).
• A와 B가 논리식이면 ¬A, (A ∧ B), (A ∨ B), (A ⇒ B), (A ⇔ B)도 논리식이다.

이 정의는 이치에 맞는다. 첫 번째 항목에 따라 모든 원자 명제는 논리식이기도 하다. 따라서 “서울 도심에 비가 온다”와 “해가 비친다”라는 두 원자 명제가 있으면 논리식도 두 개 있는 셈이다. 이제 두 번째 항목을 적용하면 예를 들어 다음과 같이 더 복잡한 논리식을 만들 수 있다.

• 서울 도심에 비가 오고 동시에 해가 비친다.
• 서울 도심에 비가 오거나 또는 해가 비친다.
• 서울 도심에 해가 비치면 비가 온다.
• 서울 도심에 해가 비칠 때 그리고 그때에만 비가 온다.

물론 논리식이 반드시 참일 필요는 없다. 이렇게 해서 새로운 논리식을 여러 개 얻었으니, 이것들로 더 복잡한 논리식을 만들 수 있다. A=“서울 도심에 해가 비치거나 비가 온다.”(이것이 논리식이라는 것은 이미 알고 있다), B=“무지개가 보인다”(이번에도 서울 도심이라고 하자. 매번 반복하지 않기 위해서이다)라고 하면 새로운 논리식을 만들 수 있다. 문장 속의 괄호는 연결사가 어느 부분에 걸리는지를 나타낼 뿐이다.

• A ∧ B: (서울 도심에 해가 비치거나 비가 온다) 그리고 (무지개가 보인다).
• A ∨ B: (서울 도심에 해가 비치거나 비가 온다) 또는 (무지개가 보인다).
• A ⇒ B: (서울 도심에 해가 비치거나 비가 오면) (무지개가 보인다).
• A ⇔ B: (서울 도심에 해가 비치거나 비가 올 때) 그리고 그때에만 (무지개가 보인다).

이것들도 모두 논리식이다. 따라서 이 가운데 하나를 골라 다른 논리식과 다시 이을 수 있다. 그러면 “서울 도심에 해가 비치거나 비가 오거나 무지개가 보이면, 무지개가 보일 때 그리고 그때에만 해가 비치거나 비가 온다”처럼 괴상한 문장도 만들 수 있다.

다음 글에서는 논리식의 참, 거짓을 살펴본다.