一阶谓词逻辑题目

●镇江的夏天既炎热又潮湿

解：定义谓词

hot(X,Summer)：X地的夏天很炎热

wet(X,summer)：X地的夏天很潮湿

该知识可以表示为

hot(Zhenjiang,summer)∧wet(Zhenjiang,summer)

●有人每天下午都去打篮球。

解：定义谓词

P(x)：x是人

B(x)：x打篮球

?

A(y)：y是下午

将知识用谓词表示为：

(?x)(?y) (A(y)→B(x)∧P(x))

●新型计算机速度又快，存储容量又大

解：定义谓词

NC(x)：x是新型计算机

F(x)：x速度快

B(x)：x容量大

将知识用谓词表示为：

(?x) (NC(x)→F(x)∧B(x))

●不是每个信息系的学生都喜欢在计算机上编程序。解：定义谓词

S(x)：x是信息系学生

L(x, pragramming)：x喜欢编程序

U(x,computer)：x使用计算机

将知识用谓词表示为：

?(?x) (S(x)→L(x, pragramming)∧U(x,computer))

●所有的消防车都是红色的

解: 定义谓词

Fireengine(x) : x是消防车

Color(x, y) : x的颜色是y

red:表示红色

该知识可以表示为：

(?x)( Fireengine(x))→Color(x, red)

对于所有的x, 如果x是消防车，那么x的颜色是红色的●所有的自然数，不是奇数就是偶数

解：定义谓词

N(x) : 表示x是自然数

O(x) : 表示x是奇数

E(x) : 表示x是偶数

该知识可表示为：

(?x)( N(x))→(O(x) ∨E(x))

●305房间有个物体

解：定义谓词

In（x，y）：x在y里面

Room（x）：x是房间

r305：305房间

（?x）In（x，Room（r305））

●每个车间都有一个人负责

有一个人是所有车间的负责人

解：定义谓词：

Workshop（x）：x是个车间

Head（y,x）: y是x的负责人

以上知识可表示为：

(?x)(?y)( Workshop（x）→Head（y,x）) (?y)(?x)( Workshop（x）→Head（y,x）)

谓词逻辑归结原理源代码

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

第3章谓词逻辑

谓 词 逻 辑 原子命题是命题逻辑中最基本的组成单元，不能对它再作进一步的分解，但同时也无法反映出某些原子命题的共同特征和相互关系。 例如，用p表示命题“小李是大学生”，用q表示命题“小王是大学生”，在命题逻辑的范畴中它们是两个独立的原子命题，p和q之间没有任何关系。但是，命题“小李是大学生”和“小王是大学生”之间有着相同的结构和内在的联系，它们都具有相同的谓语（及宾语）“是大学生”，不同的只是主语，它们都描述了“是大学生”这样一个共同的特性；而使用原子命题表示时并没有能将这一共性刻画出来。 再如著名的苏格拉底三段论： 凡是人都是要死的。 苏格拉底是人。 所以苏格拉底是要死的。 这个推理显然是正确的。但是，如用p、q、r分别表示上面3个命题，由于p∧q?r不是永真式，因此它不是正确的推理；也就是说，当p和q都为真时，得不出r一定为真。其根本原因在于命题逻辑不能将命题p、q、r间的内在的联系反映出来。 为了克服命题逻辑的局限性，引入了谓词和量词对原子命题和命题间的相互关系做进一步的剖析，从而产生了谓词逻辑。 谓词逻辑亦称一阶逻辑，它同命题逻辑一样，是数理逻辑中最基础的内容。 §3.1谓词、量词与自然语句形式化 §3.1.1 谓词 在谓词逻辑中，一般将原子命题分解为个体词和谓词两个部分。 定义3.1个体词（individual）是一个命题里表示思维对象的词，表示独立存在的具体或抽象的客体。简单地讲，个体词就表示各种事物，相当于汉语中的名词。具体的、确定的个体词称为个体常项，一般用a、b、c表示；抽象的、不确定的个体词称为个体变项，一般用x、y、z表示。个体变项的取值范围称做个体域或论域（domain of the discourse），宇宙间一切事物组成的个体域称做全总个体域（universal domain of individuals）。 注：本书在提及论域时，如未特别说明，指的都是全总个体域。 定义3.2在命题中，表示个体词性质或相互之间关系的词称做谓词（predicate）。

离散数学第二章一阶逻辑知识点总结

数理逻辑部分 第2章一阶逻辑 2.1 一阶逻辑基本概念 个体词（个体）: 所研究对象中可以独立存在的具体或抽象的客体个体常项：具体的事物，用a, b, c表示 个体变项：抽象的事物，用x, y, z表示 个体域: 个体变项的取值范围 有限个体域，如{a, b, c}, {1, 2} 无限个体域，如N, Z, R, … 全总个体域: 宇宙间一切事物组成 谓词: 表示个体词性质或相互之间关系的词 谓词常项：F(a)：a是人 谓词变项：F(x)：x具有性质F 一元谓词: 表示事物的性质 多元谓词(n元谓词, n2): 表示事物之间的关系 如L(x,y)：x与y有关系L，L(x,y)：x y，… 0元谓词: 不含个体变项的谓词, 即命题常项或命题变项 量词: 表示数量的词 全称量词: 表示任意的, 所有的, 一切的等 如x 表示对个体域中所有的x 存在量词: 表示存在, 有的, 至少有一个等 如x表示在个体域中存在x 一阶逻辑中命题符号化 例1 用0元谓词将命题符号化 要求：先将它们在命题逻辑中符号化，再在一阶逻辑中符号化 (1) 墨西哥位于南美洲 在命题逻辑中, 设p:墨西哥位于南美洲 符号化为p, 这是真命题 在一阶逻辑中, 设a：墨西哥，F(x)：x位于南美洲 符号化为F(a)

例2 在一阶逻辑中将下面命题符号化 (1) 人都爱美; (2) 有人用左手写字 分别取(a) D为人类集合, (b) D为全总个体域. 解：(a) (1) 设G(x)：x爱美, 符号化为x G(x) (2) 设G(x)：x用左手写字, 符号化为x G(x) (b) 设F(x)：x为人，G(x)：同(a)中 (1) x (F(x)G(x)) (2) x (F(x)G(x)) 这是两个基本公式, 注意这两个基本公式的使用. 例3 在一阶逻辑中将下面命题符号化 (1) 正数都大于负数 (2) 有的无理数大于有的有理数 解注意: 题目中没给个体域, 一律用全总个体域 (1) 令F(x): x为正数, G(y): y为负数, L(x,y): x>y x(F(x)y(G(y)L(x,y))) 或 x y(F(x)G(y)L(x,y)) 两者等值 (2) 令F(x): x是无理数, G(y): y是有理数, L(x,y)：x>y x(F(x)y(G(y)L(x,y))) 或x y(F(x)G(y)L(x,y)) 两者等值 几点注意： 1元谓词与多元谓词的区分 无特别要求，用全总个体域 量词顺序一般不能随便颠倒 否定式的使用 思考： ①没有不呼吸的人 ②不是所有的人都喜欢吃糖 ③不是所有的火车都比所有的汽车快 以上命题应如何符号化？ 2.2 一阶逻辑合式公式及解释字母表 定义字母表包含下述符号： (1) 个体常项：a, b, c, …, a i, b i, c i, …, i1 (2) 个体变项：x, y, z, …, x i, y i, z i, …, i 1 (3) 函数符号：f, g, h, …, f i, g i, h i, …, i1 (4) 谓词符号：F, G, H, …, F i, G i, H i, …, i1 (5) 量词符号：, (6) 联结词符号：, , , , (7) 括号与逗号：(, ), ， 定义项的定义如下： (1) 个体常项和个体变项是项. (2) 若(x1, x2, …, x n)是任意的n元函数，t1,t2,…,t n

离散数学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}，求θ与λ的合成。 解： 先求出集合

一阶谓词逻辑题目

●镇江的夏天既炎热又潮湿 解：定义谓词 hot(X,Summer)：X地的夏天很炎热 wet(X,summer)：X地的夏天很潮湿 该知识可以表示为 hot(Zhenjiang,summer)∧wet(Zhenjiang,summer) ●有人每天下午都去打篮球。 解：定义谓词 P(x)：x是人 B(x)：x打篮球 ? A(y)：y是下午 将知识用谓词表示为： (?x)(?y) (A(y)→B(x)∧P(x)) ●新型计算机速度又快，存储容量又大 解：定义谓词 NC(x)：x是新型计算机 F(x)：x速度快 B(x)：x容量大 将知识用谓词表示为： (?x) (NC(x)→F(x)∧B(x)) ●不是每个信息系的学生都喜欢在计算机上编程序。解：定义谓词 S(x)：x是信息系学生 L(x, pragramming)：x喜欢编程序 U(x,computer)：x使用计算机 将知识用谓词表示为： ?(?x) (S(x)→L(x, pragramming)∧U(x,computer)) ●所有的消防车都是红色的 解: 定义谓词 Fireengine(x) : x是消防车 Color(x, y) : x的颜色是y red:表示红色 该知识可以表示为： (?x)( Fireengine(x))→Color(x, red) 对于所有的x, 如果x是消防车，那么x的颜色是红色的●所有的自然数，不是奇数就是偶数 解：定义谓词 N(x) : 表示x是自然数 O(x) : 表示x是奇数

E(x) : 表示x是偶数 该知识可表示为： (?x)( N(x))→(O(x) ∨E(x)) ●305房间有个物体 解：定义谓词 In（x，y）：x在y里面 Room（x）：x是房间 r305：305房间 （?x）In（x，Room（r305）） ●每个车间都有一个人负责 有一个人是所有车间的负责人 解：定义谓词： Workshop（x）：x是个车间 Head（y,x）: y是x的负责人 以上知识可表示为： (?x)(?y)( Workshop（x）→Head（y,x）) (?y)(?x)( Workshop（x）→Head（y,x）)

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

河南城建学院 《人工智能》实验报告 实验名称：实现基于谓词逻辑的归结原理 成绩：____ 专业班级： 学号： 姓名： 实验日期：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<<"------------------求子句集九步法演示-----------------------"<

人工智能课后答案第三章

1.基于谓词逻辑的机器推理方法：自然演绎推理，归结演绎推理，基于规则的演绎推理。 2. 求下列谓词公式的子句集 (1) x y(P(x,y) Q(x,y)) 解：去掉存在量词变为：P(a,b) Q(a,b) 变成子句集{ P(a,b),Q(a,b )} (2) x y(P(x,y) Q(x,y)) 解：去掉蕴涵符号变为：x y(? P(x,y) Q(x,y)) 去掉全称量词变为：? P(x,y) Q(x,y) 变成子句集{ ? P(x,y) Q(x,y)} (3) {()[(,)(,,)]}x P x y zQ x z zR x y z ?→??∨? ()(,)(,(),)P x Q x z R x f x z ?∨∨ (4)((,,,,,)(,,,,,)(,,,,,))x y z u v w P x y z y v w Q x y z y v w R x y z u v w ??????∨∧ {p(a,y,f(y),y,v,g(y,v)) Q(a,y,f(y),y,v,g(y,v)), p(a,x,f(x),x,z,g(x,z)) R(a,x,f(x),h(x),z,g(x,z))} 3. 试判断下列子句集中哪些是不可满足的 （1）使用删除策略 （2）归结 4.用合一算法求下列公式集的最一般合一。 （1）W={Q(a,x),Q(y,b)} 最一般合一为:{a/y,b/y} （2）{()((,))}W Q x y z Q u h v v u =，，，，， 最一般合一为：{z/u,h(v,v)/y,z/x}或{x/u,h(v,v)/y,x/z} 5.用归结原理证明，G 是否可肯定是F 的逻辑结果。 (1) F 1 ( x)(P(x)(Q(x)∧R(x)) F 2 ( x) (P(x) ∧S(x) G (x)(S(x) ∧R(x))

谓词逻辑_归结原理习题

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

离散数学答案 第三章 谓词逻辑

第三章 谓词逻辑 习题3.1 1．解 ?个体：离散数学；谓词：…是一门计算机基础课程。 ?个体：田亮；谓词：…是一名优秀的跳水运动员。 ?个体：大学生；谓词：…要好好学习计算机课程；量词：所有。 ?个体：推理；谓词：…是能够由计算机来完成的；量词：一切。 2． 解 ?设)(x F ：x 是舞蹈演员；a ：小芳。命题符号化：)(a F 。 ?设)(x F ：x 是一位有名的哲学家；a ：苏格拉底。命题符号化：)(a F 。 ?设)(x F ：x 作完了他的作业家；a ：张三。命题符号化：)(a F 。 ?设)(x F ：x 身体很好；a ：我。命题符号化：)(a F 。 3．解 ?选取个体域为整数集合。设)(x F ：x 的平方是奇数；)(x G ：x 是奇数。命题符号化：)()(x G x F →。 ?选取个体域为所有国家的集合。设)(x F ：x 在南半球；)(x G ：x 在北半球。命题符号化：)()(x xG x xF ?∧?。 ?选取个体域为所有人的集合。设)(x F ：x 在中国居住；)(x G ：x 是中国人。命题符号化：))()((x G x F x ?→??? ?选取个体域为所有人的集合。设)(x M ：x 是艺术家；)(x F ：x 是导演；)(x G ：x 是演员。命题符号化：?x (M (x )∧F (x )∧G (x ))。 ?选取个体域为所有猫的集合。设M (x )：x 是好猫；F (x )：x 捉耗子。命题符号化： ?x ?M (x )∧?x (F (x )→M (x ))。 4．解 ?①设)(x F ：x 喜欢开汽车；)(x G ：x 喜欢骑自行车。命题符号化：)()(x xG x xF ?∧?。 ②设)(x F ：x 喜欢开汽车；)(x G ：x 喜欢骑自行车；)(x M ：x 是人。命题符号化： ))()(())()((x G x M x x F x M x ∧?∧∧?。 ?①设)(x F ：x 必须学好数学。命题符号化：)(x xF ?。 ②设)(x F ：x 必须学好数学；)(x M ：x 是学生。命题符号化：))()((x F x M x →?。 ?①设)(x F ：x 的平方是质数；)(x M ：x 是质数。命题符号化： ))()((x F x M x ?→?。 ②同①。

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

第三章 谓词逻辑

第三章谓词逻辑 例3.2.1 在谓词逻辑中将下列命题符号化： （1）每个人都有心脏。 （2）有的狗会飞。 解：（1）若将个体域取为人的集合，且H(x)：x有心脏， 则该命题符号化为：?x H(x)。如果将个体域取作所有生物的集合，则需要引入表示人的集合的特性谓词P.P(x)：x是人。这时，该命题可符号化为：?x(P(x)→H(x))。 例3.2.2 将命题“并非A中的每个数都小于或等于B中的每个数”按以下要求的形式表达出来： （1）出现全称量词，但不出现存在量词； （2）出现存在量词，但不出现全称量词。 解：（1）??x（x∈A →?y(y∈B → x≤y)）. （2）?x（x∈A ∧?y(y∈B ∧ x>y)）. 说明：可以证明二者是等价的： ??x（x∈A →?y(y∈B → x≤y)）= ?x?（?（x∈A）∨?y(?（y∈B）∨ x≤y)） = ?x（??（x∈A）∧??y(?（y∈B）∨ x≤y)）= ?x（x∈A∧?y(??（y∈B）∧?( x≤y)) = ?x（x∈A ∧?y(y∈B ∧ x>y)） 3.2.2 求谓词公式在解释下的真值 设P(x)是一元谓词，D是个体域，由?x P(x)和?xP(x)的真值指定知，当D={x0，x1，…}是可数集合时， ?xP(x)的真值为P(x0)∧P(x1)∧… ?xP(x)真值为P(x0)∨P(x1)∨… 这时，判断一个谓词公式在某一解释下的真值可通过按上面两个等价式先将该公式中的量词消除，写成与之等价的命题公式，再进行判断。 例3.2.4 设个体域D={1，2，3}，P(x) ：x>2。试判断下列公式的真值： (1) ?xP(x) →P(2)； (2) P(3) →?xP(x). 解：（1）?xP(x) →P(2) 等价于(P(1) ∨P(2) ∨P(3)) →P(2) 所以真值为(0∨0∨1) →0=1 →0=0 (2) P(3) →?xP(x) 等价于1→( P(1) ∧P(2) ∧P(3)) 所以真值为1→( 0 ∧0 ∧1)=1 →0=0 例3.2.5 构造解释I（假设个体域D={a,b}），使得I弄假如下公式： （2）??xP(x) →?x?P(x)； (2)??xP(x) →?x?P(x)= ?xP(x) ∨?x?P(x)= ( P(a) ∧ P(b)) ∨(? P(a) ∧?P(b)) (3)= ( P(a) ∨?P(b)) ∧( ?P(a) ∨P(b)) 由此可见，若取 P(a)=1，P(b)=0， 则该解释弄假( P(a) ∨?P(b)) ∧( ?P(a) ∨P(b))，亦即弄假??xP(x) →?x?P(x)。 3.2.3 使用量词时的注意事项 1. 注意量词的使用顺序 多个量词连续出现，它们之间无括号分隔时，后面的量词在前面量词的作用域内，且量词