数理逻辑与可计算性

首先，我想为我的英语和我将在这个wiki上使用的名字道歉，因为他们中的许多人在书中可能有不同的名字(Guillermo Templado)。本维基的目的是研究普通逻辑或自然逻辑，使用数学方法或“数学逻辑”。这个wiki有3章和第0章:

第0章:导论(9节)
第一章:逻辑或微积分<一个target="_blank" rel="nofollow" href="//www.parkandroid.com/wiki/propositional-logic/">命题逻辑（6节)
第2章:一阶逻辑(11节)
第三章:可计算性(10节)

本wiki是J.桑乔·桑的书的摘要Román: Lógica matemática y computabilidad。在第三章中，我们将讨论<一个target="_blank" rel="nofollow" href="//www.parkandroid.com/wiki/turing-machines/">图灵机， Church的论文，和<一个target="_blank" rel="nofollow" href="https://en.wikipedia.org/wiki/Kurt_G%C3%B6del">库尔特Gödel的不完备性定理（使用<一个target="_blank" rel="nofollow" href="//www.parkandroid.com/wiki/lambda-calculus/">微积分），当然，我们会证明它们。很重要的一点是，我们会假设<一个target="_blank" rel="nofollow" href="//www.parkandroid.com/wiki/axiom-of-choice/">选择公理这相当于Zorn的引理(0.5章)，不过;然而，集合论中存在着不假设这个公理的逻辑。这不是必须的，但是抽象代数或群论的初级课程的知识会非常有用。

$\ \空间$ 所有章节都是相互联系的。必要时，本维基将在另一页继续。

内容

前言

数学逻辑是计算机构造和编程语言形成的基本工具。这个维基是为那些想要了解逻辑的精确概念和基本规则，或者这些规则背后的原因的人而写的。特别是，这些概念和规则将对所有从事逻辑编程(如PROLOG、LISP或人工智能专家系统)的人产生兴趣。

为了解这个维基你需要大量的时间，一遍又一遍地复习章节，不断地记忆，使用大量的普通逻辑。

简介

数学逻辑或符号逻辑是一门以数学方法研究普通逻辑或自然逻辑为主要任务的科学。普通逻辑或自然逻辑，基本上是由普通的语言和所述语言的句子序列被称为扣除．语言和演绎法是人类思维的基本工具，它奠定了今天所知的所有科学。

对现实生活中的任何事物的研究都是通过创建该事物的模型来完成的。为此，取一些元素，并选择一些属性。每个元素都由一个与之相似的理想实体表示，模型由这些理想实体(即模型的元素)和所选择的属性定义。

你能用数学方法研究普通逻辑吗?为了回答这个问题，我将抄录LUKASIEWICZ的几段话:

“哲学逻辑包括认识论问题:什么是真理?真理有什么标准吗?然而，这些问题不属于逻辑…如果我们从哲学逻辑中除去一切属于认识论、心理学和一般哲学的东西，我们所拥有的就是所谓的形式逻辑，内容合乎逻辑……没有两种逻辑，数学的和哲学的，只有一种逻辑，由亚里士多德创立，由斯多葛学派的旧学派完成，由中世纪逻辑学家以非常微妙的方式继续，这就是发展数学逻辑的逻辑"

第0章:前言

本章共9节，将会有一些没有证明的定理和例子。这并不意味着你不应该证明它。你总是要证明所有的一切，以获得对这个wiki的全部知识和理解。本章介绍了抽象代数第一课的许多“已知”概念，以及基数和可数集的概念。

1.集

任何对“集合”一词含义的解释都将使用比我们试图定义的更复杂的概念;然而，对于每个人赋予这个词的含义，我们或多或少都有一个清晰的概念，或足够的巧合。对我们来说，<一个target="_blank" rel="nofollow" href="//www.parkandroid.com/wiki/sets/">集是不同对象(元素)的定义良好的集合。

相关链接:<一个target="_blank" rel="nofollow" href="https://en.wikipedia.org/wiki/Set_(mathematics)">集

$a \in a$ 意味着 $一个$ 是 $一个$ ,即 $一个$ 属于 $一个$ ．

$a \notin$ 意味着 $一个$ 不是一个元素 $一个$ ,即 $一个$ 不属于 $一个$ ．

$A = b$ 意味着 $一个$ 而且 $b$ 都是一样的。

对我们来说,

$\mathbb{N} = \{0,1,2,3， \ldots \}$

$\ mathbb {N} ^ {+} = \ mathbb {Z }^{+} = \{ 1、2、3,\ ldots \}$

$\mathbb{Z} = \text{set of}$ 整型数字

$\mathbb{Q} = \text{set of}$ 有理数

$\mathbb{R} = \text{set of}$ 实数．

$\ \$ 2.命题符号与量词

“命题”是事件发生的表达。如果这真的发生了，这个命题就被认为是正确的;如果不是，就说它是假的。如果每当一个命题 $J$ 是真的，另一个 $K$ 也是真的，那么说呢 $J$ 意味着 $K。$ 在这种情况下， $J$ 是的充分条件吗 $K$ , $K$ 是必要的 $珍:$

$J \隐含k \四(\文本{逻辑含义})$

当不仅仅是 $J$ 意味着 $K$ ，但也 $K$ 意味着 $J$ ，据说命题 $J$ 而且 $K$ 逻辑上是等价的。那么事件 $J$ 的事件发生时且仅当 $K$ 发生:

$J \iff K. \quad(\文本{逻辑等价})$

命题“J =今天是星期二”和“K =明天是星期三”在逻辑上是等价的。

有更多的命题符号。我们稍后再看。有两个符号， $\存在$ 而且 $\原则$ ,被称为量词用于下列含义:

＂ $a中存在一个\，一个\文本{满足}P$ 意思是存在一个元素 $一个$ 属于集合 $一个$ 这样 $一个$ 满足属性 $P$ ．

＂ $对于a中所有的一个\，一个\文本{满足}P$ 意思是每一个元素 $一个$ 属于集合 $一个$ 满足属性 $P$ ．

$\ \$ 3.子集:交集和并集

集 $一个$ 是集合的子集吗 $E$ 如果的每个元素 $一个$ 属于 $E$ ．这是写 $A \subseteq$ ．

根据这个， $E \subseteq$ 但在这种情况下，包含并不严格。当 $A \subseteq$ ,但 $E$ 包含一个元素 $一个$ 这样 $a \notin$ ，即， $E$ ，包含严格和 $一个$ 是合适的子集吗 $E$ ．这是写 $A \子集E，\空间A \neq E$ ．请注意,

$(A \subseteq E \text{and} E \subseteq A) \iff A = E。$

对于下面的内容，您需要阅读<一个target="_blank" rel="nofollow" href="https://en.wikipedia.org/wiki/Set_(mathematics)">子集，<一个target="_blank" rel="nofollow" href="https://en.wikipedia.org/wiki/Set_(mathematics)">幂集，<一个target="_blank" rel="nofollow" href="https://en.wikipedia.org/wiki/Set_(mathematics)">联合，交集和补语．

一个集合的划分 $E \neq \emptyset$ 是一个集合 $F$ 的子集 $E$ ，无一空，这样每一个元素 $E$ 属于且仅属于的一个成员 $F$ ．的每个非空元素 $F$ 是一个分区的类的 $E$ ,也就是说, $E \neq \emptyset$ 的非空子集的不相交并集是 $E$ ，其中每个非空子集都是的元素 $F$ ．

等价关系 $\敌我识别$ 分区．我们将在本章的第5节看到这一点

$\ \$ 4.产品集

让 $E$ 而且 $G$ 两组，然后产品集这两组中的

$E \乘以G = \ {(a, b)在E \文本{/}\ \文本在G b{和}\ \}。$

注意，一般来说， $(a,b) eq (b,a)$ ，即这两个耦合的顺序是重要的。

用同样的方法，我们定义的乘积集 $n\， (n > 2 \in \mathbb{Z}^{+})$ 集,

$E_1 \乘以E_2 \ \ ldots \ * E_n = \ {(a_1,, \ ldots, an) {/} a_1 \ \文本在E_1, a₂\ E_2、\ ldots an在E_n \ \}。$

符号:如果 $E_i = E， \space \forall i =1，…n$ 时，乘积集为 $\括号{E \乘E \乘\cdots \乘E}_\text{n} = E^{n}。$

5.关系与秩序

让 $E$ 先一套，再一套 $n$ 必要的关系在 $E$ 是 $E ^ n。$

这个案子 $n = 2$ ,一个二元关系，尤其重要。

让 $R \subseteq E^2$ 中的二元关系 $E$ ，那么如果 $(a,b) \在R$ ，我们会写 $aRb$ ．

$\mathbb{N} = E$ ．然后 $B =\{(a, B) \in \mathbb{N}^2 \text{/} a < B \}$ 是否存在二元关系 $\ mathbb {N}$ ．根据这个关系式， $1 r4;$ 尽管如此, $5 r4$ 是不正确的，即。 $(5,4) \not tin B;$

二元关系 $R$ 在 $E$ 据说是一个自反关系如果对于每个元素 $a \in E$ 很满意 $aRa$ ．

据说 $R$ 是一个对称关系当 $aRb \暗示bRa$ ．

据说 $R$ 是一个传递关系当 $aRb \text{and} bRc \隐含aRc$ ．

据说 $R$ 是一个反对称的关系当 $aRb \text{and} bRa \隐含a = b$ ．

二元关系 $R$ 在 $E \neq \emptyset$ 据说是一个等价关系如果它具有自反、对称和传递关系。给定一个等价关系 $R$ 在 $E \neq \emptyset$ ，和一个元素 $一个$ 在 $E$ ， $[a] = \{b \in E \text{/} bRa\}$ 叫做等价类的 $一个。$

请注意, $A \in [A]$ ．等价类的集合表示为 $R \压裂{E} {}$ 它叫做商集由等价的类制成的 $R。$ 的等价类，如果一个人说话的等价关系是毫无疑问的 $一个$ ， $(一)$ ，有时表示为 $一个$ ．

让 $Z \ mathbb {}$ 是一组<一个target="_blank" rel="nofollow" href="//www.parkandroid.com/wiki/integers/">整型数字而且 $n \in \mathbb{Z}$ 那么，是一个固定的整数 $R = \{(a, b) \in \mathbb{Z}^2 \text{/} \exists m \in \mathbb{Z} \text{filling} n\cdot m = a - b\}$ 是一个等价关系 $R$ 在 $Z \ mathbb {}$ ．在这种情况下，

$R \ displaystyle \压裂{E}{} = \压裂{\ mathbb {Z}} {R} = \压裂{\ mathbb {Z}} {n \ mathbb {Z}} = \ mathbb {Z} _n”=大\ \{[0],[1],…， [n - 1]\大\}。$

看到<一个target="_blank" rel="nofollow" href="//www.parkandroid.com/wiki/quotient-group/">商集团： $Z \ mathbb {} _0 = \ mathbb Z}{\四\ mathbb {Z} _1 = \大\{[0]\大\}。$

集合中的每一个等价关系 $E \neq \emptyset$ 产生集合的分割 $E$ ，反过来，集合的每一个分区 $E \neq \emptyset$ 在集合中产生一个等价关系 $E$ ．

一个集合的一个分区 $E \neq \emptyset$ 在集合中产生一个等价关系 $E$ ，其中每个类的划分 $E$ 是类的等价吗 $E$ ．另一方面，集合中的等价关系 $E \neq \emptyset$ 产生集合的分割 $E$ ，因为每个元素 $a \in E$ 满足 $A \in [A]$ ，并给出了两类等价 $[一]、[b]$ 在 $E$ ，我们有两种可能:

$[a] \cap [b] = \emptyset，$ 或

$[a] \cap [b] \neq \emptyset \暗示\存在c \in [a]$ 而且 $C \in [b]$ ．

$\大(c \in [a] \隐含cRa \下撑{\隐含}_\文本{对称}aRc\大)$ 而且 $\大(c \in [b] \暗指cRb\大)\暗指$ $\大(aRc \text{and} cRb\大)\下括号{\隐含}_\text{传递性}aRb \隐含a \in [b] \隐含[a] \subseteq [b]$ ．

同样地， $B \in [a] \隐含[B] \subseteq [a]$ ．因此, $[a] = [b]$ ． $_ \广场$

二元关系 $R$ 在 $E \neq \emptyset$ 据说是一个偏序关系如果它具有反身、反对称和传递关系。在这种情况下， $E$ 据说是半序通过 $R$ ．

一个部分有序子集 $C$ 的 $E$ 是一个链，如果每两个元素 $C$ 满足 $aRb$ 或 $胸罩$ 的任意两个元素 $C$ 是类似的在这种情况下， $C$ 是完全命令与 $R$ ．

一个元素 $a \in E$ (部分有序集)称为最大如果对于每个元素 $x \in E$ 它满足以下条件: $aRx \隐含x = a。$

看到<一个target="_blank" rel="nofollow" href="//www.parkandroid.com/wiki/partially-ordered-set/">部分有序集而且<一个target="_blank" rel="nofollow" href="//www.parkandroid.com/wiki/combinatorial-optimization/">组合集基础．

动力装置 $\ mathbb {P} (E)$ 一组的 $E \neq \emptyset$ 部分有序集是否具有二元关系 $\ subseteq$ ,即 $I = \{(A, B) \text{/} A \subseteq E, B\ subseteq E \text{and} A \subseteq B\}$ 是否存在偏序关系 $E。$

佐恩引理

让 $X$ 是一个<一个href="//www.parkandroid.com/wiki/partially-ordered-set/" class="wiki_link" title="部分有序集＂target="_blank">部分有序集每条链都有 $X$ 有上限吗 $X。$ 然后 $X$ 包含一个最大值元素。

参见选择公理．这个引理无法被证明，这是我们自己的选择。你可以试着证明选择公理和佐恩引理之间的等价性，这需要一个“先进的机器”，或者换句话说，一个“深刻的逻辑思维”。

注:由于临时限制，本维基已被删节，全文将很快发布。

有关……

内容