《离散数学及其运用》课后习题

引子

不论考研初试的结果如何, 复试总是要开始准备起来了. 看了下复试要求, 笔试需要离散数学和编译原理两门课, 据说难度不小, 特别是离散数学, 有很多很难的证明题. 于是买来 离散数学及其运用 和 编译原理龙书.

学习过程中光是看讲义当然不行, 做题肯定是必要的. 然而很多书上的课后习题非常多, 达到了惊人的 4200 道. 而且有相当一部分的题目都很简单, 全部做完既是一种折磨, 也不现实, 于是只选做带星号或有其他特殊标记的题目.

本书的标准答案可以参考如下链接.

https://qsctech.github.io/zju-icicles/离散数学及其应用/

我会先写一遍自己的答案, 如果对答案之后有错误, 会在对应的题号下列出.

1.1

42

如果 $p, q, r$ 的真值相同, 则对于 bool 相同值的变量 $i, j$ 而言, $i\lor\lnot j$ 必定为真. 故原式为三个真值取并,则最终结果也为真.

如果 $p, q, r$ 的真值不同, 则在 $(p , q), (q, r), (r, p)$ 这三组中一定存在恰好两组具有不同值, 且值分别为 $(T, F),(F, T)$. 其中取值为 $(F, T)$ 的组代入 $i\lor\lnot j$ 结果为假.

43

运用两次德摩根律, 可得如下结果:

$\lnot p\lor\lnot q\lor\lnot r = \lnot{(p\land q\land r)}$

当 $p, q, r$ 中至少有一个为真且至少有一个为假时, $\lnot{(p\land q\land r)} = T$, 且 $p \lor q \lor r = T$
则原式为真.

当 $p, q, r$ 全为真时, $\lnot{(p\land q\land r)} = F$; 当 $p, q, r$ 全为假时, $p \lor q \lor r = F$. 则在这两种情况下原式结果为假.

52

不是命题, 因为不能确定断言是否为真或假.

53

a

第 99 条语句为真, 剩下的所有语句皆是假.

由于这 100 条语句相互矛盾, 故最多只有一条语句为真. 若所有语句全为假, 则 “列表中恰有 100 条语句为假” 为真, 即第 100 条语句为真, 产生矛盾. 则只有一条语句为真, 有 99 条语句为假, 即第 99 条语句为真, 剩下的所有语句皆是假.

b

设总共有 $x$ 条命题为假, 则前 $x$ 条语句为真, 后 $n - x$ 条语句为假.故可得:

$x = n - x$

解得 $x = 50$, 故可得前 50 条语句为真, 后 50 条语句为假.

c

同问题 b 的做法, 解得 $ x = 99 / 2$, 而 $x$ 必须为整数, 故无解. 则列表中所有语句都矛盾, 无法确定真假.

1.2

19

"是否应该走这条路"和"你是一个诚实的人"的答案一样吗?

标准答案提供了另外一种问法: “If I were to ask you whether the right branch leads to the ruins, would you answer yes?”

42

根据初始条件, 可以列出如下表格:

国籍	颜色	工作	宠物	饮料	房子的位置
英国人	红色
西班牙人			狗
日本人		油漆工
意大利人				茶
挪威人					1

将出现在同一行的分别有:

(摄影师, 蜗牛), (外交官, 黄色), (牛奶, 3), (绿色, 咖啡), (蓝色, 2), (小提琴家, 橘子汁)

根据位置关系:

$绿色 = 白色 + 1$, $|狐狸 - 医师| = 1$, $|马 - 外交官| = 1$

推导可得:

国籍	颜色	工作	宠物	饮料	房子的位置
英国人	红色
西班牙人			狗
日本人		油漆工
意大利人				茶
挪威人	黄色	外交官		矿泉水	1

由于有 (蓝色, 2, 马), 假设白色的房子在第三个位置, 则:

国籍	颜色	工作	宠物	饮料	房子的位置
英国人	红色	摄影师	蜗牛	咖啡
西班牙人		小提琴家	狗	橘子汁
日本人	白色	油漆工	狐狸	牛奶	3
意大利人	蓝色	医师	马	茶	2
挪威人	黄色	外交官	斑马	矿泉水	1

故矛盾, 则白色的房子在第四个位置, 可得:

国籍	颜色	工作	宠物	饮料	房子的位置
英国人	红色	摄影师	蜗牛	牛奶	3
西班牙人	白色	小提琴家	狗	橘子汁	4
日本人	绿色	油漆工	斑马	咖啡	5
意大利人	蓝色	医师	马	茶	2
挪威人	黄色	外交官	狐狸	矿泉水	1

由上表观察可得, 挪威人喝矿泉水, 日本人养斑马.

这题做着是真的烧脑…感觉像是数独的变体

1.3

11