Math Logic Truth

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

명제의 참거짓표

명제와 명제의 연산 에서 이미 명제와 명제들의 논리적 접속사의 진리표에 대해서는 말을 했다. 어떤 명제가 n 개의 변수인 명제들로 이루어져 있다고 하면 이는

$F(P_{1},P_{2},\dots ,P_{n})$

나타낼 수 있다. 문법에 따라 명제식 F 이 잘 이루어졌다고 가정하고, 변수들을 드러내 쓴 것이다. 진리표란 사실 명제들에 대한 함수다. 정의되는 영역은 문장들의 참거짓값들이 연속된 것이고, 함수값은 0 과 1이다. 참과 거짓을 0 과 1로만 나타내기로 했기 때문에 {0, 1} 을 집합 $\mathbb {B}$ 로 나타낸다면, 명제식은

$f:\mathbb {B} \times \mathbb {B} \times \cdots \times \mathbb {B} \ \mapsto \ \mathbb {B}$

라는 함수로 결정된다. 이렇게 0 과 1 값만 갖는 함수들의 성격을 집중적으로 탐구한 영국의 부울(George Boole , 1815 – 1864)이다. 그의 이름을 따서 그런 함수들을 부울 함수라 부른다. 컴퓨터나 전기설비를 포함해서 전기 전자분야나 논리학에서 부울 함수는 폭넓게 응용된다.

참과 거짓만 있는 경우의 진리표

명제식 F 가 두 개의 명제 변수를 가졌다면 그때 가능한 함수는 몇개나 될까?

진리표

P	Q	$f_{1}$	$f_{2}$	$f_{3}$	$f_{4}$	$f_{5}$	$f_{6}$	$f_{7}$	$f_{8}$	$f_{9}$	$f_{10}$	$f_{11}$	$f_{12}$	$f_{13}$	$f_{14}$	$f_{15}$	$f_{16}$
0	0	1	1	1	1	0	1	1	1	0	0	0	1	0	0	0	0
0	1	1	1	1	0	1	1	0	0	1	1	0	0	1	0	0	0
1	0	1	1	0	1	1	0	1	0	1	0	1	0	0	1	0	0
1	1	1	0	1	1	1	0	0	1	0	1	1	0	0	0	1	0

보다시피 P 는 {0,1} 값을 갖게 되고 Q 도 {0,1} 값을 가지기 때문에 F(P,Q) 에서 정의되는 영역의 변수들의 경우는 (1,1), (1,0), (0,1), (0,0) 네가지다. 각각의 경우에 대하여 서로 다른 값을 갖는 함수는 위에서 본 것처럼 모두 16 가지다.

$f:\{0,1\}\times \{0,1\}\mapsto {0,1}$

의 함수의 개수이기 때문이다. 여기서 $f_{1},f_{2},\dots ,f_{16}$ 들은 모두 어떤 연산을 뜻할 수 있다. 이 중 네가지 기본 연산을 부여했다. 거기에 새로운 연산들을 생각해볼 수 있다. $P\leftrightarrow Q,\ P|Q$같은 것들이다. 이 연산들 중 $P\leftrightarrow Q$ 경우는 수학에서 종종 등장하는 것이다. 어떤 두 문장이 '필요충분조건'일 때를 나타낼 때 쓰기도 한다. 이 함수들에 대한 진리값을 부여하는 것을 보면 어떤 연산을 하는지 짐작할 수 있다. 이미 나왔지만, 기본적인 연산들에 대한 함수만 뽑아내서 다시 쓰면 아래와 같다.

진리표

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

다시 말해 위의 가능한 모든 함수 중, $f_{15}$ 은 '그리고' 연산을 말한다. $f_{5}$ 는 '또는' 을, $f_{3}$ 은 '..이면, .. .이다' 연산을, 그리고 $f_{6}$ 은 'P 가 아니다'를, $f_{7}$ 은 'Q 가 아니다'를 나타낸다. 어느 것이나 일상이나 수학 용어로도 나름대로 합리적인 이유가 있었다. $f_{1},f_{16}$ 은 P, Q 가 어떤 값이든 상관없이 항상 참이거나 거짓인 상수만을 내보내는 상수 함수들이다. 앞의 것을 참 함수, 뒤의 것을 거짓 함수라 이름붙일 수 있다.

변수가 세 개로 이루어진 명제식에 대해 진리표를 만들어보라.

n 개의 변수를 가진 명제식을 정의할 함수는 몇개나 될까?

아래의 예들에 대해 논리적 접속사를 정의한, 진리표를 만들어보라.

$P\lor \ \neg P$

$P\And \ \neg P$

$(P\rightarrow Q)\rightarrow \ P$

$(P\rightarrow \neg \neg P)\land \ (\neg \neg P\rightarrow P)$

$P\rightarrow \neg P$

어떤 명제식 안의 변수들이 어떤 진리값을 가질 때, 명제식의 함수값이 참인지 거짓인지 알기 위해 반드시 함수표를 만들어야 되는 것은 아니다. 거짓이 나올 수 밖에 없는 경우를 거꾸로 추적해들어갈 수 있다.

$(P\rightarrow \ Q)\rightarrow (P\lor \neg Q)$

이 명제식에서 앞의 괄호 부분이 참, 뒤의 괄호 부분이 거짓이면 전체는 거짓이면 전체 명제식의 함수값은 거짓이다. $1\rightarrow 0$ 의 꼴이기 때문이다. 그렇게 되기 위해서는 변수 P 에 거짓인 명제가, Q 에 참인 명제 가 들어가면 전체 문장은 거짓이 된다. 그것이 아닌 경우, 예를 들어 P 가 참이면 전체 문장은 참일 수 밖에 없다. 또는 Q 가 거짓일 때도 전체 문장은 참이다. 두 경우 모두 뒤 괄호부분이 참이기 때문이다. 그런데 이 명제를 다음과 같이 조금 수정해보면...

$(P\rightarrow \ Q)\rightarrow (\neg P\lor Q)$

이면 이 명제는 거짓일 수 없다. 거짓이기 위해서는 앞부분이 1, 뒷부분이 0 이 되는 경우여야 하고, 이렇게 되기 위해서는 뒷부분에서 Q 는 0 , P 는 1 이어야 한다. 그런 경우 앞부분 'P 이면 Q ' 다는 진리표에 따라 0 일수 밖에 없다. 따라서 전체 구조는 참이다. 만약 위의 문장이 이렇게 바뀌면 어떻게 될까? (확인해보라. )

$(P\lor \neg Q)\rightarrow (P\rightarrow \ Q)$

$(\neg P\lor Q)\rightarrow (P\rightarrow \ Q)$

$(P\rightarrow \ Q)\leftrightarrow (P\lor \neg Q)$

실제로 마지막으로 나온 명제식은 고전논리에서 논리적 법칙으로 받아들여지고 항상 참이다.

아래의 명제들은 항상 참일까? 직접 확인해보라.

$((P\rightarrow Q)\rightarrow P)\rightarrow P$

$((P\rightarrow Q)\rightarrow (\neg Q\rightarrow \ \neg P))$

항상 참인 명제 ($\top$)

n 개의 명제 변수를 갖는 명제식 $F(P_{1},P_{2},\dots ,P_{n})$ 은 어떤 경우에는 그 변수들의 값에 따라 참일 수도 있고 거짓일 수도 있다. 이런 명제식 중 특별한 명제식이 있다. $P_{1},P_{2},\dots ,P_{n}$ 의 참값에 상관없이 $F(P_{1},P_{2},\dots ,P_{n})$ 항상 참이 되는 경우다. 진리표로 확인해볼 수 있다. 따라서 '진리표'가 어떻게 주어지는가에 따라 다를 수 있다는 점을 명심해야한다. 앞에서 정한 진리표에 따를 경우, 아래의 문장은 항상 참인 식들이다. 물론 참-거짓만 있는 진리표가 아니거나, 참-거짓만 있다고 해도 접속사에 다른 진리값을 부여한다면 아래 문장이 항상 참이라고 말할 수는 없다. 우리의 '해석'에 따라 달라지는 것이다.

$P\lor \neg P$

$(P\And Q)\rightarrow \ P$

$P\rightarrow \ (P\lor Q)$

$\neg P\rightarrow \ (P\rightarrow \ Q)$

이런 명제식들은 '참'일 수 밖에 없는 '구조'를 갖고 있다. 제아무리 변수에 엉뚱한 말을 해도 그것에 참거짓을 부여할 수 있고 앞의 표로 정한 진리표를 따른다면, 이런 문장들은 '구조적으로' 항상 참이다. '공리' 또는 '정리'라고 부를 수 있는 문장이다. 이런 문장들은 특별하기 때문에 따로 이름을 붙여주기도 한다.

정의 (항상 참인 명제)  : 명제 변수의 진리값에 상관없이 항상 참인 명제식을 '항상 참인 명제' 또는 '토톨로지'(tautology) 라고 부르고 기호로 $\top$ 를 쓴다.

물론 명제변수의 진리값에 상관없이 항상 거짓이 되는 문장도 있다. 이것은 항상 참인 명제 앞에 $\neg$ 를 붙인 것과 논리적으로 등가인 모든 문장들이다.

$\neg (P\lor \neg P)\equiv \neg P\And P$

이런 경우 변수에 상관없이 항상 거짓인 명제식이 된다. 이런 것을 상수명제처럼 써서 기호로 $\bot$ 로 나타내기도 한다.

논리적 법칙과 정리를 보고 다음 질문에 답해보라.

우리가 합리적으로 받아들일 수 있는 논리적 법칙들은 모두 항상 참일까?

항상 참인 명제들은 논리적 법칙일 수 있을까?

모든 가능한 부울 함수를 기본 연산들로 나타낼 수 있을까 ?

네 개의 기본 연산으로 충분하다.

앞에서 변수가 두 개 일때 부울 함수의 개수는 열 여섯개나 되었다. 자연스럽게 드는 질문

왜 네 개의 연산만 기본 연산으로 삼았을까? 이 네 기본연산으로 표현할 수 없는 연산이 그 중 있지 않을까?

네 개의 연산으로 충분하다. 다시 말해 다음과 같은 사실을 확인할 수 있다.

$F(P_{1},P_{2},\dots ,P_{n})$ 에 대응하는 모든 부울함수는 논리적으로 등가인 명제식이 있다.

어떤 부울 함수건 네 기본연산으로 나타낼 수 있다는 것을 말한다. $P\leftrightarrow Q$ 의 경우를 보자. 직접 확인하고, $P|Q$ 연산과 진리표에서 $f_{i}$ 에 대해서 명제식을 찾아보라.

$P\leftrightarrow Q\equiv (\neg P\lor Q)\And (P\lor \neg Q)$

어떤 경우든 가능하다. 예를들어 3 개의 명제 변수로 된 함수가 아래와 같이 정의되었다고 하자.

어떤 부울 함수

P	Q	R	$F_{1}(P,Q,R)$	$F_{2}(P,Q,R)$	$F_{3}(P,Q,R)$
0	0	0	1	1	1
0	0	1	1	0	1
0	1	0	0	0	0
0	1	1	1	1	0
1	0	0	0	0	1
1	0	1	0	1	1
1	1	0	1	0	0
1	1	1	0	1	1

다음 절차를 따라 어떤 함수라도 같은 명제식을 찾을 수 있다.

• 함수값이 1 일 때, 그때의 P, Q, R 의 진리값과 네 기본연산으로 표현한 명제식으로 참이 나오도록 한다.
• 그 경우들을 '또는'으로 연결한다.

첫번째 함수에 대해서만 보기로 하자. 이 함수는 참이 네 번 나온다. 그 때의 (P,Q,R) 의 진리값의 경우는 네가지이다.

(0,0,0), (0,0,1) , (0,1,1), (1,1,0)

이제 그 경우마다 참이 되도록 네 명제식을 연산한다.

$(\neg P\And \neg Q\And \neg R)$ 은 (0,0,0) 일 때 항상 참이다.

$(\neg P\And \neg Q\And R)$ 은 (0,0,1) 일 때 항상 참이다.

$(\neg P\And Q\And R)$ 은 (0,1,1) 일 때 항상 참이다.

$(P\And Q\And \neg R)$ 은 (0,0,0) 일 때 항상 참이다.

이제 이것들을 '또는' 으로 연결한다.

$(\neg P\And \neg Q\And \neg R)\lor (\neg P\And \neg Q\And R)\lor (\neg P\And Q\And R)\lor (P\And Q\And \neg R)$

다. 네 기본연산으로만 표현된 명제식이다. 이 명제식은 분명히 위의 네 경우에 대해서만 참이다. 이와 같은 논리로 이해하면 변수가 3 개 있을 때 가능한 모든 함수는 모두 명제식으로 표현된다.

어떤 부울 함수와 논리적으로 등가인 명제식이 하나만 있는 것은 물론 아니다. 위의 경우에도 우리가 제시한 명제식과 논리적으로 등가인 모든 명제식은 첫번째 함수와 논리적으로 등가가 된다. 나머지 두 경우에 대해서도 직접 명제식을 찾아보라.

세연산으로도 충분하다

앞의 설명에서 보듯, $\rightarrow$ 연산 없이 모든 부울 함수를 명제식으로 나타낼 수 있다는 것은 명백하다. 따라서

$\And ,\ \lor ,\ \neg$ 세 연산으로 어떤 부울함수에 대해서든 명제식으로 나타낼 수 있다.

별로 대단할 것 없다. 왜냐하면

$P\rightarrow Q\equiv \neg P\lor Q$

이기 때문이다. 마찬가지로 $\And$ 없이 또는 $\lor$ 없이 세 연산으로만으로도 나타낼 수 있다.

$P\And Q\equiv \neg (P\rightarrow \neg Q)$

$P\lor Q\equiv \neg (\neg P\And \neg Q)$

이기 때문이다. 이미 눈치를 챘겠지만, 굳이 세 개의 연산을 쓰지 않아도 된다.

두 연산으로도 충분하다

앞에서 보였듯이

$P\rightarrow Q\equiv (\neg P\lor Q)$

$P\And Q\equiv \neg (\neg P\And \neg Q)$

따라서 모든 부울함수는 기본 연산 $\neg ,\ \lor$ 두개만 써서 나타내는 명제식과 논리적으로 등가를 이룰 수 있다. 마찬가지로,

$P\rightarrow Q\equiv \neg (P\And \neg Q)$

$P\lor Q\equiv \neg (\neg P\lor \neg Q)$

이므로 모든 부울함수는 기본 연산 $\neg ,\ \And$ 두개만 써서 나타내는 명제식과 논리적으로 등가를 이룰 수 있다. 그렇다면

기본 연산 $\neg ,\ \rightarrow$ 두 개만 써서도 나타낼 수 있을까?

기본 연산 $\And ,\ \lor ,\rightarrow$ 세 개 또는 그 중 두 개만 써서도 나타낼 수 있을까?

$\neg$ 없이 가능할까?

수학적 문장은 참과 거짓만 있어야 하나?

명제는 참과 거짓을 말할 수 있는 문장이라고 했지만, 모든 명제에 대해 참거짓을 분명하게 말할 수 있는 것은 아니다. 예를들어

p 도 소수고 p + 2 도 소수인 p 는 끝없이 많다.

라는 문장은 참이거나 거짓을 부여할 수는 있지만, 참이냐 거짓이냐를 아직 알지 못한다. 수학이 아무리 발달해간다고 해도 이런 '증명안된' 문장들은 계속 등장할 수 밖에 없을 것이다. 신의 시각으로 보면 참이거나 거짓이라고 말할 수 있을지 모르지만, '참-거짓'에 대해 다른 관점을 가진다면 진리값이 꼭 참과 거짓이어야 할 이유는 없다. 예를들어 '문장이 성립한다는 증명할 수 있음'을 참이라고 하고, '그 문장이 성립하지 않는다'는 것을 거짓으로 받아들인다면, 수학의 문장은 참과, 거짓, 그리고 증명안됨으로 나뉘게 된다. 그런 경우는 '3개의 진리값을 갖는 직관주의'의 입장을 따르는 명제논리라 할 수 있다. 이럴 때 진리표를 어떻게 부여하는 것이 합리적일까 하는 것은 철학적 입장에 따라 다르게 된다. 대표적인 두 경우만 예로 보자.

참과 거짓, 그리고 또 하나의 진리가 있는 진리표의 두 경우

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

연산의 '참'에 대하여 이와 같은 입장을 가질 경우 앞에서 항상 참이었던 문장 중 여기서는 참이라고 할 수 없는 경우가 있다. 특히 주의할 연산은 $\lor ,\rightarrow$ 다. 예를들어 제 3 의 가능성을 배제하는 법칙과 연관된, 고전 논리의 가장 밑바닦을 지지하고 있는 다음 법칙들은 항상 참이라고 할 수 없다.

$p\lor \neg p,\ \neg \neg p$

의 경우 p 가 1/2 일 때, 모두 1/2 이지 1 이 되지 않는다. 또 어떤 법칙들이 받아들여지지 않을까? 이와 연관된 문제는 직관주의 논리 를 참고하라. 다음 문제를 풀어보자.

어떤 경우에 왼쪽이고 어떤 경우에 오른쪽 진리표를 가질까? 나름의 해석을 해보라.

n 개의 변수를 가진 명제식이 3 개의 진리표를 갖는다면, 함수의 개수는 몇개일까?

Note

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