操作系统第2章谓词演算

《操作系统第2章谓词演算》由会员分享，可在线阅读，更多相关《操作系统第2章谓词演算（46页珍藏版）》请在金锄头文库上搜索。

1、1第二章 谓词演算在命题逻辑中，命题被当作一个基本的，不可分割的 单位，只研究由原子命题和联接词所组成的复合命题；因 而无法研究命题的内部结构及命题之间内在的联系。本章 介绍的谓词逻辑，对原子命题的成份、结构和原子命题间 的共同特性等作了进一步分析。引入了个体词、谓词、量 词、谓词公式等概念，在此基础上研究谓词公式间的等值 关系和蕴含关系，并且对命题逻辑中的推理规则进行扩充 和进行谓词演绎。主要内容如下：1 谓词、合式公式和量词2 谓词演算的等价式与蕴含式3 前束范式4 谓词演算的推理理论22.1 谓词概念 例 在命题逻辑中 ，对下述论断无法判断其正确性。 “苏格拉底三段论” ：凡人都是要死的

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

3、 ；“是学生”是一元谓词， “比高”是二元谓词 ， “坐与之间”是三元谓词。4通常，我们用大写字母表示谓词，小写字母表示个体。上述命题可分别表示为 Q（a）, P（b,c），R（c,b,a）。一般地，一个由n个个体和n元谓词所组成的命题可表示为F（a1,a2, ,an）,其中F表示n元谓词, a1,a2, ,an 分别表示n个个体。注意：a1,a2, ,an的排列次序是重要的。5二、个体变元和命题函数个体常元 表示具体或特定的个体的个体词称为个体常元。个体变元 表示抽象的，或泛指的（或者说取值不确定的）个体称为个体变元。例2 设 H是表示谓词“能够到达山顶”，若个体w:王红；t：老虎；s：汽车

4、，则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”。62.2、量词和全总个体域 量词 在命题里表示数量的词。1.量词使用前面介绍的概念，还不足以表达日常生活中的各种命题。例如：对于命题 “ 所有的正整数都是素数 ” 和“ 有些正整数是素数 ”仅用个体词和谓词是很难

5、表达的。 （1） 全称量词 “ x” 如“所有人都是要死的。”可表示为 x D（x），x的个体域为全体人的集合。 7（2）存在量词 “ x ” （3）存在唯一量词 “ !x ” 如 “有些有理数是整数。”令(x）：x是整数；于是命题可表示为 x(x）其中x的个体域为有理数集合。如 “方程x+1=0存在唯一的整数解。”令P（x）：x是x+1=0的整数解。则命题可表示为 !x P（x），其中x的个体域为整数集。82个体域含有量词的命题的表达式的形式，与个体域有关。含有量词的命题的真值与个体域也有关。因此，为了方便，我们引入个体域的概念。 定义25 宇宙间所有的个体聚集在一起所构成的集合称为全总个体

6、域。后面的讨论中，除特殊说明外，均使用全总个体域。而对个体变化的真正取值范围，用特性 谓词加以限制。 一般地，对全称量词，此特性谓词作蕴含的前件；对存在量词，此特性谓词常作合取项。9当取x的个体域为全总个体域时，必须引入一个特性谓 词将人从全宇宙的一切事物中分离出来。 （1）对所有个体而言，如果它是人，则它是要死的。( 2）存在着个体，它是人并且它活百岁以上。 令D（x）：x是要死的。则（1）可表示为 x D（x）。令G（x）：x活百岁以上。则（2）可表示为 x G（x）。 例5 (1) “所有的人都是要死的。”(2) “有的人活百岁以上。”当x的个体域E为全体人组成的集合时，符号化上述命题。

7、于是令M（x）：x是人。（1） x（M（x） D（x） （2） x（M（x）G（x） 10四命题符号化 例6 将下列命题符号化(使用全总 个体域)。(1) 发光的不都是金子解 令P（x）：x发光；G（x）：x是金子。 （2）所有运动员都钦佩某些教练。 解 令P（x）：x是运动员；T（x）：x是教练； Q（x，y）：x钦佩y。 则可表示为 或则该命题可表示为 11（3）凡是实数均能比较大小。 解 令R（x）：x是实数；G（x,y)：x与y可比较大小. 例7 将下列命题符号化（1）会叫的狗未必咬人。解 令D（x）：x是狗；P（x）：x会叫；Q（x）：x咬人。 则可表示为 或表示为 则该命题可表示为

8、 或者令Q（x,y）:xy;12（3）不是一切人都一样高。 （2）一切人不是一样高。 解 M(x)：x是人；G(x,y):x与y一样高 ; H(x,y):x与y是不同的人。可表示为 可表示为 或者表示为133 谓词合式公式一、合式公式定义2-6 （谓词公式的递归定义。） ( 1）命题常元、命题变元和简单命题函数都是谓词公式。（2）如果A是谓词公式，则 A也是合式公式。（3）如果A和B是谓词公式，则（AB）,(AB）, (A B) , (A B) 也 合式公式。（4）如果A是谓词公式，x是A中的个体变元，则 和 也是合式公式。（5）只有由使用上述四条规则有限次而得到的才是合式公式。14例1 苏格

9、拉底三段论可用合式公式表示。 令M（x）：x是人；D（x）：x是要死的；a：苏格拉底 例2 给出“x+y3”的谓词公式的表示形式。 解 令P（x,y,z）：x+yz 则上述表达式可用谓词公式表示为P（x,y,3）。 则三段论可表示为( x（M（x） D（x） M（a）) D（a） 15二、约束变元和自由变元 个体变元有自由变元和约束变元之分.例3 “x是整数”可以表示为Q（x），它是一个命题函数，而不是命题。例4 “ x yQ（x，y，z）是 x的辖域，在这一部分中，x是约束出现 ，故x是约束变元，在P（x，y）中的y是自由出现，故y为自由变元。但Q（x， y ，z）是 y的辖域，因而在Q（x

10、， y ，z）中y却是约束出现，故此时y是约束变元，z是自由变元。在S（x，z）中x，z是自由变元。192.3 谓词演算的等价式和蕴含式指派 一组代入到谓词公式中，并使得谓词公式成 为命题的确定的个体和命题称为公式的一组指派。一、公式的类型一个谓词公式一般含有个体变元、命题变元和谓 词，只有当公式中的自由变元用某个体域中确定的个 体代入，命题变元用确定的命题代入后，原公式才变 成为一个命题。 定义2-7 给定谓词公式A，其个体域为E，如果 对于任一组指派，公式A的值总是为真，则称A在E上式 永真的。如果对于公式A的任一组指派，公式A的值总是 为假，则称A在E上是永假的。如果至少存在着一组指派

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

12、，记作A B。定义2-9 对于公式A和B，若A B 1，则称公式 A蕴含公式B，记作A B。谓词演算中的等值式和蕴涵式在命题演算中，任一等值式或蕴涵式，其中同一命题变元，当用同一命题公式取代时，其结果仍是等值式或蕴涵式。二、公式的等值与蕴含1.命题公式的推广23将此情况推广到谓词公式中，用谓词公式去取代命题演算中等值式或蕴涵式的命题变元时，便得到谓词演算的等值式或蕴涵式。例如例如又例如242. 全称量词和存在量词间转化的等值式（其中A(x)是任意的公式） 对个体域是有限时，给出其证明。证明 设个体域 ,则253.量词辖域扩展与收缩的等值式1.证明 设个体域 ,则26（2）证明27证明 （1）

13、“个体域中每一个体x，使得A(x)与B(x)均为真”与 “个体域中每一个体x，使得A(x)为真且每一个体x使得B(x)为真”具有相同的含义.4. 量词分配等值式与蕴涵式（1）28（1） 证明 由得29证明 （1）5.量词与联结词的关系30证明因此在个体域中必存 在某个体a使B(a)为假，但A(a)为真。证明 设 为假，则 为真， 为假。于是 为假，因此 为假。故由此 永真。312.4前束范式 2.4.1.定义： 一个公式如果量词都在全式的开头，它们的作用域 延伸到整个公式的末尾，则称该公式为前束范式 。前束范式有如下形式：(Q1V1 ) (QnVn ) A 例如， xyz(P(x，y)Q(x，z) xyzP(x，y，z)32定理：任意一个谓词公式均和一个前束范式等价。例：把下列公式化为前束范式（1）xG(x)xH(x)xG(x)xH(x) =xG(x)yH(y) 换名规则 =x(G(x)yH(y) 引理1 =xy(G(x)H(y) 引理1332.5 谓词演算的推理理论 一、推理规则命题演算中的推理规则，可在谓词推理理 论中应用。在谓词演算中，推理的形式结构仍为 若 是永真式，则称由前提 逻辑的推出结论C，在此