人工智能基础及应用 课件 第1、2章 绪论、确定性推理

人工智能第1章绪论

1.1

人工智能及其衡量智能机器准则国家级一流本科线上线下混合式课程“人工智能”什么是人工智能？衡量智能机器的标准：图灵测试主要内容百度上说：“智能化”：是指由现代通信与信息技术、计算机网络技术、行业技术、智能控制技术汇集而成的针对某一个方面的应用。智能家电智能楼宇智能交通能够制造和使用工具人类与动物的重要区别利用工具来减轻劳动强度，提高劳动效率。用人工的方法在机器上实现智能，这就是人工智能。如何在机器上实现人类智能，减轻脑力劳动者的劳动强度,提高效率脑力劳动者人工智能的定义

人工智能是一门研究如何构造智能机器（或智能系统），使它能模拟、延伸、扩展人类智能的学科。英国数学家图灵（A.M.Turing,1921〜1954）图灵机——现代计算机的数学模型图灵奖——

计算机科学的最高奖衡量智能机器的标准：图灵测试可以通话，但彼此都看不到对方总结

人工智能的概念衡量智能机器的准则

作业：你觉得要实现人工智能，最重要的因素是什么？请给出你的理由请您设想，如何衡量机器是否具有“感性的思考”?（其中的相关名词等自主学习）第1章绪论

1.2

人工智能研究历史和研究途径人工智能主要内容一、人工智能的发展历史二、人工智能的研究途径

事物发展的一般规律一、人工智能的发展历史

1、孕育阶段（1956年之前）2、形成阶段（1956年〜1970年）3、发展阶段（1970年〜现在）二、人工智能的发展历史理论基础物质基础提出“人工智能”一词国际学术组织国际会议国际学术期刊逻辑程序设计语言PROLOG专家系统MYCIN等等机器翻译问题求解专家系统和知识工程自然语言理解机器学习计算智能生物计算等等人机棋类大战仿真机器人机器翻译“Timeflieslikeanarrow”“Thespiritiswillingbutthefleshisweak”“Thewineisgoodbutthemeatisspoiled”二、人工智能的主要研究途径（主要学派）符号主义(Symbolicism)：又称逻辑主义(Logicism)或计算机学派(Computerism)连接主义(Connectionism)：又称仿生学派(Bionicsism)行为主义(Actionism):又称进化主义(Evolutionism)1、符号主义（Symbolicism）方法：逻辑演绎智能的基本单元：符号思维：符号计算，认为人工智能源于数理逻辑理论体系："启发式算法→专家系统→知识工程理论与技术"2、连接主义(Connectionism)方法：仿生学的方法智能的基本单元：神经元认知过程是由神经元构成的网络的信息传递的过程原理：神经网络及神经网络间的连接机制与学习算法3、行为主义(Actionism)方法：进化论的思想人工智能起源：控制论原理：控制论和机器学习算法总结

人工智能的研究历史

孕育、形成、发展人工智能的研究途径

符号主义连接主义行为主义作业：你认为在未来人工智能会给人类社会带来什么？你觉得未来的智能机器能够超越人类的智能吗？请给出理由。人工智能第1章绪论

1.3人工智能研究内容和研究领域一、人工智能的研究内容二、人工智能的研究领域主要内容一、人工智能的研究内容智能智能是什么?智能是怎样发生的？智能有什么特点？人工智能研究内容智能机器思维理论认为：智能是脑活动的产物，来自于大脑的思维活动。知识阈值理论认为：智能就是在巨大的搜索空间中迅速找到满意解的能力。有表达的智能或没有推理的智能认为：智能是某种复杂系统所浮现的性质，是没有表达的、没有推理的。智能是知识与智力的总和，知识是智能的基础，智力是获取并运用知识求解问题的能力。智能的发生与物质的本质、宇宙的起源、生命的本质被称为自然界的四大奥秘，至今也无法破解。1、具有感知能力2、具有记忆与思维的能力3、具有学习能力及自适应能力4、具有行为和表达能力1、机器感知：2、机器思维3、机器学习4、机器行为5、智能系统及其构造技术思维是一个动态过程，是获取知识以及运用知识求解问题的根本途径。思维逻辑思维：具有依靠逻辑进行、过程线性严谨可靠、易于形式化形象思维：具有依靠直觉，过程非线性（并行协同式），形式化困难，在缺少信息的情况下仍有可能得到比较满意的结果。顿悟思维：具有不定期的突发性、非线性的独创性及模糊性，起着突破、创新、升华的作用，目前还不能描述其产生和实现机理。人工智能的研究内容机器感知：所谓的机器感知就是使机器（计算机）具有类似于人的感知能力，其中以机器视觉和机器听觉为主。机器思维：所谓的机器思维是指对通过感知得来的外部信息及机器内部的各种工作信息进行有目的的处理。主要工作包括：知识表示、知识管理、推理、搜索及推理系统工作原理等。机器学习：机器学习就是使计算机具有获取新知识、学习新技巧，并在实践中不断完善和改进的能力，达到自动获取知识的能力，包括通过阅读、谈话、实践等各种方式去学习。机器行为：机器行为主要指机器的行动能力和表达能力，包括“动作”、“运动”、“说”、“写”、“画”等能力。智能系统及其构造技术：研究智能系统的模型、系统分析、系统构造技术、系统集成技术等。二、人工智能的研究领域1、问题求解：包括问题表示空间的研究、搜索策略的研究和归约策略的研究2、机器学习机器学习是指计算机自身具有学习能力，能够自动获取新的事实及新的推理算法。机器学习方法：机械式学习、讲授式学习、类比式学习、归纳式学习、观察发现式学习、基于解释的学习、基于事例的学习、基于概念的学习、基于神经网络的学习、遗传学习等3、专家系统专家系统专家系统的重要事件专家系统的发展路线：单一知识库多知识库集中式专家系统分布式专家系统手工获取方式半自动化式知识库推理机知识获取方系统构造：单一推理机多推理机确定性推理或简单的不确定性推理多种不确定性推理、非单调推理、模糊推理等4、自动定理证明著名成果：海伯伦（Herbrand）理论鲁滨逊（Robinson）理论我国的吴文俊院士的“吴方法”获2000年度国家最高科学技术奖获2000年度国家最高科学技术奖获2000年度国家最高科学技术奖5、自然语言理解：

就是研究如何让计算机理解人类自然语言的一个研究领域6、机器人学第一代机器人可编程控制机器人自动程序设计、机器视觉、模式识别、人工神经网络等等第二代机器人自适应机器人第三代机器人智能机器人研究内容机器感知：机器思维机器学习机器行为智能系统及其构造技术

总结：问题求解机器学习专家系统自动定理证明自然语言理解机器人学机器视觉研究领域作业：

你对人工智能的那个研究领域感兴趣？你认为这个研究领域的研究目标是什么？目前国内外学者研究到什么程度了？人工智能第1章

绪论

1.4智能的应用及未来人工智能的应用人工智能的未来人工智能面临的挑战人工智能发展带来的机遇主要内容一、人工智能的应用*智能是什么？*智能在哪里应用？*人工智能在哪里应用？自然科学里心理学家认为智能感觉记忆思维智慧行为语言能力知识智力自然界四大奥秘：智能的发生、物质的本质宇宙的起源、生命的本质无处不在无时不有AlphaGo2015年10月欧洲围棋冠军樊麾2016年3月世界围棋冠军李世石2017年5月世界围棋冠军排名世界第一柯洁2017年5月27日退役深度学习世界围棋顶尖高手2016年12月~2017年1月二、人工智能的未来人工智能可以分为：弱人工智能（ArtificialNarrowIntelligence，简称ANI）是指仅在单个领域较强的人工智能程序强人工智能（ArtificialGeneralIntelligence，简称AGI）是指能够达到人类级别的人工智能程序。二、人工智能的未来网络特征：

侧重于描述人类社会乃至物理社会广泛连接的状态

大数据特征：

侧重描述新社会状态下的内容形态和数字本位状态人工智能特征：

描述了新的社会创造物和广泛的机器介入的社会状态人类的新时代：虚拟现实技术三、人工智能面临的挑战机器的自主学习能力还需要突破机器意识处于零起步阶段人工智能技术的标准化、规范化等问题伦理、法律与社会问题、隐私保护等许多社会问题人类的控制能力问题四、人工智能发展带来的机遇

人工智能必将推动社会的发展和变革美国《国家人工智能发展与研究战略计划》（TheNationalArtificialIntelligenceResearchandDevelopmentStrategicPlan）《为人工智能的未来做好准备》（PreparingfortheFutureoftheArtificialIntelligence）中国国家“十三五”规划纲要，人工智能相关学科列入国家未来几年的重要发展战略。

《“互联网+”人工智能三年行动实施方案》目的之一“加快人工智能产业发展”

人工智能经济增长社会进步主要驱动力中国梦助力实现人工智能网络大数据生活方式政府提供服务方式商业运转方式新的社会生活方式感谢您的关注l联系方式：周军辽宁工业大学电子与信息工程学院，

Email：zhoujun@梅红岩辽宁工业大学电子与信息工程学院，

Email：dxxy_mhy@课程中用到的图片等资源大多来源于公开的网络资源。人工智能第2章确定性推理

国家级一流本科线上线下混合式课程“人工智能”人工智能第2章确定性推理

2.1

确定性推理与不确定推理确定性推理的基本内容*推理：是指从已知的事实出发，用已掌握的知识，推导出其中蕴含的

事实性结论或归纳出某些新结论的过程。---人工智能系统的推理过程实际上就是一种思维过程，即运用知识进行推理来求解问题的过程。依据知识的确定性

确定性推理不确定性推理确定性推理：就是指推理时所用的知识都是精确的，推出的结论也是确定的，其值或者为“真”或者为“假”没有第三种情况出现。

知识如何表示推理的依据是什么推理的过程又是怎样人工智能第2章确定性推理

2.2

谓词逻辑推理方法一阶谓词逻辑表示法谓词逻辑推理方法求解问题的一般步骤谓词逻辑推理方法的应用举例主要内容一阶谓词逻辑表示法命题逻辑命题：能够分辨真假的语句称为命题。原子命题：一个语句如果不能再进一步分解成更简单的语句，并且又

是一个命题，则称此命题为原子命题。原子命题是命题中的基本单位，一般用大写的P、Q、R、S…等表示。若命题的意义为真，称它的真值为真，记为T。若命题的意义为假，称它的真值为假，记为F。一个命题可在一种条件下为真，在另一种条件下为假。*谓词公式：就是用谓词联接符号将一些谓词联接起来所形成的公式。3<5

太阳从西边升起

1＋1＝2命题逻辑：研究命题及命题之间关系的符号逻辑系统。命题逻辑表示法的局限性：无法把它所描述的客观事物的结构及逻辑特征反映出来，也不能把不同事物间的共同特征表述出来。P：李白是诗人Q：杜甫也是诗人R:老李是小李的父亲一阶谓词逻辑表示法谓词逻辑原子命题分为谓词和个体两部分。*谓词公式：就是用谓词联接符号将一些谓词联接起来所形成的公式。用于刻画个体的性质、状态或个体间的关系可以独立存在的物体，可以是抽象的、也可以是具体的

例如：李白是诗人PoetLiBai谓词表示Poet(LiBai)5>3X<6Greater(5,3)Less(x,6)谓词的一般形式为：

P(x1,x2,…,xn)个体谓词名谓词的元数例如：P(x),Q(x,y),R(x,y,z)个体域连接词有:（1）﹁：“否定”（negation）或“非”。（2）∨：“析取”（disjunction）——或。（3）∧：“合取”（conjunction）——与。（4）→：“蕴含”(implication)或“条件”(condition)。（5）

：“等价”（equivalence）或“双条件”（bicondition）。一阶谓词逻辑表示法对应的真值表为:连接词的优先级别从高到低排列：﹁，∧，∨，→，量词有:（1）全称量词（universalquantifier)：“对个体域中的所有（或任一个）个体x”。

（2）

存在量词（existentialquantifier)：“在个体域中存在个体x”。

一阶谓词逻辑表示法例如:可按下面的规则得到谓词公式：

一阶谓词逻辑表示法(4)若A是谓词公式，则

A，

A也是谓词公式。(1)单个谓词是谓词公式，称为原子谓词公式。(2)若A是谓词公式，则﹁A也是谓词公式。

(3)若A，B都是谓词公式，则A∧B，A∨B，A→B，A

B也都是谓词公式。有限步应用（1）－（4）生成的公式也是谓词公式。怎样应用谓词公式来表示知识呢？63一阶谓词逻辑表示法

*一般步骤：

首先定义谓词及个体，确定每个谓词及个体的确切含义。然后依据所要表达的事物或概念，为每个谓词中的变元赋予特定的值。最后根据所要表达的知识的语义，用适当的连接符号将各个谓词连接起来，形成谓词公式。例如：李是一名计算机系的学生，但他不喜欢编程序。解：按照知识表示的步骤，用谓词公式表示上述知识。首先：定义谓词如下：

COMPUTER(X)：x是计算机系的学生。LIKE(x,y)：x喜欢y。

涉及的个体有：

李(Li)，编程序(programming)然后：将这些个体代入到谓词中，得到

COMPUTER(Li)，~LIKE(Li,programming)最后：根据语义用连接词将它们连接起来，就

得到上述知识的谓词公式：

COMPUTER(Li)∧~LIKE(Li,programming)

案例分析系列谓词逻辑推理方法之机器人搬弄盒子问题

用谓词逻辑推理方法进行问题求解—案例机器人搬弄盒子问题：在房间的c处有一个机器人，在a和b处各有一张桌子，a桌子上有一个盒子，如图所示（初始状态）。现需要机器人将a桌子上的盒子移到b桌子上，然后回到c处，如图所示（目标状态）。初始状态目标状态如何用一阶谓词逻辑来表示这一问题，并对其进行求解呢？

acbacb用谓词逻辑推理方法进行问题求解—案例初始状态目标状态acbacb解：先定义谓词和确定个体：则定义谓词如下：TABLE(x)：x是桌子；EMPTY(y)：y手中是空的；AT(y,z)：y在z附近；HOLDS(y,w)：y拿起w；ON(w,x)：w在x上面。对应的个体分别为：

x：{a，b}；y：{robot}；z：{a，b，c}；w：{box}。AT(rabot,c)∧EMPTY(rabot)∧ON(box,a)∧TABLE(a)∧TABLE(b)AT(rabot,c)∧EMPTY(rabot)∧ON(box,b)∧TABLE(a)∧TABLE(b)用谓词逻辑推理方法进行问题求解—案例acb用谓词逻辑推理方法进行问题求解—案例acbGOTO(x,y)：从x处走到y处条件：AT(robot,x)动作：删除：AT(robot,x)

增加：AT(robot,y)PICK-UP(x)：在x处拿起盒子(box)条件：TABLE(x)∧ON(box,x)

∧AT(robot,x)∧EMPTY(robot)动作：删除：ON(box,x)∧EMPTY(robot)

增加：HOLDS(robot,box)SET-DOWN(x)：在x处放下盒子条件：TABLE(x)∧AT(robot,x)

∧HOLDS(robot,box)动作：删除：HOLDS(robot,box)

增加：ON(box,x)∧EMPTY(robot)用谓词逻辑推理方法进行问题求解—案例机器人搬弄盒子问题的具体过程：初始状态acb目标状态acbAT(rabot,c)∧EMPTY(rabot)∧ON(box,a)∧TABLE(a)∧TABLE(b)AT(rabot,a)∧EMPTY(rabot)∧ON(box,a)∧TABLE(a)∧TABLE(b)GOTO(c,a)GOTO(x,y)用c替换x，a替换yAT(rabot,a)∧HOLDS(robot,box)∧TABLE(a)∧TABLE(b)PICK-UP(x)用a代换xPICK-UP(a)AT(rabort,b)∧HOLDS(robort,box)∧TABLE(a)∧TABLE(b)AT(rabort,b)∧ON(box,b)∧EMPTY(robort)∧TABLE(a)∧TABLE(b)AT(rabort,c)

∧ON(box,b)∧EMPTY(rabort)∧TABLE(a)∧TABLE(b)GOTO(x,y)用a替换x，b替换yGOTO(x,y)GOTO(a,b)SET-DOWN(x)用b代换xGOTO(x,y)用b替换x，c替换yGOTO(b,c)SET-DOWN(b)一阶谓词逻辑表示法具有如下特点

自然性：其形式接近于自然语言，易于被人理解和接受。精确性：谓词公式非真即假，能够精确的表示知识，进行确定性推理。严密性：谓词逻辑具有严格的形式定义与推理规则。易实现：易于转换为计算机的内部形式，易于模块化。不足之处：不能表示不精确、不确定、模糊性的知识。作业：

总结课后请大家思考，在机器人搬积木的问题中，当某一状态可同时满足多个操作的条件时，应选用哪一个操作？在进行变量代换时，如果存在多种代换的可能性，如何确定用哪一个？课堂练习用谓词表示法求解农夫、狼、山羊、白菜问题。农夫、狼、山羊、白菜全部放在一条河的左岸，现在要把他们全部送到河的右岸去，农夫有一条船，过河时，除农夫外船上至多能载狼、山羊、白菜中的一种。狼要吃山羊，山羊要吃白菜，除非农夫在那里。似规划出一个确保全部安全过河的计划。请写出所用谓词的定义，并给出每个谓词的功能及变量的个体域。

人工智能第2章确定性推理

2.3

自然演绎推理方法自然演绎推理方法的基本内容自然演绎推理方法的推理规则自然演绎推理方法的应用举例主要内容自然演绎推理的基本内容*按照推理的逻辑基础推理分为：演绎推理、归纳推理和默认推理。演绎推理：就是从已知的一般知识出发，推理出适合于某种个别情况的结论的过程，是一种由一般到个别的推理方法。最常用的演绎推理形式是三段论式，包括：

大前提是已知的一般性知识或推理过程得到的判断；小前提是关于某种具体情况或某个具体实例的判断；例如：有如下三个判断：

①

计算机系的学生都会编程序；

（一般性知识）

②

程强是计算机系的一位学生；

（具体情况）

③

程强会编程序。

（结论）结论是由大前提推出的，并且适合于小前提的判断。

自然演绎推理的基本内容自然演绎推理：就是从一组已知为真的事实出发，直接运用命题逻辑或谓词逻辑中的推理规则推出结论的过程。

谓词公式的永真性、可满足性、等价性和永真蕴涵

谓词公式的永真性：如果谓词公式P，对于个体域D上的任何一个解释都取得真值T，则称P在D上是永真的；如果P在每个非空个体域上均永真，则称P永真。

谓词公式的永假性：如果谓词公式P，对于个体域D上的任何一个解释都取得真值F，则称P在D上是永假的；如果P在每个非空个体域上均永假，则称P永假。谓词公式的可满足性：对于谓词公式P，如果至少存在一个解释使得公式P在此解释下的真值为T，则称公式P是可满足的。谓词公式的不可满足性：对于谓词公式P，如果不存在任何解释，使得公式P的真值为T，则称公式P是不可满足的。等价的自然演绎推理的基本内容谓词公式的永真性、可满足性、等价性和永真蕴涵

谓词公式的等价性：设Ｐ和Ｑ是两个谓词公式，Ｄ是它们公共的个体域。若对Ｄ上的任何一个解释，Ｐ与Ｑ的取值都相同，则称公式Ｐ和Ｑ在域Ｄ上式等价的。如果Ｄ是任意个体域，则称Ｐ和Ｑ是等价的，记为。谓词公式的永真蕴涵：对于谓词公式P和Q，如果永真，则称P永真蕴涵Q，且称Q为P的逻辑结论，称P为Q的前提，记为。常用等价式常用蕴涵式交换律结合律吸收律补余律逆否律

推理规则化简式附加式拒取式

自然演绎推理的推理规则常用等价式常用蕴涵式交换律结合律吸收律补余律逆否律

推理规则化简式附加式拒取式

案例分析系列自然演绎推理之问题证明

用自然演绎推理进行问题证明—案例例1:设已知如下事实：

A,B,A→C,B∧C→D,D→Q

求证：Q为真。证明：因为

A,A→C⇒C

假言推理及P规则

B,C⇒B∧C

引入合取词

B∧C，B∧C→D⇒D

假言推理及T规则

D,D→Q⇒Q

假言推理及T规则

因此，Q为真。用自然演绎推理进行问题证明—案例例2:设已知如下事实：(1)只要是需要室外活动的课，郝亮（Hao）都喜欢。(2)所有的公共体育课都是需要室外活动的课。(3)篮球（Ball）是一门公共体育课课。求证：郝亮喜欢篮球这门课。Outdoor(x)

x是需要室外活动的课。Like(x,y)x喜欢y。Sport(x)x是一门公共体育课证明：①依据已知事实定义如下谓词：②把已知事实及待求解问题用谓词公式表示如下：(1)Outdoor(x)→Like(Hao,x)(2)(∀x)(Sport(x)→Outdoor(x))(3)Sport(Ball)待求解的问题：Like(Hao,Ball)③应用推理规则进行推理：因为有(∀x)(Sport(x)→Outdoor(x))所以

Sport(y)→Outdoor(y)全称固化又Sport(Ball)，Sport(y)→Outdoor(y)⇒Outdoor(Ball)假言推理{Ball/y}又Outdoor(Ball),Outdoor(x)→Like(Hao,x)⇒Like(Hao,Ball)假言推理

{Ball/x}所以原题得证：郝亮喜欢篮球这门课。主要优点：定理证明过程自然，易于理解，并且有丰富的推理规则可用。

主要缺点：容易产生知识爆炸，推理过程中得到的中间结论一般按指数规律递增，对于复杂问题的推理不利，甚至难以实现。

总结

所谓肯定后件的错误是指：当为真时，希望通过肯定后件Q为真来推出前件P为真。这是错误的推理逻辑，请问为什么？

所谓否定前件的错误是指：当为真时，希望通过否定前件P来推出后件Q为假，这也是不允许的，请问为什么？人工智能第2章确定性推理

2.4

归结演绎推理方法子句与子句集的基本概念归结原理的基本内容应用归结原理进行定理证明与问题求解

主要内容定理证明的实质*证明P→Q永真*应用反证法即证明﹁(P→Q)是永假的，也就是不可满足的。﹁(﹁P∨Q)所以，只要能够证明P∧﹁Q是不可满足的就可以了。P∧﹁Q

等价变换﹁(P→Q)那么，如何证明P∧﹁Q是不可满足的呢？子句与子句集定义1不含有任何连接词的谓词公式叫原子公式，简称原子。例如，P(x)、Q(x)、﹁P(x)、﹁Q(x)等都是文字。定义2原子或原子的否定统称为文字。定义3子句就是由一些文字组成的析取式。定义4不含任何文字的子句称为空子句。定义5由子句或空子句所构成的集合称为子句集。例如，P(x)∨Q(x)，P(x，f(x))∨Q(x，g(x))都是子句。例如，{P(x)∨Q(x)，P(x，f(x))∨Q(x，g(x))，NIL}就是一个子句集。由于空子句不含有任何文字，也就不能被任何解释所满足，因此空子句是永假的，是不可满足的。空子句可表示为NIL.谓词公式到子句集的转换如果将谓词公式G的Skolem标准型前面的全称量词全部消去，并用逗号，代替合取符号∧，便可得到谓词公式G的子句集S。例如，有谓词公式G=(∀x)((∀y)P(x,y)→﹁(∀y)(Q(x,y)→R(x,y)))依据等价变化和谓词公式化为Skolem标准型的步骤有：

(∀x)((﹁P(x,f(x))∨Q(x,g(x))∧(﹁P(x,f(x))∨﹁R(x,g(x))))化为合取范式(∀x)((∀y)P(x,y)→﹁(∀y)(Q(x,y)→R(x,y)))(∀x)(﹁(∀y)P(x,y)∨﹁(∀y)(﹁Q(x,y)∨R(x,y)))消去蕴涵(∀x)((∃y)﹁P(x，y)∨(∃y)(Q(x，y)∧﹁R(x，y)))减少否定符号的辖域

(∀x)((∃y)﹁P(x，y)∨(∃z)(Q(x，z)∧﹁R(x，z)))变元重新命名，使所有变元的名字均不相同(∀x)(∃y)(∃z)(﹁P(x，y)∨(Q(x，z)∧﹁R(x，z)))量词前移(∀x)(﹁P(x,f(x))∨(Q(x,g(x))∧﹁R(x,g(x))))应用Skolem函数消去存在量词则谓词公式G的子句集S为：S={(﹁P(x,f(x))∨Q(x,g(x))，(﹁P(x,f(x))∨﹁R(x,g(x)))}Skolem标准型

Robinson的归结原理定理1设有谓词公式G，而其相应的子句集为S，则G是不可满足的充分必要条件是S是不可满足的。

子句集中各子句之间是合取的关系，因此，其中只要有一个子句是不可满足的，则子句集就是不可满足的。

空子句是不可满足的。所以，只要子句集中包含一个空子句，则此子句集一定是不可满足的。

基本思想检查子句集S中是否有空子句，若有，则表明S是不可满足的；若没有，就在子句集中选择合适的子句对其进行归结推理，如果能推出空子句，就说明子句集是不可满足的。1965年，Robinson鲁滨逊提出了一种证明子句集不可满足性的方法，称为归结原理。

命题逻辑中的归结原理定义6若P是原子谓词公式或原子命题，即为文字，则称

P与﹁P为互补文字。例：设C1=P∨Q∨R，C2=﹁P∨S，求C1和C2的归结式C12。定义7归结与归结式：设C1和C2是子句集中的任意两个子句，

如果C1中的文字L1与C2中的文字L2互补，那么可从C1

和C2中分别消去L1和L2，并将C1和C2中余下的部分按

析取关系构成一个新的子句C12，则称这一过程为归结，

称C12为C1和C2的归结式，称C1和C2为C12的亲本子句。解：这里L1=P，L2=﹁P，通过归结可以得到C12=Q∨R∨S命题逻辑中的归结原理例：设C1=﹁P∨Q，C2=﹁Q，C3=P，求C1、C2、C3的归结式C123。解：若先对C1、C2归结，可得到C12=﹁P

然后再对C12和C3归结，得到C123=NIL如果改变归结顺序，同样可以得到相同的结果，即其归结过程是不唯一的。其归结过程可用右图来表示，该树称为归结树。命题逻辑中的归结原理定理2归结式C12是其亲本子句C1和C2的逻辑结论。推论1：设C1和C2是子句集S中的两个子句，C12是C1和C2的归结式，若用C12代替C1和C2后得到新的子句集S1，则由S1的不可满足性可以推出原子句集S的不可满足性。即：S1的不可满足性⇒S的不可满足性推论2：设C1和C2是子句集S中的两个子句，C12是C1和C2的归结式，若把C12加入S中得到新的子句集S2，则S与S2的不可满足性是等价的。即：S2的不可满足性⇔S的不可满足性证明：设C1=L∨C1’，C2=﹁L∨C2’关于解释I为真，则只需证C12=C1’∨C2'

关于解释I也为真。

对于解释I，L和﹁L中必有一个为假。

若L为假，则必有C1'为真，不然就会使C1为假，这将与前提假设

C1为真矛盾，因此只能有C1'为真

同理，若﹁L为假，则必有C2'为真。

因此，必有C12=C1'∨C2'关于解释I也为真。即C12是C1和C2的逻辑结论。定理3子句集S是不可满足的，当且仅当存在一个从S到

空子句的归结过程。谓词逻辑中的归结原理定义8设C1和C2是两个没有公共变元的子句，L1和L2分别是

C1和C2中的文字。如果L1和L2存在最一般合一σ，则称

C12=({C1σ}-{L1σ})∪({C2σ}-{L2σ})

为C1和C2的二元归结式，而L1和L2为归结式上的文字。例：设C1=P(x)∨Q(a)，C2=﹁P(b)∨R(x)，求C12解：由于C1和C2有相同的变元x，不符合定义的要求。为了进行归结，需要修改C2中变元的名字，令C2=﹁P(b)∨R(y)。此时L1=P(x),L2=﹁P(b)，L1和L2的最一般合一是σ={b/x}。则有C12=({C1σ}-{L1σ})∪({C2σ}-{L2σ})=({P(b),Q(a)}-{P(b)})∪({﹁P(b),R(y)}-{﹁P(b)})=({Q(a)})∪({R(y)})={Q(a),R(y)}=Q(a)∨R(y)归结演绎推理方法*归结原理指出了证明子句集不可满足的方法*对于定理证明，即要证明谓词公式G=P→Q永真应用归结原理，只需证明P∧﹁Q所对应的子句集是不可满足的也就是通过归结，归结出一个空子句

应用反证法，即证明﹁(P→Q)是永假的，也就是不可满足的。欲证明﹁(P→Q)是不可满足的，只需证明P∧﹁Q是不可满足的

案例分析系列归结演绎推理之定理证明与问题求解

用归结演绎推理进行问题证明—步骤定理证明：通过上面的学习，应用归结原理进行定理证明的步骤

可归纳如下：设要被证明的定理可用谓词公式表示为：G=P→Q①否定结论Q，得﹁Q;②把﹁Q并入到公式集P中，得到G=P∧﹁Q；③把{G=P∧﹁Q}化为其对应的子句集S。④应用归结原理对子句集S中的子句进行归结，并把每次得到的归结式并入S中。如此反复进行，若出现空子句，则停止归结，此时就证明了G为真。用归结演绎推理进行定理证明—案例例:已知：P=(∀x)((∃y)(A(x,y)∧B(y))→(∃y)(C(y)∧D(x,y)))Q=﹁(∃x)C(x)→(∀x)(∀y)(A(x,y)→﹁B(y))

证明:Q是P的逻辑结论，即证明P→Q永真。{(∀x)((∃y)(A(x,y)∧B(y))→(∃y)(C(y)∧D(x,y)))∧﹁(﹁(∃x)C(x)→(∀x)(∀y)(A(x,y)→﹁B(y)))}证明：①依据证明步骤：先把Q否定，并入

到公式集P中，得到G=P∧﹁Q如下：②再把G=P∧﹁Q化为其对应的子句集，得到如下5个子句：(1)﹁A(x,y)∨﹁B(y)∨C(f(x))(2)﹁A(u,v)∨﹁B(v)∨D(u,f(u))(3)﹁C(z)(4)A(m,n)(5)B(k)③最后应用谓词逻辑的归结原理对上述子句集进行归结，其过程为：由(1)和(3)归结，取置换：σ={f(x)/z}得：(6)﹁A(x,y)∨﹁B(y)由(4)和(6)归结，取置换：σ={m/x,n/y}得：(7)﹁B(n)由(5)和(7)归结，取置换：σ={n/k}得：(8)NIL因此，Q是P的逻辑结论。例:“快乐学生”问题假设：①任何通过计算机考试并获奖的人都是快乐的，

②任何肯学习或幸运的人都可以通过所有考试，

③张不肯学习但他是幸运的，

④任何幸运的人都能获奖。求证：张是快乐的。Pass(x,y)x可以通过y考试Win(x,prize)x能获得奖励Study(x)x肯学习Happy(x)x是快乐的Lucky(x)x是幸运的

解：①

对其进行求解时，先定义谓词：②再将问题用谓词表示如下：①(∀x)(Pass(x,computer)∧Win(x,prize)→Happy(x))②(∀x)(∀y)(Study(x)∨Lucky(x)→Pass(x,y))③﹁Study(zhang)∧Lucky(zhang)④(∀x)(Lucky(x)→Win(x,prize))

结论“张是快乐的”的否定

﹁Happy(zhang)③接下来按照