文件名称：持久的演绎丑闻-研究论文
文件大小：1.44MB
文件格式：PDF
更新时间：2024-06-09 07:59:12
Boolean Logic Tractability Semantic Information
演绎推理通常被认为是“重言式”或“分析性”：结论所传达的信息包含在前提所传达的信息中。 但是，这种想法与一阶逻辑的不确定性和布尔逻辑的（可能）难处理性相冲突。 在本文中，我们从语义和证明理论的角度解决了这个问题。 我们提出了命题逻辑的层次结构，尽管借助不断增长的计算资源，这些命题逻辑都是易处理的（即在多项式时间内可确定），并趋向于经典的命题逻辑。 潜在的主张是，该层次结构可用于表示布尔推理的“深度”或“信息性”水平的提高。 特别注意此层次结构中最基本的逻辑，即纯“整数逻辑”，它满足自然演绎系统的所有要求（允许每个逻辑运算符同时引入和消除规则），同时承认可行的（二次的）决策程序。 我们认为这种逻辑在特别严格的意义上是“分析”的，因为它排除了对“虚拟信息”的任何使用，而“虚拟信息”的使用主要负责标准经典系统的组合爆炸式增长。 结果，协调了分析性和易处理性，并且计算复杂性的增长程度与允许使用虚拟信息的深度有关。