第四章-谓词逻辑归结基本方法

谓词逻辑归结原理源代码

#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;

离散数学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，或记为?-）

第二章 谓词逻辑

第二章谓词逻辑 1.什么叫做客体和客体变元？如何表示客体和客体变元？ 2.么叫做谓词？ 3.什么叫做论域？我们定义一个“最大”的论域叫做什么？ 4.填空题： 1．存在量词：记作( )，表示( )或者( )或者( )。 2．全称量词：记作( )，表示( )或者( )或者( )。 5.什么叫做量词的作用域？指出下面两个谓词公式中各个量词的作用域。 ?x(F(x,y)→?yP(y))∧Q(z)∧?xA(x) ?x?y?z(A(x,y)→B(x,y,z))∧C(t) 6.什么叫做约束变元？什么叫做自由变元？指出下面公式中哪些客体变元是约束变元？哪些客体变元是自由变元？ ?x(F(x,y)→?yP(y))∧Q(z)∧?xA(x) 7.填空：一个谓词公式如果无自由变元，它就表示一个( )。 8.给出的谓词 J(x)：x是教练员， L(x) ：x是运动员， S(x) ：x是大学生，O(x) ：x是年老的，V(x) ：x是健壮的，C(x) ：x是国家选手，W(x) ：x是女同志， H(x) ：x是家庭妇女，A(x,y)：x钦佩y。客体 j：金某人。用上面给出的符号将下面命题符号化。 1．所有教练员是运动员。 2．某些运动员是大学生。 3．某些教练是年老的，但是健壮的。 4．金教练既不老，但也不是健壮的。 5．不是所有运动员都是教练。 6．某些大学生运动员是国家选手。 7．没有一个国家选手不是健壮的。 8．所有老的国家选手都是运动员。 9．没有一位女同志既是国家选手又是家庭妇女。 10．有些女同志既是教练又是国家选手。 11．所有运动员都钦佩某些教练。

12．有些大学生不钦佩运动员。 9.将下面命题符号化 1．金子闪光,但闪光的不一定都是金子。 2．没有大学生不懂外语。 3．有些液体可以溶解所有固体。 4．每个大学生都爱好一些文体活动。 5．每个自然数都有唯一的后继数。 10.令P表示天气好。Q表示考试准时进行。A(x)表示x是考生。B(x)表示x提前进入考场。C(x)表示x取得良好成绩。E(x,y)表示x=y。利用上述符号，分别写出下面各个命题的符号表达式。 1．如果天气不好，则有些考生不能提前进入考场。 2．只有所有考生提前进入考场，考试才能准时进行。 3．并非所有提前进入考场的考生都取得良好成绩。 4．有且只有一个提前进入考场的考生未能取得良好成绩。 11.将下面命题符号化。 1．对一个大学生来说，仅当他刻苦学习，才能取得优异成绩。 (S(x):x是大学生；Q(x):x取得了优异成绩；H(x):x刻苦学习。) 2．每个不等于0的自然数，都有唯一的前驱数。 (Z(x):x是自然数； E(x,y):x=y； Q(x,y):y是x的前驱数。) 12.是偏序集，B是A的非空子集。在括号内分别写入y是B的极小元、最小元、下界相应的谓词表达式。 y是B的极小元?( ) y是B的最小元?( ) y是B的下界?( ) 13.设论域D={1,2} 又已知a=1 b=2 f(1)=2 f(2)=1 P(1,1)=T P(1,2)=T P(2 ,1)=F P(2,2)=F 求谓词公式?x?y(P(x,y)→P(f(x),f(y)))的真值。(要求有解题的过程)

第二章 谓词逻辑 1.原子命题的内部结构

第二章 谓词逻辑 一、原子命题的内部结构 12．谓词逻辑·谓词和个体词·量词、全称量词和存在量词·个体域·量词的辖域·自由 个体变项和约束个体变项·一阶谓词逻辑 什么是谓词逻辑 在第一章中，我们知道，命题逻辑的根本特征，就在于把原子命题作为基本的单位，对原子命题的内部结构不再进行分析。在思维实际中，有时我们不涉及原子命题的内部结构，例如，命题推理只涉及命题之间的关系，这时命题逻辑的工具就足够了。但在更多的情况下需要涉及原子命题的内部结构。例如： 推理1： 所有的人都是要死的。 苏格拉底是人。 所以，苏格拉底是要死的。 推理1包括三个不同的原子命题，经过相应的设定后，它的真值形式是()r q p →∧。这不是一个重言式。因此，这个显然有效的推理在命题逻辑个被判定无效。这是因为，推理1的有效性的根据不在原于命题之间的关系，而在于原子命题内部的构成要素之间的关系。命题逻辑无法解决这样的推理的判定问题。传统逻辑中的词项逻辑把原子命题进一步分析为主项、谓项、量项和联项的合式构成，这样它就能处理命题逻辑所无法处5理的许多推理，如推理1这样的三段论。但是，词项逻辑的处理能力有着很大的局限。例如： 推理2： 所有的罪犯或者是故意犯罪，或者是过失犯罪。 有些罪犯不是故意犯罪。 因此，有些罪犯是过失犯罪。 这个有效性同样明显的推理的判定，命题逻辑解决不了，词项逻辑同样解决不了。 为了更为有效和尽量不失—般性地解决推理的判定，需要提出新的逻辑工具，进—步分析原子命题的内部结构。这就是谓词逻辑的任务。 在谓词逻辑中，原子命题被进一步分析为谓词、个体词、量词和联结词这样几个基本成分。谓词、个体词和量词是谓词逻辑中新引入的概念，联结词作为符号就是真值联结词。 谓词和个体词 我们通过以下实例来说明什么是谓词和个体词。 (1) 这张桌子是方的。 (2) 陈先生是贾女土的丈夫。 显然，以上两个命题都是原子命题。 在(1)中，今F(x)表示“x 是方的”，a 表示“这张桌子”，这样，F(a)就表示“这张桌子是方的”，也就是说，命题(1)的表达式是F(a)。这里，F 就是谓词，表示“方”这种性质；x 和a 就是个体词，表示具有“方”这种性质的个体。其中，x 称为个体变项，它只表示某一个个体，而不表示一个确定的个体；a 称为个体常项，它表示一个确定的个体，即这张桌子。 在(2)中，令H(x ，y)表示“x 是y 的丈夫”，a 表示陈先生，b 表示贾女士，这样，H(a ，b)就表示“陈先生是贾女士的丈夫”，也就是说，命题(2)的表达式是H(a ，b)。这里，H 是谓词，表示某人是某人的丈夫”这种关系，x 、y 和a 、b 是个体词，同样，x 和y 是个体变项，a 和b 是个体常项。

人工智能原理教案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<<"------------------求子句集九步法演示-----------------------"<

第2章谓词逻辑习题及答案

谓词逻辑习题 1. 将下列命题用谓词符号化。 （1）小王学过英语和法语。 （2）2大于3仅当2大于4。 （3）3不是偶数。 （4）2或3是质数。 （5）除非李键是东北人，否则他一定怕冷。 解： (1) 令)(x P ：x 学过英语，Q(x)：x 学过法语，c ：小王，命题符号化为)()(c Q c P ∧ (2) 令),(y x P ：x 大于y, 命题符号化为)3,2()4,2(P P → (3) 令)(x P ：x 是偶数，命题符号化为)3(P ? (4) 令)(x P ：x 是质数，命题符号化为)3()2(P P ∨ (5) 令)(x P ：x 是北方人；)(x Q ：x 怕冷；c ：李键；命题符号化为)()(x P c Q ?→ 2. 设个体域}{c b a D ，，=，消去下列各式的量词。 （1）))()((y Q x P y x ∧?? （2）))()((y Q x P y x ∨?? （3）)()(y yQ x xP ?→? （4）))()((y yQ y x P x ?→?， 解： (1) 中))()(()(y Q x P y x A ∧?=，显然)(x A 对y 是自由的，故可使用UE 规则，得到 ))()(()(y Q y P y y A ∧?=，因此))()(())()((y Q y P y y Q x P y x ∧?∧??α，再用ES 规则， )()())()((z Q z P y Q y P y ∧∧?α，D z ∈，所以)()())()((z Q z P y Q x P y x ∧∧??α （2）中))()(()(y Q x P y x A ∨?=，它对y 不是自由的，故不能用UI 规则，然而，对 )(x A 中约束变元y 改名z ，得到))()((z Q x P z ∨?，这时用UI 规则，可得： ))()((y Q x P y x ∨?? ))()((z Q x P z x ∨??? ))()((z Q x P z ∨?α （3）略 （4）略 3. 设谓词)(y x P ，表示“x 等于y ”，个体变元x 和y 的个体域都是}321{，，=D 。求下列各式 的真值。 （1）)3(，x xP ? （2）)1(y yP ，? （3）)(y x yP x ， ?? （4）)(y x yP x ， ?? （5）)(y x yP x ，?? （6）)(y x xP y ，?? 解： (2) 当3=x 时可使式子成立，所以为Ture 。 (3) 当1≠y 时就不成立，所以为False 。

谓词逻辑_归结原理习题

谓词逻辑-归结原理例题 习题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 →→→。不

谓词逻辑

第二章谓词逻辑 在命题逻辑中，我们把原子命题看作命题演算和推理的基本单位，是不可再分的整体。因而命题逻辑无法研究命题的内部结构及命题之间的内在联系，甚至无法有效地研究一些简单的推理。 例如，著名的“苏格拉底三段论”：凡是人都是要死的；苏格拉底是人；所以苏格拉底是要死的。我们知道，这个推理是正确的，但用命题逻辑无法说明这一点。 设p:凡人都是要死的；q：苏格拉底是人；r：苏格拉底是要死的。则“苏格拉底三段论”可符号化为（p∧q）→r。显然（p∧q）→r不是重言式。 因此，为了能够进一步深入地研究推理，需要对原子命题做进一步的分析。 2.1 谓词逻辑的基本概念 2.1.1 个体与谓词 我们可以将原子命题的结构分解为个体和谓词。 定义2.1-1 个体(Individual)：个体是我们思维的对象，它是具有独立意义、可以独立存在的客体。 谓词(Predicate)：谓词是表示一个个体的性质或若干个个体之间的关系的词。 个体和谓词一起构成了原子命题中的主谓结构。 例2.1-1?海水是咸的。 ?张强与张亮是兄弟。 ?无锡位于上海与南京之间。 ?、?、?都是原子命题，其中海水、张强、张亮、无锡、上海和南京都是个体，“…是咸的”、“…与…是兄弟”和“…位于…与…之间”都是谓词。?中的谓词描述了一个个体的性质，称为一元谓词，?中的谓词表示两个个体之间的关系，称为二元谓词，?中的谓词表示三个个体之间的关系，称为三元谓词。依次类推，我们将描述n个个体之间关系的谓词称为n元谓词，通常用大写英文字母来表示谓词。为方便起见，将命题称为零元谓词。 例如，例2.1-1中的三个谓词可符号化为： P(x)：x是咸的；Q(x，y)：x与y是兄弟；R(x，y，z)：x位于y和z之间。 这里P 、Q 和R表示的都是具体的谓词，称为谓词常元；否则称为谓词变元。P(x)、Q(x，y)和R(x，y，z)等都是谓词表示的函数形式，通常称为谓词函数，简称为谓词。 然而，仅仅一个谓词，即使是谓词常元，也不能构成一个命题。例如谓词P(x)就不是一个命题。这是因为谓词P(x)中的个体x不是一个确定的个体，称其为个体变元。只有将个体变元代以用具体或者特定的个体时，才能构成命题，我们称其中具体或者特定的个体为个体常元。 例2.1-2设P(x)：x是咸的；Q(x，y)：x与y是兄弟；R(x，y，z)：x位于y和z之间。a表示“海水”，b表示“张强”，c表示“张亮”，d表示“无锡”，e表示“上海”，f表示“南京”。

人工智能原理教案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. 谓词公式