第三讲谓词演算的等价式与蕴涵式

谓词逻辑归结原理源代码

#include #include #include #define null 0 typedef struct { char var; char *s; }mgu; void strreplace(char *string,char *str1,char *str2) { char *p; while(p=strstr(string,str1)) { int i=strlen(string); int j=strlen(str2); *(string+i+j-1)='\0'; for(int k=i-1;(string+k)!=p;k--) *(string+k+j-1)=*(string+k); for(i=0;is)) continue; if((u+i)->var==(u+j)->var) { delete (u+j)->s; (u+j)->s=null; k--; j=i; } if(((u+i)->s)&&((u+i)->var==*((u+i)->s))) { delete (u+i)->s; (u+i)->s=null; k--;

} } j=count; if(k==j)return; count=k; for(int i=1;i0;i++) { if((u+i)->s) continue; while(!((u+j)->s)) j--; (u+i)->var= (u+j)->var; (u+i)->s= (u+j)->s; (u+j)->s=null; k--; } cout<<"gjvjkhllknkln"; } class unifier { char *string; mgu unit[50]; int count; public: int num; unifier(); void input(); int differ(int n); int change(int i,int j,int n); void print(); ~unifier(){delete string;} }; unifier::unifier() { count=0; unit[0].s=null; } void unifier::input() { cout <>num;

谓词演算推证

2.5 谓词逻辑推理理论 谓词演算推证的基本思路是将量词消去， 然后用类似命题演算推证法证明。

2.5.1 谓词演算推证 谓词演算推证也是由三个要素组成：推理根据、推理规则和证明方法。 推理根据： 一方面命题演算推证中命题定律和推理定律的代换实例可以作为谓词演算推证的推理依据； 一方面谓词演算的基本逻辑等价式和逻辑蕴涵式： 量词否定逻辑等价式 量词辖域的收缩与扩张逻辑等价式 量词分配逻辑等价式 具有两个量词的逻辑等价式 量词与联结词的逻辑蕴涵式 具有两个量词的逻辑蕴涵式

2.5.1 谓词演算推证 证明方法： 直接证法 间接证明方法 反证法 附加前提证法

2.5.1 谓词演算推证 推理规则： P规则 T规则 CP规则 消去和添加量词的规则

2.5.1 谓词演算推证 1）US 规则（全称指定规则） 这里P 是谓词，而c 是个体域中某个任意的个体。 例如，设个体域为全体偶数的集合，P(x)表示“x 是整数”，则?xP(x)表示“所有的偶数都是整数”，那么根据全称指定规则有P(6)，即“6是整数”。 全称指定规则在使用时要求x 是P(x)中自由出现的个体变元。该规则使用时还可以有以下形式：() () c Ρx x Ρ∴?() () y Ρx Ρ∴?x 这里y 是任意的不在P(x)中约束出现的个体变元。注意：

2.5.1 谓词演算推证 2）UG 规则（全称推广规则） 设E 是指定的个体域，若对于E 中的任意个体a ，都有P(a)成立，才能应用该全称推广规则。例如，设个体域是全体人类，P(x)表示“x 是要死的”。显然，对于任意一个人a ，P(a)都成立，即任何人都是要死的。则应用全称推广规则有?xP(x)成立。 全称推广规则在使用时要求y 不在P(x)中约束出现。注意：) () (y yP x P ?∴

离散数学24谓词演算的推理理论

谓词演算的 推理理论

在谓词逻辑中，除了命题逻辑中的推理规则继续有效外，还有以下四条规则。设前提Г= {A 1,A 2,…,A k }. 1. 全称指定规则（全称量词消去规则）US ： 例1 取个体域为实数域，F(x, y): x>y, P(x)=(?y) F(x,y), 则(?x)P(x) ?P(z)=(?y) F(z,y). 而不能(?x) P(x) ?P(y)=(?y) F(y,y). 其中x,y 是个体变项符号，c 为任意的个体常量. 或 (?x ) P (x ) ∴ P (y ) (?x) P (x ) ∴ P (c )

2 . 全称推广规则（全称量词引入规则） UG： P(x) ∴ (?x)P(x) 其中x是个体变项符号，且不在前提的任何公式中 自由出现. 3. 存在指定规则（存在量词消去规则） ES： (?x)P(x) ∴ P(c) 1)c是使P(x)为真的特定的个体常量，不是任意的. 2)c不在前提中或者先前推导公式中出现或自由出现， 换句话说，此c是在该推导之前从未使用过的.

4. 存在推广规则（存在量词引入规则) EG： P(c) ∴ ( x)P(x) 其中x是个体变项符号, c是个体常项符号.

谓词逻辑的推理理论由下列要素构成. 1. 等价公式 2. 蕴含式 3. 推理规则： (1) 前提引入规则 (2) 结论引入规则 (3) CP推理规则 (4)归谬论 (5) US规则 (6) UG规则 (7) ES规则 (8) EG规则

1)在推导的过程中，可以引用命题演算中的规则P、规则T、 规则CP . 2)为了在推导过程中消去量词，可以引用规则US和规则ES来 消去量词. 3)当所要求的结论可能被定量时，此时可引用规则UG和规则 EG将其量词加入. 4)证明时可采用如命题演算中的直接证明方法和间接证明方法. 5)在推导过程中，对消去量词的公式或公式中没含量词的子公 式，完全可以引用命题演算中的基本等价公式和基本蕴涵公式. 6)在推导过程中，对含有量词的公式可以引用谓词中的基本等 价公式和基本蕴涵公式.

谓词演算的推理理论(牛连强)

2.5 谓词演算的推理理论 1．推理定律 谓词演算中也存在一些基本的等价与蕴含关系，参见表2-2。我们以此作为推理的基础，即推理定律。 表2-2 序号 等价或蕴含关系 含义 E27 E28 ┐?xA(x)??x┐A(x) ┐?xA(x)??x┐A(x) 量词否定等值式 E29 E30?x(A(x)∧B(x))??xA(x)∧?xB(x) ?x(A(x)∨B(x))??xA(x)∨?xB(x) 量词分配等值式（量词分配律） E31 E32 E33 E34 E35 E36 E37 E38 E39 E40 E41 E42 E43?x(A(x)∨B)??xA(x)∨B ?x(A(x)∧B)??xA(x)∧B ?x(A(x)∨B)??xA(x)∨B ?x(A(x)∧B)??xA(x)∧B ?x(B∨A(x))? B∨?xA(x) ?x(B∧A(x))? B∧?xA(x) ?x(B∨A(x))? B∨?xA(x) ?x(B∧A(x))? B∧?xA(x) ?x(A(x)→B(x))??xA(x)→?xB(x) ?x(A(x)→B)??xA(x)→B ?xA(x)→B??x(A(x)→B) A→?xB(x)??x(A→B(x)) A→?xB(x)??x(A→B(x)) 量词作用域的扩张与收缩 I21 I22?xA(x)∨?xB(x)??x(A(x)∨B(x)) ?x(A(x)∧B(x))??xA(x)∧?xB(x) I23 ?xA(x)→?xB(x)??x(A(x)→B(x)) 表2-2中的I、E序号是接着表1-5和1-8排列的，表明它们都是谓词逻辑的推理定律。E31~E34与E35~E38只是A和B的顺序不同。 2．量词的消除与产生规则 谓词推理可以看作是对命题推理的扩充。除了原来的P规则（前提引入）、T规则（命题等价和蕴含）及反证法、CP规则外，为什么还需引入新的推理规则呢？ 命题逻辑中只有一种命题，但谓词逻辑中有2种，即量词量化的命题和谓词填式命题。如果仅由表2-2的推理定律就可推证，并不需要引入新的规则，但这种情况十分罕见，也失去了谓词逻辑本身的意义。为此，要引入如下4个规则完成量词量化命题与谓词填式之间的转换，其中的A(x)表示任意的谓词。 (1) 全称指定（消去）规则US（Ubiquity Specification，或记为?-）

人工智能原理教案02章 归结推理方法2.4 归结原理

2.4 归结原理 本节在上节的基础上，进一步具体介绍谓词逻辑的归结方法。谓词逻辑的归结法是以命题逻辑的归结法为基础，在Skolem 标准性的子句集上，通过置换和合一进行归结的。 下面先介绍一些本节中用到的必要概念： 一阶逻辑：谓词中不再含有谓词的逻辑关系式。 个体词：表示主语的词 谓词：刻画个体性质或个体之间关系的词 量词：表示数量的词 个体常量：a,b,c 个体变量：x,y,z 谓词符号：P,Q,R 量词符号：, 归结原理正确性的根本在于，如果在子句集中找到矛盾可以肯定命题是不可满足的。 2.4.1 合一和置换 置换：置换可以简单的理解为是在一个谓词公式中用置换项去置换变量。 定义： 置换是形如{t1/x1, t2/x2, …, t n/x n}的有限集合。其中，x1, x2, …, x n是互不相同的变量，t1, t2, …, t n是不同于x i的项（常量、变量、函数）；t i/x i表示用t i置换x i，并且要求t i与x i不能相同，而且x i

不能循环地出现在另一个t i中。 例如 {a/x，c/y，f(b)/z}是一个置换。 {g(y)/x，f(x)/y}不是一个置换，原因是它在x和y之间出现了循环置换现象。置换的目的是要将某些变量用另外的变量、常量或函数取代，使其不在公式中出现。但在{g(y)/x，f(x)/y}中，它用g(y)置换x，用f(g(y))置换y，既没有消去x，也没有消去y。若改为{g(a)/x，f(x)/y}就可以了。 通常，置换用希腊字母θ、σ、α、λ来表示的。 定义：置换的合成 设θ＝{t1/x1, t2/x2, …, t n/x n}，λ＝{u1/y1, u2/y2, …, u n/y n}，是两个置换。则θ与λ的合成也是一个置换，记作θ·λ。它是从集合{t1·λ/x1, t2·l/x2, …, t n·λ/x n, u1/y1, u2/y2, …, u n/y n} 即对ti先做λ置换然后再做θ置换，置换xi 中删去以下两种元素： i. 当t iλ＝x i时，删去t iλ/x i(i = 1, 2, …, n); ii. 当y i∈{x1,x2, …, x n}时，删去u j/y j(j = 1, 2, …, m) 最后剩下的元素所构成的集合。 例： 设θ＝{f(y)/x, z/y}，λ＝{a/x, b/y, y/z}，求θ与λ的合成。 解： 先求出集合

实现基于谓词逻辑的归结原理

河南城建学院 《人工智能》实验报告 实验名称：实现基于谓词逻辑的归结原理 成绩：____ 专业班级： 学号： 姓名： 实验日期：20 14 年 05 月 13日 实验器材：一台装PC机。 一、实验目的 熟练掌握使用归结原理进行定理证明的过程，掌握基于谓词逻辑的归结过程中，子句变换过程、替换与合一算法、归结过程及简单归结策略等重要环节，进一步了解机器自动定理证明的实现过程。 二、实验要求 对于任意给定的一阶谓词逻辑所描述的定理，要求实现如下过程： (1) 谓词公式到子句集变换； (2) 替换与合一算法； (3) 在某简单归结策略下的归结。 三、实验步骤 步1 设计谓词公式及自居的存储结构，即内部表示。注意对全称量词?x和存在量词?x可采用其他符号代替； 步2 实现谓词公式到子句集变换过程； 步3 实现替换与合一算法； 步4 实现某简单归结策略；

步5 设计输出，动态演示归结过程，可以以归结树的形式给出； 步6 实现谓词逻辑中的归结过程，其中要调用替换与合一算法和归结策略。 四、代码 谓词公式到子句集变换的源代码： #include #include #include #include using namespace std; //一些函数的定义 void initString(string &ini);//初始化 string del_inlclue(string temp);//消去蕴涵符号 string dec_neg_rand(string temp);//减少否定符号的辖域 string standard_var(string temp);//对变量标准化 string del_exists(string temp);//消去存在量词 string convert_to_front(string temp);//化为前束形 string convert_to_and(string temp);//把母式化为合取范式 string del_all(string temp);//消去全称量词 string del_and(string temp);//消去连接符号合取% string change_name(string temp);//更换变量名称 //辅助函数定义 bool isAlbum(char temp);//是字母 string del_null_bracket(string temp);//删除多余的括号 string del_blank(string temp);//删除多余的空格 void checkLegal(string temp);//检查合法性 char numAfectChar(int temp);//数字显示为字符 //主函数 void main() { cout<<"------------------求子句集九步法演示-----------------------"<

7逻辑代数(下)：谓词演算习题答案

练习5.1 1?指出下列谓词公式中的量词及其辖域，指出各自由变元和约束变元，并作适当更改，同时回答它们是否是命题： (1)x(P(x)V Q(x))A R (2)x(P(x)A Q(x))A xS(x) f T(x) (3)x(P(x) f y(B(x,y)A Q(y))V T(y)) (4)P(x) ( y x(P(x)A B(x,y)) P(x)) 解： (1)全称量词，辖域P(x)V Q(x)，其中x为约束变元， x(P(x)V Q(x))A R是命题。不需要更改变元。 (2)全称量词，辖域P(x)V Q(x),其中x为约束变元。 存在量词，辖域S(x),其中x为约束变元。 T(x)xxx为自由变元。 x(P(x)A Q(x))A xS(x) f T不是命题。 公式中x既是自由变元又是约束变元，可更改变元为如下公式： x(P(x)A Q(x))A yS(y) f T(z) (3)全称量词，辖域P(x) f y(B(x,y)A Q(y))V T(y),其中x为约 束变元, 存在量词，辖域B(x,y)A Q(y)，其中y为约束变元。 T(y)xxy为自由变元。 x(P(x) f y(B(x,y)A Q(y))V T(y))不是命题。 公式中y既是自由变元又是约束变元，可更改变元为如下公式：

x(P(x) -y(B(x,y)A Q(y))V T(z)不是命题。 (4)全称量词，辖域x(P(x)A B(x,y)),其中y为约束变元。 存在量词，辖域P(x)A B(x,y),其中x为约束变元。 不在量词辖域中的P(x)(第一个和第三个P(x))中的x为自由变元。 P(x) y x(P(x)A B(x,y)) - P不是命题。 公式中x既是自由变元又是约束变元，可更改变元为如下公式： P(z) -(y x(P(x)A B(x,y)) - P(z)) 2. 对个体域｛0,1｝判定下列公式的真值，E(x)表示“是偶数” (1)x(E(x) x=1) (2)x(E(x)A「x=1) (3)x(E(x)A x=1) (4)x(E(x) —x=1) 再将它们的量词消去，表示成合取或析取命题公式，鉴别你所确定的真值是否正确。 解： (1)x(E(x) x真) x(E(x) —n可表示成命题公式(E (0) —n 0=1A (E (1) —n 1)1 其中E (0) —n 0真，E

谓词演算推证举例

设前提为?x?yF(x, y) ，下面的推证是否正确？ (1) ?x?yF(x, y) P (2) ?yF(y, y) T (1) US 解：推证不正确。 取解释I：个体域为R，在I下前提被解释为?x?y(x>y) ，为真； 而?yF(y, y)被解释为?y(y>y) ，为假。 所以推理不正确。 错误的原因是第(2)步违反了US规则成立的条件y不应在P(x)中约束出现。

设前提为?x?yF(x, y) ，下面的推证是否正确？ (1) ?x?yF(x, y) P (2) ?yF(t, y) T (1) US (3) F(t, c) T (2) ES (4)?xF(x,c) T (3) UG (5)?y?x F(x,y) T (4) EG 解：推证不正确。 取与例2.16相同的解释，则?x?yF(x,y)为真； 而?y?x F(x,y)意为“存在着最小实数”，是假命题， 所以推理不正确。 之所以出现这样的错误，是第(3)步违反了ES规则成立的条件 P(x)中除x外还有其他自由出现的个体变元时，不能用此规则。

试证明 ?x(P(x)→Q(x))∧?x(Q(x)→R(x))??x(P(x)→R(x))证：(1)?x(P(x)→Q(x)) P (2)P(y)→Q(y)T (1) US (3)?x(Q(x)→R(x)) P (4)Q(y)→R(y)T (3) US (5)P(y)→R(y) T (2)(4) I (6)?x(P(x)→R(x)) T (5) UG 证毕。

试证明 ?x(C(x)→W(x)∧R(x))∧?x(C(x)∧Q(x))??x(Q(x)∧R(x))证：(1) ?x(C(x)∧Q(x))P (2) C(a)∧Q(a)T (1) ES (3) ?x(C(x)→W(x)∧R(x))P (4)C(a)→W(a)∧R(a)T (3) US (5)C(a) T (2) I (6)W(a)∧R(a) T (4)(5) I (7)Q(a)T (2) I (8)R(a)T (6) I (9)Q(a)∧R(a)T (7)(8) I (10)?x(Q(x)∧R(x)) T (9) EG 证毕。

谓词逻辑_归结原理习题

谓词逻辑-归结原理例题 习题3.5, 1. (1) ()P x ：x 是大学生 ()Q x ：x 是诚实的 则命题可表示为： 已知：1:(()())G x P x Q x ?→， 2:()G Q a ? 证明：()P a ? 习题3.5, 1. (2) 将下面的命题符号化，并证明之：已知每一个运动员都是强壮的，而每一个既强壮又聪明的人在他所从事的事业中都能获得成功，彼得是运动员并且是聪明的，证明彼得在他的事业中将会成功。 提示：定义谓词 ()P x ：x 是运动员 ()Q x ：x 是强壮的 ()R x ：x 是聪明的 ()S x ：x 在他所从事的事业中获得成功。 则命题可表示为： 已知：1:(()())G x P x Q x ?→， 2:(()()())G x Q x R x S x ?∧→，()P a ，()R a 证明：()S a 提示：可用归结原理证明：（1）先把公式都化成Skolem 范式，（2）然后利用US ，ES 将公式中的量词除去，（3）化成合取范式，（4）化成蕴涵式，（5）化成子句集（结论用否定加入）， （6）进行归结，直至引出矛盾。 可化成如下子句集： {()()P x Q x →，()()()Q x R x S x ∧→，()P a →，()R a →，}()S a → 归结： （1）()()P x Q x → （2）()P a → （3）()Q a → 由（1）（2）

（4）()()()Q x R x S x ∧→ （5）()()R a S a → 由（3）（4） （6）()R a → （7）()S a → 由（5）（6） （8）()S a → （9） 由（7）（8） 习题3.5, 1. (3) ()E x ：x 进入国境 ()V x ：x 是重要人物 ()C x ：x 是海关人员 ()P x ：x 是走私者 (,)S x y ：y 检查x 已知： 1:((()())(()(,)))G x E x V x y C y S x y ?∧?→?∧， 2:(()()((,)()))G x P x E x y S x y P y ?∧∧?→ 3:(()())G x P x V x ?→? 证明：(()())x P x C x ?∧ 先化成子句集： {} 1((()())(()(,))) ((()())(()(,))) ((()()())(()()(,))) ()()(()),()()(,())G x E x V x y C y S x y x y E x V x C y S x y x y E x V x C y E x V x S x y E x V x C f x E x V x S x f x =??∧?∨?∧=???∨∨∧=???∨∨∧?∨∨?→∨→∨ {}2(()()((,)()))(),(),(,)()G x y P x E x S x y P y P a E a S a y P y =??∧∧→?→→→ 注意G2，如果理解成(()()(,)())x y P x E x S x y P y ??∧∧→，则还需有条件(()())x P x E x ?∧，最后同样能得到如上的子句集{}(),(),(,)()P a E a S a y P y →→→。不

人工智能原理教案02章 归结推理方法2.2 命题逻辑的归结

2.2命题逻辑的归结 2.2.1命题逻辑基础 逻辑可分为经典逻辑和非经典逻辑，其中经典逻辑包括命题逻辑和谓词逻辑。归结原理是一种主要基于谓词（逻辑）知识表示的推理方法，而命题逻辑是谓词逻辑的基础。因此，在讨论谓词逻辑之前，先讨论命题逻辑的归结，便于内容上的理解。 本节中，将主要介绍命题逻辑的归结方法，以及有关的一些基础知识和重要概念，如数理逻辑基本公式变形、前束范式、子句集等。 描述事实、事物的状态、关系等性质的文字串，取值为真或假（表示是否成立）的句子称作命题。 命题：非真即假的简单陈述句 在命题逻辑里，单元命题是基本的单元或作为不可再分的原子。下面所列出的是一些基本的数理逻辑公理公式和一些有用的基本定义，如合取范式、子句集，这些公式和定义在归结法的推理过程中是必不可少的，也是归结法的基础，应该熟练掌握。 －数理逻辑的基本定义 下面所列的是一些数理逻辑中重要的定义，在后面的分

析中要用到： ·合取式：p与q，记做p∧q ·析取式：p或q，记做p∨q ·蕴含式：如果p则q，记做p→q ·等价式：p当且仅当q，记做p q ·若A无成假赋值，则称A为重言式或永真式； ·若A无成真赋值，则称A为矛盾式或永假式； ·若A至少有一个成真赋值，则称A为可满足的； ·析取范式：仅由有限个简单合取式组成的析取式 ·合取范式：仅由有限个简单析取式组成的合取式 －数理逻辑的基本等值式 下面这些基本的等式在归结原理实施之前的公式转化过程中是非常重要的。只有将逻辑公式正确转换成为归结原理要求的范式，才能够保证归结的正常进行。 ·交换律：p∨q q∨p； p∧q q∧p ·结合律：(p∨q)∨r p∨(q∨r); (p∧q)∧r p∧(q∧r) ·分配律：p∨(q∧r)(p∨q)∧(p∨r)； p∧(q∨r)(p∧q)∨(p∧r)·双重否定律：p～～p ·等幂律：p p∨p；p p∧p

05-L.01 谓词逻辑的推理结构

? 离散数学基础 2017-11-19?定义：谓词逻辑的推理结构 ?设有谓词公式 A、B，若在令 A 为真的任一解释下，B 亦为真，则说 B 是 A 的逻辑推论，或称推理结构 A├ B 是正确的（或者有效的），记为 A ? B。 ?例1：所有的整数都是有理数，所有的有理数都是实数，所以所有的整数都是实 数。 ?解：设 P(x)：x 是整数。 Q(x)：x 是有理数。 R(x)：x 是实数。 形式化： ① (?x)(P(x) →Q(x)) ②(?x)(Q(x) →R(x)) ③(?x)(P(x) →R(x)) 推理结构： ①, ② ├ ③ ?例2：人总是要死的，苏格拉底是人，所以苏格拉底也是要死的。 ?解：设 P(x)：x 总是要死的。 Q(x)：x 是人。 形式化： ① (?x)(Q(x) →P(x)) ②Q(苏格拉底) ③P(苏格拉底) 推理结构： ①, ② ├ ③ ?例3：有一个人又高又胖，所以必有一个高个子和一个胖子。 ?解：设论域为人的集合 P(x)：x 是高的。 Q(x)：x 是胖的。 推理结构： (?x)(P(x)∧Q(x)) ├ (?x)P(x)∧(?x)Q(x) ?定理：演绎定理 ?设谓词公式 A、B，如果从 A 应用推理规则得到 B，并且在推出过程中，A 中

的自由变量保持不变，则A→B 是普遍有效的。 ?由于普遍有效性的不可判定性，在谓词逻辑中应用推理规则更为重要。 ?推理定理 ?若干常用的正确的推理形式： (1)(?x)P(x)∨(?x)Q(x) ? (?x)(P(x)∨Q(x)) (2)(?x)(P(x)∧Q(x)) ? (?x)P(x)∧(?x)Q(x) (3)(?x)(P(x)→Q(x)) ? (?x)P(x)→(?x)Q(x) (4)(?x)(P(x)→Q(x)) ? (?x)P(x)→(?x)Q(x) (5)(?x)(?y)P(x, y) ? (?y)(?x)P(x, y) (6)(?x)(?y)P(x, y) ? (?y)(?x)P(x, y) (7)(?x)(?y)P(x, y) ? (?x)(?y)P(x, y) ?推理定理 ?(3) 证：(?x)(P(x)→Q(x)) ? (?x)P(x)→(?x)Q(x) ?设 (?x)(P(x)→Q(x))=T ?当 (?x)P(x)=T时，对任意 x0，有P(x0)=T。 ?对此 x0，由假设知，P(x0)→Q(x0)=T ?故此时只能 Q(x0)=T ?从 x0 的任意性得 (?x)Q(x)=T ?即 (?x)P(x)→(?x)Q(x)=T ?故上述推理形式是有效的。 ?推理定理 ?(5) 证： (?x)(?y)P(x, y) ? (?y)(?x)P(x, y) ?设 (?x)(?y)P(x, y)=T ?即任意的 x 与所有的 y 都有 P(x, y)=T ?则对任意的 x 与某一固定的 y0，都有 P(x, y0)=T ?即 (?x)P(x, y0)=T ?故 (?y)(?x)P(x, y)=T ?即上述推理形式是有效的。 ?推理规则 ?在谓词逻辑的推理中，可以直接引用命题逻辑的推理规则。我们还需要建立一些新的推理规则处理与个体和量词相关的推理过程。 ?(1) 全称量词消去 US ?① (?x)A(x) ? A(y) –假设 y 不在 A(x) 中约束出现 ?② (?x)A(x) ? A(c) –假设 c 是个体域中的任一常量 ?(2) 全称量词引入 UG

谓词逻辑

第二章 谓词逻辑 学习指导 2 .1 谓词逻辑的基本概念 谓词 在原子命题中，所描述的对象称为个体，用以描述一个个体的性质或多个个体间关系的部分，称为谓词。一般用大写字母P ，Q ，R ，… 等来表示它们。另外这些大写字母还可以用来表示一个谓词所在的位置，而不表示具体的谓词，此时称之为谓词符号。如果一个谓词描述n 个个体的性质或关系，那么称此谓词为n 元谓词。表示一个n 元谓词所在位置的字母称为n 元谓词符号。约定0元谓词符号为命题变元。 个体常元和个体变元 表示具体的，特指的个体词，称为个体常元，常用小写字母 , … 或带下标的小写字母, … 来表示。同样这些小写字母也可以用来表示一个个体常元所在的位置，而不表示具体的个体常元，此时称之为个体常元符号。表示抽象的，泛指的或在一定范围内变化的个体词，称为个体变元，常用小写字母c b a ,,i i i c b a ,,z y x ,,, … 或 带下标的小写字母, … 来表示。 个体变元的取值范围称为个体域，常用大写字母表示。个体常元符号与个体变元是两个不同的概念，例如对个体变元可以加量词，但对个体常元符号却不能加。 i i i z y x ,,D n 元谓词函数 设P 为一个元谓词符号，为个个体变元，由它们组成的称为n 元谓词函数。本身不是一个命题， 但在用具体的谓词代替P ，用n 个个体常元分别代替个个体变元n n x x x ",,21n ),,(21n x x x P "),,(21n x x x P "n 12,,,n x x "x 之后，它就是一个命题了。 量词 （1） 符号“”称为全称量词符，用来表达个体域中所有个体，对应于自然语言中“对所有的”，“每一个”，“对任何一个”和“一切”等词语。?x ?称为全称量词，x 称为其指导变元。 （2）符号“”称为存在量词符，用来表达个体域中某个或某些个体，对应于自然语言中“存在一些”，“至少有一个”，“对于一些”和“有的”等词语。?x ?称为存在量词，x 称为其指导变元。 全总个体域 由宇宙间一切事物组成的个体域称为全总个体域。 一般地，命题中个体变元的个体域是被明确给出的，如果没有明确给出个体域，那么我们就认为个体域是全总个体域。 特性谓词 我们把为了确定个体变元的取值范围而引进的谓词称为特性谓词。一般地对全称量词的指导变元限制取值范围用特性谓词和条件式，对存在量词的指导变元限制取值范围用特性谓词和合取式。 2 .2. 谓词公式

7 逻辑代数(下)：谓词演算 习题答案

练习5.1 1. 指出下列谓词公式中的量词及其辖域，指出各自由变元和约束变元，并作适当更改，同时回答它们是否是命题： （1）?x(P(x)∨Q(x))∧R （2）?x(P(x)∧Q(x))∧?xS(x)→T(x) （3）?x(P(x)→?y(B(x,y)∧Q(y))∨T(y)) （4）P(x)→( ?y?x(P(x) ∧B(x,y))→P(x)) 解： （1）全称量词?，辖域P(x)∨Q(x)，其中x为约束变元，?x(P(x)∨Q(x))∧R是命题。不需要更改变元。 （2）全称量词?，辖域P(x)∨Q(x)，其中x为约束变元。 存在量词?，辖域S(x) ，其中x为约束变元。 T(x)中x为自由变元。 ?x(P(x)∧Q(x))∧?xS(x)→T(x)不是命题。 公式中x既是自由变元又是约束变元，可更改变元为如下公式： ?x(P(x)∧Q(x))∧?yS(y)→T(z) （3）全称量词?，辖域P(x)→?y(B(x,y)∧Q(y))∨T(y)，其中x为约束变元，存在量词?，辖域B(x,y)∧Q(y)，其中y为约束变元。 T(y) 中y为自由变元。 ?x(P(x)→?y(B(x,y)∧Q(y))∨T(y))不是命题。 公式中y既是自由变元又是约束变元，可更改变元为如下公式： ?x(P(x)→?y(B(x,y)∧Q(y))∨T(z))不是命题。 （4）全称量词?，辖域?x(P(x)∧B(x,y))，其中y为约束变元。 存在量词?，辖域P(x)∧B(x,y)，其中x为约束变元。 不在量词辖域中的P(x)（第一个和第三个P(x)）中的x为自由变元。 P(x)→(?y?x(P(x)∧B(x,y))→P(x))不是命题。 公式中x既是自由变元又是约束变元，可更改变元为如下公式： P(z)→(?y?x(P(x)∧B(x,y))→P(z)) 2．对个体域{0，1}判定下列公式的真值, E(x)表示“x是偶数”： （1）?x(E(x)→┐x=1) （2）?x(E(x)∧┐x=1) （3）?x(E(x)∧x=1) （4）?x(E(x)→x=1) 再将它们的量词消去,表示成合取或析取命题公式，鉴别你所确定的真值是否正确。 解: （1）?x(E(x)→┐x=1) 真 ?x(E(x)→┐x=1) 可表示成命题公式（E(0)→┐0=1）∧（E(1)→┐1=1） 其中E(0)→┐0=1真，E(1)→┐1=1也真，故（E(0)→┐0=1）∧（E(1)→┐1=1）真。（2）?x(E(x)∧┐x=1) 假 ?x(E(x)∧┐x=1) 可表示成命题公式（E(0) ∧┐0=1）∧（E(1) ∧┐1=1）