离散数学课件--2谓词逻辑.ppt

第二章 谓词逻辑 合肥工业大学数学学院 邢燕 2.1 谓词的概念与表示 命题逻辑的局限性： 下列推理：凡是人都是要死的。 苏格拉底是人。 苏格拉底是要死的。 众所周知，这是真命题。但在命题逻辑中 ( P Q ) R ，难证其为重言式。 原因：命题逻辑不考虑命题之间的内在联系 和数量关系。 办法：将命题再次细分。 2.1 谓词的概念与表示 谓词 在反映判断的句子中，用以刻划客 体的性质或关系的即是谓词。 例：(1)3是有理数。 (2)x是无理数。 (3)阿杜与阿寺同岁。 (4)x与y有关系L。 其中，“是有理数”、“是无理数”、“与同 岁”、“与有关系L”均为谓词。前两个 是指明客体性质的谓词，后两个是指明两 个客体之间关系的谓词。 2.1 谓词的概念与表示 将上述谓词分别记作大写字母F、G、H、L ，用小写字母表示客体名称，则上述可表 示为： (1)F(3) (2)G(x) (3)H(a,b) a:阿杜 b:阿寺 (4)L(x,y) 谓词填式 单独一个谓词不是完整的命题 ，把谓词字母后填以客体所得的式子称为 谓词填式。 2.1 谓词的概念与表示 n元谓词 由n个客体插入到固定位置上的 谓词填式。 例如：A(b)称作一元谓词，B(a, b)称作二元 谓词，L(a, b, c)称作三元谓词，P(x1 , x2 , , xn)称作n元谓词。 注意：代表客体名称的字母，它在多元谓 词中出现的次序是固定的，与事先约定的 次序有关，如L(a, b, c)和L(b, c, a)代表两个 不同的命题。 2.2 命题函数与量词 例：H是谓词“能够到达山顶”，t表示老虎 ，c表示汽车，z表示张三，那么H(t), H(c), H(z)表示三个不同的命题，但它们有一个共 同的形式H(x)，当x分别取t, c, z 时。 L(x, y)表示“x小于y”，那么L(2, 3)表示了一 个真命题“2小于3”，而L(5, 1)表示假命题“5 小于1”。可以看出，L(x, y)本身不是一个命 题，只有当变元x, y取特定的客体时，才是 一个命题。 2.2 命题函数与量词 简单命题函数 由一个谓词，一些客体变 元组成的表达式称为简单命题函数。 n元谓词就是有n个客体变元的命题函数。 不带任何客体变元的谓词称为0元谓词。 复合命题函数 由一个或n个简单命题函数 以及逻辑联结词组合而成的表达式称复合 命题函数。 2.2 命题函数与量词 命题函数不是一个命题，只有客体变元取 特定名称时，才能成为一个命题。 但客体变元在哪些范围内取特定的值，对 是否成为命题及命题的真值极有影响。 例：R(x)表示“x是大学生”，如果x的讨论范围 是某大学里班级中的学生，则R(x)是永真式。 如果x的讨论范围是某中学里班级中的学生， 则R(x)是永假式。如果x的讨论范围为一剧场 中的观众，那么对某些观众，R(x)为真，对另 一些观众，R(x)为假。 2.2 命题函数与量词 个体 可以独立存在的具体的或抽象的客 体。 个体常量：具体的或特定的，一般用 a,b,c,表示。 个体变元：抽象的或泛指的，一般用 x,y,z,表示。 个体域 个体变元的论述范围。 全总个体域 把各种个体域综合在一起作 为论述范围的域。 2.2 命题函数与量词 量词 用来表示个体常量或变元之间数量 关系的词。量词分为两种： 全称量词 表示“一切”,“所有”,“凡”,“每一 个”,“任意”等意的词称为全称量词，记作 。 如：x 表示个体域内所有的x。 存在量词 表示“某个”,“对于一些”,“存在 一些”,“至少有一个”等意的词称为存在量 词，记作。 如：y 表示个体域内存在一些y。 2.2 命题函数与量词 例：用谓词表达式写出下列命题。 (1)凡是人都呼吸。 (2)有的人是左撇子。 解：令F(x)：x 呼吸。G(x)：x 是左撇子。 当个体域为人类集合时： (1) xF(x) (2)xG(x) 当个体域为全总个体域时： 令M(x)：x 是人。 (1) x(M(x) F(x) (2) x(M(x)G(x) 2.2 命题函数与量词 约定：以后如不指定个体域，默认为全总 个体域。 特性谓词 在讨论带有量词的命题函数时 ，必须确定其个体域。当使用全总个体域 时，对客体变元的变化范围限制的词，称 作特性谓词。 如上例中，M(x)为F(x)和G(x)的特性谓词， 它限定了变元x的范围。 一般，对全称量词，特性谓词常作条件的 前件；对存在量词，特性谓词常作合取项 。 2.2 命题函数与量词 例：将下列命题符号化，并讨论其真值。 (1)所有的人都长头发。 解: 令M(x): x是人。F(x): x 长头发。则 x(M(x) F(x) 真值为0 (2)有的人吸烟。 解: 令M(x): x是人。S(x): x 吸烟。则 x(M(x)S(x) 真值为1 2.2 命题函数与量词 (3)没有人登上过木星。 解: 令M(x): x是人。D(x): x 登上过木星。则 x(M(x)D(x) 真值为1 (4)清华大学的学生未必都是高素质的。 解: 令Q(x): x 是清华大学的学生。H(x): x 是 高素质的。则 x(Q(x) H(x) 真值为1 或 x(Q(x)H(x) 可见，有些命题的符号化形式不止一种。 2.2 命题函数与量词 至此，下列推理即可解决： 凡是人都是要死的。 苏格拉底是人。 苏格拉底是要死的。 令M(x): x 是人。D(x): x 是要死的。s: 苏格 拉底。则谓词表达式为： (x)(M(x) D(x) M(s) D(s) 2.3 谓词公式与翻译 一阶语言 一阶语言F 的字母表定义如下: (1) 个体常项：a,b,c,ai,bi,ci,i1. (2) 个体变项：x,y,z,xi,yi,zi,i1. (3) 函数符号：f,g,h,fi,gi,hi,i1. (4) 谓词符号：F,G,H,Fi,Gi,Hi,i1. (5) 量词符号：，. (6) 联结词符号：，. (7) 括号与逗号：( , ) , , . 2.3 谓词公式与翻译 F 的项： (1)个体常项和个体变项都是项。 (2)若f(x1, x2, , xn)是任意的n元函数，t1, t2, , tn是任意的n个项，则f(t1, t2, , tn)是项。 (3)所有的项都是有限次使用(1),(2)得到的 。 原子公式 若A(x1, x2, , xn)是F 的任意n 元谓词，t1, t2, , tn是F 的任意n个项，则称 A(t1, t2, , tn)为谓词演算的原子公式。 2.3 谓词公式与翻译 谓词演算的合式公式/谓词公式 (1)原子公式是合式公式。 (2)若A 是合式公式，则 (A) 也是合式公式。 (3)若A和B是合式公式，则(AB)，(AB)， (AB)，(AB)也是合式公式。 (4)若A是合式公式，x是A中出现的任何变元 ，则xA和xA，也是合式公式。 (5)只有有限次应用规则(1)(4)构成的符号串 才是合式公式。 2.3 谓词公式与翻译 约定：最外层的圆括号可以省略。但量词 后面若有括号则不能省略。 例：将下列命题符号化 。 (1)没有不能表示为分数的有理数。 解: 令Q(x):x是有理数。W(x):x能表示成分数 。 则x(Q(x)W(x) 或 x(Q(x)W(x) 2.3 谓词公式与翻译 (2)在北京买菜的人不全是外地人。 解: 令B(x):x在北京买菜的人。F(x):x是外地 人。则 x(B(x)F(x) 或 x(B(x)F(x) 例：将下列命题符号化 。 (1)火车都比轮船快。 解: 令T(x):x是火车。S(x):x是轮船。F(x,y):x 比y 跑得快。则 xy(T(x)S(y) F(x,y) 2.3 谓词公式与翻译 (2)有的火车比有的汽车快。 解: 令T(x):x是火车。C(x):x是汽车。F(x,y):x 比y 跑得快。则 xy(T(x)C(y)F(x,y) (3)不存在比所有火车都快的汽车。 解: 令T(x):x是火车。C(x):x是汽车。F(x,y):x 比y 跑得快。则 x(C(x)y(T(y)F(x,y) 或 x(C(x) y(T(y)F(y,x) 2.4 变元的约束 给定A为一谓词公式，其中有一部分公式形 为xP(x)或xP(x)。和后面所跟的x，称 为相应量词的指导变元。P(x)称为相应量 词的作用域/辖域。在x和x的辖域中，x 的所有出现都称为x在公式A中的约束出现 ，所有约束出现的变元，叫做约束变元。 A中不是约束出现的变元均称作自由变元 。 2.4 变元的约束 (1)x(F(x) G(x,y) x是指导变元，量词的辖域为 (F(x)G(x,y)，其中，x是约束出现两次，y 是自由出现一次。 (2)x F(x,y) y G(x,y) x是指导变元，量词的辖域是F(x,y)，其中 ，x是约束出现一次，y是自由出现一次；同 时，y也是指导变元，量词 的辖域是G(x,y) ，其中，y是约束出现一次，x是自由出现一 次。 2.4 变元的约束 (3)x y (F(x,y)G(y,z)x H(x,y,z) x、y是指导变元，对应量词、的辖域为 (F(x,y)G(y,z)，其中x是约束出现一次，y 是约束出现两次，z是自由出现一次；后一 个x也是指导变元，量词的辖域为H(x,y,z) ，其中x是约束出现一次，y、z是自由出现 一次。 2.4 变元的约束 例: (1) x(H(x,y) y(W(y)L(x,y,z) (2) x(H(x)W(y) y(F(x)L(x,y,z) 为了避免由于变元的约束与自由同时出现 ，引起概念上的混乱，故可对约束变元进 行换名。使得一个变元在一个公式中只呈 一种形式出现，即呈自由出现或呈约束出 现。 一个公式的约束变元所使用的名称符号是 无关紧要的，即xP(x)与yP(y)具有相同 的意义，xP(x)与yP(y)意义也相同。 2.4 变元的约束 约束变元的换名规则： 对于约束变元可以换名，其更改的变元名 称范围是量词中的指导变元，以及该量词 作用域中所出现的该变元，公式的其余部 分不变。 换名时一定要更改为作用域中没有出现的 变元名称。 例: 对x(H(x,y) y(W(y)L(x,y,z)换名。 解: 可换名为x(H(x,y) u(W(u)L(x,u,z) 2.4 变元的约束 对于公式中的自由变元，也允许更改，这 种更改叫做代入/代替。 自由变元的代入规则： 对于谓词公式中的自由变元，可以作代入 ，代入时需对公式中出现该自由变元的每 一处进行。 用以代入的变元与原公式中所有变元的名 称不能相同。 2.4 变元的约束 例:对x(H(x)W(y)y(F(x)L(x,y,z)代 入。 解:经代入后公式为 x(H(x)W(v) y(F(u)L(u,y,z) 2.4 变元的约束 A(x1, x2, , xn)是n元谓词，它有n个相互独 立的自由变元。若对其中k个变元进行约束 则成n - k元谓词。若谓词公式中没有自由 变元出现，则该式就成为一个命题。 当论域的元素有限时，可以消去公式中的 量词。设论域元素为a1, a2, , an。则 (x)A(x)A(a1)A(a2)A(an) (x)A(x)A(a1)A(a2)A(an) 2.4 变元的约束 量词对变元的约束，往往与量词的次序有 关。命题中的多个量词，我们约定从左到 右的次序读出。注意: 量词的次序不能颠倒 ，否则将与原命题不符。 2.5 谓词演算的等价式与蕴含式 赋值/解释 在谓词公式中常包含命题变元 和客体变元，当客体变元由确定的客体所 取代，命题变元用确定的命题所取代时， 就称作对谓词公式赋值。一个谓词公式经 过赋值以后，就成为命题。 等价 给定任何两个谓词公式wff A和wff B ，设它们有共同的个体域E，若对A和B的 变元的任一组真值指派，所得真值均相同 ，则称谓词公式A和B在E上是等价的，并 记作AB。 永真式/逻辑有效式 给定任意谓词公式 wff A，其个体域为E，对于A的任一组真值 指派，wff A皆为1，则称公式A在E上是有 效的/永真的。 不可满足式/永假式 一个谓词公式wff A ，如果在所有赋值下都为0，则称该wff A是 不可满足的/永假的。 可满足式 一个谓词公式wff A，如果至少 在一种赋值下为T，则称该wff A是可满足 的。 2.5 谓词演算的等价式与蕴含式 谓词演算中的等值式和蕴涵式 命题演算 中的等值公式表和蕴含公式表都可推广到 谓词演算中使用。 消去量词的等值式 量词否定的等值式（量词的转化律） (x)P(x)(x)P(x) ， (x)P(x)(x)P(x) 证明：(可在有限个体域上证明) 2.5 谓词演算的等价式与蕴含式 设个体域中的客体变元为a1, a2, , an，则 (x)A(x)(A(a1)A(a2)A(an) A(a1)A(a2)A(an) (x)A(x) (x)A(x) (A(a1)A(a2)A(an) A(a1)A(a2)A(an) (x)A(x) 2.5 谓词演算的等价式与蕴含式 量词作用域的扩张与收缩的等值式 x(A(x)B) x A(x)B x(A(x)B) x A(x)B x(A(x)B) x A(x)B x(BA(x) Bx A(x) x(A(x)B) x A(x)B x(A(x)B) x A(x)B x(A(x)B) x A(x)B x(BA(x) Bx A(x) 2.5 谓词演算的等价式与蕴含式 以上各等价式中的B不含客体变元x ; 或含 有与量词指导变元x 不同的变元 , 如y , z 等 。 试证明 x(A(x)B) x A(x)B 证：左x(A(x)B) x A(x)B x A(x)B x A(x)B（右） 2.5 谓词演算的等价式与蕴含式 量词分配的等价式 x(A(x)B(x) x A(x)x B(x) x(A(x)B(x) x A(x)x B(x) 量词与命题联结词间的一些蕴含式 x A(x)x B(x) x(A(x)B(x) x(A(x)B(x) x A(x)x B(x) x(A(x) B(x) x A(x) x B(x) x(A(x) B(x) x A(x) x B(x) x A(x) x B(x) x(A(x) B(x) 2.5 谓词演算的等价式与蕴含式 具有两个量词的二元谓词公式（共八种） x y A(x,y) y x A(x,y) x y A(x,y) y x A(x,y) x y A(x,y) y x A(x,y) y x A(x,y) x y A(x,y) 其中：x y A(x,y) y x A(x,y) x y A(x,y) y x A(x,y) 后四种均不等价，故全称量词和存在量词 在公式中出现的次序，不能随意更换。 2.5 谓词演算的等价式与蕴含式 二元谓词公式的一些蕴含式 x y A(x,y) x A(x,x) x A(x,x) x y A(x,y) x y A(x,y) y x A(x,y) 2.5 谓词演算的等价式与蕴含式 2.6 前束范式 前束范式 一个公式如果量词均包含在全 式的开头，它们的作用域延伸到整个公式 的末尾，则该公式叫做前束范式。其形式 为 (v1)(v2)(vn)A ，其中是量词或，vi (i=1,2,n)是客体变元，A 是没有量词的谓 词公式。 如：x y(F(x)G(y)H(x,y) x y(F(x,y)G(y,z)x H(x,y,z) 2.6 前束范式 Th1(前束范式存在定理) 任意一个谓词公 式，均和一个前束范式等价。 本定理说明任何公式的前束范式都是存在的 ，但一般不是唯一的。 求法： 利用双否律、德摩根律、量词转化律把否 定深入到命题变元和谓词填式的前面； 利用换名和代入规则，量词作用域的扩张和 收缩等价式，把量词提到前面。 2.6 前束范式 例: 求下列公式的前束范式。 (1)x F(x) x G(x) 解：xF(x) xG(x) xF(x)xG(x) (量词否定等价式) x(F(x)G(x) (量词分配等价式) 或xF(x) yG(y) (换名规则) xF(x)yG(y) (量词否定等价式) x(F(x)yG(y) (量词辖域扩张等价式) xy(F(x)G(y) (量词辖域扩张等价式) 2.6 前束范式 (2)x F(x) x G(x) 解：原式 xF(x) yG(y) (换名规则) xF(x)yG(y) (量词否定等价式) x(F(x)yG(y) (量词辖域扩张等价式 ) xy(F(x)G(y) (量词辖域扩张等价式 ) (3)x F(x)x G(x) 解：原式 xF(x)yG(y) (换名规则) xy(F(x)G(y) (量词辖域扩张等价式) 2.6 前束范式 (4)x F(x,y) y G(x,y) 解：xF(x,y)yG(x,y) t F(t,y)w G(x,w) (换名规则) tw(F(t,y)G(x,w) (量词辖域扩张等价式 ) 或x F(x,t)y G(w,y) (代入规则) xy(F(x,t)G(w,y) (量词辖域扩张等价式 ) (5)x F(x) x G(x) 解：原式xF(x)yG(y) (换名规则) x y(F(x)G(y) (量词辖域扩张等价式) 2.6 前束范式 (6)(x F(x,y)y G(y)x H(x,y,z) 解：原式 (x F(x,y)b G(b)c H(c,y,z) x b(F(x,y)G(b)c H(c,y,z) x b c (F(x,y)G(b)H(c,y,z) 2.6 前束范式 前束合取范式 一个wff A如果具有如下形 式，则称为前束合取范式。 (v1)(v2)(vn)(A11A12A1k1) (A21A22A2k2)(Am1Am2 Amkm) ， 其中是量词或，vi (i=1,2,n)是客体变元 ，Ai j是原子公式或其否定。 Th2(前束合取范式存在定理) 每一个wff A 都可转化为与其等价的前束合取范式。 2.6 前束范式 前束析取范式 一个wff A如果具有如下形 式，则称为前束析取范式。 (v1)(v2)(vn)(A11A12A1k1) (A21A22A2k2)(Am1Am2 Amkm) ， 其中是量词或，vi (i=1,2,n)是客体变元 ，Ai j是原子公式或其否定。 Th3(前束析取范式存在定理) 每一个wff A 都可转化为与其等价的前束析取范式。 2.6 前束范式 任一个wff A转换为等价的前束合(析)取范 式的步骤： 消去公式中出现的多余量词； 利用换名、代入规则使所有约束变元均不 相同，并且使约束变元和自由变元不同； 将谓词公式中出现的联结词均转化成 , , ； 2.6 前束范式 利用双否律，德摩根律及量词转化律，将 谓词公式中的 深入到命题变元和谓词填式 的前面； 利用量词作用域的扩张和收缩等价式，将 量词推到左边，扩大量词作用域至整个公 式。 2.7 谓词演算的推理理论 命题演算中的推理规则，如P、T和CP规则 等也可在谓词演算的推理理论中应用。 但在谓词推理中，某些前提与结论可能受 量词限制，为了能使用命题演算中的等价 式和蕴含式，必须在推理过程中有消去和 添加量词的规则。 2.7 谓词演算的推理理论 (1)全称指定规则（简记为UI或US） (x)P(x) P(c) (x)P(x) P(y) 如果对论域中所有客体x ，P(x)成立，则 对论域中某个任意客体常元c ，P(c)成立 ；或对论域中客体变元y ，P(y)成立，注 意要求P(x)对y是自由的。 UI UI 2.7 谓词演算的推理理论 (2)全称推广规则（简记为UG） P(x)(y)P(y) 如果能够证明对论域中每一个客体x断言 P(x)都成立，则可得到结论(y)P(y)成 立，注意P(x)对y是自由的。 UG 2.7 谓词演算的推理理论 (3)存在指定规则（简记为EI或ES） (x)P(x) P(c) (x)P(x) P(y) 如果对于论域中某些客体，P(x)成立，则 必有某个特定客体常元c或某些特定客体 变元y，使P(c)或P(y)成立。应注意，指 定的客体c或y不是任意的，而且P(x)中有 其他自由变元时，不能应用本规则。 EI EI 2.7 谓词演算的推理理论 (4)存在推广规则（简记为EG） P(c) yP(y) P(x) yP(y) 如果对论域中某个特定客体常元c 或变元 y，有P(c) 或P(x)成立，则在论域中，必 存在y使得P(y)成立。注意，取代c的个体 变元y不能在P(c)中出现，P(x)对y是自由 的。 EG EG 2.7 谓词演算的推理理论 例：构造下列推理的证明。 前提：x (A(x)B(x)，x A(x) 结论：x B(x) 证明：(1) x A(x) P (2) A(c) (1)EI (3) x (A(x)B(x) P (4) A(c)B(c) (3)UI (5) B(c) (2)(4) 假言推理 (6) x B(x) (5)EG 注意：(1) (3)引入的顺序不可更改! 2.7 谓词演算的推理理论 例：证明凡是人都是要死的。 苏格拉底是人。 苏格拉底是要死的。 解: 令M(x): x是人。D(x): x是要死的。a: 苏 格拉底。即要证 x(M