2012-2-22 一阶逻辑 2
注意：
在论域不同时，命题符号化的形式也不同 若未给出论域，则以全总个体域为论域 论域确定后，使用全称量词与存在量词符 号化形式不同 多个量词同时出现时，不能随意颠倒次序 ∀x∃y(x≤y) ∃x∀y(x≤y)
2012-2-22
一阶逻辑
3
谓词演算的形式系统
字母表 公式 公理 推理规则 形式语言 形式推理
最外层 优先级递减： ∃, ∀; ¬; ∧,∨, →,↔
2012-2-22
一阶逻辑
17
合式公式中的变项
量词辖域: 在∃xA, ∀xA中, A是量词的辖 域. 例如: ∃x(F(x)∧∀y(G(y)→H(x,y))) 指导变项: 紧跟在量词后面的个体变项. 例如: ∃ ∃x(F(x)∧∀y(G(y)→H(x,y))) ∧∀ → 约束出现: 在辖域中与指导变项同名的变 项. 例如: ∃x(F(x)∧∀y(G(y)→H(x,y))) 自由出现: 既非指导变项又非约束出现. 例如: ∀y(G(y)→H(x,y))
一阶逻辑 9
L生成的一阶语言
个体常元: 函数符号: 谓词符号: a, b, c, …, a1, b1, c1,… f, g, h, …, f1, g1, h1,… F, G, H, …, F1, G1, H1, …
非逻辑符号并不一定都出现 一阶语言随着非逻辑符号的不同而不同，称为 由非逻辑符号集合L生成的一阶语言。
2012-2-22
一阶逻辑
8
字母表
个体常元: 函数符号: 谓词符号: 个体变元: 量词符号: 联结词符号: 括号与逗号:
2012-2-22
a, b, c, …, a1, b1, c1,… f, g, h, …, f1, g1, h1,… F, G, H, …, F1, G1, H1, … x, y, z, …, x1, y1, z1,… ∃, ∀ ¬, ∧, ∨, →, ↔ (, ), ，
原子公式是合式公式 若A是合式公式，则(¬A)是合式公式 若A,B是合式公式，则(A∧B), (A∨B), (A→B), (A↔B)也是合式公式 若A是合式公式，则∃xA, ∀xA也是合式 公式 只有有限次地应用上述规则形成的符号 串才是合式公式
2012-2-22 一阶逻辑 16
合式公式（举例）
∃x(F(x)∧∀y(G(y)→H(x,y))) F(f(a,a),b) F(x,y) 约定：省略多余括号
赋值(举例)
F(f(a,a),b) 赋值1： 个体域是全体自然数; a: 2; b: 4; f(x,y)=x+y; F(x,y): x=y 原公式赋值成: “2+2=4”。 赋值2： 个体域是全体实数; a: 3; b: 5; f(x,y)=x-y; F(x,y): x>y 原公式赋值成: “3-3>5”。
2012言是用于一阶逻辑的形式语 言 一阶逻辑是建立在一阶语言上的逻 辑体系
2012-2-22
一阶逻辑
5
一阶语言
谓词演算形式系统语言
•非逻辑符号 •逻辑符号 •项 •（合式）公式
2012-2-22
一阶逻辑
6
非逻辑符号
个体常元: 函数符号: 谓词符号: a, b, c, …, a1, b1, c1,… f, g, h, …, f1, g1, h1,… F, G, H, …, F1, G1, H1, …
可满足式：非永假式
2012-2-22 一阶逻辑 24
代换实例
在含命题变项p1,p2,……,pn的命题公式中, 每个命题变项代换成一阶逻辑公式所得 到的式子, 称为原来公式的代换实例. 例： F(x)→G(y) ¬ ∀xF(x)∨G(y)
2012-2-22
一阶逻辑
25
一阶逻辑公式分类
例： ¬∀xF(x) ↔ ∃x¬F(x) ∀xF(x) →(G(y) → ∀xF(x) ) ∃xF(x) → ∀yG(y) ¬(∀xF(x) →∃yG(y) ) ∧ ∃yG(y)
把函数和谓词中的变元直接写到符号后 的括号中,如F(x,y,x), g(x,y)等 非逻辑符号集合常记为L
2012-2-22 一阶逻辑 7
逻辑符号
个体变元: 量词符号: 联结词符号: 括号与逗号: x, y, z, …, x1, y1, z1,… ∃, ∀ ¬, ∧, ∨, →, ↔ (, ), ，
2012-2-22 一阶逻辑 22
赋值
是否存在一种公式在任何赋值下都 取相同的真值呢？
2012-2-22
一阶逻辑
23
一阶逻辑永真式(tautology)
永真式:在各种赋值下取值均为真(逻辑有 效式) 命题逻辑永真式: 在各种赋值下取值均为真
(重言式)
永假式:在各种赋值下取值均为假(矛盾式)
命题逻辑永假式: 在各种赋值下取值均为假 (矛盾式)
2012-2-22
一阶逻辑
14
原子公式(atomic formula)
若R(x1,x2,…,xn)是n元谓词, t1,t2,…,tn是项, 则R(t1,t2,…,tn)是原子公式 例如: F(a), G(a,y), F(f(a)), G(x,g(a,y))
2012-2-22
一阶逻辑
15
合式公式(well-formed formula)
2012-2-22
一阶逻辑
10
L生成的一阶语言举例
如：非逻辑符号
个体常元: 函数符号: : 0 +
L1={0, +} 如：非逻辑符号
个体常元: 函数符号: 0，1 +,*
L2={0,1, +,*}
2012-2-22 一阶逻辑 11
L生成的一阶语言说明
非逻辑符号与所描述的特定对象有关。 逻辑符号是逻辑系统中的符号。 一阶逻辑研究一阶语言的一般性质，而 不是针对某个特定的一阶语言。对一个 具体的应用而言，L通常是不言自明的， 由使用的全部非逻辑符号组成。
闭式: 无自由出现的变项 一般来说, 闭式表示的是命题, 例如
F(a) ∃xF(x) F(x) ∀y(G(y)→H(x,y))
后两个不是闭式
2012-2-22 一阶逻辑 20
赋值(解释interpret)
对一个合式公式的赋值包括给出
个体域 谓词 函数 个体常项
的具体含义
2012-2-22
一阶逻辑
21
一阶(谓词)逻辑
量词 谓词、函数 个体词 个体域
全总个体域: 世界上的万事万物 特性谓词: 表示所关注的对象的性质
2012-2-22 一阶逻辑 1
苏格拉底三段论
凡人都是要死的。 苏格拉底是人。 所以，苏格拉底是要死的。 重新符号化：∀, ∃, F( ), x, a 设：F(x)：x是人。G(x)：x是要死的。 a：苏格拉底。 前提：∀x(F(x)→G(x))，F(a) 结论：G(a)
2012-2-22 一阶逻辑 12
一阶(first order)逻辑的合式公式
项 原子公式 合式公式
2012-2-22
一阶逻辑
13
项(term)
个体常项和个体变项是项 若ϕ(x1,x2,…,xn)是n元函数, t1,t2,…,tn是项, 则ϕ(t1,t2,…,tn)是项 所有的项都是有限次地应用上述规则形 成的 例如: a, x, f(a), g(a,x), g(x,f(a))
2012-2-22 一阶逻辑 18
合式公式中的变项(举例)
H(x,y)∨∃xF(x)∨∀y(G(y)→H(x,y)) x 与 y 是指导变项 x与y是约束出现 x与 y是自由出现 注：同一变元在同一公式中可能既有约 束出现又有自由出现
2012-2-22 一阶逻辑 19
闭式(closed form)
2012-2-22
一阶逻辑
26
习题
P66 10,11,12,15
2012-2-22
一阶逻辑
27