离散数学讲义 武汉科技大学计算机学院
第三章 命题逻辑
重点：掌握数理逻辑中命题的翻译及命题公式的定义；利用真值表技术和
公式转换方式求公式的主析取范式和主合取范式；利用规则、基本等价和蕴涵公式、三种不同的推理方法完成命题逻辑推理；
难点：如何正确地掌握对语言的翻译，如何利用推理方法正确的完成命题
推理。
数理逻辑是用数学方法来研究推理的形式结构和推理规律的数学学科，它与数学的其他分支、计算机学科、人工智能、语言学等学科均有十分密切的联系，并且益显示出它的重要作用和更加广泛的应用前景。要很好地使用计算机，就必须学习逻辑。数理逻辑分五大部分。在离散数学中仅介绍命题逻辑和谓词逻辑。命题逻辑是谓词逻辑的基础，只有掌握了命题逻辑，才能学好谓词逻辑。对于命题逻辑，下面从六个知识点来加以阐述。
3.1 命题符号化及联系结词 1 命题
有确切真值的陈述句称为命题。
所谓确切真值是指在具体的环境，具体的时间，具体的对象，具体的位置等情况下
能唯一确定真值的。命题分为两种：
(1) 简单命题：不能分解为更为简单的句子的命题。 (2) 复合命题：能够分解为更为简单的命题。 2 命题联结词
联结词 记号 复合命题 否定 合取 析取 乛 P是不对的 ∧ ∨ P并且Q P或者Q 读法 P的否定 记法 乛P 真值结果 乛P为真当且仅当P为假 P∧Q为真当且仅当P，Q同为真 P∨Q为真当且仅当P，Q至少一个为真 P与Q的合取 P∧Q P与Q的析取 P∨Q 蕴涵 等价 → 若P，则Q P蕴涵Q P→Q P→Q为假当且仅当P为真，Q为假 ←→ P当且仅当Q P等价于Q P←→ P←→ Q为真当县仅当P，Q同为真假 Q
－3.1－
离散数学讲义 武汉科技大学计算机学院
关于联结词，有如下几点要注意：
（1）此联结词是联结的句子与句子之间的联结，而非单纯的名记号、形容词、数词等的联结；
（2）此联结词是两个句子真值之间的联结词，而非句子的具体含义的联结，两句子之间可以无任何的内在联系；
（3）联结词与自然语言之间的对应并非一一对应，如合取联结词“∧”对应了自然语言中的“既??又??”、“不仅??而且??”、“虽然??但是??”、“并且”、“和”、“与”等。如蕴涵联结词“→”，P→Q对应了自然语言中的“加P则Q”，“只要P就Q”，“P仅当Q”，“只有Q才P”，“除非Q否则乛P”等。如等价联结词“←→ ”对应了自然语言中的“等价”、“并且仅当”、“充分必 ”等。如析取联结词∨是对应相容的或(中兼的或)。
3.2 命题公式及分类
一般称具有确切真值的简单命题叫命题常量，用P，Q，R，?等表示。而没有赋
予具体内容的简单命题称为命题变量（变元），此时的P，Q，R没有具体的真值。
1．合式公式
（1）单个的命题变量或常量（含1或0）是合式公式； （2）若P是合式公式，则（乛P）也是合式公式；
（3）若P，Q是合式公式，则（P∨Q）、（P∧Q）、（P→Q）、（P←→ Q）也是合式公式。 只有有限次使用上述三步形式的符号串才是合式公式（命题公式）“?”，简称公式。 为了简化公式，可按如下优先级别进行：“（）”?“乛”?“?”→ ”
?“→”?“←
其中，为避免错误，合取与析取看成是同等优先级别，要改变或强调其优先级别，
采用括号。另外，最外层的括号可以省掉，同级的按从左到右的顺序进行运算。
2．赋值或解释与真值表
设G是命题公式，P1，P2，?，Pn (n?1)是出现在公式G中的所有命题变元，指定
P1，P2，?，Pn一组真值，则这组真值称为G的一个解释或赋值。此时不同的赋值就有2n种。将此2n种不同的赋值下的取值情况列成的表称为G的真值表。
3．公式的分类 设G为一公式，
（1）如G在它所有的解释之下都为真，则称G为永真或重言式； （2）如G在它所有的解释之下都为假，则称G为永假或矛盾式；
－3.2－
离散数学讲义 武汉科技大学计算机学院
（3）如G在它所有的解释之下至少有一个为真，则称G为可满足式。 3.3 等价公式与演算 1．等价关系
称公式G，H是等价的，如果在其任意的解释下，其真值相同，记为G=H。 说明：G=H仅描述了两公式G，H之间的一种等价的关系，G=H本身并非是一个公
式，它不能作直接计算。
要判断G=H，可采用：G=H当且仅当公式G←→ H 是一个永真式。
2．代入定理
设G(P1，P2，?，Pn)是一个公式，G1(P1，P2，?，Pn)，?，Gn(P1，P2，?，Pn)为任意公式，若G是永真式或永假式，则用G1，G2，?，Gn取代公式G中的P1，P2，?Pn后而得的新公式G(G1，?，Gn)＝G’(P1，P2，?Pn)仍是一个永真式或永假式。
3．运算定律
设G，H，S是任意的公式，则有如下基本的运算定律： （1）幂等律：G∨G＝G，G∧G＝G
（2）结合律：(G∨H)∨S＝G∨(H∨S),（G∧H）∧S＝G∧（H∧S） （3）交换律：G∨H＝H∨G，G∧H＝H∧G
（4）分配律：G∨（H∧S）＝（G∨H）∧（G∨S）， G∧（H∨S）＝（G∧H）∨（G∧S） （5）吸收律：G∨（G∧H）＝G，G∧（G∨H）＝G
（6）同一律：G∨0=G，G∧1=G(0，1分别是关于运行∨，∧的幺元) （7）零 律：G∨1=1，G∧0=0(0，1分别是关于运算∨，∧的零元) （8）排中律，矛盾律：G∨乛G=1，G∧0=0(乛G又叫做G的补元) （9）D，M律：乛(G∨H)=乛G∧乛H，乛(G∧H)=乛G∨乛H （10）双重否定律：乛（乛G）＝G （11）蕴涵等值式：G→H＝乛G∨H
（12）等价等值式：G←→ H＝（G→H）∧（H→G）＝（乛G→H）∧（乛H→G） （13）假言易位：G→H＝乛H→乛G （14）等价否定等值式：G←→ H＝乛G←→ 乛H （15）归谬论：(G←→ H)∧(G←→ 乛H)?乛G
其中：只要将运处“乛”，“∧”，“∨”分别对应集合中的运算“～”，“∩”、“∪”，
－3.3－
离散数学讲义 武汉科技大学计算机学院
真值“1”，“0”分别对应集合中的全集E和空集○，集合对应于命题的公式，则定律(1)～(10)就完全同集合中的定律(1)～(10).另外,(11)～(15)是命题逻辑中特有的公式,重点要求记住(11),(12).
4．等值演算
利用等值定律到已有的公式中而推演出新的公式的过程称为等值演算。 5．置换规则
设G(G1)是含子公式G1的公式，G(G2)是用G2置换了G(G1)之后的公式，若G1＝G2，
则G(G1)＝G(G2)
3.4 全功能联结词集 1．其他联结词
设P，Q为两个命题元，U为其对应的联结词，则U作用于P，Q后的真值表如表2．2
所示。
由组合的意义，U1，U2，U3，U4的不同真值结果有24＝16种，即从0000到1111，
为此除已有的五个联结词以外，还需引入下面四个联结词如表2．3所示。
表中?，↑，↓在逻辑电路中称为异或门，与非门，或非门。
2．全功能联合词集合
设S是联结词集合，用S中的联结词可表示任何的命题公式；且从S中删除任一个
联结词后而得的新联结词集合S1，至少存在一个命题公式不能用S1中联结词表示。则称S是一个全功能联结词集合。
如{乛，∧}，{乛，∨}，{乛，→}，{↑}，{↓}等都是全功能联结词集合。
－3.4－
表 2.2 P Q 0 0 0 1 1 0 1 1 U U1 U2 U3 U4 离散数学讲义 武汉科技大学计算机学院
表 2.3
联结词 记号 复合命题 读法 G异或G不可兼或H H 记法 G?H 真值结果 A?H为真当县仅当G.H不同为真假 异或 ? 蕴涵否定 ? ↑ ↓ G蕴涵否定G与H的蕴涵否定 H G?H G H为真当且仅当G为真，H为假 与非 或非 G与H的与非 G与非H G与H的或非 G或非H G↑H G↓H G↑H为假当且仅当G, H同为真 G↓H为真当且仅当G，H同为假
3.5 范式
1. 析取范式和合取范式
(1) 称命题变元或其否定为文字； (2) 有限个文字的合取称为短语； (3) 有限个文字的析取称为子句； (4) 有限个短词的析取称为析取范式； (5) 有限个子句的合取称为合取范式。
求一个公式G所对应的析取、合取范式一般通过公式的等值演算而得到。 2. 主析取范式和主合取范式
(1) 在含有n个命题变元P1, P2, ?, Pn的公式中，一个短语或一个子句如果恰当包括
所有这n个命题变元或其否定，且排列顺序与P1, P2, ?, Pn一致，则称此短语或子句为关于P1, P2, ?, Pn的一个有小项或极大项。此时极小项有2n个，极大项也有2n个；
(2) 由有限个极小项组成的析取范式称为主析取范式； (3) 由有限个极大项组成的合取范式称为主合取范式。
求一个公式G所对应的主析取、主合取范式可采用真值表技术、公式的等值演
算、公式的主析取与主合取范式之间的转换。其中，最方便、最直观、最不易出错的方法是真值表技术。该方法为：设G（P1, P2, ?, Pn）是一个公式，建立该公式所对应的真值表。
(4) 在真值表中，公式G取值为真的所有行所对应解释之极小项的析取为该公式G
的主析取范式。
(5) 在真值表中，公式G取值为假的所有行所对应解释之极大项的合取为该公式G
的主合取范式。其中，极小项与解释之间的对应为：如P值为0，在极小项中则还原为乛P，
－3.5－