De Logica Mathematica 02 // 数理逻辑笔记 〇二:一阶语言的语义

Structurae & Interpretationes 结构与解释

〔定义 2.1〕:

S 为符号集,S–结构S-structure)是具有下述性质的二元组 A=(A,a)

 (α) A 是非空集合,称为 A论域(domain)或全集(universe);

 (β) a 是定义于 S 的映射,满足以下条件:

   (1) 对任一 n 元关系符号 RSa(R)A 上的 n 元关系;

   (2) 对任一 n 元函数符号 fSa(f)A 上的 n 元函数;

   (3) 对任一常元 cSa(c)A 的元素.

后文将 a(R),a(f),a(c) 分别记为 RA,fA,cARA,fA,cA.结构 A,B, 的论域相应地记作 A,B,.结构 A=(A,a) 中的映射 a 将会写成符号集中对应符号的值列表,如 {R,f,c}–结构记作 A=(A,RA,fA,cA)

〔定义 2.2〕:

AS–结构,映射 β:{vnnN}A 将变元映射为 A 中的元素,称为 A 的一个赋值(assignment).

S–解释(interpretation)I 是指含有一个 S–结构 A 与其中的一个赋值 β 的二元组 (A,β)

βA 的一个赋值,aAx 为变元,则 βax 表示将 x 映射为 a,而将与 x 相异的元素如同 β 一样映射的赋值,即

βax(y):={a,y=x,β(y),otw.

对于 I=(A,β),记 Iax=(Aax,β)

Relatio Satisfactionis Consequentiaeque 满足关系与推论关系

〔定义 2.3〕:

定义 I=(A,β)S–解释,函数 I(t) 将每个项 t 映射为 A 的元素,即
 (α) 对变元 vI(v):=β(v)

 (β) 对常元 cI(c):=cA

 (γ) 对 n 元函数符号 fS,以及项 t1,,tnI(ft1tn)=fA(I(t1),,I(tn))

对公式 φ 归纳,可如下定义关系「Iφ模型(model)」,其中 I 是任意的解释.「Iφ 的模型」可以等价地称为「I 满足(satisfies)φ」或「φI 中成立(holds)」,并记作 Iφ

〔定义 2.4〕:

It1t2:iffI(t1)=I(t2)IRt1tn:iffRAI(t1)I(tn)I¬φ:iffIφI(φψ):iffIφIψI(φψ):iffIφIψI(φψ):iffIφIψI(φψ):iffIφIψIxφ:iffaA,IaxφIxφ:iffaA使Iaxφ

易知,Iφ 当且仅当 φI 解释下为真命题.

对于 S–公式集合 Φ,若对任意 φΦ,均有 Iφ,则称 IΦ 的模型(I 满足 Φ),并记作 IΦ

〔定义 2.5〕:

Φ 为公式集合,φ 为公式.φΦ推论(consequence),当且仅当满足 Φ 的所有解释亦满足 φ,记作 Φφ

ψ 为公式,{ψ}φ 简记作 ψφ

〔定义 2.6〕:

公式 φ有效的(valid),当且仅当 φ,记作 φ.因此公式有效当且仅当其在所有解释下均成立.

公式 φ可满足的(satisfiable),当且仅当存在满足 φ 的解释,记作 Satφ.公式集合 Φ 是可满足的,当且仅当对于任意 φΦ,均有 Satφ,记作 SatΦ

〔引理 2.a〕:

对于任意公式集合 Φ 及任意公式 φΦφ 当且仅当 SatΦ{¬φ} 不成立.

特别地,φ 有效当且仅当 {¬φ} 不可满足.

〔证明〕:

Φφ

当且仅当所有满足 Φ 的解释亦满足 φ

当且仅当不存在满足 Φ 而不满足 φ 的解释,

当且仅当不存在满足 Φ{¬φ} 的解释,

当且仅当 SatΦ{¬φ} 不成立.

Urgetur ab Hexo and Hexo-theme-hiker

Copyright © 2021 - 2024 Histologium Kotobae All Rights Reserved.

UV : 2955 | PV : 6124