句子 (数理逻辑)
在数理逻辑中，句子是没有自由变量的公式；在模型论中，一个句子在给定的数学结构中要么是真要么是假。 例如 :( \exists x)x^2=y 不是一个句子，因为出现了自由变量y；在实数的结构中，如果y=2则它是真，但是如果y=-2则不是。在另一方面 :(\forall y)(\exists x)x^2=y 是一个句子，但它在实数结构中是假。 参见 自由变量和约束变量 原子句子 *开放句子
标签：#數理邏輯
共 81 篇文章
量化 (数理逻辑)
在语言和逻辑中，量化是用量词指定一个谓词的有效性的广度的构造，就是说指定谓词在一定范围的事物上成立的程度。产生量化的语言元素叫做量词。结果的句子是量化的句子，我们称我们已经量化了这个谓词。量化在自然语言和形式语言中都使用。在自然语言中，量词的例子有“所有”、“某些”；“很多”、“少量”、“大量”也是量词。在形式语言中，量化是从旧公式产生新公式的公式构造子（constructor）。语言的语义指定了如何把这个构造子解释为一个有效性的广度。…
公理
在傳統邏輯中，公理（古希臘語: ἀξίωμα, 德語、英語: Axiom）是沒有經過證明，但被當作不證自明的一個命題。因此，其真實性被視為是理所當然的，且被當做演繹及推論其他（理論相關）事實的起點。當不斷要求證明時，因果關係毕竟不能無限地追溯，而需停止於無需證明的公理。通常公理都很簡單，且符合直覺，如「a+b=b+a」。 不同的系統，會預計不同的公理。例如非歐幾何的公理，和歐氏幾何的公理就有一點不同；另外，集合論的選擇公理在許多系統的建…
存在量化
在谓词逻辑中，存在量化是对论域内至少一个成员的性质或关系的论断。在符号逻辑中，存在量词「∃」是用来指示存在量化的符号。 它相对于声称某些谓词对所有事物都为真的全称量化。 基础 要表达“某些自然数自乘得25”这个命题，一种方式是： : 0 \times 0=25，或1 \times 1=25，或2 \times 2=25，或3 \times 3=25，以此类推。 因为使用了“或”一词，这看上去是逻辑析取。然而形式逻辑中的析取概念却不能表达…
塔斯基不可定義定理
塔斯基不可定義定理（），是由阿爾弗雷德·塔斯基在1936年給出並證明，是在數理邏輯、數學基礎及形式化語義方面的一個重要的限制結果。簡單來說：我們無法在算術系統中定義何謂「算術的真理」。從而這個定理可被推廣成適用於任何足夠強的形式系統，以表明：我們無法在系統中定義何謂「系統標準模型的真理」。 歷史 庫爾特·哥德爾在1931年發表了著名的哥德爾不完備定理，他一部分是透過一階算術的語義表達技巧來完成定理的證明。在他的算術語言中，每條表達式都配…
皮亚诺公理
皮亚诺公理（；），也称皮亚诺公设，是意大利数学家朱塞佩·皮亚诺提出的关于自然数的五条公理系统。根据这五条公理可以建立起一阶算术系统，也称皮亚诺算术系统。 内容 正确性，即排除与浅色不相关的深色骨牌的结构。]] 皮亚诺的这五条公理用非形式化方法叙述如下： 0是自然数； 每一个确定的自然数a，都有一个确定的后继数a' ，a' 也是自然数； 对于每个自然数b、c，b=c当且仅当b的后继数=c的后继数； 0不是任何自然数的后继数； 任意关于自然…
決定性問題
在可計算性理論與計算複雜性理論中，決定性問題，亦稱判定問題，（）是一個在某些形式系統回答「是」或「否」的問題。 舉例來說，「判定給定的自然數是否為質數」是一個決定性問題。另一個具體的例子是：「給兩個數字 x 與 y，x 是否可以整除 y？」，此問題依據其 x 與 y 的值可回答是或否。以演算法形式給出的解決決定性問題的方法稱為決策程式（）。對決定性問題「給兩個數字 x 與 y，x 是否可以整除 y？」決策程式將確定 x 是否整除 y。一…
模型论
模型论（）一般是指数学中集合论的论述角度对数学概念表现（representation）的研究，或者说是对于作为数学形式系统基础的“模型”的研究。粗略地说，该学科假定有一些既存的数学抽象对象(abstract objects)，然后研究：当这些对象之间的一些运算或者一些关系乃至一组公理被给定时，可以相应证明出什么，以及如何证明。 比如实数理论中一个模型论概念的例子是：我们从一个任意集合开始，作为集合元素的每个个体都是一个实数，其间有一些关…
数学基础
数学上，数学基础（）一词有时候用于数学的特定领域，例如数理逻辑，公理化集合论，证明论，模型论，和递归论（可計算性理論）。但是寻求数学的基础也是数学哲学的中心问题：在什么终极基础上命题可以称为“真”? 目前占统治地位的数学典範思想是基于公理化集合论和形式逻辑的。實際上，幾乎所有现在的数学定理都可以表述為集合论下的定理。在这个观点下，所謂数学命题的真实性，不过就是该命题可以从集合论公理使用形式逻辑推导出来。 这个形式化的方法不能解释一些问题…
後繼函數
数学中，後繼函數 或 後繼運算是使S(n)=n+1的原始递归函数S，其中n為自然数。例如， S(1)=2， S(2)=3。后继函數也称为zeration，因為它是第零个超運算：H_0(a,\ b)=1+b。zeration的推广是加法，加法可看做反复进行一定次数的后继运算。 概述 后繼函数被用在定义自然数的皮亚诺公理，皮亚诺公理形式化了自然数的结构，当中后继函数是自然数上的一种原始运算，定义所有大於0的自然数和加法。例如，1被定义为 S…
真值表
真值表是使用於邏輯中（特別是在連結邏輯代數、布林函數和命題邏輯上）的一類數學用表，用來計算邏輯表示式在每種論證（即每種邏輯變數取值的組合）上的值。尤其是，真值表可以用來判斷一個命題表示式是否對所有允許的輸入值皆為真，亦即是否為邏輯有效的。 「用真值表製表的推理模式是由弗雷格、查尔斯·皮尔士和恩斯特·施羅德於1880年代所发明的。這種表格於1920年代之後廣泛地發現在許多文獻上（扬·武卡谢维奇、埃米爾·波斯特、维特根斯坦）”（蒯因, 39…
递归定义
递归定义是数理逻辑和计算机科学用到的一种定义方式，使用被定义对象的自身来为其下定义（简单说就是自我复制的定义）。递归定义与归纳定义类似，但也有不同之处。递归定义中使用被定义对象自身来定义，而归纳定义是使用被定义对象的已经定义的部分来定义尚未定义的部分。不过，使用递归定义的函数或集合，它们的性质可以用数学归纳法，通过递归定义的内容来证明。 定义方式 大部分的递归定义都由三个部分构成：基本情况的定义，递归法则和递归结束的情况。如果定义的对象…
前束范式
在谓词演算中，如果一个公式可以被写为量词在前，被称为母体的无量词部分在后的形式，则称其为前束范式的，所有经典逻辑公式都逻辑等价于某个前束范式公式。 可以用公式在如下重写规则下的逻辑等价来证实： :\forall x ( P(x) ) \land Q \equiv \forall x ( P(x) \land Q ) :\forall x ( P(x) ) \lor Q \equiv \forall x ( P(x) \lor Q ) :…
类型论
類型論，數學、邏輯和電腦科學以下的一個分支，是研究不同類型系統及其表達形式的學科。某些類型系統適合用作數學基礎，取代數學家一般使用的集合論，其中最具影響力的有阿隆佐·邱奇的有類型λ演算和佩爾·馬丁-洛夫的直覺類型論。許多函式語言和工具都建立在類型論的基礎上，如Agda、Coq、Idris、Lean等等。 類型論的核心概念是，每一條合乎語法規則的表達式（或稱「项」）都有其所屬的「類型」。通過結合多個基礎類型，可以定義更加複雜的類型。如此得…
实质条件
A \rightarrow B]] 在命题演算，或在数学的逻辑演算中，实质条件、實質蘊涵或蕴涵算子是一种二元的真值泛函的逻辑运算符，它有着如下形式： :若A，則B。 这裡的A和B是陈述变量（可以被语言中任何有意义的可表示的句子所替代）。在这种形式的陈述中，第一项这裡的A，叫做前件；第二项这裡的B，叫做后件。 这个算子使用右箭头“→”（有时用符号“⇒”或“⊃”）来符号化，其語義僅爲“如果A為真，那么B亦為真”。它的常見寫法見下： A \t…
可靠性定理
可靠性定理是数理逻辑的最基本结果。它们有关于某个形式逻辑语言与这个语言的形式演绎系统的特定语义理论。可靠性定理有两种主要变体：弱可靠性的和强可靠性的。“强”与“弱”的意义在于，强可靠性考虑句子的任意集合，而与弱可靠性有关的句子的空集是这种集合之一。大多数的演绎系统，强可靠性和弱可靠性都成立，但並非全部的演繹系統都如此。 論證可靠性 邏輯論證可靠若且唯若 論證有效。 所有前提皆已被證實為真。 弱可靠性定理 演绎系统的弱可靠性定理声称，在这…
重写逻辑
在数学、计算机科学和逻辑学中，重写逻辑是把目标逻辑的抽象语法替换为代数结构，通过用其他术语表示公式子项的各种实现方法。利用重写规则，目标逻辑的推理规则可以被描述出来。 重写逻辑中的结构化公理和语法都由用户自己定义，这使其变得极为简单且通用。在最基本的形式中，一种重写的规则可适用多个规则。因此，当与适当的算法结合时，重写系统被视为绝大多数编程语言和系统应用程序进行规范描述的计算机逻辑，许多定理证明和宣告式编程语言是基于重写的。 1992年…
递归论
递归论或可计算性理论，是一个数理逻辑分支。它起源于可计算函数和图灵度的研究。它的领域增长为包括一般性的可计算性和可定义性的研究。在这些领域中，这门理论同证明论和能行描述集合论（effective descriptive set theory）有所重叠。 数理逻辑中的可计算性理论家经常研究相对可计算性、可归约性概念和程度结构的理论。相对于计算机科学家，他们研究次递归层次，可行的计算和公用于可计算性理论研究的形式语言。在这两个社区之间有着相…
字元集 (數理邏輯)
字元集在不同領域中有不同意義。在邏輯學（特別是數理邏輯中）代表的是列舉出形式語言中的一組集合；在泛代數中則是列舉出代數結構具代表性的運算。另外，在模型論中兩種用法皆有使用。 對邏輯學更哲學性的討論中，字元集的概念較少被提及。 定義 一個（單域）字元集在形式上定義為四元組 \sigma = \left(S_{\operatorname{func}}, S_{\operatorname{rel}}, S_{\operatorname{con…
相等
在數學的領域中，若兩個数学对象在各个方面都相同，则称他们是相等的。这就定义了一个二元谓词等于，写作“=”；x=y当且仅当x和y相等。通常意义上，等于是通过两个元素间的等价关系来构造的。将两个表达式用等于符号连起来，就构成了等式，例如6-2=4，即6-2與4是相等的。 注意，有些时候“A=B”并不表示等式。例如，T(n)=O(n^2)表示在数量级n^2上渐进。因為这裡的符号“=”不滿足若且唯若的定義，所以它不等於等于符号；实际上，O(n^…