数理逻辑基础¶
逻辑简介¶
数理逻辑(Mathematical logic)研究的是证明过程的逻辑。
数理逻辑是数学的基础。
命题逻辑¶
命题¶
命题(proposition)，指的是一个可以判断正确或错误（真(True)与假(False)）的陈述句。命题讲述一个事情，不可以同时正确和错误，也不可以既不正确也不错误（这也就是排中律(Law of excluded middle)）。
命题可以纯粹由数学符号构成，也可以由自然语言（如汉语或英语）构成。大多数情况下，命题由自然语言和数学符号混合写成。
以下是命题举例：
- \(1+1=2.\)
- \(2|4.\)（2是4的因数）
- 分子不停地做无规则的热运动。
- Michael's personal computer runs Linux.
以下的例子不是命题：
- 作以\(O\)为圆心，半径\(r=1\)的圆。
- 球往平面上的投影是圆吗？
- \(x+2=4.\)
在上面的例子中，前两条都没有在陈述一个事情，而第三条则是无法判断正误，它们都不是命题。
正确和错误的命题，分别称为真命题和假命题。
命题可以用字母表示，如\(p,q,r,s\)等。
而真命题和假命题则一般用字母\(\mathbf T\)和\(\mathbf F\)表示。
逻辑连接词¶
否定，非(NOT)¶
非(NOT)将一个命题否定(negation)，也就是取一个命题的相反情况。
我们用符号\(\neg p\)表示命题\(p\)的否定，通常读作“非\(p\)”(not p)。
例如：
的否定是
非的真值表(Truth table)如下：
| \(p\) | \(\neg p\) |
|---|---|
| T | F |
| F | T |
合取，与(且，AND)¶
两个命题的合取(conjunction)，指的是用与(数学中也作且，AND)连接的两个命题。当两个命题都是真命题时，它们的合取才是真命题，其他情况都是假命题就。
两个命题\(p,q\)的合取记作\(p\land q\)，读作\(p\)且\(q\)（\(p\) and \(q\)）。
例如，命题\(p:\)“12是3的倍数”和\(q:\)“12是4的倍数”的合取是：
或者等价地表述为“12是3和4的因数”，用数学符号表示为：\((3|12) \land (4|12)\)。
与的真值表如下：
| \(p\) | \(q\) | \(p\land q\) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
析取，或(OR)¶
两个命题的析取(disjunction)，指的是用或(OR)连接的两个命题。当两个命题的合取是假命题时，它们的析取才是假命题，其他情况都是真命题。
两个命题\(p,q\)的析取记作\(p\vee q\)，读作\(p\)或\(q\)（\(p\) or \(q\)）。
例如，命题
或的真值表如下：
| \(p\) | \(q\) | \(p\vee q\) |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
条件关系¶
条件和条件命题¶
在数理逻辑中，条件关系也是一种逻辑关系，指的是像“如果\(p\)，那么\(q\)”(If \(p\), then \(q\))这样的命题。这个句子也是条件关系的一种典型表述。
对于条件命题“如果\(p\)，那么\(q\)”，我们也用 \(p\rightarrow q\) 或 \(p\Rightarrow q\) 表示，通常读作“\(p\)推出\(q\)”。其中，\(p\) 称为条件，\(q\) 称为结论。
条件关系还有其他的表述方法，例如“若 \(p\)，则 \(q\)”，“\(q\) 仅当 \(p\)”等。
条件关系中，只有当\(p\)为真且\(q\)为假时，\(p\to q\) 才为假。我们看几个例子，来理解为何这样定义条件命题的真假性。
Example
\(p:\) 明天下雨，\(q:\) 我们不去打球,
\(p \to q:\) 如果明天下雨，我们就不去打球。
在这个例子中，如果第二天真的下雨了，我们还要冒雨打球的话，说明我们昨天“撒了谎”，原命题是假命题；只有第二天我们不去打球，原命题才是真命题。
但如果第二天没有下雨，此时我们无论去打球，还是不去打球，都不算“撒谎”，因为命题的前提“下雨”没有成立。注意到我们认为排中律成立，如果这个命题“不是错误”，那么它就是“正确”的。这说明，当条件不成立时，无论结论是否成立，条件命题都是真命题。
我们再看看数学中的例子：
Example
如果一个整数是大于2的质数，那么这个数是奇数。
这句话说明，大于2的质数都是奇数。但是，如果一个整数不是“大于2的质数”，那么这个数可能是奇数，也可能不是奇数。例如8和9都是大于2的合数，但9是奇数，而8是偶数。
因此，条件命题只有当“条件为真且结论为假”时才是假命题。我们可以总结条件关系的真值表如下：
| \(p\) | \(q\) | \(p \to q\) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
等价关系，同或¶
等价命题，字面上看就是“两个命题等价”，也就是“两个命题可以相互替换”这个命题。而严格来说，“两个命题等价”指的是，“命题1可以推出命题2，且命题2也可以推出命题1”。
\(p,q\)的等价关系记作\(p \leftrightarrow q\)或\(p \Leftrightarrow q\)。根据上面的定义，\(p \leftrightarrow q\)指的是\((p \to q)\land(q \to p)\)。
\(p \leftrightarrow q\)也通常表述为：“\(p\)当且仅当\(q\)”(if and only if，简写\(p\) iff \(q\))等。