1-7 对偶与范式

$\{\neg, \lor\}$ $\{\neg, \land\}$ $\{\neg, \lor, \land\}$ 表 1-4.8 $\lor$ $\land$ 互换。我们把这样的公式称作具有对偶规律。

$\lor$ $\land$ $\land$ $\lor$ $F$ $T$ $A^*$ $A$ 的对偶式。

例题1

写出下列表达式的对偶式

$(P \lor Q) \land R$

$(P \land Q) \lor T$

$\neg (P \lor Q) \land (P \lor \neg (Q \land \neg S))$

\begin{aligned} 解 & 这 些 表 达 式 的 对 偶 式 是 ： \\ (a) (P \land Q) \lor R \\ (b) (P \lor Q) \land F \\ (c) \neg (P \land Q) \lor (P \land \neg (Q \lor \neg S)) \end{aligned}

例题2

$P \uparrow Q$ $P \downarrow Q$ 的对偶式。

\begin{array}{r} 解 因 为 P ↑ Q ⟺ \neg (P \land Q) ， 故 P ↑ Q 的 对 偶 式 为 \neg (P \lor Q) ， 即 P ↓ Q 。 同 理 P ↓ Q 的 对 偶 式 是 P ↑ Q 。 \end{array}

$A$ $A^*$ $P_1, P_2, \cdots, P_n$ $A$ $A^*$ 中的原子变元，则

\begin{aligned} \neg A (P_{1}, P_{2}, \dots, P_{n}) & ⟺ A * (\neg P_{1}, \neg P_{2}, \dots, \neg P_{n}) \\ A (\neg P 1, \neg P_{2}, \dots, \neg P_{n}) & ⟺ \neg A * (P_{1}, P_{2}, \dots, P_{n}) \end{aligned}

证明由德·摩根定律

P \land Q ⟺ \neg (\neg P \lor \neg Q), P \lor Q ⟺ \neg (\neg P \land \neg Q)

故

\neg A (P_{1}, P_{2}, \dots, P_{n}) ⟺ A^{*} (\neg P_{1}, \neg P_{2}, \dots, \neg P_{n})

同理

\neg A^{*} (P_{1}, P_{2}, \dots, P_{n}) ⟺ A (\neg P_{1}, \neg P_{2}, \dots, \neg P_{n})

例题3

$A^*(S, W, R)$ $\neg S \land (\neg W \lor R)$ ，证明

A^{*} (\neg S, \neg W, \neg R) ⟺ \neg A (S, W, R)

$A^*(S, W, R)$ $\neg S \land (\neg W \lor R)$ $A^*(\neg S, \neg W, \neg R)$ $S \land (W \lor \neg R)$ $A(S, W, R)$ $\neg S \lor (\neg W \land R)$ $\neg A(S, W, R)$ $\neg (\neg S \lor (\neg W \land R)) \iff S \land (W \lor \neg R)$ 。

所以

A^{*} (\neg S, \neg W, \neg R) ⟺ \neg A (S, W, R)

定理 1-7.2： $P_1, P_2, \cdots, P_n$ $A$ $B$ $A \iff B$ $A^* \iff B^*$ 。

$A \iff B$ ，即

A (P_{1}, P_{2}, \dots, P_{n}) \leftrightarrow B (P_{1}, P_{2}, \dots, P_{n})

是一个重言式，故

A (\neg P_{1}, \neg P_{2}, \dots, \neg P_{n}) \leftrightarrow B (\neg P_{1}, \neg P_{2}, \dots, \neg P_{n})

也是一个重言式。即

A (\neg P_{1}, \neg P_{2}, \dots, \neg P_{n}) ⟺ B (\neg P_{1}, \neg P_{2}, \dots, \neg P_{n})

由定理 1-7.1 得

\neg A^{*} (P_{1}, P_{2}, \dots, P_{n}) ⟺ \neg B^{*} (P_{1}, P_{2}, \dots, P_{n})

因此

A^{*} ⟺ B^{*}

例题4

$A(P, Q, R)$ $P \uparrow (Q \land \neg (R \downarrow P))$ $A^*(P, Q, R)$ $A$ $A^*$ $\land$ $\lor$ $\neg$ ”的公式。

\begin{aligned} 解 & 因 A (P, Q, R) 是 P ↑ (Q \land \neg (R ↓ P)) \\ 故 & A^{*} (P, Q, R) 是 P ↓ (Q \lor \neg (R ↑ P)) \\ 但 & P ↑ (Q \land \neg (R ↓ P)) ⟺ \neg (P \land (Q \land (R \lor P))) \\ 所 以 & P ↓ (Q \lor \neg (R ↑ P)) ⟺ \neg (P \lor (Q \lor (R \land P))) \end{aligned}

定义 1-7.2：一个命题公式称为合取范式，当且仅当它具有型式：

A_{1} \land A_{2} \land \dots \land A_{n}, (n ⩾ 1)

$A_1, A_2, \cdots, A_n$ 都是由命题变元或其否定所组成的析取式。

$(P \lor \neg Q \lor R) \land (\neg P \lor Q) \land \neg Q$ 是一个合取范式。

定义 1-7.3：一个命题公式称为析取范式，当且仅当它具有型式：

A_{1} \lor A_{2} \lor \dots \lor A_{n}, (n ⩾ 1)

$A_1, A_2, \cdots, A_n$ 都是由命题变元或其否定所组成的合取式。

$\neg P \lor (P \land Q) \lor (P \land \neg Q \land R)$ 是析取范式。

任何一个命题公式，求它的合取范式或析取范式，可以通过下面三个步骤进行：

$\land$ $\lor$ $\neg$ 。

$\neg$ 直接移到各个命题变元之前。

(3) 利用分配律、结合律将公式归约为合取范式或析取范式。

例题5

$(P \land (Q \to R)) \to S$ 的合取范式。

\begin{aligned} 解 (P \land (Q \to R)) \to S & ⟺ (P \land (\neg Q \lor R)) \to S \\ ⟺ \neg (P \land (\neg Q \lor R)) \lor S ⟺ \neg P \lor (Q \land \neg R) \lor S \\ ⟺ (\neg P \lor S) \lor (Q \land \neg R) \\ ⟺ (\neg P \lor S \lor R) \land (\neg P \lor S \lor \neg R) \end{aligned}

例题6

$\neg (P \lor Q) \leftrightarrow (P \land Q)$ 的析取范式。

\begin{aligned} 解 因 为 有 公 式 (A \leftrightarrow B) & ⟺ (A \land B) \lor (\neg A \land \neg B) \\ 故 \neg (P \lor Q) \leftrightarrow (P \land Q) & ⟺ (\neg (P \lor Q) \land (P \land Q)) \lor ((P \lor Q) \land \neg (P \land Q)) \\ ⟺ (\neg P \land \neg Q \land P \land Q) \lor ((P \lor Q) \land (\neg P \lor \neg Q)) \\ ⟺ (\neg P \land \neg Q \land P \land Q) \lor (P \land \neg P) \lor (Q \land \neg P) \lor (P \land \neg Q) \lor (Q \land \neg Q) \end{aligned}

$P \lor (Q \land R)$ 是一个析取范式，但它亦可以写成

\begin{aligned} P \lor (Q \land R) & ⟺ (P \lor Q) \land (P \lor R) \\ ⟺ (P \land P) \lor (P \land R) \lor (Q \land P) \lor (Q \land R) \end{aligned}

为了使任意一个命题公式，化成唯一的等价命题的标准形式，下面介绍主范式的有关概念。

$n$ 个命题变元的合取式，称作布尔合取或小项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。

$P$ $Q$ $P \land Q$ $P \land \neg Q$ $\neg P \land Q$ $\neg P \land \neg Q$ 。

$P$ $Q$ $R$ $P \land Q \land R$ $P \land Q \land \neg R$ $P \land \neg Q \land R$ $P \land \neg Q \land \neg R$ $\neg P \land Q \land R$ $\neg P \land Q \land \neg R$ $\neg P \land \neg Q \land R$ $\neg P \land \neg Q \land \neg R$ 。

$n$ $2^n$ 个小项。

表 1-7.1 $P$ $Q$ 及其小项的真值表。

表 1-7.1

$P$	$Q$	$P \land Q$	$P \land \neg Q$	$\neg P \land Q$	$\neg P \land \neg Q$
$T$	$T$	$T$	$F$	$F$	$F$
$T$	$F$	$F$	$T$	$F$	$F$
$F$	$T$	$F$	$F$	$T$	$F$
$F$	$F$	$F$	$F$	$F$	$T$

$P$ $Q$ $T$ 。

$n$ 个变元的小项可以很快地写出来。现按三个变元为例说明如下。

$P$ $Q$ $R$ $T$ $F$ $1$ $0$ ”，则小项的真值表如表 1-7.2 所示。

表 1-7.2

$P$	$Q$	$R$	$\neg P \land \neg Q \land \neg R$	$\neg P \land \neg Q \land R$	$\neg P \land Q \land \neg R$	$\neg P \land Q \land R$
$0$	$0$	$0$	$1$	$0$	$0$	$0$
$0$	$0$	$1$	$0$	$1$	$0$	$0$
$0$	$1$	$0$	$0$	$0$	$1$	$0$
$0$	$1$	$1$	$0$	$0$	$0$	$1$
$1$	$0$	$0$	$0$	$0$	$0$	$0$
$1$	$0$	$1$	$0$	$0$	$0$	$0$
$1$	$1$	$0$	$0$	$0$	$0$	$0$
$1$	$1$	$1$	$0$	$0$	$0$	$0$

$P$	$Q$	$R$	$P \land \neg Q \land \neg R$	$P \land \neg Q \land R$	$P \land Q \land \neg R$	$P \land Q \land R$
$0$	$0$	$0$	$0$	$0$	$0$	$0$
$0$	$0$	$1$	$0$	$0$	$0$	$0$
$0$	$1$	$0$	$0$	$0$	$0$	$0$
$0$	$1$	$1$	$0$	$0$	$0$	$0$
$1$	$0$	$0$	$1$	$0$	$0$	$0$
$1$	$0$	$1$	$0$	$1$	$0$	$0$
$1$	$1$	$0$	$0$	$0$	$1$	$0$
$1$	$1$	$1$	$0$	$0$	$0$	$1$

\begin{aligned} m_{000} = \neg P \land \neg Q \land \neg R & m_{100} & = P \land \neg Q \land \neg R \\ m_{001} = \neg P \land \neg Q \land R & m_{101} & = P \land \neg Q \land R \\ m_{010} = \neg P \land Q \land \neg R & m_{110} & = P \land Q \land \neg R \\ m_{011} = \neg P \land Q \land R & m_{111} & = P \land Q \land R \end{aligned}

小项有如下几个性质：

$T$ $2^n - 1$ $F$ 。

(2) 任意两个不同小项的合取式永假。例如

\begin{aligned} m_{001} \land m_{100} & = (\neg P \land \neg Q \land R) \land (P \land \neg Q \land \neg R) \\ ⟺ \neg P \land P \land \neg Q \land R \land \neg R ⟺ F \end{aligned}

(3) 全体小项的析取式永为真，记为：

\sum_{i = 0}^{2^{n} - 1} m_{i} = m_{0} \lor m_{1} \lor \dots \lor m_{2^{n} - 1} ⟺ T

定义 1-7.5：对于给定的命题公式，如果有一个等价公式，它仅由小项的析取所组成，则该等价式称作原式的主析取范式。

$T$ 的指派所对应的小项的析取，即为此公式的主析取范式。

$A$ $T$ $m_1^{'}, m_2^{'}, \cdots, m_k^{'}$ $B$ $A \iff B$ $A$ $B$ 在相应指派下具有相同真值。

$A$ $T$ $m_i^{'}$ $m_i^{'}$ $T$ $m_1^{'}, m_2^{'}, \cdots, m_{i - 1}^{'}, m_{i + 1}^{'}, \cdots, m_k^{'}$ $F$ $B$ $T$ 。

$A$ $F$ $B$ $m_1^{'}, m_2^{'}, \cdots, m_k^{'}$ $F$ $B$ $F$ $A \iff B$ 。

例题7

$P \to Q$ $P \lor Q$ $\neg (P \land Q)$ ，求这些公式的主析取范式。

解三公式的真值表如表 1-7.3 所示。故

\begin{aligned} P \to Q & ⟺ (\neg P \land \neg Q) \lor (\neg P \land Q) \lor (P \land Q) \\ P \lor Q & ⟺ (\neg P \land Q) \lor (P \land \neg Q) \lor (P \land Q) \\ \neg (P \land Q) & ⟺ (\neg P \land \neg Q) \lor (\neg P \land Q) \lor (P \land \neg Q) \end{aligned}

表 1-7.3

$P$	$Q$	$P \to Q$	$P \lor Q$	$\neg (P \land Q)$
$T$	$T$	$T$	$T$	$F$
$T$	$F$	$F$	$T$	$T$
$F$	$T$	$T$	$T$	$T$
$F$	$F$	$T$	$F$	$T$

例题8

$A$ 的真值表如表 1-7.4 所示。

表 1-7.4

$P$	$Q$	$R$	$A$
$T$	$T$	$T$	$T$
$T$	$T$	$F$	$F$
$T$	$F$	$T$	$F$
$T$	$F$	$F$	$T$
$F$	$T$	$T$	$F$
$F$	$T$	$F$	$F$
$F$	$F$	$T$	$F$
$F$	$F$	$F$	$T$

$A$ 的主析取范式。

解 ： 公 式 A 的 主 析 取 范 式 为 ： A ⟺ (P \land Q \land R) \lor (P \land \neg Q \neg R) \lor (\neg P \neg Q \land \neg R)

除了用真值表方法外，也可利用等价公式构成主析取范式。

例题9

$(P \land Q) \lor (\neg P \land R) \lor (Q \land R)$ 的主析取范式。

\begin{aligned} 解 原 式 & ⟺ (P \land Q \land (R \lor \neg R)) \lor (\neg P \land R \land (Q \lor \neg Q)) \lor (Q \land R \land (P \lor \neg P)) \\ ⟺ (P \land Q \land R) \lor (P \land Q \land \neg R) \lor (\neg P \land R \land Q) \lor (\neg P \land R \land \neg Q) \end{aligned}

例题10

$P \to ((P \to Q) \land \neg (\neg Q \lor \neg P))$ 的主析取范式。

\begin{aligned} 解 P & \to ((P \to Q) \land \neg (\neg Q \lor \neg P)) \\ ⟺ \neg P \lor ((\neg P \lor Q) \land (Q \land P)) \\ ⟺ \neg P \lor ((\neg P \land Q \land P) \lor (Q \land Q \land P)) \\ ⟺ \neg P (\neg P \land Q \land P) \lor (Q \land P) \\ ⟺ \neg P \lor (Q \land P) \\ ⟺ (\neg P \land (Q \lor \neg R)) \lor (Q \land P) \\ ⟺ (\neg P \land Q) \lor (\neg P \land \neg Q) \lor (P \land Q) \end{aligned}

由上述各例我们看到，一个命题公式的主析取范式，可由两种方法构成。一是由公式的真值表得出，另一是由基本等价公式推出。其推演步骤可归纳为：

(1) 化归为析取范式。

(2) 除去析取范式中所有永假的析取项。

(3) 将析取式中重复出现的合取项和相同的变元合并。

$(P \lor \neg P)$ 式，然后，应用分配律展开公式。

对于一个命题公式的主析取范式，如将其命题变元的个数及出现次序固定后，则此公式的主析取范式便是唯一的，因此，给定任两个公式，由主析取范式可以方便地看出两个公式是否等价。

与主析取范式类似的是主合取范式。

$n$ 个命题变元的析取式，称作布尔析取或大项。其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。例如

P \lor Q, P \lor \neg Q, \neg P \lor Q, \neg P \lor \neg Q

又如

P \lor Q \lor R, P \lor Q \lor \neg R, \dots, \neg P \lor \neg Q \lor R

$n$ 位二进制予以编码：

$n == 2$

\begin{aligned} M_{00} = P \lor Q, & M_{01} & = P \lor \neg Q \\ M_{10} = \neg P \lor Q, & M_{11} & = \neg P \lor \neg Q \end{aligned}

$n == 3$

\begin{aligned} M_{000} = P \lor Q \lor R, & M_{100} & = \neg P \lor Q \lor R \\ M_{001} = P \lor Q \lor \neg R, & M_{101} & = \neg P \lor Q \lor \neg R \\ M_{010} = P \lor \neg Q \lor R, & M_{110} & = \neg P \lor \neg Q \lor R \\ M_{011} = P \lor \neg Q \lor \neg R, & M_{111} & = \neg P \lor \neg Q \lor \neg R \end{aligned}

大项有如下性质：

$F$ $2^n - 1$ $T$ 。

(2) 任意两个不同大项的析取式为永真。

M_{i} \lor M_{j} ⟺ T (i \neq j)

(3) 全体大项的合取式必为永假，记为：

\prod_{t = 0}^{2^{n} - 1} M_{i} = M_{0} \land M_{1} \land \dots \land M_{2^{n} - 1} ⟺ F

定义 1-7.7：对于给定的命题公式，如果有一个等价公式，它仅由大项的合取所组成，则该等价式称作原式的主合取范式。

$F$ 的指派所对应的大项的合取，即为此公式的主合取范式。

例题11

$(P \land Q) \lor (\neg P \land R)$ 的主合取范式与析取范式。

$(P \land Q) \lor (\neg P \land R)$ 的真值表如表 1-7.5 所示。

表 1-7.5

$P$	$Q$	$R$	$P \land Q$	$\neg P \land R$	$(P \land Q) \lor (\neg P \land R)$
$T$	$T$	$T$	$T$	$F$	$T$
$T$	$T$	$F$	$T$	$F$	$T$
$T$	$F$	$T$	$F$	$F$	$F$
$T$	$F$	$F$	$F$	$F$	$F$
$F$	$T$	$T$	$F$	$T$	$T$
$F$	$T$	$F$	$F$	$F$	$F$
$F$	$F$	$T$	$F$	$T$	$T$
$F$	$F$	$F$	$F$	$F$	$F$

故主合取范式为：

(P \land Q) \lor (\neg P \land R) ⟺ (\neg P \lor Q \lor \neg R) \land (\neg P \lor Q \lor R) \land (P \lor \neg Q \lor R) \land (P \lor Q \lor R)

主析取范式为：

(P \land Q) \lor (\neg P \land R) ⟺ (P \land Q \land R) \lor (P \land Q \land \neg R) \lor (\neg P \land Q \land R) \lor (\neg P \land \neg Q \land R)

一个公式的主合取范式，亦可用基本等价式推出，其推演步骤为：

(1) 化归为合取范式。

(2) 除去合取范式中所有永为真的合取项。

(3) 合并相同的析取项和相同的变元。

$(P \lor \neg P)$ 式，然后，应用分配律展开公式。

例题12

$(P \land Q) \lor (\neg P \land R)$ 的主合取范式。

\begin{aligned} 解 (P \land Q) \lor (\neg P \land R) & ⟺ ((P \land Q) \lor \neg P) \land ((P \land Q) \lor R) \\ ⟺ (P \lor \neg P) \land (Q \land \neg P) \land (P \lor R) \land (Q \lor R) \\ ⟺ (Q \lor \neg P) \land (P \lor R) \land (Q \lor R) \\ ⟺ (Q \lor \neg P \lor (R \land \neg R)) \land (P \lor R \lor (Q \land \neg Q)) \land (Q \lor R \lor (P \land \neg P)) \\ ⟺ (Q \lor \neg P \lor R) \land (Q \lor P \lor \neg R) \land (P \lor R \lor Q) \land (P \lor R \lor \neg Q) \land (Q \lor R \lor P) \land (Q \lor R \lor \neg P) \\ ⟺ (\neg P \lor Q \lor R) \land (\neg P \lor Q \lor \neg R) \land (P \lor \neg Q \lor R) \land (P \lor Q \lor R) \end{aligned}

$\sum$ $\sum i, j, k$ $m_i \lor m_j \lor m_k$ $\prod$ $\prod i, j, k$ $M_i \land M_j \land M_k$ ，由这样的约定，例题11 可以表达为：

\begin{aligned} (P \land Q) \lor (\neg P \land R) & ⟺ m_{001} \lor m_{011} \lor m_{110} \lor m_{111} = \sum_{1, 3, 6, 7} \\ (P \land Q) \lor (\neg P \land R) & ⟺ M_{000} \land M_{010} \land M_{100} \land M_{101} = \prod_{0, 2, 4, 5} \end{aligned}

$P$ 的主析取范式为：

\sum i_{1}, i_{2}, \dots, i_{k}

$P$ 的主合取范式为：

\prod 0, 1, 2, \dots, i_{1} - 1, i_{1} + 1, \dots, i_{k} - 1, i_{k} + 1, \dots, 2^{n} - 1

$P$	$Q$	$P \land Q$	$P \land \neg Q$	$\neg P \land Q$	$\neg P \land \neg Q$
$T$	$T$	$T$	$F$	$F$	$F$
$T$	$F$	$F$	$T$	$F$	$F$
$F$	$T$	$F$	$F$	$T$	$F$
$F$	$F$	$F$	$F$	$F$	$T$

$P$	$Q$	$R$	$\neg P \land \neg Q \land \neg R$	$\neg P \land \neg Q \land R$	$\neg P \land Q \land \neg R$	$\neg P \land Q \land R$
$0$	$0$	$0$	$1$	$0$	$0$	$0$
$0$	$0$	$1$	$0$	$1$	$0$	$0$
$0$	$1$	$0$	$0$	$0$	$1$	$0$
$0$	$1$	$1$	$0$	$0$	$0$	$1$
$1$	$0$	$0$	$0$	$0$	$0$	$0$
$1$	$0$	$1$	$0$	$0$	$0$	$0$
$1$	$1$	$0$	$0$	$0$	$0$	$0$
$1$	$1$	$1$	$0$	$0$	$0$	$0$

$P$	$Q$	$R$	$P \land \neg Q \land \neg R$	$P \land \neg Q \land R$	$P \land Q \land \neg R$	$P \land Q \land R$
$0$	$0$	$0$	$0$	$0$	$0$	$0$
$0$	$0$	$1$	$0$	$0$	$0$	$0$
$0$	$1$	$0$	$0$	$0$	$0$	$0$
$0$	$1$	$1$	$0$	$0$	$0$	$0$
$1$	$0$	$0$	$1$	$0$	$0$	$0$
$1$	$0$	$1$	$0$	$1$	$0$	$0$
$1$	$1$	$0$	$0$	$0$	$1$	$0$
$1$	$1$	$1$	$0$	$0$	$0$	$1$

$P$	$Q$	$P \to Q$	$P \lor Q$	$\neg (P \land Q)$
$T$	$T$	$T$	$T$	$F$
$T$	$F$	$F$	$T$	$T$
$F$	$T$	$T$	$T$	$T$
$F$	$F$	$T$	$F$	$T$

$P$	$Q$	$R$	$A$
$T$	$T$	$T$	$T$
$T$	$T$	$F$	$F$
$T$	$F$	$T$	$F$
$T$	$F$	$F$	$T$
$F$	$T$	$T$	$F$
$F$	$T$	$F$	$F$
$F$	$F$	$T$	$F$
$F$	$F$	$F$	$T$

$P$	$Q$	$R$	$P \land Q$	$\neg P \land R$	$(P \land Q) \lor (\neg P \land R)$
$T$	$T$	$T$	$T$	$F$	$T$
$T$	$T$	$F$	$T$	$F$	$T$
$T$	$F$	$T$	$F$	$F$	$F$
$T$	$F$	$F$	$F$	$F$	$F$
$F$	$T$	$T$	$F$	$T$	$T$
$F$	$T$	$F$	$F$	$F$	$F$
$F$	$F$	$T$	$F$	$T$	$T$
$F$	$F$	$F$	$F$	$F$	$F$

$P$	$Q$	$P \land Q$	$P \land \neg Q$	$\neg P \land Q$	$\neg P \land \neg Q$
$T$	$T$	$T$	$F$	$F$	$F$
$T$	$F$	$F$	$T$	$F$	$F$
$F$	$T$	$F$	$F$	$T$	$F$
$F$	$F$	$F$	$F$	$F$	$T$

$P$	$Q$	$R$	$\neg P \land \neg Q \land \neg R$	$\neg P \land \neg Q \land R$	$\neg P \land Q \land \neg R$	$\neg P \land Q \land R$
$0$	$0$	$0$	$1$	$0$	$0$	$0$
$0$	$0$	$1$	$0$	$1$	$0$	$0$
$0$	$1$	$0$	$0$	$0$	$1$	$0$
$0$	$1$	$1$	$0$	$0$	$0$	$1$
$1$	$0$	$0$	$0$	$0$	$0$	$0$
$1$	$0$	$1$	$0$	$0$	$0$	$0$
$1$	$1$	$0$	$0$	$0$	$0$	$0$
$1$	$1$	$1$	$0$	$0$	$0$	$0$

$P$	$Q$	$R$	$P \land \neg Q \land \neg R$	$P \land \neg Q \land R$	$P \land Q \land \neg R$	$P \land Q \land R$
$0$	$0$	$0$	$0$	$0$	$0$	$0$
$0$	$0$	$1$	$0$	$0$	$0$	$0$
$0$	$1$	$0$	$0$	$0$	$0$	$0$
$0$	$1$	$1$	$0$	$0$	$0$	$0$
$1$	$0$	$0$	$1$	$0$	$0$	$0$
$1$	$0$	$1$	$0$	$1$	$0$	$0$
$1$	$1$	$0$	$0$	$0$	$1$	$0$
$1$	$1$	$1$	$0$	$0$	$0$	$1$

$P$	$Q$	$P \to Q$	$P \lor Q$	$\neg (P \land Q)$
$T$	$T$	$T$	$T$	$F$
$T$	$F$	$F$	$T$	$T$
$F$	$T$	$T$	$T$	$T$
$F$	$F$	$T$	$F$	$T$

$P$	$Q$	$R$	$A$
$T$	$T$	$T$	$T$
$T$	$T$	$F$	$F$
$T$	$F$	$T$	$F$
$T$	$F$	$F$	$T$
$F$	$T$	$T$	$F$
$F$	$T$	$F$	$F$
$F$	$F$	$T$	$F$
$F$	$F$	$F$	$T$

$P$	$Q$	$R$	$P \land Q$	$\neg P \land R$	$(P \land Q) \lor (\neg P \land R)$
$T$	$T$	$T$	$T$	$F$	$T$
$T$	$T$	$F$	$T$	$F$	$T$
$T$	$F$	$T$	$F$	$F$	$F$
$T$	$F$	$F$	$F$	$F$	$F$
$F$	$T$	$T$	$F$	$T$	$T$
$F$	$T$	$F$	$F$	$F$	$F$
$F$	$F$	$T$	$F$	$T$	$T$
$F$	$F$	$F$	$F$	$F$	$F$

$P$	$Q$	$P \land Q$	$P \land \neg Q$	$\neg P \land Q$	$\neg P \land \neg Q$
$T$	$T$	$T$	$F$	$F$	$F$
$T$	$F$	$F$	$T$	$F$	$F$
$F$	$T$	$F$	$F$	$T$	$F$
$F$	$F$	$F$	$F$	$F$	$T$

$P$	$Q$	$R$	$\neg P \land \neg Q \land \neg R$	$\neg P \land \neg Q \land R$	$\neg P \land Q \land \neg R$	$\neg P \land Q \land R$
$0$	$0$	$0$	$1$	$0$	$0$	$0$
$0$	$0$	$1$	$0$	$1$	$0$	$0$
$0$	$1$	$0$	$0$	$0$	$1$	$0$
$0$	$1$	$1$	$0$	$0$	$0$	$1$
$1$	$0$	$0$	$0$	$0$	$0$	$0$
$1$	$0$	$1$	$0$	$0$	$0$	$0$
$1$	$1$	$0$	$0$	$0$	$0$	$0$
$1$	$1$	$1$	$0$	$0$	$0$	$0$

$P$	$Q$	$R$	$P \land \neg Q \land \neg R$	$P \land \neg Q \land R$	$P \land Q \land \neg R$	$P \land Q \land R$
$0$	$0$	$0$	$0$	$0$	$0$	$0$
$0$	$0$	$1$	$0$	$0$	$0$	$0$
$0$	$1$	$0$	$0$	$0$	$0$	$0$
$0$	$1$	$1$	$0$	$0$	$0$	$0$
$1$	$0$	$0$	$1$	$0$	$0$	$0$
$1$	$0$	$1$	$0$	$1$	$0$	$0$
$1$	$1$	$0$	$0$	$0$	$1$	$0$
$1$	$1$	$1$	$0$	$0$	$0$	$1$

$P$	$Q$	$P \to Q$	$P \lor Q$	$\neg (P \land Q)$
$T$	$T$	$T$	$T$	$F$
$T$	$F$	$F$	$T$	$T$
$F$	$T$	$T$	$T$	$T$
$F$	$F$	$T$	$F$	$T$

$P$	$Q$	$R$	$A$
$T$	$T$	$T$	$T$
$T$	$T$	$F$	$F$
$T$	$F$	$T$	$F$
$T$	$F$	$F$	$T$
$F$	$T$	$T$	$F$
$F$	$T$	$F$	$F$
$F$	$F$	$T$	$F$
$F$	$F$	$F$	$T$

$P$	$Q$	$R$	$P \land Q$	$\neg P \land R$	$(P \land Q) \lor (\neg P \land R)$
$T$	$T$	$T$	$T$	$F$	$T$
$T$	$T$	$F$	$T$	$F$	$T$
$T$	$F$	$T$	$F$	$F$	$F$
$T$	$F$	$F$	$F$	$F$	$F$
$F$	$T$	$T$	$F$	$T$	$T$
$F$	$T$	$F$	$F$	$F$	$F$
$F$	$F$	$T$	$F$	$T$	$T$
$F$	$F$	$F$	$F$	$F$	$F$