离散数学 第7章 谓词逻辑

1、离 散 数 学第3编 数理逻辑第七章第七章 谓词逻辑谓词逻辑7.1 谓词的概念及表示 一、命题的构成 原子命题是由主语和谓语两部分构成的。 主语个体词 主语的取值范围称为个体域 个体(客体)常用a、b、c等表示。 谓语表述客体的性质和客体间关系的词。 谓语(谓词)常用A(x)、B(x)、P(x,y)等表示。 谓词不是命题，只有当谓词中的变项取定具体的个体值时才是命题。 所以，A(a)、B(a)、F(a,b)等才是命题。一、命题函数1简单命题函数 表示一般谓词的式子如A(x)、P(x,y)，称为简单命题函数。2。复合命题函数 有限个简单命题函数和联结词 组成的表达式称为复合命题函数。3。命题函数

2、本身不是命题，只有命题函数中的变元取得特定的值后才是命题。 ,7.2 命题函数与量词 二、量词表达个体在个体域中取值情况的词称为量词。量词有全称量词和存在量词两种。 1。全称量词 表示个体的取值情况为“所有的”、“每一个”等。特性谓词后面用 联结。例如，命题：所有的素数都是整数，符号化为：A(x):x是素数，H(x):x是整数，2。存在量词 表示个体的取值情况为“存在某个”、“至少有一个”等。特性谓词后面用 联结。例如，命题：有的素数是偶数，符号化为：A(x):x是素数，M(x):x是偶数，)()()(xHxAx)()()(xMxAx2000年1月选择题1 = 2006年1月填空题7 设F(x

3、):x是鸟，G(x):x会飞，命题“鸟都会飞”符号化为 。 A） B） C） D）再如课本P.42 (B) 1设A(x):x是人，B(x):x犯错误，命题“没有不犯错误的人”可符号化为 。解：原命题的意思是：不存在不犯错误的人。符号化为：)()()(xGxFx)()()(xGxFx)()()(xGxFx)()()(xGxFx)()()(xBxAxB三、多个量词的使用 包含有多个个体的命题，可能会对不同的个体使用不同的量词。对这样的命题符号化时要注意：1。量词的顺序不能改变，否则会改变命题的含义。2。特性谓词后面的联结符通常由括号最前面的量词决定。例如， 2000年7月填空题6设N(x):x是自

4、然数，H(x,y):y是x的后继数，命题“每个自然数都有后继数”可符号化为 。解：),()()()()(yxHxBxAyx),()()()()(yxHxBxAyx),()()()()(yxHyNyxNx2000年7月选择题2 设个体域为整数，下列公式中真值为1的是 A） B） C） D）解：各答案的意义是：任取一个x和任取一个z，都满足x+z=0任取一个x，存在一个t，满足x+t=0存在一个y，对于任取的一个z，满足y+z=0不存在这样的u，v，满足u+v=0A) 正确答案为B)0)()(zxzx)0)()(txtx)0)()(zyzy)0)()(vuvu7.3 谓词公式的翻译与解释一、谓词公

5、式 1。原子公式 若 是n元函数， 是个体变元，则 是原子命题公式。 2。合式公式 原子公式是合式公式， 若A、B是合式公式，则 也是合式公式， 若A是合式公式，x是A中出现的变元，则 也是合式公式， 有限次地使用构成的公式是合式公式。),(21nxxxPnxxx,21),(21nxxxP)(),(),(BABAA)(),(BABAAxAx)( ,)(一、变元 在合式公式 中， x：指导变元，A：量词 的辖域。 若A中有x，则x称为约束变元， 若A中无x，则x称为自由变元。例如在 中， x是约束变元，约束出现2次， y是自由变元， 的辖域是 ，即约束变元后面括号内的式子是辖域。 量词只对辖域中

6、的指导变元有效。AxAx)()(和 ,),()()(yxGxFx),()(yxGxFx7.4 变元的约束2001年7月选择题2 表达式中 的辖域是（ ）。 A） B） C） D）2004年1月选择题3 设个体域是整数集，P：下面4个命题中为真的是 ( ) (A) P是真命题 (B) P是假命题 (C) P是谓词公式，但不是命题 (D) P不是谓词公式 )(),()()(),()(zzQyxRyzQyxPx),(yxP)(),(zQyxP),(yxR),(),(yxRyxPx)()()(xyxyxyxBB二、换名规则和代入规则 在同一个合式公式中，一个变元既可能约束出现，又可能自由出现。为避免混

7、淆，可采用换名的办法使约束情况更加清楚。 1。换名规则对约束变元换名 把公式中量词的指导变元及其辖域中的该变元换成公式中没有出现的新变元，其它部分不变。 2。代入规则对自由变元换名 把公式中的自由变元，用公式中没有出现的新变元替代，并且处处替代。 公式经换名和代入后，公式的意义不应当改变。2005年7月化简解答题13 将谓词公式中的约束变元换名。（请按约束变元出现的顺序，使用字母 等）解： ),()()()(),()()()(zxSzxRxzxQxRxPxtswvu,),()()()(),()()()(zxSzxRxzxQxRxPx),()()()(),()()()(wxSwvRvzuQuRu

8、Pu7.5 谓词的等值演算一、解释或赋值 对谓词公式中的个体变元、函数变项、谓词变元用指定的常项去替代，所得到的结果称为对谓词公式的一个解释或赋值 I 。消去量词的规则： 在有限个体域下，可按下列规则消去量词。 例如：,21naaaD)()()()()(21naAaAaAxAx)()()()()(21naAaAaAxAx2001年1月填空题6 设个体域 ,公式 消去量词可化为 。2003年1月填空题8 设个体域D1,2,那么谓词公式消去量词后的等值式 。2005年1月填空题7 设个体域 ，公式消去量词为 。 )()()()(yGyxFx,cbaD )()()()()()(cGbGaGcFbFa

9、F)()(yyBxxA)2() 1 ()2() 1 (BBAA,baD ),()(yxyHxGx),(),()(),(),()(bbHabHbGbaHaaHaG二、谓词公式的分类 在给定的解释下，谓词公式的值称为谓词公式的真值。真值可以为1，也可以为0。 如果个体域有限，求谓词公式的真值，可以消去量词，把函数值代入谓词，即可求出。 如果谓词公式在任何解释下都为真，称为永真式，在任何解释下都为假，称为永假式或矛盾式，若至少有一个解释下为真称为可满足式。 要判断一个谓词公式是永真式还是永假式，是较困难的。简单公式当然一眼就可看出，稍复杂一点就只能通过下面所讲的等值演算法化简。如公式等值于1，则为永

10、真式；如公式等值于0，则为永假式。例1，已知解释 I 如下： 解：2)3(, 3)2()3(,2)2(, 3 , 2) 1 (ffaD3 , 2, 1),(, 1)3(, 0)2()4(jijiQPP的真值和求)(,()(),()(afxQxfPxaxQxPx),()(axQxPx)(,()(afxQxfPx010) 11 () 10()2 , 3()3()2 , 2()2(QPQP)2(, 3()3()2(, 2()2(fQfPfQfP)3 , 3()2()3 , 2()3(QPQP101) 10() 11 (三、谓词公式的等值演算 谓词公式在等值演算下，可以有不同的表现形式其中特别要记住的

11、有： )()()()(xBxAxxBxAx)()()()(xBxAxxxBxxA),(),(yxxAyyxyAx)()()()(xxBxxAxxBxxA)()(),()(xAxxxAxAxxxA)()()()(xBxAxxxBxxA)()()()(yBxAyxxxBxxA)()()()(yBxAyxxxBxxA),(),(yxxAyyxyAx2000年1月化简解答题12 通过等值演算说明下列等值式成立：解：)()()()()()()(xQxxPxxQxPx)()()(xQxPx)()()()(xQxxPx)()()(xQxPx)()()()(xQxxPx)()()()(xQxxPx7.6 前束

12、范式一、前束范式 前束范式是指所有的量词都在最前面的谓词公式。例如， 和是前束范式， 就不是前束范式。 任何一个谓词公式都可以通过等值演算，将其化为前束范式，而且所得到的结果不是唯一的。 怎样把谓词公式化为与之等值的前束范式呢？方法可以分解成下面这五个步骤，而且应当严格地按照这五步的顺序进行，不能颠倒。)()(yGxPyx)(),(xQzyxPzyx)()(yyGxxF利用等值变换消去联结词将联结词 移到原子谓词公式之前3. 对于公式中变元相同的部分，看能否用等值演算化简合并4. 用换名规则或代入规则，使所有约束变元的符号均不相同，约束变元与自由变元也要用不同的符号5. 将 等移到公式的最左边

13、。)()()()(xAxxAx)()(KHHKHK,HKHKxx ,)()()()(xAxxAx2000年1月填空题7 谓词公式 的前束范式是 解：2001年1月计算题14 求谓词命题公式 的前束范式。解：)()()()(xQxxPx),()(yxyGxxF)()()(xQxPx)()()()()()()()(xQxxPxxQxxPx),()(yxyGxxF),()(yxyGxxF),()(yzyGxxF),()(yzGxFyx7.7 谓词逻辑的推理理论 谓词逻辑推理是命题逻辑推理的推广和扩充。一、推理规则 1. 全称量词消去规则(US规则) 已知 和个体常项c或个体变项y, 则有 2. 全称量词附加规则(UG规则) 已知个体变项y和 ，则有 3. 存在量词消去规则(ES规则) 已知 ，则有 4. 存在量词附加规则(EG规则) 已知个体常项c和 ，则有 。)()(xAx)()(xAx)(),(yAcA)()(xAx)(yA)(cA)(cA)()(xAx二、推理方法 1. 从前提出发，对于量词 ，把辖域中的约束变元以可以在个体域中任意取值的个体 y,z,s,t 等替代，需要时也可以用个体常量 a,b,c等替代，对于量词 ，以个体常量 a,b,c 等替代。 2. 按命题逻辑的推理方法进行推理，得出与结