x x
第4章
逻辑的知识表示和推理
2. 量词
首先来考察两个谓词 P（x）： x2 - 1＝（x + 1）（x – 1） Q（x）： x + 3＝１ 对于ｘ＝-２时为T。
• 1． 全称量词
通常把“所有”、“一切”、“任一”、“全体”、 ( x) x “凡是”等词统称为全称量词，记为x) p(；符号 “ ”表示对于个体域中所有的个体 x，p(x) 谓词均为T。
• • • •
4．OWNS(heming,book-1)→COLOR(book-1,blue); 5．GRASP(i，you) GRASP(you，i) ； 6． (x)[ROBOT( x) COLOR(x, gray )〕; 7. ( x )INROOM(x，room-1)
第4章
逻辑的知识表示和推理
例如 (x)(y)(z )( A( x, y) B( x, y, z) C ( x, z))就是一个 前束范式。 • ⑵ Skolem范式 在前束范式中，如果所有的存在量词都出现在全称量 词之前，则称这种形式的范式表达式为Skolem范式。 例如 (x)(y)(z)( A( x, y) B( x, y, z) C ( x, z))
第4章
逻辑的知识表示和推理
7. 利用命题定律证明等价式 逻辑推理的步骤： •⑴ 利用联结词化规律化掉 →、 ； • ⑵ 利用狄· 摩根定律将～深入到 变元； • ⑶ 利用分配律进行变换。
第4章
逻辑的知识表示和推理
8. 示例
• 例4-1 试证明： • （P∧（P→Q））∨Q （P∧Q）∨（～P∧Q） • 例4-2 证明等价式：（P→Q） ∧（R→Q） （P∨R）→Q
3. 谓词逻辑的一般表示方法
• 例4-4 用谓词逻辑表示“所有的整数不是 偶数就是奇数”。 • 定义谓词: INTEGER(x):表示x是整数； EVEN(x):表示x是偶数； ODD(x):表示是奇数。 • 该知识表示为: ( )(INTEGER(x)→EVEN(x)∨ODD(x)) x
第4章
第4章
逻辑的知识表示和推理
3. 含有量词的等价式
• ⑷ 其他等价式 ① (x) A( x) B (x)( A( x) B) ② (x) A( x) B (x)( A( x) B) ③ A (x)B( x) (x)( A B( x)) ④ A (x)B( x) (x)( A B( x)) ⑤ (x)( A( x) B( x)) (x) A( x) (x)B( x) • ⑸ 量词消去规则 ① (x) A( x) A( y) (c为常量) ② (x) A( x) A(c)
第4章
逻辑的知识表示和推理
4. 量词之间的关系
• 对于二元谓词P(x,y)，存在以下量化的可能：
(x)(y) P( x, y) (x)(y) P( x, y)
(x)(y) P( x, y) (x)(y) P( x, y)
(y)(x) P( x, y) (y)(x) P( x, y)
逻辑的知识表示和推理
2. 联结词和量词的应用
• 1、～INROOM（robot，room2）； • 2．LIKE（i，music）∧LIKE（i，painting）； LIVE(lisi,house1)∧COLOR(house1,yellow)；
• 3．PLAY(lihao,basketball)∨PLAY(lihao,football)；
第4章
逻辑的知识表示和推理
4. 真值表
P F F Q F T ～P T T P∧Q F F P∨Q F T P→Q T T P T F Q
T
T
F
TFFF源自TTTF
T
F
T
第4章
逻辑的知识表示和推理
5. 常用的等价命题定律
• ⑴ 双重否定律 ～～P P • ⑵ 交换律 ① P∧Q Q∧P ② P∨Q Q∨P • ⑶ 结合律 ①（P∧Q）∧R ②（P∨Q）∨R
• 2．存在量词
(x)Q( x 通 常把 “存 在 ”、 “ 有些 ” 、“ 至 少有 一)个 ” 、 x “有的”等词统称为存在量词，记为 ；符号 “ ”表示对于个体域中存在某些个体x，Q(x)
第4章
逻辑的知识表示和推理
3. 量词的集合表示
• 设个体域x是有限集合S： S = { a1，a2，…，an} • 由量词的意义可知 (x)A(x) 1)∧A(a2)∧…∧A(an) A(a (x) A( x) 1)∨A(a2)∨…∨A(an) A(a
第4章
逻辑的知识表示和推理
4. 定理证明
～(A(a1)∧A(a2)∧…∧A(an)) ~ (x) A( x) ～A(a 1)∨～A(a2) ∨～A(an) ( x)[~ A( x)]
(x)( A( x) B( x)) (A(a1)∧B(a1))∧ (A(a2)
• • ∧B(a2)) ∧…∧(A(an)∧B(an)) (A(a 1)∧A(a2)∧…∧A(an)) ∧(B(a1)∧B(a2)∧…∧B(an))
第4章
逻辑的知识表示和推理
1．2 谓词逻辑
•
1. 谓词和个体
个体是指可以独立存在的事物，如花（桃花， 玫瑰，犁花）、计算机、智能等等。谓词是用来刻 划个体的性质或关系的。例如张三和李四是工人。 通常用大写英文字母表示谓词，用小写英文字 母 表 示 个 体 。 如 果 x 的 集 合 为 a1，a2，…，an， 则 STUDENT（an）为真（T）。 与一个个体相联的谓词叫一元谓词，与多个个 体相联的谓词叫多元谓词。一个n元的谓词常可表 示为P（x1，x2，…，xn），一般来说，在多元谓词 中，个体间的次序不可随意交换。
第4章
逻辑的知识表示和推理
第4章
逻辑的知识表示和推理
敖志刚 编制
第4章
逻辑的知识表示和推理
第4章 逻辑的知识表示和推理
• 4．1 命题与逻辑 • 4．1．1 命题与命题定律 • 4．1．2 谓词逻辑 • 4．2 谓词逻辑知识表示 • 4．2．1 谓词逻辑知识表示方法 • 4．2．2 谓词逻辑表示的优缺点 • 4．3 逻辑推理的技术与算法 • 4．3．1 子句集及其化简 • 4．3．2 置换与合一 • 4．3．3 鲁滨逊消解(归结)原理
第4章
逻辑的知识表示和推理
5. 常用的等价命题定律
• ⑹ 吸收律 ① P∧（P∨Q） P ② P∨（P∧Q） P • ⑺ 联结词化规律 ① P→Q ～P∨Q ② P Q （P→Q）∧（Q→P） ③ P Q （P∧Q）∨（～P∧～Q） • ⑻ 变换等价式 P （P∧Q）∨（P∧～Q）
第4章
逻辑的知识表示和推理
6. 永真蕴含式
常用的永真蕴含式如下： • (1) 化简式 P∧Q ⇒ P， P∧Q ⇒ Q • (2) 附加式 P ⇒ P∨Q， Q ⇒ P∨Q • (3) 析取三段论 ﹁ P, P∨Q ⇒ Q • (4) 假言推理 P, P→Q ⇒ Q • (5) 拒取式 ¬ P→Q ⇒ P Q, • (6) 假言三段论 P→Q, Q→R ⇒P→R • (7) 二难推理 P∨Q, P→R, Q→R ⇒ R • (8) 全称固化 (∀x)P(x) ⇒ P(y) 其中，y是个体域中任一个体，依此可消去谓词公式中的全称量词 • (9) 存在固化 (∃x)P(x) ⇒ P(y) 其中，y是个体域中某一个可以使P(y)为真的个体，依此可消去谓 词公式中的存在量词。
P∧（Q∧R） P∨（Q∨R）
第4章
逻辑的知识表示和推理
5. 常用的等价命题定律
• ⑷ 分配律 ① P∧（Q∨R） （P∧Q）∨（P∧R） ② P∨（Q∧R） （P∨Q）∧（P∨R） ③ P→（Q→R） （P→Q）→（P→R） • ⑸ 狄· 摩根定律 ① ～（P∧Q） ～P∨～Q ② ～（P∨Q） ～P∧～Q
逻辑的知识表示和推理
3. 谓词逻辑的一般表示方法
• 例4-5 用谓词逻辑表示如下知识: “王宏是计算机 系的一名学生”；“李明是王宏的同班同学”； “凡是计算机系的学生都喜欢编程序”。 • ① 首先定义谓词: COMPUTER(x):表示x是计算机系的学生； CLASSMATE(x，y):表示x是y的同班同学； LIKE(x，y):表示x喜欢y。 • ② 用谓词公式表示上述知识: COMPUTER(wanghong)； CLASSMATE(liming，wanghong)； ( x )(COMPUTER(x)→LIKE(x，programing))。
第4章
逻辑的知识表示和推理
3. 含有量词的等价式
• ⑶ 量词辖域扩张及收缩律 ① (x) A( x) P (x)( A( x) P) ② (x) A( x) P (x)( A( x) P) ③ (x) A( x) P (x)( A( x) P) ④ (x) A( x) P (x)(A( x) P)
(y)(x) P( x, y) (y)(x) P( x, y)
• 一般来讲，量词的先后次序不可交换。例如，x和 y的个体域都是所有鞋子的集合，P(x,y)表示一只 鞋子x可与另一只鞋子y配对，(x)(y) P( x,则表示 y) “存在一只鞋子x，它可以与任何一只鞋子y配 对”,这是不可能的，是个假命题。而 x) P( x, y) (y)( 表示“对任何一只鞋子y，总存在一些鞋子x可以 与它配对”，这是真命题。
第4章
逻辑的知识表示和推理
4．1 命题与逻辑
• • • • • • • • • • • 4.1.1 命题与命题定律 1.概念 命题、真命题、假命题、原子命题、不是命题。 命题的表示——大写A、B、C ┈┈ P、Q、R。 2. 联结词（Connectives） ① 否定或补的联结词用“～”表示 ② 合取用“∧”表示， ③ 析取用“∨”表示， ④ 单条件联结词用“→” ⑤ 双条件联结词“ ” 联结词运算的先后次序为～、∧、∨、→、 ，同级联结 词先出现先运算