离散数学-逻辑与证明基础1.2（命题逻辑的应用）
离散数学-逻辑与证明基础1.2（命题逻辑的应用）
翻译句子
有很多理由将英文句子翻译成涉及命题变量和逻辑联结词的表达式。特别是，英语（以及所有其他人类语言）通常是模糊的。将句子翻译成复合语句（以及本章稍后会介绍的其他类型的逻辑表达式）可以消除这种模糊性。请注意，这可能涉及根据句子的预期含义作出一系列合理的假设。此外，一旦我们将句子从英文翻译成逻辑表达式，我们就可以分析这些逻辑表达式来确定它们的真值，操作它们，并且可以使用推理规则（在 1.6 节中讨论）来进行推理。
为了说明将英语句子翻译成逻辑表达式的过程，请参考例子 1 和 2。
例1如何将这个英文句子翻译为逻辑表达式？
“You can access the Internet from campus only if you are a computer science major or you are not a freshman.”
解有很多方法可以将这个句子翻译成逻辑表达式。虽然可以用一个单一的命题变量（例如p）来表示句子，但在分析其含义或推理时这并没有太大帮助。相反，我们将使用命题变量来表示句子的每个部分，并确定它们之间的合适的逻辑联结词。具体来说，我们让a、c和f分别表示 “You can access the Internet from campus”（你可以从校园访问互联网）、“You are a computer science major”（你是计算机专业的学生）和 “You are a freshman”（你是大一新生）。注意，“only if” 是表达条件语句的一种方式，因此该句子可以表示为：
a → ( c ∨ ¬ f )
例2如何将这个英文句子翻译为逻辑表达式？
“You cannot ride the roller coaster if you are under 4 feet tall unless you are older than 16 years old.”
解设q、r和s分别表示 “You can ride the roller coaster”（你可以乘坐过山车）、“You are under 4 feet tall”（你的身高低于 4 英尺）和 “You are older than 16 years old”（你超过 16 岁）。那么该句子可以翻译为：
( r ∧ ¬ s ) → ¬ q
还有其他方法可以将原句翻译为逻辑表达式，但我们使用的这种方法应该能满足我们的需求。
系统规格
将自然语言（例如英语）的句子翻译成逻辑表达式是指定硬件和软件系统的关键部分。系统和软件工程师从自然语言中获取需求，并生成可以作为系统开发基础的精确且明确的规格说明。例子 3 展示了如何在此过程中使用复合命题。
例3使用逻辑联结词表示规格说明：“The automated reply cannot be sent when the file system is full.”
解一种翻译方法是让p表示 “The automated reply can be sent”（自动回复可以发送），q表示 “The file system is full”（文件系统已满）。那么¬p表示 “It is not the case that the automated reply can be sent”，也可以表达为 “The automated reply cannot be sent”（自动回复无法发送）。因此，该规格说明可以表示为条件语句q → ¬p。
系统规格应该是一致的，也就是说，它们不应该包含可能会引发矛盾的要求。当规格不一致时，将无法开发出满足所有规格的系统。
例4确定这些系统规格是否一致：
- “The diagnostic message is stored in the buffer or it is retransmitted.”
- “The diagnostic message is not stored in the buffer.”
- “If the diagnostic message is stored in the buffer, then it is retransmitted.”
解为了确定这些规格是否一致，我们首先用逻辑表达式来表示它们。让p表示 “The diagnostic message is stored in the buffer”（诊断消息存储在缓冲区中），q表示 “The diagnostic message is retransmitted”（诊断消息被重新传输）。那么这些规格可以表示为p ∨ q、¬p和p → q。要使这三个规格都为真，必须使p为假以使¬p为真。因为我们希望p ∨ q为真但p为假，因此q必须为真。由于当p为假且q为真时p → q为真，我们得出这些规格是一致的，因为当p为假且q为真时，它们都是成立的。我们也可以通过使用真值表来检查p和q的四种可能的真值分配，得出相同的结论。
例5如果添加规格说明 “The diagnostic message is not retransmitted”（诊断消息未被重新传输），那么例子 4 中的系统规格是否仍然一致？
解根据例子 4 的推理，来自该例子的三个规格仅在p为假且q为真时为真。然而，这个新的规格是¬q，当q为真时为假。因此，这四个规格是不一致的。
布尔搜索
逻辑联结词被广泛用于对大规模信息集合的搜索中，比如网页索引。由于这些搜索采用了命题逻辑中的技术，因此它们被称为布尔搜索（Boolean searches）。
在布尔搜索中，联结词AND用于匹配包含两个搜索词的记录，联结词OR用于匹配一个或两个搜索词，而联结词NOT（有时写作AND NOT）用于排除某个特定的搜索词。在进行布尔搜索时，通常需要仔细规划如何使用逻辑联结词，以定位可能感兴趣的信息。例子 6 说明了布尔搜索是如何进行的。
例6网页搜索大多数网页搜索引擎支持布尔搜索技术，这在查找特定主题的网页时非常有用。例如，使用布尔搜索可以查找关于新墨西哥州的大学的网页，我们可以搜索符合条件 “NEW AND MEXICO AND UNIVERSITIES” 的网页。该搜索的结果将包括包含这三个单词 NEW、MEXICO 和 UNIVERSITIES 的网页。这将包括所有相关的网页，以及其他一些网页，例如关于墨西哥新大学的网页。（注意，Google 和其他许多搜索引擎确实需要使用 “AND”，因为这些搜索引擎默认使用所有搜索词。）大多数搜索引擎支持使用引号来搜索特定短语。因此，搜索匹配 “NEW MEXICO” AND UNIVERSITIES 的网页可能更有效。
接下来，为了查找与新墨西哥州或亚利桑那州的大学有关的网页，我们可以搜索符合条件 “(NEW AND MEXICO OR ARIZONA) AND UNIVERSITIES” 的网页。（注意：在这里，AND 运算符优先于 OR 运算符。此外，在 Google 中，搜索词 “NEW MEXICO OR ARIZONA” 的结果将包括所有包含单词 UNIVERSITIES 且同时包含单词 NEW 和 MEXICO 或单词 ARIZONA 的所有页面。）再一次，除了相关网页之外，其他网页也会被列出。最后，为了查找有关墨西哥（而不是新墨西哥州）大学的网页，我们可能会先查找符合条件 “MEXICO AND UNIVERSITIES” 的网页，但由于此搜索的结果将包括有关新墨西哥州的大学以及墨西哥的大学的网页，因此可能更好地搜索符合条件 “(MEXICO AND UNIVERSITIES) NOT NEW” 的网页。此搜索的结果将包括同时包含单词 MEXICO 和 UNIVERSITIES 且不包含单词 NEW 的页面。（在 Google 和其他许多搜索引擎中，词 “NOT” 被符号 “-” 替代。在 Google 中，最后一次搜索使用的词为 “MEXICO UNIVERSITIES -NEW”。）
逻辑谜题
可以通过逻辑推理解决的谜题被称为逻辑谜题。解决逻辑谜题是练习逻辑规则的极好方法。此外，设计用来执行逻辑推理的计算机程序经常使用著名的逻辑谜题来展示其能力。许多人喜欢解逻辑谜题，这些谜题通常发表在期刊、书籍和网络上，作为一种娱乐活动。
接下来的三个例子展示了逐渐增加难度的逻辑谜题。更多的谜题可以在练习中找到。在 1.3 节中，我们将讨论 n 皇后问题和数独游戏。
例7国王为了感谢你从海盗手中救回了他的女儿，给了你一个赢得宝藏的机会。宝藏藏在三个箱子中的一个。没有宝藏的另外两个箱子是空的。为了赢，你必须选对正确的箱子。箱子 1 和箱子 2 上的铭文都是 “This trunk is empty”（这个箱子是空的），而箱子 3 上的铭文是 “The treasure is in Trunk 2”（宝藏在箱子 2 里）。从不说谎的女王告诉你，这些铭文中只有一个是对的，而另外两个是错的。你应该选择哪个箱子才能赢得宝藏？
解答：设p_i 表示 “宝藏在箱子i里”，对于i = 1, 2, 3。为了将女王关于铭文中只有一个是对的陈述翻译成命题逻辑，我们注意到箱子 1、箱子 2 和箱子 3 上的铭文分别为¬ p_1 、¬ p_2 和p_2 。因此，她的陈述可以翻译为：
( ¬ p_1 ∧ ¬ ( ¬ p_2 ) ∧ ¬ p_2 ) ∨ ( ¬ ( ¬ p_1 ) ∧ ¬ p_2 ∧ p_2 ) ∨ ( ¬ ( ¬ p_1 ) ∧ ¬ ( ¬ p_2 ) ∧ p_2 )
使用命题逻辑的规则，我们看到这等价于( p_1 ∧ ¬ p_2 ) ∨ ( p_1 ∧ p_2 )。根据分配律，( p_1 ∧ ¬ p_2 ) ∨ ( p_1 ∧ p_2 )等价于p_1 ∧ ( ¬ p_2 ∨ p_2 )。由于¬ p_2 ∨ p_2 为真，因此这等价于p_1 ∧ T，进一步等价于p_1 。所以宝藏在箱子 1 里（即，p_1 为真），并且p_2 和p_3 为假；箱子 2 上的铭文是唯一一个真实的铭文。（在这里我们使用了 1.3 节中讨论的命题等价的概念。）
例子 8
在 [Sm78] 中，Smullyan 提出了许多关于一个岛屿的谜题，岛上有两种居民：骑士，他们总是说真话；无赖，他们总是撒谎。你遇到两个人 A 和 B。A 说：“B 是骑士。” B 说：“我们两个人是相反类型的。”A 和 B 分别是什么类型？
解答：
设p和q分别表示 A 是骑士和 B 是骑士的命题，那么¬p和¬q分别表示 A 是无赖和 B 是无赖的命题。
首先我们考虑 A 是骑士的可能性；也就是说，p是真的。如果 A 是骑士，那么当他说“B 是骑士”时，他在说真话，因此q也是真的，A 和 B 是相同的类型。然而，如果 B 是骑士，那么 B 所说的“我们两个人是相反类型的”这一陈述应该是真的，但是p ∧ ¬ q ∨ ¬ p ∧ q这一命题必须为真，这不可能，因为 A 和 B 都是骑士。
因此，我们可以得出结论，A 不是骑士，也就是说，p是假的。
如果 A 是无赖，那么由于无赖说的都是假话，A 说的“B 是骑士”是假的。这意味着q是假的，B 也是无赖。此外，如果 B 是无赖，那么 B 所说的“我们两个人是相反类型的”是假的，这与 A 和 B 都是无赖这一结论一致。
我们可以得出结论：A 和 B 都是无赖。
逻辑电路
命题逻辑可以应用于计算机硬件的设计。这个应用最早是在1938年由Claude Shannon在他的MIT硕士论文中提出的。在第12章，我们将深入研究这个话题。在这里，我们简要介绍这一应用。
逻辑电路（或数字电路）接收输入信号p_1, p_2, \dots, p_n，每个信号是一个比特（0表示关闭，1表示开启），并产生输出信号s_1, s_2, \dots, s_n，每个信号也是一个比特。在本节中，我们将注意力限制在单个输出信号的逻辑电路上；通常，数字电路可能有多个输出。
复杂的数字电路可以由三种基本电路，称为门，构建，如图1所示。反相器，或非门，接收一个输入比特p，并输出¬p。或门接收两个输入信号p和q，每个信号是一个比特，并输出信号p ∨ q。最后，与门接收两个输入信号p和q，每个信号是一个比特，并输出信号p ∧ q。我们使用这三种基本门的组合来构建更复杂的电路，例如图2所示的电路。
例10确定图 2 中组合电路的输出。
解答：在图 2 中，我们展示了每个逻辑门电路的输出。我们看到，与门接受输入p和¬q，非门的输出为¬q，因此与门产生p ∧ ¬q。接着，我们注意到或门接受p ∧ ¬q和¬r的输入，非门的输出为¬r，因此或门产生最终的输出( p ∧ ¬ q ) ∨ ¬ r。
例11构建一个数字电路，该电路在输入位p、q和r时产生输出( p ∨ ¬ r ) ∧ ( ¬ p ∨ ( q ∨ ¬ r ) )。
解为了构建所需的电路，我们分别为p ∨ ¬ r和¬ p ∨ ( q ∨ ¬ r )构建单独的电路，并使用 AND 门将它们组合起来。
要构建p ∨ ¬ r的电路，我们使用一个反相器从输入r生成¬r。然后，我们使用一个 OR 门将p和¬r组合在一起。
要构建¬ p ∨ ( q ∨ ¬ r )的电路，我们首先使用反相器得到¬p。然后，我们使用 OR 门将q和¬r作为输入得到q ∨ ¬r。最后，我们使用另一个反相器和 OR 门将¬p和q ∨ ¬r组合在一起，得到¬ p ∨ ( q ∨ ¬ r )。
为了完成电路构建，我们使用一个最终的 AND 门，将p ∨ ¬ r和¬ p ∨ ( q ∨ ¬ r )作为输入。生成的电路如图 3 所示。