排序方式： 共有4条查询结果，搜索用时 15 毫秒
1
1.
使用辅助变元来引入定义,在知识表达中是一个流行和有力的技巧,能够得到更短、更自然的编码而无需冗长的重复。这篇论文中,我们形式地定义了辅助变元的概念,检验了其表达力并讨论了有趣的相关应用。我们把以下两者联系起来:一是,反复使用中间结果而不通过定义重复;二是,布尔函数其他表达中的相似概念。特别的,我们表明带定义的命题逻辑与具有任意输出端的布尔线路以及约束变元满足Horn性质的存在量化布尔公式(记作(?)HORN~b)具有相同的表达力。本文还考虑了定义结构的限制,以及命题定义的扩充。特别的,我们检验了正命题定义与带存在量化的正定义之间的关系(或等价地,检验了(?)HORN~b公式和约束变元未被Horn限定的存在量化的CNF公式(记作(?)CNF~*)之间的关系)。对命题定义的进一步扩充,是允许在定义中使用任意的量词,或等价地,允许布尔公式的嵌入。我们还证明了,量化CNF公式中的约束变元的表达力,是由子句中被约束部分的极小不可满足子公式或极小假子公式的结构所决定的。 相似文献
2.
不同的时态逻辑能够适应不同的推理任务。为了符合应用,关于时间的模型从离散的自然数和整数,延伸到稠密的线性实数,甚至扩展到区间代数和树代数。如果简单的时态连接词的表达力已经足够,就只需使用这些简单的时态连接词来构造的时态逻辑。在能够承担降低运算速度的风险下,我们可以为实现更强的表达力而使用更多的连接词,也可以加上度量信息或者固定点。作者近期提出了一个令人惊讶的结论:建立在实数时间上的具有足够表达力的语言和基于自然数离散时间流的传统简单算子,它们推理的计算复杂性是一样的。在这篇论文中,作者试图对建立在标准时态连接词和线性时间流的普通类上的时态逻辑中所有决策问题的计算复杂性作新的说明。尤其是,文中指出,所有标准逻辑在PSPACE中都存在决策问题。 相似文献
3.
我们在膨胀不动点逻辑IFP的基础上,加入一种带有(多重)对数上界的新二阶量词,并且证明了,在有序结构上我们的新逻辑■logωIFP刻画受限非确定性复杂类βP。为了研究该逻辑的表达力,我们也设计了一种新的Ehrenfeucht-Fraïssé博弈,并说明在最一般的情况下,也就是在全体有穷模型之上,该逻辑对βP的刻画并不成立。 相似文献
4.
尽管自然语言没有形式语言那样严格,在某些情况下甚至会造成歧义,但日常生活中,我们不可能放弃自然语言而采取形式语言作为人际交流的媒介。事实上,形式语义学的研究表明,自然语言本身也存在着多种值得研究的形式结构。自然语言有很多吸引人的特点,例如其中不含形式语言中那样的变 相似文献
1