第 2 讲 · 命题、联结词与合式公式

命题是具有确定真假的陈述句。“请关门”不是命题，“$x+1=2$”在没有指定 $x$ 时也不是命题；“若 $1+1=3$，则北京在中国”虽然前后毫无因果关系，却是一个真命题。

数理逻辑只关心真假怎样由结构决定，不分析自然语言中的因果是否合理。

六种常用联结词

$p$	$q$	$\neg p$	$p\land q$	$p\lor q$	$p\to q$	$p\leftrightarrow q$	$p\oplus q$
0	0	1	0	0	1	1	0
0	1	1	0	1	1	0	1
1	0	0	0	0	0	0	1
1	1	0	1	1	1	1	0

蕴涵最容易出错：

$$p\to q$$

只在“前件真、后件假”时为假。它等值于

$$\neg p\lor q.$$

“只要”和“只有”

令 $p$ 表示“天气好”，$q$ 表示“去公园”：

• “只要天气好，我就去公园”：$p\to q$；
• “只有天气好，我才去公园”：$q\to p$；
• “当天气好且仅当天气好时去公园”：$p\leftrightarrow q$。

判断必要条件时可以问：若条件不成立，结果还能不能成立？“天气好是去公园的必要条件”意味着没有好天气就不去，即 $\neg p\to\neg q$，它与 $q\to p$ 等值。

合式公式是递归生成的

在包含常元 $0,1$ 与联结词

$$\{\neg,\land,\lor,\to,\leftrightarrow,\oplus\}$$

的命题语言中：

1. $0,1$ 是公式；
2. 命题变元是公式；
3. 若 $A,B$ 是公式，则 $\neg A$、$A\land B$、$A\lor B$、$A\to B$、 $A\leftrightarrow B$、$A\oplus B$ 是公式；
4. 只有有限次使用这些规则得到的符号串才是公式。

括号、联结词和操作数缺一不可。$p\land\to q$ 不是公式，不是因为它“意思奇怪”，而是因为它不能由形成规则生成。

复杂度和唯一解析

课件用 $FC(A)$ 表示公式复杂度：

$$FC(p)=0,\qquad FC(\neg A)=FC(A)+1,$$ $$FC(A\circ B)=\max\{FC(A),FC(B)\}+1.$$

其中 $\circ$ 是任意二元联结词。

例如

$$A=\neg p\lor(q\land r)$$

中 $FC(q\land r)=1$，$FC(\neg p)=1$，所以 $FC(A)=2$。

复杂度不是“联结词总数”，而是语法树最深路径的长度。按复杂度归纳时，这个定义保证子公式一定比原公式简单。

通常的优先级从高到低为

$$\neg,\quad\land,\quad\lor,\quad\oplus,\quad\to,\quad\leftrightarrow.$$

但写证明或试卷答案时，不要让运算顺序依赖默认优先级；关键位置保留括号。

代换和替换

代换是同时把命题变元换成公式。若

$$A=(p\land\neg q)\to q,$$

用 $q\land r$ 代换 $p$、用 $r\to p$ 代换 $q$，必须在原公式中同时进行：

$$A[p/(q\land r),q/(r\to p)] = \bigl((q\land r)\land\neg(r\to p)\bigr)\to(r\to p).$$

不能先换 $p$，再在新塞进去的 $q\land r$ 中继续替换 $q$；那会把“同时代换”做成“顺序改写”。

替换则是把某个子公式整体换成与它等值的公式。若 $R_1\equiv R_2$，那么在任意上下文中用 $R_2$ 替换 $R_1$，所得公式仍与原公式等值。

这就是等值演算可以“局部改写”的依据。

从真值表反推公式

给定 $n$ 个命题变元的真值表，每一行都对应一个极小项。例如三变量行

$$(p,q,r)=(1,0,1)$$

对应

$$p\land\neg q\land r.$$

把输出为 $1$ 的行对应极小项全部析取，就得到定义该真值函数的公式。这不仅说明“可从真值表写公式”，还为完全集证明提供了直接构造。