《交大数理逻辑课件5-3谓词逻辑的等值和推理演算》由会员分享，可在线阅读，更多相关《交大数理逻辑课件5-3谓词逻辑的等值和推理演算（29页珍藏版）》请在金锄头文库上搜索。
1、调 课 通 知,因下周五(11月12日)为广州亚运会开幕式官方放假时间，课程调到下周三(11月10日) 5,6节在310305课室上课，特告之。,第5章 谓词逻辑的等值和推理演算,5.1 否定型等值式 5.2 量词分配等值式 5.3 范式 5.4 基本的推理公式 5.5 推理演算 5.6 谓词逻辑的归结推理法,推理规则,(1)前提引入规则 (2)结论引入规则 (3)置换规则 (4)假言推理规则 (AB)A B (5)附加规则 A (AB) (6)化简规则 (AB) A (7)拒取式规则 (AB)B A,(8)假言三段论规则 (AB)(BC) (AC) (9)析取三段论规则 (AB)B A (1
2、0)构造性二难推理规则 (AB)(CD)(AC) (BD) (11)合取引入规则 A, B AB,有关量词的推理规则,全称量词消去规则（UI规则） 全称量词引入规则（UG规则）,存在量词引入规则（EG规则） 存在量词消去规则（EI规则）,使用推理规则的推演算举例,前提: (x)P(x)(x)(P(x)Q(x)R(x)， (x)P(x) 结论： (x)(y)(R(x)R(y) 证明： (x)P(x)(x)(P(x)Q(x)R(x) 前提引入 (x)P(x) 前提引入 (x)(P(x)Q(x)R(x) 分离 P(c) EI (P(c)Q(c)R(c) UI P(c)Q(c) 附加规则 R(c) 分
3、离 (x)R(x) EG (y)R(y) EG (x)R(x)(y)R(y) 合取规则 (x)(y)(R(x)R(y) 置换,证明: (x)(H(x)M(x)，(x)H(x)(x)M(x),证明： (x)H(x) 前提引入 H(c) EI (x)(H(x)M(x) 前提引入 H(c)M(c) UI M(c) 分离 (x)M(x) EG 若把,写在,的后面，得到如下的推理： (x)(H(x)M(x) 前提引入 H(c)M(c) UI (x)H(x) 前提引入 H(c) EI M(c) 分离 (x)M(x) EG,这个推理在逻辑上是错误的。 因为 中的c为个体域中一个个体， 用EI规则由 推到 不
4、能选择 中的c，因为它要选的个体和 中的个体c不一定是同一个个体， 故推理是错误的。,5.6 谓词逻辑的归结推理法,归结证明法的出发点 证明A B是定理，等价于证明AB=G是矛盾式 归结证明过程 建立子句集S 将G中的全称量词省略，并将G中的合取词用“，”表示，得子句集S 如： (x)(P(x)(y)(D(y)L(x,y)的子句集S为 P(a), D(y) L(a,y) 对S作归结 子句：P(x)Q(x)， P(a)R(x) 作归结，得 归结式：Q(a)R(a) 并将此归结式仍放入S中，重复此过程 直至归结出空子句，证明结束,归结法证明举例,A1= (x)(P(x)(y)(D(y)L(x,y)
5、 A2= (x)(P(x) (y)(Q(y)L(x,y) B= (x)(D(x) Q(x) B= (x)(D(x) Q(x) = (x)(D(x)Q(x) 证明 A1 A2 B P(a) 前提A1的子句 D(y) L(a,y) 前提A1的子句 P(x) Q(y) L(x,y) 前提A2的子句 D(b) 前提B的子句 Q(b) 前提B的子句 L(a,b) 归结 Q(y) L(a,y) 归结 L(a,b) 归结 归结,第二部分 集合论,引例 有10名学生参加一个Party，一共要了8瓶饮料和6个雪糕，已知有1人什么也没要，其他人每种至多要1份，问：最后有多少人既要了饮料又要了雪糕？ 集合论 是现代
6、数学的重要基础，集合不仅可用来表示数及运算，更可用于非数值信息的表示和处理， 如：数据的维护、数据间关系的描述，有些很难用传统的数值计算来处理，但可用集合运算来处理， 它在计算机科学领域中是不可或缺的数学工具，在形式语言、自动机、人工智能、数据库等领域中都卓有成效地应用了集合论。 第二部分主要介绍集合论的基础知识，如集合的基本概念、运算、性质、关系、函数等。,第9章 集 合,9.1 集合的概念和表示方法 9.2 集合间的关系和特殊集合 9.3 集合的运算 9.4 集合的图形表示法 9.5 集合运算的性质和证明 9.6 有限集合的基数,9.1 集合的概念和表示方法,集合是不能精确定义的基本的数学
7、概念。 一个集合一般指的是一些可确定的、可分辨的事物构成的整体。 集合的元素集合中的对象或个体。 集合的构成 集合可以由各种类型的事物构成。 例如： 26个英文字母的集合； C+语言中保留字的集合； 坐标平面上所有点的集合； 方程x210的实数解集合；,集合的表示法,通常用大写英文字母来标记一些集合。 例如， N 代表自然数集合(包括0)， Z 代表整数集合， Q 代表有理数集合， R 代表实数集合， C 代表复数集合。,集合的表示法列举法,列举法（外延表示法） 列出集合的所有元素，元素之间用逗号隔开，并把它们用花括号括起来。 例如，A=1,2,3,4,5 其中1是A的元素，记作1A。 同样有
8、2A , 4A 。 但6不是A的元素，可记作6A。 注意： 对于任何集合 A 和元素 x (可以是集合)， xA和 xA 两者成立其一，且仅成立其一互补律.,元素与集合的关系 隶属关系 属 于 不属于 ,集合的表示法描述法,描述法(内涵表示法) 用谓词概括集合中元素的属性。 例如: 集合 B=x|P(x)， 表示B由使P(x)为真的全体x构成。 B=x|x Z 3x6 ，则B=4,5,6。 注意 谓词P(x)的范围一定要明确清楚，否则集合无法构造。 如：A=x|P(x)，P(x)：x是公园里的美丽的花。 诸如: P(x)：xx 这样的谓词不能作为定义集合的性质条件。 若用这样的谓词来确定集合会
9、产生悖论。 如：我只给不给自己理发的人理发。,集合的元素,集合的元素可以是任何类型的事物。 一个集合也可以作为另一个集合的元素。 例如，集合A=a, b, c,d, e 。 其中：a A，c,d A, e A, 但是：c A, e A。 在集合论中规定 元素之间是彼此相异的，并且是没有次序关系的。 如：3,4,5, 3,4,4,5, 5,3,4都是同一个集合。,A只有4个元素， 表示成|A|=4。,元素与集合隶属关系的层次结构,例 ： A= a, b,c, d, d b,cA bA d A d A dA,n元集含有n个元素的集合的简称； 一个集合的含有m个元素的子集称作它的m元子集。,9.2
10、集合间的关系和特殊集合,定义 设A, B为集合，如果B中的每个元素都是A中的元素，则称B为A的子集合，简称子集。 这时也称B被A包含，或A包含B。记作BA 或 AB。 “BA”的符号化表示为： BA (x)(xBx A) 如果不被包含，则记作B A ，符号化为： B A (x) (xB xA) 如：A=0,1,2, B=0,1, C=1,2 则有 BA, C A, 但C B。因为存在2，2C 但 2B 。,集合相等的定义,集合相等的定义： 设A、B为任意集合， 如果AB且BA，则称A与B相等。记为A=B。 如果A与B不相等，记为AB。 集合相等的谓词公式表示 A=B ABBA (x)(xAxB
11、)(x)(xBxA) (x)(xAxB) 结论：两个集合相等的充要条件是它们互为子集。,集合间的关系,例如： 设 A=1, 2，B=1, 2 ，C=2, 1 则 A=C AB 集合相等有下列性质： 设A、B、C为任意集合 自 反 性: A A A=A。 反对称性: （A B B A） B = A。 传 递 性: （A B B C） A C。,集合间的关系,集合间的关系 包含(子集) A B (x) (xA xB) 不包含 A B (x) (xA xB) 相等 A = B A B B A (x)(x A xB) 不相等 A B 真包含 A B A B A B (x)(xAxB)(x)(xBxA)
12、 不真包含 A B 思考： 和 的定义,空集与全集,空集 不含任何元素的集合。 如：A= x | x2+1=0xR = 定理：空集是任何集合的子集。 A x (xxA) T 推论：空集是唯一的. 证： 假设存在： 1和2， 由上面定理得： 12 且 21， 因此： 1=2 全集 E 在给定的问题中，所考虑的所有事物的集合称为全集，记作E。 在给定问题中，全集包含任何集合，即A (AE ) 全集的概念相当于谓词逻辑的论域,x(x ) = F,x(xE) = T,确定下列命题的真假：,(1) (2) (3) (4) ,解 ：(1)为真 (2)为假 (3)为真 (4)为真,注意： 和 是不同层次的问题,9.3 集合的运算,集合的基本运算 并集 AB = x | xA xB 交集 AB = x | xA xB 差集 A B = x | xA xB 余集 A = EA= x | xA （A的余集是A对E的相对补集） 对称差 AB = (AB)(BA) = (AB)(AB) = x | xA xB ,集合运算举例,已知：A=a, b, c, d , B=e, f, a, d 全集E=a, b, c, d, e, f, g 则 AB =a, b, c, d, e, f = BA AB =a, d = BA AB =b, c BA =e, f
