列举法 (集合论)
列举法是集合论（或者类的理论）中表示集合（或类）的一种方法。 如果已知集合（或类）的每一个元素，而且元素个数“相当有限”，我们可以通过“列举”其所有元素的方法来表示这个，如：{1,2,3}、{a}、{A,B,C,D,E}等。一对花括号“{ }”是集合（或类）表示法的特征符号。 如果集合（或类）的元素有“很多”甚至“无限多”以至于很难或无法将其所有元素一一列出，但其元素又具有很明显的“规律”，可以用“…”略过规律性比较明显的大量元素，如用…
标签：#數理邏輯
共 81 篇文章
哥德尔不完备定理
哥德尔不完备定理（）是数理逻辑中的两条定理，探讨了形式化公理系统中可证明性的局限性。这些结果由库尔特·哥德尔于1931年发表，在数理逻辑和数学哲学领域都具有重要意义。人们普遍认为，这些定理表明希尔伯特计划——即为所有数学寻找一套完备且一致的公理系统——是不可能实现的。 第一定理指出： 这是形式逻辑中的定理，容易被错误表述。有许多命题听起来很像是哥德尔不完备定理，但事实上并不是。具体实例见对哥德尔定理的误解。 把第一条定理的证明过程在系统…
演绎推理
演绎推理（）、正向推理在传统的亚里士多德逻辑中是「结论，可从叫做‘前提’的已知事实，‘必然地’得出的推理」。如果前提为真，则结论必然为真。这区别于溯因推理和归纳推理：它们的前提可以预测出高概率的结论，但是不确保结论为真。 “演绎推理”还可以定义为结论在普遍性上不大于前提的推理，或「结论在确定性上，同前提一样」的推理。 例子 任何三角形只可能是锐角三角形、直角三角形和钝角三角形。——大前提 这个三角形既不是锐角三角形，也不是钝角三角形。—…
证明论
证明论是数理逻辑的一个分支，它将数学证明表达为形式化的数学客体，从而通过数学技术来简化对他们的分析。证明通常用归纳式地定义的数据结构来表达，例如链表，盒链表，或者树，它们根据逻辑系统的公理和推理规则构造。因此，证明论本质上是语法逻辑，和本质上是语义学的模型论形相反。和模型论，公理化集合论，以及递归论一起，证明论被称为数学基础的四大支柱之一。 证明论也可视为哲学逻辑的分支，其主要兴趣在于证明论语义学的思想，该思想依赖于结构证明论的技术型想…
谓词逻辑
在数理逻辑中，谓词逻辑（）是符号形式系统的通用术语，比如一阶逻辑，二阶逻辑、多类逻辑或无穷逻辑等等。 参考文献 A. G. Hamilton (1978). Logic for Mathematicians. Cambridge, England: Cambridge University Press. ISBN 0-521-21838-1. Abram Aronovic Stolyar (1970). Introduction to …
公式 (数理逻辑)
在数理逻辑中，公式是 公式精确定义依赖于涉及到的特定的形式逻辑，但有如下一个非常典型的定义（特定于一阶逻辑）：公式是相对于特定语言而定义的；就是说，一组常量符号、函数符号和关系符号，这里的每个函数和关系符号都带有一个元数（arity）来指示它所接受的参数的数目。 定义 项的递归定义 一个变量 或 一个常量符号 或 f(t_1,...,t_n)\,，这里的f\,是一个n-元函数符号，而t_1,...,t_n\,是项。 公式的递归定义 t_…
命题
在逻辑学、哲学、语言学中，命题（）是一个陈述句所表达的判断，具有真值，即不是真的就是假的。例如，“雪是白色的”。命题不等同于句子，例如，“雪是白色的”和“白色是雪的颜色”是不同的句子，但它们判断相同的事，是相同的命题；同时，命题也不依赖于语言，不同的语言可以表达相同的命题，例如，“雪是白的”和“Snow is white”是相同的判断。疑问句、祈使句、感叹句都不能表达命题。 由其他命题推出命题（前提推出结论）的过程，叫做推论；而这些作为…
一致性 (邏輯)
邏輯上，一致理论（consistent theory）、相容理论、自洽理论，是指不蘊涵矛盾的理论。在大部分逻辑系统中，不一致理论总是蕴含所有命题，因此不大有用。 一致理论是语法上的概念；与此对应的语义上的概念是理论，即具有模型的理论。由可靠性定理和哥德尔完备性定理，一阶逻辑理论是一致的当且仅当它是可满足的。 能够编码皮亚诺算术的递归可枚举理论（如皮亚诺算术、策梅洛-弗兰克尔集合论）的一致性只能被不弱于它的某个理论证明；参见哥德尔不完备定…
命题逻辑
命题逻辑是逻辑学的一个分支。 它也称为命題演算、句子演算、句子逻辑，有时也称为零阶逻辑。它涉及命题（可以是真或假）和命题之间的关系，包括基于它们的论证的构建。复合命题是通过逻辑连接词连接命题而形成的。不包含逻辑连接词的命题称为原子命题。 与一阶逻辑不同，命题逻辑不处理非逻辑对象、以及关于它们的谓词或量词。然而，命题逻辑的所有机制都包含在一阶逻辑和高阶逻辑中。从这个意义上说，命题逻辑是一阶逻辑和高阶逻辑的基础。 在邏輯和數學裡， 命题逻辑…
谢费尔竖线
A | B]] 谢费尔竖线（），得名于，写为“| ”（見豎線）或“↑”，指示等价于合取运算的否定的逻辑运算。普通语言表达为“不全是即真”（Not AND，因此也常縮寫為NAND），也就是说，A | B假，当且仅当A与B都真时才成立。它是可用来表达与命题逻辑有关的所有布尔函数的自足算子之一。在布尔代数和数字电子中有叫做「NAND」的等价运算。 定义 谢费尔竖线“|”等价于逻辑与的否定： : A | B = \neg(A \wedge B)…
元逻辑
元逻辑（）是逻辑的元理论。逻辑研究如何使用逻辑系统构建有效且可靠的论证，而元逻辑研究逻辑系统本身的属性。逻辑关注可以由逻辑系统推导出的真理；元逻辑关注关于用于表达真理的形式语言和系统所能推导出的真理。 基本概念 形式语言 形式语言是由精确定义的符号组成的集合，其符号通过形状和位置精确界定。这种语言可以在不涉及表达式意义的情况下定义。一阶逻辑即用某种形式语言来表达。形式文法确定哪些符号和符号串构成公式。然而，直到19世纪末20世纪初形式语…
真值语义
在逻辑的语义中，真值语义是对 Tarski主义语义的一种替代选择。它主要由 Ruth Barcan Marcus、H. Leblanc、M. Dunn 和 N. Belnap 所拥戴。它也叫做(量词的)代换释义或代换量化。 Beth 的一个定理声称，在模型中一个域内所有成员除了那些被指派给常量的都可以被折消，假定了全称量词(存在量词)可以被读做公式的合取(析取)，其中常量替代在量词作用域内的变量的想法。比如，∀xPx 可以读做 (Pa …
變數
在数学、物理学中，变数（）又称-{zh-cn:变数;zh-tw:變量;zh-hk:變數}-，是表達式或公式中，没有固定的值而可以变动的数或量；該数或量可以是隨意的，也可能是未指定或未定的。表示变数的字母，统称为变元、元，即变元是一个用来表示值的符号。在初等數學中，也以未知数、未知量代称变数。 在语-{}-义上，变-{}-数（变-{}-量）相对于常数（常-{}-量）。变-{}-数（量）强调因果与依存关系；一个（自变）变了，另一个（因变）跟…
停机问题
停机问题（）是逻辑数学中可计算性理论的一个问题。通俗地说，停机问题就是判断任意一个程序是否能在有限的时间之内结束运行的问题。该问题等价于如下的判定问题：是否存在一个程序P，对于任意输入的程序w，能够判断w会在有限时间内结束或者死循环。 艾伦·图灵在1936年用對角論證法证明了，不存在解决停机问题的通用算法。这个证明的关键在于对计算机和程序的数学定义，这被称为图灵机。停机问题在图灵机上是不可判定问题。这是最早提出的决定性问题之一。 用数学…
謂詞 (邏輯)
在数理逻辑中，謂詞（predicate）是一個表示性質或是關係的符號。例如在一阶逻辑 P(a)裡，符號P是謂詞 ，作用在a上。在公式R(a,b)中，符號 R是謂詞，作用在個體常元a和b上。 依照戈特洛布·弗雷格，謂詞的意義是一個函數，其定義域是物件，其值域則是真值，真或是假。 在邏輯語義學中，謂詞會詮釋為關係。例如在一階邏輯的標準語義中，若a和b表示的物件之間有R表示的關係，則R公式R(a,b)會解釋為真。因為謂詞是，可以依詮釋而表示不…
递归
是递归的一种视觉形式。图中女性手持的物体中有一幅她本人手持同一物体的小图片，进而小图片中还有更小的一幅她手持同一物体的图片，依此类推。]] 递归（），又译为-{zh-cn:递回; zh-tw:遞歸; zh-hk:遞迴;}-，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。例如，当两面镜子相互之间近似平行时，镜中嵌套的图像是以无限递归的形式出现的。也可以理解为自我复制的过程。 …
逆数学
逆数学（Reverse mathematics）是数学的一个分支，大致可以看成是“从定理导向公理”而不是通常的方向(从公理到定理)。更精确一点，它试图通过找出证明所需的充分和必要的公理来评价一批常用数学结果的逻辑有效性。 该领域由Harvey Friedman在其文章“二阶算术系统及其应用（Some systems of second order arithmetic and their use）”中创立。它被Stephen G. Si…
克魯斯卡爾樹定理
TREE函數與克魯斯卡爾樹定理（）是逆數學中極具代表性的例子。該定理最早由提出猜想，隨後由約瑟夫·克魯斯卡爾給出證明。 在數學上，克魯斯卡爾樹定理指出：如果一個標籤集合本身具備，那麼由這些標籤構成的所有有限樹的集合，在同胚嵌入的意義下，也同樣具備良準序。 歷史 如前所述，該定理由安德魯·瓦茲尼提出猜想，並於1960年由證明；隨後在1963年，給出了一個更為簡潔的證明。此後，它成為了逆數學領域的經典案例——人們發現該定理無法在 ATR0（…
一阶逻辑
一阶逻辑是使用於数学、哲学、语言学及電腦科學中的一种形式系统，也可以稱為：一阶斷言演算、低階斷言演算、量化理論或谓词逻辑。一階邏輯和命題邏輯的不同之處在於，一階邏輯包含量詞。 高階邏輯和一階邏輯不同之處在於，高階邏輯的斷言符號可以有斷言符號或函數符號當做引數，且容許斷言量詞或函數量詞。在一階邏輯的語義中，斷言被解釋為關係。而高階邏輯的語義裡，斷言則會被解釋為集合的集合。 在通常的語義下，一階邏輯是可靠（所有可證的敘述皆為真）且完備（所有…
形式文法
在形式语言理论中，文法（formal grammar)是形式语言中字符串的一套产生式规则（production rule）。这些规则描述了如何用语言的字母表生成符合句法(syntax)的有效的字符串。文法不描述字符串的含义，也不描述在任何上下文中可以用它们做什么——只描述它们的形式。 形式语言理论是应用数学的一个分支，是研究形式文法和语言的学科。它在理論計算機科學、理论语言学、形式语义学、数理逻辑等领域有着广泛的应用。 形式文法是从一个…