相关笔记: 1.1 命题逻辑 | 1.3 命题等价

概览

本节展示 1.1 命题逻辑 中学到的逻辑工具在多个实际领域中的应用,核心在于将自然语言的模糊性转化为逻辑表达式的精确性

  • 自然语言翻译是消除歧义的关键步骤,将英语/中文句子转化为命题逻辑公式
  • 系统规约(system specification)用逻辑表达式精确描述软硬件需求,并检验规约的一致性(consistency)
  • 布尔搜索(Boolean search)利用 AND、OR、NOT 联结词在大型信息集合中精确检索
  • 逻辑谜题(logic puzzle)通过命题建模和逻辑推理训练形式化思维能力
  • 逻辑电路(logic circuit)将命题逻辑直接映射为数字电路设计,是计算机硬件的基础

一、知识结构总览

graph TB
    A["1.2 命题逻辑的应用"] --> B["自然语言翻译"]
    A --> C["系统规约"]
    A --> D["布尔搜索"]
    A --> E["逻辑谜题"]
    A --> F["逻辑电路"]

    B --> B1["消除歧义"]
    B --> B2["命题变量定义"]
    B --> B3["联结词选择"]

    C --> C1["需求精确化"]
    C --> C2["一致性检验"]
    C --> C3["矛盾检测"]

    D --> D1["AND 匹配"]
    D --> D2["OR 匹配"]
    D --> D3["NOT 排除"]

    E --> E1["宝箱问题"]
    E --> E2["骑士与无赖"]
    E --> E3["泥孩子问题"]

    F --> F1["NOT 门 / 反相器"]
    F --> F2["OR 门"]
    F --> F3["AND 门"]
    F --> F4["组合电路"]

二、核心思想

核心思想

1. 将英语句子翻译为逻辑表达式

1. 将英语句子翻译为逻辑表达式

翻译方法论

将自然语言翻译为命题逻辑的一般步骤:

  1. 识别原子命题:将句子分解为最基本的陈述成分
  2. 定义命题变量:为每个原子命题分配一个字母(
  3. 选择逻辑联结词:根据句子中的关键词(“and”、“or”、“if…then”、“only if”、“unless” 等)选择对应的逻辑联结词
  4. 组合表达式:按照句子的逻辑结构组合命题变量

翻译示例 1

“You can access the Internet from campus only if you are a computer science major or you are not a freshman.”

步骤分析

  1. 定义命题变量:

    • :“You can access the Internet from campus”
    • :“You are a computer science major”
    • :“You are a freshman”
  2. 关键词分析:

    • “only if” 对应条件语句
    • “or” 对应析取
    • “not a freshman” 对应
  3. 最终表达式:

翻译示例 2

“You cannot ride the roller coaster if you are under 4 feet tall unless you are older than 16 years old.”

步骤分析

  1. 定义命题变量:

    • :“You can ride the roller coaster”
    • :“You are under 4 feet tall”
    • :“You are older than 16 years old”
  2. 关键词分析:

    • “cannot ride” 对应
    • “if” 引出条件,“unless” 等价于 “if not”
    • 整句逻辑:如果你身高不足4英尺你不超过16岁,则不能乘坐
    • 即:
  3. 最终表达式:

"unless" 的处理

unless ” 等价于 。例如 “You will get an A unless you don’t study” 等价于 “If you study, you will get an A”。翻译 “unless” 时,将其替换为 “if not” 往往更清晰。

2. 系统规约

系统规约(System Specification)

在软硬件工程中,系统规约是使用逻辑表达式精确描述系统需求的过程。规约必须满足一致性(consistency)——即所有规约不能相互矛盾,否则无法开发出满足所有需求的系统。

系统规约示例

“The automated reply cannot be sent when the file system is full.”

定义变量:

  • :“The automated reply can be sent”
  • :“The file system is full”

翻译:(如果文件系统满了,则不能发送自动回复)

一致性检验

判断以下系统规约是否一致:

  1. “The diagnostic message is stored in the buffer or it is retransmitted.”
  2. “The diagnostic message is not stored in the buffer.”
  3. “If the diagnostic message is stored in the buffer, then it is retransmitted.”

推理过程

  1. 为真,得
  2. 为真且 ,得
  3. 验证

三者在 时同时为真,因此规约是一致的

不一致性检验

在上述规约基础上,添加第四条:

  1. “The diagnostic message is not retransmitted.”

由前面的推理,唯一使前三条同时为真的赋值是 。但 时为假。因此四条规约不一致

一致性检验方法

检验一组规约是否一致,就是寻找是否存在一组真值赋值使得所有规约同时为真。如果存在,则一致;如果不存在(即所有可能的赋值都至少使一条规约为假),则不一致。

3. 布尔搜索

布尔搜索(Boolean Search)

布尔搜索利用命题逻辑的联结词在大型信息集合(如网页索引)中进行精确检索:

搜索运算符逻辑联结词含义
AND匹配同时包含两个搜索词的记录
OR匹配包含至少一个搜索词的记录
NOT(或 AND NOT)排除包含特定搜索词的记录

布尔搜索示例

目标:查找关于新墨西哥州(New Mexico)大学的网页

搜索表达式匹配内容
NEW AND MEXICO AND UNIVERSITIES同时包含三个词的页面(但也会匹配墨西哥的新大学)
"NEW MEXICO" AND UNIVERSITIES包含短语 “NEW MEXICO” 和词 UNIVERSITIES 的页面
(NEW MEXICO OR ARIZONA) AND UNIVERSITIES包含 UNIVERSITIES 且包含 NEW MEXICO 或 ARIZONA 的页面
(MEXICO AND UNIVERSITIES) NOT NEW包含 MEXICO 和 UNIVERSITIES 但不包含 NEW 的页面

搜索引擎中的布尔运算

在 Google 等现代搜索引擎中,AND 是默认行为(所有搜索词都必须出现),OR 需要显式写出,NOT 用减号 - 表示。例如 MEXICO UNIVERSITIES -NEW

4. 逻辑谜题

4.1 宝箱问题

宝箱问题

三个宝箱,只有一个装有宝藏。宝箱铭文:

  • 宝箱 1:“This trunk is empty.”(
  • 宝箱 2:“This trunk is empty.”(
  • 宝箱 3:“The treasure is in Trunk 2.”(

女王说:只有一条铭文为真。

求解过程

表示”宝箱 中有宝藏”()。

女王的话翻译为逻辑表达式(恰好一条铭文为真):

化简(利用 1.3 命题等价 中的等价律):

  1. 第一个子式:(矛盾,不可能)
  2. 第二个子式:
  3. 第三个子式:

所以:

结论:宝藏在宝箱 1 中(),宝箱 2 的铭文是唯一为真的。

4.2 骑士与无赖(Knights and Knaves)

骑士与无赖

Raymond Smullyan 提出的经典逻辑谜题:

  • 骑士(knight):总是说真话
  • 无赖(knave):总是说谎话

骑士与无赖问题

A 说:“B is a knight.” B 说:“The two of us are opposite types.”

:“A is a knight”,:“B is a knight”。

推理过程

情况 1:假设 A 是骑士(

  • A 说真话 B 是骑士(
  • B 说真话 “A 和 B 是不同类型”为真
  • 但 A 和 B 都是骑士,是相同类型 矛盾!
  • 因此 ,A 不是骑士

情况 2:A 是无赖(

  • A 说谎 “B is a knight” 为假 ,B 也是无赖
  • B 说谎 “A 和 B 是不同类型” 为假
  • A 和 B 都是无赖,确实是相同类型 与”不同类型为假”一致 ✓

结论:A 和 B 都是无赖。

4.3 泥孩子问题(Muddy Children Puzzle)

泥孩子问题

父亲对两个孩子说:“你们中至少一个人额头上有泥。” 然后问:“你知道自己额头上有泥吗?” 问两次。

:“儿子额头有泥”,:“女儿额头有泥”。两个孩子都有泥,即

第一次提问

  • 儿子看到女儿有泥(),知道 为真,但无法确定 是否为真 回答 “No”
  • 女儿看到儿子有泥(),知道 为真,但无法确定 是否为真 回答 “No”

第二次提问

  • 儿子推理:女儿第一次回答 “No”,说明女儿不确定自己是否有泥。如果女儿没有泥(),那么女儿看到儿子有泥(),且知道 为真,就会立即知道 必须为真,从而回答 “Yes”。但女儿回答了 “No”,说明 不可能为假,即 。但儿子已经知道 (看到了),这个推理不能帮儿子确定

等等,让我们更仔细地分析:

第二次提问的推理

  • 儿子知道: 为真(父亲说的),(看到的)
  • 儿子还知道:女儿第一次回答 “No”
  • 儿子推理:如果 ,那么女儿看到 ,但知道 为真,所以女儿能推出 ,就会在第一次回答 “Yes”。但女儿回答了 “No”,所以 ,即
  • 女儿做对称推理,得出

结论:两个孩子第二次都回答 “Yes”。

5. 逻辑电路

逻辑门(Logic Gates)

命题逻辑可以直接映射到数字电路设计。三种基本逻辑门:

逻辑门符号输入输出对应逻辑运算
反相器(Inverter)/ NOT 门NOT否定
OR 门OR析取
AND 门AND合取

分析组合电路

给定电路:输入 ,输出

电路结构

  1. 取反得到 (NOT 门)
  2. 做合取得到 (AND 门)
  3. 取反得到 (NOT 门)
  4. 做析取得到最终输出(OR 门)

根据逻辑表达式构造电路

构造输出为 的电路:

分解步骤

  1. 构造子电路
    • NOT 门:
    • OR 门:
  2. 构造子电路
    • NOT 门:(可复用)
    • OR 门:
    • NOT 门:
    • OR 门:
  3. 用 AND 门组合两个子电路的输出

逻辑电路与命题逻辑的对应关系

每一个命题逻辑表达式都可以对应一个逻辑电路,反之亦然。这种对应关系是布尔代数(1.3 命题等价 和第12章)的核心应用。电路化简对应逻辑表达式化简,可以减少硬件成本。


三、补充理解与易混淆点

补充理解

1. 逻辑在软件工程形式化方法中的应用

将自然语言需求翻译为逻辑表达式不仅是学术练习,更是工业界**形式化方法(formal methods)**的核心。在安全攸关系统(如航空控制、医疗设备、核反应堆)的开发中,使用逻辑规约语言(如 Z、VDM、TLA+、Alloy)精确描述系统行为,并通过模型检测(model checking)自动验证系统是否满足规约。例如,Amazon Web Services 使用 TLA+ 对其分布式系统(如 DynamoDB)进行形式化验证,在部署前发现了多个微妙的设计缺陷。这种方法的核心思想与本节介绍的”系统规约 + 一致性检验”完全一致。

网络资源:

2. 布尔搜索与信息检索的演进

布尔搜索是信息检索(Information Retrieval)领域的基石。早期的信息检索系统(如 1960 年代的 MEDLINE)完全依赖布尔查询模型。虽然现代搜索引擎(Google、Bing)已发展出基于概率排序的模型(如 PageRank、BM25),布尔逻辑仍然是查询语法的基础组成部分。在专业数据库检索(如法律数据库 Westlaw、学术数据库 PubMed)中,布尔搜索仍然是核心检索方式。理解布尔逻辑的 AND/OR/NOT 运算对于有效利用这些工具至关重要。更高级的检索系统还引入了模糊逻辑(fuzzy logic),允许对查询结果进行相关性排序而非简单的二元匹配。

网络资源:

易混淆点

1. “only if” vs “if” 的翻译方向

  • ❌ 将 “You can graduate only if you pass all exams” 翻译为 “If you pass all exams, you can graduate”(
  • ✅ 正确翻译为 “If you can graduate, then you passed all exams”()。“only if” 表示必要条件:通过考试是毕业的必要条件,即毕业 通过考试。注意 ” only if ” 等价于 ,而非

2. 系统规约的一致性 vs 正确性

  • ❌ 认为一致的规约一定是正确的、合理的
  • ✅ 一致性(consistency)仅意味着规约之间不矛盾,不保证规约本身是正确或合理的。例如,“系统总是返回错误”和”系统从不返回错误”是不一致的(矛盾),但”系统总是返回错误”和”系统在用户输入时返回错误”是一致的(不矛盾),尽管前者可能不是好的设计

四、习题精选

习题概览

题号范围核心考点难度
1-6自然语言翻译为命题逻辑⭐⭐
7-8系统规约的逻辑表达⭐⭐
9-12系统规约一致性检验⭐⭐⭐
13-16布尔搜索表达式构造⭐⭐
17-18宝箱问题变体⭐⭐⭐
19-22骑士与无赖谜题⭐⭐⭐
23-35骑士、无赖与间谍谜题⭐⭐⭐⭐
36-42逻辑推理综合题⭐⭐⭐⭐
44-47逻辑电路分析与构造⭐⭐⭐

题1:系统规约一致性检验

题目

判断以下系统规约是否一致:

  1. “当文件系统满时,不能发送自动回复。”(
  2. “诊断消息存储在缓冲区中或被重传。”(
  3. “诊断消息没有存储在缓冲区中。”(
  4. “如果诊断消息存储在缓冲区中,则被重传。”(

题2:自然语言翻译为命题逻辑

题目

将”如果天下雨且我出门,我就带伞”翻译为命题逻辑公式。定义所有使用的命题变量。

题3:判断逆命题是否等价

题目

判断 (即逆命题)是否逻辑等价。用真值表验证。

题4:用命题逻辑建模多数表决系统

题目

一个系统有3个开关 ,当至少2个开关开启时系统运行。用命题逻辑写出系统运行的逻辑表达式。

题5:设计4人委员会多数决投票系统

题目

设计一个4人委员会投票系统(多数决,即至少3人赞成时提案通过)。设4个委员为 ,用命题逻辑写出所有通过条件。


解题思路提示

  1. 自然语言翻译:先定义命题变量,再识别关键词(“only if”、“unless”等),最后组合表达式
  2. 一致性检验:寻找使所有规约同时为真的赋值,若存在则一致
  3. 布尔搜索:AND = 同时包含,OR = 至少一个,NOT = 排除

五、视频学习指南

视频资源

资源链接对应内容备注
Rosen 8e Section 1.2教材原文命题逻辑的应用完整内容英文教材
MIT 6.042J Lectures链接对应章节讲解英文,MIT开放课程
TrevTutor Discrete Math链接知识点精讲英文,适合入门

六、教材原文

教材原文

“Translating sentences in natural language (such as English) into logical expressions is an essential part of specifying both hardware and software systems.”

“We can use Boolean searches to find relevant Web pages. These searches employ techniques from propositional logic.”


参见 Wiki

  • 命题逻辑 — 基于命题和逻辑联结词的形式逻辑系统
  • 逻辑电路 — 使用逻辑门实现布尔函数的电子电路

逻辑与证明