02-2.4 前束范式PPT

US规则(全称量词消去规则) UG规则(全称量词附加规则) ES规则(存在量词消去规则) EG规则(存在量词附加规则)等
2.5 谓词逻辑地推理理论
课堂练习
本章小结
本章重点：谓词与量词，公式与解释，前束范式，
谓词逻辑推理证明
主要概念：谓词 个体词 量词 变元前束范式 推理规
则
主要方法：推理规则（US规则 UG规则 ES规则 EG规则） 主要公式： (1)命题公式的推广；(2) 量词否定式的
2.2 谓词公式
变元与辖域
自由变元有时会在量词辖域中出现，但是它 不受相应量词指导变元的约束。
当谓词公式中没有自由变元时，它就是一个 命题。
出现n个自由变元就是n元谓词。 变元可以既是约束出现又是自由出现。
例子：P44
2.2 谓词公式
换名规则：
对约束变元进行换名 就是把公式中量词的指导变元及其该量词辖域中的
2.2 谓词公式
相关概念：
字母表
项：递归定义 P43
原子公式
2.2 谓词公式
合式公式
递归定义：P43
命题常数0，1，一个命题和命题变元以及一个命题 函数P(x1,x2,…,xn)，统称原子公式
由原子公式、联结词和量词可构成谓词公式(严格定 义见教材).
命题的符号化结果都是谓词公式。
约束变元换成该公式中没有出现的个体变元，公式
的其余部分不变.
代入规则：
对自由变元进行代入 就是把公式中的某一自由变元，用该公式中没有出
现的个体变元符号替代，且要把该公式中所有的该
自由变元都换成新引入的该符号.
经过换名或代入后，公式的意义不应该改变
2.2 谓词公式
课堂练习
对P44 例1中公式用换名或代入规则

然而，(P∧Q)R并不是永真式，故上述 推理形式又是错误的。一个推理，得出矛盾的 结论
问题在哪里呢? ? ?
问题就在于这类推理中，各命题之间的逻辑关系 不是体现在原子命题之间，而是体现在构成原子命题 的内部成分之间，即体现在命题结构的更深层次上。
对此，命题逻辑是无能为力的。 所以，在研究某些推理时，有必要对原子命题作
③符号!称为存在唯一量词符，用来表达 “恰有一个”、“存在唯一”等词语；!x称为 存在唯一量词，称 x 为指导变元。
全称量词、存在量词、存在唯一量词统称量 词。
量词记号是由逻辑学家Fray引入的，有了量 词之后，用逻辑符号表示命题的能力大大加强了。
例：(1) 所有的人都是要死的。
(2) 有的人活百岁以上。 一、考虑个体域 D 为人类集合
列规则形成的符号串： P60 ① 原子谓词公式是谓词合式公式；
② 若A是谓词合式公式，则(¬A)是谓词合式公式； ③ 若A、B是谓词合式公式，则(A∧B)，(A∨B)， (AB)和(AB)都是谓词合式公式； ④ 若A是谓词合式公式，x是个体变元，则(x)A、 (x)A都是谓词合式公式； ⑤ 只有经过有限项次地使用①、②、③、④形成的 才是谓词合式公式。——简称为谓词公式。
例如：令 f(x,y) 表示 x+y，谓词 N(x) 表示x是 自然数，那么 f(2,3) 表示个体自然数 5，而 N(f(2,3))表示 5是自然数。
这里函数是就广义而言的。
例如：P(x): x是教授，f(x): x的父亲，c: 张 强，那么 P(f(c)) 便是表示“张强的父亲是教授” 这一命题。
客体——是指可以独立存在的，它可以是具体
的事物，也可以是抽象的概念。
如：李明，计算机，玫瑰花，自然数，思想，定 理等。

人工智能
命题逻辑归结方法
吉林大学珠海学院计算机科学与技术系
为叙述方便， 我们把命题原子称作正文字， 例如P, Q, R„., 等等， 把带有非符号的命题原子叫做 负文字，例如P, Q, R„., 等等，把正文字 和负文字统称为文字。 单个文字， 文字的析取构成的命题逻辑公式叫做子 句。 例如， P, Q, P ∨Q ∨R都是子句。
人工智能
命题逻辑归结方法
吉林大学珠海学院计算机科学与技术系
例：证明 (P → Q) →(～ Q → ～ P)} 前提集合F={(P → Q) }, 结论= (～ Q → ～ P)。 F中命题公式转换成的子句集是{～ P∨Q} ～g 转换成的子句集是{～Q, P } 把上述子句集组合在一起，得到初始子句集 Φ ={～ P∨Q, ～Q, P }
结论（conclusion）, 后项（ consequent） 命题语句的例 P, Q, R, ┓P, ┓Q, P∧Q, P∧Q→R, ┓P∨┓Q, ┓P∨┓Q ∨R (P∧Q)→R ┓P∨┓Q ∨R
人工智能
吉林大学珠海学院计算机科学与技术系
命题语句就是一个符号串， 只有对串中的命题符号指定 了真假值之后， 这个语句才具有实际意义。 命题演算的语义 由单个逻辑运算符连接的简单语句的语义 定义：命题语句的语义 对每一个命题指定其真假值。 按由单个逻辑运算符连接的简单语句的语义递归地
F
T T
F
T T
F
T T
人工智能
P T T F Q T F T ┓P F F T
吉林大学珠海学院计算机科学与技术系
┓ PVQ T F T
P→Q T F T
(┓ PVQ) P→Q T T T
F
F

3. 4.
利用量词作用域的扩张和收缩等价式， 利用量词作用域的扩张和收缩等价式，把量 词提到前面。 词提到前面。
前束合取范式
定义2-6.2 前束合取范式： 前束合取范式： 定义 一个wff A如果具有如下形式，则称为前束 如果具有如下形式， 一个 如果具有如下形式 合取范式： 合取范式： (Q1x1)(Q2x2)…(Qnxn)[(A11∨A12∨…∨ 1k1)∧ ∨…∨A ∧ (A21∨A22∨…∨ 2k2)∧…∧(Am1∨Am2∨…∨ mkm)] ∨…∨A ∧ ∨…∨A 其中Q 为客体变元， 其中 i (1≤i≤n）为∃或∀，xi为客体变元， ） Aij是原子变元或其否定。 是原子变元或其否定。
前束合取范式
定理2 每一个wff 定理2-6.2 ：每一个wff A都可转化为与其等价 的前束合取范式。 的前束合取范式。 转化方法： 转化方法： 取消多余量词。 1. 取消多余量词。 2. 换名 消去条件联结词。 3. 消去条件联结词。 利用量词转化公式， 否定深入到命题变元和 4. 利用量词转化公式 ， 把 否定深入 到命题变元和 谓词填式的前面。 谓词填式的前面。 5. 利用量词作用域的扩张和收缩等价式， 把量词 利用量词作用域的扩张和收缩等价式 ， 提到前面。 提到前面。
(2)全称推广规则（universal generalization）
全称量词引入规则，简称 规则。 全称量词引入规则，简称UG规则。 规则 P(x)⇒ (∀x)P(x) ⇒ ∀ 如果能够证明对论域中每一个客体c， 如果能够证明对论域中每一个客体 ， 命 都成立， 题 P(c)都成立 ， 则全称推广规则可得到结论 都成立 (∀x)P(x)成立。在应用本规则时，必须能够证 成立。 ∀ 成立 在应用本规则时， 明前提P(x)对论域中每一可能的 是真。 对论域中每一可能的x是真 明前提 对论域中每一可能的 是真。

(2) ∀x∀y(x+0=y →y+0=x) 真命题 (3) ∀x∀y∃z(x+y=z) 真命题 (4) ∀x∀y(x+y=x*y) 假命题 (5)x+y=y+z,它的真值不确定,因而不是命题. 注)非闭式,在有的解释中不是命题.
定义:设A为一公式(谓词公式),如果A在任何解释下都是 真的,则称A为逻辑有效式(永真式);如果A在任何解释下 都是假的,则称A是矛盾式(永假式);若至少存在一个解 释使A为真,则称A是可满足式. 2.代换实例 设A0是含命题变项p1,p2,…,pn的命题公式,A1,A2,…,An 是n个谓词公式,用Ai(1≤i≤n)处处代换pi,所得公式A 称为A0的代换实例. 例如:F(x)→G(x),∀xF(x)→∃xG(x)等都是p→q的代换实例; 命题公式中的重言式的代换实例在谓词公式中可仍称为重言式 ,这样的重言式都是逻辑有效式. 命题公式中的矛盾式的代换实例仍为矛盾式.
例2.7 给定解释I如下: 1)DI={2,3} 2)DI中特定元素a=2 3)函数f(x)为f(2)=3,f(3)=2 4)谓词F(x)为F(2)=0,F(3)=1 G(x,y)为G(i,j)=1,i,j=2,3 L(x,y)为L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0 在解释I下,求下列各式的真值 (1) ∀ ∀x(F(x)∧G(x,a)) (2)∃x(F(f(x))∧G(x,f(x))) ∃ (3)∀x∃yL(x,y) ∀ ∃
例2.2 在一阶逻辑中将下面命题符号化 (1)凡有理数均可表成分数; (2)有的有理数是整数; 要求:1)个体域为有理数集合, 2)个体域为实数集合, 3)个体域为全总个体域. 解: 1)个体域为有理数集合(不用引入特性谓词): (1) 设 F(x):x可表成分数; 则命题符号化为∀xF(x). ∀ (2) 设 G(x):x是整数;则命题符号化为∃xG(x). 2)个体域为实数集合(引入特性谓词):令 R(x):x是有理数; (1) 设F(x):x可表成分数;则命题符号化为∀x(R(x)→F(x)) (2) 设G(x):x是整数;则命题符号化为∃x(R(x)∧G(x))。

第2章 谓词逻辑
存在量词：“ ” 称为存在量词，用来表达 “某个”、 “存在一些”、“至少有一个”、“对于一些” 等词。 例4：采用存在量词翻译下列命题 1) 至少有一台微机是坏的 设 A(x): x是微机 B(x): x是坏的 (x) ( A(x) B(x) ) 2) 有些人没有来上课 设 M(x): x是人 C(x): x没来上课 (x)( M(x) C(x) ) 3) 存在小于3的自然数 设 N(x): x是自然数 L(x): x小于3 (x)( N(x) L(x) )
第2章 谓词逻辑
客体
a:张三
谓词 S(x):x是个大学生

S(a)
张三是个大学生
客体常元：表示确定的客体，以a，b，c…或带下 标的ai，bi，ci…表示。 客体变元：表示不确定的客体，以x，y，z…或xi， yi，zi…表示。 谓词常元：表示确定谓词。如S(x):x是个大学生 谓词变元：表示不确定的谓词。如S,R。
第2章 谓词逻辑
约定： 最外层括号可以省略；量词后面如果有括号，
则不能够省略。 例如： (x)(P(x) Q(x)) (x) P(x) Q(x) 2. 谓词公式的翻译 例1：并非名人的话都是名言 解：设 R(x): x是名人的话 F(x): x是名言
¬ (x)( R(x) F(x) )
解：设 M(x): x是人 P(x): x聪明 (x)( M(x) P(x) ) ¬ ((x)( M(x) P(x))) 例4：如果有限个数的乘积为零，那么至少有一个因子为零 解：设 A(x): x是有限个数的乘积 B(x): x为零 C(x): x是乘积中的一个因子 (x)( A(x) B(x) ) (y)( C(y) B(y))
2、如果没有给出个体域，都应该统一为全总个体域。

第二章 谓词逻辑
2.1 谓词的概念与表示
苏格拉底三段论：
所有人都是要死的，苏格拉底是人，所以苏格拉底 是要死的。
用P,Q,R分别表示以上三个命题。 则得到推理的形式结构为：
(P∧Q)→R
第二章 谓词逻辑
2.1 谓词的概念与表示
谓词逻辑命题符号化的三个基本要素：客体词、 谓词、量词。 反映判断的句子由主语和谓语组成。
第二章 谓词逻辑
2.2 命题函数与量词
每个由量词确定的表达式都与个体域有关。为了方便，
将所有命题函数的个体域全部统一，使用全总个体域，之
后，对每一个客体变元的变化范围，用特性谓词加以限制。 特性谓词：从全总个体域中分离出一个集合，定义的
谓词。
对全称量词，特性谓词常作蕴含的前件，对存在量 词，特性谓词常作合取项。
则: (1) x (M(x) → F(x));
(2) x (M(x)∧ G(x)).
第二章 谓词逻辑
由上面例子可见：
（1）在不同个体域中，同一个命题的符号化形式可能不同。 一般地，对全称量词，特性谓词应作为蕴含式的前件。
一般地，对存在量词，特性谓词应作为合取式的一项。 （2）同一个命题，在不同个体域中的真值也可能不同。
组成的表达式为复合命题函数。
逻辑联结词组、∧、∨、—>、<—>的意义与 命题演算中的解释完全类同。
第二章 谓词逻辑
2.2 命题函数与量词
有了个体词和谓词的概念之后，有些命题还是不能准确地符号化 。 以前面所讨论的三段论为例： 令：P(x)：x是偶数。 S(x) ： x能被2整除。 a：6。
符号化为： (1)P(x)→S(x) (2)P(a) (3)S(a) 我们知道，“凡偶数都能被2整除。”是一个真命题， 而“P(x)→S(x)”是一个一元函数，不是一个命题。原因是 “P(x)→S(x)”没有把命题(1) 中“凡”的意思表示出来。 即缺少表示个体常项或变项的数量关系的词。所以还要引入量 词的概念。

-吴扬扬8
§2.5 推理理论(4)
例3: 下列推导结论是错误的： (1) ∀x∃yP(x,y) (2) (3) (4) (5) ∃yP(z,y) P(z,d) ∀xP(x,d) ∃y∀xP(x,y) 前提 (1)US (2)ES (3)UG (4)EG
所以， ∀x∃yP(x,y)⇒ ∃y∀xP(x,y) 设：个体域实数集，P(x,y): x+y=1 则 ∀x∃yP(x,y)为T，而∃y∀xP(x,y)为F。 错在哪里？为什么？
»
(4) D(a) (1)(3)假言推论 例2: 证明 ∀x(P(x)∨Q(x))⇒∃x¬P(x)→∃xQ(x). ∃x ¬P(x) 附加前提 证明: (1) (2) ¬P(c) (1)ES (3) ∀x(P(x)∨Q(x)) 前提 (4) P(c)∨Q(c) (3)US (5) Q(c) (2)(4)析取三段论 (6) ∃xQ(x) (5)EG (7) ∃x¬P(x)→∃xQ(x) CP
-吴扬扬4
不是等价变换
§2.4 范式(4)
定理2.4.1: 设A为合式公式,那么A是永假式 iff A的Skolem 范式是永假式。 引理2.4.1: 设C为∀x1,…,∀xt∃yB(x1,…,xt,y), C’为∀x1,…,∀xtB(x1,…,xt,f(x1,…,xt)),那么 C是永假式 iff C’是永假式。 证明：必要性 若C是永假式，但C’不是永假式， 则有解释I，使C’在I下为1， 即∀a1,…,at∈DI,有B(a1,…,at,f(a1,…,at))为1, ∵ f(a1,…,at)∈DI， ∴ ∀a1,…,at∈DI,有a=f(a1,…,at)，使B(a1,…,at,a)为1, 与C是永假式矛盾。 充分性证明见pp.48 -吴扬扬5
-吴扬扬-

2.5谓词逻辑的推理理论
【例2.21】证明 (x)(A(x)∨B(x))，(x)¬ A(x)(x)B(x) 证明：用直接法证明。 ⑴ (x)(A(x)∨B(x)) P ⑵ A(s)∨B(s) US⑴ ⑶ (x)¬ A(x) P ⑷¬ A(s) US⑶ ⑸ B(s) T⑵⑷析取三段论 ⑹ (x)B(x) EG⑸
2.4前束范式
定理2.4.2 每个谓词公式都可化为与其等价的前束合取范式。 【例2.18】将((x)F(x)∨(x)G(x))→(x)(F(x)∨G(x))化为与 其等价的前束合取范式。 解： ((x)F(x)∨(x)G(x))→(x)(F(x)∨G(x)) (x)(F(x)∨G(x))→(y)(F(y)∨G(y)) (x)(y)((F(x)∨G(x))→(F(y)∨G(y))) (x)(y)(¬ (F(x)∨G(x))∨(F(y)∨G(y))) (x)(y)((¬ F(x)∧¬ G(x))∨(F(y)∨G(y))) (x)(y)((¬ F(x)∨F(y)∨G(y))∧(¬ G(x)∨F(y)∨G(y)))
2.5谓词逻辑的推理理论
【例2.23】设个体域为全总个体域。证明推理：学术会的成 员都是工人并且是专家。有些成员是青年人。所以有的成员 是青年专家。 首先将命题符号化： F(x)：x是学术会成员。 G(x)：x是专家。 H(x)：x是工人。 R(x)：x是青年人。 本题要证明：(x)(F(x)→G(x)∧H(x)), (x)(F(x)∧R(x)) (x)(F(x)∧R(x)∧G(x))
例如： (x)(y)(F(x)∨G(y)→L(x,y)) (y)(x)(z)(¬ H(x,y)∧F(x)→L(x,z)) 都是前束范式。 (x)F(x)∨(y)(G(y)→L(x,y)) (y)(x)(¬ H(x,y)∧F(x))→(z)L(x,z) 不是前束范式。

4
第三章：基于归结原理的推理证明
主要内容：谓词公式与子句集的概念,斯柯林(Sko
lem)标准范式及其求取过程,海伯伦（Herbrand） 理论的H域及其解释,置换与合一,命题和谓词归结 原理,归结过程的控制策略。
教学要求：深刻理解和掌握归结原理的基本概念
和基本归结过程。
重点：归结原理的基本概念和基本归结方法 难点：归结原理的实现方法 。 实践活动：归结原理的程序实现
离散数学讲义之
数理逻辑
主讲:邱晓红
数理逻辑简介
• 数理逻辑是用数学方法研究形式逻辑的科学。 数学方法即符号方法，故数理逻辑又称符号 逻辑。包含命题逻辑、谓词逻辑、证明论、 模型论、递归函数、公理化集合论、归纳逻 辑、模态逻辑、多值逻辑和时态逻辑等内容， 与计算机有密切关系。
2
各知识点关联图
命题逻辑 简单命题 命题 复合命题 对偶式 命题公式 真值表 主合取范式 主析取范式 合取范式 析取范式 蕴含式 前提引入 P 规则 置换等 T 规则 推理规则 推理系统 置换 归结原理 自动推理 合一 量词引入规则 量词消去规则
9
（5）把全称量词全部移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整 个部分。 （6）母式化为合取范式：任何母式都可以写成由一些谓词公式和谓词公式否定的析取的 有限集组成的合取。 需要指出的是，由于在化解过程中，消去存在量词时作了一些替换，一般情况下，公式 G 的 Skolem 标准型与 G 并不等值。
(x1 )(x2 )...(xn )M ( x1, x2 ,...,xn )
其中，M(x1,x2,…,xn)是一个合取范式，称为 Skolem 标准型的母式。
8
将谓词公式 G 化为 Skolem 标准型的步骤如下： （1）消去谓词公式 G 中的蕴涵（→）和双条件符号（） ，以A∨B 代替 A→B，以(A∧ B)∨(A∧B)替换 AB。 （2）减少否定符号（）的辖域，使否定符号“”最多只作用到一个谓词上。 （3）重新命名变元名，使所有的变元的名字均不同，并且自由变元及约束变元亦不同。 （4）消去存在量词。这里分两种情况，一种情况是存在量词不出现在全称量词的辖域内，此 时，只要用一个新的个体常量替换该存在量词约束的变元，就可以消去存在量词；另一种情况 是，存在量词位于一个或多个全称量词的辖域内，这时需要用一个 Skolem 函数替换存在量词 而将其消去。