离散数学左孝陵版第二章答案课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《离散数学左孝陵版第二章答案课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 左孝陵版 第二 答案 课件
- 资源描述:
-
1、Charter twonwelcome第二章第二章 谓词逻辑谓词逻辑n1 谓词的概念与表示法n2 命题函数与量词n3 谓词公式与翻译n4 变元的约束n5 谓词演算的等价式与蕴含式n6 前束范式n7 谓词演算的推理理论1 谓词的概念与表示法在研究命题逻辑中,原子命题是命题演算中最基本的单位,不再对原子命题进行分解,这样会产生二大缺点:(1)不能研究命题的结构,成分和内部逻辑的特征;(2)也不可能表达二个原子命题所具有的共同特征,甚至在命题逻辑中无法处理一些简单又常见的推理过程。例:苏格拉底论证是正确的,但不能用命题逻辑的推理规则推导出来。“所有的人总是要死的。A “苏格拉底是人。B “所以苏格拉
2、底是要死的。”C1 谓词的概念与表示法1.谓词:谓词:定义定义:用以刻划客体的性质或关系的即是谓词谓词。我们可把陈述句分解为二部分:主语(名词,代词)和谓语(动词)。例:张华是学生,李明是学生。则可把它表示成:H:表示“是学生”,j:表示“张华”,m:表示“李明”,则可用下列符号表示上述二个命题:H(j),H(m)。H作为“谓词”(或者谓词字母)用大写英文字母表示,j,m为主语,称为“客体”或称“个体”。1 谓词的概念与表示法(1)谓词填式)谓词填式:谓词字母后填以客体所得的式子。例:H(a,b)(2)若谓词字母联系着一个客体,则称作一元谓词一元谓词;若谓词字母联系着二个客体,则称作二元谓词二
3、元谓词;若谓词字母联系着n个客体,则称作n元谓词元谓词。(3)客体的次序必须是有规定的。例:河南省北接河北省。n L b写成二元谓词为:L(n,b),但不能写成L(b,n)。2 命题函数与量词命题函数与量词1.命题函数命题函数客体在谓词表达式中可以是任意的名词。例:C“总是要死的。”j:张三;t:老虎;e:桌子。则C(j),C(t),C(e)均表达了命题。在上面的例子中,C:表示“总是要死的”;x:表示变元(客体变元),则C(x)表示“x总是要死的”,则称C(x)为命题函数。定义定义由一个谓词字母和一个非空的客体变元的集合所组成的表达式,称为简单命题函数。2 命题函数与量词命题函数与量词讨论定
4、义:(a)当简单命题函数仅有一个客体变元时,称为一元简单命题函数;(b)若用任何客体去取代客体变元之后,则命题函数就变为命题;(c)命题函数中客体变元的取值范围称为个体域(论述域)。例:P(x)表示x是质数。这是一个命题函数。其值取决于个体域。可以将命题函数命题,有两种方法:2 命题函数与量词命题函数与量词a)将x取定一个值。如:P(4),P(5)b)将谓词量化。如:xP(x),xP(x)个体域的给定形式有二种:具体给定。如:j,e,t全总个体域任意域:所有的个体从该域中取得。2 命题函数与量词命题函数与量词2.量词量词(1)全称量词“”为全称量词符号,读作“对于所有的”,“对任一个”,“对一
5、切”。例:“这里所有的都是苹果”可写成:xA(x)或(x)A(x)几种形式的读法:xP(x):“对所有的x,x是”;xP(x):“对所有x,x不是”;xP(x):“并不是对所有的x,x是”;xP(x):“并不是所有的x,x不是”。2 命题函数与量词命题函数与量词例:将“对于所有的x和任何的y,如果x高于y,那么y不高于x”写成命题表达形式。解:x y(G(x,y)G(y,x)G(x,y):x高于y(2)存在量词“”为存在量词符号,读作“存在一个”,“对于一些”,“对于某些”,“至少存在一个”,“这里存在着这样的”等等。“”表达式的读法:x A(x):存在一个x,使x是;xA(x):存在一个x,
6、使x不是;x A(x):不存在一个x,使x是;xA(x):不存在一个x,使x不是。2 命题函数与量词命题函数与量词例:(a)存在一个人;(b)某个人很聪明;(c)某些实数是有理数 将(a),(b),(c)写成命题。解:规定:M(x):x是人;C(x):x是很聪明;R1(x):x是实数(特性谓词)R2(x):x是有理数。则 (a)x M(x);(b)x(M(x)C(x);(c)x(R1(x)R2(x)。(3)量化命题的真值:决定于给定的个体域给定个体域:a1an以a1an中的每一个代入xP(x)P(a1)P(an)xQ(x)Q(a1)Q(an)3谓词公式与翻译谓词公式与翻译1.谓词公式原子谓词公
7、式:不出现命题联结词和量词的谓词命名式称为原子谓词公式,并用P(x1xn)来表示。(P称为n元谓词,x1xn称为客体变元),当n=0时称为零元谓词公式。定义(谓词公式的归纳法定义)原子谓词公式是谓词公式;若A是谓词公式,则A也是谓词公式;若A,B都是谓词公式,则(AB),(AB),(AB),(AB)都是谓词公式;若A是谓词公式,x是任何变元,则xA,xA也都是谓词公式;3谓词公式与翻译谓词公式与翻译只有按-所求得的那些公式才是谓词公式(谓词公式又简称“公式”)。例1:任何整数或是正的,或是负的。解:设:I(x):x是整数;R1(x):x是正数;R2(x):x是负数。此句可写成:x(I(x)(R
8、1(x)R2(x)。例2:试将苏格拉底论证符号化:“所有的人总是要死的。因为苏格拉底是人,所以苏格拉底是要死的。”解:设M(x):x是人;D(x):x是要死的;M(s):苏格拉底是人;D(s):苏格拉底是要死的。3谓词公式与翻译谓词公式与翻译写成符号形式:x(M(x)D(x),M(s)D(s)2.由于对个体描述性质的刻划深度不同,可翻译成不同形式的谓词公式。4变元的约束变元的约束1.辖域:紧接在量词后面括号内的谓词公式。例:xP(x),x(P(x)Q(x)。若量词后括号内为原子谓词公式,则括号可以省去。2.自由变元与约束变元约束变元:在量词的辖域内,且与量词下标相同的变元。自由变元:当且仅当不
9、受量词的约束。例:xP(x,y),x(P(x)y(P(x,y)。4变元的约束变元的约束3.约束变元的改名规则任何谓词公式对约束变元可以改名。我们认为xP(x,y)和zP(z,y)是一等价的谓词公式,但是需注意,不能用同一变元去表示同一谓词公式中的二个变元。例如:yP(y,y)是不正确的。下面介绍约束变元的改名规则:(a)在改名中要把公式中所有相同的约束变元全部同时改掉;(b)改名时所用的变元符号在量词辖域内未出现的。4变元的约束变元的约束例:xP(x)yR(x,y)可改写成xP(x)zR(x,z),但不能改成xP(x)xR(x,x),xR(x,x)中前面的x原为自由变元,现在变为约束变元了。4
10、.区别是命题还是命题函数的方法(a)若在谓词公式中出现有自由变元,则该公式为命题函数;(b)若在谓词公式中的变元均为约束出现,则该公式为命题。例:xP(x,y,z)是二元谓词,yxP(x,y,z)是一元谓词,而谓词公式中如果没有自由变元出现,则该公式是一个命题。4变元的约束变元的约束举例:例1:“没有不犯错的人。”解:设F(x)为“x犯错误”,M(x)为“x是人”(特性谓词)。可把此命题写成:(x(M(x)F(x)x(M(x)F(x)例2:“x是y的外祖父”“x是z的父亲且z是y的母亲”设P(z):z是人;F(x,z):x是z的父亲;M(z,y):z是y的母亲。则谓词公式可写成:z(P(z)F
11、(x,z)M(z,y)。5.代入规则:代入规则:对公式中的自由变元的更改叫做代入。(a)对公式中出现该自由变元的每一处进行代入,(b)用以代入的变元与原公式中所有变元的名称不能相同。4变元的约束变元的约束6.个体域(论述域,客体域):用特定的集合表示的被约束变元的取值范围。(1)个体域不同,则表示同一命题的谓词公式的形式不同。例:“所有的人必死。”令D(x),x是要死的。下面给出不同的个体域来讨论:()个体域为:人类,则可写成xD(x);()个体域为任意域(全总个体域),则人必须首先从任意域中分离出来,设M(x),x是人,称M(x)为特性谓词。命题可写成 x(M(x)D(x)4变元的约束变元的
12、约束(2)个体域不同,则表示同一命题的值不同。Q(x):x5-1,0,3-3,6,215,30 xQ(x)T F FxQ(x)T T F(3)对于同一个体域,用不同的量词时,特性谓词加入的方法不同。对于全称量词,其特性谓词以前件的方式加入;对于存在量词,其特性谓词以与的形式加入。4变元的约束变元的约束例:设个体域为:白虎(白猫),黄咪(黄猫),同时令C(x):x是猫(特性谓词);B(x):x是黑色的;A(x):x是动物。()描述命题:“所有的猫都是动物”。即:x(C(x)A(x)(T)(真命题)写成x(C(x)A(x)(F)则为假命题了。x(C(x)A(x)TT T TT x(C(x)A(x)
13、TT F FF()描述命题:“一些猫是黑色的”。x(C(x)B(x)FF F F F而 x(C(x)B(x)F F T TT4变元的约束变元的约束7.量词对变元的约束,往往与量词的次序有关。例:yx(xy-2)表示任何y均有x,使得x3,则可写出:xP(x)P(0)P(1)P(i)xP(x)P(0)P(1)P(i)下面分类介绍在谓词公式中含有量词的等价式和永真蕴含式。(1)量词转换律:E25(Q3)xP(x)xP(x)E26(Q4)xP(x)xP(x)下面证明:设个体域为:S=a1,a2,an 5谓词演算的谓词演算的 等价式与蕴含式等价式与蕴含式 xP(x)(P(a1)P(a2)P(an)P(
14、a1)P(a2)P(an)xP(x)下面举例说明量化命题和非量化命题的差别:否定形式不同例:否定下列命题:(a)上海是一个小城镇 A(s)(b)每一个自然数都是偶数 x(N(x)E(x)上述二命题的否定为:(a)上海不是一个小城镇 A(s)(b)有一些自然数不是偶数 x(N(x)E(x)x(N(x)E(x)x(N(x)E(x)x(N(x)E(x)5谓词演算的谓词演算的 等价式与蕴含式等价式与蕴含式结论:对于非量化命题的否定只需将动词否定,而对于量化命题的否定不但对动词进行否定而且对量词同时进行否定,其方法是:x的否定变为x,x的否定变为x。(2)量词辖域的扩张及其收缩律 E27(Q6)xA(x
15、)P x(A(x)P)(Q7)xA(x)P x(A(x)P)E28(Q9)xA(x)P x(A(x)P)(Q8)xA(x)P x(A(x)P)P为不含有变元的任何谓词公式5谓词演算的谓词演算的 等价式与蕴含式等价式与蕴含式证明E27(Q6),设个体域为:S=a1,a2,an xA(x)P(A(a1)A(a2)A(an)P (A(a1)P)(A(a2)P)(A(an)P)x(A(x)P)E30(Q14)xA(x)B x(A(x)B)E31(Q15)xA(x)B x(A(x)B)E32(Q16)AxB(x)x(AB(x)E33(Q17)A x B(x)x(AB(x)证明E30(Q14),设个体域为
16、:S=a1,a2,an x(A(x)B)(A(a1)B)(A(an)B)(A(a1)B)(A(an)B)5谓词演算的谓词演算的 等价式与蕴含式等价式与蕴含式 (A(a1)A(an)B x A(x)B x(A(x)B)xA(x)B(3)量词分配律E24(Q10)x(A(x)B(x)xA(x)xB(x)E23(Q11)x(A(x)B(x)xA(x)xB(x)I18(Q12)x(A(x)B(x)xA(x)xB(x)I17(Q13)xA(x)xB(x)x(A(x)B(x)E29(Q18)x(A(x)B(x)xA(x)xB(x)I19(Q19)xA(x)xB(x)x(A(x)B(x)5谓词演算的谓词演算
展开阅读全文