第二章基于谓词逻辑的机器推理讲解.ppt

第二章 基于谓词逻辑的机器推理 李伟生 信科大厦19楼 Telliws@cqupt.edu.cn 第2章??? 基于谓词逻辑的机器推理 逻辑学是研究人如何正确地思维以达到认识客观真理的科学，它包括形式逻辑和辨证逻辑两部分。形式逻辑又名静态逻辑或初等逻辑，它着重研究思维形式的结构及其规律。辩证逻辑又名动态逻辑或高等逻辑，它是全面研究思维的形式和内容，研究思维的辨证发展规律的科学。形式逻辑反映的是认识过程处在量变阶段的规律，它完成的是已知规律的逻辑推理。辩证逻辑反映的是认识过程处在质变阶段的规律，它研究的是人的认识的发生、发展和完善的全过程。 数理逻辑是用数学方法研究逻辑学的科学，目前仅局限在形式逻辑范围内。数理逻辑以命题演算和一阶谓词演算为基础。在数理逻辑中，仅关心推理在形式上的有效性，而不涉及推理的内容本身。命题逻辑与谓词逻辑是最先应用于人工智能的两种逻辑，对于知识的形式化表示，特别是定理的自动证明发挥了重要作用，在人工智能的发展史中占有重要地位。本节主要介绍命题逻辑，在下一节介绍谓词逻辑。 2.1.1 命题 2.1.2 命题定律 2.1.3 范式 2.1.4 命题逻辑的局限性 定义2.1 命题（Proposition）：命题是具有真假意义的语句。 命题代表人们进行思维时的一种判断，或者是肯定，或者是否定，只有这两种情况。如果命题的意义为真，称它的真值为真，记作T；如果命题的意义为假，称它的真值为假，记作F。一个命题不能同时既为真又为假，但可以在一定条件下为真，在另一种条件下为假。没有真假意义的语句(如感叹句、疑问句等)不是命题。例如，“北京是中华人民共和国的首都”、“35” 等都是真值为T的命题；“太阳从西边升起”，“煤球是白色的”都是真值为F的命题。“1+1=10”在二进制情况下是真值为T的命题，但在十进制情况下却是真值为F的命题。同样，对于命题“今天是雨天”，也要看当天的实际情况才能决定其真值。 如果一个命题不能进一步分解为更简单的命题，则此命题叫原子命题（或本原命题、原始命题）。使用适当的联结词，可以把原子命题组合成复合命题或分子命题。 在命题逻辑中，命题通常用大写的英文字母表示，例如可用英文字母P表示“北京是中国的首都”这个命题。英文字母表示的命题既可以是一个特定的命题，也可以是一个抽象的命题，前者称为命题常量，后者称为命题变元。当“P”表示某个特定命题时，我们说P 是一个命题常量，它的真值就是该特定命题的真值。当“P”仅是任意命题的位置标志符时，我们说P 是一个命题变元，它没有真值。在数理逻辑中，命题变元不代表一个确定的命题，没法确定其真值，但可以用任意一个给定的命题取代它。这时就可以给出P的真值。也就是说可以给命题变元任意指派真值。在命题逻辑中常把命题变元简称为变元。 定义2.2 命题联接词：在数理逻辑中也有类似的严格定义过的联结词，叫命题联接词。常用的命题联接词有五个：合取、析取、否定、蕴含、双条件。它们的定义如表2-1所示。 定义2.3 合式公式：合式公式是指： ① 孤立的命题变元或逻辑常量是一个合式公式（叫原子公式）； ② 如果A是一个合式公式，则~A也是一个合式公式； ③ 如果A和B是合式公式，则（A∧B）、（A∨B）、（A→B）和（A ? B）都是合式公式； ④ 当且仅当经过有限次使用规律①、②、③得到的由命题变元、联结词符号和圆括号所组成的字符串，才是合式公式。 为了减少括号的使用次数，特作如下简化的规定： ① 联结词运算的优先级从高到低为：~，∧，∨，→， ? ； ② 同级联结词中，先出现的先运算； ③ 最外层的括号可以省去，在上述优先级规定下，凡省去后不会引起二义性的括号，均可省去。 定义2.4 真值指派：设有一个由n个变元P1，P2，...，Pn所组成的谓词公式A，则A的取值由这n个变元唯一确定。如果给（P1，P2，...，Pn）一组确定的值（Pi=T或F，i=1,2,...,n），则A有一确定的真值（T或F ）。我们把变元的一组取值叫做公式的一个真值指派。 真值表：由公式的所有真值指派和对应的公式真值所组成的表叫该公式的真值表。例如公式（P→Q）∧（Q→P）的真值表可构造如表2-2所示。 表2-2 公式（P→Q）∧（Q→P）逻辑真值表 给定一个公式，如果对于所有的真值指派，它的真值都是T，则称该公式为永真式（或重言式）；如果对于所有的真值指派，它的真值都是F，则称该公式为永假式（或不可满足的）；除了这两种极端情况外，一般的命题公式的真值有T有F。称非永假的公式为可满足的公式。 定义2.5 等价（Equivalence）：设A、B都是命题公式，Pi(i=1,2,...,n)是出现在A和B中的所有命题变元。如果对于