2数理逻辑(编辑修改稿)

2数理逻辑(编辑修改稿)内容摘要：

q) →r 2. Give the normal disjunction formumlas of the following statements (1) ((p∨ q) →r) →p ~q p→ q ~p p→ q q→ r p→ r p∨ q p→ r q→ s r∨ s (2) ~( p→q)∧ q∧ r 3. Give the deductions of the following consequence (1) p→q, r→~q, r∨ s, s→~q⇒ ~p (2) ~(p∧ ~q), ~q∨ r, ~r⇒ ~p (3) p→ (q→r), q, p∨ ~s⇒ s→r First Order Logic 谓词和量词 Predicate and Quantifiers 1 谓词 Predicate 关系 Relation 集合 {x|P(x)}中 P(x) 变元 x满足某种性质 称 P(x)为一元谓词 ,或一元关系 Q(x,y) 二元谓词二元关系 R(x,y,z) 三元谓词三元关系 论域 A中元素 a,b,c∈ A,满足关系 P,Q,R，记作 P(a),Q(a,b),R(a,b,c). 不满足关系记作 ~P(a),~Q(a,b),~R(a,b,c). 函数 Function 论域 A上的函数是一种特殊的关系，也是谓词 F:A→A，一元函数，也是二元关系 对任意 x∈ A, F(x) ∈ A, F(x)唯一确定。 G:A A→A,二元函数，任意 x,y∈ A,G(x,y) ∈ A唯一确定。 对 a,b,c∈ A, 如果 F(a)=b, 就说 F(a)=b 真。 G(a,b)=c就说 G(a,b)=c真。 2 量词 Quantifier 全称量词 Universal Quantifier ∀ ∀ xP(x), ∀ yQ(x,y) 存在量词 Existencial Quantifier ∃ ∃ xP(x), ∀ x∃ yQ(x,y) 一阶逻辑的符号集 语言 Language 1 逻辑符号 个体变元 v1,v2,v3,…… 命题联结符号 ~， ∨ ， ∧ ， →， ↔ 量词符号 ∀ ， ∃ 等号 = 技术符号），（ 2 非逻辑符号 关系符号 P,Q,R,…… 每个关系符号都指定是几元关系 函数符号 F,G,H,…… 每个函数符号都指定是几元函数 常量符号 a,b,c,…… 2 一阶语言 L ={P,Q,R,……。 F,G,H,……。 a,b,c…… } 非逻辑符号属于每一个一阶语言。 一阶逻辑的公式 formulas of first order logic 1．项 term 1） 单个命题变元 vi是项， 2）单个常量是项， 3） 如果 t1,t2,… ,tn是项， F是 n元函数符号，则 F(t1,t2,… ,tn)是项。 例 L={+， ， 0,1} v1+v2 +1 是 L的项。 2．原子公式 atomic formulas 1）若 t1,t2是项，则 t1=t2是原子公式， 2）若 t1,t2,… ,tn是项， P是 n元关系符号，则 P(t1,t2,… ,tn)是原子公式。 v1 +1=0 v1+v2 +10 都是原子公式。 3．公式 1）原子公式是公式 , 2) 设 φ， ψ是公式，则（ ~φ），（ φ∧ ψ），（ φ∨ ψ），（ φ→ψ），（ φ↔ψ）， 3) 设 φ， ψ是公式， x是个体变元则（ ∀ xφ）， (∃ xψ)都是公式。 ∃ v1 (v1 +1=0) ∀ v2 (v1+ v2 +10) ∀ v1 (v1 +1=0 →∃ v2 (v1+ v2 +10) ) 量词的辖域约束变元和自由变元 ∃ v1 (v1 +1=0) 量词的辖域是全公式。 v1是约束变元 ∀ v2 (v1+ v2 +10) 量词的辖域是全公式。 v2是约束变元 , v1是自由变元 ∀ v1 (v1 + v2+1=0 →∃ v2 (v1+ v2 +10)) ∃ v2 的辖域是 (v1+ v2 +10) ∀ v1的辖域是全公式， v1是约束变元，第二个 v2是约束变元，第一个 v2是自由变元 . 公式常记作 φ(x1,x2,…… ,xn), φ中自由变元都在 x1,x2,……,x n中。 没有自由变元的公式 φ叫做闭公式，也叫句子。 一阶语言 L的 一个句子集叫做一个理论。 一阶语言的模型 Model— 数学结构 Mathematical Structure 一阶语言 L={ P,Q,R,…。 F,G,H,…。 a,b,c… } 一阶语言的模型 M=〈A, PM,QM,…。 FM,GM,HM,…。 aM,bM,cM… 〉 A 是论域 Universe， PM,QM,RM,…是 A的关系 FM,GM,HM,…是 A上函数 aM,bM,cM… 是 A 的元素 例 〈N,+,0〉,〈N,+,∙,0〉, 〈Z,+,∙,0,1〉,〈R,+,∙,0,1〉, 〈Zn,+,∙,0,1〉 都是模型。 一阶公式的赋值 一阶公式在模型 M上的赋值。 1 项的解释 1）先为个体变元 指派 模型论域中的一些元素做解释， a1, a2,……∈ A, σ (v1,v2…… )=( a1,a2,…… ) x=vi , a∈ A, σ (a/x)=( a1,a2,… ,a,… ) 2）项 t1,t2,… ,tn如果有解释 t1σ ,t2σ ,… ,tnσ ， F是 n 元函数符号，则 Fσ (t1,t2,… ,tn)=FM(t1σ ,t2σ ,… ,tnσ ) 2．原子公式 的取值 1）原子公式 t1=t2的取值，对赋值σ，若 t1σ =t2σ 则在模型 M中 t1=t2取值为真，记作 M╞σ t1=t2. 2）原子公式 P(t1,t2,… ,tn) 的取值 , 对赋值σ，若 PM(t1σ ,t2σ ,… ,tnσ )成立， 则在模型 M 中 P(t1,t2,… ,tn),取值为真，记作 M╞σ P(t1,t2,… ,tn). 3．公式的取值 对赋值σ，公式 φ在模型 M中取值真， 记作 M╞σ φ. 1) M╞σ ~φ 当且仅当 M╞σ φ. 2) M╞σ φ∨ ψ 当且仅当 M╞σ φ或 M╞σ ψ 3) M╞σ φ∧ ψ 当且仅当 M╞σ φ且 M╞σ ψ 4) M╞σ φψ 当且仅当 M╞σ ~φ或 M╞σ ψ 5) M╞σ φ↔ ψ 当且仅当 M╞σ φ且 M╞σ ψ 或 M╞σ φ且 M╞σ ψ 6) M╞σ ∀ xφ当且仅当对任意 a∈ A, M╞σ (a/x)φ 7) M╞σ ∃ xφ当且仅当存在 a∈ A, M╞σ (a/x)φ 模型 M=〈Z,+,∙,0,1〉,σ =(0,0,…… ) 公式 ∃ v1 (v1 +1=0)， ∀ v2 ( v1∙ v2+10)， ∀ v1 (v1 ≠ 0 →∃ v2 (v1+ v2 +10) ) 在 M 上的取值： M╞σ ∃ v1 (v1 +1=0) M╞σ ∀ v2 (v1∙v2 +10) M╞σ ∀ v1 (v1≠ 0 →∃ v2 (v1∙ v2 +10) ) 一个公式的 取值只与公式中自由变元的解释有关，与约束变元的取值无关。 M╞σ φ(x1,x2,…… ,xn) 当且仅当 M╞φ(x1σ ,x2σ ,…… ,xnσ ) 如果 x1σ =a1, x2σ =a2, …… ,xnσ =an, 则 M╞σ φ(x1,x2,…… ,xn)也写成 M╞φ(a1,a2,…… ,an). 闭公式在模型中的取值与指派 σ无关 ， 如果存在一个指派 σ ， M╞φ，则对任意指派 M╞φ。 一阶公式的分类 恒真式 如果公式 φ (x1,x2,…… ,xn), 在模型 M的任何指派下取值都是真，就称为在 M中恒真，记作M╞φ。 如果公式 φ(x1,x2,…… ,xn), 在任何模型，任何指派下取值都是真，就称为恒真式 , 记作 ╞φ。 恒假式 如果公式 φ(x1,x2,…… ,xn), 在任何模型，任何指派下取值都是假，就称为恒假式。 可满足公式 如果公式 φ (x1,x2,…… ,xn), 存在模型，存在指派取值为真，就称为可满足公式。 ╞φ→ φ， ╞φ→ ψ→ φ。 命题逻辑的所有恒真形式都是恒真式。 Homework Prove the following 1) ╞φ(x)→∃ xφ(x)， 2) ╞∀ x(φ→ψ)→∀ xφ→∀ xψ 3) ╞∀ x(φ→ψ) →∃ xφ→∃ xψ。 4) ╞∀ x(φ∧ ψ) →∀ xφ∧ ∀ xψ 5) ╞∃ x (φ∨ ψ) →∃ xφ∨ ∃ xψ Prove each of the following is not a tautology 1) φ(x) →∀ xφ(x), 2)∀ x∃ yφ(x,y)→∃ y∀ xφ(x,y). 一阶公式的等价变换 1 等价公式 如果一阶公式 φ(x1,x2,…… ,xn), ψ(x1,x2,…… ,xn)在任何模型，任何指派下都有相同取值，就称φ(x1,x2,…… ,xn), ψ(x1,x2,…… ,xn)是等价公式 ，记作 φ(x1,x2,…… ,xn) ψ(x1,x2,…… ,xn)。 φ(x1,x2,…… ,xn)ψ(x1,x2,…… ,xn)是等价公式当且仅当 φ(x1,x2。