交大数理逻辑课件5-3谓词逻辑的等值和推理演算.ppt

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