- 1.1 命题逻辑
- 1.2 命题逻辑的应用
- 1.3 等价命题
- 1.4 谓词和量词
- 1.5 量词嵌套
- 1.6 推理规则
- 1.7 证明简介
- 1.8 证明方法和策略
逻辑规则明确了数学陈述的含义。比如，逻辑规则帮助我们理解和推理诸如“存在一个不是两个平方数和的整数”及“对每个正整数n，不超过n的所有正整数的和是n(n+1)/2”的数学陈述。
逻辑是所有数学推理和自动推理的基础，在计算机设计、系统规范、人工智能、计算机编程、程序语言、计算机科学的其他领域及许多其他研究领域中都有实际应用。
为了理解数学，我们必须理解什么组成了一个正确的数学论证，即证明。一旦我们证明了一个数学陈述是正确的，就称它为定理。有关一个主题的定理集构成了我们对这个主题的了解。为了学习一个数学主题，一个人不仅要阅读论述，还要积极地构建有关该主题的数学论证。而且，知道了一个定理的证明会使得修改结果来适应新的情况成为可能。
虽然每个人都知道证明在整个数学中很重要，但是许多人对证明在计算机科学中有多重要很好奇。实际上，可使用证明来验证：对所有可能的输入值，计算机程序都能有正确的输出。可使用证明来展示：算法通常会产生正确的结果。可使用证明来确保一个系统的安全性。可使用证明来创建人工智能。而且，创建自动推理系统就是允许计算机自己构建证明。
在这一章中，我们将解释什么组成了一个正确的数学论证，及介绍构建这些论证的工具。我们将开发一个由不同证明方法组成的库，使得我们能证明不同类型的结果。在介绍了许多不同证明方法后，我们将介绍几种构建证明的策略。我们将介绍猜想的概念，并通过研究猜想来解释数学发展的过程。
1.1 命题式逻辑
1.1.1 简介
关键词 逻辑 逻辑规则
逻辑规则给予数学陈述精确的含义。可使用逻辑规则来区分有效和无效的数学论证。
因为本书的一个主要目标是教会读者如何理解和构建正确的数学论证，所以我们从对逻辑的介绍开始对离散数学的研究。
逻辑除了在理解数学推理上很重要，还在计算机科学中有许多应用。逻辑规则可用于计算机电路设计、计算机程序构建、程序正确性验证以及许多其他方面。而且，已开发了用于自动构建一些证明类型(不是全部类型)的软件系统。
1.1.2 命题
命题是逻辑的基本构建模块。
一个命题就是一条陈述性语句，即声明了一个事实的语句。
命题要么是真的，要么是假的，不可能同时为真或假。
例1 命题示例
- 华盛顿是美国的首都。
- 多伦多是加拿大的首都。
- 1+1=2。
- 2+2=3。
解释：命题1和命题3是真的，命题2和命题4是假的。
例2 非命题示例
- 几点了？
- 仔细阅读这个。
- x+1=2。
- x+y=z。
解释：句1和句2不是命题，因为它们不是声明式语句。
句3和句4不是命题，因为它们既不为真，也不为假。
注意：如果给变量赋值，则句3和句4可以转换成命题。我们将在第1.4节里讨论将诸如句3和句4的语句转换成命题的其他的方法。
跟使用字母来表示数值变量一样，我们使用字母来表示命题变量，即表示命题的变量。
用来表示命题变量的约定字母是。
如果一个命题是真命题，则它的真值就是真的，用大写字母T表示；
如果一个命题是假命题，则它的真值就是假的，用大写字母F表示；
不能用更简单的命题来表示的命题就是原子命题。
命题式逻辑
处理命题的逻辑规则就是命题式逻辑。
命题式逻辑是由距今超过2300年的古希腊哲学家亚里士多德首次开发出来的。
从已有命题发展出新命题的方法
早在1854年，英国数学家乔治布尔就已在他的书《思维法则》中讨论了如何从已有命题发展出新命题。
通过组合一个或者多个命题可以构建许多数学语句。
复合命题
通过使用逻辑运算符从已有命题形成的新命题，就是复合命题。
有哪些逻辑运算符？(与、或、非)
- 非运算符
- 与运算符
- 或运算符
- 异或运算符
否命题
对原命题使用非运算符就形成了否命题。
例3 找出命题“Michael的PC运行的是linux”的否命题。
解：否命题是Michael的PC运行的不是linux。
例4 找出命题“Vandana的智能手机至少有32GB的内存”的否命题。
解：否命题是Vandana的只能手机的内存少于32GB。
与命题
例5 命题p：Rebecca的PC有超过16GB的空闲磁盘空间。命题q：Rebecca的PC上的处理器运行速度超过1GHz。找出命题p和命题q的与命题。
或命题
例6 命题p：上过微积分的学生可以选这门课。命题q：上过计算机科学导论的学生可以选这门课。请用命题逻辑来转换语句：上过微积分或者计算机科学导论的学生可以选这门课。
例7 命题p：Rebecca的PC有超过16GB的空闲磁盘空间。命题q：Rebecca的PC上的处理器运行速度超过1GHz。找出命题p和命题q的或命题。
异或命题
例8 命题p：学生的晚餐有色拉。命题q：学生的晚餐有汤。找出命题p和命题q的异或命题。
例9 命题p：我将使用所有的积蓄去欧洲旅行。命题q：我将使用所有的积蓄来买一辆电动车。请使用命题逻辑来表示语句“我将使用所有的额积蓄去欧洲旅行或者购买电动车”。
1.1.3 条件语句
假设p和q都是命题，则条件语句p->q就是命题“如果p，则q”。
条件语句p->q的真值
- 当p为真，q是假时，条件语句p->q的真值为F；
- 其余情形，条件语句p->q的真值为T；
注意：
- 当p为F，则无论q的真值是T还是F，条件语句p->q的真值都是T；
示例1 如果我当选了，则我将降低税收。
示例2 如果你在期末考试中得了100分，则你将得到A。
示例3 只有你在期末考试中分数至少是90分时，你才会拿到A。
例10
命题p：Maria学习了离散数学
命题q：Maria将会找到一个好工作
请使用条件语句p->q来表示。
解：如果Maria学习了离散数学，则她将会找到一份好工作。
注意：
命题式语言是人造的语言。
在许多编程语言中的if-then结构跟命题式逻辑中的if-then结构是不同的。
许多编程语言包含诸如if p then S的语句，其中p是一个命题，S是一个程序段(一条或者多条待执行的语句)。注意，虽然看起来像条件语句，但是S不是一个命题，而是一组可执行指令。当程序执行遇到这样的语句时，如果p为真，则就执行S；如果p为假，则不执行S。
例11 在语句“if 2+2=4 then x:=x+1”后，变量x的值是多少？如果在碰到该语句前，x的值是0。
解：x的值是1
从条件语句p->q出发，形成新的条件语句：
- 逆命题 q->p
- 否命题 非p->非q
- 逆否命题 非q->非p
逆否命题和原命题的等价性
逆否命题r：非q->非p
命题r为假，当且仅当命题“非q为真”，命题“非p为假”，即p为真，q为假。
等价命题
当两个复合命题有相同的真值时，称这两个命题是等价的。
双条件语句p<->q
一种将有相同真值的命题组合起来的方式。
双条件语句的5种等价命题描述
- 命题p 当且仅当 q
- 命题p是q的充分必要条件
- 命题if p the q，and if q then p
- 命题p iff q
- 命题p exactly when q
总结一下：
命题组合的方法
- 使用逻辑运算符
- 条件语句
- 双条件语句
具体地讲，就是
- 从一个命题出发，通过非运算形成否命题；
- 从两个命题出发，通过与运算、或运算、异或运算等逻辑运算符可形成新的命题：与命题、或命题、异或命题等；
- 从条件命题出发，可形成逆命题、否命题、你否命题、等价命题；
- 双条件命题，对应的是等价命题
1.1.4 复合命题的真值计算
我们已经介绍了5个重要的逻辑运算符：与、或、异或、条件语句、双条件语句等。
我们可使用这些连接词来构建复杂的复合命题，可能包含任意数量的命题变量。
我们使用真值表来判断这些复合命题的真值。
- 与 &
- 或 |
- 非 !
- ->
- <->
1.1.5 逻辑运算符的优先级
非运算符 1
与运算符 2
或运算符 3
条件运算符 4
双条件运算符 5
1.1.6 逻辑运算和位运算
计算机使用bit来表示信息。
一个bit就是一个有两个可能值(0或1)的符号。
可使用1个bit来来表示真值，因为有两种可能的真值，true和false。
通常使用1表示T，0表示F。
布尔变量
如果一个变量的值是true或者false，则这个变量就是布尔变量。
可使用1个bit来表示布尔变量。
计算机中的位运算对应着命题逻辑中的逻辑运算。
与逻辑运算符对应着位运算符与AND
或逻辑运算符对应着位运算符或OR
异或逻辑运算符对应着位运算符XOR
信息一般使用位字符串表示的。
对位字符串进行运算就是对信息进行操作。
位字符串的运算
- 按位与
- 按位或
- 按位异或
将命题的逻辑运算转化为位运算。
- 用1表示T
- 用0表示F
重点
信息的计算机化处理流程：
- 将信息转化成命题，即将信息的处理转换成命题的逻辑运算，数学推理；
- 将命题的逻辑运算转换成位运算，这样就能在计算机上进行信息处理了，计算机处理；
1.2 命题逻辑的应用
1.2.1 简介
逻辑在数学、计算机科学以及其他许多学科中有重要的应用。
在数学、科学以及自然语言中的语句一般都是不精确的或者模棱两可的。
为了使这些语句精确化，通常要将它们转换成逻辑语言。比如，在软件和硬件的描述中会使用到逻辑，因为在开发前，这些描述必须是精确的。
可使用命题逻辑和逻辑规则来设计计算机电路、构建计算机程序、验证程序的正确性、构建专家系统等。
可使用逻辑来分析许多熟悉的谜题。
已经开发出了基于逻辑规则的软件系统来自动地构建一些类型的证明。
1.2.2 转换英文语句
为什么要将英文语句转换成包含有命题变量和逻辑运算符的复合命题？
- 为了消除模糊
由于英文经常是模糊的，所以为了消除模糊，要将英文转换成复合逻辑语句；
这个过程中可能要基于语句要表达的意思，做许多合理的假设； - 转换是有好处的
分析这些逻辑表达式来判断它们的真值；
操作这些逻辑表达式；
使用推断规则来进行推理；
例1 将语句“你才能从校园访问互联网仅当你是一名计算机专业的学生或者你不是新生”转换成一个复合命题。
解：假设命题变量a表示“你能从校园访问互联网”，命题c表示“你是一名计算机专业的学生”，命题f表示“你是一名新生”，则可使用a->(c or 非f)来表示。
例2 将语句“如果你身高不足4英尺，则你就不能乘坐过山车，除非你超过16岁了”转换成一个复合命题。
解：假设命题q表示“你能乘坐过山车”，命题r表示“你的身高低于4英尺”，命题s表示“你的年龄超过16岁”，则：如果身高不足4英尺且年龄不到16岁，则不能乘坐过山车，即(r and 非s)->非q。
1.2.3 系统规范
将自然语言中的语句转换成逻辑表达式是描述硬件和软件系统的必要部分。
系统和软件工程师从自然语言中提取要求，生成精确的、无歧义的、可当做系统开发基础的规范文档。
系统规范应该是一致的，即系统规范里不应该包含能产生矛盾的有冲突的需求。
当存在不一致的规范时，则没法开发一个满足所有规范的系统。
例3 使用逻辑连接词来表示语句“当文件系统满了时，无法发送自动回复”。
解：假设命题p表示“可发送自动回复”，命题q表示“文件系统是满的”，则有q->非p。
例4 判断以下系统规范是不是一致的：
“诊断消息被存储在缓冲区中”
“诊断消息没有存储在缓冲区中”
“如果诊断消息被存储在缓冲区中，则它就会被重传”
解：
假设命题p表示“诊断消息被存储在缓冲区中”，命题q表示“诊断消息被重传”。
则上述三条规范被描述成p或q、非p、p->q。
要使三条规范都为真，则命题p必为假，因为非p要为真。要使p或q为真，因为p为假，所以q必为真。当p为假，q为真时，p->q为真。
因此，这三条规范是一致的。
例5 如果在例4中加入一条规范：“诊断消息不会被重传”，则整个系统规范还是一致的吗？
解：不一致。
首先，为了要保证所有的规范都是真的，则p为假，q为假。
当p为假，q为假时，有p或q为假，与p或q为真矛盾了。
1.2.4 布尔搜索
什么是布尔搜索？
对大规模信息进行搜索时会大量使用逻辑连接词，比如网页索引等。由于这样的搜索采用了命题逻辑技术，所以称这样的搜索为布尔搜索。
在布尔搜索中，
- 使用连接词AND来匹配同时包含两个搜索词的记录；
- 使用连接词OR来匹配包含其中一个或者同时包含两个的记录；
- 使用NOT来排除一个特定的搜索词；
当使用布尔搜索来查找潜在感兴趣的信息时，需要仔细地设计要使用的逻辑连接词。
例6 问题1：查找有关在New Mexico的大学的相关网页。 请写出所需的逻辑表达式。
解："New Mexico" AND UNIVERSITIES
问题2：查找有关在New Mexico或者Arizona的大学的网页。请写出所需的逻辑表达式。
解：("NEW MEXICO" OR ARIZONA) AND UNIVERSITIES
问题3：查找有关Mexico(而非New Mexico)的大学相关网页。请写出所需的逻辑表达式。
解：Mexico AND UNIVERCITIES NOT NEW
1.2.5 逻辑谜题
什么是逻辑谜题？
能使用逻辑推理来解决的谜题，称为逻辑谜题。
解决逻辑谜题是一种非常好的验证逻辑规则的方式。
执行逻辑推理的计算机程序也经常使用有名的逻辑谜题来展示它的能力。
许多人喜欢求解在期刊、书籍、网络等上公开的逻辑谜题。
例7 宝藏箱子
你从海盗手里救回了国王的女儿，国王给了你一次赢得宝藏的机会。宝藏被藏在3个箱子里的某一个里。没有宝藏的两个箱子都是空的。
要赢，你必须选择一个箱子。
箱子1和箱子2上都刻有消息说“这个箱子是空的”，箱子3上刻的消息说“宝藏在箱子2里”。
从不说谎的王后告诉你：在箱子上刻的消息里只有一个是真的，其余两个都是假的。
请问：选择哪一个箱子你才会赢。
解：
假设命题p1表示“宝藏在箱子1里”，命题p2表示“宝藏在箱子2里”，命题3表示“宝藏在箱子3里”。
则非p1表示刻在箱子1上的消息，非p2表示刻在箱子2上的消息，p2表示刻在箱子3上的消息。
根据王后的提示“3个消息中仅有1个为真，其余为假”，则将王后的提示转换成逻辑表达式：
(消息1为真 and 消息2为假 and 消息3为假) or (消息1为假 and 消息为真 and 消息3为假) or (消息1为假 and 消息2为假 and 消息3为真)
等价于
(非p1 and p2 and 非p2) or (p1 and 非p2 and 非p2) or (p1 and p2 and p2)
等价于
(p1 and 非p2) or (p1 and p2)
等价于
p1 and (p2 or 非p2)
等价于
p1
即，选择箱子1肯定会拿到宝箱。
例8 小岛居民的谜题
在一个小岛上，有两类居民：一类是骑士，一直讲真话；另一类是恶棍，一直说谎话。有一天，你碰到了两个人A和B。如果A说“B是一个骑士”，B说“我们两人是不同类型的居民”，则A和B是什么类型的居民？
解：假设命题p表示A是骑士，命题q表示B是骑士，则非p表示A是恶棍，非q表示B是恶棍。
假设A是骑士，因为骑士一直讲真话，所以B也是骑士，即A和B是同一类型居民。但是，如果B也是骑士，则根据B说的话为真，即A和B是不同类型的居民，出现矛盾。进而得出：A不是骑士，是恶棍。
如果A是恶棍，因为恶棍一直讲谎话，所以B不是骑士，B也是恶棍。
例9 泥巴问题
一个父亲告诉他的两个孩子，一男一女，可以在后院玩耍，不要弄脏自己了。但是，在玩耍期间，两个孩子的额头上都沾上了泥巴。当孩子们不玩了，父亲说“你们中至少有一个人的额头上有泥巴”，然后让孩子们回答问题：“你知道你的额头上是否有泥巴吗？”，请求回答“Yes”或者"No"。假设一个孩子能看到他或者她的兄弟姐妹的额头上是否有泥，但是不能看到自己的额头；假设两个孩子都很诚实，且同时回答每个问题。父亲问两次这个问题。每次问这个问题时，孩子们该如何回答呢？
解：假设命题s表示儿子的额头有泥巴，命题d表示女儿的额头有泥巴。当父亲说“两个孩子中至少有1个的额头有泥巴”时，等价于说命题s or d是真的。
第一次两个孩子都回答NO，因为每个人都看到对方的额头上有泥。
第二次两个孩子都回答Yes。以女儿为例来分析，因为儿子在第一个问题里回答了NO，即儿子的额头上没有泥巴，即s为假。但s or d是真的，则d必须是真的，因为孩子都很诚实，所以女儿第二次必回答Yes。同理，儿子也能得到同样的结论。
1.2.6 逻辑电路
命题逻辑可应用到计算机的硬件设计上，这是由Claude Shennon在1938年的硕士论文中首次提出。
一个逻辑电路接收输入信号(每个输入信号可用一个比特位表示)，产生输出信号
(同样，每个输出信号也可用1个比特位表示)。
复杂的电子电路可由3种基本的电路构成，即与门、或门、非门。
例10 图2中的组合电路的输出信号怎么表示？
解：(p and 非q) or 非r
例11 请画出能产生输出信号(p ∨ ¬r) ∧ (¬p ∨ (q ∨ ¬r)) 的逻辑电路图。
1.3 命题等价性
在数学论证中，很重要的一步是用另一条具有相同真值的语句来替换一条语句。因此，在数学论证的构造中会大量使用能产生与给定复合命题具有相同真值的命题的方法。
什么是复合命题？
复合命题指的是通过对命题变量使用逻辑运算符形成的表达式，比如p ∧ q等。
什么是重言式？
不管组成它的命题的真值是什么，称一个永为真的复合命题为重言式。
什么是矛盾式？
称一个永为假的复合命题为矛盾式。
什么是偶然性？
既不是重言式，也不是矛盾式的复合命题就是偶然式。
重言式和矛盾式在数学推理中非常重要。
例1 仅有一个命题变量组成的重言式和矛盾式
p and 非p是一个矛盾式。
p or 非p是一个重言式。
1.3.2 逻辑等价性
什么是逻辑等价？
在所有可能的情形下，有相同真值的两个复合命题是逻辑等价的。
逻辑等价性常见情形
- 条件语句之间的等价性
- 双条件语句之间的等价性
- 普通复合命题之间的等价性
总结如下3张图：
如果双条件语句p<->q是一个重言式，则复合命题p和q就是逻辑等价的。
两个逻辑等价的复合命题记做
注意：
-
不是一个逻辑连接词或者逻辑运算符；
-
不是一个复合命题，而是一个描述“p<->q是一个重言式”的语句；
问题1：如何判断两个复合命题是等价的？
方法一：使用真值表，仅适用命题变量比较少的情形；
问题2：当命题变量变多时，如何快速有效地确定两个命题的等价性？
1.3.3 使用De Morgan定律
¬(p ∨ q) ≡ ¬p ∧ ¬q 或的非等于非的与
¬(p ∧ q) ≡ ¬p ∨ ¬q 与的非等于非的或
De Morgan定律非常重要，讲述了如何对两个命题的与求非，如何对两个命题的或求非。
例5 使用摩根定律
- “Miguel有一部手机且有一台掌上电脑”的非命题是什么？
解：假设命题p表示“Miguel有一部手机”，命题q表示“Miguel有一台掌上电脑”，则上述语句可表示成p ∧ q 。
根据摩根定律有：¬(p ∧ q) ≡ ¬p ∨ ¬q 。
则原始语句的非命题可表述成：“Miguel一台手机也没有或者一台掌上电脑也没有” - “Heather将去听音乐会或者Steve将去听音乐会”的非命题是什么？
解：假设命题p表示“Heather将去听音乐会”，命题q表示“Steve将去听音乐会”，则原始命题可表示成p ∨ q 。
根据摩根定律有：¬(p ∨ q) ≡ ¬p ∧ ¬q
则原始语句的非命题可表示成“Heather不会去听音乐会且Steve也不会去听音乐会”。
1.3.4 构建新的逻辑等价性
例6 ¬(p → q) ≡ p ∧ ¬q
例7 ¬(p ∨ (¬p ∧ q)) ≡ ¬p ∧ ¬q
例8 (p ∧ q) → (p ∨ q) 是一个重言式。
1.3.5 命题的可满足性
如果存在一组对命题变量的真值赋值，使得复合命题为真，则称该复合命题是可满足的。
如果对命题变量的所有真值赋值，都使得复合命题为假，则称该复合命题是不可满足的。
注意：
一个复合命题是不可满足的，当且仅当对命题变量的所有真值赋值，该复合命题的否命题是真的，当且仅当该复合命题的否命题是一个重言式。
当我们找到一组特定的真值赋值使得复合命题为真时，我们就展示了该复合命题是可满足的。称这样的一组真值赋值为这个特定的可满足问题的一个解。
要证明一个复合命题是不可满足的，我们需要证明对命题变量的所有真值赋值都使得复合命题为假。
如何判断一个命题是否是可满足的？
- 使用真值表
- 对真值进行推理论证
例9 (p ∨ ¬q) ∧ (q ∨ ¬r) ∧ (r ∨ ¬p) 是可满足的，因为当p、q、r有相同的真值时，该复合命题就是真的。
(p ∨ q ∨ r) ∧ (¬p ∨ ¬q ∨ ¬r) 是可满足的，当p、q、r中至少有1个是真的，且至少有1个是假时，该复合命题就是真的。
(p ∨ ¬q) ∧ (q ∨ ¬r) ∧ (r ∨ ¬p) ∧ (p ∨ q ∨ r) ∧ (¬p ∨ ¬q ∨ ¬r) 是不可满足的，因为要使原复合命题为真，就必须保证命题(p ∨ ¬q) ∧ (q ∨ ¬r) ∧ (r ∨ ¬p) 是真的，且(p ∨ q ∨ r) ∧ (¬p ∨ ¬q ∨ ¬r)是真的。要使第一个命题为真，就必须得保证3个命题变量有相同的真值；要使第二个命题为真，就必须保证3个命题变量中至少有1个真，至少有1个为假。这些条件是矛盾的，所以该复合命题是不可满足的。
1.3.6 命题可满足性的应用
在诸多领域中的许多问题都可用命题可满足性的形式来建模，比如机器人、软件测试、人工智能规划、计算机赋值设计、机器视觉、集成电路设计、调度、计算机网络、基因等。
例10 n-皇后问题
n-皇后问题要求：在一个nn的棋盘上放置n个皇后，使得没有一个皇后可攻击另一个皇后。这意味着：不存在两个皇后被放置在同一行上、同一列上、同一个对角线上。
1.3.7 求解命题式可满足性问题
如何求解命题式可满足性问题？
方法一：真值表
方法二：针对特定类型的命题式可满足性问题，使用特定的算法
命题式可满足性问题在研究算法复杂度中扮演者重要角色。
可使用真值表来判断一个复合命题是否是可满足的，或者等价地判断它的否命题是否为重言式。
当命题变量较少时，可以手动来做。
当命题变量变多时，手动来做就不切实际了。比如，当复合命题有20个命题变量时，相应的真值表的行数为。如果还使用真值表方法，则需要一台计算机来帮助判断有20个命题变量的复合命题是否是可满足的。
当对许多应用进行建模时，会出现由成百上千、成千上万、成百万上千万个命题变量组成的可满足性问题。
注意：
- 当有1000个命题变量时，计算机甚至花费数万亿年的时间都不能完成对
个可能的真值组合的逐一检查。
- 不存在计算机程序能在合理的时间内判断一个由如此多的命题变量组成的复合命题是否是可满足的。
不要灰心，
- 已经开发出了求解针对特定类型的可满足性问题的方法，比如Sudoku谜题等。
- 已经开发了许多求解有实际用途的计算机程序。
