离散数学证明题记录（2）

PS2 Problem 1

断言：令 \(p, q \in \mathbb{Z}\) 且互质，设 \(r\) 为 \(q\) 的因数，
          则有 \(\{ x \in \mathbb{Z} : p \mid x \} \cap \{ x \in \mathbb{Z} : q \mid x \} \subseteq \{ x \in \mathbb{Z} : (r \cdot p) \mid x \}\)

名词解释：

• 互质：若两个整数 \(a, b\) 的公约数只有 \(1\)，则称 \(a, b\) 为互质。

代入验证

\(p\)	\(q\)	\(r\)	\(r \mid q\) ?	\(r \mid p\) ?	\(r\) 质数?	\(pr\)	\(x\)	\(p \mid x\) ?	\(q \mid x\) ?	\((p \cdot r) \mid x\) ?
\(2\)	\(9\)	\(3\)	\(T\)	\(F\)	\(T\)	\(6\)	\(18\)	\(T\)	\(T\)	\(T\)
\(3\)	\(10\)	\(2\)	\(T\)	\(F\)	\(T\)	\(6\)	\(30\)	\(T\)	\(T\)	\(T\)
\(16\)	\(15\)	\(5\)	\(T\)	\(F\)	\(T\)	\(80\)	\(160\)	\(T\)	\(T\)	\(T\)

证明

令 \(A = \{ x \in \mathbb{Z} : p \mid x \}, \ B = \{ x \in \mathbb{Z} : q \mid x \}, \ C = \{ x \in \mathbb{Z} : (r \cdot p) \mid x \}\)，

由于证明 \(A \subseteq B\) 可以视为证明，对于任意元素\(a\)，如果 \(a \in A\)，则 \(a \in B\)，

我们可以将原命题转换为：如果 \(x \in A \cap B\)，则\(x \in C\)。

\[ \begin{aligned} & x \in A \cap B && 蕴含命题前提 \\ \Rightarrow \ & x \in A \land x \in B && 根据并集的定义 \\ \Rightarrow \ & p \mid x \land q \mid x && 根据集合A, B的定义 \\ \Rightarrow \ & x = p \cdot m \land x = q \cdot n, && 根据整除的定义 \\ & m, n \in \mathbb{Z} && 即(a \mid b) \Rightarrow (b = a \cdot k), \ k \in \mathbb{Z} \\ \Rightarrow \ & p \cdot m = q \cdot n \\ \Rightarrow \ & p \mid (q \cdot n) && 根据整除的定义 \\ \Rightarrow \ & p \mid n && 由于 p, q 互质，p 不整除 q \\ \Rightarrow \ & n = p \cdot k, && 根据整除的定义\\ & k \in \mathbb{Z} \\ \Rightarrow \ & x = q \cdot (p \cdot k) && 代换x = q \cdot n中的n为p \cdot k \\ \Rightarrow \ & x = (r \cdot l) \cdot (p \cdot k), && 因为r为q的因数 \\ & l \in \mathbb{Z} \\ \Rightarrow \ & x = (r \cdot p) \cdot (l \cdot k) && 根据乘法结合律 \\ \Rightarrow \ & x = (r \cdot p) \cdot s, && 因为整数的积为整数 \\ & s \in \mathbb{Z} && 且l, k \in \mathbb{Z} \\ \Rightarrow \ & (r \cdot p) \mid x && 根据整除的定义 \\ \Rightarrow \ & x \in C && 根据集合C的定义 \end{aligned} \]

PS2 Problem 2

断言1

断言：对于任意集合 \(A, B\) 使得 \(A \subseteq B\)，则有 \(\overline{(A-B) \cup (B - A)} \subseteq \overline{B} - \overline{A}\)

概念解释：

• 对于任意集合\(A, B\)，\(A - B = A \setminus B := \{ x : x \in A \land x \notin B\}\) 或者 \(A \cap \overline{B}\)，

  即所有 \(A\) 中不同时属于 \(B\) 的元素（从 \(A\) 集合中减去同时在 \(B\) 集合中的元素）

反例反证：\(U = \{1, 2, 3, 4\}, \ A = \{1, 2\}, \ B = \{1, 2, 3\}\)

代入验证：

\(A\)	\(B\)	\(A \subseteq B\)	\(A-B\)	\(B-A\)	\(\overline{(A-B)\cup(B-A)}\)	\(\overline{B}\)	\(\overline{A}\)	\(\overline{B}-\overline{A}\)
\(\{1, 2\}\)	\(\{1, 2, 3\}\)	\(T\)	\(\emptyset\)	\(\{3\}\)	\(\overline{\emptyset \cup \{3\}} = \overline{\{3\}} = \{1, 2, 4\}\)	\(\{4\}\)	\(\{3, 4\}\)	\(\emptyset\)

因为 \(\{ 1, 2, 4 \} \not\subseteq \emptyset\)，反例证明原命题不为真

断言2

更改断言：对于任意集合 \(A, B\) 使得 \(A \subseteq B\)，则有 \(\overline{(A-B) \cup (B - A)} = \overline{B} \cup (A \cap B)\)

证明

要证明两个集合相等，我们可以分别证明两个集合都是互相的子集，即，证明以下两个情况：

• \(\overline{(A-B) \cup (B - A)} \subseteq \overline{B} \cup (A \cap B)\)

• \(\overline{B} \cup (A \cap B) \subseteq \overline{(A-B) \cup (B - A)}\)

---

为了证明 \(\overline{(A-B) \cup (B - A)} \subseteq \overline{B} \cup (A \cap B)\)，我们可以将命题等价转化为：

如果 \(x \in \overline{(A-B)\cup(B-A)}\)，则 \(x \in \overline{B} \cup (A \cap B)\)

\[ \begin{aligned} 假设 \ & x \in \overline{(A-B)\cup(B-A)} \\ \Rightarrow \ & x \in \overline{(A - B)} \cap \overline{(B-A)} && 根据德摩根定律 \\ & && 即 \overline{A \cup B} = \overline{A} \cap \overline{B} \\ \Rightarrow \ & x \in \overline{(A \cap \overline{B})} \cap \overline{(B \cap \overline{A})} && 根据集合减法的定义 \\ \Rightarrow \ & x \in (\overline{A} \cup \overline{\overline{B}}) \cap (\overline{B} \cup \overline{\overline{A}}) && 根据德摩根定律 \\ & && 即 \overline{A \cap B} = \overline{A} \cup \overline{B} \\ \Rightarrow \ & x \in (\overline{A} \cup B) \cap (A \cup \overline{B}) && 一个集合补集的补集等于集合本身 \\ \Rightarrow \ & x \in (\overline{A} \cap A) \cup (\overline{A} \cap \overline{B}) \cup (B \cap A) \cup (B \cap \overline{B}) && 根据交集运算的分配律 \\ \Rightarrow \ & x \in \emptyset \cup (\overline{A} \cap \overline{B}) \cup (B \cap A) \cup \emptyset && 因为 \overline{A} \cap A = \emptyset = B \cap \overline{B} \\ \Rightarrow \ & x \in (\overline{A} \cap \overline{B}) \cup (A \cap B) && 因为对于任意集合Z \\ & && 有Z \cup \emptyset = Z \\ \Rightarrow \ & x \in (\overline{A} \cap \overline{B}) \cup (A \cap B), && 对于任意集合Y,Z \\ & (\overline{A} \cap \overline{B}) \subseteq \overline{B} && 有(Y \cap Z) \subseteq Z \\ \Rightarrow \ & x \in \overline{B} \cup (A \cap B), && 由于(\overline{A} \cap \overline{B}) \subseteq \overline{B}, \\ & && 则x \in \overline{A} \cap \overline{B} \Rightarrow x \in \overline{B} \\ & && 代换\overline{A} \cap \overline{B}为\overline{B} \end{aligned} \]

---

为了证明\(\overline{B} \cup (A \cap B) \subseteq \overline{(A-B) \cup (B - A)}\)，我们可以将命题等价转换为：

如果\(x \in \overline{B} \cup (A \cap B)\)，则\(x \in \overline{(A-B) \cup (B - A)}\)

\[ \begin{aligned} 假设 \ & x \in \overline{B} \cup (A \cap B) \\ \Rightarrow \ & x \in \overline{B} \cup A && 因为A \subseteq B，\\ & && 则 A \cap B = A \\ \Rightarrow \ & x \in \overline{B} \cup \overline{\overline{A}} && 因为集合补集的补集为其自身 \\ \Rightarrow \ & x \in \overline{B \cap \overline{A}} && 根据德摩根定律 \\ \Rightarrow \ & x \in \overline{(B - A)} && 根据集合减法的定义 \\ \Rightarrow \ & x \in \overline{(A - B) \cup (B - A)} && A \subseteq B \Rightarrow A - B = \emptyset \\ & && 且任意集合Z \cup \emptyset = Z \end{aligned} \]

PS2 Problem 3

断言：对于任意集合 \(A, B\)，有 \(\mathcal{P}(A) \cap \mathcal{P}(B) = \mathcal{P}(A \cap B)\)

名词解释：

• 幂集：\(\mathcal{P}(A) = \{X : X \subseteq A\}\)，即幂集 \(\mathcal{P}(A)\) 中的元素都为集合 \(A\) 的子集

证明

要证明两个集合相等，我们可以分别证明两个集合都是互相的子集，即，证明以下两个情况：

• \(\mathcal{P}(A) \cap \mathcal{P}(B) \subseteq \mathcal{P}(A \cap B)\)

• \(\mathcal{P}(A \cap B) \subseteq \mathcal{P}(A) \cap \mathcal{P}(B)\)

---

为了证明 \(\mathcal{P}(A) \cap \mathcal{P}(B) \subseteq \mathcal{P}(A \cap B)\)，我们可以将命题等价转化为：

如果 \(Z \in \mathcal{P}(A) \cap \mathcal{P}(B)\)，则 \(Z \in \mathcal{P}(A \cap B)\)

\[ \begin{aligned} 假设 \ & Z \in \mathcal{P}(A) \cap \mathcal{P}(B) \\ \Rightarrow \ & Z \in \mathcal{P}(A) \land Z \in \mathcal{P}(B) && 根据交集的定义 \\ \Rightarrow \ & Z \subseteq A \land Z \subseteq B && 根据幂集\mathcal{P}(A), \mathcal{P}(B)的定义 \\ \Rightarrow \ & (z \in Z) \Rightarrow (z \in A) \ \land && 根据子集的定义 \\ & (z \in Z) \Rightarrow (z \in B) \\ \Rightarrow \ & (z \in Z) \Rightarrow (z \in A \land z \in B) && 等价 \\ \Rightarrow \ & z \in Z \Rightarrow z \in (A \cap B) && 根据交集的定义 \\ \Rightarrow \ & Z \subseteq A \cap B && 根据子集的定义 \\ \Rightarrow \ & Z \in \mathcal{P}(A \cap B) && 根据幂集\mathcal{P}(A \cap B)的定义 \end{aligned} \]

---

为了证明 \(\mathcal{P}(A \cap B) \subseteq \mathcal{P}(A) \cap \mathcal{P}(B)\)，我们可以将命题等价转化为：

如果 \(Z \in \mathcal{P}(A \cap B)\)，则 \(Z \in \mathcal{P}(A) \cap \mathcal{P}(B)\)

\[ \begin{aligned} 假设 \ & Z \in \mathcal{P}(A \cap B) \\ \Rightarrow \ & Z \subseteq A \cap B && 根据幂集\mathcal{P}(A \cap B)的定义 \\ \Rightarrow \ & z \in Z \Rightarrow z \in (A \cap B) && 根据子集的定义 \\ \Rightarrow \ & (z \in Z) \Rightarrow (z \in A \land z \in B) && 根据交集的定义 \\ \Rightarrow \ & (z \in Z) \Rightarrow (z \in A) \ \land && 与上条等价 \\ & (z \in Z) \Rightarrow (z \in B) \\ \Rightarrow \ & Z \subseteq A \land Z \subseteq B && 根据子集的定义 \\ \Rightarrow \ & Z \in \mathcal{P}(A) \land Z \in \mathcal{P}(B) && 根据幂集\mathcal{P}(A), \mathcal{P}(B)的定义 \\ \Rightarrow \ & Z \in \mathcal{P}(A) \cap \mathcal{P}(B) && 根据交集的定义 \end{aligned} \]