命题逻辑
数理逻辑的研究对象是逻辑推理，研究逻辑推理的形式和规律。一个推理由若干命题组成，推理中的前提和结论都是命题，命题是逻辑推理的基本成分。若在推理中只需要分析命题之间的关系，不需要把命题分解成构成命题的各种非命题成分，那么此类推理的逻辑研究称作命题逻辑，而对命题加以分解的推理称作谓词逻辑，谓词逻辑相对命题逻辑来说较复杂。我们的研究先从比较简单的命题逻辑开始，命题逻辑是数理逻辑中最基本、最简单的部分。
本章介绍命题逻辑的基本知识，包括命题与联结词、命题公式与真值、逻辑蕴涵与逻辑等价、范式、联结词的功能完备集以及对偶式等内容。
命题与联结词
命题符号化
命题
命题对于命题逻辑来说是一个原始的概念，因此不能在命题逻辑的范围内给出它的精确定义，但可以描述它的性质。
这包括两层意思：首先，命题必须是一个陈述句，而疑问句、祈使句、感叹句则都不是命题；其次，这个陈述句所表达的内容可决定是真还是假，而且不是真的就是假的，不能既真又假，也不能不真又不假。凡与事实相符的陈述句（命题）为真语句，与事实不符的陈述句（命题）为假语句，这就是说，一个命题只有两种可能的取值，为真或为假，并且只能取其一。
下面举例说明命题的概念。
(1) 北京是中国的首都。
(2) $X+Y=2$ 。
(3) $2+2=5$ 。
(4) 火星上有生命存在。
(5) 地球是宇宙的中心吗？
(6) 太阳从西边出来。
仅有(1)(3)(4)(6)是命题，其余不是命题。其中(1)是真命题，其命题真值为 $ \mathrm{T}$ ；(4)(6)为假命题，其命题真值为 $\mathrm{F}$ ；(4)的命题真值受限于人类目前的认知水平还不能确定其真假值，但从事物的本质来看该语句的内容真假是可以唯一确定的。(2)含有命题变元 $X$ 与 $Y$ ，是不确定的判断，而(5)为疑问句，因此(2)(5)均不是命题。
原子命题
从语法的角度看就是不能分解为更简单的陈述句的命题。如命题“雪是白的。”就是一个原子命题。原子命题的符号通常用小写的英文字母表示。
复合命题
复合命题的真值依赖于构成该复合命题的各简单命题的真值及联结词。如命题“今天是晴天而且今天是星期天。”即为一复合命题，如果命题“今天是晴天”的真值为真，而且命题“今天是星期天”的真值也为真，那么整个复合命题的真值为真，其他情况则复合命题的真值为假。命题逻辑所要讨论的正是由多个命题经联结词联结而成的复合命题的规律性。
命题变元
为了用数学的方法对命题做逻辑演算，首先必须像数学处理问题那样将命题符号化（形式化）。通常用大写的英文字母或带下标来表示命题，这种用以表示命题的标识符号称为命题变元。如以字母 $P$ 表示命题“北京是中国的首都。”，字母 $Q$ 表示命题“水在常温下是液体。”等。
对命题变元可以指定任何命题给它。与命题有确定的真值不同，命题变元的真值不定，只有对命题变元指定为某个具体命题时，才能确定其真值。
命题联结词及真值表
联结词可以将简单命题联结起来构成复杂的命题，从而构造新的命题，使命题逻辑的内容变得丰富起来。下面先介绍数理逻辑中最基本、最常用的 $5$ 个逻辑联结词：
$$\begin{aligned} \neg,\and,\or,\imp,\iff \end{aligned}$$ 这 $5$ 个逻辑联结词符号分别读作“非”、“与”，“或”、“蕴涵”、“等价”，分别表示“否定”、“合取”、“析取”、“所以”、“当且仅当”，值得注意的是这些逻辑联结词与日常自然语句中的有关联结词的共同点和不同点。
由于复合命题中各个命题变元的取值只能取值 $T$ 或 $F$ ，同时复合命题本身的真值取值也只能为 $T$ 或 $T$ ，因此从映射的角度来看，一个 $n$ 元逻辑联结词其实就是一个 $n$ 元映射，一个从 $\set{T,F}^n$ 至 $\set{T,F}$ 的映射，于是可以用一个函数值表的形式反映该映射过程，此函数值表的形式称为真值表。
否定词 $\neg$
| $P$ | $\neg P$ |
|---|---|
| $\mathrm{T}$ | $F$ |
| $\mathrm{T}$ | $T$ |
表1 $\neg P$ 的真值表
一般地，自然语句中的“不”、“无”、“没有”、“并非”等词均可符号化为“ $\neg$ ”。但这并不意味着在使用否定词的时候可以简单地加个不字就能完成。比如下面这个例子。
合取词 $\and$
| $P$ | $Q$ | $P \and Q$ |
|---|---|---|
| $\mathrm{T}$ | $\mathrm{F}$ | $\mathrm{T}$ |
| $\mathrm{T}$ | $\mathrm{F}$ | $\mathrm{F}$ |
| $\mathrm{F}$ | $\mathrm{T}$ | $\mathrm{F}$ |
| $\mathrm{F}$ | $\mathrm{F}$ | $\mathrm{F}$ |
表2 $P \and Q$ 的真值表
一般地，自然语句中常用的联结词如“既···又···”、“不仅···而且···"、“虽然···但是···”、“···和···”通常都可以化为“ $\and$ ”。但自然语句中有些“和“、“与”并不表示两个命题的复合，如“张三和李四是大学同学”就是一个简单命题。
析取词 $\or$
| $P$ | $Q$ | $P \or Q$ |
|---|---|---|
| $\mathrm{T}$ | $\mathrm{T}$ | $\mathrm{T}$ |
| $\mathrm{T}$ | $\mathrm{F}$ | $\mathrm{T}$ |
| $\mathrm{F}$ | $\mathrm{T}$ | $\mathrm{T}$ |
| $\mathrm{F}$ | $\mathrm{F}$ | $\mathrm{F}$ |
表3 $P \or Q$ 的真值表
自然语句中常用的联结词如“或者”一般可以化为" $\or$ “。但有些情况下，在使用析取词“ $\or$ ”表达由“或者”联结的复合命题时，需要注意自然语句中的“或者”与我们通常所说的“异或”区分开来，比如复合命题“今天我去图书馆或者去踢足球”，它表达的是一种不可兼或，二者只能取一，即我们常说的“异或”，而不是逻辑“或”。
蕴涵词 $\imp$
| $P$ | $Q$ | $P \imp Q$ |
|---|---|---|
| $\mathrm{T}$ | $\mathrm{T}$ | $\mathrm{T}$ |
| $\mathrm{T}$ | $\mathrm{F}$ | $\mathrm{F}$ |
| $\mathrm{F}$ | $\mathrm{T}$ | $\mathrm{T}$ |
| $\mathrm{F}$ | $\mathrm{F}$ | $\mathrm{T}$ |
表4 $P \imp Q$ 的真值表
复合命题 $P \imp Q$ 表达的逻辑关系是“ $P$ 是 $Q$ 的充分条件”或“ $Q$ 是 $P$ 的必要条件”。由于自然语言的复杂性，表示 $P \imp Q$ 的术语除了“如果 $P$ ，那么 $Q$ ”外，还有常见的表述如“只要 $P$ ，就 $Q$ ”，“ $P$ 仅当 $Q$ ”，“只有 $Q$ ，才 $P$ ”以及“除非 $Q$ ，否则非 $P$ ”等。
等价词 $\iff$
| $P$ | $Q$ | $P \imp Q$ |
|---|---|---|
| $\mathrm{T}$ | $\mathrm{T}$ | $\mathrm{T}$ |
| $\mathrm{T}$ | $\mathrm{F}$ | $\mathrm{F}$ |
| $\mathrm{F}$ | $\mathrm{T}$ | $\mathrm{F}$ |
| $\mathrm{F}$ | $\mathrm{F}$ | $\mathrm{T}$ |
表5 $P \iff Q$ 的真值表
在由上述五个逻辑联结词构成的复合命题中，有时候为了减少其中的括号使用次数，可以约定它们的运算优先级，按照优先级从高到低依次为
$$\begin{aligned} \neg,(\and,\or),\imp,\iff \tag{1}\end{aligned}$$其中 $\land$ 与 $\or$ 的优先级相同，在容易引起歧义的地方可以通过 加括号来更改运算的结合顺序。
命题公式及真值
命题公式
(1) 原子命题是命题公式。
(2) 若 $A,B$ 是命题公式，则 $\neg A,A \and B,A \or B,A \imp B,A \iff B$ 均是命题公式。
(3) 有限次使用(1)与(2)复合所得的结果均是命题公式。
命题公式通常简称为公式，一般用大写的字母等表示。如果公式 $A$ 中含有原子变元 $p_1,p_2,\cdots,p_n$ ，那么公式 $A$ 通常记为 $A(p_1,p_2,\cdots,p_n)$
指派
对于一个给定的命题公式，通过对其中的命题变元赋值，然后结合逻辑联结词的含义来给出命题公式的真值取值情况，这其中的赋值过程称为指派。
指派常用符号 $\alpha$ 来表示。若对公式 $A$ 的一个给定的指派 $\alpha$ ，使得 $A$ 的真值为真，则记为 $\alpha(A)=\mathrm{T}$ ，表示公式 $A$ 在指派 $\alpha$ 的作用下其真值为真，反之则记为 $\alpha(A)=\mathrm{F}$ 。
很显然公式 $A$ 若含有 $n$ 个命题变元，则共有 $2^n$ 个不同的指派。
根据公式的真值取值情况不同，可以将公式分为以下 $3$ 类：永真式、永假式和满足式。
永真式
永假式
可满足式
根据它们的定义可以看出三者之间的关系：
(1) 公式 $A$ 永真，当且仅当 $\neg A$ 永假。
(2) 公式 $A$ 可满足，当且仅当 $\neg A$ 非永真。
(3) 不是可满足的公式必永假。
(4) 不是永假的公式必可满足。
逻辑蕴涵与逻辑等价
逻辑蕴涵
若所有使公式集 $\Gamma=\set{A_1,A_2,\cdots,A_n}$ 中的每个公式为真的指派，也必使公式 $B$ 为真，则称 $\Gamma$ 逻辑蕴涵 $B$ ，或称 $B$ 是 $\Gamma$ 的逻辑推论，记为 $\Gamma \vDash B$ 。
(1) $\neg A \vDash A \imp B$ 。
(2) $\Gamma \vDash A \imp C$ ，其中公式集 $\Gamma = \set{A \imp (B \imp C),B}$ 。
(1) 成立。从表6可以看出使得 $\neg A$ 为真的指派也使得 $A \imp B$ 为真。
| $A$ | $B$ | $\neg A$ | $A \imp B$ |
|---|---|---|---|
| $\mathrm{T}$ | $\mathrm{T}$ | $\mathrm{F}$ | $\mathrm{T}$ |
| $\mathrm{T}$ | $\mathrm{F}$ | $\mathrm{F}$ | $\mathrm{F}$ |
| $\mathrm{F}$ | $\mathrm{T}$ | $\mathrm{T}$ | $\mathrm{T}$ |
| $\mathrm{F}$ | $\mathrm{F}$ | $\mathrm{T}$ | $\mathrm{T}$ |
表6 $\neg A$ 蕴涵 $A \imp B$
(2) 成立。使得 $\Gamma$ 中的每个公式为真的指派分别为
$$\begin{aligned} \alpha_1(A)=\mathrm{F},\alpha_1(B)=\mathrm{T},\alpha_1(C)=\mathrm{T},此时\alpha_1(A \imp C)=\mathrm{T} \end{aligned}$$$$\begin{aligned} \alpha_2(A)=\mathrm{F},\alpha_2(B)=\mathrm{T},\alpha_1(C)=\mathrm{F},此时\alpha_2(A \imp C)=\mathrm{T} \end{aligned}$$$$\begin{aligned} \alpha_3(A)=\mathrm{T},\alpha_3(B)=\mathrm{T},\alpha_3(C)=\mathrm{T},此时\alpha_3(A \imp C)=\mathrm{T} \end{aligned}$$故 $\Gamma \vDash (A \imp C)$ 成立。〔例9解毕〕
逻辑等价
| $A$ | $B$ | $\neg A \imp B$ | $\neg B \imp A$ |
|---|---|---|---|
| $\mathrm{T}$ | $\mathrm{T}$ | $\mathrm{T}$ | $\mathrm{T}$ |
| $\mathrm{T}$ | $\mathrm{F}$ | $\mathrm{T}$ | $\mathrm{T}$ |
| $\mathrm{F}$ | $\mathrm{T}$ | $\mathrm{T}$ | $\mathrm{T}$ |
| $\mathrm{F}$ | $\mathrm{F}$ | $\mathrm{F}$ | $\mathrm{F}$ |
表7 $\neg A \imp B$ 逻辑等价于 $\neg B \imp A$
〔例10解毕〕
地狱是什么？我以为它是“再也不能爱”这样的痛苦。― Fyodor Mikhailovich Dostoevsky, 《卡拉马佐夫兄弟》