逻辑

逻辑是数学思维的根基，它为我们提供了从已知推演未知、分辨真假的普遍法则。

参考资料

• 逻辑 - 维基百科

命题

定义

在初中阶段，我们已经对 命题 有了初步的认识。

《人教版高中数学·必修一》：一般地，我们把用语言、符号或式子表达的，可以判断真假的陈述句 叫做命题。判断为真的语句是真命题，判断为假的语句是假命题。

命题通常用 $p,q$ 等小写字母表示。

引入

我们从生活中的一个示例开始。

假设 你被 XX 大学录取 需要同时满足 $3$ 个条件：

1. 完成高中学业；
2. SAT $\ge1400$ 分；
3. TOEFL $\ge100$ 分。

简单命题

我们称只包含一个判断，不能再分的命题为 简单命题。

例如“你被 XX 大学录取”、“你完成高中学业”等都是简单命题。

复合命题

类似英语中的简单句和复合句。

由简单命题通过 逻辑联结词 组合而成的命题称为 复合命题。

tip

复合命题有 $5$ 种类型：否定、合取、析取、蕴涵和等价。

再往后就是大学阶段的《数理逻辑》和《离散数学》等课程的内容了。

蕴涵

我们定义一个复合命题来描述两个简单命题 $p$ 和 $q$ 之间的 蕴涵 关系，形式为“若 $p$，则 $q$”。

我们设命题 $p$ 为“你被 XX 大学录取”，命题 $q$ 为“你完成高中学业”。

这样命题就变成了“若 $p$，则 $q$” 的形式，而 $p$ 可以推出 $q$，就说 $p$ 蕴含 $q$，记为：

$$p\Rightarrow q$$

但反过来说“若 你完成高中学业，则 你被 XX 大学录取”，这个命题不成立，$q$ 不能推出 $q$，记为：

$$q\nRightarrow p$$

等价

如果“若 $p$，则 $q$”及其 逆命题“若 $q$，则 $p$”都为真，即：

$$p\Rightarrow q\text{且}q\Rightarrow p$$

则两个命题 等价，记为：

$$p\Leftrightarrow q$$

这两句话本身也可以用等价表示：

$$(p\Rightarrow q\text{且}q\Rightarrow p)\Leftrightarrow(p\Leftrightarrow q)$$

否定

命题 $p$ 的 否定 就是把命题 $p$ 取反，记为：

$$\lnot p$$

显然 $p$ 和 $\lnot p$ 必有一个真，一个假。

例如命题“你被 XX 大学录取”的否定就是“你没被 XX 大学录取”。

充分条件与必要条件

充分条件

如果命题 $p$（你被 XX 大学录取）成立，就可以 充分 说明命题 $q$（你完成高中学业）成立，所以我们称 $p$ 是 $q$ 的 充分条件。

必要条件

反过来，如果命题 $q$（你完成高中学业）成立，命题 $p$（你被 XX 大学录取）成立是 必要 的，所以我们称 $q$ 是 $p$ 的 必要条件。

充要条件

如果 $p$ 即是 $q$ 的充分条件，也是 $q$ 的必要条件，我们称 $p$ 是 $q$ 的 充分必要条件，简称为 充要条件。

总结

对于两个命题 $p,q$：

• 如果“若 $p$，则 $q$”成立，则 $p$ 可以推出 $q$，记为 $p\Rightarrow q$。
• 如果“若 $p$，则 $q$”不成立，则 $p$ 不能推出 $q$，记为 $p\nRightarrow q$。
• 如果 $p\Rightarrow q,q\Rightarrow p$（$p\Leftrightarrow q$），则称 $p$ 是 $q$ 的 充分必要条件。
• 如果 $p\Rightarrow q,q\nRightarrow p$，则称 $p$ 是 $q$ 的 充分不必要条件。
• 如果 $p\nRightarrow q,q\Rightarrow p$，则称 $p$ 是 $q$ 的 不充分必要条件。
• 如果 $p\nRightarrow q,q\nRightarrow p$，则称 $p$ 是 $q$ 的 既不充分也不必要条件。

全称量词与存在量词

全称量词

短语“所有的”“任意一个”在逻辑中通常叫做 全称量词，用符号 $\forall$ 表示。

含有全称量词的命题，叫做 全称量词命题。

$$\forall x\in M,p(x)$$

全称量词命题只有在 所有情况 下都成立时才为真。

Example

全称量词命题“所有实数 $x$ 的 $0$ 次幂都等于 $1$”可以表示为：

$$\forall x\in\mathbb{R},x^0=1$$

这个命题是假的，因为当 $x=0$ 时不成立。（$0^0$ 属于未定式）

存在量词

短语“存在一个”“至少有一个”在逻辑中通常叫做 存在量词，用符号 $\exists$ 表示。

含有存在量词的命题，叫做 存在量词命题。

$$\exists x\in M,p(x)$$

存在量词命题只要在 某个情况 下成立时就为真。

Example

存在量词命题“存在整数 $x$ 的平方等于 $9$”可以表示为：

$$\exists x\in\mathbb{Z},x^2=9$$

这个命题是真的，因为当 $x=-3$ 或 $x=3$ 时成立。

全称量词命题的否定

全称量词命题：

$$\forall x\in M,p(x)$$

它的否定为：

$$\lnot(\forall x\in M,p(x))\Leftrightarrow\exists x\in M,\lnot p(x)$$

全称量词命题 的否定是 存在量词命题。

Example

考虑全称量词命题“所有实数 $x$ 的 $0$ 次幂都等于 $1$”：

$$\forall x\in\mathbb{R},x^0=1$$

它的否定是“并非所有实数 $x$ 的 $0$ 次幂都等于 $1$”，换句话说就是“存在实数 $x$ 的 $0$ 次幂不等于 $1$”：

$$\lnot(\forall x\in\mathbb{R},x^0=1)\Leftrightarrow\exists x\in\mathbb{R},x^0\ne 1$$

存在量词命题的否定

存在量词命题：

$$\exists x\in M,p(x)$$

它的否定为：

$$\lnot(\exists x\in M,p(x))\Leftrightarrow\forall x\in M,\lnot p(x)$$

存在量词命题 的否定是 全称量词命题。

Example

考虑存在量词命题“存在整数 $x$ 的平方等于 $9$”：

$$\exists x\in\mathbb{Z},x^2=9$$

它的否定是“不存在整数 $x$ 的平方等于 $9$”，换句话说就是“所有整数 $x$ 的平方都不等于 $9$”：

$$\lnot(\exists x\in\mathbb{Z},x^2=9)\Leftrightarrow\forall x\in\mathbb{Z},x^2\ne 9$$