公务员考试-第二章 谓词逻辑

《公务员考试-第二章 谓词逻辑》由会员分享，可在线阅读，更多相关《公务员考试-第二章 谓词逻辑（74页珍藏版）》请在金锄头文库上搜索。

1、第四章第四章 一阶逻辑基本概念一阶逻辑基本概念1苏格拉底三段论：凡人都是要死的。苏格拉底是人。所以苏格拉底是要死的。2第一节 一阶逻辑基本概念 一、个体词定义 研究对象中可以独立存在的具体或抽象 的客体，称为个体词。注 表示具体或特定的客体的个体词称为个体常 项，一般用a,b,c等表示。表示抽象或泛指的客体的个体词称为个体变 项，一般用x,y,z等表示。个体变项的取值范围称为个体域。由所有的 个体构成的个体域成为全总各体域。3二、谓词1、定义 用来刻画个体词的性质或个体词之间关系的词称为谓词。 注 1)一个谓词与一个个体词相联，称为一元谓词。一般的，一个谓词与n个个体词相联，称为n元谓词。43

2、)n元谓词F(x1,x2,xn)不是一个命题，只是一个 命题变元。2)谓词分类谓词常项：表示具体或特指的性质或关系的谓词， 记为F,G,H等。谓词变项：表示抽象或泛指的性质或关系的谓词， 记为F,G,H等。5解 设谓词H(x,y):x小于y，a:2，b:3，c:8，d:7 则上述命题符号化为谓词的蕴涵式： H(a,b)H(c,d)由于此蕴涵式的前件为真，后件为假，所以命题为 假。例1 将下列命题在谓词逻辑中符号化，并讨论它们 的真值：如果2小于3，则8小于7。2、谓词逻辑命题的符号化 6三、量词定义 表示个体常项或变项之间数量关系的词称为量词。量词分为两类：全称量词x和存在量词x，分别表示所有

3、的个体x和存在一个个体x。注 a)x后面括号内的式子称为全称量词的辖域； x后面括号内的式子称为存在量词的辖域。7解 (a)令F(x)：x要死的；G(x)：x天生就近视。(1)在个体域D1中除人外，没有其他的事物，因而(1) 可符号化为： xF（x）例2 在个体域分别限制为(a)和(b)条件时，将下面 的命题符号化：(1)所有人都是要死的。 (2)有的人天生就近视。其中(a)个体域D1为人类集合。(b)个体域D2为全总个体域。8(b)在个体域D2中除人外，还有其他的事物，因而在将(1),(2)符号化时，必须考虑先将人分离出来，令M(x):x是人。在D2中，(1),(2)可分别描述如下：(2)在

4、个体域D1中有些人是天生就近视，因而(2)可 符号化为xG（x）9(1)对于宇宙间的一切事物，如果事物是人，则他是要死的。(2)在宇宙间存在着天生就近视的人。将(1),(2)分别符号化为：(1)x(M(x)F(x)(2)x(M(x)G(x)在个体域D1、D2中命题(1),(2)都是真命题。10例3 在个体域分别限制为（a）和（b）条件时，将下面的命题符号化：（1）对任意的x，都有x2-5x+6 =(x-2)(x-3)（2）存在x，使得x+1=0。其中：（a）个体域D1为自然数集合。（b）个体域D2为实数集合。b)量词所确定的公式与个体域有关。c)对不同个体域表达式有不同的真值。11解(a)令F

5、(x):x2-5x+6=(x-2)(x-3);G(x):x+1=0。在个体域D1中(1),(2)符号化分别为(1)x F(x) (2)xG(x)在个体域D1中命题(1)为真命题，命题(2)为假命题 。(b)在个体域D2中(1),(2)符号化分别为 (1)xF（x） (2) xG（x） 在个体域D2中命题(1),(2)都是真命题。12因此，在谓词逻辑中个体域必须是确定的。有时为讨论方便，将谓词逻辑中的个体域一律用全总个体域，每个个体变元的变化范围用一定的特性谓词刻画。对全称量词，此特性谓词可作为蕴含的前件而加入；对存在量词，此特性谓词可作为合取式的合取项而加入。13例4 将下列命题符号化，并指出

6、真值情况。 （1）没有人登上过月球。 （2）未必所有人的头发都是黑色的。解 个体域为全总个体域，令M（x）：x是人。(1)令F(x)：x登上过月球。命题(1)符号化为：x（M（x）F（x）设a是1969年登上月球完成阿波罗计划的一名美国人，则M（a）F（a）为真，故命题(1)为假。14（2）令H(x):x的头发是黑色的。命题(2)可符号化为：x(M(x)H(x)我们知道有的人头发是褐色的，所以x(M(x)H(x)为假，故命题(2)为真。 15d)多个量词顺序不能随意调换。 e)当个体域D=a1,a2,an为有限集合时，可将谓词 中的量词删除，化为命题公式，即设F(x)为一元谓词 ，则xF(x)

7、 F(a1)F(a2)F(an)xF(x) F(a1)F(a2)F(an)16第二节 一阶逻辑公式及解释一、函数定义 设D为个体域，一个DnD的映射称为一个n 元函数，记为f(x1,x2,xn)。注n元函数与n元谓词的区别：n元函数f： DnDn元谓词F：Dn0，117二、公式1、谓词逻辑公式所用的符 号(七种) (1)个体常量：a,b,c(2)个体变量：x,y,z(3)函数符号：f,g,h(4)谓词符号：F,G,H(5)联结词： , , , , (6)量词： , (7)括号：（，）命题逻辑公式中所用的 符号(三种)(1)命题：P,Q,R (2)联结词：, , , , (3)括号：（，）18(

8、b)原子公式定义 设P(x1,x2,xn)是n元谓词公式，其中，x1,x2,xn是n个项，则称P(x1,x2,xn)为谓词演算的原子公式。2、公式概念(a)项定义 (1)个体常量是项；(2)个体变量是项；(3)设f为n元函数符, x1,x2,xn是项，则 f(x1,x2,xn)是项；(4)项由且仅由有限次使用(1)(2)(3)而得。19(c)公式定义 谓词逻辑公式(亦可简称公式)定义如下：（1）原子公式是公式；（2）若A，B是公式，则（A）、（AB）、（AB）、（AB）、（AB）是公式；（3）若A是公式，则xA、xA是公式；（4）只有有限次地应用（1）-（3）构成的符号串才 是公式。 注 谓词

9、逻辑公式是由谓词、量词、联结词、和括号有限次的使用构成的有意义的符号串。20三、约束变元与自由变元1、定义 在公式xF(x)和xF(x)中，称x为指导变元，F(x)为相应量词的辖域。在x和x的辖域中，x的所有出现都称为约束出现，而变元x叫做公式中的约束变元。F(x)中不是约束出现的其他变元均称为自由出现，而此变元x叫做公式中的自由变元。21例 指出下列各式量词的辖域及变元的约束情况：（1）x(F(x,y)G(x,z)（2）x(P(x)yR(x,y)（3）x(F(x)G(y)y(H(x)M(x,y,z)解 (1)对于x的辖域是(F(x,y)G(x,z)，x是约束 出现的，而且约束出现两次，y,z

10、均为自由出现，而 且各自由出现一次。(2)对于x的辖域是(P(x)yR(x,y)，y的辖域 是R(x,y)，x,y均是约束出现的。22（3）对于x的辖域是(F(x)G(y)，其中x是约束 出现的，而y是自由出现的。对y的辖域是 (H(x)M(x,y,z)，其中y是约束出现的，而x,z是 自由出现的。注 若一个公式中的所有变元均为约束出现而无自由出现，则此公式是确定的，并且可以确定其真假，否则，即公式中存在自由出现的变元，则此公式不是确定的。232、改名规则和代入规则a、改名规则约束变元的更改对公式中的约束变元改名时，应遵循下列规则：(1)改名时需要改的变元符号的范围是量词中的变元 以及该量词辖

11、域中此变元的所有约束出现处，而在 公式的其他部分不变。 (2)改名时所取的符号一定没有在量词辖域内出现过 。24b、代入规则自由变元的更改按下列规则对公式中的自由变元进行更改：(1)在公式中出现某一自由变元的每一处代入另一变 元；(2)所代入的变元不允许在原公式中以任何的约束形 式出现。25注 (1)公式利用改名规则正确改名后，其中的约束变元个数和自由变元个数应不变。否则，改名错误。(2)改名后的公式不能出现既是约束出现又是自由出现的个体变项。26四、解释定义 谓词逻辑公式的一个解释I，由下面四部分组成 ：（1）一个具体的个体域D。（2）对个体常量指定D中的具体个体。（3）对n元函数指定Dn到

12、D的具体映射。（4）对n元谓词F指定Dn到0，1的具体映射。显然，对任意公式G，如果给定G的一个解释I，则 G在I的解释下有一个真值，记作TI（G）。27求谓词逻辑公式在解释I下的真值的方法：1、当D有限时，删除公式中的量词，化为命题逻辑公式求真值。2、当D无限时，将谓词具体化，根据量词的含义说明 真值。28定义 若存在解释I，使得G在解释I下真值为真，则称公式G为可满足的。定义 若不存在解释I，使得I满足TI(G)=1，则称公 式G为永假式（或矛盾式）。若G的所有解释I都满足 TI(G)=1，则称公式G为永真式（或逻辑有效式）。2、公式的分类定理 重言式的代换实例都是永真式，矛盾式的代 换实

13、例都是矛盾式。29第五章第五章 一阶逻辑等值演算与推理一阶逻辑等值演算与推理30定义 设A、B是公式，设它们有共同的个体域D，若对任意的解释I都有TI（A）=TI（B），则称公式A、B 在D上是等值的，记作AB。 一、公式的等值定义 设A,B是公式，如有AB为永真公式则称其为等价永真公式，记为AB ，称A与B等值。第一节 一阶逻辑等值式31二、一阶逻辑等值式三、应用32定义 一个公式的所有量词均非否定地出现在在公 式的最前面，其辖域延伸到公式的末尾，且其中不 含有，联结词，则该公式称为前束范式。即具 有下列形式的公式：Q1x1Q2x2Qmxm(M(x1,xm)其中Qi=或 ，M(x1,xm)中

14、不含有任何量词和 ，联结词。第二节 一阶逻辑前束范式一、前束范式的概念33二、求谓词逻辑公式前束范式的方法：1) 将公式G中的，删除，并将深入；2) 利用基本等式或改名规则将xi,xj提到公式的 最前面，即得前束范式。定理 对任意一个谓词公式都可以化为与它等价的 前束范式。34解(1)xy(zA(x,z)A(x,z)tB(x,y,t) xy(zA(x,z)A(x,z)tB(x,y,t) xy(zA(x,z) A(x,z)tB(x,y,t) xy(wA(x,w)A(x,z)tB(u,v,t) xywt(A(x,w)A(x,z)B(u,v,t) 例 求下列谓词公式的前束范式。 (1)xy(zA(x

15、,z)A(x,z)tB(x,y,t)35解x(yP(x,y)xy(Q(x,y)y(P(y,x)Q(x,y)x(yP(x,y)xy(Q(x,y)y(P(y,x)Q(x,y)x(yP(x,y)xy(Q(x,y)y(P(y,x)Q(x,y)(2)x(yP(x,y)xy(Q(x,y)y(P(y,x)Q(x,y)36x(yP(x,y)xy(Q(x,y)z(P(z,x)Q(x,z)x(yP(x,y)xyz(Q(x,y)(P(z,x)Q(x,z)x(yP(x,y)uvz(Q(u,v)(P(z,u)Q(u，z) xyuvz(P(x,y)(Q(u,v)(P(z,u)Q(u,z)37注 在求公式前束范式过程中，应注意基本公式的灵活使用以及改名规则的合理应用。一般而言，在提出量词时若无基本公式支持，则即应用改名规则。382、基本公式（1）x A（x） xA（x）（2）x A（x） xA（x）39定