造价通

反馈
取消

热门搜词

造价通

取消 发送 反馈意见

相对解析分层解析分层

2022/07/16270 作者:佚名
导读:解析分层亦称解析谱系。按照量词复杂性对解析关系所作的递归论分层。与算术分层类似,任何解析关系可以用算术关系加上有穷个交替出现的二阶函数量词ᗄ′与∃′表示,依照量词个数,可以将该解析关系纳入具体的解析分层Σ1n或π1n中。形式地,具体的解析分层Σ1n,π1n,Δ1n可递归定义如下: 1.Σ10=π10={R:R为算术关系}。 2.Σ1n 1={(∃′f)R(f,f1,f2,…,fk,x1,x2,…,

解析分层亦称解析谱系。按照量词复杂性对解析关系所作的递归论分层。与算术分层类似,任何解析关系可以用算术关系加上有穷个交替出现的二阶函数量词ᗄ′与∃′表示,依照量词个数,可以将该解析关系纳入具体的解析分层Σ1n或π1n中。形式地,具体的解析分层Σ1n,π1n,Δ1n可递归定义如下:

1.Σ1010={R:R为算术关系}。

2.Σ1n 1={(∃′f)R(f,f1,f2,…,fk,x1,x2,…,xm):R∈π1n}.

3.π1n 1={(ᗄ′f)R(f,f1,f2,…,fk,x1,x2,…,xm):R∈Σ1n}。

4.Δ1n1n∩π1n.

Σ1n,π1n与Δ1n中的关系分别称为Σ1n关系、π1n关系与Δ1n关系,此外,Δ1w定义为:∪{Σ1n∪π1n:n∈ω},即所有解析关系的集合。此外,对n≥1,Σ1n关系可表示成下形范式:

(∃′f1)(ᗄ′f2)…(Qnfn)(Qx)

R(f1,…,fn,fn 1,…,fn p,x,x1,…,xq),

其中若n为偶数,Q1n为ᗄ′,Q0为∃0;若n为奇数,Q1n为∃′,Q0为ᗄ0;而R为递归关系。π1n关系也可表示成以ᗄ′开头的类似表达式.解析分层还具有如下封闭性:

1.Σ1n,π1n,Δ1n对合取、析取运算与一阶量词封闭。

2.Δ1n对否定运算封闭。

3.R∈Σ1n,当且仅当ᒣR∈π1n

R∈π1n,当且仅当ᒣR∈Σ1n

4.对n≥1,Σ1n对二阶量词∃′封闭,πn对二阶量词ᗄ′封闭。

关于解析分层的其他性质,参见“解析枚举定理”。此外,与算术分层不同,Δ11≠Σ101010,Δ11的关系称为超算术关系。

*文章为作者独立观点,不代表造价通立场,除来源是“造价通”外。
关注微信公众号造价通(zjtcn_Largedata),获取建设行业第一手资讯

热门推荐

相关阅读