The Foundations: Logic and Proofs
Chapter 1, Part III: 证明
大连东软信息学院/大数据科学系
Copyright By PowCoder代写加微信 powcoder
Section 1.6
若甲是盗窃犯，则作案时间不能发生在午夜前；
若乙的证词成立，则午夜时室内灯光未灭；
若乙的证词不成立，则作案时间发生在午夜前；
午夜时室内灯光灭了。
“所有人都是凡人。”
“苏格拉底是凡人。”
如何从前提得出结论?
以命题逻辑的方式表示前提(线上) 和结论 (线下) 表示论证:
这是一个有效的论证.
我们将展示如何构建有效的参数在两个阶段：命题逻辑和谓词逻辑。
在构建有效性论证的过程中，推理规则是非常重要的。
含有量词的命题推理规则
命题逻辑中的论证是一命题序列，前面的所有语句称为前提。 最后一条语句为结论。
论证是有效的，如果结论是由前提真实推出的。
论证形式是 用命题变量代替命题的论证。
如果前提是p1 ,p2, …,pn，结论是q，那么
(p1∧ p2 ∧ … ∧ pn ) → q是重言式
推理规则是一些相对简单的论证形式，将用于构造更复杂的论证形式。
证明命题逻辑中论证有效性——证明其论证形式是有效的
命题逻辑推理规则:假言推理
令 p 为 “天在下雪.”
q 为 “我将学习离散数学.”
“如果天在下雪,那么我将学习离散数学。”
“所以 , 我将学习离散数学。”
(p ∧ (p →q)) → q
令 p 为 “天在下雪.”
q 为 “我将学习离散数学.”
“如果天在下雪,那么我将学习离散数学。”
“我将不学离散数学”
“所以 , 天没有下雪.”
(¬q∧(p →q))→¬p
令 p 为 “天在下雪.”
q 为 “我将学习离散数学.”
r 为 “我将得到A.”
“如果天在下雪,那么我将学习离散数学。”
“如果我学习离散数学,那么我将得到A 。”
“所以 ,如果天在下雪,那么我将得到A .”
((p →q) ∧ (q→r))→(p→ r)
令 p 为 “我学习离散数学.”
q 为 “我学习英国文学.”
“我学习离散数学或者英国文学.”
“我不学习离散数学.”
“所以 , 我学习英国文学.”
(¬p∧(p ∨q))→q
令 p 为 “我将学习离散数学.”
q 为 “我将访问拉斯维加斯.”
“我学习离散数学.”
“所以,我将学习离散数学或者访问拉斯维加斯.”
令 p 为 “我将学习离散数学.”
q 为 “我将学习英国文学.”
“我将学习离散数学和英国文学”
“所以，我将学习离散数学.”
令 p 为 “我将学习离散数学.”
q 为 “我将学习英国文学.”
“我将学习离散数学.”
“我将学习英国文学.”
“所以，我将学习离散数学和英国文学.”
((p) ∧ (q)) →(p ∧ q)
令 p 为 “我将学习离散数学.”
q 为 “我将学习英国文学.”
r 为“我将学习数据库.”
“我将不学习离散数学或者我将学习英国文学.”
“我将学习离散数学或者我将学习数据库.”
“所以，我将学习数据库或者英国文学.”
((¬p ∨ r ) ∧ (p ∨ q)) →(q ∨ r)
在下列的每个论证里使用了什么推理规则？
Alice主修数学。因此，Alice主修数学或计算机科学。
Jerry主修数学和计算机科学。因此，Jerry主修数学。
如果今天下雨，则游泳池将关闭。今天下雨。因此，游泳池关闭。
如果今天下雪，则大学将关闭。今天大学没有关闭。因此，今天没有下雪。
如果我去游泳，则我会在太阳下停留过久。如果我在太阳下停留过久，则我会晒黑。因此，如果我去有用，则我会晒黑。
使用推理规则建立有效论证
有效的论证采用以下形式:
步骤理由
1. 前提引入
2.化简律，用（1）
3. 化简律，用（1）
4.假言推理，用（2）和（3）
“今天下午不是晴天并且今天比昨天冷.”
“只有今天下午是晴天，我们才去游泳.”
“如果我们不去游泳，则我们将乘独木舟游览.”
“如果我们乘独木舟游览，则我们将在黄昏前回家.”
使用推理规则，为结论构建一个有效的论证:
“我们将在黄昏前回家.”
p : “今天下午是晴天.” q: “今天比昨天冷.”
r: “我们将去游泳.” s: “我们将乘独木舟游览.”
t : “我们将在黄昏前回家.”
3.构建有效论证
步骤 理由
1.前提引入
2.化简律，由（1）
3. 前提引入
4. 拒取式，由（2）和（3）
5. 前提引入
6.假言推理，由（4）和（5）
7.前提引入
8.假言推理，由（6）和（7）
Note that a truth table would have 32 rows since we have 5 propositional variables.
前提：p→¬q,¬r⋁q, r∧¬s
如果小张守第一垒并且小李向B队投球，则A队取胜；或者A队未取胜，或者A队成为联赛第一名；A队没有成为联赛的第一名；小张守第一垒。因此，小李没向B队投球。
对下列每组前提，用什么样的推理规则，能得出什么结论？
如果我某天休假，则那天下雨或下雪。我在周二休假或在周四休假。周二出太阳。周四未下雪。
我或者聪明或者幸运。我不幸运。如果我幸运，则我将赢得大奖。
我们的领域包括所有的狗，Fido是一只狗。
“所有的狗都是可爱的.”
“所以, Fido是可爱的”
在数学证明中经常含蓄地使用
“有人在课程中得到了A.”
“称呼他为 a ，a得到了A”
“米歇尔在班上得了A.”
“所以,有人在班上得了A.”
例 1: 使用推理规则, 构建一个有效的论证
“约翰·史密斯有两条腿”是结论
“每个人都有两条腿。” “约翰·史密斯是人。”是前提
解: 令 M(x) 为“x 是人” ，L(x) “ x 有两条腿” ，其中约翰·史密斯是域中的一员。
前提：,结论：
论证: 步骤 理由
1.前提引入
2.全称实例，用（1）
3. 前提引入
4.假言推理，用（2）和（3）
“通过第一次考试的某个人没有读过这本书.”
前提：“班上有个学生没有读过这本书.”
“这个班上的每个人都通过了第一次考试.”
解: 令 C(x) 为 “x 在这个班上,”B(x) 为 “ x 读过这本书,”P(x) 为 “x 通过了考试.”
以符号表示前提和结论.
步骤 理由
1. 前提引入
2. C存在实例，用（1）
3. C 化简律，用(2)
4. 前提引入
5.全称实例，用（4）
6. )假言推理，用(3)和(4)
7.化简律，用(2)
8. ) 合取律，用(6)和(7)
9.存在引入，用（8）
全称实例和假言推理的组合称为全称假言推理。
这个规则可以使用到苏格拉底例子中
,其中a是论域中一个特定的元素
指出如下” P(x)∧Q(x)”为真，那么为真的论证有哪些错误？
使用推理规则建立论证
Section 1.7
证明是一个建立语句真实性的有效论证。
在数学、计算机科学等重，非形式化证明经常被使用。
每个步骤使用多于一条的推理规则；
不显示的列出所用到的假设公理和推理规则；
证明有许多实际应用:
验证计算机程序是否正确
建立操作系统是安全的
使程序在人工智能中作出推论
证明系统规范说明书是一致的
定理是一个能够被证明是真的语句:
公理 (假定为真的语句)
引理是有助于证明其它结论的定理。
推论是从一个被证明的定理直接建立起来的一个定理。
不太重要的定理有时称为命题。
猜想是从一个被提出认为是真的命题，通常是基于部分证据、启发式论证或者专家的直觉。可真可假。当猜想被证明，猜想变真理.
理解定理是如何陈述的
许多定理断言一个性质相对于论域中的所有元素都成立。
在标准的数学里，全称量词通常是被省略的。
“如果 x > y, 其中 x 和 y 是正实数, 那么 x2 > y2 ”
“对所有的正实数x 和 y, 如果 x > y, 那么 x2 > y2 .”
为了证明, 我们引入c 是其域中任一元素,
通过普遍推广，原公式的真理如下。
所以, 我们必须证明某种形式:
证明条件语句: p → q
平凡证明: 如果证明 q 为真, 那么p → q 一定为真。
“如果下雨那么1=1”
空证明: 如果证明p 为假，那么 p → q一定为真。
“如果我富有并且贫穷那么2 + 2 = 5 。”
[ 尽管这些例子看起来很傻, 平凡证明和空证明经常被用于数学归纳中 ]
定义:整数 n 是偶数，
如果存在一个整数 k 使得 n = 2k；
如果存在一个整数k 使得 n = 2k + 1。
证明条件语句: p → q
直接证明法: 假定p为真。使用推理规则、公理, 以及逻辑等价式证明 q必为真。
例: “如果n 是奇数, 那么 n2是奇数。”
解: 假定n 是奇数。那么n = 2k + 1 ，其中k是整数。两边平方, 得:
n2 = (2k + 1)2 = 4k2 + 4k +1 = 2(2k2 + 2k) + 1= 2r + 1,
其中 r = 2k2 + 2k , 是整数.
得证：如果 n 是奇数, 那么 n2是奇数。
证明条件语句: p → q
反证法: 假定 ¬q 是前提 ，证明¬p成立。证明p → q为真通过逆否命题 ¬q → ¬p 为真来完成。
例: 证明，如果 n 是整数，并且3n + 2 是奇数, 那么 n 是奇数
解: 假定 n 是偶数。所以, n = 2k 对某整数k。
于是， 3n + 2 = 3(2k) + 2 =6k +2 = 2(3k + 1) = 2j，其中 j = 3k +1
所以 3n + 2 是奇数。
证明了¬q → ¬p ,p → q为真。如果 n 是整数，并且3n + 2 是奇数, 那么 n 是奇数。
证明条件语句: p → q
为了证明p为真, 从一个矛盾式（如r ∧ ¬r ）得到¬p为假。即证明¬p →F 为真 , 对应T→p 也为真。
例:证明一个月内，任意22天中至少有4天属于每星期的同一天。
解: 假设22天中至多3 天属于每星期的同一天。 因为一周有7天， 蕴含了我们最多可以选择21天。这与前提矛盾，证明了 ¬p →（ r ∧ ¬r ） 为真，得证。
证明条件语句: p → q
假定p和¬q为真, 然后利用¬q → ¬p (逆反命题)为真的证明步骤得出¬p 必然为真。这样导出矛盾式p ∧¬p ，完成归谬证明。
例:归谬法证明， 整数域，如果3n + 2 是奇数, 那么 n 是奇数。
解: p 表示3n + 2 是奇数， q表示n 是奇数。
构造归谬证明，假设p和¬q为真，也就是n是偶数，
所以存在k使得n=2k。
于是3n + 2=3( 2k)+2=6k+2=2(3k+1)，令t=3k+1，
所以3n+2=2t，是偶数，与前提假设矛盾，得证。
为了证明一个双条件命题的定理，即形如 p ↔ q的语句, 只要证明p → q 和 q →p 都是真。
例: 证明 “如果 n 是整数, 那么 n 是奇数当且仅当 n2是奇数”
解:证明 p →q 和 q →p. 得到结论 p ↔ q.
1 = 2的“证明”
步骤理由
1. a=b 前提引入
2. a2=a*b（1）两边乘以a
3. a2 – b2 = a*b – b2(2)两边减去b2
4. (a-b)*(a+b) = (a-b)*b （3）两边因式分解
5. a+b = b （4）两边除以a-b
6. 2b = b(5)把a换成b，因为a=b并化简
7.2=1 (6)两边除以b
许多错误是源于引入了不是前面步骤得出的逻辑推导。
直接证明方法不起作用或者困难时:
使用反证法或归谬证明法。
在下一节中，我们将看到当简单的方法不工作时可以使用的策略。
用归谬法证明 p q→r, ¬r∧¬q, 推出 ¬p
Section 1.8
分别证明每个条件语句
Example: 设a @ b = max{a, b} = a ，如果 a ≥ b,
否则a @ b = max{a, b} = b.
判断实数a, b, c 大小
(a @b) @ c = a @ (b @ c) (@ 是联想操作符.)
Proof: 设 a, b, and c 为任意实数.
那么有6 种情况必须顾及。
Example: 证明如果 x 和 y 是整数，并且x∙y 和x+y 是偶数, 那么x 和 y是偶数.
Proof: 使用反证法。假设x 和 y 不都是偶数。那么, 其中一个是奇数。 不是一般性, 假设x 是奇数。 那么x = 2m + 1 对于整数m。
Case 1: y 是偶数。 那么 y = 2n对于一些整数n, 所以x + y = (2m + 1) + 2n = 2(m + n) + 1 是奇数.
Case 2: y 是奇数。那么y = 2n + 1对于一些整数n, 所以 x ∙ y = (2m + 1) (2n + 1) = 2(2m ∙ n +m + n) + 1 是奇数
我们在证明中使用不是一般性是合理的，因为当y是奇数时的证明可以通过上面的证明简单的交换x和y的角色而获得。
此类命题的证明 .
找到一个c, 使得P(c) 为真.
为真，通过存在实例化(EG).
Example: 一个正整数能写成两个不同整数的立方和:
Proof:1729 = 103+ 93= 123+ 13
(1877-1947)
Srinivasa Ramanujan
(1887-1920)
在非构造性存在证明中, 我们不是找出c 使得 P(c)而是以某种其他方式来证明。
Example: 证明无理数x和y，使得 xy 是有理数。
Proof: 我们知道√2 是无理数。 考虑√2 √2 。如果是有理数, 那么就存在两个无理数x 和 y 且 xy为有理数, 即 x = √2 和 y = √2. 但是如果√2 √2 是无理数,那么我们令x = √2 √2和y = √2 以至于xy = (√2 √2)√2= √2 (√2 √2)= √2 2= 2.
证明p → q 的证明策略
首先尝试直接证明方法.
如果困难，那么考虑使用间接证明方法(e.g.,归谬证明法).
无论何种方法，都需要为证明找寻一个起点.
正向推理。从已知的公理和定理开始，通过一系列步骤来构造证明。从p 开始到q结束, 或从¬q 开始到¬p结束。
反向推理。要证明 q，寻找一个 p 并证明具有性质 p → q。
Example: 假定两人玩游戏，轮流从15块石头的堆中每次取1，2或3块石头。取最后一块石头的人赢得游戏。证明无论第二个玩家如何取，第一个玩家都能赢得游戏。
Proof: 设 n是游戏的最后一步。
Step n:Player1能赢如果堆中包含1,2或3块石头。
Step n-1: Player2 不得不从有4块石头的堆中取石头，就迫使Player2不得不留下1,2或3块石头。
Step n-2: Player1面临5,6或7 块石头时， Player1留下4块石头。
Step n-3: Player2应该留下8块石头。
Step n-4: Player1 面临9,10, or 11块石头。
Step n-5: Player2面临12块石头。
Step n-6: Player1留下12 块石头。
/docProps/thumbnail.jpeg
程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: [email protected]
Reviews
There are no reviews yet.