上一页

ⓘ Category:數理邏輯




                                               

公式 (数理逻辑)

在数理逻辑中, 公式 是表达命题的形式语法对象,除了这个命题可能依赖于这个公式的自由变量的值之外。 公式精确定义依赖于涉及到的特定的形式逻辑,但有如下一个非常典型的定义(特定于一阶逻辑):公式是相对于特定语言而定义的;就是说,一组 常量符号 、 函数符号 和 关系符号 ,这里的每个函数和关系符号都带有一个元数(arity)来指示它所接受的参数的数目。

                                               

哥德尔不完备定理

在数理逻辑中, 哥德尔不完备定理 是库尔特 哥德尔于1931年证明并发表的两条定理。简单地说,第一条定理指出: 这是形式逻辑中的定理,容易被错误表述。有许多命题听起来很像是哥德尔不完备定理,但事实上并不是。具体实例见对哥德尔定理的误解 把第一条定理的证明过程在体系内部形式化后,哥德尔证明了第二条定理。该定理指出: 哥德尔不完备定理破坏了希尔伯特计划的哲学企图。大卫 希尔伯特提出,像实分析那样较为复杂的体系的相容性,可以用较为简单的体系中的手段来证明。最终,全部数学的相容性都可以归结为基本算术的相容性。但哥德尔的第二条定理证明了基本算术的相容性不能在自身内部证明,因此当然就不能用来证明比它更强的系统的 ...

                                               

哥德尔完备性定理

哥德尔完备性定理 是数理逻辑中重要的定理,在1929年由库尔特 哥德尔首先证明。它的最熟知的形式声称在一阶谓词演算中所有逻辑上有效的公式都是可以证明的。 上述词语" 可证明的”意味着有着这个公式的形式演绎。这种形式演绎是步骤的有限列表,其中每个步骤要么涉及公理要么通过基本推理规则从前面的步骤获得。给定这样一种演绎,它的每个步骤的正确性可以在算法上检验(比如通过计算机或手工)。 如果一个公式在这个公式的语言的所有模型中都为真,它就被称为" 逻辑上有效”的。为了形式的陈述哥德尔完备性定理,你必须定义这个上下文中词语" 模型”的意义。这是模型论的基本定义。 在另一个方向上,哥德尔完备性定理声称一阶谓词演算的推理规 ...

                                               

哥德尔数

在形式数论中, 哥德尔编号 是对某些形式语言的每个符号和公式指派一个叫做 哥德尔数 的唯一的自然数的函数。这个概念是哥德尔为证明他的哥德尔不完备定理而引入的。 可计算函数集合的编号有时叫做哥德尔编号或有效编号。哥德尔编号可以被解释为一个编程语言,带有指派哥德尔数到每个可计算函数作为在这种编程语言中计算这个函数的值的程序。Roger 等价定理特征化了是哥德尔编号的可计算函数集合的编号。

                                               

合式公式

在形式系統與逻辑中, WFF 是 合式公式 (well-formed formula)的缩写。给定一个形式文法,WFF是这个文法生成的任何字符串。 例如,在命题演算中符号序列 α → β → ¬ β → ¬ α) {\displaystyle \alpha \rightarrow \beta\rightarrow \neg \beta \rightarrow \neg \alpha)} 是一个WFF,因为它在文法上正确。符号序列 α → β → β β) α) {\displaystyle \alpha \rightarrow \beta\rightarrow \beta \beta)\alpha)} 不是WFF,因为它不符合命题演算的文法。 在形式逻辑中,证明是有特定性质的WFF序列,而序列中最终的WFF就是要证明的。

                                               

決定性問題

在可計算性理論與計算複雜性理論中,所謂的 決定性問題 ( Decision problem )是一個在某些形式系統回答 是或否 的問題。例如: 「給兩個數字x與y,x是否可以整除y?」 便是決定性問題,此問題可回答是或否,且依據其x與y的值。 決定性問題與功能性問題( Function problem ,或複雜型問題)密切相關,功能性問題的答案內容,較簡單的是與非複雜許多。範例問題:「給予一個正整數x,則哪些數可整除x?」 另一個與上述兩類問題相關的是最佳化問題( Optimization problem ),此問題關心的是尋找特定問題的最佳答案。 解決決定性問題的方法稱為 決策程式 或演算法。一個針對決定性問題的演算法將說明給予參數x和y的情況下如何決定x是否整除y ...

                                               

可靠性定理

可靠性定理 (或 健全性 )是数理逻辑的最基本结果。它们有关于某个形式逻辑语言与这个语言的形式演绎系统的特定语义理论。可靠性定理有两种主要变体:弱可靠性的和强可靠性的。" 强”与" 弱”的意义在于,强可靠性考虑句子的任意集合,而与弱可靠性有关的句子的空集是这种集合之一。大多数的演绎系统,强可靠性和弱可靠性都成立,但並非全部的演繹系統都如此。

                                               

开放句子

开放句子 是「在用特定的数,替代其中的变量的时候,将使得结果的表达式被求值为真的一个句子」。 数学家没有接受这种术语,而是称之为带有自由变量的 方程式 或 不等式 等。 这种替代也叫做对句子的 解 。 恒等式 是所有数都是解的开放句子。 开放句子的例子包括: x 2 + 7 > 0, x 的解是所有實數。例子4是恒等式。例子1、3、4和5是方程式,而例子2和6是不等式。 4 x + 3 > 9, x 的解是所有大于3/2的数; 5 x + 8 = 5x + 5, x 無解。 x + y = 0, x 和 y 的解是所有加法互逆的所有数的有序对; 3 x + 9 = 3x + 3, x 的解是所有数。 3 x − 9 = 21, x 的唯一解是10; 所有开放句子都必须(通常暗含的)有描述那些数可被当作解的 论域 。 ...

                                               

类型论

在最广泛的层面上, 类型论 (英語: type theory )是关注把实体分类到叫做类型的搜集中的数学和逻辑分支。在这种意义上,它与类型的形而上学概念有关。现代类型论在部分上是响应罗素悖论而发明的,并在伯特兰 罗素和阿弗烈 诺夫 怀海德的中起到重要作用。 在计算机科学分支中的编程语言理论中, 类型论 提供了设计分析和研究类型系统的形式基础。实际上,很多计算机科学家使用术语" 类型论”来称呼对编程语言的类型语言的形式研究,尽管有些人把它限制于对更加抽象的形式化如有类型lambda演算的研究。

                                               

逻辑等价

在逻辑中,陈述 p 和 q 是 逻辑等价 的,如果它们有相同的逻辑内容。 p 和 q 是语法等价的,如果每个都可以证明自另一个。 p 和 q 是语义等价的,如果它们在所有模型中有相同的真值。 逻辑等价经常混淆于实质等价。前者是在元语言中的一个陈述,断言关于目标语言中的陈述 p 和 q 的某个事情。而 p 和 q 的实质等价(常写为" p ↔ q ")自身是在目标语言中另一个陈述。但它们是有联系的, p 和 q 是语法等价的,当且仅当 p ↔ q 是一个定理,而 p 和 q 是语义等价的,当且仅当 p ↔ q 是重言式。 逻辑等价有时表示为 p ≡ q 或 p ⇔ q 。但是,后者记号也用于实质等价。

用户还搜索了:

...
...
...