离散数学讲义第三章谓词逻辑.ppt

《离散数学讲义第三章谓词逻辑.ppt》由会员分享，可在线阅读，更多相关《离散数学讲义第三章谓词逻辑.ppt（58页珍藏版）》请在装配图网上搜索。

1、第三章 谓词逻辑 在命题逻辑中，命题被当作一个基本的，不可分割的单位，只研究由原子命题和联结词所组成的复合命题；因而无法研究命题的内部结构及命题之间内在的联系。本章介绍的谓词逻辑，对原子命题的成份、结构和原子命题间的共同特性等作了进一步分析。引入了个体词、谓词、量词、谓词公式等概念，在此基础上研究谓词公式间的等值关系和蕴含关系，并且对命题逻辑中的推理规则进行扩充和进行谓词演绎。,主要内容如下： 3.1、 3.2 谓词的概念与表示; 命题函数和量词 3.3 3.5 谓词演算的合适公式; 变元的约束 ; 谓词公式的解释 3.6 谓词演算的永真式 3.7 谓词演算的推理理论,3.1、3.2 谓词、命

2、题函数和量词,例 判断下述论断的正确性 “苏格拉底三段论” ： 凡人都是要死的， 苏格拉底是人， 所以苏格拉底是要死的。,类似的例子 还有许多。 例如： 所有的人都要呼吸 , 所有的正整数都大于0, 李莉是人 , 3是正整数, 所以李莉要呼吸。 所以3大于0。,一、谓词 在谓词演算中，可将原子命题分解为谓词与个体词两部分。,定义3.1.1 个体是指可以独立存在的客体。 注个体可以是抽象的，也可是具体的。个体通常在一个命题里表示思维对象。,定义3.2.2 用来刻划个体的性质或个体之间关系的词称为谓词，刻划一个个体性质的词称为一元谓词；刻划n个个体之间关系的词称为n元谓词。 例1 （1）李明是学生

3、； （2）张亮比陈华高； （3）陈华坐在张亮与李明之间。,在这三个命题中，李明、张亮、陈华都是个体；“是学生”是一元谓词， “比高”是二元谓词， “坐与之间”是三元谓词。,通常，我们用大写字母表示谓词，小写字母表示个体。,一般地，一个由n个个体和n元谓词所组成的命题可表示为F（a1,a2, ,an）,其中F表示n元谓词, a1,a2, ,an 分别表示n个个体。,上述命题可分别表示为 Q（a）, P（b,c），R（c,b,a）。,注意：a1,a2, ,an的排列次序是重要的。,二、个体变元和命题函数 个体常元 表示具体或特定的个体的个体词称为个体常元。 个体变元 表示抽象的，或泛指的（或者说取

4、值不确定的）个体称为个体变元。,例2 设 H是表示谓词“能够到达山顶”，若个体w:王红；t：老虎；s：汽车，则H（w），H（t），H（s）分别表示“王红能够到 达山顶。”“老虎能够到达山顶。”“汽车能够到达山顶。”这里w、t、s均是个体常元。 H（x）：x能够到达山顶。这里的x是泛指的，不确定的，x可在一定的范围内取值。故x是个体变元。,例3 L（x,y,z）表示“x+y=z”,其中x,y,z为个体变元。 L（3，2，5）表示真命题“3+2=5”， 而L（1，2，4）表示假命题“1+2=4”。,定义2.3.3 由一个谓词和若干个个体变元组成的命题形式称为简单命题函数，表示为P（x1,x2,xn

5、）。由一个或若干个简单命题函数以及逻辑联结词组成的命题形式称为复合命题函数。,例如 H（x），L（x,y,z）均是简单命题函数。,在命题函数中，个体变元的取值范围称为个体域。,例4 P（x,y）表示“2 x+y=1”，若x,y的个体域为正整数集，则总是假； 若x,y的个体域为有理数集，则y=12x，对任意的有理数k ，在x= k，y =12k时，P（ k，12k）为真。,三、量词和全总个体域,量词 在命题里表示数量的词。,（1） 全称量词 “ x” 如“所有人都是要死的。”可表示为 x D（x）， x的个体域为全体人的集合。,（2）存在量词 “x ”,（3）存在唯一量词 “ !x ”,如 “有

6、些有理数是整数。” 令(x）：x是整数； 于是命题可表示为 x(x） 其中x的个体域为有理数集合。,如 “方程x+1=0存在唯一的整数解。” 令P（x）：x是x+1=0的整数解。 则命题可表示为 !x P（x）， 其中x的个体域为整数集。,2全总个体域 含有量词的命题的表达式的形式，与个体域有关。,含有量词的命题的真值与个体域也有关。因此，为了方便，我们引入全总个体域的概念。,定义3.1.5 宇宙间所有的个体聚集在一起所构成的集合称为全总个体域。 后面的讨论中，除特殊说明外，均使用全总个体域。而对个体变化的真正取值范围，用特性谓词加以限制。,一般地，对全称量词，此特性谓词作蕴含的前件；对存在量

7、词，此特性谓词常作合取项。,当取x的个体域为全总个体域时，必须引入一个特性谓词将人从全宇宙的一切事物中分离出来。,（1）对所有个体而言，如果它是人，则它是要死的。 ( 2）存在着个体，它是人并且它活百岁以上。,令D（x）：x是要死的。则（1）可表示为 x D（x）。 令G（x）：x活百岁以上。则（2）可表示为 x G（x）。,例5 (1) “所有的人都是要死的。” (2) “有的人活百岁以上。” 当x的个体域E为全体人组成的集合时，符号化上述命题。,于是令M（x）：x是人。 （1） x（M（x） D（x） （2） x（M（x）G（x）,解 令P（x）：x发光；G（x）：x是金子。,（2）所有运

8、动员都钦佩某些教练。,解 令P（x）：x是运动员；T（x）：x是教练；Q（x，y）：x钦佩y。,则可表示为 或,则该命题可表示为,（3）凡是实数均能比较大小。,解 令R（x）：x是实数；G（x,y)：x与y可比较大小.,例7 将下列命题符号化 （1）会叫的狗未必咬人。,解 令D（x）：x是狗；P（x）：x会叫；Q（x）：x咬人。,则可表示为 或表示为,则该命题可表示为,或者令Q（x,y）:xy;,（3）不是一切人都一样高。,（2）一切人不是一样高。,解 M(x)：x是人；G(x,y):x与y一样高 ; H(x,y):x与y是不同的人。 可表示为,可表示为,或者表示为,3.3 谓词演算的合适公式

9、,一、谓词公式,定义3.3.1 （谓词公式的递归定义。） ( 1）命题常元、命题变元和简单命题函数都是谓词公式。 （2）如果A是谓词公式，则 A也是谓词公式。 （3）如果A和B是谓词公式，则（AB）,(AB）, (A B) , (A B) 也 是谓词公式。 （4）如果A是谓词公式，x是A中的个体变元，则 和 也是谓词公式。 （5）只有由使用上述四条规则有限次而得到的才是谓词公式。,例1 苏格拉底三段论可用谓词公式表示。,令M（x）：x是人；D（x）：x是要死的； a：苏格拉底,例2 给出“x+y3”的谓词公式的表示形式。,解 令P（x,y,z）：x+yz,则上述表达式可用谓词公式表示为P（x,

10、y,3）。,则三段论可表示为 ( x（M（x） D（x） M（a）) D（a）,例1 令 P（x, y）：“ xy ”，Q（x）：x是有理数；F（x）：x可以表示为分数。判断下列式子那些是命题函数，那些是命题？ P（x, y）,P（x, y） Q（x）,3.4 变元的约束,Q（x） F（x）,当x的出现不是约束出现时，称x的出现是自由出现。 自由出现的变元是自由变元。,公式中约束出现的变元称约束变元,一个给定的谓词公式P中，形如 或 的那一部分称为公式的x约束部分。而A（x）称为量词 x或 x的辖域。x在公式的x约束部分的任一出现都称为x的约束出现。,一、约束变元与自由变元,x,y,z在公式中

11、的所有出现均是约束出现，故它们均是约束变元。,例3 指出下列各公式中的量词辖域及自由变元和约束变元。,解 是 的辖域。 是 的辖域. R(z）是 z的辖域。,解 P（x，y） yQ（x，y，z）是 x的辖域，在这一部分中，x是约束出现 ，故x是约束变元，在P（x，y）中的y是自由出现，故y为自由变元。但Q（x， y ，z）是 y的辖域，因而在Q（x， y ，z）中y却是约束出现，故此时y是约束变元，z是自由变元。在S（x，z）中x，z是自由变元。,二、换名规则和代入规则 1.换名规则 对约束变元进行换名，使得一个变元在一个公式中只呈一种形式出现。,（1）约束变元换名时，该变元在量词及其辖域中的

12、所有出现均须同时更改，公式的其余部分不变； （2）换名时，一定要更改为该量词辖域中没有出现过的符号，最好是公式中未出现过的符号。,解需对x，y换名,错误法：,例4对公式 进行换名，使各变元只呈一种形式出现。,2. 代入规则 对于公式中自由变元的更改叫做代入。,3.5 谓词公式的解释,定义3.5.1 对谓词公式A的解释I包括以下几点： 1) 指定一个论域D 2) 对A中出现的每一个n元函数，指定一个D上的 n元个体函数常量 3)对A中出现的每一个n元谓词，指定一个D上的n元谓词常量 4)对A中出现的每一个个体常量及自由变元，指定D中的一个个体常量 5)对A中出现的每一个命题变元P，指派一个真值T

13、或F 由此得到一个命题AI，称AI的真值为合适公式A在解释I 下的真值,例 取解释I如下： 1）D=1,2, 2）定义D上的二元谓词P真值为 P(1,1): T； P(1,1): F； P(2,1):F； P(2,2): T 则 和 在解释I下的真值分别为,T 和F,3.6 谓词演算的永真式,一、公式的类型,定义3.6.1 给定谓词公式A，其个体域为E，如果对于E上的任一组解释，公式A的值总是为真，则称A在E上是永真的。如果对于公式A的任一组解释，公式A的值总是为假，则称A在E上是永假的。如果至少存在着一组指派，使公式A的值为真，则称A在E上是可满足的。,例1 试说明下列各公式的类型（个体域取

14、为全总个体域）,（1） （2） （3） F(x) （其中F(x): x+6=5） （4）,解 (1) 永真公式,(2) 可满足公式,(3) 可满足公式,(4) 永假公式,解 （1） 可满足公式。,（2） 永假公式。,（3） 永真公式。,（4） 可满足公式。,例2 试说明下列各公式的类型。 （1） （2） （3） （4）P（x，y） 其中x，y的个体域为R；谓词P（x，y）：x=y； Q是命题变元.,定义3.6.2设A、B是两个公式，它们有共同的个体域E，若对于A和B的任意一组指派，两公式都具有相同的真值，则称公式A和B在E上等价，记作A B。,定义3.6.3对于公式A和B，若A B 1，则称公

15、式A蕴含公式B，记作A B。,二、谓词演算中的等价式和蕴涵式,定理3.6.1 (代入定理） 设A是命题逻辑中的永真式，则用谓词逻辑的合适公式代替A中的某些命题变元得到的代换实例也是永真式；如果A是永假式，则上述代换实例也是永假式。,例如,例如,又例如,1.命题演算的推广,2. 全称量词和存在量词间转化的等价式,（其中A(x)是任意的公式）,3.量词辖域扩展与收缩的等价式 1.,证明 设个体域 ,则,（2） ,证明,证明 （1） “个体域中每一个体x，使得A(x)与B(x)均为真”与 “个体域中每一个体x，使得A(x)为真且每一个体x使得B(x)为真”具有相同的含义.,（1）,证明 由得,证明

16、（2） 由（2） 得,（2） ,即,即,故,证明 （1）,5.量词与联结词的关系,证明,因此在个体域中必存 在某个体a使B(a)为假，但A(a)为真。,证明 设 为假， 则 为真， 为假。,于是 为假，因此 为假。,故,由此 永真。,6.多个量词的量化次序,3.7 谓词演算的推理理论,2、与量词有关的推理规则,1. US(全称特定化规则),使用此规则时要注意： （1）y为任意不在A(x)中约束出现的个体变元； （2）c为任意的个体常元 。,例如：设A(x,y):xy 考查 x yA(x,y):xy 可得到结论 yA(z,y) 但不能得出结论 yA(y,y),使用此规则时应注意： （1）c 是使

17、A为真的特定个体常元； （2）c不在A（x)中出现 （3）如果A(x)中有其他自由变元出现，且x是随其他自由变元变化的，那么不能使用此规则。,2.ES（存在特定化规则）,yA(z,y),例如：设A(x,y):xy，考查如下推理过程是否正确 x yA(x,y),A(z,c),3. UG（全称一般化规则）,使用此规则时注意: (1) y在A(y)中自由出现，且y取任何值时A均为真。 (2) x不在A(y)中约束出现,是错误的!,4、EG（存在一般化规则）,使用此规则时注意: (1) C是个体域中某个确定的个体。 (2) 代替C的x不能已在A(c)中出现。,是错误的!,解 令M(x):x是人; D(

18、x):x是要死的; c:苏格拉底。,于是苏格拉底三段论可表示为：,证明（1）M(c) P,（2） P,（3） T（1）;US,（4）D(c) T(1),(3);I,例2 证明,（3） C(a) Q(a) T（2）;ES,证明 （1） P,（2） P,（4） T（1）;US,（5） C(a) T（3）；I,（6） W(a) R(a) T（4）,（5）；I,（7） Q(a) T（3）；I,（8） R(a) T（6）；I,（9） Q(a) R(a) T（7）,（8）；I,（10） T（9）;EG,例3 证明,证明 （1） 附加前提,（2） T（1）；E,（6） Q(c) T（3）,（5）；I,（7）

19、 T（6）;EG,（3） T（2）;ES,（4） P,( 5 ) T（4）;US,例4 证明,（1） 附加前提,（2） T（1）；E,证法一 : (间接证明法),（3） T（2）；I,（4） T（2）；I,（5） T（4）；I,（6） T（3）；E,（7） T（6）;ES,（8） T（5）;US,（9） T（7）（8）；I,（10） T（9）；E,（11） P,（12） T（11）;US,（13） T（10）（12）;I,证法二 （1） 附加前提,（2） T（1）；E,（3） P,（4） T（2）;ES,（5） T（3）;US,（6） T（4）（5）；I,（7） T（6）;EG,（8） T（1

20、）（7）；CP,（9） T（8）；E,原题可转化为证明,证明（1） P,（2） T（1）；I,例5 指出下面推理的错误.,（3） T（1）；I,（4） T（2）;ES,（5） T（3）;ES,（6） T（4）（5）；I,（7） T（6）;EG,因此,例6 指出下面推理的错误. 设D(x,y)表示“x可被y 整除” ,个体域 为 5,7 ,10 ,11 . 因为D(5，5)和D(10,5)为真，所以 xD(x,5)为真. 因为D(7，5)和D(11,5)为假，所以 xD(x,5)为假.,但有下面的推理过程： (1) xD(x,5) P (2) D(z,5) T(1);ES (3) xD(x,5)

21、 T(2);UG 因此， xD(x,5) xD(x,5).,例7 对多个量词的使用情况，观察下列推理过程.,证明（1） 前提,（2） US（1）,（3） ES（2）,（4） UG（3）,（5） EG （4）,推出错误结论： 与 可交换.,习 题,1 将下列命题符号化.,（1）在上海高校学习的学生，未必都是上海籍的学生。,解 令 H(x)：x是在上海高校学习的学生 S(y)：y是上海籍的学生 或者,（2）没有一位女同志既是国家选手又是家庭妇女。,解 令W(x):x是一位女同志； C(x):x是国家选手； H(x):x是家庭妇女 x(W(x)C(x)H(x),（3）对于每一个实数x，存在一个更大的

22、实数y。,解 令R(x)：x是实数； G(x,y):x比y大。 x(R(x) y(R(y)G(y,x),（4）某些汽车比所有的火车都慢，但至少有一列火车比每辆汽车快。,解 令C(x)：x是汔车；H(x)：x是火车； S(x,y): x比y慢。,解 对 x(P(x) (R(x)Q(x)中的x换为y. xR(x)中的x换名为t得,3.将下面谓词公式中的自由变元进行代换.,解 对 y(P(x,y)中的自由变元x和 Q(x,z)中的自由变元x代换为t , 对 x(R(x,y) 中的自由变元y代换为s得,4. 用构造推理过程的方法证明,证明,证明,T(1);US,T(2);US,T(3),(4);I,T(5);E,前提,前提,证明,T(3):I,T(4):I,T(1),(5):I,T(4):I,T(2),(7):I,T(8):ES,T(6):US,T(9),(10):I,T(11):EG,T(3),(12):CP,5.符号化下述命题,并推证其结论。 “所有有理数是实数，某些有理数是整数，因此某些实数是整数。”,解 先将命题符号化 令Q(x):x是有理数；R(x):x是实数;I(x);x是整数.,证明,T(1);ES,T(2);US,T(3);I,T(4),(5);I,T(3);I,T(6),(7);I,T(8);EG,