查看“︁逻辑”︁的源代码

数理逻辑研究数学陈述的形式、推理规则以及证明与模型之间的关系。命题逻辑处理陈述之间的连接，一阶逻辑进一步使用变量、量词和关系描述对象。逻辑的作用是把“结论为什么跟随前提成立”说清楚。

== 命题与连接词 ==
命题是具有确定真值的陈述。“2 是偶数”为真命题；“x 是偶数”在没有给定 <math>x</math> 或量词时是含自由变量的谓词，不能直接作为确定真假的封闭命题。

常见连接词为否定 <math>\neg P</math>、合取 <math>P\land Q</math>、析取 <math>P\lor Q</math> 与蕴含 <math>P\Rightarrow Q</math>。普通逻辑中的析取允许两者同时为真。

{| class="wikitable"
! P !! Q !! P∧Q !! P∨Q !! P⇒Q
|-
| 真 || 真 || 真 || 真 || 真
|-
| 真 || 假 || 假 || 真 || 假
|-
| 假 || 真 || 假 || 真 || 真
|-
| 假 || 假 || 假 || 假 || 真
|}
蕴含只在“前提真、结论假”时为假。它表达真值之间的约束，并不自动表示因果关系；前提为假时蕴含为真，也不能由此断定结论本身为真。

== 必要条件、充分条件与逆否命题 ==
若 <math>P\Rightarrow Q</math>，则 <math>P</math> 是 <math>Q</math> 的充分条件，<math>Q</math> 是 <math>P</math> 的必要条件。例如“整数能被 4 整除”足以推出“整数是偶数”，反向却不成立，6 就是反例。

[[File:Gezhi-logic-subsets.svg|frame|center|alt=能被四整除的整数集合包含在偶数集合中，偶数集合又包含在整数集合中，六位于内圈之外|集合包含关系解释蕴含：所有满足强条件的对象都满足弱条件，但弱条件可能包括额外对象。]]
蕴含与逆否命题等价：
<math display="block">(P\Rightarrow Q)\ \Longleftrightarrow\ (\neg Q\Rightarrow\neg P).</math>
它通常不等价于逆命题 <math>Q\Rightarrow P</math>。若两个方向都成立，才写作 <math>P\Leftrightarrow Q</math>，称为充要条件。

== 量词顺序不能随意交换 ==
<math>\forall</math> 表示“对所有”，<math>\exists</math> 表示“存在”。例如在实数范围内，
<math display="block">\forall x\ \exists y\ (y>x)</math>
为真，因为对每个 <math>x</math> 可选择 <math>y=x+1</math>。交换后
<math display="block">\exists y\ \forall x\ (y>x)</math>
却为假，它要求找到一个比所有实数都大的固定实数。前者允许 <math>y</math> 依赖 <math>x</math>，后者不允许。

这正是[[极限]]定义中“任给误差，存在足够小的邻域”的核心：邻域可以依赖误差，而不是预先选好同一个邻域应对一切误差。

== 怎样正确否定一句话 ==
否定全称命题得到存在反例；否定存在命题得到全部不成立：
<math display="block">\neg(\forall x\,P(x))\Leftrightarrow\exists x\,\neg P(x),\qquad\neg(\exists x\,P(x))\Leftrightarrow\forall x\,\neg P(x).</math>
“所有整数都是偶数”的否定是“存在一个整数不是偶数”，不是“所有整数都不是偶数”。对于复合语句，德摩根律给出 <math>\neg(P\land Q)\Leftrightarrow\neg P\lor\neg Q</math>。

== 证明与反例承担不同任务 ==
全称命题不能靠检查有限个普通例子证明，却可以被一个满足前提、违反结论的反例推翻。例如“所有素数都是奇数”被 2 推翻。

直接证明从假设按有效规则推出结论；逆否证明转而证明等价的逆否命题；反证法假设所求结论的否定并导出矛盾。数学归纳法则需要同时给出初始情形和从 <math>n</math> 到 <math>n+1</math> 的一般推理，仅检查前几项并不构成归纳证明。

本条使用经典逻辑。形式证明保证结论跟随前提，但现实建模中前提是否符合实际，还需要定义、观测和验证。

== 延伸阅读 ==
* [https://discrete.openmathbooks.org/dmoi3.html Oscar Levin，《Discrete Mathematics: An Open Introduction》第 0、3 章]：量词、逻辑与证明。
* [[极限]] · [[组合数学]] · [[数学建模]]
[[分类:离散数学]]