第一章，第三部分：证明
汇总
有效的论据和推理规则
证明方法
证明策略
有效的论据和推理规则
小节汇总
有效论证
命题逻辑的推理规则
使用推理规则构建参数
量化陈述的推理规则
建立量化陈述的论据
有效论证
数学证明是确定数学陈述真实性的有效论据。
通过论证，我们指的是一系列陈述最后得出结论。
有效的，我们的意思是论证的结论或最终陈述必须遵循论证的前述陈述或前提的真实性。
苏格拉底的例子
我们有两个前提
“所有人都是凡人”
“苏格拉底是人”
我们得出结论：
“苏格拉底是凡人”
我们如何通过前提来得到结论呢？
论证
我们可以将谓词逻辑中的前提（在行之上）和结论（在行之下）表示为一个参数：
我们很快就会看到这是一个有效的论点。
有效论证
我们将展示如何在两个阶段构建有效的参数; 首先是命题逻辑，然后是谓词逻辑。 推理规则是构造有效论证的基本构件。
命题逻辑
推理规则
谓词逻辑
命题逻辑的推理规则以及处理变量和量词的附加推理规则。
命题逻辑中的论证
命题逻辑中的一个论点是一系列命题。 除最终命题之外的所有命题都称为前提。 最后的陈述是结论。
如果前提表面结论，则该论证是有效的。 论证形式是一种有效的论证，无论什么命题被代入其命题变量。
如果前提是p1，p2，...，pn，则结论为q (p1∧p2∧…∧pn)→q是一个 tautology（同义反复）.
推理规则是所有参数简单参数形式，将用于构造更复杂的参数形式。
命题逻辑的推理规则：Modus Ponens
对应的 Tautology:
(p ∧ (p →q)) → q
例：
让p成为“正在下雪”。
设q为“我将研究离散数学”。
“如果下雪，我会学习离散数学。”
“下雪了。”
“因此，我将研究离散数学。”
Modus Tollens
对应的 Tautology:
(¬q∧(p →q))→¬p
例：
让p成为“正在下雪”。
设q为“我将研究离散数学”。
“如果下雪，我会学习离散数学。”
“我不会研究离散数学。”
“因此，它不会下雪。”
假设的三段论
对应的 Tautology:
((p →q) ∧ (q→r))→(p→ r)
例：
让p成为“下雪”。
设q为“我将研究离散数学”。
让我成为“我会得到一个A.”
“如果下雪，那么我将学习离散数学。”
“如果我学习离散数学，我会得到一个A.”
“因此，如果下雪，我会得到A.”
析取三段论
Corresponding Tautology:
(¬p∧(p ∨q))→q
例：
设p为“我将研究离散数学”。
设q为“我将学习英语文学”。
“我将学习离散数学，或者我将学习英语文学。”
“我不会研究离散数学。”
“因此，我将学习英语文学。”
补充
Corresponding Tautology:
p →(p ∨q)
例：
设p为“我将研究离散数学”。
让q为“我将访问拉斯维加斯”。
“我将研究离散数学。”
“因此，我将研究离散数学，否则我将访问拉斯维加斯
简化
(p∧q)
p
对应的 Tautology:
(p∧q) →p
例子：
设p为“我将研究离散数学”。
设q为“我将学习英语文学”。
“我将学习离散数学和英语文学”
“因此，我将研究离散数学。”
连词
对应的 Tautology:
((p) ∧ (q)) →(p ∧ q)
例：
设p为“我将研究离散数学”。
设q为“我将学习英语文学”。
“我将研究离散数学。”
“我会学习英语文学。”
“因此，我将学习离散数学，我将学习英语文学。”
解析度
解析度在AI中起着重要作用，并在Prolog中使用。
对应的 Tautology:
((¬p ∨ r ) ∧ (p ∨ q)) →(q ∨ r)
例：
设p为“我将研究离散数学”。
设r为“我将学习英国文学”。
设q为“我将研究数据库”。
“我不会学习离散数学，也不会学习英语文学。”
“我将学习离散数学，或者我将研究数据库。”
“因此，我将学习数据库，或者我将学习英语文学。”
使用推理规则构建有效参数
有效参数是一系列语句。 每个陈述都是前提，或者遵循推理规则的先前陈述。 最后一个陈述叫做结论。
有效参数采用以下形式：
有效参数
例1：来自单一命题
证明q是一个结论。
解决方案：
例2：
有了这些假设：
“今天下午不是晴天，比昨天还要冷。”
“只有天气晴朗，我们才会去游泳。”
“如果我们不去游泳，那么我们将乘独木舟旅行。”
“如果我们乘独木舟旅行，那么我们将在日落之前到家。”
使用推理规则，为结论构造一个有效的参数：
“我们将在日落之前回家。”
解：
选择命题变量：
p：“今天下午天气晴朗。”
q：“它比昨天更冷。”
r：“我们会去游泳。”
s：“我们将乘独木舟旅行。”
t：“我们将在日落之前回家。”
翻译成命题逻辑：
构造有效参数
处理量化陈述
量化语句的有效参数是一系列语句。 每个陈述都是前提或前面的陈述规则，包括：
命题逻辑的推理规则
量化陈述的推理规则
在接下来的几张幻灯片中介绍了量化语句的推理规则。
通用实例化（UI）
例：
我们的域包括所有狗，Fido是一只狗。
“所有的狗都可爱。”
“因此，菲多是可爱的。”
普遍推广（UG）
经常在数学证明中隐式使用。
存在实例化（EI）
例：
“有人在课程中获得了A.”
“让我们叫她a，我们说a得到一个A”
存在泛化（EG）
例：
“米歇尔在课堂上得到了A。”
“因此，有人在课堂上得到了A。”
使用推理规则
示例1：使用推理规则，构造一个有效的参数来显示
“约翰史密斯有两条腿”
是前提的结果：
“每个人都有两条腿。”“约翰史密斯是个男人。”
解：让M（x）表示“x是人”，L（x）“x有两条腿”，让John Smith成为域的成员。
有效参数：
示例2：使用推理规则构造一个显示结论的有效参数
“通过第一次考试的人还没有读过这本书。”
从假定开始
“这堂课的学生还没读过这本书。”
“这堂课的每个人都通过了第一次考试。”
解：让C（x）表示“x在这个类中”，B（x）表示“x已经读过这本书”，P（x）表示“x通过了第一次考试”。
首先我们翻译前提和结论成为象征形式。
有效参数：
回到苏格拉底的例子
有效参数：
Universal Modus Ponens将通用实例化和模态推理结合为一个规则。
这条规则可以在苏格拉底的例子中使用。
证明简介
小节汇总
数学证明
定理的形式
直接证明
间接证明
对立面的证明
矛盾证明
数学证明
证明是确定陈述真实性的有效论据。
在数学，CS和其他学科中，通常使用通常较短的非正式证明。
通常在一个步骤中使用一个以上的推理规则。
可以跳过步骤。
使用的推理规则没有明确说明。
更容易理解和向人们解释。
但是引入错误也更容易。
证明有许多实际应用：
验证计算机程序是否正确
确定操作系统是安全的
使计划能够在人工智能中做出推论
表明系统规范是一致的
定义
定理是一个可以使用以下方式显示为真的陈述：
定义
其他定理
公理（声明为真）
推理规则
引理是一个“帮助定理”或证明一个定理所需的结果。
推论是直接来自定理的结果。
不太重要的定理有时被称为命题。
猜想是一种被认为是真实的陈述。 一旦找到猜想的证明，它就成了一个定理。 结果可能是假的。
定理的形式
许多定理断言属性适用于域中的所有元素，例如整数，实数或我们将在本课程中学习的一些离散结构。
通常，标准数学惯例省略了通用量词（精确定理陈述所需）。
例如，声明：
“如果x> y，其中x和y是正实数，那么x^2> y^2”
真正意思
“对于所有正实数x和y，如果x> y，则x^2> y^2。”
证明定理
许多定理都有以下形式：
为了证明它们，我们证明了c是域的任意元素，
通过普遍概括，原始公式的真实性如下。
所以，我们必须证明某种形式：
证明条件语句：p→q
琐碎的证据：如果我们知道q是真的那么
p→q也是如此。
“如果下雨那么1 = 1。”
真实的证据：如果我们知道p是假的那么
p→q也是如此。
“如果我既富裕又贫穷，那么2 + 2 = 5。”
[尽管这些例子看起来很愚蠢，但通常在数学归纳中使用琐碎和空洞的证据，我们将在第5章中看到]]
偶数和奇数整数
定义：如果存在整数k使得n = 2k，整数n是偶数，并且如果存在整数k使得n = 2k + 1，则n是奇数.注意每个整数是偶数或奇数并且没有整数是偶数和奇数。
我们将需要关于一些示例证明中的整数的基本事实。 我们将在第4章中了解有关整数的更多信息。
证明条件语句：p→q
直接证明：假设p为真。 使用推理，公理和逻辑等价的规则来表明q也必须是真的。
示例：直接证明定理“如果n是奇数，则n2是奇数”。
解答：假设n是奇数。 然后对于整数k，n = 2k + 1。 平方的两边，我们得到：
n2 =（2k + 1）2 = 4k2 + 4k +1 = 2（2k2 + 2k）+ 1 = 2r + 1，
其中r = 2k2 + 2k，一个整数。
我们已经证明，如果n是奇整数，则n2是奇整数。
定义：如果存在整数p和q，其中q≠0，使得r = p / q，则实数r是有理数。
示例：证明两个有理数的和是有理数
解答：假设r和s是两个有理数。 那么必须有整数p，q和t，u这样
示例：证明如果n是整数且3n + 2是奇数，则n是奇数。
解决方案：假设n是偶数。 因此，对于某些整数k，n = 2k。 从而
3n + 2 = 3（2k）+ 2 = 6k + 2 = 2（3k + 1）= 2j，j = 3k +1
因此3n + 2是偶数。 由于我们已经显示了¬q→¬p，所以p→q也必须保持。 如果n是整数并且3n + 2是奇数（不是偶数），则n是奇数（不是偶数）。
示例：证明对于整数n，如果n^2为奇数，则n为奇数。
解决方案：使用对位证明。 假设n是偶数（即，不是奇数）。 因此，存在整数k，使得n = 2k。因此，
n^2 = 4k^2 = 2（2k^2）
并且n2是偶数（即，不是奇数）。
我们已经证明，如果n是偶数，那么n2是偶数。 因此，通过对比，对于整数n，如果n2是奇数，则n是奇数。
矛盾证明:( AKA reductio ad absurdum）。
为了证明p，假设¬p并导出矛盾，例如p∧¬p。 （间接证明形式）。 由于我们已经证明¬p→F是正确的，因此相反的T→p也成立。
示例：证明如果您从日历中选择22天，则至少4天必然是一周中的同一天。
解决方案：假设22天中不超过3天是在一周的同一天。 因为一周有7天，我们只能选择21天。 这与我们选择22天的假设相矛盾。
因此总和是有理数
相反的证明：假设¬q和显示¬p也是如此。 这有时被称为间接证明方法。 如果我们给出¬q→¬p的直接证明，那么我们有p→q的证明。
矛盾证明
第4章的预览。
示例：使用矛盾证明来证明√2是无理数。
解决方案：假设√2是有理数的。 然后存在整数a和b，其中√2= a / b，其中b≠0且a和b没有共同因子（见第4章）。 然后
因此a^2必须是偶数。 如果a^2是偶数则a必须是偶数（练习）。 由于a是偶数，对于某个整数c，a = 2c。 从而，
因此b^2是偶数。 再一次，b必须是偶数。
但是这样2必然可将a和b除尽。 这与我们假设a和b没有公因素相矛盾。 我们已经通过矛盾证明我们的初始假设必须是假的，因此√2是无理数。
作为双条件陈述的定理
为了证明作为双条件陈述的定理，即形式为p↔q的陈述，我们证明p→q和q→p都是真的。
示例：证明定理：“如果n是整数，则当且仅当n^2为奇数时，n才为奇数。”
解答：我们已经显示（先前的幻灯片）p→q和q→p。 因此，我们可以得出结论。
有时，iff用作“if and only if”的缩写，如
“如果n是整数，那么n是奇数，如果n2是奇数。”
这有什么问题？
“证明”1 = 2
解决方案：步骤5.a-b = 0的前提和除以0是未定义的。
展望未来
如果直接的证明方法不起作用：
我们可能需要通过对立巧妙地使用证明。
或者是矛盾的证明。
在下一节中，我们将看到当简单方法不起作用时可以使用的策略。
在第5章中，我们将看到数学归纳和相关技术。
在第6章中，我们将看到组合证明
证明方法和策略
小节汇总
案件证明
存在证明
建设性
Nonconstructive
通过反例进行反证
不存在证明
唯一性证明
证明策略
证明普遍量化的断言
打开问题
案件证明
要证明形式的条件陈述：
使用重言式
每个的含义都是一个案例。
示例：如果n是n≤4的正整数，则证明（n + 1）3≥3n。
解：
疲惫证明。 验证不等式（n + 1）3≥3n
当n = 1,2,3和4时。
n = 1，（n + 1）3 = 23 = 8且3n = 31 = 3;
n = 2，（n + 1）3 = 33 = 27且3n = 32 = 9;
n = 3，（n + 1）3 = 43 = 64且3n = 33 = 27; 和
n = 4，（n + 1）3 = 53 = 125且3n = 34 = 81。
在这四种情况中，我们看到（n + 1）3≥3n。
存在证明
形式定理的证明。
建设性存在证明：
找到c的显式值，P（c）为真。
然后是存在主义概括（EG）。
示例：显示有一个正整数，可以用两种不同的方式写为正整数的多维数据集的总和：
证明：1729就是这样的数字
1729 = 103 + 93 = 123 + 13
非建构性存在证明
在非建设性存在证明中，我们假设不存在使得P（c）成立并且导出矛盾的c。
示例：显示存在无理数x和y，使得x^y是有理数。
证明：我们知道√2是无理数。 考虑数字√2^√2。 如果它是有理数，我们有两个无理数x和y与x^y有理数，即x =√2和y =√2。 但如果√2^√2是无理数，那么我们可以让x =√2√2和y =√2使得x^y =（√2^√2）^√2=√2^（√2√2）=√2^2=2。
反例
回想一下。
为了确定这是真的（或是假的），找到c使得¬P（c）为真或P（c）为假。
在这种情况下，c被称为断言的反例。
示例：“每个正整数是3个整数的平方和。”整数7是一个反例。 因此声称是错误的。
唯一性证明
一些定理证明了具有特定属性的唯一元素的存在，∃！x P（x）。 唯一性证明的两个部分是
存在：我们显示具有属性的元素x存在。
唯一性：我们证明如果y≠x，则y不具有该属性。
示例：证明如果a和b是实数且≠0，则存在唯一的实数r，使得ar + b = 0。
解：
存在性：实数r = -b / a是ar + b = 0的解，因为a（-b / a）+ b = -b + b = 0。
唯一性：假设s是实数，使得as+ b = 0.那么ar + b = as + b，其中r = -b / a。 从两侧减去b并除以r表示r = s。
证明p→q的证明策略
选择一种方法。
首先尝试直接的证明方法。
如果这不起作用，尝试间接方法（例如，尝试证明对立面）。
无论您尝试哪种方法，请选择策略。
首先尝试推理。 从公理和已知定理开始，构建一系列结论中的步骤。 从p开始并证明q，或以¬q开始并证明¬p。
如果这不起作用，请尝试后退推理。 当试图证明q时，找到一个我们可以用属性p→q证明的语句p。
后向推理
示例：给定两个正实数x和y，它们的算术平均值为（x + y）/ 2，它们的几何平均值为√xy。当我们比较不同正实数对的算术和几何平均值时，我们发现算术平均值总是大于几何平均值。
解：构造一系列等价不等式。 等价的不等式是
（x + y）/ 2>√xy
（x + y）2/4> xy
（x + y）2> 4xy
x2 + 2xy + y2> 4xy
x2 - 2xy + y2> 0
（x - y）2> 0
因为当x≠y时（x-y）2> 0，所以最终的不等式为真。 因为所有这些不等式都是等价的，所以当x = y时，它遵循（x + y）/ 2>√xy。
颠倒使用forward构建证明的步骤
推理。
其他证明方法
稍后我们将看到许多其他证明方法：
数学归纳，这是证明形式为∀nP（n）的语句的有用方法，其中域由所有正整数组成。
结构归纳，可用于证明关于递归定义集的这种结果。
Cantor对角化用于证明无限集大小的结果。
组合证明使用计数参数。
