推理喜羊羊与灰太狼之羊羊小侦探

逻辑与证明(3)南京大学计算机系离散数学教学组回顾命题逻辑命题;命题变量;逻辑连接词;复合命题;自然语言事实和推理的命题逻辑形式表达真值;指派;重言式(永真式),矛盾式(永假式),可能式逻辑等价真值表证明;双蕴含永真;等价替换;提要谓词逻辑谓词,量词,论域谓词的否定与嵌套逻辑等价推理有效论证形式推理规则与及用推理规则来论证有关谓词逻辑的论证谓词逻辑例:人都要死的苏格拉底是人苏格拉底要死的命题逻辑对此推理毫无办法!
谓词逻辑知识表示brother(x,y)father(y,z)uncle(x,z)father(x,y)father(y,z)grandfather(x,z)命题逻辑无法表达!
谓词如果x是整数,"x大于2"不是命题,它的真值依赖于x的取值可以将"x大于2"表示为P(x).
谓词:P(x)陈述可以视同关于x的一个P属性取值(一个函数)P的定义域是整数集,其值域是{T,F}P(3)是一个取值为T的命题"forallx,P(x)"是一个取值为F的命题"存在一个x,P(x)"是一个真值为T的命题量词若P(x)是谓词,xP(x)表示"对所有的x,P(x)"称为全称量词若P(x)是谓词,xP(x)表示"存在某个x,P(x)"称为存在量词例:P(x)表示x>2,xP(x)为假,xP(x)为真关于论域/作用域的讨论符号化以下语句:P(x)表示x2>0,xP(x)的真值有的政治家诚实所有美国人都喜欢汉堡包不同的论域,真值不一不同的谓词,符号化表达式不一特别注意:不同论域下,不同量词的符号化关于论域/作用域的讨论观察量化表达式:x(P(x)Q(x))x(P(x,y)Q(x,y))xP(x)xQ(x)xP(x)yQ(y)量化表达式中的变元:绑定、自由、作用域、替换逻辑等价逻辑表达式的逻辑等价:都有相同的真值,无论变量设定在哪个论域上,无论什么谓词代入.
带量词的公式的否定式xP(x)xP(x)对所有的x,x的平方是正数否定:存在某个实数x,其平方不是正数.
xP(x)xP(x)存在x,满足5x=x.
否定:对任意的x,5xx.
多个量词并用xyP(x,y)yxP(x,y)举例:P(x,y)表示x+y=y+x.
论域为实数集xyP(x,y)yxP(x,y)举例:P(x,y)表示x=y+1.
xyP(x,y)与yxP(x,y)不一定等价举例:P(x,y)表示"y>x".
多个量词并用考虑实数集:xyP(x,y)与yxP(x,y)总是有相同的真值.
若P(x,y)表示x+y=y+x,则yxP(x,y)为真.
xyP(x,y)与yxP(x,y)总是有相同的真值.
若P(x,y)表示x=y+1,则yxP(x,y)为真.
若P(x,y)表示"y>x"则xyP(x,y)为真,但yxP(x,y)为假.
将自然语言翻译成逻辑表达式这个班上的每个学生都学过微积分课程.
S(x):x是这个班上的C(x):x学过微积分课程x(S(x)C(x))这个班上的每个学生都或去过加拿大,或去过墨西哥.
x(S(x)V(x,加拿大)V(x,墨西哥))练习:所有狮子都是凶猛的,有些狮子不喝咖啡.
一个关于素数的命题n(N(n)x(N(x)(xn)(x2n)y(y|x(y=1y=x))))定义:N(x):x是正整数;y|x:y整除x练习:"不存在最大的素数.
"在n与2n之间存在素数(Tschebyscheff定理):为阅读和构造证明而必须掌握的若干基本逻辑要素:推理规则推理的样例老张请小刘和老钱吃饭.
他和老钱先到饭店,等了好久小刘还没有到.
老张自言自语说:"哎,该来的还没来.
"老钱听了不高兴了:"哦,原来我是不该来的那我走吧.
"问题:如果你是老钱,你会不高兴吗你的不高兴,有道理吗推理的一般解释:从"前提"A1,A2,…,Ak为真出发,推出"结论"B为真的推理(证明)过程.
前提:该来的还没有来;老钱来了结论:老钱不该来其中我们关心的是:结论是否正确其实,我们更关心的是:推理(证明)过程是否正确!
当前提都正确的时候,如果推理过程正确,那么,结论一定正确!
老钱该不该来前提:该来的还没有来-------(1)老钱来了Q(老钱)2)推理过程(1)P(老钱)→Q(老钱)3)(3)+(2)P(老钱)结论:老钱不该来!
定义谓词:P(x):x该来;Q(x):x来了:全称量词,表示"对所有的"老钱其实完全可以来!
问题出在哪里推理过程正确!
前提前提有误!
再一例如果税收下降,收入一定上升.
现在我的收入上升了,所以,一定是税收下降了!
定义命题P:税收下降;命题Q:收入上升前提:PQ;Q结论:P推理过程:推理过程的不正确,不能保证任何结果的正确性推理过程正确性保障推理过程正确性的保障需要数学(具体而言是数理逻辑)的支持!
数理逻辑基础包括:命题逻辑和谓词逻辑推理的结构-重言式前提:一组命题公式A1,A2,…,Ak结论:一个命题公式B所谓"推理正确"指:对诸Ai和B中出现的命题变元的任一指派,若前提的合取式为真,则结论必为真推理的结构-重言式即"推理为正确的"当且仅当(A1A2…Ak)B是重言式说明:若推理正确,则或者A1A2…Ak≡F,或者(A1A2…Ak≡T,且B≡T),无论何种情况,上式为真,蕴涵式永真.
若上述蕴涵式为重言式,且A1A2…Ak为真,B也必为真,因此推理正确.
注意:若前提的合取式为假,推理总是正确,或者说,推理正确并不保证结论正确推理过程从前提A1,A2,…,Ak为真出发,推出结论B为真的推理过程是一个表达式序列,该序列最后一个表达式应是要证明的结论,而其它任一表达式满足如下的条件,:它可以是任意一个重言式;它可以是{A1,A2,…,Ak}中的任何一个表达式;可以是序列中前面的任一表达式通过应用"替换规则"得到的表达式;可以是对序列中前面任意一个或若干个表达式应用推理规则得到的新表达式A,(AB)得到B例以下推论合理吗晚上编程序就没法早早睡觉;睡得早,起床早,上课不迟到;所以,要想不迟到,晚上千万不能编程序!
不合理再一例:如果税收下降,收入一定上升.
现在我的收入上升了,所以,一定是税收下降了!
不合理命题逻辑的推理规则用推理规则建立论证"今天下午不出太阳并且比昨天冷","只有今天下午出太阳,我们才去游泳","若我们不去游泳,则我们将乘独木舟游览","若我们乘独木舟游览,则我们将在黄昏时回家",结论"我们将在黄昏时回家".
用推理规则建立论证已知(p∧q)∨r和r→s,那么p∨s是否为真常用的蕴涵重言式蕴含重言式在逻辑推理中相当重要蕴涵重言式与导出的推理规则附加律化简律假言推理取拒式析取三段论假言三段论等价三段论构造性二难破坏性二难与量词有关的基本推理规则全称例示UI:xP(x)P(c)全称生成UG:P(c),任意cxP(x)存在例示EI:xP(x)对某个c,P(c)存在生成EG:对某个c,P(c)xP(x)苏格拉底到底死不死P(x):x是人;Q(x):x要死符号化及推理过程:人都是要死的:x(P(x)Q(x))P(苏格拉底)Q(苏格拉底)苏格拉底是人:P(苏格拉底)Q(苏格拉底)谓词逻辑中的推理(举例)"在这个班上的某个学生没有读过这本书","班上的每个人都通过了第一门考试",结论"通过第一门考试的某个人没有读过这本书".
C(x):x在这个班上B(x):x读过书了P(x):x通过了第一门考试x(C(x)B(x))x(C(x)P(x))x(P(x)B(x))C(a)B(a)存在例示C(a)化简C(a)P(a)全称例示P(a)假言推理B(a)化简x(P(x)B(x))存在生成老钱真的可以来前提:"该来的还没有来"改成"还有一个该来的还没有来"-------(1)老钱来了Q(老钱)2)推理过程(1)==>P(小刘)Q(小刘)结论:老钱真的可以来!
定义谓词:P(x):x该来;Q(x):x来了再一例以下推论正确吗有人喜欢喝茶,有人喜欢喝酒因此,有人既喜欢喝茶又喜欢喝酒令:A(x):x喜欢喝茶;B(x):x喜欢喝酒推理如下:1.
xA(x)xB(x)Premise2.
xA(x)化简,13.
xB(x)化简,14.
A(c)例示,25.
B(c)例示,36.
A(c)B(c)合取.
4,57.
x(A(x)B(x))生成,6再一例请根据下面事实,找出凶手:a.
清洁工或者秘书谋害了经理.
b.
如果清洁工谋害了经理,则谋害不会发生在午夜前.
c.
如果秘书的证词是正确的,则谋害发生在午夜前.
d.
如果秘书的证词不正确,则午夜时屋里灯光未灭.
e.
如果清洁工富裕,则他不会谋害经理.
f.
经理有钱且清洁工不富裕.
g.
午夜时屋里灯灭了.
再一例用谓词逻辑,将下列推理形式化,并对正确的推理给出推理过程,要指明所假设命题或谓词的含义人都喜欢吃蔬菜,但说所有人都喜欢吃鱼是不对的,所以存在只喜欢吃蔬菜而不喜欢吃鱼的人再一例用命题逻辑,将下列推理形式化,并对正确的推理给出推理过程,要指明所假设命题的含义若小张喜欢数学,则小赵或小李也喜欢数学.
若小李喜欢数学,他也喜欢物理.
小张确实喜欢数学,可小李不喜欢物理.
所以小赵喜欢数学小结谓词逻辑在命题逻辑基础上引入谓词和量词,推理严格的基于命题逻辑和谓词逻辑的形式推理作业教材内容:[Rosen]1.
3—1.
5节课后习题:pp.
34—37(英文教材pp.
47—49,第七版pp.
44-47):10,14(任选3小题),34,42pp.
43—47(英文教材pp.
58—62,第七版pp54-59):6(任选3小题),16,44p.
56(英文教材pp.
74,第七版pp68-69):19,21,24,29