第七讲 谓词逻辑的性质及前束范式
- 格式：doc
- 大小：24.50 KB
- 文档页数：2
下载文档原格式
合集下载
3.2前束范式谓词推理
存在指定规则ES，或称为存在量词消去规则
xP (x) P ( c)
C是论域中的某些客体，必须注 意，其指定的客体C不是任意的。
2/4/2019
discrete math
存在推广规则EG existential generalization L o g i c 一阶逻辑
存在推广规则EG，存在量词产生规则
2/4/2019
discrete math
前束合取范式
Logic 一阶逻辑
定义：一个谓词公式 A如果具有如下形式， 则称为前束合取范式： (Q1x1)(Q2x2)…(Qnxn)[(A11A12A1k1)( A21A22A2k2)(Am1Am2Amkm)] 其中Qi (1≤i≤n）为或，xi为客体变元，
P (c) x P (x )
这里C是论域中的一个客体，
对于某些客体C成立。
2/4/2019 discrete math
Logic 一阶逻辑
Rules of Inference for Quantified Statements. Rule of Inference Name
∀xP(x) ∴P(c)
xy(z(┐P(x,z)∨┐P(y,z))∨z Q(x,y,z))
xy (z(┐P(x,z)∨┐P(y,z))∨u Q(x,y,u)) xy zu (┐P(x,z)∨┐P(y,z)∨Q(x,y,u)) （或xy zu (P(x,z)∧P(y,z)→Q(x,y,u))）
2/4/2019
discrete math
前束范式例子
Logic 一阶逻辑
前束范式的特点是，所有量词均非否定地 出现在公式最前面，且它的辖域一直延伸 到公式之末。 例如，xyz((P(x,y)Q(y,z)) R(x,y)) 是前束范式。 而xP(x)yQ(y)，x(P(x)yQ(x,y)) 不是前束范式。
第七章谓词逻辑
整个公式中，
是自由出现。
z
约束出现，
x
既有约束出现又有自由出现，
y
33
变元的约束讨论
❖ 从约束变元的概念可以看出，P(x1,x2, … ,xn)是n元谓词， 它有n个相互独立的自由变元。
❖ 若对其中k个变元进行约束，则P成为n-k元谓词。
❖ 当k = n，即谓词公式中没有自由变元出现时，则该公式就 成为一个命题。
请将下列命题符号化： (1) 某些实数是有理数。 (2) 没有不犯错误的人。 (3) 尽管有人聪明，但未必一切人都聪明。
解：(1) R(x)：x是实数。Q(x)：x是有理数。 (x)(R(x)Q(x) )
(2) M(x)：x是人。F(x)：x犯错误。 (x)(M(x)F(x))
(3) M(x)：x是人。S(x)：x聪明。 (x)(M(x)S(x)) (x)(M(x)S(x))
某种性质或具有某种关系，需要引入量词。 例如： (1) 某些人会跳舞； (2) 所有人都会跳舞；
14
量词
❖ [定义]量词 表示数量的词
1.全称量词: 表示任意的,所有的,每一个，凡是 x 表示对个体域中所有的x……
2.存在量词: 表示存在, 有的, 至少有一个，有些 x 表示在个体域中存在x……
❖ 在∀x A(x)和∃x A(x)中： ❖ 紧跟量词的x称为量词的指导变元或作用变元 ❖ A称为量词的辖域或作用域
回答：(1)(2)是谓词合式。
30
谓词逻辑
❖7.1.1 谓词与命题函数
▪ 1. 谓词 ▪ 2. 命题函数
❖7.1.2 量词
▪ 1. 全称量词 ▪ 2. 存在量词
❖7.1.3 谓词合式
❖7.1.4 约束元与自由元
谓词公式化与转换逻辑学教案
谓词公式化与转换逻辑学教案引言：转换逻辑学是一门重要的逻辑学分支，研究命题逻辑中真值保持的转换关系。
而谓词公式化是转换逻辑学中的一个关键概念，指的是将非标准的谓词逻辑公式转换为标准的形式。
本教案旨在介绍谓词公式化的概念、原理及其在转换逻辑学中的应用。
第一节：谓词逻辑与转换逻辑学概述1.1 谓词逻辑的基本概念谓词逻辑是研究谓词、量词和变量等逻辑概念的分支学科。
它通过谓词公式来描述和分析命题，具有更强的表达能力和逻辑推理能力。
1.2 转换逻辑学的重要性转换逻辑学是研究逻辑推理中的转换关系，旨在深入理解从一个命题到另一个命题的逻辑转换过程。
它对于逻辑演绎和证明的有效性具有重要的理论和实际价值。
第二节：谓词公式化的基本原理2.1 谓词变量的引入为了描述复杂的命题逻辑，引入谓词变量是必要的。
谓词变量代表具有未知值的谓词，通过它可以描述包含任意个体的命题。
2.2 谓词公式的基本形式根据谓词逻辑的基本概念，谓词公式由谓词、变量和量词组成。
常用的量词有全称量词和存在量词，它们分别表示对于全部和存在个体都成立的命题。
第三节：谓词公式化的实例应用3.1 公式合一公式合一是指将两个谓词公式中的变量统一赋值，使得它们相互对应的谓词成立。
这在转换逻辑学中广泛应用于等价关系的证明和逻辑推理。
3.2 全称量化和存在量化的转换转换逻辑学中，全称量化和存在量化之间存在特定的转换关系。
谓词公式化提供了一种途径，将各类量词形式转化为标准的形式，从而进一步推导出转换关系。
第四节：谓词公式化与转换逻辑学的进一步研究4.1 前束范式和后束范式前束范式（Prenex Normal Form）和后束范式（Skolem Normal Form）是谓词公式化中的两种标准形式，它们在转换逻辑学的研究中发挥着重要的作用。
4.2 谓词公式合一算法的改进公式合一算法是转换逻辑学中的核心算法之一，研究者们不断优化和改进算法，以提高逻辑推理的速度和准确性。
结论：谓词公式化是转换逻辑学中的重要概念，它能够将非标准的谓词逻辑公式转换为标准的形式，进而深入探索逻辑推理的转换关系。
1.7谓词演算的永真公式
P(x)：x今天没来校上课。
1 xP(x)：不是所有的大学生今天都来上课。
与 xP(x)：存在一些大学生今天没来上课。（含义相同）
2 xP(x)：今天没有(不存在)来上课的大学生。
与 xP(x)：所有的大学生今天都没来上课。（含义相同）
10
NUIST
3．量词辖域的扩张与收缩律
设P是不含自由变元x的任一谓词公式(包括命题公式)，
3
谓词公式类型的判断
NUIST
方法一：真值表法 ——当谓词公式A的个体域E是有限的，谓词变元的解释也
是有限的时，原则上可以用真值表来判断。
方法二：指派分析法 ——当谓词公式A的个体域E是无限的，或谓词变元的解释
是无限的时，谓词公式A的指派就是无限多个，无法实 现用真值表来判断，一般根据联结词、量词的意义，直 接用自然语言来叙述进行证明。
命题演算的等价式就转化为谓词演算的等价式。 依据：永真式的任何代入实例也必永真。 例如：1 由 P P
得： A(x) A(x) 2 由 P→Q P∨Q
得：xA(x)→xB(x) (xA(x))∨(xB(x))
二、由于引入量词而产生的谓词演算中特有的逻辑等价式、 永真蕴含式。
8
与量词有关的逻辑等价式
NUIST
1．量词的消去律
(1)设个体域为有限集D={a1, a2, …,an}时，则有
∀x P(x)
P(a1)∧P(a2)∧…∧P(an) （1）
∃x P(x)
P(a1) ∨P(a2) ∨…∨P(an) （2）
(2) 设A是不含自由变元x的谓词公式，则有
xA A
（3）
xA A
（4）
(因为A的真值与自由变元x无关)
7谓词逻辑
蕴含表达式量词转化律量词辖域扩张蕴含表达式蕴含表达式量词辖域扩张蕴含表达式蕴含表达式量词辖域扩张蕴含表达式只要给出一种解释上式不成立即可如可用1个体域d为自然数集合n是奇数是偶数
第七章 谓词逻辑
在命题逻辑中,主要研究命题和命题演算,其基本组 成单位是原子命题,并视为不可再分解. 命题逻辑中的推理有很大的局限性. 例如:著名的苏格拉底三段论: 所有的人都是要死的; 苏格拉底是人; 所以苏格拉底是要死的.
在命题逻辑中的符号化:
用P、Q、R分别表示以上三个命题,
则可用
P Q R表示这一推理过程.
谓词逻辑的任务: 对原子命题作进一步的分析,研究其内部的逻辑结构,并 在此基础上更深入地刻画推理.
第七章
§7.1 谓词与量词
谓词逻辑
§7.2 谓词公式与变元约束 §7.3 谓词演算的等价式与永真蕴含式
左到右的顺序读出.
习题:P178
1、2
§7.2 谓词公式与变元约束
引入命题演算合式公式:为了使命题的符号化更准确 和规范,以及正确进行谓词演算和推理. 定义7.2.1 设 R( x1 , x2 ,, xn ) 是n元谓词,其中 x1 , x2 ,, xn 是个体变元,则 R( x1 , x2 ,, xn ) 称为谓词演算的原子公式. 定义7.2.2 谓词演算的合式公式定义如下:
0 元谓词:不含个体变元的谓词,如:原子命题
谓词 P ( x1 , x2 ,, xn ) 不是命题,真值无法确定,只有当以
n个个体常元代替变元后,才有确定的真值,从而成为命 题.
注:命题逻辑中的联结词在谓词逻辑中仍然可用且含
义不变.
二、量词: 谓词逻辑中表示数量的词.
例:所有的人都是要死的,有些人是要死的 两个命题中的个体词和谓词均相同,区别在于“所有 的”和“有些”两个量词. 量词可分为:全称量词和存在量词 全称量词:对应自然语言中的“一切”、“所有的” 、 “任意的”等,表示对个体域中的所有个体,用符号“ ” 表示.
第七章 谓词逻辑
在命题逻辑中,主要研究命题和命题演算,其基本组 成单位是原子命题,并视为不可再分解. 命题逻辑中的推理有很大的局限性. 例如:著名的苏格拉底三段论: 所有的人都是要死的; 苏格拉底是人; 所以苏格拉底是要死的.
在命题逻辑中的符号化:
用P、Q、R分别表示以上三个命题,
则可用
P Q R表示这一推理过程.
谓词逻辑的任务: 对原子命题作进一步的分析,研究其内部的逻辑结构,并 在此基础上更深入地刻画推理.
第七章
§7.1 谓词与量词
谓词逻辑
§7.2 谓词公式与变元约束 §7.3 谓词演算的等价式与永真蕴含式
左到右的顺序读出.
习题:P178
1、2
§7.2 谓词公式与变元约束
引入命题演算合式公式:为了使命题的符号化更准确 和规范,以及正确进行谓词演算和推理. 定义7.2.1 设 R( x1 , x2 ,, xn ) 是n元谓词,其中 x1 , x2 ,, xn 是个体变元,则 R( x1 , x2 ,, xn ) 称为谓词演算的原子公式. 定义7.2.2 谓词演算的合式公式定义如下:
0 元谓词:不含个体变元的谓词,如:原子命题
谓词 P ( x1 , x2 ,, xn ) 不是命题,真值无法确定,只有当以
n个个体常元代替变元后,才有确定的真值,从而成为命 题.
注:命题逻辑中的联结词在谓词逻辑中仍然可用且含
义不变.
二、量词: 谓词逻辑中表示数量的词.
例:所有的人都是要死的,有些人是要死的 两个命题中的个体词和谓词均相同,区别在于“所有 的”和“有些”两个量词. 量词可分为:全称量词和存在量词 全称量词:对应自然语言中的“一切”、“所有的” 、 “任意的”等,表示对个体域中的所有个体,用符号“ ” 表示.
3.2前束范式谓词推理
1/11/2011
discrete math
前束合取范式
Logic 一阶逻辑
定义：一个谓词公式A如果具有如下形式 如果具有如下形式， 定义：一个谓词公式 如果具有如下形式， 则称为前束合取范式： 则称为前束合取范式： 前束合取范式 (Q1x1)(Q2x2)…(Qnxn)[(A11∨A12∨…∨ 1k1)∧( ∨…∨A ∧ A21∨A22∨…∨ 2k2)∧…∧(Am1∨Am2∨…∨ mkm)] ∨…∨A ∧ ∨…∨A 其中Q 为客体变元， 其中 i (1≤i≤n）为∃或∀，xi为客体变元， ） Aij是原子变元或其否定。 是原子变元或其否定。
1/11/2011 discrete math
谓词演算的推理理论
Logic 一阶逻辑
在谓词逻辑中，如果A 在谓词逻辑中，如果 1∧A2∧…∧An→B ∧ 是逻辑有效式，则称B是 是逻辑有效式，则称 是A1, 效结论， 效结论，记作 A1∧A2∧…∧An⇒B ∧ A⇒B 当且仅当 A→B是重言式 ⇒ → 是重言式 例如： 例如： ∀xF(x) ⇒∃xF(x) A2, …，An的有 ，
1/11/2011
discrete math
前束范式例子
Logic 一阶逻辑
(3) ∀x∀y (∃z(P(x,z)∧P(y,z))→∃z Q(x,y,z)) ∀ ∃ ∧ ∃ ⇔∀x∀y (┐∃z(P(x,z)∧P(y,z))∨∃z Q(x,y,z)) ⇔∀ ∀ ∃ ∧ ∨ ⇔∀x∀ ∀ ∨ ∨ ⇔∀ ∀y(∀z(┐P(x,z)∨┐P(y,z))∨∃z Q(x,y,z)) ⇔∀x∀y (∀z(┐P(x,z)∨┐P(y,z))∨∃u Q(x,y,u)) ⇔∀ ∀ ∀ ∨ ∨ ⇔∀x∀ ⇔∀ ∀y ∀z∃u (┐P(x,z)∨┐P(y,z)∨Q(x,y,u)) ∃ ∨ ∨ （或⇔∀x∀y ∀z∃u (P(x,z)∧P(y,z)→Q(x,y,u))） ⇔∀ ∀ ∃ ∧ ）
数理逻辑-谓词逻辑
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中公式用换名或代入规则
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中公式用换名或代入规则
谓词逻辑的等值和推理演算
• 例2:人皆有死,孔子是人,所以孔子有死.
(x)(Man(x)→Mortal(x)) Man(Confucius) → Mortal(Confucius)
• 例3:若有一种又高又胖旳人,则有一种高个子而 且有一种胖子.
(x)(Tall(x)Fat(x)) → (x)Tall(x) (x)Fat(x)
(x)P(x, f(x)) = P(1, f(1)) P(2, f(2)) • 两者明显不等值.但在(不)可满足旳意义下两者
是一致旳.
Lu Chaojun, SJTU
20
谓词逻辑旳推理
• 命题逻辑中有关推理形式、重言蕴涵以 及基本旳推理公式旳讨论和所用旳术语 都可引入到谓词逻辑中,并可把命题逻辑 旳推理作为谓词逻辑旳推理旳一种部分 来看待.
• 前束范式定理:任一公式都有与之等值旳 PNF.
Lu Chaojun, SJTU
11
怎样转化成PNF
1.消去和↔ 2.否定词内移
– 应用De Morgan律
3.约束变元易名(假如必要旳话) 4.量词左移
– 应用分配等值式
Lu Chaojun, SJTU
12
例:求PNF
((x)(y)P(a,x,y)(x)((y)Q(y,b)R(x))) = ((x)(y)P(a,x,y)(x)((y)Q(y,b)R(x))) = (x)(y)P(a,x,y) (x)((y)Q(y,b) R(x)) = (x)(y)P(a,x,y) (x)((y)Q(y,b) R(x)) = (x)((y)P(a,x,y) (y)Q(y,b) R(x)) = (x)((y)P(a,x,y) (z)Q(z,b) R(x)) = (x)(y)(z)(P(a,x,y) Q(z,b) R(x)) = (x)(z)(y)(P(a,x,y) Q(z,b) R(x)) = (x)(y)(z)(P(a,x,y)Q(z,b)R(x)(pp))
(x)(Man(x)→Mortal(x)) Man(Confucius) → Mortal(Confucius)
• 例3:若有一种又高又胖旳人,则有一种高个子而 且有一种胖子.
(x)(Tall(x)Fat(x)) → (x)Tall(x) (x)Fat(x)
(x)P(x, f(x)) = P(1, f(1)) P(2, f(2)) • 两者明显不等值.但在(不)可满足旳意义下两者
是一致旳.
Lu Chaojun, SJTU
20
谓词逻辑旳推理
• 命题逻辑中有关推理形式、重言蕴涵以 及基本旳推理公式旳讨论和所用旳术语 都可引入到谓词逻辑中,并可把命题逻辑 旳推理作为谓词逻辑旳推理旳一种部分 来看待.
• 前束范式定理:任一公式都有与之等值旳 PNF.
Lu Chaojun, SJTU
11
怎样转化成PNF
1.消去和↔ 2.否定词内移
– 应用De Morgan律
3.约束变元易名(假如必要旳话) 4.量词左移
– 应用分配等值式
Lu Chaojun, SJTU
12
例:求PNF
((x)(y)P(a,x,y)(x)((y)Q(y,b)R(x))) = ((x)(y)P(a,x,y)(x)((y)Q(y,b)R(x))) = (x)(y)P(a,x,y) (x)((y)Q(y,b) R(x)) = (x)(y)P(a,x,y) (x)((y)Q(y,b) R(x)) = (x)((y)P(a,x,y) (y)Q(y,b) R(x)) = (x)((y)P(a,x,y) (z)Q(z,b) R(x)) = (x)(y)(z)(P(a,x,y) Q(z,b) R(x)) = (x)(z)(y)(P(a,x,y) Q(z,b) R(x)) = (x)(y)(z)(P(a,x,y)Q(z,b)R(x)(pp))
[数学]02-谓词逻辑
规则内容：
A(c) (y)A(y) A(x) (y)A(y)
其中c为某指定个体常元 A(x)对y是自由的
规则成立条件：
y不在A(c) 或A(x)中出现 若A(x)为推导行的公式，x是由EI引入的，则不能用x 以外的个体变元作为约束变元
存在量词的产生规则 EG
例2.16 考察下面推论是否合乎规则？
A(x)对y是自由的
2020/11/14
为什么不把(x)P(x) 也都换y？
A(x) = (x)P(x) ∧ Q(x, y) 代入规则针对自由变元
A(x)对y是自由的。A(y)= (x)P(x) ∧ Q(y, y)
A(x) = (y)( P(y) ∧ Q(x, y) )
A(x)对y不是自由的。
此时可以将A(x)中的约束变元y进行改名： A(x) = (z)( P(z) ∧ Q(x, z) )，
引言
2020/11/14
➢ Lp是Ls的深化发展，因此Ls的推理理论在Lp中几乎可完全
照搬。
(x)A(x) A(y)
➢ 在Lp中，某些前提和结论可能受到量词的约束，为确立前
提和结论之间的内部联系，有必要削去量词和添加量词，
因此正确理解和运用有关量词规则是关键所在。
➢ 必要准备：A(x)对y是自由的。目的是：允许用y代入x后 得到A(y)，它不改变原来公式A(x)的约束关系
A(y) = (y)P(y) ∧ Q(y, y) 即(x)((y)P(y) ∧ Q(x, y)) (y)P(y) ∧ Q(y, y)
(x)A(x) A(y)；消去了量词(x)
全称量词的消去规则 UI/US
2020/11/14
(x)A(x) = (x)((y)P(x, y) ∧ Q(x, y)) 由于x出现在(y)的辖域内，因此需要对约束变元y改名 (x)A(x)经过改名得到：(x)((z)P(x, z)∧Q(x, y)) A(y) = (z)P(y, z) ∧ Q(y, y) 即(x)((y)P(y, z)∧Q(x, y))(z)P(y,z)∧Q(y, y)
命题逻辑与谓词逻辑
如 D2 = {1，2，3}
根据上面的分析，在D2上的解释应有29个。
下面是其中的一个解释：
I: P(1, 1) P(1, 2) P(1, 3) P(2, 1) P(2, 2) P(2, 3) P(3, 1) P(3, 2) P(3,3)
T
T
T
F
F
T
FF
F
由于x = 3时，不存在一个y使P(x, y) = T。所以在这个解释下公式B为假，
要考察在这个解释下公式A的真假，根据量词(x)要对所有x 进行考察。由于：对x = 0时，
P(x)→Q( f (x), a) = P(0)→Q( f (0), 0) = P(0)→Q(1, 0) = F→F = T
对x = 1时
P(x)→Q( f (x), a) = P(1)→Q( f (1), 0) = P(1)→Q(0,0) = T→T = T
定义2-5 永真蕴涵：命题公式A永真蕴 涵命题公式B，当且仅当A→B是一个永真 式，记作AB，读作“A永真蕴涵B”，简 称“A蕴涵B”。
2.2 谓 词 逻 辑
• 1．谓词与个体 原子命题被分解为谓词和个体两部分。
• 个体是指可以单独存在的事物，它可以是 一个抽象的概念，也可以是一个具体的东 西。
定理2-2是反证法的理论依据。
6．谓词公式中的等价和蕴涵式 定义2-13 设P与Q是两个谓词公式，D是它们
共同的个体域。若对D上的任何一个解释，P与Q 的真值都相同，则称公式P和Q在域D上是等价的。 如果在任何个体域上P和Q都等价，则称P和Q是 等价的，记做：P Q。
下面是一些常用的等价式：
• 交换律 P∨QQ∨P
（证毕）
定理2-2 G为B1, B2, …, Bn的逻辑结论，当且仅当 (B1 ∧ B2 ∧ … ∧ Bn) ∧ ～ G
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
第七讲
谓词逻辑的性质及前束范式
1.在命题逻辑中成立的基本等价式（详见第三讲）可以推广到谓词逻辑中：
例如：
幂等律在谓词逻辑中表述为：
∃x A（x）∧∃x A（x）⇔∃x A（x）
蕴涵律在谓词逻辑中表述为：
∀x（A（x）→B）⇔∀x（┓A（x）∨B）
2.量词和否定的交换：
%
┓∀x A（x）⇔∃x ┓A（x）
┓∃x A（x）⇔∀x ┓A（x）
3.量词辖域的扩张和收缩
【这里注意∀x（A（x）→B）和∀xA（x）→B 的区别：
比如A（x）: x遵纪守法B：社会和谐
∀xA（x）→B表述为：只要人人遵纪守法，社会就会和谐
∀x（A（x）→B）表述为：对于每一人，只要他遵纪守法，社会就会和谐】以下是等价公式：
（1）∀x（A（x）∨B）⇔∀xA（x）∨B
（2）∀x（A（x）∧B）⇔∀xA（x）∧B
@
（3）∃x（A（x）∨B）⇔∃xA（x）∨B
（4）∃x（A（x）∧B）⇔∃xA（x）∧B
（5）∀x（A（x）→B）⇔∃xA（x）→B
该公式看上去难以理解，所以证明如下：
∀x（A（x）→B）⇔∀x（┓A（x）∨B）蕴涵律
⇔∀x┓A（x）∨B
⇔┓∃xA（x）∨B 否定的交换
⇔∃xA（x）→B 蕴涵律
（6）∀x（B→A（x））⇔B→∀xA（x）
（7）∃x（A（x）→B）⇔∀xA（x）→B （证明类似公式（5））（
（8）∃x（B→A（x））⇔B→∃xA（x）
4.量词和联结词的关系的等值式
∀xA（x）∧∀xB（x）⇔∀x(A（x）∧B（x）)
∃xA（x）∨∃xB（x）⇔∃x(A（x）∨B（x）)
5.量词和联结词的重言蕴含式
∀xA（x）∨∀xB（x）⇒∀x（A（x）∨B（x））
∃x（A（x）∧B（x））⇒∃xA（x）∧∃x B（x）
后者是不能推出前者的，比如对于第一个公式：
x有两个取值，x取0时，A（x）为True, B（x）为False; x取0时，A（x）为False, B（x）为True. 此时，前者能推出后者，后者不能推出前者。
《
利用以上规则及前面命题逻辑中相应的公式，我们可以进行公式的等价性证明.
举例来说：
证明┓∀x∀y（F（x）∧G(y) →H(x,y)）⇔∃x∃y（F（x）∧G(y) ∧┓H(x,y)）证：┓∀x∀y（F（x）∧G(y) →H(x,y)）
⇔∃x ┓（∀y（┓（F（x）∧G(y)）∨H(x,y)））
⇔∃x∃y┓（┓（F（x）∧G(y)）∨H(x,y)）
⇔∃x∃y（F（x）∧G(y) ∧┓H(x,y)）
6.前束范式
|
所谓前束范式，通俗来讲，就是将命题公式中所有的量词提到最前面。
举例来说：
∀x F（x）∧┓∃x G(x)
化为前束范式：∀x F（x）∧┓∃x G(x)
⇔∀x F（x）∧∀x ┓G(x)
⇔∀x （F（x）∧┓G(x)）
有时，我们需要变换变元的名称：
比如：(∀x F（x，y）→∃yG(y)) →∀x H（x，y）
⇔(∀x F（x，y）→∃zG(z)) →∀t H（t，y）
⇔(┓∀x F（x，y）∨∃zG(z)) →∀t H（t，y）
⇔┓(┓∀x F（x，y）∨∃zG(z)) ∨∀t H（t，y）
⇔(∀x F（x，y）∧┓∃zG(z)) ∨∀t H（t，y）
⇔(∀x F（x，y）∧∀z┓G(z)) ∨∀t H（t，y）
⇔∀x∀z ∀t (( F（x，y）∧┓G(z)) ∨H（t，y）)
这里需要注意：我们看到在∀x F（x，y）→∃yG(y) 中，量词的作用范围只局限在其后面一个谓词，所以尽管后面∃yG(y)含有y,但此y不是F（x，y）中的y. 所以∃yG(y)可以变为∃zG(z)；但是∀x H（x，y）中的y,由于前面没有量词来约束y,所以此y和F（x，y）中的y是同一个y.。