行政、Ed、学术诚信、命题逻辑、蕴含、量词、集合运算

题目要求学生自行陈述协作情况，官方解答中未提供标准答案，由学生根据实际情况作答。

(a) 课程网站位于 https://www.eecs70.org/ 。

(b)

• (i) 含作业（With HW）：讨论课出勤 5%，维生素 5%，作业 20%，期中考试 25%，期末考试 45%。不含作业（Without HW）：讨论课出勤 6.25%，维生素 6.25%，期中考试 31.25%，期末考试 56.25%。

• (ii) 每次讨论课你可以获得 1 个出勤积分；至少需要 13 个积分才能获得讨论课出勤的满分。你可以参加其他讨论课，但只有你实际被分配的 section 的出勤才会被计入。

• (iii) 当周的作业于周日在 Gradescope 上发布；作业于下周六下午 4:00 截止（宽截止到下午 6:00）；该次作业的解答于周日发布。

• (iv) 你可以在课程离散数学部分去掉最低的 2 次作业成绩，在概率论部分也可以去掉最低的 2 次作业成绩；维生素作业执行相同的政策。不过请把这些“去掉”机会留给紧急情况。

• (v) 期中考试在 2023 年 3 月 8 日晚上 7–9 点；期末考试在 2023 年 5 月 11 日下午 3–6 点。

(a) 是（Yes），违反了课程政策。所有解答必须完全由提交作业的学生本人撰写。即使学生之间进行了合作，每名学生也必须撰写一份独一无二的个人解答。在本情形中，Alice 和 Bob 都负有责任。

(b) 否（No），不违反课程政策。虽然分享书面解答是不被允许的，但分享对问题的思路是被允许且受到鼓励的。由于 Carol 只记下了笔记而非抄录 Dan 的解答，并且恰当地致谢了 Dan，这属于被积极鼓励的合作形式。

(c) 否（No），不违反课程政策。利用外部资源协助完成作业——虽然不如与同学合作那样受到鼓励——只要满足以下条件即可：(i) 学生确保自己理解了解答；(ii) 学生基于理解重新撰写一份新解答，而不是照抄外部来源；(iii) 学生标注引用了外部来源。不过需要注意：在网上查找作业解答违反课程政策；正确做法是一看到作业解答就关闭该标签页。

(d) 是（Yes），违反了课程政策，Frank 和 Grace 都负有责任。尽管 Frank 致谢了 Grace，但书面解答从一开始就不应该被分享，当然更不应该被抄录。这是为了确保每名学生都能学会如何写出清晰且有说服力的论证。为安全起见，请尽量避免让任何人在课程期间的任何时候看到你的书面解答——请将合作限制在思路交流与口头沟通之内。

(e) 是（Yes），违反了课程政策。同样，致谢或引用并不能弥补“书面解答永远不该被分享”这一事实，无论以书面形式还是打字形式。在本情形中，Heidi 和 Irene 都负有责任。

(f) 是（Yes），违反了课程政策。Joe 不应该在官方发布之前阅读解答。当 Joe 卡住时，他应当通过 Ed 或 Office Hours 寻求帮助。

(a) 该提问有两点不妥。首先，它没有通过 5 分钟测试：这个概念需要超过 5 分钟才能解释清楚，因此更适合在 Office Hours 进行。其次，它没有聚焦于学生具体感到困惑的那个概念。Ed 上的提问应当范围窄，并包含导致该问题的所有推理步骤。一个更好的提问示例是：“我理解了 Note 2 中定理 XYZ 证明的每一步，除了最后一步。我尝试这样推理，但没看出它是如何得到结果的。请问我哪里出错了？”

(b) 每周帖子于每周日发布。它们属于必读内容。

(c) 请发送电子邮件至 sp23@eecs70.org 。

题目要求学生亲笔（或打印）并签署上述学术诚信誓词。官方解答不提供额外内容，由学生自行完成签署。

(a) 令 \(p(x)=x^2\)。该句可理解为：“存在一个方程 \(p(x)=0\) 的解 \(x\)，且任意另一个解 \(y\) 都等于 \(x\)”。即 \[(\exists x \in \mathbb{R})\big((p(x)=0) \land ((\forall y \in \mathbb{R})(p(y)=0) \implies (x=y))\big).\]

(b) 该句可理解为：“如果 \(x\) 和 \(y\) 是不同的有理数，则存在一个有理数 \(z\) 介于 \(x\) 与 \(y\) 之间”。即 \[(\forall x,y \in \mathbb{Q})\big((x \neq y) \implies ((\exists z \in \mathbb{Q})(x<z<y \lor y<z<x))\big).\] 等价地， \[(\forall x,y \in \mathbb{Q})\big((x=y) \lor (\exists z \in \mathbb{Q})(x<z<y \lor y<z<x)\big).\] 注意 \(x<z<y\) 是 \((x<z)\land(z<y)\) 的数学简写，故上式等价于 \[(\forall x,y \in \mathbb{Q})(x=y) \lor ((\exists z \in \mathbb{Q})((x<z)\land(z<y)) \lor ((y<z)\land(z<x)))).\]

(c) \[(\forall x \in \mathbb{Z})\big((x^2 > 4) \implies ((x > 2) \lor (x < -2))\big).\]

(d) 所有实数都是复数。

(e) 方程 \(x^2 - y^2 = 10\) 没有整数解。

(f) 对于任意大于 1 的自然数，总存在质数 \(a\) 和 \(b\) 使得 \(2x = a + b\)。换言之：任何大于 2 的偶整数都可以写成两个质数之和。附注：该命题被称为哥德巴赫猜想（Goldbach's Conjecture），是数论中一个著名的未解决问题。

(a) 真（True）。相邻的存在量词可以交换：\(\exists x\exists y\) 与 \(\exists y\exists x\) 都表示“在我们论域中存在 \(x\) 与 \(y\)”。

(b) 假（False）。令 \(Q(x,y)\) 为 \(x<y\)，\(x\) 与 \(y\) 的论域为整数集。或者令 \(Q(x,y)\) 为 \(x=y\)，论域为任意至少含两个元素的集合。在这两种情况下，前件为真而后件为假，故整个蕴含为假。

(c) 真（True）。第一个命题表明，存在某个 \(x\)，记作 \(x'\)，使得对每个 \(y\) 都有 \(Q(x,y)\) 为真。因此对第二个命题可以取 \(x=x'\)，则该命题对每个 \(y\) 仍然为真。

(d) 假（False）。设 \(Q\) 为命题“\(y\) 是 5，且 \(x\) 是任意整数”。当 \(y=5\) 时前件为真，但当 \(y \neq 5\) 时，不存在任何 \(x\) 能使该命题为真。

(a) 等价。 把左边改写为 \(\forall x \exists y (\neg P(x) \lor Q(x,y))\)。 把右边改写为 \(\forall x (\neg P(x) \lor \exists y Q(x,y))\)。 若 \(\neg P(x)\) 为真，则两边显然相同。若 \(\neg P(x)\) 为假，则两边仍然相同，因为 \(\forall x \exists y (\text{False} \lor Q(x,y)) \equiv \forall x \exists y Q(x,y) \equiv \forall x (\text{False} \lor (\exists y Q(x,y)))\)。

(b) 不等价。 把左边改写为 \[\forall x ((\exists y Q(x,y)) \implies P(x)) \equiv \forall x ((\neg(\exists y Q(x,y))) \lor P(x)) \equiv \forall x ((\forall y \neg Q(x,y)) \lor P(x)) \equiv \forall x \forall y (\neg Q(x,y) \lor P(x)),\] 其中最后一步把 \(\forall y\) 提到 \(\lor\) 内，因为 \(P(x)\) 不依赖于 \(y\)。 把右边改写为 \[\forall x \exists y (Q(x,y) \implies P(x)) \equiv \forall x \exists y (\neg Q(x,y) \lor P(x)).\] 于是得到 \(\forall x \forall y (\neg Q(x,y) \lor P(x)) \not\equiv \forall x \exists y (\neg Q(x,y) \lor P(x))\)，故两边不等价。

另一种思路是用一个通俗例子：让 \(x\) 与 \(y\) 取遍所有人的集合，\(Q(x,y)\) 表示“\(x\) 是 \(y\) 的后代”，\(P(x)\) 表示“\(x\) 喜欢豆腐”。右边声称：对所有 \(x\)，存在某个 \(y\) 使得 \(x\) 不是 \(y\) 的后代或 \(x\) 喜欢豆腐。左边声称：对所有 \(x\)，如果 \(x\) 有父母，则 \(x\) 喜欢豆腐。二者显然不同。

(c) 不等价。 对左边用德摩根律将否定向内传播： \[\neg \exists x \forall y (P(x,y) \implies \neg Q(x,y)) \equiv \forall x \neg \forall y (P(x,y) \implies \neg Q(x,y)) \equiv \forall x \exists y \neg (P(x,y) \implies \neg Q(x,y)) \equiv \forall x \exists y \neg (\neg P(x,y) \lor \neg Q(x,y)) \equiv \forall x \exists y (P(x,y) \land Q(x,y)).\] 但 \(\exists\) 对 \(\land\) 不可分配。对于给定的 \(x\)，可能存在不同的 \(y\) 值分别使得 \(P(x,y)\) 与 \(Q(x,y)\) 成立，而不必是同一个 \(y\)。因此两边不等价。

要证明 \(A=B\)，需证 \(A\subseteq B\) 且 \(B\subseteq A\)。要证左 \(\subseteq\) 右，需证：若一个元素属于左，则它也属于右。

(a) 设 \(x\) 满足 \(f(x) \in A \cap B\)。则 \(f(x)\) 同时属于 \(A\) 与 \(B\)，故 \(x\) 同时属于 \(f^{-1}(A)\) 与 \(f^{-1}(B)\)，即 \(x \in f^{-1}(A) \cap f^{-1}(B)\)。因此 \(f^{-1}(A \cap B) \subseteq f^{-1}(A) \cap f^{-1}(B)\)。

反之，设 \(x \in f^{-1}(A) \cap f^{-1}(B)\)。则 \(x\) 同时属于 \(f^{-1}(A)\) 与 \(f^{-1}(B)\)，故 \(f(x) \in A\) 且 \(f(x) \in B\)，即 \(f(x) \in A \cap B\)，从而 \(x \in f^{-1}(A \cap B)\)。因此 \(f^{-1}(A) \cap f^{-1}(B) \subseteq f^{-1}(A \cap B)\)。

(b) 设 \(x\) 满足 \(f(x) \in A \setminus B\)。则 \(f(x) \in A\) 且 \(f(x) \notin B\)，从而 \(x \in f^{-1}(A)\) 且 \(x \notin f^{-1}(B)\)，即 \(x \in f^{-1}(A) \setminus f^{-1}(B)\)。因此 \(f^{-1}(A \setminus B) \subseteq f^{-1}(A) \setminus f^{-1}(B)\)。

反之，设 \(x \in f^{-1}(A) \setminus f^{-1}(B)\)。则 \(x \in f^{-1}(A)\) 且 \(x \notin f^{-1}(B)\)，故 \(f(x) \in A\) 且 \(f(x) \notin B\)，即 \(f(x) \in A \setminus B\)，从而 \(x \in f^{-1}(A \setminus B)\)。因此 \(f^{-1}(A) \setminus f^{-1}(B) \subseteq f^{-1}(A \setminus B)\)。

(c) 设 \(x \in A \cap B\)。则 \(x\) 同时属于 \(A\) 与 \(B\)，故 \(f(x)\) 同时属于 \(f(A)\) 与 \(f(B)\)，即 \(f(x) \in f(A) \cap f(B)\)。因此 \(f(A \cap B) \subseteq f(A) \cap f(B)\)。

反例：取 \(a \in A\)，\(b \in B\)，满足 \(f(a)=f(b)\)，但 \(A\) 与 \(B\) 不相交。此时 \(f(a)=f(b) \in f(A) \cap f(B)\)，但 \(f(A \cap B)=\varnothing\)（因为 \(A \cap B = \varnothing\)），等号不成立。

(d) 设 \(y \in f(A) \setminus f(B)\)。由于 \(y \notin f(B)\)，\(B\) 中没有元素映射到 \(y\)。设 \(x\) 为 \(A\) 中任意一个映射到 \(y\) 的元素；由前一句知 \(x\) 不可能属于 \(B\)。故 \(x \in A \setminus B\)，从而 \(y \in f(A \setminus B)\)。因此 \(f(A) \setminus f(B) \subseteq f(A \setminus B)\)。

反例：取 \(B=\{0\}\)，\(A=\{0,1\}\)，且 \(f(0)=f(1)=0\)。则 \(A \setminus B = \{1\}\)，故 \(f(A \setminus B)=\{0\}\)。然而 \(f(A)=f(B)=\{0\}\)，故 \(f(A) \setminus f(B)=\varnothing\)，等号不成立。