离散数学
第一章 逻辑和证明
命题
[TOC]
命题
定义： 命题是一个陈述句（即陈述一个事实的句子），它不是真就是假，但不是两者都是假。
示例 以下都是命题
1、华盛顿特区是美利坚合众国的首都. 真命题
2、多伦多是加拿大的首都。 否命题
3、1 + 1 = 2 真命题
4、2+2=3. 否命题
考虑下面的句子
1、现在几点了？
2、清仔细看这个短片。
3、$x+1=2$
4、$x+y=z$
解析
- 句子1和2不是命题，因为它们不是陈述句。
- 句子3和4不是命题，因为它们既不是真也不是假。
注意，如果我们给变量赋值，第3句和第4句都可以变成一个命题。我们还将在第1.4节中讨论将这些句子转化为命题的其他方法。
在逻辑学中，命题（proposition）是陈述句的一种，它可以被判断为真（true）或假（false）。当我们说一个命题的“否定”（negation）时，我们是指创建一个新的命题，这个新命题的真假性正好与原命题相反。
给定一个命题p，它的否定表示为¬p（有时也用~p表示）。这个否定命题的陈述是“不是p的情况”，或者说“非p”。换句话说，如果p为真，那么¬p就为假；如果p为假，那么¬p就为真。
这里的关键点是理解否定如何影响命题的真假性：
如果p是真命题，那么$¬p$（非p）就是假命题。
如果p是假命题，那么$¬p$（非p）就是真命题。
这种关系确保了逻辑上的一致性和完整性，因为否定操作提供了一种精确的方式来反转命题的真假性。
举个例子，假设命题p是“今天下雨”。那么$¬p$（非p）就是“今天不下雨”。如果今天确实下雨了，那么p为真，而¬p为假。相反，如果今天没有下雨，那么p为假，而¬p为真。
例 1.1.2
找出命题的否定“ Michael 's PC运行Linux ”用简单的英语表达
答：Michael 's PC运行的不是Linux或Michael 's PC没有运行Linux。
例 1.1.3
找出命题的否定“Vandana的智能手机至少有32gb的内存”，用简单的语言表达出来
答：Vandana的智能手机并没有至少32gb的内存
Vandana的智能手机不超过32gb的内存
Vandana的智能手机不足32gb的内存
真值表
| $p$ | $¬p$ |
|---|---|
| T | F |
| F | T |
在逻辑学中，命题（proposition）是可以判断真假的陈述句。对于任何命题p，它都有两种可能的真值（truth values）：真（True）或假（False）。当我们对命题p进行否定（negation）操作时，我们使用符号¬（读作“非”）来表示，得到的新命题¬p的真值与p的真值相反。
具体来说：
如果p为真（True），则¬p为假（False
如果p为假（False），则¬p为真（True）
这个表格说明了否定运算符如何从一个命题构造出一个新的命题，且这个新命题的真值与原命题的真值相反。
接下来，逻辑学中还有其他逻辑运算符（也称为连接词或联结词），它们允许我们从两个或多个现有命题中形成新的命题。这些运算符包括但不限于：
-
合取（Conjunction）：使用符号∧（读作“与”）表示。如果两个命题都为真，则它们的合取为真；否则为假。
-
析取（Disjunction）：使用符号∨（读作“或”）表示。如果两个命题中至少有一个为真，则它们的析取为真；只有当两者都为假时，析取才为假。
-
蕴含（Implication）：使用符号→（读作“如果...则...”或“蕴含”）表示。如果第一个命题为真且第二个命题为假，则第一个命题对第二个命题的蕴含为假；在其他情况下，蕴含为真。
-
双条件（Biconditional）：使用符号↔（读作“当且仅当”）表示。两个命题的双条件为真，当且仅当这两个命题的真值相同（即都为真或都为假）。
| $p$ | $q$ | $p \land q$ | $p \lor q$ | $p \oplus q$ | $p \to q$ |
|---|---|---|---|---|---|
| T | F | F | T | T | F |
| F | T | F | T | T | T |
| T | T | T | T | F | T |
| F | F | F | F | F | T |
例 1.1.4 找出命题“Vandana的智能手机至少有32gb的内存”和命题“ Vandana 's PC运行Linux ”的合取。
解：$p \land q$: Vandana的智能手机至少有32gb的内存且 Vandana 的 PC运行Linux；
例 1.1.5 将陈述“已经学习过微积分或基础计算机科学的学生可以选修这门课程”翻译成使用命题逻辑表示的语句，
其中命题p表示“已经学习过微积分的学生可以选修这门课程”，
命题q表示“已经学习过基础计算机科学的学生可以选修这门课程”。
解：$p \lor q$
定义 4 ： 设p和q为命题。p和q的异或（记作$p \oplus q$，或p XOR q）是一个命题，当且仅当p和q中恰好有一个为真时，该命题为真；否则为假。
例 1.1.5 设p和q分别为命题“一个学生晚餐可以吃沙拉”和“一个学生晚餐可以喝汤”。那么$p \oplus q$，即p和q的异或（exclusive or），表示什么？
解 $p \oplus q$ 表示一个学生晚餐可以吃沙拉或喝汤，但不能同时吃沙拉和喝汤，而没有明确说明不能同时吃两者。因为由异或的定义当且仅当p和q中恰好有一个为真时，该命题为真，否者为假。
例 1.1.6 用命题逻辑表达“我将用我所有的积蓄去欧洲旅行或买一辆电动汽车”，用命题p：“我将用我所有的积蓄去欧洲旅行”和命题q：“我将用我所有的积蓄买一辆电动汽车。”
我们首先注意到这句话中的or必须是一个排他性的or，因为这个学生可以用他或她所有的积蓄去欧洲旅行，或者用所有的积蓄买一辆电动汽车，但不能既去欧洲又买一辆电动汽车。（这很明显，因为两种选择都需要他所有的积蓄。）因此，这个命题可以表示为 **$p \oplus q$**。
1.1.3条件语句
我们将讨论命题可以组合的其他几种重要方式。
定义5 ：设p和q是命,条件语句 $p \to q$是命题“如果p，则q”。当p为真且q为假时，条件语句$p \to q$为假，否则为真。在条件命题$p \to q$中，p被称为假设（或前提或前提），而q被称为结论（或推论）
备注：命题p → q被称为条件命题，因为p → q断言：当条件p成立时，q为真。条件命题也被称为蕴含命题。请注意，当p和q都为真，或者当p为假时（无论q的真值如何），命题p → q都为真
| $p$ | $q$ | $p \to q$ |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
充要条件
充要条件的定义
在逻辑学中，充要条件（sufficient and necessary condition）是指两个命题 $P$ 和 $Q$ 之间的一种特殊关系，满足以下两个条件：
-
充分性：如果 $P$ 为真，则 $Q$ 也必定为真。用逻辑符号表示即： $$ P \rightarrow Q $$ 这意味着 $P$ 是 $Q$ 的充分条件。
-
必要性：如果 $Q$ 为真，则 $P$ 也必定为真。用逻辑符号表示即： $$ Q \rightarrow P $$ 这意味着 $P$ 是 $Q$ 的必要条件。
当且仅当这两个条件同时满足时，我们称 $P$ 是 $Q$ 的充要条件，或者 $Q$ 是 $P$ 的充要条件。用逻辑符号表示这一等价关系为： $$ P \leftrightarrow Q $$
换句话说，充要条件是指两个命题在逻辑上相互蕴含，即一个命题的真值完全决定了另一个命题的真值。
在逻辑学中，"充要条件"描述了两个命题之间的等价关系。
-
充分条件：如果命题 $P$ 是命题 $Q$ 的充分条件，那么当 $P$ 为真时，$Q$ 必定为真。用逻辑符号表示即： $$ [ P \rightarrow Q ]$$
-
必要条件：如果命题 $P$ 是命题 $Q$ 的必要条件，那么当 $Q$ 为真时，$P$ 必定为真。用逻辑符号表示即： $$[ Q \rightarrow P \quad \text{(或者等价地表示为 } \neg P \rightarrow \neg Q \text{)} ]$$
-
充要条件：如果命题 $P$ 是命题 $Q$ 的充要条件，那么 $P$ 既是 $Q$ 的充分条件也是必要条件。即当 $P$ 为真时，$Q$ 必定为真；当 $Q$ 为真时，$P$ 也必定为真。用逻辑符号表示即： $$ P \leftrightarrow Q $$
实例分析
-
充分条件实例：如果一个人是大学生（$P$），那么他一定接受过高等教育（$Q$）。这里，“是大学生”是“接受过高等教育”的充分条件。 $$ \text{大学生} \rightarrow \text{接受过高等教育}$$
-
必要条件实例：如果一个人想成为医生（$Q$），那么他必须接受医学教育（$P$）。这里，“接受医学教育”是“成为医生”的必要条件。 $$ \text{成为医生} \rightarrow \text{接受医学教育} \quad \text{(或者 } \neg \text{接受医学教育} \rightarrow \neg \text{成为医生)} $$
-
充要条件实例：当且仅当一个数（$P$）是正整数（$Q$）时，它才能被正整数整除且余数为零（注意：这里的表述有局限性，更严谨的表述应限定在非零自然数范围内）。 $$ \text{是正整数} \leftrightarrow \text{能被正整数整除且余数为零} $$
由于条件语句在数学推理中起着至关重要的作用，因此使用了各种术语来表示p→q。您将遇到大多数（如果不是全部的话）表示该条件语句的方法：
-
如果 p，则 q：
$p \rightarrow q $（p 蕴含 q） -
p 当且仅当 q：
$ p \leftrightarrow q $
（p 等价于 q，或 p 仅在 q 时成立，q 也仅在 p 时成立） -
p 是 q 的充分条件：
$ p \rightarrow q $ （也可以表述为“q 的一个充分条件是 p”） -
q 每当 p：
$ p \rightarrow q $
（如果 p 成立，则 q 一定成立，即 p 蕴含 q） -
q 在 p 时：
$ p \rightarrow q $
（这同样可以解释为 p 蕴含 q，即当 p 成立时，q 成立） -
q 是 p 的必要条件：
$ \neg q \rightarrow \neg p $
（或者等价地，$ p \rightarrow q $，但这里强调的是从 q 的必要性角度来看）- 注意：直接表述为“q 是 p 的必要条件”在离散数学中通常不直接对应一个单一的逻辑表达式，因为“必要条件”意味着如果没有 q，则一定没有 p。但逻辑上更常用的是其逆否命题的形式，即如果非 p，则非 q（$ \neg p \rightarrow \neg q $），或者等价地表述为 p 蕴含 q。
-
p 的一个必要条件是 q：
$ \neg q \rightarrow \neg p $
（或者理解为，如果 q 不成立，则 p 一定不成立） -
q 除非非 p：
$ p \vee q $
（即 p 或 q 至少有一个成立，或者说，除非 p 不成立（¬p），否则 q 一定成立） -
q 在 p 的条件下：
$ p \rightarrow q $
（这同样解释为 p 蕴含 q） -
q 提供 p（这个表述不太标准，但如果理解为“q 是 p 成立的一个情况”或“在 q 的情况下 p 成立”，可以近似为）：
$ q \rightarrow p $
（即如果 q 成立，则 p 一定成立）
理解条件语句真值的一个有用方法是考虑义务或契约。例如，许多政治家在竞选公职时所作的承诺是
“如果我当选，我会降低税收。”
如果这位政治家当选，选民会期望这位政治家降低税收。此外，如果政治家没有当选，那么选民就不会期望这个人会降低税收，尽管这个人可能有足够的影响力来促使当权者降低税收。
只有当政治家当选但没有降低税收时，选民才会说政治家违背了竞选承诺。最后一个场景对应于p→q中p为真而q为假的情况。
类似地，考虑一个教授可能会说的话：
“如果你期末考100%，那你就得a。”
如果你在期末考试中拿到100%，那么你可能会得到A。如果你没有得到100%，你可能会得到A，也可能不会得到A，这取决于其他因素。然而，如果你得到100%，但是教授没有给你A，你会觉得被骗了。
备注：由于表达p暗示q的一些不同方式可能令人困惑，我们将提供一些额外的指导。要记住“ p only if q ”和“ if p, then q ”表达的是一样的东西，注意“ p only if q ”说的是当q不为真时p不可能为真。也就是说，如果p为真，但q为假，则陈述为假。当p为假时，q可能为真也可能为假，因为该陈述没有说明q的真值。
例如，假设你的教授告诉你
“只有期末成绩达到90%以上，这门课才能得A。”
然后，如果你在这门课上得了A，那么你就知道你在期末考试中的分数至少是90%。如果你没有得到A，你可能在期末考试中得到至少90%的分数，也可能没有。注意不要用“q only if p”来表示p→q，因为这是不正确的。这个词“only”在这里起着重要的作用。
当p和q具有不同的真值时，p→q是不同的。要明白为什么“q是p的必要条件”等价于“如果p，则q”，请注意“q是p的必要条件”意味着除非q为真，否则p不可能为真，或者如果q为假，则p为假。这就等于说如果p为真，那么q也为真。要明白为什么“p对q是充分的”等价于“如果p，那么q”，注意“p对q是充分的”意味着如果p为真，那么q也必须为真。如果p为真，则q也为真。
q 除非 ¬p 读法：除非p为假（即非p为真）
要记住“ q除非$\neg p$”（除非p为假） 表达的条件语句与“如果p，则q ”表达的条件语句相同，请注意“ q除非¬p ”意味着如果¬p为假，则q必须为真。也就是说，当p为真但q为假时，命题“ q除非$\neg p$ ”为假，否则命题为真。因此,“ q除非$\neg p$ ”和p→q总是有相同的真值。
例 1.1.7 设p代表“Maria学习离散数学”，q代表“Maria会找到一份好工作”。用英语表达语句p→q。
解 $p \to q$ 表示 如果p 则 q。 那么可表示为“如果Maria学习离散数学，那么就会找到一份好工作。”
这里，“如果...那么...”是条件语句的标准形式，其中“如果”后面跟着的是前提（p），“那么”后面跟着的是结论（q）。条件语句p → q的含义是：当p为真时，q也必然为真。但需要注意的是，这并不意味着当q为真时，p也一定为真；也就是说，这个条件语句并不逆向成立。
在英语中还有很多其他表达这个条件句的方法。其中最自然的是
“玛丽亚学习离散数学后会找到一份好工作。”
“玛丽亚要想找到一份好工作，学习离散数学就足够了。”,
“玛利亚会找到一份好工作，除非她不学习离散数学。”
“除非Maria不学习离散数学，否则她会找到一份好工作。”
形式化条件命题的特性说明
需特别注意：我们在数理逻辑中定义的蕴含式 $p \to q$,其语义范畴显著宽泛于自然语言中的条件句。例如：
“例1.1.7所述条件命题
日常陈述"若天晴，则我们去海滩"。”
在自然语言中，这类陈述通常隐含着前件与后件之间的语义关联。然而在离散数学框架下，蕴含式的真值仅由命题真值表决定，与其实际语义关联性无关。。
形式化验证：
- 当且仅当"Maria修习离散数学但未获理想职位"时，第一个蕴含式为假
- 当且仅当"实际天晴但我们未去海滩"时，第二个陈述为假
关键差异
数理逻辑蕴含式⊃自然语言条件句
在真值函数语义下，$p \to q$ 的有效性独立于：
- p与q的因果关系
- 命题间的现实相关性
- 非逻辑语境要素
另一方面，声明
“如果Juan有智能手机，那么2 + 3 = 5”
从条件语句的定义来看是真的，因为它的结论是真的。（此时，假设的真值并不重要。）
条件语句 “如果胡安有智能手机，那么2 + 3 = 6” 是正确的, 如果Juan没有智能手机，即使2 + 3 = 6是假的，我们不会在自然语言中使用最后这两个条件语句（或许讽刺时除外），因为这两个语句中的前提与结论之间没有任何关系。在数学推理中，我们考虑的条件语句类型比英语中使用的更为广泛。数学中的条件语句概念独立于前提与结论之间的因果关系。我们对条件语句的定义明确了其真值；它不是基于英语用法的。命题语言是一种人工语言；我们只是将英语的用法与之平行，使之易于使用和记忆。
许多编程语言中使用的if-then结构与逻辑中使用的结构不同。大多数编程语言都包含类似if p then S这样的语句，其中p是一个命题，S是一个程序段（要执行的一条或多条语句）。（虽然这看起来像是一个条件语句，但S不是一个命题，而是一组可执行指令。）当程序的执行遇到这样的语句时，如果p为真则执行S，但如果p为假则不执行S，如
例1.1.8 如果2 + 2 = 4，那么x:= x + 1，语句后变量x的值是多少？如果x = 0之前遇到这个语句？
解 2+2=4 为true，所以 x:= x + 1 = 0 + 1 = 1
我们可以从一个条件语句 p→q 出发，形成一些新的条件语句。特别是，有三种相关的条件语句出现得非常频繁，以至于它们有了特殊的名称。命题 q→p 被称为 p→q 的逆命题。p→q 的逆否命题是 ¬q→¬p。命题 ¬p→¬q 被称为 p→q 的否命题。我们将看到，在这三个由 p→q 形成的条件语句中，只有逆否命题总是与 p→q 具有相同的真值。
当两个复合命题无论其命题变量的真假如何，总是具有相同的真假值时，我们称它们为等价命题。因此，一个条件命题与其逆否命题是等价的。读者可以验证，一个条件命题的逆命题和否命题也是等价的，但它们都不等同于原条件命题。（我们将在1.3节中研究等价命题。）请注意，最常见的逻辑错误之一就是认为一个条件命题的逆命题或否命题与该条件命题是等价的。
例 1.1.8 找到条件命题“只要下雨，主队就会赢”的逆否命题、逆命题和否命题。
解：逆命题：如果条件命题是“如果P，则Q”，那么它的逆命题是“如果Q，则P”。
- 如果主队会赢，那么就会下雨
逆否命题：如果条件命题是“如果P，则Q”，那么它的逆否命题是“如果非Q，则非P”。
- 只要不下雨，主队就不回应
否命题：如果条件命题是“如果P，则Q”，那么它的否命题是“如果P，则非Q”。然而，更常见的否命题形式是针对整个条件命题的否定，即“非（如果P，则Q）”，这等价于“P且非Q”。
-
只要下雨，主队就不会赢或
下雨但主队没有赢
定义6：设p和q是命题。双条件语句$p \leftrightarrow q$是命题“ p当且仅当q ”。当p和q有相同的真值时$p \leftrightarrow q$为真，否则为假。双条件命题也被称为双向蕴含。
表六
| $p$ | $q$ | $p \leftrightarrow q $ |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
表6显示了p↔q的真值表。注意，当条件语句p→q和q→p都为真时，语句p↔q为真，否则为假。这就是为什么我们使用“当且仅当”来表达这个逻辑连接词，以及为什么它是通过组合符号→和←来象征性地书写的。还有一些其它常见的表示p↔q的方法：
-
“p是q的充要条件”。
-
“如果p则q，反之亦然”。这里的“反之亦然”表示“如果q则p”也成立，即p和q之间存在双向蕴含关系。
-
“p当且仅当q”。这里的“iff”是“if and only if”的缩写，表示p和q之间的等价关系。
-
“p恰好在q时成立”。这个表述强调了p和q在相同条件下同时成立的关系，即p和q具有相同的真值。虽然这个翻译在离散数学的严格术语中不如前几个常见，但它传达了p和q之间紧密关联的概念。在更正式的场合，可能会更倾向于使用“p当且仅当q”这样的表述。
-
双条件语句p↔q的方法使用表示“当且仅当”的缩写“ iff ”。注意p↔q与（p→q）∧（q→p）有完全相同的真值。
例 1.1.9 设p表示“你可以乘坐这趟航班”，设q表示“你买张票”。则p↔q是语句
解：只要你买张票，你就可以乘坐这趟航班。或 你可以乘坐这趟航班但是你要买张票。
该命题在以下情况下为真：p和q要么都为真，要么都为假。也就是说，如果你买了机票并且能乘坐飞机，或者你没买机票并且不能乘坐飞机，那么这个命题就是真的。当p和q的真值相反时，该命题为假。也就是说，如果你没买机票，但你却能乘坐飞机（比如你获得了免费旅行的机会），或者你买了机票却不能乘坐飞机（比如航空公司将你拒载），那么这个命题就是假的。
你应该意识到，在自然语言中，双条件句（biconditionals）并不总是明确表达的。特别是，双条件句中使用的“当且仅当”（if and only if）结构在日常语言中很少使用。相反，双条件句通常使用“如果，那么”（if, then）或“只有”（only if）结构来表达，而“当且仅当”的另一部分则是隐含的。也就是说，逆命题是隐含的，但没有明确陈述。例如，考虑这个英语语句
-
“如果你吃完饭，你就可以吃甜点了。”