逻辑与公理化集合论(01)：数理逻辑的基本语法

数学在未曾深入学习数学的人群中, 常常被当成纯粹进行算术操作的学科. 事实上, 它是关于命题及其演绎的学科. 在正式讲述数学分析的内容之前, 确立一种通用的逻辑语言是必要的.\(\newcommand{\R}{\mathbb{R}}\newcommand{\C}{\mathbb{C}}\newcommand{\K}{\mathbb{K}}\newcommand{\exist}{\exists}\newcommand{\and}{\land}\newcommand{\or}{\lor}\)

命题与量词

我们从命题开始. 在数学中, 命题(proposition) 是一个具有确定真值的陈述句.

Example 命题与陈述句

1. "\(3<4\)"是真命题;
2. "\(2-6>0\)"是假命题;
3. "\(x+5<8\)"不是命题.

注意到, 上述例3之所以不是命题, 是因为\(x\)是一个自由变量, \(x\)的赋值不同, 例3的真值就随之改变, 称之为 开语句. 只有赋予\(x\)一定的约束, 才能转化为命题. 下面给出转化为命题的示例.

Example 将普通陈述句"\(x+5<8\)"构造为命题

1. "当\(x=1\)时, \(x+5<8\)"是真命题;
2. "对于任意实数\(x\), \(x+5<8\)"是假命题;
3. "存在实数\(x\), 使得\(x+5<8\)"是真命题.

这里使用了两种约束, 一个是"对于任意…", 称为 全称量词, 记号为\(\forall\); 另一个是"存在…", 称为 存在量词, 记号为\(\exist\). 下表给出自然语言和逻辑符号(主要是量词)的转换示例

自然语言	逻辑符号
对于任意实数\(x\)	\(\forall x\in\R\)
存在实数\(x\)	\(\exist x\in\R\)

Remark

是的, 现在还没有集合论, 也没有属于关系. 但是正如寓言所说: 蜈蚣在解释清楚自己如何同时控制那么多腿之前, 已经会走路了.

最后, 可以通过一个例子说明量词不一定能交换顺序. 例如

• "\(\forall x\in\R(\exist y\in\R(x+y=0))\)"为真命题;
• "\(\exist y\in\R(\forall x\in\R(x+y=0))\)"为假命题.

逻辑算子

"非"是惟一的一元逻辑算子(如果不考虑恒等算子的话), 当我们试图反转一个命题时, 我们使用"非", 符号为\(\neg\), 例如"\(3>5\)"是假命题, 则"\(\neg(3>5)\)"(更常见地写为"\(3\not>5\)")构成一个真命题. "非"符号能够反转一切命题的真假性.

倘若对含量词的命题取非, 又该如何写呢? 例如命题\(P\)为"\(\forall x\in\R (x+5<8)\)", 它的非是 \[ \exist x\in\R (x+5\ne8) \] 全称量词被变为了存在量词. 反之亦然.

二元的逻辑算子将两个命题连接为一个复合命题. 给定命题\(P\)和\(Q\), 最常见的二元连接词是"与"和"或".

与关系	或关系	蕴含关系	等价关系
\(P\and Q\)	\(P\or Q\)	\(P\Rightarrow Q\)	\(P\Leftrightarrow Q\)

与或关系的特点是具有对称性, 并且形式逻辑符合对应的语义逻辑, \(P\and Q\)为真当且仅当\(P\)和\(Q\)都为真, \(P\or Q\)为假当且仅当\(P\)和\(Q\)都为假.

蕴含关系\(P\Rightarrow Q\)可以读作"若\(P\)则\(Q\)", 表示已知\(P\)成立则\(Q\)一定成立, 反之则不然. 这种结构也叫作 假言推断 或者 假言命题.

等价关系读作"\(P\)等价于\(Q\)", 它可以看成两个蕴含的并列, 即 \[ (P\Rightarrow Q)\and(Q\Rightarrow P) \] 通常"若\(P\)为真"会被简写为"若\(P\)". 蕴含关系可以表述为所谓的充分性和必要性

Def 充分条件和必要条件

若\(P\Rightarrow Q\), 称\(P\)是\(Q\)的 充分条件, \(Q\)是\(P\)的 必要条件.

如果\(P\Leftrightarrow Q\), 说明\(P\)既是\(Q\)的充分条件, 也是\(Q\)的必要条件, 称为 充分必要条件(充要条件).

假言推断

真值和逻辑正确的区别

在日常生活中, 人们会对类似假言推断的结构赋予"正确"与"错误"的性质, 与真假性相同的是, "正误性"同样符合排中律, 即一个命题不会既正确又错误, 但是"正误性"不具有真值表. 例如如下三个"正确的"命题: \[ P:(2+2=4)\and(4<5)\quad Q_1:2+2<5 \quad Q_2:\text{鲸和鱼类不属于同一个纲} \] 对于假言命题\(P\Rightarrow Q_1\)和\(P\Rightarrow Q_2\), 人们常常认为前者是"正确的", 后者是"错误的", 尽管\(P,Q_1,Q_2\)都是"正确的". 出现这种现象的原因是, "正误性"不是一个严格的形式逻辑概念, 它是一种语义上的关系, 包含了一种具有模糊性的"逻辑递进", 这是只接收和处理布尔值的形式逻辑所无法应对的. 形式逻辑更希望处理一种"相容性", 任何真命题到真命题的假言推断都是真的, 无论它们是否具有"因果关联".

既然已经抛弃了模糊的因果关系, 那么假言命题就具有严格遵循的真值表, 需要对其它三种情形的真假性作出回答. 假言推断的完整真值表如下

\(P\)	\(Q\)	\(P\Rightarrow Q\)	诠释
T	T	T	真推真一定为真, 与是否具有因果关系无关
T	F	F	真推不出假, 如果推出了, 说明推断为假
F	T	T	空真
F	F	T	空真

可以用一个例子来解释空真. 考虑如下两个自然语言中出现的命题 \[ P:\text{今天会下雨}\quad Q:\text{明天我会放弃使用手机} \] \(P\Rightarrow Q\)相当于一个承诺: 如果今天晚上下雨, 那么我明天不使用手机. 后来发现晚上没有下雨, 那么第二天无论是否使用手机, 都不违背承诺; 类比到假言推断就是, \(P\)是假命题, 则无论\(Q\)是真还是假, \(P\Rightarrow Q\)都是真的, 这就是所谓的"空真".

这个例子可以继续解释真到假的假言推断. 发现晚上下雨后, 我依然在次日使用手机, 显然违背了承诺, 因此真到假的假言命题是假命题.

逆命题、否命题和逆否命题

对于假言命题"\(P\Rightarrow Q\)", 可以定义出三种衍生的命题结构(注意否命题不是取原命题的非)

原命题	逆命题	否命题	逆否命题
\(P\Rightarrow Q\)	\(Q\Rightarrow P\)	\(\neg P\Rightarrow\neg Q\)	\(\neg Q\Rightarrow \neg P\)

"原命题"这一概念显然具有相对性, 例如"\(Q\Rightarrow P\)"和"\(\neg P\Rightarrow\neg Q\)"也是一对逆否命题.

逆否命题的优良性质是, 一对互为逆否命题的命题具有相同的真假性.

二元逻辑算子的性质

在充分理解真值表的前提下, 真值表应当作为逻辑算子的公理化定义. 现在所有逻辑算子的真值表已然明确, 可以指出几条非常有用的性质了.

二元逻辑算子的性质

1. "与"和"或"的对称性: 命题\(P\and Q\)等价于\(Q\and P\), \(P\or Q\)也等价于\(Q\or P\).

2. "蕴含"具有如下性质:

   1. 自反性: 命题\(P\Rightarrow P\)一定为真;

   2. 传递性: 若\(P\Rightarrow Q\)且\(Q\Rightarrow R\), 则\(P\Rightarrow R\);

   3. 空真性: 任何假命题作为前提的蕴含关系总为真.

3. 等价具有如下性质:

   1. 对称性: \(P\Leftrightarrow Q\)等价于\(Q\Leftrightarrow P\);
   2. 自反性: \(P\Leftrightarrow P\);
   3. 传递性: 若\(P\Leftrightarrow Q\)且\(Q\Leftrightarrow R\), 则\(P\Leftrightarrow R\).

全部证明从略.