离散数学笔记_第一章：逻辑和证明（2 ）

1.2.1 语句翻译

🐳为啥要翻译语句？
➡因语言常常有二义性（有歧义，尤其是博大精深的汉语），把语句翻译成复合命题可以消除歧义！

把语句翻译成逻辑表达式的过程：
step①：设原子命题变量
step②：用所设的这些变量，通过逻辑联结词，表示出语句的各个部分
step③：把各个部分再通过逻辑联结词组合成最终的复合命题

1.2.2 系统规范说明

描述硬件系统和软件系统的时候，将自然语言语句翻译成逻辑表达式是很重要的一部分。系统和软件工程师根据自然语言描述的需求，生成精确而无二义的规范说明。

注意：系统规范说明应该是一致的！！！

⭐⭐⭐"一致"指的是： 存在同时为真的情况。

1.2.3 布尔搜索

逻辑联结词广泛用于海量信息如网页索引的搜索中。由于搜索采用命题逻辑的技术，因此被称为布尔搜索

布尔搜索中，联结词AND用于匹配同时包含两个搜索项的记录；OR用于匹配两个搜索项之一或者两项均匹配的记录；NOT（有时写作AND NOT），用于排除某个特定搜索项👇

1.2.4 逻辑谜题

泥巴孩子谜题

父亲让两个孩子（一个男孩和一个女孩）在后院玩耍，并让他们不要把身上搞脏。然而，在玩耍的过程中，两个孩子额头上都沾了泥。当孩子们回来后，父亲说："你们当中至少有一个人额头上有泥。“然后要求孩子们用"是"和"否"回答问题：“你知道你额头上是否有泥吗？“父亲问了两遍同样的问题。假设每个孩子都可以看到对方的额头上是否有泥，但不能看见自己的额头，孩子们在每次被问到这个问题时将会怎样回答呢？（假设两个孩子都很诚实并且都同时回答每一次提问）
解：令 s 和 d 分别表示语句"儿子的额头上有泥"和"女儿的额头上有泥”。当父亲说：“你们当中至少有一个人额头上有泥"时，表示的是 sVd 为真。当父亲第一次问那个问题时两个孩子都将回答"否”，因为他们都看到对方的额头上有泥。也就是说，儿子知道 d 为真，但不知道 s 是否为真。而女儿知道 s 为真，但不知道 d 是否为真。
在儿子对第一次询问回答"否"后，女儿可以判断出 d 必为真。这是因为问第一次问题时，儿子知道 sVd 为真，但不能判断 s 是否为真。利用这个信息，女儿能够得出结论 d 必定为真，因为如果 d 为假，则儿子就有理由推出，由于 sVd 为真，那么 s 必定为真，因此他对第一个问题的回答应为"是”。儿子也可以类似推断出 s 必为真。因此，第二次两个孩子都将回答"是”。

骑士和流氓

一个岛上居住着两类人——骑士和流氓。骑士说的都是真话，而流氓总是说谎。现在碰到了两个人A和B，如果A说“B是骑士”，B说“我们两人不是一类人”。请判断A、B两人到底是骑士还是流氓。

解：每个人要么是骑士，要么是流氓。给出假设通过判断是否产生矛盾，来求解。
假设A是骑士（说真话），则B也是骑士，那么B也应当说真话，但B所说的与A说的矛盾→A不是骑士。

假设A是流氓（说假话），则B也是流氓，那么B也应当说谎话，可以判断出AB不矛盾，所以A和B都是流氓。

（考研逻辑题）

1.

某项测试共有4道题,每道题给出A、B、C、D四个选项,其中只有一项是正确答案。现有张、王、赵、李4人参加了测试,他们的答题情况和测试结果如下：
答题者第一题第二题第三题第四题测试结果：
①张A B A B均不正确
②王B D B C只答对一题
③赵D A A B均不正确
④李C C B D只答对一题
I、根据以上信息,可以得出以下哪项?
A.第二题的正确答案是C
B.第二题的正确答案是D
C.第三题的正确答案是D
D.第四题的正确答案是C
E.第四题的正确答案是A
II、如果每道题的正确答案各不相同,则可以得出以下哪项?
A.第一题的正确答案是B
B.第一题的正确答案是C
C.第二题的正确答案是D
D.第二题的正确答案是A
E.第三题的正确答案是C

解：由①、③得：
B D B C只答对一题
C C B D只答对一题
Ⅰ假设第一题B对，则第二题的D、第三题的B、第四题的C错。
再根据CCBD只对一题，得：

Ⅱ假设第二题D对，则第一题的B、第三题的B、第四题的C错。再根据CCBD只对一题，得：
Ⅲ假设第三题B对，第一题的B、第二题的D、第四题的C错。
与C C B D只答对一题矛盾，故第三题B错

Ⅳ假设第四题C对，则第一题的B、第二题的D、第三题的B错。

与C C B D只答对一题矛盾，故第四题C错

最终可以得到：

答案I.E、II.A

1.2.5 逻辑电路

逻辑电路（又叫做数字电路）接受输入信号p1，p2，······，pn,每个信号1bit[或0（关）或1（开）]，产生输出信号s1，s2，······，sn, 每个1bit.

一般来说，数字电路可以有多个输出，但在这一节中只讨论只有一个输出信号的数字电路。

复杂的数字电路可以从三种基本的门电路构造而来：

(网上没找着，自己在画图里画的，有些粗糙，见谅~)