第2章谓词逻辑(2009-2010-02).ppt
《第2章谓词逻辑(2009-2010-02).ppt》由会员分享,可在线阅读,更多相关《第2章谓词逻辑(2009-2010-02).ppt(64页珍藏版)》请在三一文库上搜索。
1、离 散 数 学,戎 玫,第2章 谓词逻辑,2.1 个体、谓词与量词 2.2 谓词公式 2.3 谓词演算的等价式与蕴含式 2.4 前束范式 2.5 谓词逻辑的推理理论,2.1 .1 个体,苏格拉底推论 所有的人总是要死的 苏格拉底是人 苏格拉底总是要死的 将原子命题进一步细分,分解出个体、谓词和量词,以表达个体与总体的内在联系和数量关系,即谓词逻辑研究的内容。,2.1 个体、谓词与量词,2.1 .1 个体,考察下面的三个原子命题: 李玲是优秀共产党员。 张华比李红高。 小高坐在小王和小刘的中间。 个体是指所研究对象中可以独立存在的具体的或抽象的客体。 个体常用小写英文字母或小写英文字母带下标表示
2、,叫做个体标识符。 表示具体或特定个体的标识符称个体常元。 例如:李玲、张华可如下表示: a:李玲 b:张华,2.1 .1 个体,将表示任意个体或泛指某类个体的标识符称为个体变元,常表示为x、y、z、等或这些英文字母带下标。 个体变元的变化范围称为个体域或论域。 个体域可以是有穷集合,也可以是无穷集合,包含任意个体域的个体域称为全总个体域,它是由宇宙间一切对象组成的集合。 在本课程中,如无特别说明,所采用的都是全总个体域。,2.1.2谓 词,刻划个体性质或几个个体关系的模式叫做谓词。 谓词常用大写英文字母表示,叫做谓词标识符。 例如可以用F,G,H表示前面三个命题中谓词: F:是优秀共产党员。
3、 可以分解成为个体“李玲”和“是优秀共产党员”两部分。“是优秀共产党员”是用来描述个体“李玲”的性质; G:比高。 H:坐在和的中间。,2.1.2谓 词,把与一个个体相关联的谓词叫做一元谓词。 把与两个个体相关联的谓词叫做二元谓词。 把与三个个体相关联的谓词叫做三元谓词。 一般的,把与n个个体相关联的谓词叫做n元谓词。 F是一元谓词; G是二元谓词; H是三元谓词;,2.1.2谓 词,设F是一元谓词,a是个体常元,用F(a)表示个体常元a具有性质F; 设G是二元谓词,a,b是个体常元,用G(a,b)表示个体常元a和b具有关系G; 于是上面三个命题就表示为: F(a):李玲是优秀共产党员。 G(
4、b,c):张华比李红高。 H(d,e,f):小高坐在小王和小刘的中间。 将谓词后面填上相关联的个体常元所得的式子叫做谓词填式。F(a),G(b,c),H(d,e,f)都是谓词填式。谓词填式表示的是命题。,2.1.2谓 词,类似的,用F(x)表示个体变元x具有性质F ,F(x)叫做一元命题函数; 用G(x, y)表示个体变元x和y具有关系G ,G(x,y)叫做二元命题函数; 用P(x1,x2,xn)(n1)表示个体变元x1, x2, ,xn具有关系P。 P(x1,x2, ,xn) 为n元命题函数。 命题函数没有确定的真值,它不是命题。只要用个体常元取代所有的个体变元,就得到了命题。,2.1.2谓
5、 词,例,H(x,y):x+y0,此命题函数是否为命题? 令 a:5, b:7 H(a,b) 是否为命题?真值? 用个体常元取代命题函数的所有个体变元所得到的表达式就是谓词填式,谓词填式也叫做0元命题函数。 F(a),G(b,c),H(d,e,f)都是0元命题函数,它们都是命题。 命题逻辑中的命题均可以表示为谓词逻辑中的0元命题函数(谓词填式),命题成为命题函数的特例。,2.1.2谓 词,【例2.1】将下列命题符号化,并讨论它们的真值。 2与3都是偶数。 如果5大于3,则2大于6。,解: 设F(x):x是偶数。 a:2,b:3 该命题符号化为: F(a)F(b) F(b)表示3是偶数,它是个假
6、命题。所以F(a)F(b)为假。, 设G(x,y): x大于y a:5,b:3,c:2,d:6 该命题符号化为:G(a,b)G(c,d) G(a,b)表示5大于3,它是真命题。G(c,d)表示2大于6,这是个假命题。所以G(a,b)G(c,d)为假。,2.1.3 量词,量词分两种: 全称量词 全称量词符号化为“”。 即“一切的”,“所有的”,“每一个” 等。用(x),(y)等表示个体域里的所有个体,(x)F(x) 表示个体域中的所有个体都有性质F。 存在量词 存在量词符号化为“”。即“存在”,“有一个”,“有些” 等。用(x),(y)等表示个体域里有些个体,用(x)F(x) 表示在个体域中存在
7、个体具有性质F。 全称量词与存在量词统称为量词。,2.1.3 量词,【例2.2】个体域是人类集合,对下列命题符号化。 凡人要死。 有的人是研究生。 解: 令F (x):x要死。 命题“凡人要死。”符号化为:(x)F (x) 令G(x):x是研究生。 命题“有的人是研究生。”符号化为:(x)G(x) 在命题函数前加上量词(x)和(x)分别叫做个体变元x被全称量化和存在量化。如果对命题函数中所有命题变元进行全称量化或存在量化,该函数就变成了命题。,2.1.3 量词,【例2.3】对下列命题符号化,并在,三个个体域中考察命题的真值。 命题: 所有数小于5。 至少有一个数小于5。 个体域: -1,0,1
8、,2,4 3,-2,7,8 15,20,24,解:设L(x):x小于5。 “所有数小于5。”符号化为:(x) L(x) 在个体域,中,它们的真值分别为:真,假,假。 “至少有一个数小于5。”符号化为:(x)L(x) 在个体域,中,它们的真值分别为:真,真,假。,2.1.3 量词,设个体域为D=-2,3,6,谓词P(x):x3,G(x):x5,R(x):x7,求下列各谓词公式的真值。 1、 (x)(P(x) G(x) 。 2、 (x)(R(x) P(x)G(5) 3、 (x)(P(x)G(x) 解:,2.1.3 量词,命题函数中的个体变元量化以后变成命题,其真值与个体域的选择有关,为了统一我们使
9、用全总个体域,而对于其它个体域用一个谓词来表示,即特性谓词。 特性谓词:用一个谓词来表示除全总个体域外的特殊的个体域。 特性谓词加入的方法为: 对全称量词,特性谓词作为条件命题的前件加入。 对存在量词,特性谓词作为合取项加入。,2.1.3 量词,【例2.4】对下列命题在,两个个体域中符号化。 命题: 所有老虎是要吃人。 存在一个老虎要吃人。 个体域: 所有老虎组成的集合。 全总个体域。 解:设A(x):x是要吃人的。 个体域为所有老虎的集合。 符号化为 (x)A(x) 符号化为 (x)A(x) 个体域为全总个体域。设特性谓词T(x):x是老虎。 符号化为 (x)(T(x)A(x) 符号化为 (
10、x) (T(x)A(x),特性谓词的位置和描述,(1) 在全称量词下的特性谓词 例:所有的北京人均去过天安门 符号:P(x):x是北京人 Q(x):x去过天安门 正确符号: (x)(P(x)Q(x) 字面翻译为:全总个体域中任一个x,如果x是北京人,则他就去过天安门。这是符合原句的。 如果在全称量词下,我们把特性作为合取式一项: (x)(P(x)Q(x) 则该命题变成了假命题(矛盾式)。,特性谓词的位置和描述,(1) 在全称量词下的特性谓词 例:凡人要死 符号:P(x):x是人 D(x):x是要死的 正确符号: (x)(P(x)D(x) 如果描述为: (x)(P(x)D(x) 字面翻译为:“全
11、总个体域中每一个x,x是人并且x会死。”这显然是假命题。因为我们只要取一个不是人的个体xo。则P(xo)是假命题,则P(xo)D(xo)是假命题,则(x)(P(x) D(x)就是假命题。,特性谓词的位置和描述,(2) 在存在量词下的特性谓词 例:有一个南京人他去过北京 符号:N(x):x是南京人 P(x):x去过北京 正确描述: (x)(N(x)P(x) 存在量词下,特性谓词作合取式的一项。 如果存在量词下,我们将特性谓词作为蕴涵的前体,这样会导致原来的命题变成了永真式。,特性谓词的位置和描述,(2) 在存在量词下的特性谓词 例:有一个人他去过太阳。 符号:P(x):x是人 Q(x):x去过太
12、阳 正确描述: (x)(P(x)Q(x) 存在量词下,特性谓词作合取式的一项。 如果描述为:(x)(P(x)Q(x),2.1.3 量词,有些自然数是素数。 金子是闪光的,但闪光的并不都是金子。 所有运动员都钦佩某些教练员。 解:设N(x):x是自然数。 P(x):x是素数。 (x)(N(x) P(x) 解:设G(x):x是金子。 S(x):x是闪光的。 (x)(G(x)S(x)(x)(S(x)G(x) 解:设L(x):x是运动员。 C(x):x是教练员。 A(x,y):x钦佩y。 (x)(L(x)(y)(C(y)A(x,y),实例,例1:所有演员均佩服一些教师 例2:所有的病人均相信一些医生,
13、而所有的病人均不相信一切骗子。 P(x):x是演员 Q(x):x是教师 R(x,y):x佩服y 描述为: (x)(P(x)(y)(Q(y)R(x,y) P(x):x是病人 Q(x):x是医生 R(x):x是骗子 S(x,y):x相信y 描述为: (x)(P(x)(y)(Q(y)S(x,y) (x)(P(x)(y)(R(y)S(x,y),2.2.1 谓词公式,定义2.2.1 按下列规则构成的表达式称为谓词演算的合式公式,简称谓词公式。 谓词演算的原子公式是合式公式。 若A是合式公式,则A是合式公式。 若A和B是合式公式,则(AB),(AB),(AB)和(AB)是合式公式。 如果A是合式公式,x是
14、A中出现的任意个体变元,则(x)A,(x)A是合式公式。 只有有限次地应用、所得的公式是合式公式。,2.2.1 谓词公式,谓词公式也有以下约定: 最外层的括号可以省略。 如果按、在运算中的优先级别,省略括号后不改变原来的运算次序,可以省略括号,但量词后面括号不能省略。,2.2.1 谓词公式,【例2.5】并非每个实数都是有理数。 解:设R(x):x是实数 Q(x):x是有理数 该命题符号化为:(x)(R(x)Q(x) 【例2.6】没有不犯错误的人。 解:设M(x):x是人 F(x):x犯错误 符号化为: (x) (M(x) F(x) 【例2.7】并不是所有的兔子都比所有的乌龟跑得快。 解:设F(
15、x):x是兔子。 G(x):x是乌龟。 H(x,y):x比y跑得快。 该命题符号化为:(x) (y) (F(x)G(y)H(x,y),多个量词同时出现时,不能随意颠倒它们的顺序。颠倒后会改变原命题的含义。 例如:对任意的x,存在着y,使得xy5 。 取个体域为实数集, 用H(x,y)表示xy5,这个命题符号化为: (x)(y)H(x,y) 如果将量词的顺序颠倒: (x)(y)H(x,y),2.2.2约束变元与自由变元,定义2.2.2 如果A是谓词公式B的一部分且是谓词公式,则称A是B的子公式。 定义2.2.3 紧接量词以后的最小子公式叫做该量词的辖域或作用域。 定义2.2.4 量词(x)和(x
16、)中的x叫做该量词的指导变元或作用变元。 定义2.2.5 量词(x)和(x)的辖域内x的一切出现叫约束出现,x叫做约束变元;约束变元以外的其它变元的出现叫自由出现,自由出现的变元叫自由变元。,2.2.2约束变元与自由变元,【例2.10】说明下列各式量词的辖域,找出约束变元和自由变元。 (x)P(x)Q(y) (x) (P(x)(y)Q(x,y) (x) P(x)(y)Q(x,y) (x)(y)(P(x,y)Q(y,z) (x) R(x,y) 解:(x)的辖域为P(x),x是约束变元,y是自由变元。 (x)的辖域为P(x)(y)Q(x,y),(y)的辖域为Q(x,y),x和y都是约束变元,无自由
17、变元。 (x)的辖域为P(x),(y)的辖域为Q(x,y),P(x)中的x和Q(x,y) 中的y是约束变元,Q(x,y)中的x是自由变元。 (x)的辖域为(y)(P(x,y)Q(y,z),(y)的辖域为P(x,y)Q(y,z),(x)的辖域为R(x,y), (P(x,y)Q(y,z)中的x 、y是约束变元, z是自由变元, R(x,y)中的y是自由变元。,2.2.2约束变元与自由变元,换名规则: 对约束变元可以换名,其更改变元名称的范围是量词的指导变元,以及该量词辖域中的所有该变元,公式的其余部分不变。 换名时一定要更改成辖域中没有出现的变元名,最好是公式中没有的变量名。 代入规则是: 对于谓
18、词公式中的自由变元可以代入,代入时需对公式中该变元自由出现的每处进行。 代入的变元与原公式中其他变元的名称不能相同。,2.2.2约束变元与自由变元,【例2.11】对(x)(y)(P(x,y)Q(y,z)(x) R(x,y)中的约束变元y换名。 解:用u置换约束变元y。换名后为: (x)(u)(P(x,u)Q(u,z)(x) R(x,y) 不能换成: (x)(u)(P(x,u)Q(y,z)(x) R(x, y) 也不能换成:(x)(z)(P(x, z)Q(z,z)(x) R(x,y) 【例2.12】对(x)(P(y)R(x,y)(y)Q(y) 中的自由变元y进行代入。 解:用z代换y,代入后为:
19、 (x)(P(z)R(x,z)(y)Q(y) 不能换成: (x)(P(x)R(x,x)(y)Q(y) 或 (x)(P(z)R(x,y)(y)Q(y),2.2.2 约束变元与自由变元,自然数有以下三条公理: 1、每个数都有唯一的一个数是它的后继数。 2、没有一个数使数1是它的后继数。 3、每个不等于1的数都有唯一的一个数是它的直接先驱数。 解:设N(x):x是自然数。 S(x,y):y是x的后继(x是y的先驱)。 1、 (x)(N(x)(y)(N(y)S(x,y)(z)(zy) N(z)S(x,z) 2、 (x)(N(x)S(x,1) 3、 (x)(N(x) S(x,2) (y)(N(y)S(y
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 谓词 逻辑 2009 2010 02
链接地址:https://www.31doc.com/p-2120689.html