数理逻辑基础

HW1

题目1

(1)

$P$	$Q$	$P\land Q$	$P\land Q\to Q$
0	0	0	1
0	1	0	1
1	0	0	1
1	1	1	1

该式为永假公式（矛盾式）.

(2)

$P$	$Q$	$R$	$P\lor Q$	$P\to(P\lor Q)$	$P\to R$	$(P\to(P\lor Q))\lor(P\to R)$
0	0	0	0	1	1	1
0	0	1	0	1	1	1
0	1	0	1	1	1	1
0	1	1	1	1	1	1
1	0	0	1	1	0	1
1	0	1	1	1	1	1
1	1	0	1	1	0	1
1	1	1	1	1	1	1

该式为永真公式（重言式）.

(3)

$P$	$Q$	$R$	$P\lor Q$	$P\land R$	$(P\lor Q)\to(P\land R)$
0	0	0	0	0	1
0	0	1	0	0	1
0	1	0	1	0	0
0	1	1	1	0	0
1	0	0	1	0	0
1	0	1	1	1	1
1	1	0	1	0	0
1	1	1	1	1	1

该式为可满足公式.

题目2

$P$	$Q$	$\lnot Q$	$A=P\to Q$	$B=P\land \lnot Q$	$\lnot A$	$\lnot B$	$A\lor B$
0	0	1	1	0	0	1	1
0	1	0	1	0	0	1	1
1	0	1	0	1	1	0	1
1	1	0	1	0	0	1	1

$A$ $B$ 适合德·摩根律

\neg (A \lor B) \Leftrightarrow \neg A \land \neg B .

题目3

(1)

\begin{aligned} P \to (Q \to R) & \Leftrightarrow \neg P \lor (Q \to R) & (蕴 涵 等 值 式) \\ \Leftrightarrow \neg P \lor (\neg Q \lor R) & (蕴 涵 等 值 式) \\ \Leftrightarrow (\neg P \lor \neg Q) \lor R & (\lor 的 结 合 律) \\ \Leftrightarrow \neg (\neg P \lor \neg Q) \to R & (蕴 涵 等 值 式) \\ \Leftrightarrow (P \land Q) \to R . & (德·摩根定律) \\ ◻ \end{aligned}

(2)

\begin{aligned} \neg P \land (\neg Q \land R) & \Leftrightarrow (\neg P \land \neg Q) \land R & (\land 的 结 合 律) \\ (1) & \Leftrightarrow \neg (P \lor Q) \land R, & (德 \cdot 摩 根 定 律) \end{aligned}

\begin{aligned} (Q \land R) \lor (P \land R) & \Leftrightarrow (Q \lor P) \land R & (\land 在 \lor 上 的 分 配 律) \\ (2) & \Leftrightarrow (P \lor Q) \land R . & (\lor 的 交 换 律) \end{aligned}

$(1)$ $(2)$ ，

\begin{aligned} (\neg P \land (\neg Q \land R)) \lor (Q \land R) \lor (P \land R) & \Leftrightarrow (\neg P \land (\neg Q \land R)) \lor ((Q \land R) \lor (P \land R)) & (\lor 的 结 合 律) \\ \Leftrightarrow (\neg (P \lor Q) \land R) \lor ((P \lor Q) \land R) & ((1) 、 (2) 式) \\ \Leftrightarrow (\neg (P \lor Q) \lor (P \lor Q)) \land R & (\land 在 \lor 上 的 分 配 律) \\ \Leftrightarrow T \land R & (排 中 律) \\ \Leftrightarrow R . & (幺 律) \\ ◻ \end{aligned}

HW2

题目1

(1)

\begin{aligned} P \to (Q \to R) & \Leftrightarrow \neg P \lor (Q \to R) & (蕴 涵 等 值 式) \\ \Leftrightarrow \neg P \lor (\neg Q \lor R) & (蕴 涵 等 值 式) \\ \Leftrightarrow (\neg P \lor \neg Q) \lor R & (\lor 的 结 合 律) \\ \Leftrightarrow \neg (P \land Q) \lor R & (德 \cdot 摩 根 定 律) \\ \Leftrightarrow \neg ((P \land Q) \land \neg R) . & (德 \cdot 摩 根 定 律) \\ ◻ \end{aligned}

(2)

\begin{aligned} \neg (P \to Q) \lor R & \Leftrightarrow \neg (\neg P \lor Q) \lor R & (蕴 涵 等 值 式) \\ \Leftrightarrow (P \land \neg Q) \lor R & (德 \cdot 摩 根 定 律) \\ \Leftrightarrow (P \lor R) \land (\neg Q \lor R) & (\lor 在 \land 上 的 分 配 律) \\ \Leftrightarrow \neg (\neg ((P \lor R) \land (\neg Q \lor R))) & (双 重 否 定 律) \\ \Leftrightarrow \neg (\neg (P \lor R) \lor \neg (\neg Q \lor R)) & (德 \cdot 摩 根 定 律) \\ \Leftrightarrow \neg ((\neg P \land \neg R) \land (Q \land \neg R)) . & (德 \cdot 摩 根 定 律) \\ ◻ \end{aligned}

(3)

\begin{aligned} P \leftrightarrow Q & \Leftrightarrow (P \to Q) \land (Q \to P) & (等 价 等 值 式) \\ \Leftrightarrow (\neg P \lor Q) \land (\neg Q \lor P) & (蕴 涵 等 值 式) \\ \Leftrightarrow ((\neg P \lor Q) \land \neg Q) \lor ((\neg P \lor Q) \land P) & (\land 在 \lor 上 的 分 配 律) \\ \Leftrightarrow ((\neg P \land \neg Q) \lor (Q \land \neg Q)) \lor ((\neg P \land P) \lor (Q \land P)) & (\land 在 \lor 上 的 分 配 律) \\ \Leftrightarrow ((\neg P \land \neg Q) \lor F) \lor (F \lor (Q \land P)) & (矛 盾 律) \\ \Leftrightarrow (\neg P \land \neg Q) \lor (Q \land P) & (幺 律) \\ \Leftrightarrow (\neg P \land \neg Q) \lor (P \land Q) & (\land 的 交 换 律) \\ \Leftrightarrow \neg (\neg ((\neg P \land \neg Q) \lor (P \land Q))) & (双 重 否 定 律) \\ \Leftrightarrow \neg (\neg (\neg P \land \neg Q) \land \neg (P \land Q)) . & (德 \cdot 摩 根 定 律) \\ ◻ \end{aligned}

题目2

(1)

\begin{aligned} P \to (Q \to R) & \Leftrightarrow \neg (P \land Q) \lor R & (1 中 结 果) \\ \Leftrightarrow (\neg P \lor \neg Q) \lor R . & (德 \cdot 摩 根 定 律) \\ ◻ \end{aligned}

(2)

\begin{aligned} \neg (P \to Q) \lor R & \Leftrightarrow \neg (\neg (P \lor R) \lor \neg (\neg Q \lor R)) . & (1 中 结 果) \\ ◻ \end{aligned}

(3)

\begin{aligned} P \land Q & \Leftrightarrow \neg (\neg (P \land Q)) & (双 重 否 定 律) \\ (A) & \Leftrightarrow \neg (\neg P \lor \neg Q) . & (德 \cdot 摩 根 定 律) \end{aligned}

\begin{aligned} \neg P \land \neg Q & \Leftrightarrow \neg (\neg (\neg P) \lor \neg (\neg Q)) & (式 A) \\ (B) & \Leftrightarrow \neg (P \lor Q) . & (双 重 否 定 律) \end{aligned}

从而，

\begin{aligned} P \leftrightarrow Q & \Leftrightarrow (\neg P \land \neg Q) \lor (P \land Q) & (1 中 结 果) \\ \Leftrightarrow \neg (P \lor Q) \lor \neg (\neg P \lor \neg Q) . & (式 A 、 B) \\ ◻ \end{aligned}

题目3

(1)

\begin{aligned} (\neg P \to Q) \to (\neg Q \lor P) & \Leftrightarrow \neg (\neg P \to Q) \lor (\neg Q \lor P) & (蕴 涵 等 值 式) \\ \Leftrightarrow \neg (\neg \neg P \lor Q) \lor (\neg Q \lor P) & (蕴 涵 等 值 式) \\ \Leftrightarrow \neg (P \lor Q) \lor (\neg Q \lor P) & (双 重 否 定 式) \\ \Leftrightarrow (\neg P \land \neg Q) \lor (\neg Q \lor P) & (德 \cdot 摩 根 定 律) \\ \Leftrightarrow ((\neg P \land \neg Q) \lor \neg Q) \lor P & (\lor 的 结 合 律) \\ \Leftrightarrow \neg Q \lor P & (吸 收 律) \\ (1) & \Leftrightarrow P \lor \neg Q, & (\lor 的 交 换 律) \end{aligned}

$P\lor\lnot Q$ . 同时它也是合取范式.

(2)

\begin{aligned} \neg (\neg P \lor Q) \land Q & \Leftrightarrow P \land \neg Q \land Q & (德 \cdot 摩 根 定 律 、 双 重 否 定 式) \\ \Leftrightarrow P \land Q \land \neg Q, & (\land 的 交 换 律) \end{aligned}

$P\land Q\land\lnot Q$ ，同时它也是析取范式.

(3)

\begin{matrix} \begin{aligned} (P \lor (Q \land R)) \to (P \lor Q \lor R) & \Leftrightarrow \neg (P \lor (Q \land R)) \lor (P \lor Q \lor R) & (蕴 涵 等 值 式) \\ \Leftrightarrow (\neg P \land \neg (Q \land R)) \lor P \lor Q \lor R & (德 \cdot 摩 根 定 律 、 \lor 的 结 合 律) \\ \Leftrightarrow (\neg P \land (\neg Q \lor \neg R)) \lor P \lor Q \lor R & (德 \cdot 摩 根 定 律) \\ \Leftrightarrow (\neg P \land \neg Q) \lor (\neg P \land \neg R) \lor P \lor Q \lor R & (\land 在 \lor 上 的 分 配 律) \\ \Leftrightarrow (\neg P \land \neg Q) \lor (\neg P \land \neg R) \lor P \lor ((P \lor \neg P) \land Q) \lor ((P \lor \neg P) \land R) & (幺 律 、 排 中 律) \\ \Leftrightarrow (\neg P \land \neg Q) \lor (\neg P \land \neg R) \lor P \lor (P \land Q) \lor (\neg P \land Q) \lor (P \land R) \lor (\neg P \land R) & (\land 在 \lor 上 的 分 配 律) \\ \Leftrightarrow (\neg P \land (\neg Q \lor Q)) \lor (\neg P \land (\neg Q \lor Q)) \lor (P \lor (P \land Q) \lor (P \land R)) & (\land 在 \lor 上 的 分 配 律 、 \lor 的 交 换 律 与 结 合 律) \\ \Leftrightarrow (\neg P \land T) \lor (\neg P \land T) \lor P & (排 中 律 、 吸 收 律) \\ \Leftrightarrow \neg P \lor P, & (幺 律 、 \lor 的 幂 等 律) \end{aligned} \end{matrix}

$(\lnot P\land\lnot Q)\lor(\lnot P\land \lnot R)\lor P\lor Q\lor R$ $\lnot P\lor P$ ，

$\lnot P\lor P$ .

HW3

题目1

(1)

$P$	$Q$	$R$	$P\lor Q$	$(P\lor Q)\land R$
0	0	0	0	0
0	0	1	0	0
0	1	0	1	0
0	1	1	1	1
1	0	0	1	0
1	0	1	1	1
1	1	0	1	0
1	1	1	1	1

主析取范式为

m_{3} \lor m_{5} \lor m_{7} = (\neg P \land Q \land R) \lor (P \land \neg Q \land R) \lor (P \land Q \land R),

主合取范式为

M_{0} \land M_{1} \land M_{2} \land M_{4} \land M_{6} = (P \lor Q \lor R) \land (P \lor Q \lor \neg R) \land (P \lor \neg Q \lor R) \land (\neg P \lor Q \lor R) \land (\neg P \lor \neg Q \lor R) .

(2)

$P$	$Q$	$R$	$P\lor Q\lor R$	$P\to(P\lor Q\lor R)$
0	0	0	0	1
0	0	1	1	1
0	1	0	1	1
0	1	1	1	1
1	0	0	1	1
1	0	1	1	1
1	1	0	1	1
1	1	1	1	1

主析取范式为

\begin{aligned} ⋁_{i = 0}^{7} m_{i} = & (\neg P \land \neg Q \land \neg R) \lor (\neg P \land \neg Q \land R) \lor (\neg P \land Q \land \neg R) \lor (\neg P \land Q \land R) \\ \lor & (P \land \neg Q \land \neg R) \lor (P \land \neg Q \land R) \lor (P \land Q \land \neg R) \lor (P \land Q \land R), \end{aligned}

$\varnothing$ .

(3)

$P$	$Q$	$\lnot P$	$Q\to\lnot P$	$\lnot(Q\to\lnot P)$
0	0	1	1	0
0	1	1	1	0
1	0	0	1	0
1	1	0	0	1

$\varnothing$ ，主合取范式为

⋀_{i = 0}^{3} M_{i} = (P \lor Q) \land (P \lor \neg Q) \land (\neg P \lor Q) \land (\neg P \lor \neg Q) .

题目2

主析取范式为

m_{0} \lor m_{2} \lor m_{7} = (\neg P \land \neg Q \land \neg R) \lor (\neg P \land Q \land \neg R) \lor (P \land Q \land R),

主合取范式为

M_{1} \land M_{3} \land M_{4} \land M_{5} \land M_{6} = (P \lor Q \lor \neg R) \land (P \lor \neg Q \lor \neg R) \land (\neg P \lor Q \lor R) \land (\neg P \lor Q \lor \neg R) \land (\neg P \lor \neg Q \lor R) .

题目3

主合取范式为

M_{2} \land M_{3} \land M_{7} = (\neg P \lor Q \lor \neg R) \land (\neg P \lor Q \lor R) \land (P \lor Q \lor R),

主析取范式为

m_{0} \lor m_{1} \lor m_{4} \lor m_{5} \lor m_{6} = (P \land Q \land R) \lor (P \land Q \land \neg R) \lor (\neg P \land Q \land R) \lor (\neg P \land Q \land \neg R) \lor (\neg P \land \neg Q \land R) .

HW4

题目1

(1)

\begin{aligned} P \land Q & \Leftrightarrow (P \land Q) \land T & (幺 律) \\ \Leftrightarrow (P \land Q) \land (R \lor \neg R) & (排 中 律) \\ \Leftrightarrow (P \land Q \land R) \lor (P \land Q \land \neg R) & (分 配 律) \\ \Leftrightarrow m_{6} \lor m_{7}, \end{aligned}

\begin{aligned} R & \Leftrightarrow T \land R & (幺 律) \\ \Leftrightarrow (Q \lor \neg Q) \land R & (排 中 律) \\ \Leftrightarrow (Q \land R) \lor (\neg Q \land R) & (分 配 律) \\ \Leftrightarrow T \land ((Q \land R) \lor (\neg Q \land R)) & (幺 律) \\ \Leftrightarrow (P \lor \neg P) \land ((Q \land R) \lor (\neg Q \land R)) & (排 中 律) \\ \Leftrightarrow (P \land ((Q \land R) \lor (\neg Q \land R))) \lor (\neg P \land ((Q \land R) \lor (\neg Q \land R))) & (分 配 律) \\ \Leftrightarrow (P \land Q \land R) \lor (P \land \neg Q \land R) \lor (\neg P \land Q \land R) \lor (\neg P \land \neg Q \land R) & (分 配 律) \\ \Leftrightarrow m_{1} \lor m_{3} \lor m_{5} \lor m_{7}, \end{aligned}

\begin{aligned} (P \land Q) \lor R & \Leftrightarrow m_{1} \lor m_{3} \lor m_{5} \lor m_{6} \lor m_{7} & (替 换 定 理 、 \lor 的 幂 等 律) \\ \Leftrightarrow (\neg P \land \neg Q \land R) \lor (\neg P \land Q \land R) \lor (P \land \neg Q \land R) \lor (P \land Q \land \neg R) \lor (P \land Q \land R) \\ \Leftrightarrow M_{0} \land M_{2} \land M_{4} \\ \Leftrightarrow (P \lor Q \lor R) \land (P \lor \neg Q \lor R) \land (\neg P \land Q \land R) . \end{aligned}

(2)

\begin{aligned} (P \to Q) \land (Q \to R) & \Leftrightarrow (\neg P \lor Q) \land (\neg Q \lor R) & (蕴 涵 等 值 式) \\ \Leftrightarrow (\neg P \land \neg Q) \lor (\neg P \land R) \lor (Q \land \neg Q) \lor (Q \land R) & (分 配 律) \\ \Leftrightarrow (\neg P \land \neg Q) \lor (\neg P \land R) \lor F \lor (Q \land R) & (矛 盾 律) \\ \Leftrightarrow (\neg P \land \neg Q) \lor (\neg P \land R) \lor (Q \land R) & (幺 律) \\ \Leftrightarrow (\neg P \land \neg Q \land T) \lor (\neg P \land R \land T) \lor (Q \land R \land T) & (幺 律) \\ \Leftrightarrow ((\neg P \land \neg 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)) & (排 中 律) \\ \Leftrightarrow (\neg P \land \neg Q \land R) \lor (\neg P \land \neg Q \land \neg R) \lor (\neg P \land Q \land R) \\ \lor (\neg P \land \neg Q \land R) \lor (P \land Q \land R) \lor (\neg P \land Q \land R) & (分 配 律) \\ \Leftrightarrow m_{0} \lor m_{1} \lor m_{3} \lor m_{7} & (\lor 的 幂 等 律) \\ \Leftrightarrow (\neg P \land \neg Q \land \neg R) \lor (\neg P \land \neg Q \land R) \lor (\neg P \land Q \land R) \lor (P \land Q \land R) \\ \Leftrightarrow M_{2} \land M_{4} \land M_{5} \land M_{6} \\ \Leftrightarrow (P \lor \neg Q \lor R) \land (\neg P \lor Q \lor R) \land (\neg P \lor Q \lor \neg R) \land (\neg P \lor \neg Q \lor R) . \end{aligned}

题目2

\begin{aligned} (P \to Q) \land (P \to R) & \Leftrightarrow (\neg P \lor Q) \land (\neg P \lor R) & (蕴 涵 等 值 式) \\ \Leftrightarrow (\neg P \land \neg P) \lor (\neg P \land R) \lor (\neg P \land Q) \lor (Q \land R) & (分 配 律 、 交 换 律) \\ \Leftrightarrow (\neg P) \lor (\neg P \land R) \lor (\neg P \land Q) \lor (Q \land R) & (\land 的 幂 等 律) \\ \Leftrightarrow (\neg P) \lor (\neg P \land Q) \lor (Q \land R) & (吸 收 律) \\ (1) & \Leftrightarrow (\neg P) \lor (Q \land R) & (吸 收 律) \\ \Leftrightarrow (\neg P) \lor (T \land (Q \land R)) & (幺 律) \\ \Leftrightarrow (\neg P) \lor ((\neg P \lor P) \land (Q \land R)) & (排 中 律) \\ \Leftrightarrow (\neg P) \lor (\neg P \land Q \land R) \lor (P \land Q \land R) & (分 配 律) \\ \Leftrightarrow (\neg P) \lor (P \land Q \land R) & (吸 收 律) \\ \Leftrightarrow (\neg P \land (Q \lor \neg Q) \land (R \lor \neg R)) \lor (P \land Q \land R) & (幺 律 、 排 中 律) \\ \Leftrightarrow (\neg P \land \neg Q \land \neg R) \lor (\neg P \land \neg Q \land R) \lor (\neg P \land Q \land \neg R) \\ \lor (\neg P \land Q \land R) \lor (P \land Q \land R) & (分 配 律) \\ (2) & \Leftrightarrow m_{0} \lor m_{1} \lor m_{2} \lor m_{3} \lor m_{7} \\ \Leftrightarrow M_{4} \land M_{5} \land M_{6} \\ \Leftrightarrow (\neg P \lor Q \lor R) \land (\neg P \lor Q \lor \neg R) \land (\neg P \lor \neg Q \lor R) . \end{aligned}

\begin{aligned} P \to (Q \land R) & \Leftrightarrow \neg P \lor (Q \land R) & (蕴 涵 等 值 式) \\ \Leftrightarrow m_{0} \lor m_{1} \lor m_{2} \lor m_{3} \lor m_{7} & ((1) \to (2)) \\ \Leftrightarrow M_{4} \land M_{5} \land M_{6} \\ \Leftrightarrow (\neg P \lor Q \lor R) \land (\neg P \lor Q \lor \neg R) \land (\neg P \lor \neg Q \lor R) . \end{aligned}

题目3

$G\lrArr G_1\land G_2\land G_3$ $G_1\lrArr A\to C$ $G_2\lrArr B\to\lnot C$ $G_3\lrArr \lnot C\to(A\lor B)$ .

\begin{aligned} G_{1} & \Leftrightarrow A \to C \\ \Leftrightarrow \neg A \lor C, & (蕴 涵 等 值 式) \end{aligned}

\begin{aligned} G_{2} & \Leftrightarrow B \to \neg C \\ \Leftrightarrow \neg B \lor \neg C, & (蕴 涵 等 值 式) \end{aligned}

\begin{aligned} G_{3} & \Leftrightarrow \neg C \to (A \lor B) \\ \Leftrightarrow \neg (\neg C) \lor (A \lor B) & (蕴 涵 等 值 式) \\ \Leftrightarrow A \lor B \lor C, & (双 重 否 定 律 、 交 换 律) \end{aligned}

从而

\begin{aligned} G & \Leftrightarrow G_{1} \land G_{2} \land G_{3} \\ \Leftrightarrow (\neg A \lor C) \land (\neg B \lor \neg C) \land (A \lor B \lor C) & (替 换 定 理) \\ \Leftrightarrow ((\neg A \land \neg B) \lor (\neg A \land \neg C) \lor (\neg B \land C) \lor (C \land \neg C)) \land (A \lor B \lor C) & (分 配 律 、 交 换 律) \\ \Leftrightarrow ((\neg A \land \neg B) \lor (\neg A \land \neg C) \lor (\neg B \land C) \lor F) \land (A \lor B \lor C) & (矛 盾 律) \\ \Leftrightarrow ((\neg A \land \neg B) \lor (\neg A \land \neg C) \lor (\neg B \land C)) \land (A \lor B \lor C) & (幺 律) \\ \Leftrightarrow (A \land \neg A \land \neg B) \lor (A \land \neg A \land \neg C) \lor (A \land \neg B \land C) \\ \lor (\neg A \land B \land \neg B) \lor (\neg A \land B \land \neg C) \lor (B \land \neg B \land C) \\ \lor (\neg A \land \neg B \land C) \lor (\neg A \land C \land \neg C) \lor (\neg B \land C \land C) & (分 配 律) \\ \Leftrightarrow (F \land \neg B) \lor (F \land \neg C) \lor (A \land \neg B \land C) \\ \lor (\neg A \land F) \lor (\neg A \land B \land \neg C) \lor (F \land C) \\ \lor (\neg A \land \neg B \land C) \lor (\neg A \land F) \lor (\neg B \land C) & (矛 盾 律 、 \land 的 幂 等 律) \\ \Leftrightarrow F \lor F \lor (A \land \neg B \land C) \lor F \lor (\neg A \land B \land \neg C) \lor F \lor (\neg A \land \neg B \land C) \lor F \lor (\neg B \land C) & (零 律) \\ \Leftrightarrow (A \land \neg B \land \end{aligned}