Math Logic Operation

수리논리의 세계 로 돌아가기

명제와 명제의 연산

숨어있는 논리를 기호로 나타내보기

일상에서 일어나는 문장이나 수학적인 문장은 기호로 표시할 수 있다. 모든 문장들을 기호로 나타내려 하지 않아도 된다. 습관적으로 쓰는 방식으로 하면 그 문장의 얼개자체를 보기가 어렵다. 다 덜어내고 논리적 구조만 볼 수 있을까? 퍼즐을 맞추기위해서는 그 퍼즐의 구조를 파악하는 것이 중요하다. 또 우리 아래로 흐르는 하수도가 어디서 어디로 흐르는지 알기 위해 하수구 뚜껑을 열고 들어가 찾아다닌다면 아는 것보다는 하수도을 설계한 그림을 보면 더 쉽게 구조를 파악할 수 있다. 그것은 실재를 기호로 바꾸어 본 것이다. 수리논리에서 주로 쓰는 핵심적인 논리적 접속사들에 대해서는 이미 앞에서 한번 밝혔다.

A 그리고 (and) B , A 또는(or) B, A 이면 B 다(if A, then B), A 가 아니다.(not A )

들이다. 왜 그것만 있겠는가? 하지만, 그것으로 충분하다는 것을 곧 알 수 있다. 실은 그것보다 더 적어도 된다. 마치 수의 세계에서 덧셈, 뺄셈, 곱셈, 나눗셈의 연산이 있듯이 문장을 대상으로 하는 수학의 영역인 수리논리에서도 그것들은 기본 연산의 역할을 한다. 이것들 각각에 대해서 순서대로 다음의 기호를 쓸 것이다.

$A\And B,\ A\lor B,\ A\rightarrow B,\ \neg A$

위의 접속사나 그것의 조합으로 된 논리적 접속사로 이어지지 않은 가장 단순한 문장이 주어졌다고 하자. 그런 문장들은 대개 ' A 는 B 다'라는 형식을 띤다. 물론 현실에서는 그렇게 재미없게 드러나지는 않는다. 그보다 복잡해 보일 수도 있고 그보다 단순하게 드러난다. 예를들어, " 어제 '킹콩'이란 영화를 봤다며?" 라고 물을 때, "응" 이라고 한다면, 그때, "응" 이라는 한마디에는 이미 "나는 어제 킹콩이란 영화를 봤다"라는 다소 긴 단순한 문장이 내포되어 있다. 또 "지난 주말에 어떤 산에 다녀왔어?" 라고 물을 때, "금강산" 이라고 한다면, 그 말안에는 "나는 지난 주말에 금강산에 다녀왔다"라는 문장을 말한 것이다. 어떻든 문장에서 가장 중요한 역할을 하는 단어는 생략되지 않는다. 다만 반복되거나 없어도 되는 말은 사람들이 생략되곤 하는 것이다.

이런 단순한 문장들이 논리적 접속사로 뭉쳐져서 새로운 문장이 된다. "지난 주말에는 금강산에 다녀오고 어제는 킹콩이란 영화를 봤어" 라는 새로운 문장이 등장한 것이다. 또

비가 온다. 오늘은 수요일이다. 나는 너에게 빨간 장미를 선물한다.

라는 문장을 엮을 수도 있는데 예를들어 예전의 노래가사처럼

비가 오는 수요일엔 빨간 장미를 그대에게 주고 싶어

라고 할 수 있는 것이다. 이 문장은 "비가 온다" 그리고 "수요일이다" 그러면 "빨간 장미를 선물한다"로 뭉쳐져 새로운 문장이 된 것이다.

(비가 온다 $\And$ 수요일이다) $\rightarrow$ 빨간 장미를 선물한다.

로 바꾸어 쓸 수 있다. 좀더 복잡한 문장도 이렇게 바꾸어 볼 수 있다. 서정주의 유명한 시 '푸르른 날'이다.

눈이 부시게 푸르른 날은
그리운 사람을 그리워하자

저기 저기 저 가을 꽃 자리
초록이 지쳐 단풍 드는데

눈이 내리면 어이 하리야
봄이 또 오면 어이 하리야

내가 죽고서 네가 산다면!
네가 죽고서 내가 산다면!

눈이 부시게 푸르른 날은
그리운 사람을 그리워하자.

이 문단을 '눈이 부시게 푸르른 날이다'를 A 로, ' 그리운 사람을 그리워한다'를 B 로, '초록이 지친다' 를 C 로, '단풍이 든다' 를 D 로 바꾸면,

$A\rightarrow B,\ C\rightarrow D$

와 비슷한 문장을 담고 있다. 하지만 이 시에서 보듯 기호로 옮기기 힘든 문장 구조가 있을 뿐더러, 기호로 옮길 수 있다고 해도 썩 마음에 들지 않고 의심이 남을 수도 있다. 그래서 이처럼 모호한 경우는 없다고 전제한 다음, 그것의 진리값을 분명하게 제시할 수 있는 문장만을 앞으로 볼 것이다. 그러나 '분명하다'는 것 자체가 아직 모호한 개념이다. 그냥 우리는 참이나 거짓 또는 다른 어떤 진리값이 있다고 할 때 그것을 말할 수 있는 문장이라고 하겠다. 그 문장이 참이냐 거짓이냐, 또는 참 거짓이 아닌 다른 진리값 중 어느것을 갖느냐 하는 것은 그리 중요하지 않다. 우리의 관심은 다시한번 말하지만, '논리'이기 때문이다.

참 거짓이나 진리값을 줄 수 있는 단순한 문장의 예를 보자.

1 = 1 , 태양은 은하계의 별이다. 그 곰이 (시속1km의 속도로) 걸어가더라. $\pi$ 안에는 0 이 1000개 연속해서 나오는 구간이 있다.

또 앞에서 든 예를 보자. 모든 사람은 죽는다. 소크라테스는 사람이다. 그래서 소크라테스도 언젠가는 죽기 마련이다. 라는 문장의 논리적 구조만 보도록 하자. '사람'의 집합을 X로 하고, ‘모든’을 $\forall$’로, ‘x 는 죽는다.’를 P(x)로, ‘소크라테스’는 a 로. 그럼 예1은 다음과 같이 바꿔 쓸 수 있을다.

${\frac {\forall x\in X\ P(x),\ a\in X}{P(a)}}$

이다. 간단히 기호로 표현되었다. 기호를 쓰는 것은 처음엔 익숙하지 않지만, 빠르게 쓰고 읽을 수 있고, 무엇보다 논리적 구조에 주목하여 실수나 불필요한 생각을 줄인다. 대수학자이자 상대성이론의 이론적 기초를 마련한 푸앙카레는 “수학은 시간의 낭비를 줄이도록 한다.”하고 하였다.

사실 그렇게 문장들을 기호로 표시하고 문장들의 구조와 논리에 초점을 맞추는 것은 수의 세계에서부터 늘 해오던 것이다. 마치 우리가 ‘수’에서 사과 셋, 딸기 셋, 아들 세 명과 같은 표현에서 물질적 대상들에 대해서는 잠시 접어두고 ‘셋’이라는 특성만 끄집어내어 ‘3’이라고 쓰고 수들의 변수에 대해 x 라고 했고 덧셈은 + 기호를 썻다. 그리고 모호하나마 집합을 나타낼 때 A, B 와 같은 기호를 쓰고 그 연산을 A $\cap$ B 로 쓰는 것과 다를 바 없다. 다만 여기서는 문장이나 문장의 연산을 대상으로하는 점이 다르다.

명제란 무엇인가?

앞에서 '올바른 추론'을 위해서 꼭 필요한 경우가 어떻게 문장을 구성했는지 분명히 밝히고 그것에 틀림이 없어야 한다. 문장을 기호로 한다면 이 규칙은 더 중요하다. 마치 일상 언어에도 문법이 숨겨져 있듯이 논리의 세계에도 문장을 만들 수 있는 법칙이 있다. 그것을 기호로 나타내었으면 그것의 의미를 부여할 수 있다. 어떤 단순 문장이 주어졌을 때 그것이 참이냐 거짓이냐를 따지는 것은 우리의 관심이 아니다. 문제의 핵심은 그것이 어떤 값을 가질 수 있고, 그 문장들이 논리적 접속사로 이어져 새로운 문장이 되거나 논리 법칙에 따라 새로운 문장을 논리적으로 유도했을 때 그것이 참이냐, 거짓이냐이다. 또 살아가는 동안 참과 거짓만으로 구분하기 어려운 경우도 자주 만나게 된다. 일상에서만 이런 일이 일어나는 것이 아니다. 수학에서도 '오랜 세월이 지나도록 아직 증명안된' 사실들이 많다. 어쨌건 이것은 참이거나 거짓이라는 입장을 고전주의적 입장이라고 한다. 진리값은 참과 거짓, 그리고 아직 증명안됨이라는 세가지 상태일 수도 있고, 더 나아가 진리값이 0 부터 1 사이의 연속일 수도 있다. 진리값이 세개 있는 경우의 진리표는 명제의 참거짓표 에서 더 자세히 보기로 한다.

일단 우리에게는 참과 거짓이라는 두가지 진리값만 있다고 하자. 참이면 1 을 거짓이면 0 을 쓰자. 참과 거짓을 말할 수 있는 문장을 대상으로 보고 있기 때문에 단순한 문장들은 0 이나 1 에 대응할 것이다. 어떤 진리값을 판단 또는 부여할 함수 f 가 있다면 문장들마다 0 또는 1 을 부여하는 함수라고 보는 것이다.

어떤 문장 A 의 의미를 해석하면 참이거나 거짓일 것이다. f(A) = 0 또는 f(A) = 1 이다.

이제 문장과 문장이 논리적 접속사로 연결되었을 때, 그것의 참거짓을 말할 차례다. 연산에 따라 그 결과가 어떤 값을 가지는지 밝혀주면 그 접속사의 성격을 드러내게 된다. 어떤 철학적 입장을 가지느냐에 따라 논리적 접속사를 평가하는 눈이 달라진다. 하지만 그 전에 '문장'이 과연 무엇인지 밝혀야 한다. 참-거짓을 드러내 표현될 수 있는 명제 변수들을 $p_{1},p_{2},p_{3},...$ 과 같은 기호로 쓰기로 하자. 앞으로는 참-거짓을 말할 수 있는 문장을 간단히 '명제' 라고 부르기로 하자. 명제들이라고 할 수 있는 것들을 정의해보자. 용어의 일관성을 위해서 변수와 식이라는 용어를 쓴다. $p_{1},p_{2},p_{3},...$ 와 같은 기호들은 명제를 나타내는 변수고 P, Q 는 명제식을 나타낸다고하자.

정의 (명제 식) : 모든 명제 변수는 명제식이다. 그리고 $P,Q$ 가 명제식이면 $P\And Q,\ P\lor Q,\ P\rightarrow Q,\ \neg P$ 도 명제식이라 한다.

앞으로는 단순 명제를 나타내는 변수를 $p_{1},p_{2},p_{3},...$ 로 쓰기로 약속한다. 이렇게 하면 우리에게 무엇이 명제인지 분명해졌다. 예를 들어 $p_{1},p_{2},p_{3}$ 들이 명제일 때,

$(\neg ((p_{1}\And p_{2})\rightarrow (p_{3}\lor \neg p_{1}))\rightarrow (p_{1}\And p_{3}))$

라고 표현된 문장은 명제다. 필요한 곳에 괄호를 쳤다고 본다. 그럴 때, 괄호가 깊이 있는 곳으로부터 되돌이하면서 보면 확실하다. 괄호가 깊이 있는 문장

$p_{1}\And p_{2}$ 도 명제고 , $\neg p_{1}$ 도 명제고, 따라서 $p_{3}\lor \neg p_{1}$ 도 명제일 뿐더러, $(p_{1}\And p_{2})\rightarrow (p_{3}\lor \neg p_{1})$ 도 명제다.

그렇지만, 예를들어

$\neg ((p_{1}\And p_{2})\rightarrow \lor \neg p_{1}),\ p_{1}\neg ,\ \rightarrow (p_{1}\And p_{3})$

같은 문장들은 명제일 수 없다.

명제들의 비교 관계

명제들의 연산은 보았고, 이제 두 명제가 같다라는 논리적 관계를 정의해주어야 할 때다. 두 명제 'P 와 Q 가 같다'라는 무엇일까? 수나 식, 집합의 세계에서 정의할 때는 어땠나? 예를들어

• '2 + 5 = 7' 인 경우 2 + 5 와 7 이 같다는 것을 말한다. 실제로 2 는 1 + 1 이고 5 는 1 + 1 + 1 + 1 + 1 이고 7 은 1 + 1 + 1 + 1 + 1 + 1 + 1 이니 같은 것이다.
• 2x + 3 = 5x - 3 과 같은 경우는 x 에 어떤 원소를 넣어도 양쪽 항에 똑같이 넣어준다면 위의 식은 같은 참-거짓값이 나온다라는 말이다. 참인 경우는 x = 2 일 때 밖에 없다.
• 두 집합 A, B 에 대하여 A = B 라는 것은 '집합 A 의 원소와 집합 B 의 원소가 겹친다' 라는 뜻이다. 달리 말하면 A 집합의 모든 원소는 B 에도 있고 그 역도 성립한 경우다.

마찬가지로 명제들끼리의 같음도 아래와 같이 정의하는 것이 합리적이다.

정의 (명제의 같음 $\equiv$ )  : 명제 변수를 갖는 두 명제식 $P(p_{1},p_{2},\dots ,p_{n}),Q(p_{1},p_{2},\dots ,p_{m})$ 들이 명제 변수들의 진리값이 같은 경우 함수값이 같을 때 두 명제식은 같다고 하고 기호로 $P\equiv Q$ 를 쓴다.

예를들어, 단순 명제들일 경우, P 와 Q 가 같다는 것은 P 가 참이면 Q 도 참이고 그 역도 성립한다는 말이다.또 $P(p_{1},p_{2})$ 가 ' $(p_{1}\And p_{2})\rightarrow p_{1}$ ' 의 꼴이고 $Q(p_{1},p_{2})$ 가 ' $(p_{1}\And p_{2})\rightarrow p_{2}$ ' 의 꼴이라고 해보자. P 와 Q 의 두 명제가 있으므로 가능한 진리값의 경우는 네가지다. $p_{1},p_{2}$ 가 모두 참인 경우, 둘 다 거짓인 경우, 하나는 참, 하나는 거짓인 경우다. 각각의 경우에 P 와 Q 가 같은 참값을 가질까 ? 이 정의를 완결짓기 위해서는 먼저 논리적 접속사(연산)들이 어떤 진리값을 갖는지 정의해 주어야 한다.

논리 연산들이 어떤 값을 갖건, '같음'의 성질이 수리논리의 세계에서도 통하려면 아래의 기본 성질을 만족할 것이다. 명제식 P, Q , R 에 대해 다음의 성질을 만족한다.

(reflexive) $P\equiv P$

(symmetry) $P\equiv Q$, 이면 $Q\equiv P$

(transitive) $P\equiv Q,Q\equiv R$, 이면 $P\equiv R$

논리적 접속사들의 성격

지금까지는 '그리고' '또는' '..이면 ..이다.' '..가 아니다'와 같은 접속어를 일상적인 뜻으로 쓰고 있다. 하지만, 자연수나 정수, 유리수 세계에서 그랬듯 거기 그대로 머물러 있어야할 어떤 논리적 근거도 없다. 뿐만아니라 수학적 상상력의 날개를 펼치지 못하도록 붙들어둔다. 일상에서 흔히 발생하는 논리적 접속사들을 대표적으로 넷을 뽑긴 했지만, 아직 그것들이 구체적으로 어떤 구실을 하고 성격은 무엇인지 아무것도 말하지 않았다 ! 이 접속사들이 구체적으로 어떤 성격을 가지는지 말하는 쉬운 방법 중 하나가 바로 진리표로 성격을 드러내주는 것이다.

'P 그리고 Q', 'P 또는 Q', 'P 가 아니다'

• 그리고 ( $\And$ ) : P 라는 문장이 참이고 Q 라는 문장도 참일 때, P 이고 Q 라는 문장도 참이다.
• 아니다 ( $\neg$ ) : 참인 문장 P 에 대해 'P 가 아니다'라는 문장은 거짓이 되고, P 가 거짓이었다면, 'P 가 아니다'라는 문장은 거짓이 된다.
• 또는 ( $\lor$ ) : P 라는 문장과 Q 라는 문장의 둘 중 하나라도 참일 때, P 또는 Q 라는 문장도 참이다.

참과 거짓만 있는 세계에서는 이렇게 참값을 부여하는 것은 일상적인 의미에서의 접속사를 생각해도 충분히 합리적이다.

'P 이면, Q 이다'

이런 구조를 가진 문장들의 예를 몇개 들어보자.

비가오면 우산을 쓴다. 보일러를 켜두면 방이 따듯하다. 1 + 1 = 2 면, 1 + 2 = 3 이다. $\pi$ 가 초월수면 무리수다.

이 경우 어떻게 참값을 부여하는 것이 합리적일까? 기대하는 대로 P 가 참이고 Q 도 참일 때는 'P 이면 Q 다'라는 문장이 참이다. 그런데 만약 P 가 거짓이면 ? 예를들어 ' 1 이 허수면 $1^{2}$ 은 실수다.' 라는 문장은 참일까, 거짓일까? 또는 1 이 허수면 2 도 허수다. 와 같은 문장은 ? 답하기가 간단하지 않다. 하지만 '비가 오면 우산을 쓴다'라는 문장이 있을 때, 비가 오는데, 우산을 쓰지 않았다면 그것은 가짓이 된다. 하지만, 비가 오지 않았는데 우산을 썼다면 그 문장이 거짓이라고 할 수 있을까? 거짓이라고 하기 어렵다. 또

x 가 4 로 나뉘면 x 는 2 로 나뉜다.

라는 문장을 보자. 이것은 자연수 세계에서 분명한 법칙이다. 4로 나뉘는 모든 수들은 2 로 나뉠 수 밖에 없으니까. 그렇다면 그 수들에 2, 3, 4 를 대입해보자.

'2 가 4 로 나뉘면 2 는 2 로 나뉜다.' , '3 이 4 로 나뉘면, 3 은 4 로 나뉜다.' '4 가 4 로 나뉘면 4 는 2 로 나뉜다'

가 될 것이다. 첫번째는 조건부분이 거짓이고 결론 부분이 참인 경우, 두번째는 조건부분도 결론 부분도 모두 거짓이다. 세번째는 조건부분도 결론 부분도 모두 참이다. 앞에서 'x 가 4 로 나뉘면 2 로 나뉜다'는 문장을 참으로 받아들였듯이 여기서 그것의 구체적인 경우인 세 문장도 참이라고 받아들이는 것은 합리적이다.

앞에서 만약 어떤 수 a 가 있어서 a 가 4 로 나뉘는데, 2 로 안나뉘는 수가 존재하는 경우가 있다고 해보자. 바로 그런 수가 존재한다면 위의 문장 'x 가 4 로 나뉘면 2 로 나뉜다'는 거짓이 되는 반증인 셈이다. 이런 a 는 조건 부분이 참이고, 결론 부분이 거짓인 경우다. 따라서, 'P 이면, Q 이다'라는 문장이 거짓일 경우는 조건이 참이고 결론이 거짓일 때만 가능하다고 보는 것은 충분히 합리적이다.

여기서 'P 이면, Q 이다'의 문장은 평소 생각하는 것보다, 조건과 결론이 끈끈한 관계라는 것에 주의하자.

비가 오면 빨간 장미를 선물하겠다.

라는 문장에서 빨간 장미를 선물하기 위해서는 더 필요한 조건이 있을 수 있다. 눈이 먼 사람이 팔건, 눈이 좋은 사람이 팔건, 흑인이 팔건 백인이 팔건, 장미를 파는 꽃장수가 있어야 하고, 이 말을 한 사람은 장미를 마련할 돈이 있어야 한다. 비가오지 않아도 장미를 선물 할 수 있다. 눈이 부시게 푸르른 날 장미를 선물할 수도 있고, 회색 안개가 자욱한 날 장미를 선물할 수도 있다. 게다가 일상에서는 비가 올 때, 빨간 장미가 아니라 흰장미를 선물한 사람이 있다면 그를 거짓말쟁이라고 부르지는 않을 것이다. 하지만, 이 문장에서는 장미를 선물할 필요한 조건 중 하나로 '비가 오는' 것을 전제했다. 따라서 비가 오면 반드시 빨간 장미를 선물해야 이 문장은 참이 된다.

지금까지의 경우를 정리해서 표로 나타내보면 아래와 같다. 이런 표를 진리표라고 부르기로 하자. 두 변수가 있다면 네 경우가 가능하다.

함수표

P	Q	P $\And$ Q	P $\lor$ Q	P $\rightarrow$ Q	$\neg$ P
0	0	0	0	1	1
0	1	0	1	1	1
1	0	0	1	0	0
1	1	1	1	1	0

그렇다면 이제 $P\equiv Q$ 를 분명하게 이해할 수 있게 되었다. 예를들어 P 라는 문장이$p_{1}\And p_{2}$ 이고 Q 라는 문장이 $\neg (\neg p_{1}\lor \neg p_{2})$ 논리적으로 같기 위해서는 변수들 $(p_{1},p_{2})$ 의 진리값이 (1,1) 일때 P 와 Q 가 같은 값이 나와야 하고 (1,0) 일 때도 두 명제가 같은 진리값을, (0,1) 일 때도, (0,0) 일때도 마찬가지다. 실제로 그렇게 되는지 보자.

두 명제의 같음

$p_{1}$	$p_{2}$	$p_{1}\And p_{2}$	$\neg p_{1}$	$\neg p_{2}$	$\neg p_{1}\lor \neg p_{2}$	$\neg (\neg p_{1}\lor \neg p_{2})$
0	0	0	1	1	1	0
0	1	0	1	0	1	0
1	0	0	0	1	1	0
1	1	1	0	0	0	1

앞의 정의에서 논리적으로 같다는 것을 말할 때, 두 명제식이 꼭 같은 변수를 모두 가지고 있어야 하는 것은 아니다. 예를들어

$(\neg (p_{1}\lor p_{2})\rightarrow p_{1}\lor p_{2})\And p_{2}\ \equiv \ p_{2}$

의 경우 왼쪽 명제식은 오른쪽 명제식보다 많다. 이처럼 어느 한쪽이 다른 한쪽의 명제변수들을 모두 포함하고 있을 때도 같음 관계가 성립한다고 본다.

논리적으로 같은 명제들의 예를 명제의 참거짓표 에서 더 많이 볼 것이다. 또 진리표의 본질에 대해서도 더 자세히 보게된다.

수리 논리의 세계

자연수 세계나 집합론에서 했듯, 명제들의 세계도 이렇게 정의해줄 수 있다.

$<S;\equiv ;\And ,\lor ,\neg ,\rightarrow >$

하지만 이것은 지극히 초보적인 수리논리 세계의 세계다. 이처럼 단순하게 표시할 수 없는 광활하다. 일단 위의 언어만으로는 기초적인 수학의 언어도 다 표현할 수 없다. 예를들어

2 보다 큰 n 에 대해 $x^{n}+y^{n}=z^{n}$ 가 참이 되는 자연수의 세 쌍(x,y,z) 은 존재하지 않는다

라는 페르마의 마지막 정리의 경우 위의 명제논리의 언어로는 기호로 만드는 것이 충분하지 않다. 여기세는 '모든' '어떤 것이 존재한다' 라는 것을 기호로 할 수 있을 때 가능해진다. 이미 앞에서 예로들었지만, '모든(All)' 은 $\forall$ 로, '어떤 것이 존재한다(Exists)' 는 $\exists$ 로 쓰는 것이 보통이다. 이것들을 quantifier라고 부른다. 이제 위의 문장을 기호로 바꾸면

$\forall n\neg \exists x,y,z(x^{n}+y^{n}=z^{n})$

로 쓸수 있다. 위에서 n 은 2 보다 큰 모든 자연수를, x, y, z 도 자연수라고 하자. 2 차 방정식을 예로 들어보자.

$\exists x(x^{2}-5x+6=0)$

우리의 언어에 변수들과 변수들이 이루는 항, 그리고 $\forall ,\exists$ 들이 참여한다. 그렇다면 이런 문장들의 정의도 확장해야 한다. 이에 대해서 더 깊이 들어가지는 않겠지만, 이 언어는 수학의 언어를 기호화하는데 충분히 풍요로운 언어다. 나중에 기회가 있으면 보기로...

Note

Math : Math글쓰기 | Math번역 | MathBoard | Math&Culture | MathMoim
OnLineMathCenter | MathCamp | SoftMathJournal | MathBook | CyberAcademia | Academia