第3章 命 题 逻 辑
本章导引
考虑以下几个问题。
例3-1 一个男士和一个女士在网上聊天，内容如下。
男士：我的第一个问题是，对于我第二个和第三个问题，你可不可以只用“能”和“不能”来回答？
女士：可以。
男士：我的第二个问题是，如果我的第三个问题是你能不能做我的女朋友，那么你对于我的第三个问题的答案能不能和第二个问题的答案一样？
女士：……
例3-2 张三说李四在说谎，李四说王五在说谎，王五说张三和李四都在说谎。请问到底谁说的是真话，谁说的是假话？
例3-3 设计一个控制电路，在房间外、门内及床头分别装有控制电灯的3个开关，要求任意一个开关的开或关可以控制灯的亮与灭。
在实际生活中，经常遇到类似上述的问题。这些问题都有这样一个特点：它们在表达上存在众多约束条件，但已经指向了某一结论。如何提前得到某些结论，似乎已经成了智者的特权。借助逻辑的工具，可以掌握这种特权，成为智者。
3.1 命题与命题联结词
3.1.1 命题
数理逻辑研究的核心是推理，而推理的前提和结论都应是表述明确的陈述句。因此，表述明确的陈述句构成了推理的基本单位，称其为命题，形式化定义如下。
定义3-1 具有确切真值的陈述句称为命题（proposition）。这里指的真值包括“真”和“假”两种，通常情况下用T（1）和F（0）表示。
从该定义可以看出，命题有两个重要性质：①?命题是陈述句，因此疑问句、感叹句和祈使句均不是命题；②?命题具有确切的真值，任何具有二义性的句子都不是命题。如果命题的真值为真，该命题称为真命题；如果命题的真值为假，该命题称为假命题。在通常情况下，命题用大写字母P，Q，R，…或带下标的大写字母P1，P2，…表示。
例3-4 判断下列的句子中哪些是命题，并判断命题的真假。
（1）北京是中国的首都。
（2）抽烟的人均得肺癌。
（3）请把门关上。
（4）1+1=10。
（5）今天的天气真冷呀！
（6）火星上有生命。
（7）下午2点上课吗？
（8）我正在说谎。
（9）如果明天不下雨，我就去上课。
解：
（1）是真值为真的陈述句，因而是真命题。
（2）是真值为假的陈述句，因而是假命题。
（3）是祈使句，因而不是命题。
（4）可以看成“1与1的和是10”，因而是陈述句。在二进制数的运算中，这是一个真命题，而在其他进制的运算中，这是一个假命题。
（5）是感叹句，因而不是命题。
（6）是一个命题，但它的真值目前无法做出判断。
（7）是疑问句，因而不是命题。
（8）是一个陈述句，但它没有明确的真值。因为如果我在说谎，则我说的是真话；如果我说的是真话，那我在说谎。因此，这个句子没有明确的真值，称其为悖论（paradox），它不属于命题的范畴。
（9）是一个陈述句，真值可以根据具体情况判断，因而也是一个命题。
□
在上述的几个命题中，（1）、（2）、（4）、（6）是最简单的陈述句，它们不可能再分解为更简单的命题，因此称它们是原子命题（atom proposition），或简单命题（simple proposition），简称原子（atom）；而（9）可以分解为“明天下雨”和“我去上课”两个更简单的命题，因而（9）不是原子命题，称其为复合命题（compound proposition）。一般地，原子命题通过一些词语可以构成复合命题，这些词语称为联结词（connective），像（9）中的“如果……就……”。常用的联结词有5种，分别是“非”“并且”“或者”“如果……则……”“当且仅当”。
3.1.2 命题联结词
定义3-2 设P是一个命题，复合命题“非P”（或称P的否定），记作P，其中“”是否定联结词（negative connective）。
例3-5 如果P表示命题“2是素数”，则P表示命题“2不是素数”。
P的真值依赖于P的真值，二者的关系如表3-1所示。
表3-1 P和P的真值
P
P
0
1
1
0 从表3-1可以看出，P为真命题，当且仅当P为假命题；P为假命题，当且仅当P为真命题。
定义?3-3 设P和Q是任意两个命题，复合命题“P并且Q”称为P和Q的合取式，记为PQ，其中称为合取联结词（conjunctive connective）。P、Q和PQ的真值关系如表3-2所示。
表3-2 P、Q和PQ的真值关系
P
Q
PQ
0
0
0
0
1
0
1
0
0
1
1
1
从表3-2可以看出，PQ为真，当且仅当P和Q同时为真，反之PQ为假。
例?3-6 设命题P表示“北京是中国的首都”，命题Q表示“2是素数”，则PQ表示“北京是中国的首都，并且2是素数”。由于P和Q都为真命题，因此复合命题PQ也是真命题。
在使用合取联结词时，有两点需要注意。
（1）自然语言中表示语气转折的词语也用合取联结词表示。例如，“虽然天气下雨，但老王还是坚持上班”，用P表示“天气下雨”，Q表示“老王坚持上班”，上述语句可以表示为PQ。
（2）自然语言中的“和”不一定是合取联结词。例如，“张三和李四都上班”，可以表示为“张三上班”和“李四上班”两个命题的合取，而“张三和李四是好朋友”却无法进一步分解，因而“张三和李四是好朋友”是简单命题。
定义3-4 设P和Q是任意两个命题，复合命题“P或者Q”称为P和Q的析取式，记为PQ，其中“”称为析取联结词（disjunctive connective）。P、Q和PQ的真值关系如表3-3所示。
表3-3 P、Q和PQ的真值关系
P
Q
PQ
0
0
0
0
1
1
1
0
1
1
1
1 从表3-3可以看出，PQ为假，当且仅当P和Q同时为假，反之PQ为真。
例3-7 设命题P表示“王梦学过法语”，命题Q表示“王梦学过英语”，则复合命题PQ表示“王梦学过法语或英语”。
需要注意的是，在自然语言中出现的“或者”并不一定都可以表示成“析取”，因为自然语言中的“或者”包括两种：“可兼或”和“不可兼或”。如“王梦学过法语或英语”中的“或”属于“可兼或”，因为“王梦学过法语”和“王梦学过英语”这两件事有可能同时发生。而“王梦或孙娜是我们班的班长”中的“或”属于“不可兼或”，二者显然不可能同时发生。“可兼或”和“不可兼或”有着不同的处理方式。因此需要结合真实的语句对命题中的“或”进行正确的理解。
例3-8 父亲让两个孩子（一男一女）在后院玩耍。在玩的过程中，两个孩子的额头不小心都沾了泥。孩子们回来后，父亲告诉他们，至少有一个人的额头上有泥，然后问他们能否确定自己的额头上有泥。两个孩子都说不能，当父亲第二次再问同样的问题时，两个孩子都说可以。假设每个孩子都能看到对方的额头，但不能看到自己的额头，同时两个孩子都很诚实且同时回答同一个问题，分析两个孩子能做出正确判断的原因。
解：
设P表示男孩的额头有泥，Q表示女孩的额头有泥。父亲告诉至少一人的额头上有泥，即PQ真值为1。当父亲第一次问时，男孩看到女孩的额头有泥，即Q为真，因而男孩无法确定自己的额头是否有泥。当父亲第二次问时，女孩通过第一次提问时男孩的反应，确定了自己的额头有泥。同理，男孩也用同样的方式确定自己的额头有泥。
□
定义?3-5 设P和Q是任意两个命题，复合命题“如果P则Q”称为P和Q的蕴涵式，记作P→Q，其中“→”称为蕴涵联结词（implication connective），P称为蕴涵式的前件，Q称为蕴涵式的后件。P、Q和P→Q的真值关系如表3-4所示。
表3-4 P、Q和P→Q的真值关系
P
Q
P→Q
0
0
1
0
1
1
1
0
0
1
1
1 从表3-4可以看出，P→Q为假，当且仅当为真且Q为假。这里进一步强调一下对蕴涵式P→Q真值的判断，它是命题逻辑推理的精髓所在。如果命题为假命题，则无论Q是真命题还是假命题，P→Q一定是真命题；如果命题Q是真命题，则无论命题为真命题还是假命题，P→Q一定是真命题。
例3-9 设命题P表示“角A和角B是对顶角”，命题Q表示“角A等于角B”，则复合命题P→Q表示“如果角A和角B是对顶角，则角A等于角B”。
定义?3-6 设P和Q是任意两个命题，复合命题“P当且仅当Q”称为P和Q的等价式，记为PQ，其中“”称为等价联结词（equivalence connective）或双蕴涵式。P、Q和PQ的真值关系如表3-5所示。
表3-5 P、Q和PQ的真值关系
P
Q
PQ
0
0
1
0
1
0
1
0
0
1
1
1 从表3-5可以看出，PQ为真，当且仅当P和Q同时为真或者P和Q同时为假。
例3-10 设命题P表示“烟台在山东的东部”，命题Q表示“2是素数”，则复合命题PQ表示“烟台在山东的东部，当且仅当2是素数”。
从上述联结词的定义可以看出，通过命题联结词，可以把毫无关系的两个命题组合成一个新的命题。利用这5个联结词可以构造更复杂的命题；同时也可以把复杂的命题符号化，这个过程称为命题的形式化（formalization）。
例3-11 将下列命题形式化。
（1）他不骑自行车去上班。
（2）虽然天下雨，但他还是骑自行车去上班。
（3）他或者骑自行车去上班，或者坐公交车去上班。
（4）除非天下雨，否则他骑自行车去上班。
（5）他骑自行车去上班，当且仅当天不下雨。
（6）他骑自行车去上班，风雨无阻。
（7）只要天不下雨，他就骑自行车去上班。
（8）只有天不下雨，他才骑自行车去上班。
（9）如果天不下雨，他就骑自行车去上班，否则他就坐公交车去上班。
解：
设P表示他骑自行车去上班，Q表示天在下雨，R表示他坐公交车去上班，S表示天刮风，根据题意，上述命题可以形式化为
（1）P；
（2）PQ；
（3）(PQ)(PQ)；
（4）QP；
（5）PQ；
（6）((QS)(QS)(QS)(QS))P；
（7）QP；
（8）PQ；
（9）(QP)(QR)。
□
这里需要强调的是第（2）题和第（4）题、第（7）题和第（8）题。第（2）题从语义上带有明显的转折，但在逻辑中，二者之间只是并列的关系，因而是二者的合取；第（4）题中的重点在于对“否则”的处理上，它的含义是如果前面的条件不满足，则后面的结论成立。而在（7）和（8）两个题目中，要特别注意“只要……就……”和“只有……才……”的区别。
3.2 命题公式
在研究命题推理时，只考虑命题的真假值，并不在意该命题的具体含义。例如，给定命题P，人们并不关心它代表哪个命题，只关心它的真值是真还是假。如果P没有指定命题，则它的真值有可能是真，也有可能是假，此时称P是命题变元；反之，如果P已经指定了某个具体的命题，则它有了确切的真值，此时称P是命题常量。
如前所述，复合命题是由简单命题与命题联结词构成的。如果把简单命题用命题变元来表示，则该复合命题可以看成命题变元的函数，只不过函数的真值是0或1而已。称这样的复合命题为命题公式，具体定义如下。
定义3-7 命题公式（propositional formula），又称合式公式、公式，可以按照如下的方式递归地定义。
（1）任何命题变元和命题常量是一个命题公式。
（2）如果是命题公式，则（P）也是命题公式。
（3）如果P和Q是命题公式，则（PQ）、（PQ）、（P→Q）、（P?Q）都是命题 公式。
（4）有限次利用上述三条规则得到的串称为合法的命题公式。
进一步，如果命题公式G中只含有n个命题变元P1, P2,…, Pn，称G为n元命题公式，有时也将其表示为G(P1, P2,…, Pn)。
例?3-12 (P→Q)、(P→(PQ))等都是二元命题公式，而((P→Q)→R、(P→)等都不是合法的命题公式。
为了进一步简化命题公式的表示，对命题公式中的圆括号进行进一步的处理，做如下约定。
（1）在5个命题联结词中，按照“否定”“合取”“析取”“蕴涵”“等价”的顺序，运算优先级由高到低；遇到相同优先级的联结词时，按照由左到右的顺序进行。
（2）命题公式最外层的圆括号可以省略。
根据上述约定，命题公式(P→(PQ))可以写成P→PQ，但有时为了避免混淆，通常把P→PQ写成P→(PQ)。
定义?3-8 给定一个元命题公式，设其含有的命题变元是P1, P2,…, Pn，将这n个命题变元指定一组真值，称为命题公式的一个指派或赋值（assignment），通常情况下用I表示。如果一个指派使命题公式真值为真，称其为成真指派，而使命题公式真值为假的指派称为成假指派。
显然，命题公式在指派I下有确切的真值。如果命题公式中含有两个命题变元，则该命题公式有4种不同的指派。一般情况下，如果命题公式中有n个命题变元，则该命题公式应有2n种指派，且该命题公式在所有的指派下都有确切的真值，将命题公式的不同指派以及相应指派下的真值列出来，称为该命题公式的真值表（truth table）。
例3-13 计算下列命题公式的真值表。
（1）P(PQ)。
（2）(PQ)。
（3）。
解：
按照命题公式的构造过程，逐渐构造该命题公式的真值表，分别如下。
（1）命题公式P(PQ)的真值表如表3-6所示。
表3-6 P(PQ)的真值表
Q
PQ
P(PQ)
0
0
0
1
0
1
0
1
1
0
0
0
1
1
1
1 （2）命题公式的真值表如表3-7所示。
表3-7 的真值表
Q
PQ
→
0
0
1
1
1
1
1
0
1
1
0
1
1
1
1
0
0
1
0
0
1
1
1
1
0
0
1
1 （3）命题公式的真值表如表3-8所示。
表3-8 的真值表
Q
PQ
Q)
0
0
1
1
0
1
0
1
1
1
0
1
0
0
1
0
1
0
1
0
1
1
0
0
1
1
0
1
0
0
0
0
□
由该例可以发现，有些命题公式在任何指派下取值永远为真，如例3-13（2），而有些命题公式在任何指派下真值永远为假，如例3-13（3）。根据命题公式在不同指派下真值的不同，将命题公式加以分类。
定义3-9 给定命题公式G，设是出现在该命题公式中的所有命题变元，则有如下定义。
（1）如果该命题公式在所有指派下真值为真，则称该公式为永真式或重言式（tautology）。
（2）如果该命题公式在所有指派下真值为假，则称该公式为永假式或矛盾式（contradiction）。
（3）如果该命题公式在有些指派下真值为真，则称该公式为可满足式（contingence）。
从定义3-9可以看出3种命题公式之间的关系如下。
（1）永真式一定是可满足式。
（2）一个命题公式，如果它不是永真式，它不一定是永假式。
（3）一个命题公式如果不是永假式，则它一定是可满足式。
判断命题公式是否为永真式、永假式或者可满足式，称为命题公式的可判定问题。由于命题公式中指派的数目是有穷的，因此，命题逻辑中公式的可判定问题是可解的，常用的方法有真值表法和公式演算两种。关于利用公式演算来判断命题公式的类型，将在3.3节中介绍。
例3-14 判断下列命题公式的类型。
（1）。
（2）。
（3）。
解：
（1）命题公式的真值表如表3-9所示。
表3-9 的真值表
P
Q
R
Q
PQ
0
0
0
0
0
1
0
1
0
1
1
0
1
1
1
0
1
0
0
1
1
1
1
1
0
0
1
1
1
0
1
0
1
0
1
1
0
0
1
1
1
0
0
1
0
1
1
1 从表3-9可以看出，是可满足式。
（2）命题公式的真值表如表3-10所示。
表3-10 的真值表
P
Q
R
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
1
1
1
1
0
0
1
1
0
0
0
0
1
1
0
0
1
1
0
0
1
1
0
0
0
0
0
0
1
1
0
0
1
1
1
1
1
1
1
1 从表3-10可以看出，公式是永真式。
（3）命题公式的真值表如表3-11所示。
表3-11 的真值表
P
Q
PQ
0
0
1
1
0
1
0
1
1
1
0
1
0
0
1
0
0
0
0
0 从表3-11可以看出，公式是矛盾式。
□
基于真值表，可以对问题可能的解空间进行分析，从而得出问题的正确的解。
例3-15 某个逻辑学家误入一部落，该部落酋长对逻辑学家说：“今有两扇门，一扇为生门，一扇为死门。你可以任意开启一扇门以选择死亡和自由。现派两个人助你选择，这两个人可以回答你提出的任何问题，但这两个人中一个人天性诚实，一个人说谎成性。”逻辑学家深思片刻，即指着一扇门向一个人发问，然后选择一扇门从容离去。试问：该逻辑学家是如何发问的？
分析：在逻辑学家的提问中，需要同时涉及给定的条件：①门是生门或者死门； ②另一个人如何回答。该逻辑学家问其中一个人：“这扇门是死门，他将回答是，对吗？”在该提问中，涉及了两个命题：①被问的人是诚实的；②被提问者回答是。针对这两个基本命题的真假值，列出相应的真值表进行分析，即可以判断出逻辑学家指向的门是生门还是死门。
解：
逻辑学家向其中一个人发问：“这扇门是死门，他将回答是，对吗？”。设P表示被问的人是诚实的，Q表示被提问者回答是。根据分析，会有以下4种情况，如表3-12所示。
表3-12 例3-15的4种情况
P
Q
0
0
0
1
1
0
1
1 对第1种情况，P=Q=0。由于被提问的人是撒谎的，当他回答不是的时候，显然另一个人应回答的真实情况应是“是”，而由于另一个人是诚实的，因而逻辑学家指向的这扇门是死门。
对第2种情况，P=0，Q=1。由于被提问的人是撒谎的，当他回答是的时候，另一个人应回答的真实情况应是“不是”，而由于另一个人是诚实的，因而逻辑学家指向的这扇门是生门。
对第3种情况，P=1，Q=0。由于被提问的人是诚实的，因而另一个人回答的“是”是假的，即另一个人将回答“不是”，而由于另一个人是撒谎的，因而逻辑学家指向的这扇门是死门。
对第4种情况，P=1，Q=1。由于被提问的人是诚实的，因而另一个人回答的“是”是真的，即另一个人将回答“是”，而由于另一个人是撒谎的，因而这扇门不是死门，而是生门。
通过上述分析，当被提问者回答不是的时候，逻辑学家指向的这扇门是死门，当被提问者回答是的时候，逻辑学家指向的这扇门是生门。
□
3.3 命题公式的等值演算
定义3-10 如果两个命题公式G和H含有相同的命题变元，并且这两个命题公式在所有可能的指派下都真值相同，则称这两个命题公式是等价的（equivalent），记为G = H。
如果两个命题公式在任何指派下都真值相同，即G和H同真同假，这意味着等价式G?H是重言式，由此可得下面的定理。
定理3-1 对于公式G和H，G = H的充要条件是公式G?H是重言式。
分析：这是一个充要条件的证明，需要进行充分性和必要性的证明，主要目的是要说明等价式和公式等价之间的关系。
证明：
充分性。如果GH是重言式，I是它的任意解释，则在该解释下，GH为真。因此，命题公式G和H同为真，或者二者同为假。由于I的任意性，因此有G = H。
必要性。如果G = H，则G和H在任意解释下都同为真或同为假。根据等价运算“”的定义，GH在任意解释下都为真，即GH为永真式。
□
这个定理的证明过程看起来非常简单，但它的意义非常重大。根据该定理，可以建立许多命题公式之间的等价性。利用这种等价性，可以在命题公式上进行类似四则运算的演算，称为等值演算（equivalent calculus）。
定理3-2 设G, H, S为任意的命题公式，则下列公式的等价式成立。
（1）结合律：，。
（2）交换律：，。
（3）幂等律：，。
（4）吸收律：，。
（5）分配律：，。
（6）同一律：，。
（7）零律：，。
（8）排中律：。
（9）矛盾律：。
（10）双重否定律：。
（11）德摩根①律：，。
（12）等价式：。
（13）蕴涵式：。
（14）假言易位：。
对于上述公式的证明，可以借助命题公式的真值表进行判断，此处略。
在定理3-2中涉及的公式中，结合中学阶段学习的集合之间的运算，并不是很难理解。这里需要进一步强调的是公式（13），它将蕴涵关系与析取关系建立了等价性，在后续的学习中，会经常接触到这种等价性。
在等值演算中，定理3-2中的所有公式都可以直接应用。除了这些公式以外，还有两个重要的定理。
定理3-3（代入规则）??设命题公式是永真式（或永假式），设是出现在其中的命题变元。将其中某一个命题变元用另一个命题公式代入后，所得到的新的命题公式仍然是永真式（或永假式）。
例3-16 公式是永真式，则将其中出现的命题变元Q用命题公式替换，所得到的新公式仍然是永真式。
定理3-4（替换规则）??设命题公式G中包含子公式H，如果将子公式H换成与其等价的公式，得到的新公式与公式G等价。
例3-17 给定命题公式，从该公式的构成可以看出，是它的子公式。在定理3-2中得知，与是等价的，将其代入，得到的新公式与原公式是等价的。
例3-18 利用公式的等值演算来判断例3-13中的3个命题公式的类型。
（1）。
（2）。
（3）。
解：
（1）对该式进行等值演算，如下：
从演算的结果可以判断出，该命题公式既不是永真式，也不是永假式，它是一个可满足式。
（2）演算过程如下：
从演算结果看，该公式为永真式。
（3）演算过程如下：
从演算结果看，该公式为永假式。
□
需要说明的是，利用公式演算，不仅可以在命题公式之间建立等价关系，还可以直接用在电子线路设计、程序设计和社会生产生活的方方面面。
例3-19 将下面的程序进行化简。
If A then if B then X else Y else if B then X else Y
解：
根据题意，画出该程序的流程图，如图3-1所示。
图3-1 程序的流程图
从该程序流程图可以看出，程序最终的出口有两个，分别是X和Y，二者的执行条件分别为
X：A = B = T，或A = F，B = T
Y：A = T，B = F，或A = B = F
运用命题逻辑进行化简，得
X：???????
Y：
因此，执行X的条件是B为真，执行Y的条件是B为假。因此，程序可以简化为
If B then X else Y
□
在数字电路中，存在3种基本的门电路：与门、或门和反相器，对应的逻辑关系如图?3-2所示。
与门
A
B
Y
0
0
0
0
1
0
1
0
0
1
1
1
或门
A
B
Y
0
0
0
0
1
1
1
0
1
1
1
1
反相器
A
Y
0
1
0
0
图3-2 基本的门电路及其真值表对应关系
从上述3个门电路的真值表中可以看出，与门实现的基本功能与合取一致，或门实现的基本功能与析取一致，反相器的逻辑功能与否定一致。根据这种有效性，可以利用命题公式的等值演算对数字电路进行简化。
例3-20 简化图3-3所示的逻辑电路。
解：
根据图3-3中所示的逻辑关系，得到输出与输入的逻辑关系为
对该公式进行化简，得
根据化简后的公式，上述电路可简化为图3-4中的电路。
图3-3 例3-20中的逻辑电路图3-4 化简后的电路
□
3.4 命题联结词的完备集
前面介绍了5个常用的命题联结词，分别是否定、合取、析取、蕴涵和等价。现在回顾一下，联结词究竟是什么？为什么这5个联结词互不相同？还可以构造多少个不同的联结词？本节将针对这些问题给出准确的答案。
在前面的5个联结词中，它们之所以不同，是因为不同的命题变元通过不同的联结词得到的结果不同。从这点考虑，命题联结词本质上就是一个函数，与实数函数不同的是，函数的定义域和值域只能取逻辑中的真值（真或假）。下面讨论在给定两个命题变元的情况下，可以构造多少个不同的联结词。
根据前面的分析，命题联结词本质上是一个函数。即对输入的任意情况，都会有唯一的、确切的真值与其对应。当给定两个命题变元时，输入一共有?4?种情况，如表?3-13所示。
表3-13 包含两个命题变元的联结词
P
Q
f?(P,Q)
0
0
*1
0
1
*2
1
0
*3
1
1
*4 从表3-13可以看出，如果对任意输入而言，两个联结词的输出是相同的，则这两个联结词是等价的；反之，如果两个联结词对应着不同的输出，则两个联结词是不同的。换句话说，给定两个命题变元时，命题联结词就是针对真值表中对应的4行，给出相应的函数值。由于函数值只能是0或1，因此，共可以构造24 = 16个不同的联结词，如表3-14所示。
表3-14 两个命题变元对应的所有联结词真值
P
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
1
0
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
1
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1 根据不同的联结词对应的真值表，可以在5个基本联结词的基础上得到上述联结词的描述，如下：
从上述16个不同的联结词的描述可以看出，不同的联结词之间可以相互转换。由此产生了一个问题，为了表达所有的命题联结词，至少需要多少个命题联结词？这样的问题被称为命题联结词的完备集问题，形式化定义如下。
定义3-11 设S是某些联结词的集合，如果满足以下两个条件，S称为一个联结词完备集（adequate set of connectives）。
（1）用S中的联结词可以表达所有的联结词。
（2）从S中删除任意一个命题联结词，至少会存在一个联结词，无法用剩余的联结词表示。
例3-21 在前面给出的5个基本联结词中，可以进行如下转换：
PQ =
从上述3个式子可以看出，蕴涵、合取和等价可以用否定和析取表示，而这两个联结词无法相互表示，因此，集合是一个命题联结词的完备集。同理，也是一个命题联结词的完备集。
例3-22 将公式用命题联结词完备集表示出来。
解：
□
除上述联结词外，命题逻辑中还有异或（）、与非（）、或非（），相关联结词的真值表如表3-15所示。
表3-15 其他联结词的真值表
P
Q
0
0
1
1
0
1
0
1
0
1
1
0
1
1
1
0
1
0
0
0 由表3-15可知，上述联结词有如下性质。
（1）。
（2），。
（3），。
例3-23 证明{}是联结词完备集。
分析：在例3-21中，已经证明和是联结词的完备集，因此，如果可以用与非联结词表示否定联结词和合取联结词，即可证明。
证明：
根据与非联结词的性质，可知：
???????????????????????
由于是联结词完备集，因此{}是联结词的完备集。
同理可证：也是联结词的完备集。
□
3.5 范式
从命题公式的演算可以看出，同一个命题公式之间可能有多种表示形式，而这几种不同的表示形式之间是等价的。在等值演算中，同一命题公式的不同表示形式会带来诸多不便。因此从理论上讲，有必要对命题公式的表示形式进行规范，使命题公式规范化。为此，引入命题公式的范式这一概念。在命题公式的范式表示中，包括析取范式、合取范式、主析取范式和主合取范式等几种表示形式，这些表示形式在电子线路设计、人工智能等领域具有极其重要的意义。
3.5.1 析取范式和合取范式
定义3-12 （1）命题变元或命题变元的否定称为文字（literal）。
（2）有限个文字的析取称为子句（clause），有限个文字的合取称为短语（phrase）。
（3）有限个短语的析取式称为析取范式（disjunctive normal form），有限个子句的合取称为合取范式（conjunctive normal form）。
从析取范式和合取范式的定义中可以看出，二者只包含3种命题联结词：否定、合取和析取，并且否定联结词只能在命题变元的前端。
例3-24 已知命题变元P、Q，则有
（1）是文字、子句、短语、合取范式、析取范式。
（2）是子句、析取范式、合取范式。
（3）是短语、析取范式、合取范式。
（4）是析取范式。
（5）是合取范式。
□
给定任意命题公式，如何将其转化成等价的析取范式和合取范式呢？通常情况下，按照如下思路进行。
（1）将命题公式中的联结词和用、和表示。
（2）运用德摩根律将否定联结词移至命题变元的前端。
（3）运用结合律、分配律、吸收律和幂等律等将公式化成与其等价的析取范式或合取范式。
例3-25 求公式的析取范式和合取范式。
解：
该公式的合取范式为
该公式的析取范式为
□
需要说明的是，同一命题公式可能会有不同形式的合取范式和析取范式，这种不唯一给后续问题的处理带来了诸多不便，下面引进更为标准的范式表示。
3.5.2 主析取范式和主合取范式
定义3-13② （1）给定n个命题变元，一个短语或子句，如果恰好包含这n个命题变元或其否定，并且每个命题变元或其否定仅出现一次，称该短语或子句为关于的一个最小项（minterm）或最大项（maxterm）。
（2）有限个最小项的析取称为主析取范式（principal disjunctive normal form）。
（3）有限个最大项的合取称为主合取范式（principal conjunctive normal form）。
例3-26 给定两个命题变元P和Q，可以构造的最小项和最大项分别如下。
最小项：、、、。
最大项：、、、。
对于任何一个命题公式而言，都存在与其等价的主析取范式和主合取范式。如果一个命题公式不包含任何最小项，则称该命题公式的主析取范式为空；如果一个命题公式中不包含任何最大项，则称该命题公式的主合取范式为空。目前求取命题公式的主析取范式和主合取范式主要有两种方法：真值表法和公式演算法。下面通过分析最大项、最小项的性质来介绍这两种方法。
1. 最小项和最大项的性质
为了研究最小项和最大项的性质，首先列出包含两个命题变元的最小项与最大项的真值表，所有最小项的真值表如表3-16所示。
表3-16 包含两个命题变元的所有最小项的真值表
P
Q
0
0
1
0
0
0
0
1
0
1
0
0
1
0
0
0
1
0
1
1
0
0
0
1 从表3-16可以看出，最小项有如下性质。
（1）不存在两个等价的最小项。对任意两个不同的最小项，在不同的指派下真值不完全相同。
（2）对任意最小项，只有一个指派使其真值为真，而该指派必使其他最小项真值为假；对任一指派，只存在一个最小项真值为真，而其他最小项在该指派下真值为假。因此，最小项与使其真值为真的指派是一一对应的，通常情况下用使其真值为真的指派作为该最小项的编码。例如，用（或）表示最小项，用（或）表示最小项。
（3）任意两个不同最小项的合取为矛盾式，所有最小项的析取为重言式。
同理，列出包含两个命题变元的所有最大项的真值表，如表3-17所示。
表3-17 包含两个命题变元的所有最大项的真值表
Q
0
0
0
1
1
1
0
1
1
0
1
1
1
0
1
1
0
1
1
1
1
1
1
0 类似地，从表3-17可以看出，最大项有如下性质。
（1）不存在两个等价的最大项，任意两个不同的最大项在不同的指派下真值不完全相同。
（2）对任意一个最大项，只有一个指派使其真值为假，而该指派必使其他最大项真值为真；对任一指派，只存在一个最大项真值为假，而其他最大项在该指派下真值为真。最大项与使其真值为假的指派是一一对应的，通常情况下用使其真值为假的指派作为该最大项的编码。例如，用（或）表示最大项，用（或）表示最大项。
（3）任意两个不同最大项的析取为永真式，所有最大项的合取为矛盾式。
2. 公式演算法
运用公式演算求取命题公式的主析取范式和主合取范式是基于以下的公式演算。
（1）。
（2）。
从上述两个基本的公式演算可以看出，从公式的析取范式和合取范式计算主析取范式和主合取范式时，如果析取范式（或合取范式）的某个短语（子句）中缺少某个命题变元，则可以采用上述公式将缺少的命题变元加进去。
例3-27 运用公式演算法计算命题公式的主合取范式和主析取范式。
解：
首先计算该命题公式的合取范式。
在合取范式的基础上，利用分配律，计算该公式的析取范式。
下面在合取范式的基础上计算主合取范式。在该命题公式的合取范式中，第一个子句中缺少命题变元Q，第二个子句中缺少命题变元P，通过公式演算，可得
???????????????????????
因此有
类似地，在析取范式的基础上计算主析取范式。在析取范式的后两个短语中，分别缺少命题变元Q和命题变元P。运用公式演算，可得
?????????????????????????????????????????????????????????????
因此有
□
3. 真值表法
真值表法是主析取范式和主合取范式的主要构造方法之一，在逻辑电路设计中具有非常重要的应用价值。下面通过例题来说明真值表法构造主析取范式和主合取范式的基本原理。
例3-28 用真值表法求命题公式的主合取范式和主析取范式。
解：
首先列出该命题公式的真值表，如表3-18所示。
表3-18 命题公式的真值表
P
Q
R
PQ
G
0
0
0
1
0
0
0
1
1
1
0
1
0
1
0
0
1
1
1
1
1
0
0
0
1
1
0
1
0
0
1
1
0
1
0
1
1
1
1
1 假设命题公式G的主合取范式为，其中圆括号里的内容为最大项。根据最大项的性质，有且仅有一组指派使某一最大项真值为0，其他指派均使其真值为1。考虑主合取范式从整体上来讲是合取式，其真值为0，当且仅当其包含的某个最大项取值为0。因此，使G取值为0的指派所对应的最大项必须包含在G的主合取范式中（如果不包含，则G的真值必然为1）。同时，使G真值为1的最大项不应包含在G的主合取范式中，因为一旦出现，会使G的真值为0。因此，G的主合取范式中应包含使G真值为0的那些指派所对应的最大项，而且只包含这些最大项。以该题为例，使G真值为0的指派分别是000、010、101和110，它们对应的最大项分别为、、和，即G的主合取范式为
类似地，在计算命题公式G的主析取范式时，不妨设G的主析取范式为，其中圆括号里的内容为最小项。根据最小项的性质，有且仅有一组指派使其真值为1，而其他指派均使其真值为0。由于主析取范式从整体上看是析取式，因此，使命题公式G真值为1的指派所对应的最小项必须出现在G的主析取范式中（如果不出现，则G的真值必然为0）。同时，G的主析取范式中不应包含那些使G真值为0的最小项，它们的出现会使G的取值为1。因此，G的主析取范式中只包含使G真值为1的那些指派所对应的最小项。以该题为例，首先从真值表中获取使G真值为1的那些指派，分别是001、011、100、111，它们对应的最小项分别为、、和，即的主析取范式为