谓词逻辑等值式.ppt

一阶逻辑 一阶逻辑的字母表 个体常项: a, b, c, …, a1, b1, c1,… 个体变项: x, y, z, …, x1, y1, z1,… 函数符号: f, g, h, …, f1, g1, h1,… 谓词符号: F, G, H, …, F1, G1, H1, … 量词符号: ?, ? 联结词符号: ?, ?, ?, ?, ? 括号与逗号: (, ), ， 一阶(first order)逻辑的合式公式 项 原子公式 合式公式 合式公式中的变项 量词辖域: 在?xA, ?xA中, A是量词的辖域. 例如: ?x(F(x)??y(G(y)?H(x,y))) 指导变项: 紧跟在量词后面的个体变项.例如: ?x(F(x)??y(G(y)?H(x,y))) 约束出现: 在辖域中与指导变项同名的变项. 例如: ?x(F(x)??y(G(y)?H(x,y))) 自由出现: 既非指导变项又非约束出现. 例如: ?y(G(y)?H(x,y)) 解释(interpret) 对一个合式公式的解释包括给出 个体域 谓词 函数 个体常项 的具体含义 赋值(举例) F(f(a,a),b) 赋值1： 个体域是全体自然数; a: 2; b: 4; f(x,y)=x+y; F(x,y): x=y 原公式赋值成: “2+2=4”。 赋值2： 个体域是全体实数; a: 3; b: 5; f(x,y)=x-y; F(x,y): xy 原公式赋值成: “3-35”。 一阶逻辑永真式(tautology) 永真式:在各种解释下取值均为真(逻辑有效式) 命题逻辑永真式: 在各种解释下取值均为真(重言式) 永假式:在各种解释下取值均为假(矛盾式) 命题逻辑永假式: 在各种解释下取值均为假(矛盾式) 可满足式：非永假式 代换实例 在含命题变项p1,p2,……,pn的命题公式中, 每个命题变项代换成一阶逻辑公式所得到的式子, 称为原来公式的代换实例. 例： F(x)→G(y) ? ?xF(x)∨G(y) 一阶逻辑公式分类 例： ??xF(x) ? ?x?F(x) ?xF(x) →(G(y) → ?xF(x) ) ?xF(x) → ?yG(y) ?(?xF(x) →?yG(y) ) ? ?yG(y) 命题符号化(举例) 例: “不存在最大的自然数”。(论域取全体自然数) 解: 设: G(x,y): x?y; 原命题符号化成: ? ?x?yG(y,x) 或: ?x?y ? G(y,x) 一阶逻辑等值式(定义) 等值： A?B 读作：A等值于B 含义：A与B在各种赋值下取值均相等 A?B 当且仅当 A?B是永真式 例如： ??xF(x)??x?F(x) 一阶逻辑等值式(来源) 命题逻辑等值式的代换实例 与量词有关的 有限个体域量词消去 量词否定 量词辖域收缩与扩张 量词分配 相同量词的交换 与变项命名有关的 换名规则 代替规则 代换实例 在命题逻辑等值式中, 代入一阶逻辑公式所得到的式子, 称为原来公式的代换实例. 例1：A???A, 令A=?xF(x), 得到 ?xF(x)????xF(x) 例2：A→B??A∨B, 令A=F(x), B=G(y), 得到 F(x)→G(y)??F(x)∨G(y) 有限个体域上消去量词 设个体域为有限集D={a1, a2,…, an}, 则 ?xA(x)?A(a1)∧A(a2) ∧ … ∧ A(an) ?xA(x)?A(a1)∨A(a2) ∨ … ∨ A(an) 例: 个体域D={a,b,c}, 则 ?x?yF(x,y) ??x (F(x,a)∧F(x,b)∧F(x,c)) ? (F(a,a)∧F(a,b)∧F(a,c))∨ (F(b,a)∧F(b,b)∧F(b,c))∨ (F(c,a)∧F(c,b)∧F(c,c)) 量词否定等值式 ??xA(x)??x?A(x) ??xA(x)??x?A(x) 量词否定等值式(举例) ? ?? ?N ?n ( nN → |an-a|? ) a1,a2,a3,…,aN ,aN+1,aN+2 ,…,an ,… ? ? 量词否定等值式(举