📂집합론

명제와 결합자, 진리표

정의 ¹

참이거나 거짓이거나 둘 중 하나인 서술을 명제라고 한다. 명제는 참이거나 거짓 둘 중 하나의 진리값^{truth value}을 가진다. 두 명제 $p$, $q$ 의 진리값이 같으면 $p$ 와 $q$ 가 **(논리적) 동치^{(Logically) equivalent}라 하고, $p \equiv q$ 와 같이 나타낸다. 합성명제를 구성하는 방법으로써 다음과 같은 기호들을 결합자^connectives라고 한다:

1. 부정: $\lnot$
2. 논리곱: $\land$
3. 논리합: $\lor$
4. 조건부: $\to$
5. 쌍조건부: $\to$

진리표

보통 참은 $T$ 로, 거짓은 $F$ 로 나타낸다. 위와 같은 결합자들은 정의에 따른 논리값을 가진다. 명제에 결합자를 취해서 얻은 명제들의 진리값은 다음과 같이 진리표 로 확인하면 편리하다:

부정^negation

$p$ 가 참이면 $\lnot p$ 는 거짓이고, $p$ 가 거짓이면 $\lnot p$ 는 참이다.

• $\text{NOT}$ 게이트

논리곱^conjunction

$p$ 와 $q$ 가 모두 참이면 $p \land q$ 도 참이고, 그 외엔 거짓이다. 일반적으로 컴퓨터 공학 등의 분야에서는 $0$ 을 거짓, $0$ 이외의 수를 참으로 본다. $0$ 이 아닌 두 수 $a$, $b$ 를 생각해보면 $a \times b = ab \ne 0$ 은 참이지만, 둘 중 하나라도 $0$ 이면 $a \times b = 0$ 이므로 거짓이 된다. 이러한 센스에서 $\land$ 는 논리’곱’이라고 불리운다.

• $\text{AND}$ 게이트

논리합^disjunction

$p$ 와 $q$ 중 하나라도 참이면 $p \lor q$ 도 참이고, 둘 다 거짓일 때만 거짓이다. 논리곱과 마찬가지로 $a + b = 0$ 이면 거짓이고 그 외엔 참이기 때문에 $\lor$ 은 논리’합’이라고 불리운다. 물론 $b = -a \ne 0$ 면 $a$, $b$ 가 모두 참인데 $a+b = 0$ 이 거짓이지만, 이것을 물고 늘어지지는 말자. 그러니까 그냥 ‘합’이 아니라 ‘논리합’인 것이다.

• $\text{OR}$ 게이트

조건부^conditional

$p$ 가 참일 때 $q$ 가 참이면 $p \to q$ 도 참이다. 실제 언어와 달리 $p$ 가 거짓이면 $q$ 가 무엇이든 $p \to q$ 도 참이 되는 것에 주목하라. 한편 $p \to q \equiv \lnot p \lor q$ 인데, 이는 진리표를 통해서 쉽게 증명할 수 있다. 본문 하단을 참고하라.

쌍조건부^{biconditional}

$p \to q$ 와 $q \to p$ 이 모두 참이면 $p \to q$ 다. 수식으로 쓰면 $(p \to q) \land (q \to p) \equiv p \to q$ 이 된다. 진리표로 볼 땐 $p$ 와 $q$ 가 동시에 참이거나 동시에 거짓, 다시 말해 같은 진리값을 가질 때 $p \to q$ 는 참이 된다.

정리

조건부의 논리적 동치

$$ p \to q \equiv \left( \lnot p \lor q \right) $$

증명

부정과 논리합의 정의에 따라

■