当前位置：首页 > 文化百科

逻辑百科辞典

本文作者:四库百科 (www.04bk.com) 时间 : 2020-05-20 13:55:35 如有异议请联系管理!

作者：周礼全
出版社：四川教育出版社
出版时间： 1994-02-01

逻辑百科辞典的章节2

更多 >>

ω协调性

又称ω无矛盾性，形式(算术)系统的一个性质。一个形式系统称为ω协调的，如果没有一个公式A(x)使得下列各公式 A(0)，A(1)，…，A(n)，…；xA(x) 都在系统中可证。相反的情况，即：对每个自然[阅读]
ω完全性

形式算术系统的一个性质。一个形式系统称为ω完全的，如果对任何公式A(x)，从A(0)，A(1)，A(2)，…都是可证的，就能得出xA(x)是可证的。反之，称这系统是ω不完全的。哥德尔不完全性定理[阅读]
λ可定义函数

在λ演算(参见拉姆达演算)中数字可表示的函数。在λ演算中引入组合算子：I=λx·x，K=λxy·x。则对任意λ项M，N，λ┝IM＝M，λ┝KMN=M。用［M，N］表示序偶，定义［M，N］=λx·xMN。于是可以在λ[阅读]
U-S时态逻辑

通过引入二元时态算子U(直至)和S(自从)以及相应的公理和规则对经典逻辑进行扩充所得到的时态逻辑系统。对U-S系统的研究源自于对一元时态算子G-H表达能力的考察。在经典逻[阅读]
UR机

全称为“具有无限寄存器的计算机”(unlimited register machine)，1963年由舍弗尔德森(Shepherdson)和斯图尔吉斯(Sturgis)提出的一种理论计算机。由于它比较接近实际的电子[阅读]
T完全集

也称T完全的递归可枚举集。设AN，如果对任何递归可枚举集B都有B≤A，而A本身也是递归可枚举集，则称A为T完全集。 m完全集都是T完全的，但反之不然。[阅读]
s-m-n定理

递归论研究中一条应用极广的定理。设为第e号图灵机所计算的n元函数。任给一个m+n元部分递归函数f(x，…，x，y，…，y)，它必定出现在函数序列 φb，φ，φ2，…(*) 之中，设e是它的一个号码： f[阅读]
Rt时态逻辑

引入Rt算子，将时态词换成事件发生的具体时刻，从而将句子的时态去掉后进行处理的时态逻辑，其中Rt(p)表示“P在时间t成立”。这种类型的时态逻辑源于J．洛斯于1947年研究归纳推理[阅读]
P=NP问题

计算复杂性理论中一个尚未解决的重要问题：确定型图灵机多项式有界时间可计算的函数类是否等于非确定型图灵机多项式有界时间可计算的函数类。确定型图灵机就是普通的图灵机[阅读]
NP完全问题

设A、B是自然数集，如果存在确定型图灵机多项式时间有界可计算的函数k(x)(即k(x)∈P，参见P=NP问题)使 x∈B 当且仅当 k(x)∈A，则称B可在多项式时间内归约到A，记作 B≤A (显然，若[阅读]
m完全集

也称m完全的递归可枚举集。如果自然数集A是递归可枚举集，且对任何递归可枚举集B都有。 B≤A，则称A为m完全集(参见多一归约) 从m归约的角度可以认为m完全集是包含信息最多的[阅读]
m度

自然数集在(等价关系)≡下的等价类称为m度，含有集合A的m度记作d(A)： d(A)=｛BA≡B｝ (参见多一归约)。设a、b为两个m度，A∈a，B∈b；如果A≤B，则记a≤b；若a≤b且a≠b，则记a＜b 以下是几个[阅读]

热门推荐

野史解密
民间故事
幽默故事
童话故事
历史故事

网友喜欢读