数学
Mathematics
代数几何
Algebraic Geometry
代数拓扑学
Algebraic Topology
偏微分方程分析
Analysis of PDEs
我们为量化布尔公式(QBF)引入了新的半代数证明系统,类似于Nullstellensatz,Shereali-Adams和Sum-of-Squares的命题系统。 我们从QBF文献(策略提取)和命题证明复杂性(大小度关系和伪期望)转移到这种设置技术。 我们获得许多强大的QBF下界和这些系统之间的分离,即使无视命题硬度。
使用生成式AI模型进行高级数学的主要缺点是,这些模型不是逻辑推理引擎。 然而,大型语言模型及其改进可以在高等数学中选择人类难以看到的模式。 通过将生成式AI模型的设计发挥优势,数学家可以将它们用作强大的交互助手,可以执行繁琐的任务,生成和调试代码,检查示例,制定猜想等等。 我们讨论了如何利用生成式AI模型推进数学研究。 我们还讨论了他们与计算机代数系统和Lean等正式证明助手的集成。
基于量子逻辑的模态逻辑以最简单的形式形式化。 具体来说,提供了关系语义和隐性微积分,并证明了连接这两个概念的健全性和完整性定理。 该框架旨在作为将量子逻辑的各种模态逻辑形式化的基础,例如量子极化逻辑、量子时间逻辑、量子认识论逻辑和量子动态逻辑。
Tarski 的 E_2 欧几里得几何学一阶公理系统 E_2 以其完整性和可判定性而著称。 然而,毕达哥拉斯定理 - 无论是在其现代代数形式 a^2+b^2=c^2 还是在欧几里德的元素中 - 都不能直接用E_2表示,因为距离和面积都不是E_2语言中的原始概念。 在本文中,我们引入了一种双排序语言的替代公理系统 E_d ,它以双位距离函数 d 作为唯一的几何原语。 我们还介绍了它的保守扩展E_da,其中还包含一个三位角函数a。 该系统 E_d 有两个显著特征:它简单(具有单一的几何原始),并且是定量的。 数值距离可以用这种语言直接表达。 相似性公理在 E_d 中起着核心作用,用一块石头有效地杀死两只鸟:它为比例和相似性理论提供了严谨的基础,它暗示了欧几里德的平行姿势(EPP)。 相似性公理可以看作是EPP的定量表述。 毕达哥拉斯定理和相似性理论的其他定量结果可以直接用E_d和E_da的语言表达,激励了Quantitative Euclidean Geometry的名称。 传统的分析几何学可以在E_d的合成几何学下统一。 也就是说,解析几何学不被视为E_d的模型,而是其语句可以用E_d的语言表示为一阶形式句子。 系统 E_d 被证明是一致、完整和可决定的。 最后,我们将理论扩展到高维度的双曲几何和欧几里得几何。
这项工作引入了一个框架,通过使用暗示超图来量化逻辑命题的信息内容。 我们认为,命题的信息性主要取决于它与其他命题的关系;特别是它暗示或衍生其他命题的程度。 为了正式确定这个概念,我们开发了一个基于暗示超图的框架,试图捕捉这些关系。 在这个框架中,我们定义命题信息,导出一些关键属性,并通过示例来说明概念。 虽然该方法广泛适用,但数学命题因其固有的丰富和相互关联的结构而成为其应用的理想领域。 我们提供几个例子来说明这一点,然后讨论框架的局限性,以及潜在的改进建议。
我们描述了Monadic二阶逻辑(MSO)中的句子,这些句子在存在鹅卵石游戏中等同于Datalog程序的有限结构。 我们还表明,对于可以在MSO中表达并在同态下关闭的每个类有限结构的C类,对于所有整数l,k,在Feder和Verdi的意义上存在一个规范的宽度(l,k)数据程序Pi。 相同的特征也适用于受保护的二阶逻辑(GSO),它正确地扩展了MSO。 为了证明我们的结果,我们表明GSO中的每一个C类,其补充在同态下是约束满意度问题(CSP)的有限结合,可数分类结构。 众所周知,MSO和Datalog的交集包含嵌套monadically定义查询(Nemodeq)的类;同样,我们表明GSO和Datalog的交集包含所有可以通过嵌套保护查询的更富有表现力的语言表达的问题。 然而,通过利用我们的结果,我们可以证明这两种查询语言都不能作为表征,因为我们在MSO和Datalog的交叉中展示了一个在嵌套保护查询中无法表达的查询。
我们考虑一阶逻辑中的一类公式方程,Horn公式方程,这是由对谓词变量发生的句法限制定义的。 角方程在计算机科学的许多应用中发挥着重要作用。 我们用最少的定点运算符在一阶逻辑中对 Horn 公式方程进行定点定理。 我们的定点定理是抽象的,因为它适用于概括标准语义的抽象语义。 我们描述了这个定点定理在计算逻辑的各个领域的几个推论,从程序验证的逻辑基础到归纳定理证明。
在本文中,我们提供了Barmpalias-Lewis-Pye结果的简单证明,即所有可计算增加的序列汇合到随机真实,以相同的速度(高达c+o(1)因子)收敛,并指出它立即遵循Bishop的交叉不平等。 我们还提供了这种不平等的简单推导。
我处理了两种证明理论语义的方法:一种基于论证结构和理由,我称之为可还原性语义,一种基于原子基(集)公式之间的后果,称为基础语义。 后者反过来分裂为标准读数,以及Sandqvist提出的变体。 我证明一些结果,当满足适当的条件时,允许一个人从一种方法转向另一种方法,我得出这些结果相对于(递归)逻辑系统在有效性的证明理论概念方面的完整性问题的一些后果。 这将导致我专注于一个基本完整性的概念,我将讨论关于直觉逻辑的已知完整性结果。 拟议方法的一般兴趣源于这样一个事实,即可还原性语义可以理解为基础语义的标签,其基础语义与基础语义产生关系(成集)的公式中键入的证明对象,并且见证了这一事实。 反之亦然,基础语义可以理解为通过删除这种关系所持有的事实的见证而获得的可还原语义结果关系的类型抽象,并且仅仅关注相关证明对象的输入和输出类型。
线性逻辑(LL)是一种资源感知的抽象逻辑编程语言,它既完善了经典逻辑,又完善了直觉逻辑。 线性逻辑语义通常以两种方式之一呈现:通过将每个公式与可用于证明它的所有上下文集(例如相位语义)或直接为证明(例如一致性空间)分配意义。 这项工作提出了通过采用证明理论视角为证明赋予意义的不同观点。 更具体地说,我们使用基础扩展语义(BeS)来表征基于基础支持的概念。 最近的发展表明,BeS足够强大,可以在结构丰富的逻辑(如直觉线性逻辑)中捕获证明理论概念。 在本文中,我们将这个框架扩展到经典案例,为线性逻辑(MALL)的乘法附加片段的语义提出了证明理论方法。
目前,缺乏严格的理论体系来系统地产生非平凡和逻辑上有效的定理。 解决这一关键差距,本文进行研究,提出一种新的自动化定理生成理论和工具。 基于具有独特演绎优势的标准矛盾概念,本文首次定义并证明了一种被称为矩形标准矛盾的新逻辑结构。 以这种结构为中心,提出了一个完整的自动理论生成(ATG)理论。 理论证明澄清了矩形标准矛盾的两个核心属性:第一,它是一个标准矛盾(必然不满足);第二,它表现出非冗余(其余条款集在删除任何子句后变得令人满意)。 利用这些属性,本文证明,将一个矩形标准矛盾分割成一个前提子集A,否定其补体H,可以形成有效的定理A ⊢ H,并且所有这些定理在逻辑上是等价的。 为了实现这一理论,设计了一个高效的基于模板的ATG算法,并开发了矩形自动定理生成器。 这项研究使机器能够从“验证者”过渡到“发现者”,为逻辑和人工智能领域的基础研究开辟了新的途径。
排列可以视为线性序对的组合，或者更形式化地，作为由两个二元关系符号组成的签名上的模型。Albert、Bouvel和Féray采用了这种方法，他们研究了在此设置下一阶逻辑的表达能力。我们将注意力集中在一元二阶逻辑上。我们的结果朝着两个方向发展。首先，我们研究一元二阶逻辑的表达能力。我们展示了排列的自然性质，这些性质可以用一元二阶逻辑表达但不能用一阶逻辑表达。此外，我们证明了即使在一元二阶逻辑中，具有不动点的性质也是不可表达的。其次，我们关注一元二阶模型检验的复杂性。我们证明存在一种算法，可以在时间f(|φ|, tw(π)) · n内判定排列π是否满足给定的一元二阶句子φ，其中n = |π|且tw(π)是π的树宽，f是某个可计算函数。另一方面，我们证明即使将排列π限制在具有温和假设的固定遗传类𝒞中，该问题仍然保持困难。
我们学习可计算可能大致正确(CPAC)学习,其中学习者必须是可计算功能。 以前观察到,统计学习的基本定理,其特征是Vapnik-Chervonenkis(VC-)尺寸的有限性,不再在这个框架中存在。 最近的作品在可计算设置中恢复了基本定理的类似物,例如引入了有效的VC-dimension。 以此为指导,我们研究了CPAC学习和递归可枚举可表示(RER)类之间的联系,这些类的成员可以算法列出。 我们的结果表明,有效的VC-dimensions可以将任意值高于传统值,即使是RER类,它为CPAC学习的各种概念创造了一个完整的(非)示例。 然而,这两个维度与满足CPAC学习足够强烈概念的课程相吻合。 然后,我们观察到CPAC可学习性也可以通过包含实现相同样本的RER类来表征。 此外,表明满足唯一识别属性的CPAC可学习类必然是RER。 最后,我们确定,通过考虑非统一CPAC学习的轻松概念,可以保证RER类的不可知论可学习性。
我们提出了新的描述性复杂性表征类REG(普通语言),LCFL(线性上下文自由语言)和CFL(无上下文语言)作为推理规则的限制,公式的大小和允许的连接在兰贝克演算; 零直觉的非交换线性逻辑的片段与方向敏感的暗示连接。 我们对具有证明复杂性REG和LCFL的兰贝克微积分碎片的鉴定是同类的第一个结果。 我们进一步展示了逻辑中严格“最弱”的可能变体之一的CFL复杂性,只承认一个单一的推理规则。 此外,其证明是基于对可证明的琉挛的语法和形式语法的直接翻译以及可证明的隐身的结构归纳;一种比先前作品中使用的更简单,更直观的方法。 因此,我们建立了切消除定理的明确概念效用,用于比较形式语法和连续演算,并确定兰贝克语法中Greibach正常形式的精确模拟。 我们认为,本文介绍的结果构成了计算与逻辑之间相互作用的更广泛和更丰富的表征的第一步,以及各种连续演算的细粒度复杂性分离。
循环证明理论研究允许循环的证明。 这对于开发具有固定点运算符的逻辑的证明理论很有用:循环可以用来表示固定点的展开。 然而,这种循环字符并不是这种显式固定点独有的。 例如,帧具有Noetherian(相反有充分理由)条件的模态逻辑,例如GL(Goedel-Loeb逻辑),S4Grz(Grzegorczyk逻辑)和K4Grz也有循环证明系统。 特别是,Shamkanov引入了一个非良好和循环序列系统GL。 他通过证明翻译证明了这两个系统的等价性与一个循环有限系统。 为了从有限系统到非有根据的系统,他通过corecursion定义了翻译。 Iemhoff概括了Shamkanov的研究,当对于给定的模态逻辑证明系统,存在另一个模态逻辑证明系统,使得第一个中的证明相当于第二个中的循环证明。 在那里,她表明iGL,一个直觉版的GL,也有一个自然的循环证明系统。 我们提供iGL和循环式计算等效性的替代证明。
我们认为模态逻辑与众所周知的时间运算符“最终”扩展,并为捕获此片段的循环隐式演算提供剪切消除程序。 这项工作展示了还原剪切方法对循环微积分的适应。 值得注意的是,提议的算法适用于循环证明,并直接输出循环无切无证明,而不会吸引中间机械对最终证明进行规范化。
传统上,代理人的信仰将来自代理人可以看到、听到或感觉到的东西。 在现代世界,信仰往往基于代理人可用的数据。 在这项工作中,我们研究这种信念的动态逻辑,其中包含数据的公开公告。 主要的技术贡献是对数据知情信念和数据公告模式之间的相互作用进行健全和完整的公理化。 我们还描述了一个非平凡的多项式模型检查算法,用于这个逻辑系统。
模块和森田等的概念是经典研究环的基础。 这些概念自然延伸到半环,然后专给Kleene代数,我的目标是调查Kleene模块和Kleene代数的Morita等效性,希望在这个新的上下文中也可以找到在环的背景下看到的一些力量。
经典和直觉逻辑传统都不是与计算推理的目的完全一致的,因为逻辑传统通常都不能允许直接表达任意的一般递归函数而不不一致。 我们引入了基础算术或GA,这是形式推理的一个极简但强大的基础,允许直接表达任意递归的定义。 GA调整了传统的推理规则,使得表示非终止计算的术语无害地表示没有语义值(即“底部”),而不是导致逻辑悖论或不一致。 递归函数可以在GA中证明终止,主要是通过“动态类型”术语,或者等价地,象征性地反向执行它们通过GA的推理规则表示的计算。 一旦递归函数被证明终止,关于其结果的逻辑推理就会减少到熟悉的经典规则。 Isabelle/HOL中机械检查的一致性证明存在于GA的基本无量分片中。 量化器可以作为普通计算添加到此基础之上,因此其推理规则可接受,并且不会引入新的不一致风险。 虽然GA只是迈向手动或自动计算推理中日常使用的丰富类型接地演绎的第一步,但它表明,原则上可以将任意递归定义的表达自由纳入正式系统。
GANs承诺不区分,逻辑解释它。 我们把两者放在预算上:一个只能“看到”到逻辑深度k的判别器,以及一个必须看起来正确的生成器。 LOGAN(LOGical GANs)将鉴别器描绘成一个深度-k Ehrenfeucht-Fraïssé(EF)对手,搜索小的,可清晰的故障(奇怪的循环,非平面交叉,定向桥梁),而生成器播放生成器,产生允许k-round匹配目标理论T的样本。 我们推出了一个最小的工具包 - 一个EF探测器模拟器和MSO风格的图形检查器 - 以及四个实验,包括使用PyTorch进行真正的神经GAN训练。 除了验证之外,我们还对样本进行逻辑损失的评分,将预算的EF圆形弹性与便宜的证书条款混合,从而实现深度实践课程。 框架验证通过模拟演示了92%-98%的属性满意度(Exp. 3),虽然真正的神经GAN训练通过对抗性学习(Exp)在具有挑战性的属性上实现了5%-14%的改进和98%的连接(匹配模拟)的满意度。 4). LOGAN是一个紧凑的,可重复的走向逻辑边界生成的路径,具有可解释的失败,经过验证的有效性(模拟和真实的训练)以及用于控制的拨号盘。
继续滚动加载更多
