수학/수리논리학 2023. 7. 15. 17:37

정의1

명제 :

참(True) 또는 거짓(False) 중 하나로만 표현되는 어떤 사실을 선언하는 문장을 명제로 정의한다.

명제가 참일때 문자 $\mathbf{T}$, 거짓일때 문자 $\mathbf{F}$를 사용하면 $\mathbf{T}$나 $\mathbf{F}$를 명제의 진리값이라 한다.

명제의 진리값을 표로 나타낼때 명제의 진리표라 한다.

항진명제(tautology), 모순(contradiction), 불확정명제(contingency) :

명제의 진리값이 항상 참일때 항진명제로 정의하고

명제의 진리값이 항상 거짓일때 모순으로 정의한다.

항진명제나 모순이 아닌 명제를 불확정명제라고 한다.

정의2

$P$가 명제일때 $P$의 진리값이 반대가 되는 명제 $\neg P$ 또는 $\mathsf{not} \; P$ 또는 $P가\; 아니다.$를

$P$의 부정(negation)으로 정의한다.

$P$의 부정에 대한 진리표는 다음과 같다.

$P$	$\neg P$
$\mathbf{T}$ $\mathbf{F}$	$\mathbf{F}$ $\mathbf{T}$

$P,Q$가 명제일때 아래 진리표와 같은 진리값을 갖는 명제 $P \land Q$ 또는 $P \; \mathsf{and} \; Q$ 또는 $P 이고 \; Q이다.$를

$P$와 $Q$의 논리곱(conjunction)으로 정의한다.

$P$	$Q$	$P \land Q$
$\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$

$P,Q$가 명제일때 아래 진리표와 같은 진리값을 갖는 명제 $P \lor Q$ 또는 $P \; \mathsf{or} \; Q$ 또는 $P이거나 \; Q이다.$를

$P$와 $Q$의 논리합(disjunction)으로 정의한다.

$P$	$Q$	$P \lor Q$
$\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$

정의3(조건문)

$P,Q$가 명제일때 아래 진리표와 같은 진리값을 갖는 명제 $P \to Q$ 또는 $Q \gets P$ 또는 $P 이면 \; Q이다.$를

$P$는 $Q$이기 위한 충분조건 또는 $Q$는 $P$이기 위한 필요조건 으로 정의한다.

$P$	$Q$	$P \to Q$
$\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{T}$

역(converse), 이(inverse), 대우(contrapositive) :

$P,Q$가 명제일때 아래 진리표와 같은 진리값을 갖는

명제 $Q \to P$를 $P \to Q$의 역,

명제 $\neg Q \to \neg P$를 $P \to Q$의 대우,

명제 $\neg P \to \neg Q$를 $P \to Q$의 이 로 정의한다.

$P$	$Q$	$\neg P$	$\neg Q$	$P \to Q$	$Q \to P$	$\neg Q \to \neg P$	$\neg P \to \neg Q$
$\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{F}$	$\mathbf{F}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{T}$	$\mathbf{F}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{T}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{T}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$

$P,Q$가 명제일때 아래 진리표와 같은 진리값을 갖는 명제 $P \leftrightarrow Q$ 또는 $Q \leftrightarrow P$를

$P$는 $Q$이기 위한 필요충분조건 또는 $Q$는 $P$이기 위한 필요충분조건 으로 정의한다.

$P$	$Q$	$P \leftrightarrow Q$
$\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{T}$

정의6(논리 연산자, 결합자[connective])

위에 나온 $\neg$, $\lor$, $\land$, $\to$, $\gets$, $\leftrightarrow$를 논리 연산자 또는 결합자라고 한다.

논리 연산자의 연산순위는 괄호 $()$안에 묶인 연산이 가장 먼저 계산되고

괄호 안이나 괄호가 없을때는

$\neg$ : 1순위

$\land$ : 2순위

$\lor$ : 3순위

$\to$ : 4순위

$\leftrightarrow$ : 5순위

위와 같은 순서로 연산을 진행된다.

정의4(동치)

$P,Q$가 명제일때 명제 $P \leftrightarrow Q$가 항진명제이면

$P$와 $Q$를 논리적 동치 또는 동치라고하고 $P \equiv Q$로 표기한다.

$P$와 $Q$가 동치가 아니면 $P \not\equiv Q$로 표기한다.

정리6

임의의 명제 $P,Q, R$에 대해 다음이 성립한다.

반사성 : $P \equiv P$

대칭성 : $P \equiv Q$이면 $Q \equiv P$이다.

추이성 : $P \equiv Q$이고 $Q \equiv R$이면 $P \equiv R$이다.

증명

반사성

$P$	$P \leftrightarrow P$
$\mathbf{T}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$

$P \leftrightarrow P$는 항진명제이므로 정리가 성립한다.

대칭성

$P$	$Q$	$P \leftrightarrow Q$	$Q \leftrightarrow P$
$\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{T}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{T}$

$P \equiv Q$이면 $P \leftrightarrow Q \equiv \mathbf{T}$이고

$P \leftrightarrow Q \equiv \mathbf{T}$일때 항상 $Q \leftrightarrow P \equiv \mathbf{T}$이므로 정리가 성립한다.

추이성

$P$	$Q$	$R$	$P \leftrightarrow Q$	$Q \leftrightarrow R$	$(P \leftrightarrow Q)\land (Q \leftrightarrow R)$	$P \leftrightarrow R$
$\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{T}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{T}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{T}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$

$P \equiv Q$이고 $Q \equiv R$이면 $(P \leftrightarrow Q)\land (Q \leftrightarrow R) \equiv \mathbf{T}$이고

$(P \leftrightarrow Q)\land (Q \leftrightarrow R) \equiv \mathbf{T}$일때 항상 $P\leftrightarrow R \equiv \mathbf{T}$이므로 정리가 성립한다.

정리1

$P,Q,R$이 명제일때 다음이 성립한다.

항등법칙

1. $P \land \mathbf{T} \equiv P$

2. $P \lor \mathbf{F} \equiv P$

지배법칙

1. $P \lor \mathbf{T} \equiv \mathbf{T}$

2. $P \land \mathbf{F} \equiv \mathbf{F}$

멱등법칙

1. $P \lor P \equiv P$

2. $P \land P \equiv P$

이중 부정법칙

$\neg (\neg P) \equiv P$

교환법칙

1. $P \lor Q \equiv Q \lor P$

2. $P \land Q \equiv Q \land P$

결합법칙

1. $(P \lor Q)\lor R \equiv P\lor (Q \lor R)$

2. $(P \land Q)\land R \equiv P\land (Q \land R)$

분배법칙

1. $P \lor (Q\land R) \equiv (P\lor Q )\land (P \lor R)$

2. $P \land (Q\lor R) \equiv (P\land Q )\lor (P \land R)$

드 모르간(De Morgan) 법칙

1. $\neg (P \land Q) \equiv \neg P \lor \neg Q$

2. $\neg (P \lor Q) \equiv \neg P \land \neg Q$

흡수법칙

1. $P \lor (P \land Q) \equiv P$

2. $P \land (P \lor Q) \equiv P$

부정법칙

1. $P \lor \neg P \equiv \mathbf{T}$

2. $P \land \neg P \equiv \mathbf{F}$

증명

항등법칙

$P$	$P \land \mathbf{T}$	$P \leftrightarrow (P \land \mathbf{T})$	$P \lor \mathbf{F}$	$P \leftrightarrow (P \lor \mathbf{F})$
$\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$

$P \leftrightarrow (P \land \mathbf{T})$와 $P \leftrightarrow (P \lor \mathbf{F})$가 항진명제이므로 1,2가 성립한다.

지배법칙

$P$	$P \lor \mathbf{T}$	$\mathbf{T} \leftrightarrow (P \lor \mathbf{T})$	$P \land \mathbf{F}$	$\mathbf{F} \leftrightarrow (P \land \mathbf{F})$
$\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$	$\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$

$\mathbf{T} \leftrightarrow (P \lor \mathbf{T})$와 $\mathbf{F} \leftrightarrow (P \land \mathbf{F})$가 항진명제이므로 1,2가 성립한다.

멱등법칙

$P$	$P \lor P$	$P \leftrightarrow (P \lor P)$	$P \land P$	$P \leftrightarrow (P \land P)$
$\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$

$P \leftrightarrow (P \lor P)$와 $P \leftrightarrow (P \land P)$가 항진명제이므로 1,2가 성립한다.

이중 부정법칙

$P$	$\neg P$	$\neg (\neg P)$	$P \leftrightarrow \neg (\neg P)$
$\mathbf{T}$ $\mathbf{F}$	$\mathbf{F}$ $\mathbf{T}$	$\mathbf{T}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$

$P \leftrightarrow \neg (\neg P)$가 항진명제이므로 $\neg (\neg P) \equiv P$이다.

교환법칙

$P$	$Q$	$P \lor Q$	$Q \lor P$	$(P\lor Q) \leftrightarrow (Q \lor P)$
$\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$

$(P\lor Q) \leftrightarrow (Q \lor P)$가 항진명제이므로 $P \lor Q \equiv Q \lor P$이다.

$P$	$Q$	$P \land Q$	$Q \land P$	$(P\land Q) \leftrightarrow (Q \land P)$
$\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$

$(P\land Q) \leftrightarrow (Q \land P)$가 항진명제이므로 $P \land Q \equiv Q \land P$이다.

결합법칙

$P$	$Q$	$R$	$P \lor Q$	$(P \lor Q) \lor R$	$Q \lor R$	$P \lor (Q \lor R)$	$((P \lor Q) \lor R) \leftrightarrow (P\lor (Q \lor R))$
$\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$

$((P \lor Q) \lor R) \leftrightarrow (P\lor (Q \lor R))$이 항진명제이므로 $(P \lor Q)\lor R \equiv P\lor (Q \lor R)$이다.

$P$	$Q$	$R$	$P \land Q$	$(P \land Q) \land R$	$Q \land R$	$P \land (Q \land R)$	$((P \land Q) \land R) \leftrightarrow (P\land (Q \land R))$
$\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$

$((P \land Q) \land R) \leftrightarrow (P\land (Q \land R))$이 항진명제이므로 $(P \land Q)\land R \equiv P\land (Q \land R)$이다.

분배법칙

$P$	$Q$	$R$	$Q \land R$	$P \lor (Q \land R)$	$P \lor Q$	$P \lor R$	$(P \lor Q)\land (P\lor R)$	$(P\lor (Q\land R)) \leftrightarrow ((P \lor Q)\land (P\lor R))$
$\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$

$(P\lor (Q\land R)) \leftrightarrow ((P \lor Q)\land (P\lor R))$이 항진명제이므로 $P \lor (Q\land R) \equiv (P\lor Q )\land (P \lor R)$이다.

$P$	$Q$	$R$	$Q \lor R$	$P \land (Q \lor R)$	$P \land Q$	$P \land R$	$(P \land Q)\lor (P\land R)$	$(P\land (Q\lor R)) \leftrightarrow ((P \land Q)\lor (P\land R))$
$\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$

$(P\land (Q\lor R)) \leftrightarrow ((P \land Q)\lor (P\land R))$이 항진명제이므로 $P \land (Q\lor R) \equiv (P\land Q )\lor (P \land R)$이다.

드 모르간(De Morgan) 법칙

$P$	$Q$	$P \land Q$	$\neg (P \land Q)$	$\neg P$	$\neg Q$	$\neg P \lor \neg Q$	$\neg (P \land Q) \leftrightarrow \neg P \lor \neg Q$
$\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{F}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$	$\mathbf{F}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{T}$	$\mathbf{F}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$	$\mathbf{F}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$

$\neg (P \land Q) \leftrightarrow \neg P \lor \neg Q$가 항진명제이므로 $\neg (P \land Q) \equiv \neg P \lor \neg Q$이다.

$P$	$Q$	$P \lor Q$	$\neg (P \lor Q)$	$\neg P$	$\neg Q$	$\neg P \land \neg Q$	$\neg (P \lor Q) \leftrightarrow \neg P \land \neg Q$
$\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$	$\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{T}$	$\mathbf{F}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{T}$	$\mathbf{F}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$	$\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{T}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$

$\neg (P \lor Q) \leftrightarrow \neg P \land \neg Q$가 항진명제이므로 $\neg (P \lor Q) \equiv \neg P \land \neg Q$이다.

흡수법칙

$P$	$Q$	$P \land Q$	$P \lor (P \land Q)$	$(P \lor (P \land Q)) \leftrightarrow P$
$\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$

$(P \lor (P \land Q)) \leftrightarrow P$가 항진명제이므로 $P \lor (P \land Q) \equiv P$이다.

$P$	$Q$	$P \lor Q$	$P \land (P \lor Q)$	$(P \land (P \lor Q)) \leftrightarrow P$
$\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$

$(P \land (P \lor Q)) \leftrightarrow P$가 항진명제이므로 $P \land (P \lor Q) \equiv P$이다.

부정법칙

$P$	$\neg P$	$P \lor \neg P$	$(P \lor \neg P) \leftrightarrow \mathbf{T}$	$P \land \neg P$	$(P \land \neg P) \leftrightarrow \mathbf{F}$
$\mathbf{T}$ $\mathbf{F}$	$\mathbf{F}$ $\mathbf{T}$	$\mathbf{T}$ $\mathbf{T}$	$\mathbf{T}$ $\mathbf{T}$	$\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{T}$

$(P \lor \neg P) \leftrightarrow \mathbf{T}$와 $(P \land \neg P) \leftrightarrow \mathbf{F}$가 항진명제이므로1,2가 성립한다.

정리2

$P,Q,R$이 명제일때 다음이 성립한다.

1. $P \to Q \equiv \neg P \lor Q$

2. $P \to Q \equiv \neg Q \to \neg P$

3. $P \lor Q \equiv \neg P \to Q$

4. $P \land Q \equiv \neg( P \to \neg Q)$

5. $\neg(P\to Q) \equiv P \land \neg Q$

6. $(P \to Q) \land (P \to R) \equiv P \to (Q \land R)$

7. $(P\to R) \land (Q \to R) \equiv (P\lor Q) \to R$

8. $(P\to Q) \lor (P\to R) \equiv P \to (Q \lor R)$

9. $(P \to R) \lor (Q \to R) \equiv (P \land Q)\to R$

10. $(P\to Q) \to (Q \to P) \equiv Q\to P$

증명

$P$	$Q$	$P \to Q$	$\neg P$	$\neg P \lor Q$	$(P \to Q) \leftrightarrow (\neg P \lor Q)$
$\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{T}$	$\mathbf{F}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{T}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{T}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$

$(P \to Q) \leftrightarrow (\neg P \lor Q)$가 항진명제이므로 $P \to Q \equiv \neg P \lor Q$이다.

$P$	$Q$	$\neg P$	$\neg Q$	$P \to Q$	$\neg Q \to \neg P$	$(P \to Q) \leftrightarrow (\neg Q \to \neg P)$
$\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{F}$	$\mathbf{F}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{T}$	$\mathbf{F}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{T}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{T}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$

$(P \to Q) \leftrightarrow (\neg Q \to \neg P)$가 항진명제이므로 $P \to Q \equiv \neg Q \to \neg P$이다.

1번과 이중 부정법칙으로 $\neg P \to Q \equiv \neg (\neg P) \lor Q \equiv P \lor Q$이다.

3번과 드 모르간 법칙으로 $\neg(P \to \neg Q) \equiv \neg (\neg P \lor \neg Q ) \equiv P \land Q$이다.

1번과 드 모르간 법칙으로 $\neg ( P \to Q) \equiv \neg ( \neg P \lor Q ) \equiv P \land \neg Q$이다.

1번과 분배 법칙을 사용한 뒤 3번과 이중 부정법칙으로

$\begin{align*} (P \to Q) \land (P \to R) & \equiv (\neg P \lor Q) \land (\neg P \lor R) \\[0.5em] & \equiv \neg P \lor (Q \land R) \\[0.5em] & \equiv \neg (\neg P) \to (Q \land R) \\[0.5em] & \equiv P \to (Q \land R) \text{ 이다.} \end{align*}$

1번과 교환 법칙, 분배 법칙을 사용한 뒤 교환 법칙과 3번, 드 모르간 법칙으로

$\begin{align*} (P \to R ) \land (Q \to R) & \equiv (\neg P \lor R) \land (\neg Q \lor R) \\[0.5em] & \equiv (R \lor \neg P) \land (R \lor \neg Q) \\[0.5em] & \equiv R \lor (\neg P \land \neg Q) \\[0.5em] & \equiv (\neg P \land \neg Q) \lor R \\[0.5em] & \equiv \neg (\neg P \land \neg Q ) \to R \\[0.5em] & \equiv (P \lor Q) \to R \text{ 이다.} \end{align*} $

1번과 결합 법칙, 교환 법칙을 사용한 뒤 멱등 법칙, 결합 법칙과 1번으로

$\begin{align*} (P \to Q) \lor (P \to R) & \equiv (\neg P \lor Q) \lor (\neg P \lor R) \\[0.5em] & \equiv \neg P \lor Q \lor \neg P \lor R \\[0.5em] & \equiv \neg P \lor \neg P \lor Q \lor R \\[0.5em] & \equiv \neg P \lor Q \lor R \\[0.5em] & \equiv \neg P \lor (Q \lor R) \\[0.5em] & \equiv P \to (Q \lor R) \text{ 이다.} \end{align*}$

1번과 교환 법칙, 결합 법칙을 사용한 뒤 멱등 법칙, 교환 법칙, 결합 법칙, 드 모르간 법칙과 1번으로

$\begin{align*} (P \to R ) \lor (Q \to R) & \equiv (\neg P \lor R) \lor (\neg Q \lor R) \\[0.5em] & \equiv (\neg P \lor R) \lor (R \lor \neg Q) \\[0.5em] & \equiv \neg P \lor R \lor R \lor \neg Q \\[0.5em] & \equiv \neg P \lor R \lor \neg Q \\[0.5em] & \equiv \neg P \lor \neg Q \lor R \\[0.5em] & \equiv (\neg P \lor \neg Q) \lor R \\[0.5em] & \equiv \neg (P \land Q) \lor R \\[0.5em] & \equiv (P \land Q) \to R \text{ 이다.} \end{align*} $

10.

1번과 드 모르간 법칙, 결합 법칙을 사용한 뒤 교환 법칙, 흡수 법칙과 1번으로

$\begin{align*} (P\to Q) \to (Q \to P) & \equiv (\neg P \lor Q) \to (\neg Q \lor P) \\[0.5em] & \equiv \neg (\neg P \lor Q) \lor (\neg Q \lor P) \\[0.5em] & \equiv ((P\land \neg Q) \lor \neg Q )\lor P \\[0.5em] & \equiv (\neg Q\lor (\neg Q \land P))\lor P \\[0.5em] & \equiv \neg Q \lor P \\[0.5em] & \equiv Q \to P \text{ 이다.} \end{align*}$

정리3

$P,Q$가 명제일때 다음이 성립한다.

1. $P \leftrightarrow Q \equiv (P \to Q) \land (Q\to P)$

2. $P \leftrightarrow Q \equiv \neg P \leftrightarrow \neg Q $

3. $P \leftrightarrow Q \equiv (P \land Q) \lor (\neg P \land \neg Q)$

4. $\neg (P \leftrightarrow Q) \equiv P \leftrightarrow \neg Q$

5. $(P \to Q) \leftrightarrow (Q \to P) \equiv P\leftrightarrow Q$

증명

$P$	$Q$	$P \to Q$	$Q \to P$	$P \leftrightarrow Q$	$(P \to Q) \land (Q\to P)$	$(P \leftrightarrow Q) \leftrightarrow ((P \to Q) \land (Q\to P))$
$\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{F}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$ $\mathbf{T}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{F}$ $\mathbf{T}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{T}$	$\mathbf{T}$ $\mathbf{F}$ $\mathbf{F}$ $\mathbf{T}$	$\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$ $\mathbf{T}$

$(P \leftrightarrow Q) \leftrightarrow ((P \to Q) \land (Q\to P))$가 항진명제이므로 $P \leftrightarrow Q \equiv (P \to Q) \land (Q\to P)$이다.

1번과 위 정리를 적용한 뒤 다시 1번으로

$P \leftrightarrow Q \equiv (P \to Q) \land (Q \to P) \equiv (\neg Q \to \neg P) \land (\neg P \to \neg Q ) \equiv \neg Q \leftrightarrow \neg P \equiv \neg P \leftrightarrow \neg Q$이다.

1번과 위 정리를 적용한 뒤 위 법칙들로

$\begin{align*} P \leftrightarrow Q & \equiv (P \to Q) \land (Q\to P) \\[0.5em] & \equiv (\neg P \lor Q) \land (\neg Q \lor P) \\[0.5em] & \equiv ((\neg P \lor Q) \land \neg Q) \lor ((\neg P \lor Q) \land P) \\[0.5em] & \equiv (\neg Q \land (\neg P \lor Q)) \lor (P \land (\neg P \lor Q)) \\[0.5em] & \equiv ((\neg Q \land \neg P) \lor(\neg Q \land Q)) \lor ((P \land \neg P) \lor( P \land Q)) \\[0.5em] & \equiv ((\neg Q \land \neg P) \lor \mathbf{F}) \lor (\mathbf{F} \lor( P \land Q)) \\[0.5em] & \equiv (\neg Q \land \neg P) \lor( P \land Q) \\[0.5em] & \equiv ( P \land Q) \lor (\neg P \land \neg Q) \text{ 이다.} \end{align*}$

3번과 위 법칙과 위 정리들을 적용한 뒤 1번으로

$\begin{align*} \neg (P \leftrightarrow Q) & \equiv \neg ((P \land Q) \lor (\neg P \land \neg Q)) \\[0.5em] & \equiv \neg (P \land Q) \land \neg (\neg P \land \neg Q) \\[0.5em] & \equiv \neg ( \neg (P \to \neg Q) ) \land (P \lor Q) \\[0.5em] & \equiv (P \to \neg Q) \land (\neg P \to Q) \\[0.5em] & \equiv (P \to \neg Q) \land (\neg Q \to P) \\[0.5em] & \equiv P \leftrightarrow \neg Q \text{ 이다.} \end{align*}$

1번과 위 법칙과 위 정리를 적용한 뒤 1번으로

$\begin{align*} (P \to Q) \leftrightarrow (Q \to P) & \equiv ((P \to Q) \to (Q \to P)) \land ((Q\to P) \to (P \to Q)) \\[0.5em] & \equiv (Q\to P) \land (P\to Q) \\[0.5em] & \equiv (P\to Q) \land (Q \to P)\\[0.5em] & \equiv P \leftrightarrow Q \text{ 이다.} \end{align*}$

정의5

명제함수(propositional function) :

임의의 단어 또는 문장 $x$에 따라 명제 $P(x)$의 진리값이 결정되는 $P$를 명제함수라고 정의하고

이때 $x$를 변수(variable)라고 한다.

유한 개의 변수 $x_1,x_2, \cdots, x_n$에 대해서도 명제함수 $P$를 $P(x_1,x_2,\cdots,x_n)$으로 정의한다.

변수 $x$가 취할 수 있는 특정영역을 정의역(domain) 또는 논의영역(universe of discourse)이라 한다.

전칭 한정(universal quantification) :

정의역에 속하는 모든(every) 또는 임의의(arbitrary) 변수 $x$에 대해 $P(x) \equiv \mathbf{T}$이다.

위와 같은 문장을 명제 함수 $P$의 전칭 한정이라 하고 $\forall xP(x)$로 표기한다.

$P(x) \equiv \mathbf{F}$가 되는 변수 $x$가 존재하면 $\forall xP(x) \equiv \mathbf{F}$이고 $x$를 반례라고 한다.

존재 한정(existential quantification) :

$P(x) \equiv \mathbf{T}$가 되는 정의역에 속하는 어떤(some) 변수 $x$가 적어도 하나(at least one) 존재한다.

위와 같은 문장을 명제 함수 $P$의 존재 한정이라 하고 $\exists xP(x)$로 표기한다.

정의역에 속하는 모든 변수 $x$에 대해 $P(x) \equiv \mathbf{F}$이면 $\exists xP(x) \equiv \mathbf{F}$이다.

한정기호(quantifier) :

위와 같은 기호 $\forall$과 $\exists$를 한정 기호라 하고 괄호를 제외한 모든 논리 연산자보다 상위의 연산순서를 갖는다.

한정기호의 부정 :

임의의 명제함수 $P$에 대해

$P(x) \equiv \mathbf{F}$가 되는 정의역에 속하는 변수 $x$가 존재하면 $\forall xP(x) \equiv \mathbf{F}$이므로 $\neg \forall x P(x) \equiv \exists x \neg P(x)$로 정의하고

정의역에 속하는 모든 변수 $x$에 대해 $P(x) \equiv \mathbf{F}$이면 $\exists xP(x) \equiv \mathbf{F}$이므로 $\neg \exists x P(x) \equiv \forall x \neg P(x)$로 정의한다.

정의에 따라 $\forall x P(x) \equiv \neg \exists x \neg P(x)$와 $\exists x P(x) \equiv \neg \forall x \neg P(x)$가 성립한다.

정리4

$n \ge 2$인 $n \in \mathbb{Z}^+$에 대해 $P_1,P_2, \cdots, P_n$이 명제일때

$(P_1 \to P_2) \land (P_2 \to P_3) \land \cdots \land (P_{n-1} \to P_n) \equiv \mathbf{T}$이면 $P_1 \to P_n \equiv \mathbf{T}$이다.

증명

$n = 2$일때는 자명하게 성립한다.

$n \ge 3$인 $n \in \mathbb{Z}^+$에 대해 귀납법을 사용한다.

$n = 3$일때

$(P_1 \to P_2) \land (P_2 \to P_3) \equiv \mathbf{T}$이므로 $(P_1 \to P_2) \equiv \mathbf{T}$이고 $(P_2 \to P_3) \equiv \mathbf{T}$이다.

또 위 정리로 $\mathbf{T} \equiv (P_1 \to P_2) \equiv (\neg P_1 \lor P_2)$이고 $\mathbf{T} \equiv (P_2 \to P_3) \equiv (\neg P_2 \lor P_3)$이므로

위 정리로 $\mathbf{T} \equiv \mathbf{T} \lor \mathbf{T} \equiv \neg P_1 \lor P_2 \lor \neg P_2 \lor P_3 \equiv \neg P_1 \lor \mathbf{T} \lor P_3 \equiv \neg P_1 \lor P_3 \equiv P_1 \to P_3$이다.

$k\ge 3$인 모든 $k \in \mathbb{Z}^+$에 대해 정리가 성립한다고 가정할때

$(P_1 \to P_2) \land (P_2 \to P_3) \land \cdots \land (P_{k-1} \to P_k) \land (P_k \to P_{k+1}) \equiv \mathbf{T}$이면

$(P_1 \to P_2) \land (P_2 \to P_3) \land \cdots \land (P_{k-1} \to P_k) \equiv \mathbf{T}$이므로 귀납가정으로 $P_1 \to P_k \equiv \mathbf{T}$이고

$(P_1 \to P_k) \land (P_{k} \to P_{k+1}) \equiv \mathbf{T}$이므로 위에서 보였듯이 $(P_1 \to P_{k+1}) \equiv \mathbf{T}$이다.

따라서 $n \ge 2$인 모든 $n \in \mathbb{Z}^+$에 대해

$(P_1 \to P_2) \land (P_2 \to P_3) \land \cdots \land (P_{n-1} \to P_n) \equiv \mathbf{T}$이면 $P_1 \to P_n \equiv \mathbf{T}$이다.

정리5

임의의 $n \in \mathbb{Z}^+$에대해 $P_1,P_2, \cdots, P_n$이 명제일때

$(P_1 \to P_2) \land (P_2 \to P_3) \land \cdots \land (P_{n-1} \to P_n) \land (P_n \to P_1) \equiv \mathbf{T}$이면

모든 $i,j = 1,2,\cdots , n$에 대해 $P_i \leftrightarrow P_j \equiv \mathbf{T}$가 되어 $P_1,P_2, \cdots, P_n$은 모두 동치이다.

증명

$n = 1$일때 $P_1 \to P_1 \equiv \mathbf{T}$이므로 위 정리로 $\mathbf{T} \equiv (P_1 \to P_1)\land (P_1 \to P_1) \equiv P_1 \leftrightarrow P_1 $이다.

$n \ge 2$인 $n \in \mathbb{Z}^+$에 대해서는 교환법칙으로

$(P_n \to P_1) \land (P_1 \to P_2) \land (P_2 \to P_3) \land \cdots \land (P_{n-1} \to P_n) \equiv \mathbf{T}$이므로

위 정리로 모든 $i,j = 1,2,\cdots , n$에 대해 $P_i \to P_j \equiv \mathbf{T}$이고 $P_j \to P_i \equiv \mathbf{T}$가 되어

위 정리로 $\mathbf{T} \equiv (P_i \to P_j)\land (P_j \to P_i) \equiv P_i \leftrightarrow P_j$이다.

정리7

변수 $x$에 대한 명제함수 $P,Q$에 대해 모든 한정기호의 정의역이 같다면 다음이 성립한다.

1. $\forall xP(x) \land \forall x Q(x)\equiv \forall x (P(x) \land Q(x)) $

2. $\exists xP(x) \lor \exists x Q(x) \equiv \exists x (P(x) \lor Q(x)) $

3. $\forall x (P(x) \to Q(x))$가 참이면 $ \forall xP(x) \to \forall x Q(x)$가 참이다.

4. $ \forall x (P(x) \leftrightarrow Q(x))$가 참이면 $ \forall xP(x) \leftrightarrow \forall x Q(x)$가 참이다.

증명

$\forall xP(x) \land \forall x Q(x)$가 참이면

정의역에 속하는 모든 $x$에 대해 $P(x)$가 참이고 정의역에 속하는 모든 $x$에 대해 $Q(x)$가 참이므로

임의의 변수 $a$가 정의역에 속하면 $P(a)$가 참이고 $Q(a)$가 참이 되어 $\forall x (P(x) \land Q(x)) $가 참이다.

역으로 $\forall x (P(x) \land Q(x)) $가 참이면

정의역에 속하는 모든 $x$에 대해 $P(x) \land Q(x)$가 참이므로

정의역에 속하는 모든 $x$에 대해 $P(x)$가 참이고 정의역에 속하는 모든 $x$에 대해 $Q(x)$가 참이 되어

$\forall xP(x) \land \forall x Q(x)$가 참이다.

$\exists xP(x) \lor \exists x Q(x)$가 참이면

$P(a)$가 참인 정의역에 속하는 변수 $a$가 존재하거나 $Q(b)$가 참인 정의역에 속하는 변수 $b$가 존재하므로

$P(a) \lor Q(a)$가 참이거나 $P(b) \lor Q(b)$가 참이 되어 $\exists x (P(x) \lor Q(x)) $가 참이다.

역으로 $\exists x (P(x) \lor Q(x)) $가 참이면

$P(a) \lor Q(a)$가 참인 정의역에 속하는 변수 $a$가 존재하여 $P(a)$가 참이거나 $Q(a)$가 참이므로

$P(a)$가 참이면 $\exists xP(x)$가 참이고 $Q(a)$가 참이면 $\exists xQ(x)$가 참이 되어 $\exists xP(x) \lor \exists x Q(x)$가 참이다.

$ \forall x (P(x) \to Q(x))$가 참이면 정의역에 속하는 모든 $x$에 대해 $P(x) \to Q(x)$가 참이므로

정의역에 속하는 모든 $x$에 대해 $P(x)$가 참일때 $Q(a)$가 참이 아닌 정의역에 속하는 $a$가 존재하면

$P(a)$가 참일때 $Q(a)$가 참이 아니므로 조건문의 정의로 $P(a) \to Q(a)$가 참이 아니게 되어 모순이다.

따라서 $ \forall x (P(x) \to Q(x))$가 참이면 $ \forall xP(x) \to \forall x Q(x)$가 참이다.

위 정리와 1번으로

$ \forall x (P(x) \leftrightarrow Q(x)) \equiv \forall x ((P(x) \to Q(x)) \land (Q(x) \to P(x))) \equiv \forall x (P(x) \to Q(x)) \land \forall x (Q(x) \to P(x)) $이므로

$ \forall x (P(x) \leftrightarrow Q(x))$가 참이면 $ \forall x (P(x) \to Q(x))$와 $ \forall x (Q(x) \to P(x))$가 참이 되어

위 정리와 3번으로 $ \forall xP(x) \leftrightarrow \forall x Q(x) \equiv (\forall xP(x) \to \forall x Q(x)) \land (\forall xQ(x) \to \forall x P(x)) $는 참이다.

정리8

변수 $x,y$에 대한 명제함수 $P$에 대해 같은 변수로 표기된 한정기호의 정의역이 같다면 다음이 성립한다.

1. $\neg \exists x \forall y P(x,y) \equiv \forall x \exists y \neg P(x,y)$

2. $\forall x \forall y P(x,y) \equiv \forall y \forall x P(x,y)$

3. $\exists x \exists y P(x,y) \equiv \exists y \exists x P(x,y)$

증명

한정기호 부정의 정의로 $\neg \exists x \forall y P(x,y) \equiv \forall x \neg \forall y P(x,y) \equiv \forall x \exists y \neg P(x,y)$이다.

정의역에 속하는 모든 $x$와 모든 $y$에 대해 $P(x,y)$가 참이면

정의역에 속하는 모든 $y$와 모든 $x$에 대해 $P(x,y)$가 참이고

역도 마찬가지이므로 $\forall x \forall y P(x,y) \equiv \forall y \forall x P(x,y)$이다.

$P(x,y)$가 참이 되는 정의역에 속하는 $x$와 $y$가 존재하면

$P(x,y)$가 참이 되는 정의역에 속하는 $y$와 $x$가 존재하고

역도 마찬가지이므로 $\exists x \exists y P(x,y) \equiv \exists y \exists x P(x,y)$이다.

정리9

변수 $x,y$에 대한 명제함수 $P,Q$에 대해 같은 변수로 표기된 한정기호의 정의역이 같다면 다음이 성립한다.

1. $\forall x P(x) \lor \forall y Q(y) \equiv \forall x \forall y (P(x) \lor Q(y))$

2. $\forall x P(x) \land \forall y Q(y) \equiv \forall x \forall y (P(x) \land Q(y))$

3. $\forall x P(x) \lor \exists y Q(y) \equiv \forall x \exists y (P(x) \lor Q(y))$

4. $\forall x P(x) \land \exists y Q(y) \equiv \forall x \exists y (P(x) \land Q(y))$

증명

$\forall x P(x) \lor \forall y Q(y) $가 참일때

$\forall x P(x) $가 참이거나 $\forall y Q(y) $가 참이므로 일반성을 잃지 않고 $\forall x P(x) $가 참이라고 가정하면

정의역에 속하는 모든 $x$에 대해 $y$와는 관계없이 $P(x) \lor Q(y)$가 참이므로 $\forall x \forall y (P(x) \lor Q(y))$가 참이다.

역으로 $\forall x \forall y (P(x) \lor Q(y))$가 참일때

$\forall x P(x) \lor \forall y Q(y) $가 참이 아니라고 가정하면 드 모르간 법칙과 한정기호 부정의 정의로

$ \neg (\forall x P(x) \lor \forall y Q(y) ) \equiv \neg \forall x P(x) \land \neg \forall y Q(y) \equiv \exists x \neg P(x) \land \exists y \neg Q(y) $가 참이 되어

$P(x_0)$이 참이 아닌 정의역에 속하는 $x_0$이 존재하고 $Q(y_0)$이 참이 아닌 정의역에 속하는 $y_0$이 존재하여

정의역에 속하는 모든 $x,y$에 대해 $P(x) \lor Q(y)$가 참인데 $P(x_0) \lor Q(y_0)$은 참이 아니게 되어 모순이다.

따라서 $\forall x \forall y (P(x) \lor Q(y))$가 참이면 $\forall x P(x) \lor \forall y Q(y) $가 참이다.

$\forall x P(x) \land \forall y Q(y)$가 참이면

정의역에 속하는 모든 $x$에 대해 $P(x)$가 참이고 정의역에 속하는 모든 $y$에 대해 $Q(y)$가 참이므로

정의역에 속하는 모든 $x,y$에 대해 $P(x) \land Q(y)$가 참이 되어 $ \forall x \forall y (P(x) \land Q(y))$가 참이다.

역으로 $ \forall x \forall y (P(x) \land Q(y))$일때

$\forall x P(x) \land \forall y Q(y)$가 참이 아니라고 가정하면 드 모르간 법칙과 한정기호 부정의 정의로

$ \neg (\forall x P(x) \land \forall y Q(y) ) \equiv \neg \forall x P(x) \lor \neg \forall y Q(y) \equiv \exists x \neg P(x) \lor \exists y \neg Q(y) $가 참이 되어

$P(x_0)$이 참이 아닌 정의역에 속하는 $x_0$이 존재하거나 $Q(y_0)$이 참이 아닌 정의역에 속하는 $y_0$이 존재하여

정의역에 속하는 모든 $x$에 대해 $P(x) \land Q(y_0)$이 참이 아니거나

정의역에 속하는 모든 $y$에 대해 $P(x_0) \land Q(y)$가 참이 아니게 되어 모순이다.

따라서 $ \forall x \forall y (P(x) \land Q(y))$가 참이면 $\forall x P(x) \land \forall y Q(y)$가 참이다.

$\forall x P(x) \lor \exists y Q(y)$가 참이면

$\forall x P(x)$가 참이거나 $\exists y Q(y)$가 참이므로

$\forall x P(x)$가 참이면 정의역에 속하는 모든 $x$에 대해 $y$와는 관계없이 $P(x) \lor Q(y)$가 참이므로

$\forall x \exists y (P(x) \lor Q(y))$가 참이다.

$\exists y Q(y)$가 참이면 $Q(y_0)$이 참이 되는 정의역에 속하는 $y_0$이 존재하여

정의역에 속하는 모든 $x$에 대해 $P(x) \lor Q(y_0)$이 참인 $y_0$이 존재하므로 $\forall x \exists y (P(x) \lor Q(y))$가 참이다.

역으로 $\forall x \exists y (P(x) \lor Q(y))$가 참일때

$\forall x P(x) \lor \exists y Q(y)$가 참이 아니라고 가정하면 드 모르간 법칙과 한정기호 부정의 정의로

$\neg (\forall x P(x) \lor \exists y Q(y)) \equiv \neg \forall x P(x) \land \neg \exists y Q(y) \equiv \exists x \neg P(x) \land \forall y \neg Q(y) $가 참이 되어

$P(x_0)$이 참이 아닌 정의역에 속하는 $x_0$이 존재하고 정의역에 속하는 모든 $y$에 대해 $Q(y)$가 참이 아니다.

$x_0$이 존재하여 정의역에 속하는 모든 $y$에 대해 $P(x_0) \lor Q(y)$가 참이 아니므로

$\forall x \exists y (P(x) \lor Q(y))$의 부정 $\exists x \forall y \neg (P(x) \lor Q(y))$가 참이 되어 모순이다.

따라서 $\forall x \exists y (P(x) \lor Q(y))$가 참이면 $\forall x P(x) \lor \exists y Q(y)$가 참이다.

$\forall x P(x) \land \exists y Q(y)$가 참이면

$\forall x P(x) $가 참이고 $\exists y Q(y)$가 참이므로 $Q(y_0)$이 참이 되는 정의역에 속하는 $y_0$이 존재하여

정의역에 속하는 모든 $x$에 대해 $P(x) \land Q(y_0)$이 되는 $y_0$이 존재하고 $\forall x \exists y (P(x) \land Q(y))$는 참이다.

역으로 $\forall x \exists y (P(x) \land Q(y))$가 참이면

정의역에 속하는 모든 $x$에 대해 $P(x) \land Q(y_0)$이 참이 되는 정의역에 속하는 $y_0$이 존재하여

정의역에 속하는 모든 $x$에 대해 $P(x)$가 참이고 $Q(y_0)$이 참이 되는 정의역에 속하는 $y_0$이 존재하므로

$\forall x P(x)$가 참이고 $\exists y Q(y)$가 참이 되어 $\forall x P(x) \land \exists y Q(y)$가 참이다.

정의7

불 대수(Boolean algebra) :

집합 $B$와 이항연산 $\lor, \land : B\times B \to B$과 일항연산 $\neg : B \to B$과 어떤 상수 $\mathbf{F},\mathbf{T} \in B$에 대해

아래 성질을 만족하는 $6$-순서쌍 $(B,\lor,\land,\neg,\mathbf{F},\mathbf{T})$을 불 대수로 정의한다.

모든 $x,y \in B$에 대해 $\lor(x,y) = x \lor y$와 $\land(x,y) = x \land y$와 $\neg(x) = \neg x$로 표기하고

이항연산 $\to, \leftrightarrow : B\times B \to B$를 $x\to y = \neg x \lor y$와 $x\leftrightarrow y = (x \to y) \land (y\to x)$로 정의한다.

또 $\lor, \land ,\neg,\to,\leftrightarrow$의 연산순서는 결합자 연산순서와 똑같이 정의한다.

연산에 닫힘 :

모든 $x \in B$에 대해 $\neg x \in B$이다.

모든 $x,y \in B$에 대해 $x \lor y \in B$이다.

모든 $x,y \in B$에 대해 $ x\land y \in B$이다.

교환법칙 :

모든 $x,y \in B$에 대해 $x\lor y = y\lor x $이다.

모든 $x,y \in B$에 대해 $x\land y = y\land x $이다.

분배법칙 :

모든 $x,y,z \in B$에 대해 $x \lor (y \land z) = (x\lor y) \land (x \lor z)$이다.

모든 $x,y ,z \in B$에 대해 $x \land (y \lor z) = (x\land y) \lor (x \land z)$이다.

항등법칙 :

모든 $x \in B$에 대해 $x \lor \mathbf{F} = x$이다.

모든 $x \in B$에 대해 $x \land \mathbf{T} = x$이다.

부정법칙 :

모든 $x \in B$에 대해 $x \lor \neg x = \mathbf{T}$이다.

모든 $x \in B$에 대해 $x \land \neg x = \mathbf{F}$이다.

정리10

임의의 불 대수 $(B,\lor,\land,\neg,\mathbf{F},\mathbf{T})$와 $\to$ $ : B\times B \to B$와 모든 $x,y,z \in B$에 대해 다음이 성립한다.

1. $x \lor y = \mathbf{T}$이고 $x \land y = \mathbf{F}$이기 위한 필요충분조건은 $y = \neg x$이다.

2. $\neg (\neg x) = x$

3. $x \land x = x = x \lor x$

4. $\mathbf{F} = \neg \mathbf{T}$이고 $\mathbf{T} = \neg \mathbf{F}$이다.

5. $x \land \mathbf{F} = \mathbf{F}$이고 $x \lor \mathbf{T} = \mathbf{T}$이다.

6. $x \land (x \lor y) = x = x \lor (x \land y)$

7. $y \land x = z \land x$이고 $y \land \neg x = z \land \neg x$이면 $y = z$이다.

8. $x \lor (y \lor z) = (x \lor y) \lor z$이고 $x \land (y \land z) = (x \land y) \land z$이다.

9. $\neg (x \lor y) = \neg x \land \neg y$이고 $\neg (x \land y) = \neg x \lor \neg y$이다.

10. $x \to y = \neg y \to \neg x$

11. $x \lor y = \neg x \to y$

12. $x \land y = \neg (x \to \neg y)$

13. $x = \mathbf{T}$이고 $x \to y = \mathbf{T}$이면 $y = \mathbf{T}$이다.

증명

$x \lor y = \mathbf{T}$이고 $x \land y = \mathbf{F}$이면 불 대수의 성질들로

$y = y\lor \mathbf{F} = y \lor (x \land \neg x) = (y \lor x) \land (y \lor \neg x) = (x\lor y) \land (y \lor \neg x) =\mathbf{T} \land (y \lor \neg x) = (y \lor \neg x ) \land \mathbf{T} = (y \lor \neg x) \text{ 이고}$

$\neg x = \neg x \lor \mathbf{F} = \neg x \lor (x \land y) =( \neg x \lor x) \land (\neg x \lor y) = \mathbf{T} \land (\neg x \lor y)= \mathbf{T} \land (y \lor \neg x) = \mathbf{T} \land y = y \land \mathbf{T} = y \text{ 이다.}$

역으로 $y = \neg x$이면

불 대수의 성질들로 $x \lor y = x \lor \neg x = \mathbf{T}$이고 $x \land y = x\land \neg x = \mathbf{F}$이다.

불 대수의 성질들로 $\neg x \lor x = x \lor \neg x = \mathbf{T}$이고 $\neg x \land x = x\land \neg x = \mathbf{F}$이므로 1번으로 $x = \neg (\neg x)$이다.

불 대수의 성질들로

$x = x\land \mathbf{T} = x \land (x\lor \neg x) = (x \land x) \lor (x \land \neg x) = (x \land x) \lor \mathbf{F} = x \land x$이고

$x = x\lor \mathbf{F} = x \lor (x \land \neg x) = (x \lor x) \land (x \lor \neg x) = (x \lor x) \land \mathbf{T} = x \lor x$이다.

불 대수의 성질들로 $\mathbf{T} \lor \mathbf{F} = \mathbf{T}$이고 $\mathbf{T} \land \mathbf{F} = \mathbf{F} \land \mathbf{T} = \mathbf{F}$이므로 1번으로 $\mathbf{F} = \neg \mathbf{T}$이다.

불 대수의 성질들로 $\mathbf{F} \lor \mathbf{T} = \mathbf{T} \lor \mathbf{F} = \mathbf{T}$이고 $\mathbf{F} \land \mathbf{T} = \mathbf{F}$이므로 1번으로 $\mathbf{T} = \neg \mathbf{F}$이다.

불 대수의 성질들로

$x \land \mathbf{F} = (x \land \mathbf{F}) \lor \mathbf{F} = (x \land \mathbf{F}) \lor (x \land \neg x) = x\land (\mathbf{F} \lor \neg x) = x \land (\neg x \lor \mathbf{F}) = x \land \neg x = \mathbf{F}$이고

$x \lor \mathbf{T} = (x \lor \mathbf{T}) \land \mathbf{T} = (x \lor \mathbf{T}) \land (x \lor \neg x) = x\lor (\mathbf{T} \land \neg x) = x \lor (\neg x \land \mathbf{T}) = x \lor \neg x = \mathbf{T}$이다.

불 대수의 성질들과 5번으로

$x \land (x \lor y) = (x \lor \mathbf{F}) \land (x \lor y) = x\lor (\mathbf{F} \land y) = x \lor (y \land \mathbf{F}) = x \lor \mathbf{F} = x$이고

$x \lor (x \land y) = (x \land \mathbf{T}) \lor (x \land y) = x\land (\mathbf{T} \lor y) = x \land (y \lor \mathbf{T}) = x \land \mathbf{T} = x$이다.

$y \land x = z \land x$이고 $y \land \neg x = z \land \neg x$이면 불 대수의 성질들로

$y = y \land \mathbf{T} = y \land (x \lor \neg x) = (y \land x) \lor (y \land \neg x) = (z \land x) \lor (z \land \neg x) = z\land (x \lor \neg x) = z \land \mathbf{T} = z$이다.

불 대수의 성질들과 6번으로

$(x \lor (y \lor z)) \land x = x \land (x \lor (y \lor z)) = x$이고

$((x \lor y) \lor z) \land x = x \land ((x \lor y) \lor z) = (x \land (x \lor y)) \lor (x \land z) = x \lor (x \land z) = x$이므로

$(x \lor (y \lor z)) \land x = x = ((x \lor y) \lor z) \land x$이다.

또 불 대수의 성질들로

$(x \lor (y \lor z)) \land \neg x = \neg x \land (x \lor (y \lor z)) = (\neg x \land x ) \lor (\neg x \land (y \lor z)) = \mathbf{F} \lor (\neg x \land (y \lor z)) = \neg x \land (y \lor z) \text{ 이고}$

$\begin{align*} ((x \lor y) \lor z) \land \neg x & = \neg x \land ((x \lor y) \lor z) \\[0.5em] & = (\neg x \land ( x \lor y)) \lor (\neg x \land z) \\[0.5em] & = ((\neg x \land x) \lor (\neg x \land y)) \lor (\neg x \land z) \\[0.5em] & = (\mathbf{F} \lor (\neg x \land y)) \lor (\neg x \land z) \\[0.5em] & = (\neg x \land y) \lor (\neg x \land z) \\[0.5em] & = \neg x \land (y \lor z) \text{ 이므로} \end{align*}$

$(x \lor (y \lor z)) \land \neg x = \neg x \land (y \lor z) = ((x \lor y) \lor z) \land \neg x$가 되어

7번으로 $x \lor (y \lor z) = (x \lor y) \lor z$이다.

불 대수의 성질들과 6번으로

$(x \land (y \land z)) \lor x = x \lor (x \land (y \land z)) = x$이고

$((x \land y) \land z) \lor x = x \lor ((x \land y) \land z) = (x \lor (x \land y)) \land (x \lor z) = x \land (x \lor z) = x$이므로

$(x \land (y \land z)) \lor x = x = ((x \land y) \lor z) \land x$이다.

또 불 대수의 성질들로

$(x \land (y \land z)) \lor \neg x = \neg x \lor (x \land (y \land z)) = (\neg x \lor x ) \land (\neg x \lor (y \land z)) = \mathbf{T} \land (\neg x \lor (y \land z)) = \neg x \lor (y \land z) \text{ 이고}$

$\begin{align*} ((x \land y) \land z) \lor \neg x & = \neg x \lor ((x \land y) \land z) \\[0.5em] & = (\neg x \lor ( x \land y)) \land (\neg x \lor z) \\[0.5em] &= ((\neg x \lor x) \land (\neg x \lor y)) \land (\neg x \lor z) \\[0.5em] & = (\mathbf{T} \land (\neg x \lor y)) \land (\neg x \lor z) \\[0.5em] & = (\neg x \lor y) \land (\neg x \lor z) \\[0.5em] & = \neg x \lor (y \land z) \text{ 이므로} \end{align*}$

$(x \land (y \land z)) \lor \neg x = \neg x \lor (y \land z) = ((x \land y) \land z) \lor \neg x$가 되어

7번으로 $x \land (y \land z) = (x \land y) \land z$이다.

불 대수의 성질들과 5, 8번으로

$\begin{align*}(x \lor y) \land (\neg x \land \neg y)& = (\neg x \land \neg y) \land (x \lor y) \\[0.5em] &= ((\neg x \land \neg y) \land x) \lor ((\neg x \land \neg y) \land y) \\[0.5em] &= (x \land (\neg x \land \neg y)) \lor (\neg x \land (\neg y \land y)) \\[0.5em] &= ((x \land \neg x) \land \neg y) \lor (\neg x \land \mathbf{F} ) \\[0.5em] &= (\mathbf{F} \land \neg y) \lor \mathbf{F} \\[0.5em] &= \mathbf{F} \lor \mathbf{F} \\[0.5em] &= \mathbf{F} \text{ 이고}\end{align*}$

$\begin{align*} (x \lor y) \lor (\neg x \land \neg y) & = ( (x \lor y) \lor \neg x) \land ( (x \lor y) \lor \neg y) \\[0.5em] &= ( \neg x \lor (x \lor y) ) \land ( x \lor (y \lor \neg y) ) \\[0.5em] &= ( (\neg x \lor x) \lor y ) \land ( x \lor \mathbf{T} ) \\[0.5em] &= ( \mathbf{T} \lor y) \land \mathbf{T} \\[0.5em] &= \mathbf{T} \land \mathbf{T} \\[0.5em] & = \mathbf{T} \text{ 이므로}\end{align*}$

1번으로 $ \neg x \land \neg y = \neg (x \lor y)$이다.

불 대수의 성질들과 5, 8번으로

$\begin{align*}(x \land y) \lor (\neg x \lor \neg y)& = (\neg x \lor \neg y) \lor (x \land y) \\[0.5em] &= ((\neg x \lor \neg y) \lor x) \land ((\neg x \lor \neg y) \lor y) \\[0.5em] &= (x \lor (\neg x \lor \neg y)) \land (\neg x \lor (\neg y \lor y)) \\[0.5em] &= ((x \lor \neg x) \lor \neg y) \land (\neg x \lor \mathbf{T} ) \\[0.5em] &= (\mathbf{T} \lor \neg y) \land \mathbf{T} \\[0.5em] &= \mathbf{T} \land \mathbf{T} \\[0.5em] &= \mathbf{T} \text{ 이고}\end{align*}$

$\begin{align*} (x \land y) \land (\neg x \lor \neg y) & = ( (x \land y) \land \neg x) \lor ( (x \land y) \land \neg y) \\[0.5em] &= ( \neg x \land (x \land y) ) \lor ( x \land (y \land \neg y) ) \\[0.5em] &= ( (\neg x \land x) \land y ) \lor ( x \land \mathbf{F} ) \\[0.5em] &= ( \mathbf{F} \land y) \lor \mathbf{F} \\[0.5em] &= \mathbf{F} \lor \mathbf{F} \\[0.5em] & = \mathbf{F} \text{ 이므로}\end{align*}$

1번으로 $ \neg x \lor \neg y = \neg (x \land y)$이다.

10.

$\to$의 정의와 불 대수의 성질과 2번으로 $x \to y = \neg x \lor y = y \lor \neg x = \neg (\neg y) \lor \neg x = \neg y \to \neg x$이다.

11.

$\to$의 정의와 2번으로 $x \lor y = \neg (\neg x) \lor y = \neg x \to y$이다.

12.

$\to$의 정의와 불 대수의 성질과 2, 9번으로 $x \land y = \neg ( \neg (x \land y)) = \neg (\neg x \lor \neg y) = \neg (x \to \neg y)$이다.

13.

$x = \mathbf{T}$이고 $x \to y = \mathbf{T}$일때 $y \ne \mathbf{T}$라고 가정하면

$\to$의 정의와 불 대수의 성질과 4번으로 $\mathbf{T} = x \to y = \mathbf{T} \to y = \neg \mathbf{T} \lor y = \mathbf{F} \lor y = y\lor \mathbf{F} = y$가 되어

$y \ne \mathbf{T}$임에 모순이므로 $x = \mathbf{T}$이고 $x \to y = \mathbf{T}$이면 $y = \mathbf{T}$이다.

정리11

임의의 불 대수 $(B,\lor,\land,\neg,\mathbf{F},\mathbf{T})$에 대해 다음이 성립한다.

1. 항등법칙과 위 정리 4번을 만족하는 $\mathbf{F},\mathbf{T}$는 유일하다.

2. $(\{ \mathbf{F} ,\mathbf{T}\},\lor,\land,\neg,\mathbf{F},\mathbf{T})$는 불 대수이다.

증명

$x \lor \mathbf{F}_1 = x = x\lor \mathbf{F}_2$와 $x \land \mathbf{T}_1 = x = x\land \mathbf{T}_2$가 성립하고

$\mathbf{T}_1 = \neg \mathbf{F}_1$와 $\mathbf{T}_2 = \neg \mathbf{F}_2$와 $\mathbf{F}_1 = \neg \mathbf{T}_1$와 $\mathbf{F}_2 = \neg \mathbf{T}_2$가 성립하는 $\mathbf{F}_1,\mathbf{F}_2,\mathbf{T}_1,\mathbf{T}_2 \in B$가 존재하면

불 대수의 성질과 위 정리로

$\mathbf{T}_1 \land \neg x=\neg x \land \neg \mathbf{F}_1 = \neg (x \lor \mathbf{F}_1) = \neg x= \neg (x \lor \mathbf{F}_2) = \neg x \land \neg \mathbf{F}_2 = \mathbf{T}_2 \land \neg x$이고

$\mathbf{T}_1 \land x = x \land \mathbf{T}_1 = x = x\land \mathbf{T}_2 = \mathbf{T}_2 \land x$가 되어 $\mathbf{T}_1 = \mathbf{T}_2$이고 $\mathbf{F}_1 = \neg \mathbf{T}_1 = \neg \mathbf{T}_2 = \mathbf{F}_2$이다.

$\{\mathbf{F},\mathbf{T}\} \subseteq B$는 불 대수의 성질이 성립하고 위 정리로

$\mathbf{T} = \neg \mathbf{F} , \mathbf{F} = \neg \mathbf{T} \in \{ \mathbf{F},\mathbf{T} \}$이고

$\mathbf{T} \lor \mathbf{T} = \mathbf{T}, \mathbf{T} \lor \mathbf{F} = \mathbf{T} = \mathbf{F} \lor \mathbf{T} , \mathbf{F} \lor \mathbf{F} = \mathbf{F} \in \{\mathbf{F}, \mathbf{T} \}$이고

$\mathbf{T} \land \mathbf{T} = \mathbf{T}, \mathbf{T} \land \mathbf{F} = \mathbf{F} = \mathbf{F} \land \mathbf{T} , \mathbf{F} \land \mathbf{F} = \mathbf{F} \in \{ \mathbf{F} ,\mathbf{T} \}$이므로

$\{\mathbf{F},\mathbf{T}\}$는 $\lor ,\land ,\neg $에 대해 닫혀있어 $(\{ \mathbf{F} ,\mathbf{T}\},\lor,\land,\neg,\mathbf{F},\mathbf{T})$는 불 대수이다.

정리12

임의의 집합 $X$의 멱집합 $\mathcal{P}(X)$와 집합연산 $\cup,\cap , \setminus $에 대해 $(\mathcal{P}(X),\cup,\cap,X \setminus \cdot,\emptyset,X)$는 불 대수이다.

증명

멱집합의 정의로 $A \in \mathcal{P}(X)$이기 위한 필요충분조건은 $A \subseteq X$이므로 모든 $A ,B \in \mathcal{P}(X)$에 대해

$x \in X \setminus A$이면 $x \in X$이고 $x \notin A \subseteq X$이므로 $X \setminus A \in \mathcal{P}(X)$가 되어 $ \mathcal{P}(X)$는 $X \setminus \cdot$에 대해 닫혀있고

$x \in A\cup B$이면 $x \in A \subseteq X$ 또는 $x \in B \subseteq X$이므로 $A\cup B \in \mathcal{P}(X)$이고

$x \in A\cap B$이면 $x \in A \subseteq X$이고 $x \in B \subseteq X$이므로 $A \cap B \in \mathcal{P}(X)$가 되어 $ \mathcal{P}(X)$는 $\cup,\cap $에 대해 닫혀있다.

집합 연산정리로 교환법칙이 성립하고 집합 정리로 분배법칙이 성립하고

공집합 정리와 포함관계 정리로 $A \cup \emptyset = A$이고 $A \cap X = A \subseteq X$인 항등법칙이 성립하고

집합 정리와 포함관계 정리로 $A\cup (X \setminus A) = X \cup A = X$이고 $A \cap (X \setminus A) = \emptyset$인 부정법칙이 성립하여

$(\mathcal{P}(X),\cup,\cap,X \setminus \cdot,\emptyset,X)$는 불 대수이다.

-------------------------------------------------------------------------------

정의의 링크 :

https://openknowledgevl.tistory.com/41#def번호

번호는 해당 정의 옆에 붙어있는 작은 숫자입니다.

정리의 링크 :

https://openknowledgevl.tistory.com/41#thm번호

번호는 해당 정리 옆에 붙어있는 작은 숫자입니다.

위 내용은 아래의 출처를 기반으로 정리한 내용입니다.

틀린 내용이 존재할 수 있습니다.

출처(저자 - 제목 - ISBN13)

Kenneth H. Rosen - Discrete Mathematics and Its applications - 9791132102229

Elliott Mendelson - Schaum's Outline of Boolean Algebra and Switching Circuits - 9780070414600

'수학 > 수리논리학' 카테고리의 다른 글

일차논리(First-order logic) (0)	2023.12.15
형식논리(Formal logic), 명제논리(Propositional logic) (0)	2023.12.05
증명(Proof), 귀납법(Induction) (0)	2023.05.26

정의1

정의2