一阶逻辑基本概念 幻灯片.pptVIP

定理4.2：重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式。 例7 判断下列公式中，哪些是永真式，哪些是矛盾式? (1) ?x(F(x)?G(x)) 解释I1: 个体域N, F(x):x5,G(x): x4, 公式为真 解释I2: 个体域N, F(x):x5, G(x):x4, 公式为假 结论: 非永真式的可满足式 (2) ?x(F(x)?G(x)) 重言式 p?(q?p) 的代换实例,故为永真式. 解释I1: 个体域为全总个体域, F(x):x是人,G(x): x用左手写字,公式为真 解释I2: 个体域N, F(x):x是人,G(x): x有翅膀,公式为假 结论: 非永真式的可满足式 (3) ?xF(x)?(?x?yG(x,y)??xF(x)) 重言式 p?(q?p) 的代换实例,故为永真式. （4）?(?xF(x)??yG(y))??yG(y) 矛盾式 ?(p?q)?q 的代换实例，故为永假式. * * * * * 15 * * * * * (4)不存在跑得同样快的两只兔子 解：令 F(x):x是兔子， L(x,y):x与y跑得同样快 命题符号化形式为 ┐?z?y(F(z)∧F(y)∧ L(z,y)) 思考：命题符号化形式为 ?x?y(F(x)∧F(y)?┐L(x,y))可以么？ 一阶逻辑命题符号化时需要注意的事项: (1)分析命题中表示性质和关系的谓词，分别符号为一元和n（n?2）元谓词。 (2)根据命题的实际意义选用全称量词或存在量词。 (3)有些命题的符号化形式可不止一种。（例4.5之(3)） (4)一般说来，多个量词出现时，它们的顺序不能随意调换。 例如，考虑个体域为实数集，H(x，y)表示x+y=10， 则命题“对于任意的x，都存在y，使得x+y=10”的符号化形式为 ?x?yH(x,y) 如果改变两个量词的顺序，得 ?y?xH(x,y) 真命题 假命题 同在命题逻辑中一样,为在一阶逻辑中进行演算和推理,必须给出一阶逻辑中公式的抽象定义,以及它们的分类及解释。 一阶语言是用于一阶逻辑的形式语言,而一阶逻辑就是建立在一阶语言基础上的逻辑体系,一阶语言本身不具备任何意义,但可以根据需要被解释成具有某种含义. 一阶语言的形式是多种多样的，本书给出的一阶语言是便于将自然语言中的命题符号化的一阶语言，记为F。 4.2 一阶逻辑命题符号化 定义4.1 一阶语言F的字母表定义如下: (1)个体常项：a, b, c, …, ai, bi, ci, … , i ?1 (2)个体变项：x, y, z, …, xi , yi, zi, … , i ?1 (3)函数符号：f, g, h, …, fi, gi, hi, … , i ?1 (4)谓词符号：F, G, H, …, Fi, Gi, Hi, … , i ?1 (5)量词符号: ?，? (6)联结词符号:┐,∧,∨,→, ? (7)括号与逗号:(,),， 定义4.2 一阶语言F的项的定义如下: (1)个体常项和个体变项是项。 (2)若?(x1,x2,…,xn)是任意的n元函数，t1,t2,…,tn是任意的n个项，则?(t1,t2,…,tn)是项。 (3)所有的项都是有限次使用(1),(2)得到的。 定义4.3 设R(x1 ,x2 ,… ,xn)是一阶语言F的任意n元谓词，t1 ,t2 ,… ,tn是一阶语言F的任意的n个项，则称R(t1,t2,… ,tn)是一阶语言F的原子公式。 例如：1元谓词F(x)，G(x)，2元谓词H(x,y)，L(x,y)等都是原子公式。 定义4.4 一阶语言F的合式公式定义如下: (1) 原子公式是合式公式。 (2) 若A是合式公式，则(┐A)也是合式公式。 (3) 若A，B是合式公式，则(A∧B)，(A∨B)，(A→B)，(A?B)也是合式公式。 (4) 若A是合式公式,则?xA,?xA也是合式公式 (5) 只有有限次的应用(1)～(4)构成的符号串才是合式公式.? 一阶语言F的合式公式也称为谓词公式，简称公式。 定义4.5 指导变元、辖域、约束出现、自由出现 在公式?xA和?xA中，称x为指导变元。 在公式?xA和?xA中，A为相应量词的辖域。 在?x和?x的辖域中，x的所有出现都称为约束出现。 A中不是约束出现的其他变项均称为是自由出现的。 例4.6 指出下列各公式中的指导变元，各量词的辖域，自由出现以及约束出现的个体变项。(1) ?x(F(x,y)→G(x,z)) x是指导变元。 量词?的辖域A=(F(x,y)→G(x,z))。 在A中，x的两次出现均是约束出现。y和