《曲靖师范学院《离散数学》课件-第2章 逻辑代数（下）：谓词演算》由会员分享，可在线阅读，更多相关《曲靖师范学院《离散数学》课件-第2章 逻辑代数（下）：谓词演算（52页珍藏版）》请在金锄头文库上搜索。
1、离散数学第离散数学第2 2章章 逻辑代数（下）：谓词演算逻辑代数（下）：谓词演算 2.12.12.1谓词演算基本概念谓词演算基本概念 2.22.22.2谓词演算永真式谓词演算永真式 2.32.32.3前束化和消去量词前束化和消去量词 第第2章章 逻辑代数逻辑代数（下下）：谓词演算：谓词演算 曲靖师范学院离散数学曲靖师范学院离散数学离散数学第离散数学第2 2章章 逻辑代数（下）：谓词演算逻辑代数（下）：谓词演算 问题问题1 1：为为何要何要何要何要讲谓词讲谓词演算？演算？演算？演算？例例例例1 1：数学中的常用判断无法用命数学中的常用判断无法用命题逻辑的形式准确描述。的形式准确描述。 如：如：
2、x 5 实数的平方非数的平方非负例例例例2 2：无法很好地刻画推理机制。无法很好地刻画推理机制。 如：如： 所有的人都是要死的所有的人都是要死的 苏格拉底是人格拉底是人 苏格拉底是要死的格拉底是要死的命命题演算不足的原因演算不足的原因忽略了命忽略了命忽略了命忽略了命题题内部的内部的内部的内部的细节细节。第第2章章 逻辑代数（下）：谓词演算逻辑代数（下）：谓词演算 离散数学第离散数学第2 2章章 逻辑代数（下）：谓词演算逻辑代数（下）：谓词演算 问题问题2 2：原子命：原子命：原子命：原子命题题内部究竟有那些内部究竟有那些内部究竟有那些内部究竟有那些细节细节？例例例例2 2： 所有的人都是要死的
3、所有的人都是要死的 苏格拉底是人格拉底是人 苏格拉底是要死的格拉底是要死的三个命三个命题涉及两个概念：涉及两个概念：1）表示事物的性）表示事物的性质： “是人是人”、“是要死的是要死的” 称称谓词谓词。2）表示主体：）表示主体： “所有的人所有的人”、“苏格拉底格拉底” 称称个体个体个体个体。 “所有的人所有的人”中中还使用了数量使用了数量词“所有所有”称称量量量量词词。第第2章章 逻辑代数（下）：谓词演算逻辑代数（下）：谓词演算 离散数学第离散数学第2 2章章 逻辑代数（下）：谓词演算逻辑代数（下）：谓词演算 2.1.1 个体个体2.1 谓词演算基本概念谓词演算基本概念个体：个体：个体：个体
4、：谓词谓词演算中的一切演算中的一切演算中的一切演算中的一切讨论对讨论对象。象。象。象。 个体可以是客个体可以是客观世界中的具体客体，也可以是抽象的客世界中的具体客体，也可以是抽象的客 体，体，诸如数字、符号等。如数字、符号等。确定的个体确定的个体确定的个体确定的个体：常用常用a，b，c 等小写字母或字母串表示。等小写字母或字母串表示。 个体常元个体常元个体常元个体常元不确定的个体不确定的个体不确定的个体不确定的个体：常用字母常用字母 x，y，z，u，v，w 等表示。等表示。 个体个体个体个体变变元或元或元或元或变变元元元元 离散数学第离散数学第2 2章章 逻辑代数（下）：谓词演算逻辑代数（下）
5、：谓词演算 2.1.1 个体个体2.1 谓词演算基本概念谓词演算基本概念个体域：个体域：个体域：个体域：讨论对讨论对象（个体）的全体。象（个体）的全体。象（个体）的全体。象（个体）的全体。 集合集合论中的全集（中的全集（D D），任何），任何D都至少含有一个成都至少含有一个成员。 当当讨论对象遍及一切客体象遍及一切客体时，个体域特称，个体域特称为全全全全总总域域域域（U U）。当当给定个体域定个体域时：常元表示：常元表示该域中的一个确定的成域中的一个确定的成员； 变元可以取元可以取该域中的任何一个成域中的任何一个成员为其其值。个体个体个体个体项项：由由D上个体上个体间运算的运算符、常元、运算的
6、运算符、常元、变元元组成。成。 如：如： a2+b x2c离散数学第离散数学第2 2章章 逻辑代数（下）：谓词演算逻辑代数（下）：谓词演算 谓词谓词：表示个体性：表示个体性：表示个体性：表示个体性质质或个体之或个体之或个体之或个体之间间关系。关系。关系。关系。例如：例如：例如：例如：M(x)：“苏格拉底是人格拉底是人”中中“是人是人” 整个整个语句句为M(Socrates)。 D(x)：“苏格拉底是要死的格拉底是要死的”中中“是要死的是要死的” 整个整个语句句为D(Socrates)。又如：又如：又如：又如：“3是小于是小于2”可表示可表示为： L(3,2) （L(x,y)：x小于小于y） “
7、3加加2等于等于5”可表示可表示为： ADD(3,2,5) （ADD(x,y,z)：x加加y等于等于z） 2.1.2 谓词谓词2.1 谓词演算基本概念谓词演算基本概念离散数学第离散数学第2 2章章 逻辑代数（下）：谓词演算逻辑代数（下）：谓词演算 “x是小于是小于100的的质数数”可表示可表示为: L(x,100)P(x) （L(x,100)：x小于小于100；P(x)：x是是质数）数）“小小张是教是教师，或者是工程，或者是工程师”可表示可表示为: T(xiaozhang)E(xiaozhang) （xiaozhang：小：小张；T(x)：x是教是教师；E(x)：x是工程是工程师）“如果一个人
8、生于北京，那么他不生于上海如果一个人生于北京，那么他不生于上海”可表示可表示为: B(x,beijing)B(x,shanghai) （B(x,y)：x生于生于y）2.1.2 谓词谓词2.1 谓词演算基本概念谓词演算基本概念离散数学第离散数学第2 2章章 逻辑代数（下）：谓词演算逻辑代数（下）：谓词演算 2.1.3 量词量词2.1 谓词演算基本概念谓词演算基本概念量量量量词词：指数量指数量词“所有的所有的”（“每一个每一个”）和）和“有有”，分，分别用符用符号号 和和 来表示，来表示， 称称为全称量全称量全称量全称量词词和和存在量存在量存在量存在量词词。量量量量词词的表示和意的表示和意的表示和
9、意的表示和意义义： xPxP( (x x) ) ：读作作“所有（任意，每一个）所有（任意，每一个）x满足足P(x)”。 表示个体域中所有的个体表示个体域中所有的个体满足足谓词P(x)。 xPxP( (x x) )： 读作作“有（存在，至少有一个）有（存在，至少有一个）x满足足P(x)”。 表示个体域中至少有一个体表示个体域中至少有一个体满足足谓词P(x)。 x x ： 量量词的的指指指指导变导变元元元元，填在，填在谓词P(x) 中。中。离散数学第离散数学第2 2章章 逻辑代数（下）：谓词演算逻辑代数（下）：谓词演算 关于量关于量关于量关于量词词的的的的说说明：明：明：明：(1)(1) x x
10、称称指指指指导变导变元元元元，其名字不重要，其名字不重要 量量词的指的指导变元和量元和量词“管管辖” 的的谓词填式中的填式中的变元是可以元是可以改名改名改名改名的。的。(2)(2) 量量词不不仅可用于可用于谓词填式之前，填式之前，还可用于复合的可用于复合的谓词表达式表达式 之前，之前，这时应对该表达式使用括号。表达式使用括号。 如：如： x(M(x)B(x) （有的个体是人且是勇敢的）（有的个体是人且是勇敢的） x(M(x)D(x) （所有个体中凡人者是要死的）（所有个体中凡人者是要死的） x(L(x,2)L(x,2) （所有个体或者小于（所有个体或者小于2或者不小于或者不小于2） x y z
11、 (ADD(x,y,z)ADD(y,x,z) （数的加运算（数的加运算满足交足交换律）律） 2.1.3 量词量词2.1 谓词演算基本概念谓词演算基本概念离散数学第离散数学第2 2章章 逻辑代数（下）：谓词演算逻辑代数（下）：谓词演算 量量量量词词的的的的辖辖域：域：域：域： 当量当量词用于用于谓词填式或复合的填式或复合的谓词表达式表达式时，该谓词或复合或复合 的的谓词表达式称表达式称为量量词的的辖域。域。 量量词的的辖域或者是域或者是紧邻其右其右侧的那个的那个谓词；或者是其右；或者是其右侧第第 一一对括号内的表达式。括号内的表达式。 (3) (3) 约约束束束束变变元和自由元和自由元和自由元和
12、自由变变元：元：元：元： xP(x) 和和 xP(x)中的中的变元元 x 可以改名却不能取可以改名却不能取值代入。代入。 通常通常谓词填式中的个体填式中的个体变元可以取元可以取值代入。代入。 xPxP( (x x) ) 和和和和 xPxP( (x x) ) 中中中中变变元称元称元称元称为约为约束束束束变变元元元元 可以取可以取可以取可以取值值代入的代入的代入的代入的变变元元元元则则称称称称为为自由自由自由自由变变元元元元。 2.1.3 量词量词2.1 谓词演算基本概念谓词演算基本概念离散数学第离散数学第2 2章章 逻辑代数（下）：谓词演算逻辑代数（下）：谓词演算 (4)(4) xP(x)是一命
13、是一命题，断言所有个体，断言所有个体满足性足性质P(x)，其真，其真值确定。确定。 xP(x) 也是命也是命题。当个体域中个体有当个体域中个体有穷时，例如，例如D = a1, ,an ， xP(x) 的意的意义与命与命题 P(a1)P(an) 等同等同 xP(x) 的意的意义与命与命题P(a1)P(an) 等同。等同。 2.1.3 量词量词2.1 谓词演算基本概念谓词演算基本概念离散数学第离散数学第2 2章章 逻辑代数（下）：谓词演算逻辑代数（下）：谓词演算 例例例例2.12.1： (1)(1) x x( (A A( (x x)B B( (x x) )C C( (x x) ) x的的辖域是域是
14、A(x)B(x)，其中的，其中的x是是约束束变元；元； C(x) 不在不在 的的辖域内，其中的域内，其中的x是自由是自由变元；元； (2)(2) x x A A( (x x) )B(B(x x) ) x的的辖域是域是A(x)，其中，其中x是是约束束变元，元， B(x)中中x为自由自由变元。元。 可改可改为： y y( (A A( (y y)B B( (y y) )C C( (x x) ) y y A A( (y y) )B B( (x x) ) (3)(3) 约定个体域定个体域为 0，1，2 y(y2=y) 等价于等价于 02=012=122=2 ，此，此为假。假。 y(y2=y) 等价于等价
15、于 02=012=122=2 ，此，此为真。真。2.1.3 量词量词2.1 谓词演算基本概念谓词演算基本概念离散数学第离散数学第2 2章章 逻辑代数（下）：谓词演算逻辑代数（下）：谓词演算 2.1.4 谓词公式及语句的形式化谓词公式及语句的形式化2.1 谓词演算基本概念谓词演算基本概念定定定定义义2.12.1 归纳定定义谓词谓词公式公式公式公式（又称（又称合式公式合式公式合式公式合式公式，简称称公式公式公式公式）。（1 1）谓词填式是公式，命填式是公式，命题常元是公式（看作零元常元是公式（看作零元谓词），常称），常称 原子公式原子公式原子公式原子公式。（2 2）如果如果A，B是公式，是公式，x
16、为任一任一变元，那么元，那么(A)，(AB)，( xA)， ( xA)（当使用五个（当使用五个联结词时还有有(AB)，(AB)，(AB)） 都是公式。都是公式。（3 3）终极条款，略。极条款，略。 （括号省略原（括号省略原则同命同命题公式，公式， ( xA)、( xA)的最外的最外层括号可省）括号可省）离散数学第离散数学第2 2章章 逻辑代数（下）：谓词演算逻辑代数（下）：谓词演算 2.1.4 谓词公式及语句的形式化谓词公式及语句的形式化2.1 谓词演算基本概念谓词演算基本概念例例例例2.22.2 以下均以下均为公式公式 ADD(x,y,z) x(M(x)D(x) x(A(x)B(x) x y( B(x,y)M(y) yL(3,2) x L(x,2) 其中其中 x y(B(x,y)M(y)是是 x ( y( B(x,y) M(y)的的简写。写。注意：注意：注意：注意： yL(3,2)也是公式，尽管也是公式，尽管L(3,2)中没有中没有变元元y。 yL(3,2)被理解被理解为L(3,2)。 一般地，当一般地，当A中无中无变元元x时， xA， xA，均被看作与，均被看作与A相同。相同。 离
