2.1 命题逻辑基本概念

本节对应原书 PDF 第 37–48 页。定义、定理、公式、例题及其原解答逐字取自原书；解释性文字为 AI 通俗化改写；标有「解读」的引用块为 AI 补充的额外直觉。

2.1.1 命题与联结词

数理逻辑研究推理过程本身，以及推理是否正确。它包含逻辑演算(命题演算与谓词演算)、公理集合论、证明论、递归函数论、模型论等，其中逻辑演算是其他各部分的基础。数理逻辑既是各数学学科的基础，也与人工智能、语言学等学科，特别是计算机科学关系密切，因此逻辑演算(主要是命题演算与一阶谓词逻辑演算)已成为计算机专业基础课程"离散数学"的重要组成部分。本章介绍命题逻辑(也称命题演算)的基本概念、等值演算以及推理理论。

推理是数理逻辑的主要研究内容，粗略地说，推理是从前提出发，推出结论的逻辑思维过程.下面给出两个推理，从中寻找构成推理的最基本成分，即命题.

推理 1 若华盛顿是美国的首都，则多伦多是加拿大的首都.华盛顿是美国的首都，所以，多伦多是加拿大的首都.

推理 2 若今年是 2004 年，则明年是 2005 年.明年是 2005 年，所以今年是 2004 年.

现在先不讨论以上两个推理是否正确(在 2.4 节将可以证明，推理 1 正确，而推理 2 不正确)，主要讨论它们的组成成分.除了若……则、所以等联结词外，其余部分全是陈述语句，在这些陈述句中，"华盛顿是美国首都"是真的，"多伦多是加拿大首都"是假的.在今天(2004 年 1 月 31 日)说"今年是 2004 年"，"明年是 2005 年"，它们也都是真的.

从以上两个推理可以看出，构成推理的基本要素，除联结词外就是陈述句了.在数理逻辑中，称所表达的判断是真(正确)或假(错误)但不能可真可假的陈述句为命题，命题是推理的最基本的成分.在命题逻辑中，对命题的成分(如主语、谓语等)不再细分，也就是说命题是命题逻辑中最小的研究单位.

作为命题的陈述句所表达的判断结果称为命题的真值，真值只取两个值：真或假.真值为真的命题称为真命题，真值为假的命题称为假命题.任何命题的真值都是唯一的.

判断给定语句是否为命题，要分两步：首先判断它是否为陈述句，即先淘汰感叹句、祈使句、疑问句；其次判断它是否有唯一的真值，即不是可真可假的陈述句.概括起来可以这样说，陈述句是命题的必要条件，并不是充分条件.只有具有唯一真值的陈述句才是命题.

解读：判命题就两步——先看句式，再看真值是否唯一。像 x+2\geqslant 5 这种带自由变元的句子最容易误判：它形式上是陈述句，可真值随 x 变，所以不是命题；而"火星上有生命"只是"现在还不知道"，真值客观唯一，仍算命题。

例 2.1 判断下列句子是否为命题.

(1) 多伦多是加拿大的首都.

(2) \sqrt{2}是无理数.

(3) x+2\geqslant 5.

(4) 火星上有生命.

(5) 2050 年元旦北京是晴天.

(6) 你会开车吗？

(7) 请关上门！

(8) 这个操场真大呀！

(9) 我正在说谎话.

解 在 9 个句子中，首先找陈述句.(1)，(2)，(3)，(4)，(5)，(9)均为陈述句.在陈述句中再找具有唯一真值的陈述句，它们才是命题.

因为多伦多不是加拿大的首都，因而(1)为命题.并且是假命题.

因为\sqrt{2}真是无理数，故(2)为真命题.

x+2\geqslant 5是陈述句，但它无确定的真值(当 x\geqslant 3 时，它为真，而 x\leqslant 2 时，它为假)，故(3)不是命题.

(4)是命题.它有确定的真值，只是在 2004 年 2 月 1 日的今天还不知道而已.随着美国勇气号和机遇号火星车登上火星，火星上有无生命很可能很快就会知道了，那时(4)的真值也就真相大白了.

(5)也是命题，到 2050 年元旦它的真值就知道了.

(9)虽然是陈述句，但它不是命题，原因是它既不能为真，也不能为假.若(9)的真值为真，即"我正在说谎话"是句真话，因而我正在说真话，这与"我正在说谎话"矛盾.反之，若(9)的真值为假，即"我正在说谎话"为假，也就是"我正在说谎话"是假的，因而我是在说真话.这也与"我正在说谎话"矛盾.这是一个悖论，凡是悖论都不是命题.

9 个句子中，不是陈述句的为(6)，(7)，(8)，它们分别为疑问句、祈使句和感叹句，当然它们都不是命题.

在数理逻辑中，将命题和它的真值用抽象的符号表示，称为命题符号化.在本书中，用小写的英文字母 p,q,r,\cdots,p_i,q_i,r_i,\cdots 表示命题，用数字 1 表示真，数字 0 表示假.这样规定后，命题的真值只取两个值，即 1 或 0.在例 2.1 中，用 p,q,r,s 分别表示(1)，(2)，(4)，(5)中的命题，称为对这些命题的符号化.其表示法为

p：多伦多是加拿大的首都.

q：\sqrt{2}是无理数.

r：火星上有生命.

s：2050 年元旦北京是晴天.

其中，p 的真值为 0，q 的真值为 1，r 与 s 的真值现在不知道.

在例 2.1 中，p,q,r,s 所表示的命题都是简单的陈述句，在这些陈述句中均无联结词出现，称它们为简单命题或原子命题.但在各种推理中，所出现的命题多数是由简单命题通过联结词的联结而成的陈述句，称这样的命题为复合命题.下面讨论联结词及复合命题的符号化形式.为此，先看例 2.2.

例 2.2 将下列各复合命题中的简单命题符号化，然后再写出各复合命题.

(1) 多伦多不是加拿大的首都.

(2) 华盛顿是美国的首都并且渥太华是加拿大的首都.

(3) 华盛顿是美国的首都或多伦多是加拿大的首都.

(4) 如果 2 是素数，则 3 也是素数.

(5) 2 是素数当且仅当 3 也是素数.

解 设 p：多伦多是加拿大的首都.

q：华盛顿是美国的首都.

r：渥太华是加拿大的首都.

s：2 是素数.

t：3 是素数.

(1) 不是 p.

(2) q 并且 r.

(3) q 或 p.

(4) 如果 s，则 t.

(5) s 当且仅当 t.

数理逻辑的主要特征是用符号语言来代替自然语言.在例 2.2 中，还没有达到这一点.为此还应将"不是(非)"、"并且"、"或"、"如果，则"、"当且仅当"等联结词也符号化.下面讨论这 5 种联结词的符号化，以及由它们联结的基本复合命题和复合命题.

定义 2.1 设 p 为命题，复合命题"非 p"(或"p 的否定")称为 p 的否定式，记作 \neg p，符号 \neg 称作否定联结词.并规定 \neg p 为真当且仅当 p 为假.

由定义可知，\neg p 的逻辑关系为 p 不成立，因而当 p 为真时，\neg p 为假，反之当 p 为假时，\neg p 为真.

若设 p：2 是合数，则 \neg p：2 不是合数.由于 p 为假命题，所以，\neg p 为真命题.

定义 2.2 设 p,q 为两个命题，复合命题"p 并且 q"(或"p 与 q")称为 p 与 q 的合取式，记作 p\wedge q，\wedge 称作合取联结词.并规定 p\wedge q 为真当且仅当 p 与 q 同时为真.

由定义可知，p\wedge q 的逻辑关系为 p 与 q 同时成立，因而只有当 p 与 q 同时为真，p\wedge q 才为真，其他情况 p\wedge q 均为假.

使用联结词 \wedge 需要注意两点：其一是 \wedge 的灵活性.自然语言中的"既……，又……"、"不但……，而且……"、"虽然……，但是……"、"一面……，一面……"等联结词都可以符号化为 \wedge.其二，不要见到"与"或"和"就使用联结词 \wedge.

解读：\wedge 的坑在于"和/与"不一定对应合取——它可能只是主语内部的一部分（如"王丽和王娟是亲姐妹"），这时整个句子仍是简单命题。判断标准是：这个"和"连接的是两个句子，还是一个句子的某个成分。

例 2.3 将下列命题符号化.

(1) 2 既是偶数又是素数.

(2) 6 不仅能被 2 整除，而且能被 3 整除.

(3) 8 能被 2 整除，但不能被 6 整除.

(4) 5 是奇数，6 是偶数.

(5) 2 与 3 的最小公倍数是 6.

(6) 王丽和王娟是亲姐妹.

解 在 6 个命题中，(1)，(2)，(3)，(4)为复合命题，而且都是合取式.(5)，(6)都是简单命题.

(1) p\wedge q，其中，p:2 是偶数，q:2 是素数.

(2) p\wedge q，其中，p:2|6，q:3|6.

(3) p\wedge\neg q，其中，p:2|8，q:6|8.

(4) p\wedge q，其中，p:5 是奇数，q:6 是偶数.

(5) p:2 和 3 的最小公倍数是 6.

(6) p:王丽与王娟是亲姐妹.

本例说明合取联结词在应用中叙述方法的灵活性.同时注意"和"与"与"联结的是两个句子，还是一个句子的某个成分.在(5)和(6)中"和"与"与"联结的是主语成分，因而它们都是简单命题.

定义 2.3 设 p,q 为两命题，复合命题"p 或 q"称作 p 与 q 的析取式，记作 p\vee q，\vee 称作析取联结词.并规定 p\vee q 为假当且仅当 p 与 q 同时为假.

p\vee q 的逻辑关系是 p 与 q 中至少一个成立，因而只有 p 与 q 同时为假时，p\vee q 才为假，其他情况下，p\vee q 均为真.

自然语言中的"或"具有二义性，用它联结的命题有时具有相容性，有时具有排斥性，对应的联结词分别称为相容或和排斥或.当联结的两个命题同时为真时，相容或为真，而排斥或为假.也就是说，只有当联结的两个命题一真一假时，排斥或才为真，上面定义的析取是相容或.

解读：数理逻辑里的 \vee 只取"相容或"这一种含义。日常语言的"或"有时是排斥或，这时不能直接写成 \vee，要按"二者恰有一个成立"另行符号化。

例 2.4 将下面命题符号化.

(1) 王冬梅学过日语或俄语.

(2) 张晓燕生于 1977 年或 1978 年.

(3) 小元元只能拿一个苹果或一个梨.

解 先将简单命题符号化.

(1) 令 p：王冬梅学过日语.

q：王冬梅学过俄语.

因为王冬梅可能只学过日语，也可能只学过俄语，还可能日语、俄语都学过，也还可能这两种语言都没学过.因而(1)中"或"为相容或，故符号化为

(2) 令 r：张晓燕生于 1977 年.

s：张晓燕生于 1978 年.

由于张晓燕若生于 1977 年，就不能生于 1978 年；同样若她生于 1978 年，就不能生于 1977 年.所以 r,s 不能同为真，当然可以同为假.因而(2)中"或"为排斥或.但由于 r 与 s 不能同时为真，所以(2)依然可符号化为

当张晓燕生于 1977 年(此时，r 为真，s 必为假)时，或张晓燕生于 1978 年(此时，r 必为假，s 为真)时，r\vee s 为真.当她既不是生于 1977 年，也不是生于 1978 年(此时，r,s 均为假)时，r\vee s 为假.

(3) 令 t：小元元拿一个苹果.

u：小元元拿一个梨.

不难看出(3)中"或"受"只能"的限制，应为排斥或.但它与(2)中排斥或不同，不同点在于(3)中，t,u 可同时为真，不同于(2)中 r,s 不能同时为真，因而(3)中"或"不能符号化为 t\vee u.用联结词 \neg,\vee,\wedge 可达到不使 t,u 同时为真的目的，应符号化为

易知，只 t 为真 u 为假或只 u 为真 t 为假时上面复合命题为真，而 t,u 同真或同假时，上面复合命题为假，这就达到了表示小元元只能拿一种水果的目的.

当然(2)也可以符号化为 (r\wedge\neg s)\vee(\neg r\wedge s).而(1)则不能符号化为 (p\wedge\neg q)\vee(\neg p\wedge q)，若如此，就排除了王冬梅同时学过日语和俄语的可能.

解读：排斥或能不能直接写成 \vee，取决于两个简单命题是否可能同真。(2) 中生于 1977 与生于 1978 天然互斥，\vee 恰好等价于排斥或；(3) 中"拿苹果"与"拿梨"可以同真，就必须显式写出"恰有一个成立"的形式。

定义 2.4 设 p,q 为两命题，复合命题"如果 p，则 q"称作 p 与 q 的蕴涵式，记作 p\rightarrow q，并称 p 是蕴涵式的前件，q 为蕴涵式的后件，\rightarrow 称作蕴涵联结词.并规定，p\rightarrow q 为假当且仅当 p 为真 q 为假.

p\rightarrow q 的逻辑关系为 q 是 p 的必要条件(p 是 q 的充分条件).

在使用联结词 \rightarrow 时，要特别注意以下几点：

(1) 在自然语言里，特别是在数学中，q 是 p 的必要条件(p 是 q 的充分条件)有许多不同的叙述方式，例如，"只要 p，就 q"，"因为 p，所以 q"，"p 仅当 q"，"只有 q 才 p"，"除非 q 才 p"，"除非 q，否则非 p"，等等.以上各种叙述方式表面看来有所不同，但都表达的是 q 是 p 的必要条件，因而所用联结词均应符号化为 \rightarrow，各种叙述方式都应符号化为 p\rightarrow q.

(2) 在自然语言中，"如果 p，则 q"中的前件 p 与后件 q 往往具有某种内在联系，而在数理逻辑中，p 与 q 可以无任何内在联系.

(3) 在数学或其他自然科学中，"如果 p，则 q"往往表达的是前件 p 为真，后件 q 也为真的推理关系.但在数理逻辑中，作为一种规定，当 p 为假时，无论 q 是真是假，p\rightarrow q 均为真，也就是说，只有 p 为真 q 为假这一种情况，使得复合命题 p\rightarrow q 为假.

解读：\rightarrow 最难接受的是"前件为假时整个蕴涵式为真"。这是人为规定而非推理结论，目的是让 p\rightarrow q 与"q 是 p 的必要条件"完全对齐。凡是"只要/因为/仅当/只有/除非"这类句式，判断谁是谁的必要条件，就能定出前件后件的方向。

例 2.5 将下列命题符号化，并指出各复合命题的真值.

(1) 如果 3+3=6，则雪是白色的.

(2) 如果 3+3\neq 6，则雪是白色的.

(3) 如果 3+3=6，则雪不是白色的.

(4) 如果 3+3\neq 6，则雪不是白色的.

以下命题中出现的 a 是给定的一个正整数.

(5) 只要 a 能被 4 整除，则 a 一定能被 2 整除.

(6) a 能被 4 整除，仅当 a 能被 2 整除.

(7) 除非 a 能被 2 整除，a 才能被 4 整除.

(8) 除非 a 能被 2 整除，否则 a 不能被 4 整除.

(9) 只有 a 能被 2 整除，a 才能被 4 整除.

(10) 只有 a 能被 4 整除，a 才能被 2 整除.

解 令 p：3+3=6，p 的真值为 1.

q：雪是白色的，q 的真值也为 1.

(1)～(4)的符号化形式分别为 p\rightarrow q，\neg p\rightarrow q，p\rightarrow\neg q，\neg p\rightarrow\neg q.这 4 个复合命题的真值分别为 1,1,0,1.

以上 4 个蕴涵式的前件 p 与后件 q 没有什么内在联系.

令 r：a 能被 4 整除.

s：a 能被 2 整除.

仔细分析可知，(5)～(9)这 5 个命题均叙述的是 a 能被 2 整除是 a 能被 4 整除的必要条件，只是在叙述上有所不同，因而都符号化为 r\rightarrow s.由于 a 是给定的正整数，因而 r 与 s 的真值是客观存在的，但是我们不知道.可是 r 与 s 是有内在联系的，当 r 为真(a 能被 4 整除)时，s 必为真(a 能被 2 整除)，于是 r\rightarrow s 不会出现前件真后件假的情况，因而 r\rightarrow s 的真值为 1.

而在(10)中，将 a 能被 4 整除看成了 a 能被 2 整除的必要条件，因而应符号化为 s\rightarrow r.由于 a 能被 2 整除不保证 a 一定能被 4 整除，所以当我们不知道给定的 a 为何值时，也不能知道 s\rightarrow r 会不会出现前件真后件假的情况，因而也不知道 s\rightarrow r 的真值.

定义 2.5 设 p,q 为两命题，复合命题"p 当且仅当 q"称作 p 与 q 的等价式，记作 p\leftrightarrow q，\leftrightarrow 称作等价联结词.并规定 p\leftrightarrow q 为真当且仅当 p 与 q 同时为真或同时为假.

p\leftrightarrow q 的逻辑关系为 p 与 q 互为充分必要条件.

不难看出 (p\rightarrow q)\wedge(q\rightarrow p) 与 p\leftrightarrow q 的逻辑关系完全一致，即都表示 p 与 q 互为充分必要条件.

例 2.6 将下列命题符号化，并讨论它们的真值.

(1) 雪是白色的当且仅当法国的首都是里昂.

(2) n 是奇数的必要且充分条件是 n^2 是奇数.

(3) 若两圆 O_1,O_2 的面积相等，则它们的半径相等.反之，若 O_1,O_2 的半径相等，则它们的面积也相等.

(4) 设角 1 与角 2 是对顶角，则角 1 等于角 2.反之，若角 1 等于角 2，则它们是对顶角.

解 (1) 令 p：雪是白色的.

q：法国的首都是里昂.

(1)中命题符号化为 p\leftrightarrow q.由于 p 为真，q 为假，所以 p\leftrightarrow q 为假.这里，p 与 q 无内在联系.

(2) 令 p：n 是奇数.

q：n^2 是奇数.

(2)符号化为 (p\rightarrow q)\wedge(q\rightarrow p) 或 p\leftrightarrow q，不难证明 p 与 q 同为真或同为假，因而 p\leftrightarrow q 为真.这里，p 与 q 有内在联系.

(3) 令 p：O_1 与 O_2 面积相等.

q：O_1 与 O_2 半径相等.

(3)中命题符号化为 p\leftrightarrow q.真值为 1(p 与 q 真值总相同.p 与 q 有内在联系).

(4) 令 p：角 1 与角 2 是对顶角.

q：角 1 等于角 2.

(4)符号化为 (p\rightarrow q)\wedge(q\rightarrow p) 或 p\leftrightarrow q.由于 p\rightarrow q 为真，而 q\rightarrow p 不一定为真(两相等的角不一定是对顶角)，所以 p\leftrightarrow q 为假.p 与 q 有内在联系.

以上定义了 5 种最基本、最常用、也是最重要的联结词 \neg,\wedge,\vee,\rightarrow,\leftrightarrow，将它们组成一个集合 \{\neg,\wedge,\vee,\rightarrow,\leftrightarrow\}，称为一个联结词集.其中 \neg 为一元联结词，其余的都是二元联结词.对于这个联结词集需要作以下几点说明.

(1) 由联结词集 \{\neg,\wedge,\vee,\rightarrow,\leftrightarrow\} 中的一个联结词联结一个或两个原子命题组成的复合命题是最简单的复合命题，可以称它们为基本的复合命题.为帮助读者记忆，将基本复合命题的取值情况列于表 2.1.

表 2.1

(2) 多次使用联结词集中的联结词，可以组成更为复杂的复合命题.求复杂复合命题的真值时，除依据表 2.1 外，还要规定联结词的优先顺序.将括号也算在内，本书规定的联结词优先顺序为：( )，\neg，\wedge，\vee，\rightarrow，\leftrightarrow，对于同一优先级的联结词，从左到右顺序执行.

例 2.7 令 p：北京比天津人口多.

q：2+2=4.

r：乌鸦是白色的.

求下列复合命题的真值.

① ((\neg p\wedge q)\vee(p\wedge\neg q))\rightarrow r.

② (q\vee r)\rightarrow(p\rightarrow\neg r).

③ (\neg p\vee r)\leftrightarrow(p\wedge\neg r).

解 p,q,r 的真值分别为 1,1,0，容易算出①，②，③的真值分别为 1,1,0.

(3) 从例 2.7 可以看出，今后我们关心的是复合命题中命题之间的真值关系，而不关心命题的内容.

现在，回过头来可以将例 2.2 中的 5 个复合命题完全符号化，它们分别是：\neg p，q\wedge r，q\vee p，s\rightarrow t 和 s\leftrightarrow t.

2.1.2 命题公式及其分类

2.1.1 节中讨论的是简单命题(原子命题)和复合命题，以及它们的符号化形式.由于简单命题是命题逻辑中最基本的研究单位，所以也称简单命题为命题常项或命题常元.从本节开始对命题进一步抽象，首先称真值可以变化的陈述句为命题变项或命题变元.也用 p,q,r,\cdots 表示命题变项，当 p,q,r,\cdots 表示命题变项时，它们就成了取值 0 或 1 的变项，因而命题变项已不是命题.这样一来，p,q,r,\cdots 既可以表示命题常项，又可以表示命题变项，这就需要由上下文确定它们表示的是常项还是变项了.

将命题变项用联结词和圆括号按一定的逻辑关系联结起来的符号串称为合式公式或命题公式.当使用联结词集 \{\neg,\wedge,\vee,\rightarrow,\leftrightarrow\} 中的联结词时，合式公式递归定义如下.

定义 2.6 (1) 单个命题变项和命题常项是合式公式，并称为原子命题公式.

(2) 若 A 是合式公式，则 (\neg A) 也是合式公式.

(3) 若 A,B 是合式公式，则 (A\wedge B)，(A\vee B)，(A\rightarrow B)，(A\leftrightarrow B) 也是合式公式.

(4) 只有有限次地应用(1)～(3)形成的符号串才是合式公式.

合式公式也称为命题公式或命题形式，并简称为公式.

对于定义 2.6，要作以下说明.

(1) 定义中引进了 A,B 等符号，用它们表示任意的合式公式，而不是某个具体的公式，这与 p,p\wedge q,(p\wedge q)\rightarrow r 等具体的公式是有所不同的.前者 A,B 等符号被称作元语言符号，后者被称作对象语言符号.在这里，所谓对象语言是指用来描述研究对象的语言，而元语言是指用来描述对象语言的语言，这两种语言是不同层次的语言.例如，中国人学习英语时，英语为对象语言，而用来学习英语的汉语自然就成了元语言了.在下文的讨论中还要不断地引进元语言符号，用来描述数理逻辑中的公式、论述或推理等.

(2) 为方便起见，(\neg A),(A\wedge B) 等公式单独出现时，外层括号可以省去，写成 \neg A，A\wedge B 等.另外，公式中不影响运算次序的括号可以省去，如公式 (p\vee q)\vee(\neg r) 可以写成 p\vee q\vee\neg r.

由定义可知，(p\rightarrow q)\wedge(q\leftrightarrow r)，(p\wedge q)\wedge\neg r，p\wedge(q\wedge\neg r) 等都是合式公式，而 pq\rightarrow r，(p\rightarrow(r\rightarrow q)) 等不是合式公式.

为了讨论公式的真值变化情况，下面给出公式层次的定义.

定义 2.7 (1) 若公式 A 是单个的命题变项或命题常项，则称 A 为 0 层公式.

(2) 称 A 是 n+1(n\geqslant 0) 层公式是指下面情况之一.

① A=\neg B，B 是 n 层公式.

② A=B\wedge C，其中 B,C 分别为 i 层和 j 层公式，且 n=\max(i,j).

③ A=B\vee C，其中 B,C 的层次及 n 同②.

④ A=B\rightarrow C，其中 B,C 的层次及 n 同②.

⑤ A=B\leftrightarrow C，其中 B,C 的层次及 n 同②.

(3) 若公式 A 的层次为 k，则称 A 是 k 层公式.

上面定义中的＝为普通意义的等号，在这里，它是元语言符号.

易知，(\neg p\wedge q)\rightarrow r，(\neg(p\rightarrow\neg q))\wedge((r\vee s)\leftrightarrow\neg p) 分别为 3 层和 4 层公式.

在命题公式中，由于有命题变项的出现，因而真值是不确定的.当将公式中出现的全部命题变项都解释成具体的命题之后，公式就成了真值确定的命题了.例如，在公式 (p\vee q)\rightarrow r 中，若将 p 解释成：2 是素数，q 解释成：3 是偶数，r 解释成：\sqrt{2} 是无理数，则 p 与 r 被解释成了真命题，q 被解释成假命题了，此时公式 (p\vee q)\rightarrow r 被解释成：若 2 是素数或 3 是偶数，则 \sqrt{2} 是无理数.这是一个真命题.若 p,q 的解释不变，r 被解释为：\sqrt{2} 是有理数，则 (p\vee q)\rightarrow r 被解释成：若 2 是素数或 3 是偶数，则 \sqrt{2} 是有理数.这是个假命题.还可以给出上述公式各种不同的解释，其结果不是得到真命题就是得到假命题.其实，将命题变项 p 解释成真命题，相当于指定 p 的真值为 1，解释成假命题，相当于指定 p 的真值为 0.

定义 2.8 设 p_1,p_2,\cdots,p_n 是出现在公式 A 中的全部的命题变项，给 p_1,p_2,\cdots,p_n 各指定一个真值，称为对 A 的一个赋值或解释.若指定的一组值使 A 的真值为 1，则称这组值为 A 的成真赋值，若使 A 的真值为 0，则称这组值为 A 的成假赋值.

在本书中，对含 n 个命题变项的公式 A 的赋值情况作如下规定.

(1) 若 A 中出现的命题变项为 p_1,p_2,\cdots,p_n，给定 A 的赋值 \alpha_1\alpha_2\cdots\alpha_n 是指 p_1=\alpha_1，p_2=\alpha_2,\cdots,p_n=\alpha_n.

(2) 若 A 中出现的命题变项为 p,q,r,\cdots，给定 A 的赋值 \alpha_1\alpha_2\cdots\alpha_n 是指 p=\alpha_1，q=\alpha_2,\cdots，最后字母赋值 \alpha_n.

上述 \alpha_i 取值为 0 或 1，i=1,2,\cdots,n.

例如，在公式 (\neg p_1\wedge\neg p_2\wedge\neg p_3)\vee(p_1\wedge p_2) 中，000(p_1=0,p_2=0,p_3=0)，110(p_1=1,p_2=1,p_3=0)都是成真赋值，而 001(p_1=0,p_2=0,p_3=1)，011(p_1=0,p_2=1,p_3=1)都是成假赋值.在 (p\wedge\neg q)\rightarrow r 中，011(p=0,q=1,r=1)为成真赋值，100(p=1,q=0,r=0)为成假赋值.

不难看出，含 n(n\geqslant 1)个命题变项的公式共有 2^n 个不同的赋值.

定义 2.9 将命题公式 A 在所有赋值下取值情况列成表，称作 A 的真值表.

构造真值表的具体步骤如下.

① 找出公式中所含的全体命题变项 p_1,p_2,\cdots,p_n(若无下角标就按字典顺序排列)，列出 2^n 个赋值.本书规定，赋值从 00\cdots 0 开始，然后按二进制加 1 依次写出各赋值，直到 11\cdots 1 为止.

② 按从低到高的顺序写出公式的各个层次.

③ 对应各个赋值计算出各层次的真值，直到最后计算出公式的真值.

还必须指出，下文中所谈公式 A 与 B 具有相同的或不同的真值表，是指真值表的最后一列是否相同，而不考虑构造真值表的中间过程.

按照以上步骤，可以构造出任何含 n(n\geqslant 1)个命题变项的公式的真值表.

解读：赋值串的书写顺序固定为"从 00\cdots 0 起按二进制加 1"，所以 n 个变项的赋值一共 2^n 个，最左一位对应按字典序最靠前的那个变项。层次则是"由低到高"逐列计算，先算内层括号里的子公式。

例 2.8 求下列公式的真值表，并求成真赋值和成假赋值.

(1) (\neg p\wedge q)\rightarrow\neg r.

(2) (p\wedge\neg p)\leftrightarrow(q\wedge\neg q).

(3) \neg(p\rightarrow q)\wedge q\wedge r.

解 公式(1)是含 3 个命题变项的 3 层合式公式.它的真值表如表 2.2 所示.

表 2.2

从表 2.2 可知，公式(1)的成假赋值为 011，其余 7 个赋值都是成真赋值.

公式(2)是含 2 个命题变项的 3 层合式公式，它的真值表如表 2.3 所示.从表 2.3 可以看出，该公式的 4 个赋值全是成真赋值，即无成假赋值.

表 2.3

公式(3)是含 3 个命题变项的 4 层合式公式.它的真值表如表 2.4 所示.不难看出，该公式的 8 个赋值全是成假赋值，无成真赋值.

表 2.4

表 2.2～表 2.4 都是按构造真值表的步骤一步一步地构造出来的，这样构造真值表不易出错.如果构造的思路比较清楚，有些层次可以省略.

在例 2.8 中，对于公式(1)，仅当将 p 解释成假命题，而将 q,r 都解释成真命题时，复合命题 (\neg p\wedge q)\rightarrow\neg r 才是假命题，其余情况下复合命题均为真命题.对于公式(2)，无论对 p,q 赋予怎样的解释，所得复合命题都是真命题.而对于公式(3)来说，恰恰相反，无论对 p,q,r 怎样解释，所得复合命题都是假命题.

根据公式在各种赋值下的取值情况，可按下述定义将命题公式进行分类.

定义 2.10 设 A 为任一命题公式.

(1) 若 A 在它的各种赋值下取值均为真，则称 A 是重言式或永真式.

(2) 若 A 在它的各种赋值下取值均为假，则称 A 是矛盾式或永假式.

(3) 若 A 不是矛盾式，则称 A 是可满足式.

从定义不难看出以下几点.

(1) A 是可满足式的等价定义是：A 至少存在一个成真赋值.

(2) 重言式一定是可满足式，但反之不真.若公式 A 是可满足式，且它至少存在一个成假赋值，则称 A 为非重言式的可满足式.

(3) 真值表可用来判断公式的类型.

① 若真值表最后一列全为 1，则公式为重言式.

② 若真值表最后一列全为 0，则公式为矛盾式.

③ 若真值表最后一列中至少有一个 1，则公式为可满足式.

从表 2.2～表 2.4 可知，例 2.8 中，公式(1)(\neg p\wedge q)\rightarrow\neg r 为非重言式的可满足式，公式(2)(p\wedge\neg p)\leftrightarrow(q\wedge\neg q) 为重言式，而公式(3)\neg(p\rightarrow q)\wedge q\wedge r 为矛盾式.

从以上的讨论可知，真值表不但能准确地给出公式的成真赋值和成假赋值，而且能判断公式的类型.

给定 n 个命题变项，按合式公式的形成规则，自然可以形成无穷多种形式各异的公式.现在要问这样的问题：这些公式的真值表是否也有无穷多种不同的情况呢？答案是否定的.n 个命题变项共产生 2^n 个不同的赋值，而任何公式在每种赋值下只能取两个值，0 或 1，于是含 n 个命题变项的公式的真值表只有 2^{2^n} 种不同的情况，因而必有无穷多种公式具有相同的真值表.

命题公式分类：改赋值看真值

解读：三类公式的分界只看真值表最后一列：全 1 是重言式，全 0 是矛盾式，只要出现一个 1 就是可满足式。注意"可满足式"与"重言式"不是并列关系——重言式是可满足式的特例，只有"至少有一个成假赋值"的可满足式才叫非重言式的可满足式。

例 2.9 下列各公式均含两个命题变项 p 与 q，它们中哪些具有相同的真值表？

(1) p\rightarrow q.

(2) p\leftrightarrow q.

(3) \neg(p\wedge\neg q).

(4) (p\rightarrow q)\wedge(q\rightarrow p).

(5) \neg q\vee p.

解 构造过程不写，表 2.5 给出了 5 个公式的真值表.从表中可看出，(1)和(3)具有相同的真值表，(2)和(4)具有相同的真值表.

表 2.5

设公式 A,B 中共含有命题变项 p_1,p_2,\cdots,p_n，而 A 或 B 不全含这些命题变项，比如 A 中不含 p_i,p_{i+1},\cdots,p_n，i\geqslant 2，称这些命题变项为 A 的哑元，A 的取值与哑元的取值无关，因而在讨论 A 与 B 是否有相同的真值表时，可以将 A,B 都看成含 p_1,p_2,\cdots,p_n 的命题公式.

例 2.10 下列公式中，哪些具有相同的真值表？

(1) p\rightarrow q.

(2) \neg q\vee r.

(3) (\neg p\vee q)\wedge((p\wedge r)\rightarrow p).

(4) (q\rightarrow r)\wedge(p\rightarrow p).

解 本例中给出的 4 个公式，共同含有 3 个命题变项，r 是公式(1)中的哑元，p 是公式(2)中的哑元，讨论它们是否有相同的真值表时，均按 3 个命题变项写出它们的真值表.

表 2.6 列出 4 个公式的真值表，中间过程省略了.从表中看出，(1)与(3)有相同的真值表，(2)与(4)有相同的真值表.

表 2.6

解读：比较两个公式的真值表时，必须先补齐"哑元"——把缺的变项补进表头，让两表行数一致再逐行对照。若只按各自出现的变项列表，行数不同就无从比较。