离散数学自考.ppt

《离散数学自考.ppt》由会员分享，可在线阅读，更多相关《离散数学自考.ppt（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章 谓词逻辑,1 谓词的概念与表示法 2 量词与合式公式 3 谓词演算的等价式与蕴含式 4 前束范式 5 谓词演算的推理理论,2.1 谓词的概念与表示法,在研究命题逻辑中， 原子命题是命题演算中最基本的单位，不再对原子命题进行分解，但原子命题可进一步用客体和谓词两个部分刻画。 定义：可以独立存在的对象称为客体，客体亦称个体，可以是具体事务也可以是抽象的事务。 定义：用以刻划客体的性质或关系的即是谓词。 例：张华是学生，李明是学生。则可把它表示成： H:表示“是学生”，j:表示“张华”，m:表示“李明”，则可用下列符号表示上述二个命题：H(j)，H(m)。,1. 命题函数 客体在谓词表达式中

2、可以是任意的名词。例：C“总是要死的。” j：张三；t：老虎；e：桌子。 则C(j), C(t), C(e)均表达了命题。 在上面的例子中，C：表示“总是要死的”；x：表示变元（客体变元），则C(x)表示“x总是要死的”，则称C(x)为命题函数。 定义由一个谓词字母和一个非空的客体变元的集合所组成的表达式，称为命题函数。,讨论定义：（a）若用任何客体去取代客体变元之后，则命题函数就变为命题；（b）命题函数中客体变元的取值范围称为个体域（论述域）。 例：P(x)表示x是质数。这是一个命题函数。其值取决于个体域。 可以将命题函数命题，有两种方法： a)将x取定一个值。如：P(4)，P(5) b)将

3、谓词量化。如：xP(x)，xP(x) 个体域的给定形式有二种： 具体给定。 如：j, e, t 全总个体域任意域：所有的个体从该域中取得。,作业： P28 1a、c,1.2.1量词,（1）全称量词“”为全称量词符号，读作“对于所有的”，“对任一个”，“对一切”。例：“这里所有的都是苹果”，可写成： xA(x)或(x)A(x) 几种形式的读法： xP(x)： “对所有的x，x是”； xP(x) ： “对所有x，x不是”； xP(x) ： “并不是对所有的x，x是”； xP(x) ： “并不是所有的x，x不是”。 例：将“对于所有的x和任何的y，如果x高于y，那么y不高于x”写成命题表达形式。解：

4、 x y(G(x,y) G(y,x) G(x,y)：x高于y,（2）存在量词“”为存在量词符号，读作“存在一个”，“对于一些”，“对于某些”，“至少存在一个”，“这里存在着这样的”等等。 例：（a）存在一个人；将（a）,（b）,（c）写成命题。 规定：M(x)：x是人；则 （a） x M(x) ； “”表达式的读法： x A(x) ：存在一个x,使x是； xA(x) ：存在一个x, 使x不是； x A(x) ：不存在一个x, 使x是； xA(x) ：不存在一个x, 使x不是。,著名的苏格拉底三段论可论述如下： 所有人都是要死的； 因为苏格拉底是人； 所以苏格拉底总是要死的； 试讲其符号化为谓词

5、公式。 解M（x）：表示x是人，D（x）：x是要死的；a：苏格拉底。 上述三段论可符号化为： （x）（M(x) D（x） M（a） D（a） 该三段论可用推理描述为： 前提：（x）（M(x) D（x） ）， M(a) ， 结论： D（a）,1.2.2合式公式,定义：原子谓词公式：不出现命题联结词和量词的谓词命名式称为原子谓词公式，并用P(x1xn)来表示。（P称为n元谓词， x1xn称为客体变元），当n=0时称为零元谓词公式。 定义：由一个或几个原子命题函数以及逻辑联结词组合而成的表达式称为复合命题函数。 定义：谓词演算的合式公式（合式公式记为WffA） 原子谓词公式是合式公式； 若A是合式公

6、式，则A也是合式公式； 若A, B都是合式公式，则(AB)，(AB),(AB),(AB)都是合式公式； 若A是合式公式，x是任何变元，则xA, xA也都是合式公式； 只有按-有限次所求得的那些公式才是合式公式（谓词公式又简称“公式”）。,定义 1.辖域（作用域）：紧接在量词后面括号内的谓词公式。 例： xP(x) , x(P(x) Q(x) 。 若量词后括号内为原子谓词公式，则括号可以省去。 2.指导变元（作用变元）：紧接在量词后面括号内的X。 3.约束变元：在量词的辖域内，且与量词下标相同的变元。 4.自由变元：当且仅当不受量词的约束。 例：（ x）（P（x） （x）P（x，y） （ x）的

7、指导变元为x，作用域为P（x） （x）P（x，y）， （x）的指导变元为x，作用域为P（x，y），x为约束变元，y为自由变元。 约定：最外层的括号可以省略，但需注意，量词后面若有括号则不能省略。,例2. (x)(y)(P(x,y) Q(x,z) (x)P(x，y) (x)( y)的作用域为P(x,y) Q(x,z)，x，y为约束变元，z为自由变元。 (x)为作用域为P(x，y)，x为约束变元，y为自由变元。 在上述的谓词合式公式中，有的个体变元既可以是约束出现，也可以是自由出现，为了避免混淆采用以下两个规则。 1.下面介绍约束变元的改名规则：（a）在改名中要把公式中所有相同的约束变元全部同时改

8、掉；（b）改名时所用的变元符号在量词辖域内未出现的。,例： xP(x) yR(x,y)可改写成xP(x) zR(x,z) ，但不能改成xP(x) xR(x,x) ， xR(x,x)中前面的x原为自由变元，现在变为约束变元了。 2.区别是命题还是命题函数的方法 （a）若谓词公式中出现自由变元，则该公式为命题函数； （b）若谓词公式中的变元均为约束出现，则该公式为命题。 例： xP(x,y,z)是二元谓词， yxP(x,y,z)是一元谓词， 而谓词公式中如果没有自由变元出现，则该公式是一个命题。,3.代入规则：对公式中的自由变元的更改叫做代入。 (a)对公式中出现该自由变元的每一处进行代入， (b

9、)用以代入的变元与原公式中所有变元的名称不能相同。 例： 对公式(x)(P(x) Q(x，y) R(x，y)中的自由变元带入。 解：把z代入自由变元y得： (x)(P(x) Q(x，z) R(x，z),作业 P32 1.a、c 2.b、d 6,2.3谓词演算的等价与蕴含式,个体域（论述域，客体域）:用特定的集合表示的被约束变元的取值范围。 (1)个体域不同，则表示同一命题的谓词公式的形式不同。 例：“所有的人必死。”令D(x)，x是要死的。 下面给出不同的个体域来讨论： ()个体域为：人类，则可写成xD(x)； ()个体域为任意域（全总个体域），则人必须首先从任意域中分离出来， 设M(x)，x

10、是人，称M(x)为特性谓词。命题可写成 x(M(x) D(x),例： xP(x) ，表示x是个大学生，若x的论域为a,b,c，则： xP(x)即是P(a) P(b) P(c)；x(P(x即是P(a) P(b) P(c)； 定义：在谓词公式中，常包含命题变元和个体变元，当个体变元有确定的个体取代，命题变元用确定的命题所取代时，就称作对谓词公式赋值。 亦可以通过对谓词公式的赋值消去量词来确定谓词公式的真值。 定义：A，B为二个谓词公式，E为它们共同个体域，若对A和B的任一组变元进行赋值，使得A和B的值相同，则称A和B遍及E是互为等价的，记为AB。,定义：给定任意谓词公式WffA，其个体域为E，对于

11、A的所有赋值WffA都为真，则称WffA在E上有效的（或永真的）。 定义：一个谓词公式WffA，如果在所有赋值下WffA都为假，则称WffA为不可满足的。 定义：一个谓词公式WffA，如果至少在一种赋值下WffA都为真，则称WffA为可满足的。 1.不含量词的谓词公式的永真式 : 只要用原子谓词公式去代命题公式的永真式中的原子命题变元，则在第一章中永真蕴含式和等价公式均可变成谓词演算中的永真式：,命题逻辑 谓词逻辑 (x)(x) (x)(x)(x) . . . . (x)(x) (x) (x) (x)(x)(x) (x)(x) (x) . . . . . .,下面分类介绍在谓词公式中含有量词的

12、等价式和永真蕴含式。 （1）量词转换律： E25 xP(x) xP(x) E26 xP(x) xP(x) 下面证明：设个体域为： S=a1,a2,an xP(x) (P(a1) P(a2) P(an) P(a1) P(a2) P(an)xP(x),下面举例说明量化命题和非量化命题的差别:否定形式不同 例： 否定下列命题： (a)上海是一个小城镇 A(s) (b)每一个自然数都是偶数 x(N(x)E(x) 上述二命题的否定为： (a)上海不是一个小城镇 A(s) (b)有一些自然数不是偶数 x(N(x)E(x)x(N(x)E(x) x(N(x)E(x) x (N(x) E(x) 结论：对于非量化

13、命题的否定只需将动词否定，而对于量化命题的否定不但对动词进行否定而且对量词同时进行否定，其方法是： x的否定变为x ， x的否定变为x 。,（2）量词辖域的扩张及其收缩律 E27 xA(x) P x(A(x) P) xA(x) P x(A(x) P) E28 xA(x) P x(A(x) P) xA(x) P x(A(x) P) P，A，B为不含有变元的任何谓词公式 E30 xA(x)B x(A(x)B) E31 xA(x)B x(A(x)B) E32 AxB(x) x(AB (x) E33 A x B(x) x(AB (x),（3）量词分配率 E23 x (A(x) B(x) xA(x) x

14、B(x) E24 x(A(x)B(x) xA(x) xB(x) E29 (x (A(x) B(x) xA(x) xB(x) I17 xA(x) xB(x) x(A(x) B(x) I18 x(A(x) B(x) x（A(x) B(x)） I19 xA(x) xB(x) x(A(x) B(x) （4）量词的添加和除去的永真蕴含式 Q1 xP(x) P(y) Q2 P(y) xP(x) （Y是个体域中任一元素） Q5 xP(x) xP(x) xP P xP P (P为不含x变元）,（5）含有多个量词的永真式：（）量词出现的次序直接关系到命题的含义： “xy”表示：“无论选定一个什么样的x值总能找到

15、一个y能使x和y” “yx”表示：“只选取一个y值，以致无论怎样选定一个x，能够使y和x” 下面列出对应的表达式可以看出其不同处：设x的个体域为： a1,a2,an ， y的个体域为： b1,b2,bn ，则： xyP(x,y) yP(a1,y) yP(an,y) (P(a1, b1) P(a1, bn) (P(an, b1) P(an, bn) yxP(x,y) xP(x, b1) xP(x, bn) (P(a1, b1) P(an, b1) (P(a1, bn) P(an, bn),（）在含有多个量词的谓词公式中, xy, xy的位置是可以改变的,且不影响命题的真值 （）量词转换律的推广应

16、用:把深入到谓词公式前面去的方法。 xyzP(x,y,z) x yzP(x,y,z) xyzP(x,y,z) xyzP(x,y,z) ）两个量词, 所组成的谓词公式的等价式和永真蕴含式（8个）,xyP(x,y) yxP(x,y) xyP(x,y) yxP(x,y) yxP(x,y) xyP(x,y) yxP(x,y) xyP(x,y) xyP(x,y) yxP(x,y) xyP(x,y) yxP(x,y) yxP(x,y) xyP(x,y) xyP(x,y) yxP(x,y),作业： P35 1 a、c 6，7，8,2.4前束范式,定义一个公式，如果量词均非否定地在全式的开头，它们的作用域延伸

17、到整个公式的末尾，则称此公式叫前束范式。 例： xyz( Q(x,y) R(z) (前束范式) 定理：任何一个谓词公式均和一个前束范式等价。证明：利用量词转换把深入到原子谓词公式前, 利用约束变元的改名规则， 利用量词辖域的扩张收缩律,把量词移到全式的最前面，这样一定可得到等价的前束范式。,例： xP(x) R(x) yP(y) R(x) y(P(y) R(x) 例：把xP(x) xQ(x) 变成前束范式。xP(x) xQ(x) xP(x)xQ(x) xP(x) xQ(x) x(P(x) Q(x) 作业 P37 1a、b、d,2.5谓词演算的推理理论,1.下面分别介绍四个推理规则 （1）全称指

18、定规则（US规则）。如果对个体域中所有客体x, A(x)成立，则对个体域中某个任意客体c， A(c) 成立。该规则表示成： xA(x) A(c) (x,c个体域) （2）全称推广规则（UG规则） 如果能够证明对个体域中每一个客体c，命题A(c) 都成立，则可得到结论xA(x) 成立。该规则表示成： A(x) xA(x),（3）存在指定规则（ES规则）如果对于个体域中某些客体A(x)成立，则必有某个特定的客体c，使A(c)成立。该规则表示成： xA(x) A(c) 例：x的个体域为I=整数，P(x):x是偶数，Q(x): x是奇数。 xP(x) xQ(x) T 但P(c) Q(c) F （4）存

19、在推广规则（EG规则） 如果对个体域中某个特定客体c，有A(c) 成立，则在个体域中，必存在x，使A(x)成立。该规则表示成： A(c) xA(x),2 推论规则及使用说明 命题逻辑中的P,T,CP规则和简接证明法，都可以引用到谓词逻辑的推论规则中来，不过要注意对量词做适当处理， 其方法是：用US,ES在推导中去掉量词，用UG,EG使结论量化。 规则使用说明：（1）在使用ES,US时一定要是前束范式（2）推导中连续使用US规则可用相同变元 xP(x) P(y), xQ(x) Q(y), （3）推导中既ES用，又用US， 则必须先用ES ，后用US方可取相同变元，反之不行。 xP(x) P(y)

20、 xQ(x) Q(y) （4）推导中连续使用ES规则时，使用一次更改一个变元。,例：证： x(H(x)M(x) , xH(x) xM(x) (1) xH(x) P (2) H(c) ES (3) x(H(x)M(x) P (4) H(c) M(c)US (5) M(c)T (6) xM(x) EG,例：证: x (P(x)Q(x) x P(x) xQ(x) (1) x P(x)引入前件 (2) x (P(x)Q(x) P (3)P(c) Q(c)ES (4) P(c) US (5) Q(c) T (6) xQ(x) EG (7) x P(x)xQ(x) CP,例：证明： x(P(x)Q(x),

21、 xP(x) xQ(x) (1) xQ(x) 假设前提 (2) xQ(x) T (3) Q(c)US (4) xP(x) P (5) P(c) US (6) P(c)Q(c) T (7) x(P(x)Q(x) UG (8) x(P(x)Q(x) P (9) x(P(x)Q(x) x(P(x)Q(x) T (10) F,第二章小结,学习第二章要注意以下几点： (1)同一个命题在不同个体域内可能有不同的符号化形式，同时也可能有不同的真值，因而在将一个命题符号化之前，必须弄清个体域。 (2)在将命题符号化时，要特别注意量词与联结词的搭配。经常的情况是全称量词与蕴含词搭配，存在量词与合取词搭配。 (3)记住主要的等价式。会用约束变元和自由变元换名规则进行等价演算，求出给定公式的前束范式。 (4)在谓词演算的推理证明中，要特别注意US，UG，ES，EG规则成立的条件。,作业： 3、5,