[이산수학]명제와 논리

명제 논리는 명제들 간의 논리적 관계를 다루는 논리 체계이다. 수학적 진술의 의미를 분명하게 알려주며, 수학을 이해하기 위해서는 올바른 수학적 논증, 즉 명제에 대해서 이해하여야 한다.

 

명제

명제는 참 또는 거짓을 나타내는, 진위를 명확히 파악할 수 있는 선언적 문장이다.

예를 들어 명제 p, q를 각각 다음과 같이 정의하자.

$p\overset{\underset{\mathrm{def}}{}}{=}$ "$1+1=2$"

$q\overset{\underset{\mathrm{def}}{}}{=}$"$2+2=2$"

그렇다면 명제들의 진리값(진위 여부)은 다음과 같다.

$$p\equiv T$$

$$q\equiv F$$이다. (T는 True, F는 False)

 

연결사

여러 명제들을 조합하여 새로운 명제를 만들낼 수 있다. 이를 복합명제라 하며, 연결사를 이용하여 만든다.

논리 연산자	정의
부정(not): $\neg p$	명제 $p$가 참이면 거짓으로, 거짓이면 참으로 바뀐다.
논리곱(conjunction 또는 and): $p\wedge q$	명제 $p$와 $q$가 참이어야만 명제 $p\wedge q$가 참이된다.
논리합(disjunction 또는 or): $p \vee q$	명제 $p$ 또는 $q$가 참이거나 둘 다 참이면 명제 $p \vee q$가 참이다.
조건(material conditional): $p \rightarrow q$	$p$가 거짓이거나 $q$가 참인 경우 명제 $p \rightarrow q$는 참이다.

또한 명제의 진리값을 표로 나타낸 것을 진리표라 한다.

$p$	$\neg p$
T	F
F	T

$p$	$q$	$p\wedge q$
F	F	F
F	T	F
T	F	F
T	T	T

$p$	$q$	$p\vee q$
F	F	F
F	T	T
T	F	T
T	T	T

$p$	$q$	$p \rightarrow q$
F	F	T
F	T	T
T	F	F
T	T	T

진리표를 통해 다음을 증명할 수 있다.

$p \rightarrow q \equiv \neg p \vee q$

$p$	$q$	$\neg p \vee q$
F	F	T
F	T	T
T	F	F
T	T	T

항상 같은 진리값을 갖기 때문에 위 두 명제는 논리적으로 동치이다.

 

추론 규칙

추론 규칙은 주어진 명제들로부터 논리적으로 결론을 도출하는 규칙을 말한다. 쉽게 말해서 어떠한 추론을 정당한 추론으로 볼 것인가를 정하는 것이다. 예를 들면 다음과 같다.

$$\frac{ \begin{matrix}
p \\ p\to q
\end{matrix} }{\therefore q}$$

또는 $p,p\to q\vdash q$로 표기한다.

이는 $p$가 참이고, $p\to q$가 참이면 $q$가 도출됨을 의미한다. (당연히 도출된 $q$는 참이 된다.)

 

연역적 추론

수학은 연역적인 학문이다. 세상의 모든 수학적 증명은 추론 규칙을 통해 연역적으로 이루어진다.

명제 논리와 같이 간단한 논치 체계는 진리표를 통해 증명할 수 있지만 이후에 다룰 술어논리와 같이 확장된 논리 체계와 이를 바탕으로 하는 논리 체계에서는 이러한 방식을 적용하기가 어렵거나 불가능하다. 따라서 여러가지 법칙이나 정리들을 통해 새로운 명제를 연역적으로 이끌어낼 수 있어야 한다.

다음은 명제 논리에서의 법칙들이다.

$$p \wedge q \equiv q \wedge p$$

$$p \vee q \equiv q \vee p$$

$$p \wedge (q \wedge r) \equiv (p \wedge q) \wedge r$$

$$p \vee (q \vee r) \equiv (p \vee q) \vee r$$

$$p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)$$

$$p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)$$

$$\neg (p \vee q) \equiv \neg p \wedge \neg q$$

$$\neg (p \wedge q) \equiv \neg p \vee \neg q$$

위 법칙들을 통해 $p \rightarrow (q \rightarrow r) \equiv p \wedge q \rightarrow r$임을 증명하겠다.

$p \rightarrow (q \rightarrow r) \equiv p \rightarrow (\neg q \vee r)$ (왜냐하면 $q \rightarrow r \equiv \neg q \vee r$이기 때문에)

$p \rightarrow (\neg q \vee r) \equiv \neg p \vee (\neg q \vee r)$

$\equiv (\neg p \vee \neg q) \vee r$ (4번 법칙)

$\equiv \neg (p \wedge q) \vee r$ (8번 법칙)

$\equiv p\wedge q \rightarrow r$

연역적으로 동치임을 보였기 때문에 증명이 끝난다.

 

명제함수와 양화사

명제함수는 자유변수가 결정되어야만 진리값이 결정되는 명제를 의미하며, $p(x)$와 같이 표기한다.

예를 들어 $p(x)\equiv 2x=2$이고 $x$의 범위가 실수라고 했을 때, 1이면 참이지만, 그 이외엔 모두 거짓이 된다.

이때 x의 범위를 논의영역이라고 한다.

$p(1)\equiv2=2 \equiv T$

$p(2)\equiv 4=2\equiv F$

 

양화사는 자유변수의 양을 지정하는 것을 의미한다. 양화사는 일반적으로 보편 양화사 $\forall$와 존재 양화사 $\exists$ 이렇게 총 2개이다.

$\forall x$: 모든 x에 대해서

$\exists x$: x가 존재한다.

$\forall xp(x)$: 모든 x에 대해서 p(x)이다.

$\exists xp(x)$: p(x)인 x가 적어도 하나 이상 존재한다.

 

예시

$p(x)\equiv x\in \mathbb{N}$: $x$는 자연수이다.

$\forall x p(x)$: 모든 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)$

 

위와 같이 양화사를 사용하는 논리 체계를 술어 논리라고 한다.

술어 논리는 일반적으로 프리넥스 표준형으로 표현된다.

$$\phi=\phi_{\mathrm{prefix}}\phi_{\mathrm{matrix}}$$

$\phi_{\mathrm{prefix}}$: 양화사와 변수만을 포함하는 문자열이다.

$\phi_{\mathrm{matrix}}$: 양화사를 포함하지 않으며, 변수와 연결사로 구성된 문자열이다.

예를 들면 다음과 같다.

$$\phi_{\mathrm{prefix}}= \forall x$$

$$\phi_{\mathrm{matrix}}= x<0$$

$$\phi=\phi_{\mathrm{prefix}}\phi_{\mathrm{matrix}}=\forall x\left(x<0 \right)$$

 

중첩된 양화사

양화사가 여러개 등장한 명제를 의미한다. 예를 들어 다음과 같다.

$$\forall x \forall y,\ p(x,y)$$

여기서 $p(x,y)$는 명제함수이다.

이해하기 쉽게 설명하자면 명제함수를 다음과 같이 정의하자

$$p(x,y)\equiv x+y=0$$

즉, "$x$와 $y$의 합이 0이다."를 의미한다.

그렇다면 명제 $\forall x \forall y,\ p(x,y)$가 의미하는 바는 다음과 같다. ($x$와 $y$의 논의영역은 실수 전체이다.)

"모든 실수 $x$와 $y$의 합은 0이다." 물론 이는 거짓이다.

 

양화사의 출현 순서는 매우 중요하다. 순서에 따라 의미가 바뀌기 때문이다. 예를 들면 다음과 같다.

$$\forall x \exists y,\ p(x,y)$$

는 "모든 실수 $x$에 대하여, p(x,y)를 만족하는 $y$가 적어도 하나 이상 존재한다."이다. 그리고 이는 참이다.

$$\exists y \forall x,\ p(x,y)$$

는 "어떤 실수 $y$가 존재하여 모든 실수 $x$에 대하여 p(x,y)이다."를 의미한다. 이는 거짓이다. $y$의 값이 몇이 됐든 $x+y=0$이 되는 $x$의 값은 단 하나만 존재한다.

 

중첩된 양화사의 부정

중첩된 양화사를 부정하면 맨 앞에 있는 양화사부터 차례대로 부정을 취하면 된다. 예를 들면 다음과 같다.

$$\neg \forall x \forall y \forall z\left(p(x,y,z) \right)$$

$$\equiv \exists x \neg\left( \forall y \forall z\left(p(x,y,z) \right)\right)$$

$$\equiv \exists x \exists y \neg \left( \forall z\left(p(x,y,z) \right)\right)$$

$$\equiv \exists x \exists y \exists z \left( \neg p(x,y,z)\right)$$

결론적으로는 모든 양화사를 뒤집고, $\phi_{\mathrm{matrix}}$에 부정을 취하면 된다.