离散数学东北大学信息学院计算机系许桂清版权所有 侵权必究绪 论
离散数学的性质、内容
学习此课的目的
学习此课的方法一,此课的性质、内容：
数学所 研究的对象 根据它们的取值分为：
连续的,如长度、温度、面积等。
离散的,如商店商品，学生所学课程等。
离散数学 是研究离散对象的结构以及它们之间相互关系的科学。
因为计算机不论硬件还是软件都属于离散结构，所以它所应用的数学必是离散数学。
性质,此课 是计算机科学与技术专业的重要的理论 基础课,也是该专业的 主干课 。
内容,1,数理逻辑
2,集合论
3,代数系统
4,图论
*5,组合数学
*6,形式语言与自动机
(由于时间的关系，我们只讨论前四部分内容。 )
二,学习此课的目的,
1.计算机的诞生与发展和离散数学密切相关
正如马克思所说的：“一门科学，只有当它能够运用数学时，才算真正发展了。”
计算机正是在离散数学 中的图灵机的理论指导下诞生的
(1936提出图灵机 ---1946诞生计算机 )。
计算机科学的发展十分迅速，计算机的硬件从第一代起现在发展到第四代 (电子管?晶体管?集成电路?大规模集成电路 )，第五代即将问世，正在向网络化发展。而且计算机技术发展速度越来越快。
计算机应用越来越广，所有领域几乎无所不及。
计算机科学已发展成为一门一级学科。
计算机的产业已发展成为一个高科技的新兴产业
计算机科学的发展 (硬件、软件的发展 )离不开计算机的理论,例如，程序设计语言的发展,从机器语言?
汇编语言?高级面向过程语言?面向对象语言?智能语言?…,系统软件的发展,如操作系统，从单用户
多用户?网络操作系统,…,即如 DOS
Windows? Windows NT?...; 所有这些发展都依赖于离散数学、数据结构、编译原理、操作系统、数据库原理、软件工程、网络等理论。其中离散数学是基础，其它的理论中都用到了离散数学中的基本概念、
基本思想、基本方法。
这说明了理论常常可以导致实践方面的重大进展，即理论对实践的指导作用。
计算机专业的学生学习计算机不同于非计算机专业的学生学习计算机，必须掌握离散数学的理论，才能更好地了解和从事计算机科学的研究。
2.此课是主干课，也是后继课的基础课计算机专业的后续课中都大量地应用到离散数学中的基本理论，所以要想学好专业课，必须先学好离散数学。
3.培养学生抽象的思维和逻辑推理能力和创新能力在大学学习知识很重要，但是能力的培养更重要。正如著名的物理学家劳厄所说：,重要的不是获得知识，
而是发展思维能力。教育无非是一切已学过的东西都遗忘的时候，所剩下来的东西。,剩下的就是思维能力，它可以长期起作用。
正如北京大学姜伯驹教授谈到数学时说：“数学是学习科学技术的钥匙和先决条件。”所以必须提高学生的数学修养 (数学素质 )。 数学修养 包括：理解、抽象、见识、体验。
理解能力,逻辑推理能力、不同语言对应的转换能力、
想象能力等。
抽象能力,敏锐的洞察力，灵活的联想类比、举一反三能力，特别是把实际问题转化为数学问题的能力。
见识,就是让学生见识一些重要的数学思想、数学方法以及用数学解决实际问题的著名事例。有了这样见识才会思路宽，办法多，遇到问题会自觉求助于数学。
体验,数学是一种分析问题、解决问题的实践活动。与打猎一样是活本领。像转换观点、选择方法、熟悉软件、
检验结果、发现毛病、查找原因多环节只有亲身经历才能学到手。
学到这些活本领，就是一些基本素质问题。
离散数学可以帮助学生提高数学素质。提高创造力。
三,此课的特点及学习方法,
特点,内容较杂，概念多，定理多，比较抽象，给学习带来一定难度。
学习方法,
1.准确掌握每个概念 (包括内涵及外延 )。
2.要有刻苦钻研精神,不断总结经验。
3.在理解内容的基础上，要较多地做些习题，从而再进一步加深理解所学内容。
4.注意培养分析问题和解决问题的能力第一篇 数理逻辑
逻辑 --是研究人的思维的科学。
它包含：
1.辩证逻辑,是研究人的思维中的辩证法。
例 如：用全面的和发展的观点观察事物；
具体问题具体分析；
实践是检查事物正误的唯一标准；等等。
2.形式逻辑,是研究人的思维的形式和一般规律。
这里我们只关心形式逻辑。
一,形式逻辑
人的思维过程：
概念? 判断? 推理
正确的思维：
概念清楚，判断正确，推理合乎逻辑。
人们是通过各种各样的学习 (理论学习和从实践中学习 )来掌握许多概念和判断。
而形式逻辑主要是研究推理的 。
推理：
是由若干个已知的判断 (前提 )，推出新的判断 (结论 )的思维过程。
推理方法
类比推理,由个别事实推出个别结论 。
如：地球上有空气、水，地球上有生物。
火星上有空气、水。
火星上有生物 。
归纳推理,由若干个别事实推出一般结论。
如：铜能导电。铁能导电。锡能导电。铅能导电。 ……
一切金属都导电 。
演绎推理,由一般规律推出个别事实。
形式逻辑主要是研究演绎推理的。
演绎推理 举例
例 1：
如果天下雨，则路上有水。 (一般规律 )
天下雨了。 (个别事实 )
推出结论,路上有水。 (个别结论 )
例 2：
(大前提 )：所有金属都导电。 (一般规律 )
(小前提 )：铜是金属。 (个别事实 )
推出结论,铜能导电。 (个别结论 )
二,数理逻辑
数理逻辑 是用 数学的方法 研究形式逻辑。
所谓“数学方法”：是建立一套有严格定义的符号，即建立一套形式语言，来研究形式逻辑。所以数理逻辑也称为,符号逻辑,。
它与数学的其它分支、计算机科学、人工智能、语言学等学科均有密切联系。
这里只讨论,命题逻辑,和,谓词逻辑,。
下面就前面两个例子，说明如何将推理符号化的。
数理逻辑把推理符号化之一
设 P表示：天下雨。
设 Q表示：路上有水。
设?表示,如果 … 则 …
例 1的推理过程表示为：
前提 1:P?Q (如果天下雨,则 路上有水 。 )
前提 2,P (天 下雨了。 )
结 论,Q (路上有水 。 )
(这就是第一章命题逻辑中要讨论的问题 )
数理逻辑把推理符号化之二
设 M(x),x是金属,设 C(x),x能导电,
设?x 表示,所有的 x,设 a 表示铜,
例 2的推理过程表示为：
前提,?x(M(x)?C(x)) (所有金属都导电,)
前提,M(a) (铜是金属,)
结论,C(a) (铜能导电,)
(其中符号 M(x)是谓词，所以这就是第二章“谓词逻辑”中所讨论的内容,）
使用计算机必须首先学会编“程序”，那么什么是程序？
程序＝算法＋数据算法＝逻辑＋控制可见“逻辑”对于编程序是多么重要。要想学好、使用好计算机，必须学习逻辑，此外，通过学习逻辑，掌握逻辑推理规律和证明方法,会培养学生的逻辑思维能力，提高证明问题的技巧。
数理逻辑与计算机钱学森谈“计算机与数理逻辑”
电子计算机与数理逻辑具有非常密切的关系。正是在数理逻辑中，把人类的推理过程分解成一些非常简单原始的、非常机械的动作，才使得用机器代替人类的推理的设想有了实现的可能。
有了电子计算机，使用它时，必须先进行程序设计，把整个推理、计算过程，丝毫不漏地考虑到，统统编入程序，
而机器则依次而运行；如稍有错误，将立即得到毫无意义的结果。可见必须有足够的数理逻辑的训练，熟悉推理过程的全部细节,
才能从事程序设计。
此外，程序设计是一个很细致又很麻烦的工作，如何从事程序设计，如何防止在计算过程中出错，如何很快地发现这种错误而及时加以改正，都是程序设计理论 (软件理 )中非常根本又非常重要的内容，大家都认为，
这些内容都与数理逻辑息息相关。
正如著名的计算机软件大师戴克斯特拉 (E.W.Dijkstra)曾经说过,我现在年纪大了，搞了这么多年软件，错误不知犯了多少，现在觉悟了。我想，假如我早在数理逻辑上好好下点功夫的话，我就不会犯这么多错误。不少东西逻辑学家早就说过了，可是我不知道。要是我能年轻 20岁的话，我就会回去学逻辑。
第一章 命题逻辑
这章是以,命题,为中心
主要讨论：
命题的表示、命题的演算
命题演算中的公式，及其应用
命题逻辑推理
1-1,命题与命题的真值
本节主要讨论三个问题：
命题的概念
命题的真值
原子命题与复合命题一,命题的概念
命题 是一个能确定是真的或是假的判断。（判断都是用陈述句表示）
例 1-1.1 判定下面这些句子哪些是命题。
⑴ 2是个素数。
⑵ 雪是黑色的。
⑶ 2005年人类将到达火星。
⑷ 如果 a>b且 b>c，则 a>c。
⑸ x+y<5
⑹ 请打开书！
⑺ 您去吗？
⑴⑵⑶⑷是命题二,命题的真值
一个命题所作的判断有两种可能,是正确的 判断或者 是错误的 判断 。 所以一个命题的 真值 有两个：,真,或,假,
真值 为 真,一个命题所作的判断与客观一致,
则称该命题的真值为真,记作 T (True)。
真值 为 假,一个命题所作的判断与客观不一致,则称该命题的真值为假,记作 F (False)。
例 1-1.1中 (1)(4)的真值为 真,(2)的真值为 假,
(3)暂时不能定，等到 2005年确定。
三,原子命题与复合命题
简单命题 (原子命题 ),由最简单的陈述句构成的命题 (该句再不能分解成更简单的句子了 )。通常用大写英字母表示。
例 1-1.1中的 (1),(2),(3)是原子命题。
复合命题 (分子命题 ),由若干个原子命题构成的命题。
例 1-1.1中的 (4)是由三个原子命题 (a>b、
b>c,a>c)构成的复合命题。
1-2 联结词
复合命题的构成：是用“联结词”将原子命题联结起来构成的。
归纳自然语言中的联结词，定义了六个逻辑联结词，分别是：
(1) 否定,?” (2) 合取,∧,
(3) 析取,∨,(4) 异或,”
(5) 蕴涵,?” (6) 等价,?”
一,否定,?”
表示：,… 不成立,，,不 …,。
用于：对一个命题 P的否定，写成?P,并读成,非 P”。
P的真值：与 P真值相反。
例 1-2.1 P,2是素数。
P,2不是素数。
P?P
T F
F T
二,合取,∧,
表示：,并且,、,不但 … 而且,..”、
,既 … 又,..”“尽管 … 还 …,
例 1-2.2 P：小王能唱歌。
Q：小王能跳舞。
P∧ Q：小王能歌善舞。
P∧ Q读成 P合取 Q。
P∧ Q的真值为 真,当且
仅当 P和 Q的真值均为 真 。
P Q P∧ Q
F F F
F T F
T F F
T T T
三,析取,∨,、异或,”
表示,或者,
,或者”有 二义性,看下面两个例子：
例 1-2.3,灯泡 或者 线路有故障。
例 1-2.4,第一节课上数学 或者 上英语。
例 3中的 或者 是 可兼取的或 。即 析取,∨,
例 4中的 或者 是 不可兼取的或,也称之为异或,排斥或 。即,”,?
1,析取,∨,
P：灯泡有故障。
Q：线路有故障。
例 3中的复合命题可
表示为,P∨ Q，读
成 P析取 Q,P或者 Q。
P∨ Q的真值为 F，当
且仅当 P与 Q均为 F。
P Q P∨ Q
F F F
F T T
T F T
T T T
2,异或,”
P,第一节上数学 。
Q,第一节上英语。
例 4中的复合命题可写成 P Q,读成 P异或 Q。
P Q的真值为 F，
当且仅当 P与 Q的 真值相同 。
F F F
F T T
T F T
T T F
P Q P Q?
3.异或的另一种表示
异或 是表示两个命题 不可能同时都成立。
命题“第一节课上数学 或者 上英语。”可以解释为：
“第一节课上数学而没有上英语 或者 第一节课上英语而没有上数学。”
于是有
P Q 与 (P∧?Q)∨ (Q∧?P ) 是一样的。
实际应用中必须注意,或者,的二义性。
四,蕴涵 (条件 ),?”
表示“如果 … 则 …”,
例 1-2.5,P表示：缺少水分。
Q表示：植物会死亡。
P?Q：如果 缺少水分,植物就会死亡 。
P?Q：也称之为蕴涵式，读成,P蕴涵
Q”，“如果 P则 Q”。也说成 P是 P?Q 的前件,Q是 P?Q的后件。还可以说 P是 Q
的充分条件,Q是 P的必要条件。
P?Q的真值,
P?Q的真值为假，当且仅当 P为真,Q为假。 注意,当前件 P为假时,P?Q为 T。
P Q P?Q
小王借钱不还 我替他还 （我给小王担保）
F F T
F T T
T F F
T T T
充分条件,就是只要条件成立，结论就成立，
则该条件就是 充分条件 。
上例中，,缺少水分”就是“植物会死亡”
的充分条件。在自然语言中表示充分条件的词有,如果 … 则 …,只要 … 就 …,若 … 则 …
必要条件,就是如果该条件不成立，那么结论就不成立,则该条件就是 必要条件 。
上例中，,植物死亡”就是“缺少水分”的必要条件 (植物未死亡，一定不缺少水分 )。
在自然语言中表示必要条件的词有,
只有 … 才 … ； 仅当 …,… ; …,仅当 … 。
关于充分条件和必要条件的说明：
举例,
令,P：天气好。 Q：我去公园。
1.如果天气好，我就去公园。
2.只要天气好，我就去公园。
3.天气好，我就去公园。
4.仅当天气好，我才去公园。
5.只有天气好，我才去公园。
6.我去公园，仅当天气好。
命题 1.,2.,3.写成,P?Q
命题 4.,5.,6.写成,Q?P
可见,?”既表示充分条件（即前件是后件的充分条件）；
也表示必要条件（即后件是前件的必要条件）。这一点要特别注意 !!!它决定了哪个作为前件，哪个作为后件。
五,等价 (双条件）,?”
表示“当且仅当”、“充分且必要”
例 1-2.6：
P,⊿ ABC是等边三角形。
Q,⊿ ABC是等角三角形。
P?Q,⊿ ABC是等边三角形 当且仅当它 是等角三角形。
P Q P?Q
F F T
F T F
T F F
T T T
P?Q的真值,
P?Q的真值为真，当且仅当 P与 Q的真值相同。
本节小结：
要熟练掌握这五个联结词在自然语言中所表示的含义以及它们的真值表的定义。
P Q P∧ Q P∨ Q P?Q P?Q
F F F F T T
F T F T T F
T F F T F F
T T T T T T
特别要注意“或者”的二义性，即要区分给定的“或”是“可兼取的或”还是
“不可兼取的或”。
特别要注意,?”的用法，它既表示
“充分条件”也表示“必要条件”，即要弄清哪个作为前件，哪个作为后件。
练习：填空
已知 P∧ Q为 T，则 P为 ( ),Q为 ( )。
已知 P∨ Q为 F，则 P为 ( ),Q为 ( )。
已知 P为 F，则 P∧ Q为 ( )。
已知 P为 T，则 P∨ Q为 ( )。
已知 P∨ Q为 T，且 P为 F,则 Q为 ( )。
已知 P?Q为 F，则 P为 ( ),Q为 ( )。
已知 P为 F，则 P?Q为 ( )。
已知 Q为 T，则 P?Q为 ( )。
已知?PQ为 F，则 P为 ( ),Q为 ( )。
已知 P为 T,P?Q为 T，则 Q为 ( )。
已知?Q为 T,P?Q为 T，则 P为 ( )。
已知 P?Q为 T,P为 T,则 Q为 ( ).
已知 P?Q为 F,P为 T,则 Q为 ( ).
P?P 的真值为 ( ).
P?P 的真值 为 ( )。
1-3 命题公式及命题符号化一,常值命题与命题变元
常值命题,即是我们前面所说的命题。它是有具体含义 (真值 )的。例如：,3是素数。”就是常值命题。
命题变元,用大写的英字母如 P,Q等表示任何命题。称这些字母为命题变元。
对命题变元作 指派 (给命题变元一个 解释 )：将一个常值命题赋予命题变元的过程，或者是直接赋给命题变元真值,T”或,F”的过程。
注意,命题变元本身不是命题，只有给它一个解释，才变成命题。
二,合式公式 ( wff ) (well formed formulas)
1.定义：
⑴ 单个命题变元是个合式公式。
⑵ 若 A是合式公式，则?A是合式公式。
⑶ 若 A和 B是 合式公式，则 (A∧ B)，
(A∨ B),(A?B)和 (A?B)都是合式公式。
⑷ 当且仅当有限次地应用⑴，⑵，⑶所得到的含有命题变元、联结词和括号的符号串是 合式公式 。
注意这个定义是递归的。 (1)是递归的基础，由 (1)开始，使用 (2)(3)规则，可以得到任意的合式公式。
这里所谓的合式公式可以解释为合法的命题公式之意，也称之为 命题公式,有时也简称 公式 。
下面的式子不是合式公式：
P∧ Q,PR,P∨ Q∧ R
下面的式子才是合式公式：
(P∧ Q),(?P?R),((P∨ Q)∧ R)
按照 合式公式定义最外层括号必须写。
约定,为方便，最外层括号可以不写，
上面的合式公式可以写成：
P∧ Q,?P?R,(P∨ Q)∧ R
2.命题公式的 真值表一个命题公式不是复合命题，所以它没有真值，但是给其中的所有命题变元作指派以后它就有了真值。可以以表的形式反应它的真值情况，例如命题 公式 (?P?Q)∨ Q 的真值表如下所示：
P Q?P?P?Q (?P?Q)∨ Q
F F T F F
F T T T T
T F F T T
T T F T T
由于对每个命题变元可以有两个真值 (T,F)
被指派，所以有 n个命题变元的命题公式
A(P1,P2,…,P n) 的 真值表有 2n行 。
为了有序地列出公式的真值表，在对命题变元做指派时，可以按照二进制数的次序列表。
补充,关于,二进制数,见下页。
关于二进制数简介：
由于计算机的硬件是由二个状态的逻辑元件组成的，所以它只处理二进制的信息,
二进制数：只有两个基本符号 0和 1，计算时，
逢二进一,如
0+1=1,1+1=10,10+1=11,11+1=100
0 1 10 11
+ 1 + 1 + 1 + 1
1 10 11 100
十进制数 0 1 2 3 4 5 6 7 8 9
二进制数 0 1 10 11 100 101 110 111 1000 1001
注,有效数字前加 0不影响数值，如 000=0,001=1,010=10,011=11
、,、
为了 有序地列出 A(P1,P2,…,P n)的真值表，
可以将 F看成 0，将 T看成 1，按照 二进制数 00…0,00…01,00…010,…,11…10,
11…1( 即十进制的 0,1,2,….,2 n -1)的次序进行指派列真值表。
如 A(P,Q)的真值表可按照如下次序指派：
00(F,F),01(F,T),10(T,F),11(T,T)
如 A(P,Q,R)的真值表可按照如下次序指派：
000(F,F,F),001(F,F,T),010(F,T,F),011(F,T,T)
100(T,F,F),101(T,F,T),110(T,T,F),111(T,T,T)
例如列出 P?(Q?R)的真值表
P Q R Q?R P?(Q?R)
000 F F F T T
001 F F T T T
010 F T F F T
011 F T T T T
100 T F F T T
101 T F T T T
110 T T F F F
111 T T T T T
三,命题符号化所谓命题符号化，就是用命题公式的符号串来表示给定的命题。
命题符号化的方法
1.首先要明确给定命题的含义。
2.对于复合命题，找联结词，用联结词断句，分解出各个原子命题。
3.设原子命题符号，并用逻辑联结词联结原子命题符号，构成给定命题的符号表达式。
例 1.说离散数学无用且枯燥无味是不对的。
P：离散数学是有用的。
Q：离散数学是枯燥无味的。
该命题可写成,? (?P∧ Q)
例 2.如果小张与小王都不去，则小李去。
P：小张去。 Q：小王去。 R：小李去。
该命题可写成,(?P∧?Q)?R
如果小张与小王不都去，则小李去。
该命题可写成,?(P∧ Q)?R
也可以写成,(?P∨?Q)?R
例 3,仅当 天不下雨且我有时间，才上街。
P,天下雨。 Q,我有时间。 R,我上街。
分析,由于“仅当”是表示“必要条件”
的，既,天不下雨且我有时间”，是“我上街”的必要条件。所以该命题可写成,R?(?P∧ Q)
例 4.人不犯我，我不犯人；人若犯我，我必犯人。
P：人犯我。 Q：我犯人。
该命题可写成,(?PQ)∧ (P?Q)
或写成,P?Q P是 Q的充分条件P是 Q的必要条件
P是 Q的充分且必要条件
例 5,若天不下雨，我就上街；否则在家。
P,天下雨。 Q,我上街。 R：我在家。
该命题可写成,(?P?Q)∧ (P?R).
注意,中间的联结词一定是,∧,，而不是,∨,，也不是,”。
因为原命题表示：,天不下雨时我做什么,天 下雨我又做什么,的 两种作法,其中有一种作法是假的，则我说的就是假话，所以中间的联结词一定是,∧,。
如果写成 (?P?Q)∨ (P?R)，就表明 两种作法 都是假的时候，我说的才是假话。这显然不对 。
若写成 (?P?Q) (P? R)时，当 P为 F,Q为 F时，即天没下雨而我没上街，此时我说的是假话，但是表达式
(?P?Q) (P? R) 的真值却是,T”,因为此时 (P?R)的真值 是,T”。
作业题：
第 8页：（ 3）
第 12页：（ 5）、（ 7）
第 17页：（ 1） a),d)
1-4 重言式与重言蕴涵式
一,重言式 (永真式 )与矛盾式 (永假式 )
1.例子：
P?P∨ P?P∧ P
F T F
T T F
可见不论 P取什么真值?P∨ P的真值总是为真,?P∧ P的真值总是为假。故称
P∨ P为重言式 (永真式 )，称?P∧ P为矛盾式 (永假式 )。
2,重言式 (矛盾式 )定义
A(P1,P2,…,P n) 是含有命题变元 P1,P2,…,Pn的命题公式，如不论对 P1,P2,…,Pn作任何指派，都使得 A(P1,P2,…,Pn) 为 真 (假 )，则称之为 重言式 (矛盾式 ),也称之为 永真式 (永假式 )。
3.重言式的证明方法方法 1：列真值表。
方法 2：公式的等价变换，化简成,T”。
方法 3：用公式的主析取范式。
其中方法 2 和方法 3 我们在以后讨论。
方法 1,列真值表。
例如，证明 (P∧ (P?Q))?Q 为重言式。
P Q P?Q P∧ (P?Q) (P∧ (P?Q))?Q
F F T F T
F T T F T
T F F F T
T T T T T
永真式的真值表的最后一列全是,T”。
4,永真式的性质
1).如果 A是永真式，则?A是永假式。
2).如果 A,B是永真式，则 (A∧ B),(A∨ B)、
(A?B)和 (A?B)也都是永真式。
3).如果 A是永真式，则 A的置换例式也是永真式。
置换例式,A(P1,P2,…,P n) 是含有命题变元
P1,P2,…,Pn的命题公式，如果用合式公式 X替换某个 Pi(如果 Pi在 A(P1,P2,…,P n) 中多处出现，则各处均用 X替换 )，其余变元不变，替换后得到新的公式 B，则称 B是 A(P1,P2,…,P n) 的置换例式。
例如：
公式 A,P∨ (?P∧ ((P?Q)?R))
用 (D?E)替换 A中 P得到 A的置换例式 B：
(D?E)∨ (?(D?E)∧ (((D?E)?Q)?R))
如果 A是永真式，例如 A为?P∨ P,用
(D?E)替换 A中 P，得到 A的置换例式
B,? (D?E)∨ (D?E),
显然 B也是永真式。
如果可以断定给定公式是某个 永真式的置换例式的话，则这个公式也是永真式。
二,重言 (永真 )蕴涵式有些重言 (永真 )式，如 (P∧ (P?Q))?Q，
公式中间是,?”联结词，是很重要的，
称之为 重言蕴涵式。
1.定义,如果公式 A?B是 重言式，则称 A重言 (永真 )蕴涵 B，记作 A?B。
上式可以写成 (P∧ (P?Q))?Q
注意符号,?”不是联结词，它是表示公式间的,永真蕴涵,关系，也可以看成是
,推导,关系。即 A?B可以理解成由 A可推出 B，即 由 A为真，可以推出 B也为真 。
2.重言 (永真 )蕴涵式证明方法方法 1.列真值表。 (即列永真式的真值表 )
这里就不再举例了。
下面讨论另外两种方法。
A B A?B
F F T
F T T
T F F
T T T
先看一看 A?B的真值表，如果 A?B为永真式，则真值表的第三组指派不会出现。于是有下面两种证明方法。
方法 2.假设前件为真，推出后件也为真 。
例如求证：
((A∧ B)?C)∧?D∧ (?C∨ D)A∨?B
证明,设前件 ((A∧ B)?C)∧?D∧ (?C∨ D) 为真。则 ((A∧ B)?C),?D,(?C∨ D)均真，
D为 T，则 D为 F
C∨ D为 T
((A∧ B)?C为 T
如果 A为 F，则?A为 T，所以?A∨?B为 T。
如果 B为 F，则?B为 T，所以?A∨?B 为 T。
((A∧ B)?C)∧?D∧ (?C∨ D)A∨?B
得 C为 F
得 A?B为 F
方法 3.假设后件为假，推出前件也为假 。
例如求证：
((A∧ B)?C)∧?D∧ (?C∨ D)A∨?B
证明,假设后件?A∨?B为 F,则 A与 B均为 T。
1.如 C为 F，则 (A∧ B)?C为 F，所以前件
((A∧ B)?C)∧?D∧ (?C∨ D) 为 F
2.如 C为 T，则 ⑴ 若 D为 T，则?D为 F，所以前件 ((A∧ B)?C)∧?D∧ (?C∨ D) 为假
⑵ 若 D为 F，则?C∨ D为 F，所以前件 ((A∧ B)?C)∧?D∧ (?C∨ D) 为假。
((A∧ B)?C)∧?D∧ (?C∨ D)A∨?B
3.重要的重言蕴涵式 (如教材第 43页所示 )
I1.P∧ Q?P I2,P∧ Q?Q
I3,P?P∨ Q I4,Q?P∨ Q
I5,?P?P?Q I6,Q?P?Q
I7,?(P?Q)?P I8,?(P?Q)Q
I9,P,Q?P∧ Q I10,?P∧ (P∨ Q)?Q
I11,P∧ (P?Q)?Q I12,?Q∧ (P?Q)P
I13,(P?Q)∧ (Q?R)?P?R
I14,(P∨ Q)∧ (P?R)∧ (Q?R)?R
I15,A?B?(A∨ C)?(B∨ C)
I16,A?B?(A∧ C)?(B∧ C)
上述公式的证明都比较简单，可以用假设前件为 T，推出后件也为 T的方法证明。
4,性质
1).有自反性：对任何命题公式 A，有 A?A
2).有传递性：若 A?B且 B?C，则 A?C
3).有反对称性：若 A?B且 B?A，则 A?B
符号,?”表示“等价”。
本节重点掌握,永真式及永真蕴涵式的定义、证明方法、以及常用的公式。
作业,第 23页,(2) b),(6),(8) e)
1-5 等价公式
1,例子 看下面三个公式的真值表
P Q P?Q?P∨ Q?QP
F F T T T
F T T T T
T F F F F
T T T T T
从真值表可以看出，不论对 P,Q作何指派，都使得 P?Q,?P∨ Q和?QP的真值相同，表明它们之间彼此等价。
2,定义,A,B是含有命题变元 P1,P2,…,Pn
的命题公式，如不论对 P1,P2,…,Pn作任何指派，都使得 A和 B的真值相同，则称之为 A与 B等价,记作 A?B。
显然 P?QP∨ QQP
3,重要的等价公式
⑴ 对合律P?P
⑵ 幂等律 P∨ P?P P∧ P?P
⑶ 结合律 P∨ (Q∨ R)?(P∨ Q)∨ R
P∧ (Q∧ R)?(P∧ Q)∧ R
⑷ 交换律 P∨ Q?Q∨ P P∧ Q?Q∧ P
⑸ 分配律 P∨ (Q∧ R)?(P∨ Q)∧ (P∨ R)
P∧ (Q∨ R)?(P∧ Q)∨ (P∧ R)
⑹ 吸收律 P∨ (P∧ Q)?P P∧ (P∨ Q)?P
⑺ 底 -摩根定律?(P∨ Q)P∧?Q
(P∧ Q)P∨?Q
⑻ 同一律 P∨ F?P P∧ T?P
⑼ 零律 P∨ T?T P∧ F?F
⑽ 互补律 P∨?P?T P∧?P?F
⑾ P?QP∨ Q
⑿ P?QQP
⒀ P?Q?(P?Q)∧ (Q?P)
⒁ P?Q?(?P∨ Q)∧ (P∨?Q)
⒂ P?Q?(P∧ Q)∨ (?P∧?Q )
为便于记忆，将等价公式 (前 10个 )与集合论的公式比较，请看集合公式：
⑴ 对合律 ~~A?A ~A表示 A的绝对补集
⑵ 幂等律 A∪ A?A A? A?A
⑶ 结合律 A∪ (B∪ C)?(A∪ B)∪ C
A?(B? C)?(A? B)? C
⑷ 交换律 A∪ B?B∪ A A? B?B? A
⑸ 分配律 A∪ (B? C)?(A∪ B)?(A∪ C)
A?(B∪ C)?(A? B)∪ (A? C)
⑹ 吸收律 A∪ (A? B)?A A?(A∪ B)?A
⑺ 底 -摩根定律 ~(A∪ B)?~A? ~B
~(A? B)?~A∪ ~B
⑻ 同一律 A∪ Φ?A A? E?A E表示全集
⑼ 零律 A∪ E?E A? Φ?Φ
⑽ 否定律 A∪ ~A?E A? ~A?Φ
4,等价公式的证明方法
方法 1：用列真值表。（不再举例）
方法 2：用公式的等价变换,(用置换定律 )
置换定律,A是一个命题公式,X是 A中的一部分且也是合式公式，如果 X?Y，用 Y代替 A中的 X得到公式 B，则 A?B。
应用置换定律以及前面列出的等价公式可以对给定公式进行等价变换。
例题 1,求证吸收律 P∧ (P∨ Q)?P
证明 P∧ (P∨ Q)
(P∨ F)∧ (P∨ Q) (同一律 )
P∨ (F∧ Q) (分配律 )
P∨ F (零律 )
P (同一律 )
例题 2,求证 (?P∨ Q)→(P ∧ Q)?P
证明 (?P∨ Q)→(P ∧ Q)
(?P∨ Q)∨ (P∧ Q) (公式 E16)
(P∧?Q)∨ (P∧ Q) (摩根定律 )
(P∧?Q)∨ (P∧ Q) (对合律 )
P∧ (?Q∨ Q) (分配律 )
P∧ T (互补律 )
P (同一律 )
公式 E16,P?QP∨ Q
例题 3.化简?(P∧ Q)→(?P∨ (?P∨ Q))
解 原公式
(P∧ Q)∨ ((?P∨?P)∨ Q) (E16,结合 )
(P∧ Q)∨ (?P∨ Q) (对合律，幂等律 )
(P∧ Q)∨ (Q∨?P) (交换律 )
((P∧ Q)∨ Q)∨?P (结合律 )
Q∨?P (吸收律 )
公式 E16,P?QP∨ Q
5,性质
1).有自反性：任何命题公式 A，有 A?A。
2).有对称性：若 A?B，则 B?A
3).有传递性：若 A?B且 B?C，则 A?C
4).如果 A(P1,P2,…,P n)?B(P1,P2,…,P n)，则
A(?P1,?P2,…,?Pn)?B(?P1,?P2,…,?Pn)
例 A(P,Q)?P→Q B(P,Q)P∨ Q
有 A(P,Q)?B(P,Q)
A(?P,?Q)P→?Q
B(?P,?Q)?P∨?Q
可见 A(?P,?Q)?B(?P,?Q)
6.等价公式的对偶性从前面列出的等价公式看出，有很多是成对出现的。这就是等价公式的对偶性。
⑴ 对偶式,在一个只含有联结词?,∨,
∧ 的公式 A中，将 ∨ 换成 ∧,∧ 换成 ∨,
T换成 F,F换成 T，其余部分不变，得到另一个公式 A*，称 A与 A*互为对偶式。
例如,,A A*
P P
Q∧ R?Q∨ R
(P∨ T)∧?Q (P∧ F)∨?Q
⑵ 用对偶式求公式的否定定理 1-5.1 令 A(P1,P2,…,P n)是一个只含有联结词?,∨,∧ 的命题公式，则
A(P1,P2,…,P n)?A*(?P1,?P2,…,?Pn)
此定理可以反复地使用底 -摩根定律得以证明。 下面我们 验证 一下。
令 A(P,Q)?P∨ Q A*(P,Q)?P∧ Q
A(P,Q)(P∨ Q)
A*(?P,?Q)P∧?Q
可见?A(P,Q)?A*(?P,?Q)
推论,A(?P1,?P2,…,?Pn)A*(P1,P2,…,P n)
例如，利用上述求公式的否定公式求
(((P∧ Q)∨ (P∧?Q))∨ R)
((?P∨?Q)∧ (?P∨ Q))∧?R
⑶ 对偶原理 (定理 1-5.2)：
令 A(P1,P2,…,P n),B(P1,P2,…,P n)是只含有联结词?,∨,∧ 的命题公式，则如果
A(P1,P2,…,P n)?B(P1,P2,…,P n) 则
A*(P1,P2,…,P n)?B*(P1,P2,…,Pn)
证明,因为 A(P1,P2,…,P n)?B(P1,P2,…,P n)
故 A(?P1,?P2,…,?Pn)?B(?P1,?P2,…,?Pn)
而 A(?P1,?P2,…,?Pn)A*(P1,P2,…,P n)
B(?P1,?P2,…,?Pn)B*(P1,P2,…,P n)
故?A*(P1,P2,…,P n)B*(P1,P2,…,P n)
所以 A*(P1,P2,…,P n)?B*(P1,P2,…,Pn)
下面我们验证一下对偶原理：
P∨ (Q∧ R)?(P∨ Q)∧ (P∨ R)
A B
P∧ (Q∨ R)?(P∧ Q)∨ (P∧ R)
A* B*
P∨ T?T
A B
P∧ F?F
A* B*
本节要求 掌握等价公式的证明方法及记忆公式 。
作业,第 19页 (7) f) g),(8) c)
1-6.范式范式就是命题公式形式的规范形式。这里约定在范式中 只含有联结词?,∨ 和 ∧ 。
一,析取范式与合取范式
1.合取式与析取式合取式,是用,∧,联结命题变元或变元的否定构成的式子。
如 P,?P,P∧?Q,P∧?Q∧?R
析取式,是用,∨,联结命题变元或变元的否定构成的式子。
如 P,?P,P∨?Q,P∨?Q∨?R
注,∵ P∨ P?P P∧ P?P ∴ P是合 (析 )取式,
2.析取范式公式 A如果写成如下形式：
A1∨ A2∨,..∨ An (n≥1) 其中每个 Ai
(i=1,2..n)是 合取式，称之为 A的 析取范式 。
3.合取范式公式 A如果写成如下形式：
A1∧ A2∧,..∧ An (n≥1) 其中每个 Ai
(i=1,2..n)是 析取式，称之为 A的 合取范式 。
例如,P?Q 的 析取范式与合取范式：
P?Q?(P∧ Q)∨ (?P∧?Q)----析取范式
P?Q?(?P∨ Q)∧ (P∨?Q)----合取范式
4.析取范式与合取范式的写法
⑴先用相应的公式去掉?和?。
公式 E16 P?QP∨ Q
公式 E21 P?Q?(P∧ Q)∨ (?P∧?Q)
公式 E20 P?Q?(P?Q)∧ (Q?P)
再用 E16 P?Q?(?P∨ Q)∧ (P∨?Q)
⑵ 用公式的否定公式或摩根定律将?后移到命题变元之前。
A(P1,P2,…,P n)?A*(?P1,?P2,…,?Pn)
底 -摩根定律?(P∨ Q)P∧?Q
(P∧ Q)P∨?Q
⑶ 用分配律、幂等律等公式进行整理，使之成为所要求的形式。
例如求 (P?Q)?R的 析取范式与合取范式
(P?Q)?R
((?P∨ Q)∧ (P∨?Q))∨ R
(P∧?Q)∨ (?P∧ Q)∨ R ------析取范式
(P?Q)?R((P∧ Q)∨ (?P∧?Q))∨ R
((?P∨?Q)∧ (P∨ Q))∨ R
(?P∨?Q∨ R)∧ (P∨ Q∨ R) ---合取范式二,主析取范式与主 合取范式一个公式的 析取范式与合取范式的形式是不唯一的。下面定义形式唯一的 主析取范式与主 合取范式。
㈠主析取范式
1.小项
⑴定义：在一个有 n个命题变元的合取式中，每个变元必出现且仅出现一次，
称这个合取式是个 小项 。
例如，有两个变元的小项：
P∧ Q,P∧?Q,?P∧ Q,?P∧?Q
⑵ 小项的性质
m3 m2 m1 m0
P Q P∧ Q P∧?Q?P∧ Q?P∧?Q
00 F F F F F T
01 F T F F T F
10 T F F T F F
11 T T T F F F
a).有 n个变元，则有 2n个小项。
b).每一组指派有且只有一个小项为 T。
为了记忆方便，可将各组指派对应的为 T的小项分别记作 m0,m1,m2,…,m 2n-1 上例中
m0P∧?Q m1P∧ Q
m2?P∧?Q m3?P∧ Q
2.主析取范式定义析取范式 A1∨ A2∨,..∨ An,,其中每个 Ai
(i=1,2..n)都 是 小项，称之为 主析取范式 。
3.主析取范式的写法方法 Ⅰ,列真值表
⑴列出给定公式的真值表。
⑵找出真值表中每个,T”对应的小项。
(如何 根据一组指派写对应的为,T”的项：
如果变元 P被指派为 T,P在小项中以 P形式出现；如变元 P被指派为 F,P在小项中以?P形式出现 (因要保证该小项为 T))。
⑶用,∨,联结上述小项，即可。
例如求 P?Q和 P?Q的 主析取范式
P Q P?Q P?Q
F F T T
F T T F
T F F F
T T T T
P?Q? m0∨ m1∨ m3
(?P∧?Q)∨ (?P∧ Q)∨ (P∧ Q)
P?Q?m0∨ m3
(?P∧?Q)∨ (P∧ Q)
思考题,永真式的 主析取范式是什么样？
方法 Ⅱ,用公式的等价变换
⑴先写出给定公式的析取范式
A1∨ A2∨,..∨ An 。
⑵为使每个 Ai都变成小项，对缺少变元的 Ai
补全变元，比如缺变元 R，就用 ∧ 联结永真式 (R∨?R)形式补 R。
⑶用分配律等公式加以整理。
P?QP∨ Q
(?P∧ (Q∨?Q))∨ ((P∨?P)∧ Q)
(?P∧ Q)∨ (?P∧?Q)∨ (P∧ Q)∨ (?P∧ Q)
(?P∧ Q)∨ (?P∧?Q)∨ (P∧ Q)
㈡ 主 合取范式
1.大项
⑴定义,在有 n个命题变元的析取式中，每个变元必出现且仅出现一次,称之为 大项 。
例如，有两个变元的大项及其真值表：
M0 M1 M2 M3
P Q P∨ Q P∨?Q?P∨ Q?P∨?Q
F F F T T T
F T T F T T
T F T T F T
T T T T T F
⑵ 大项的性质
a).有 n个变元，则有 2n个大项。
b).每一组指派有且只有一个大项为 F。
为了记忆方便，可将各组指派对应的为 F
的大项分别记作 M0,M1,M2,…,M 2n-1 。
上例中
M0?P∨ Q M1?P∨?Q
M2P∨ Q M3P∨?Q
2.主合取范式定义合 取范式 A1∧ A2∧,.,∧ An,,其中每个 Ai
(i=1,2..n)都 是 大项，称之为 主合取范式 。
3.主合取范式的写法方法 Ⅰ,列真值表
⑴列出给定公式的真值表。
⑵找出真值表中每个,F”对应的大项。
如何 根据一组指派写对应的为,F”的大项：
如果变元 P被指派为 F,P在大项中以 P形式出现；
如变元 P被指派为 T,P在大项中以?P形式出现
(确保该大项为 F)。
⑶用,∧,联结上述大项，即可。
例如求 P?Q和 P?Q的 主合取范式
P Q P?Q P?Q
F F T T
F T T F
T F F F
T T T T
P?Q? M2P∨ Q
P?Q?M1∧ M2
(P∨?Q )∧ (?P∨ Q)
课堂练习,
1.已知 A(P,Q,R)的真值表如图：
求它的主析取和主合取范式。
2.已知 A(P,Q,R)的主析取范式中含有下面小项 m1,m3,m5,
m7求它的和主合取范式,
P Q R A(P,Q,R)
F F F T
F F T F
F T F F
F T T T
T F F T
T F T F
T T F T
T T T T
练习答案：
1.A(P,Q,R)的主析取范式,
A(P,Q,R)? m0∨ m3∨ m4∨ m6∨ m7
(?P∧?Q∧?R)∨ (?P∧ Q∧ R)∨
(P∧?Q∧?R)∨ (P∧ Q∧?R)∨ (P∧ Q ∧ R)
A(P,Q,R)的 主合取范式：
A(P,Q,R)? M1∧ M2∧ M5
(P∨ Q∨?R)∧ (P∨?Q∨ R)∧ (?P∨ Q∨?R)
2,A(P,Q,R)? M0∧ M2∧ M4 ∧ M6
(P∨ Q∨ R)∧ (P∨?Q∨ R)∧ (?P∨ Q∨ R)
∧ (?P∨?Q∨ R)
方法 Ⅱ,用公式的等价变换
⑴先写出给定公式的合取范式
A1∧ A2∧,..∧ An 。
⑵为使每个 Ai变成大项，对缺少变元的析取式 Ai补全变元，比如缺变元 R，就用 ∨
联结永假式 (R∧?R)形式补 R。
⑶用分配律等公式加以整理。
例如，求 (P?Q)?R的主合取范式
(P?Q)?R
(?P∨ Q)∨ R
(P∧?Q)∨ R
(P∨ R)∧ (?Q∨ R)
(P∨ (Q∧?Q)∨ R)∧ ((P∧?P)∨?Q∨ R)
(P∨ Q∨ R)∧ (P∨?Q∨ R)∧
(P∨?Q∨ R)∧ (?P∨?Q∨ R)
三,范式的应用范式在逻辑设计方面有广泛的应用。
例 1.加法器的设计，有两个 n位二进制数 a,b
相加和为 s(s=a+b),a,b分别写成：
a=anan-1… ai...a2a1,
+ b=bnbn-1… bi...b2b1
s= cn sn sn-1… si…s 2 s1
其中 si是第 i位 ai,bi及 ci-1 (ci-1是第 i-1位向第 i
位的 进位 ) 的和，显然 si是 ai bi及 ci-1的函数,
写成 si(ai,bi,ci-1),它与 ai,bi,ci-1的关系如下表：
ai bi ci-1 si(ai,bi,ci-1)
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 1
在电路逻辑设计中用如下逻辑部件：
非门 与门 或门根据前边的表,列出 si(ai,bi,ci-1)的主析取范式：
si(ai,bi,ci-1)=(?ai∧?bi∧ ci-1)∨ (?ai∧ bi∧?ci-1)∨
(ai ∧?bi∧?ci-1)∨ (ai∧ bi∧ ci-1)
(在指派 001,010,100,111时 si为 1)
下面设计出 si(ai,bi,ci-1)的线路图 。
a
b
a∧ba a
b a∨b
a
si(ai,bi,ci-1)=(?ai∧?bi∧ ci-1)∨ (?ai∧ bi∧?ci-1)∨
(ai ∧?bi∧?ci-1)∨ (ai∧ bi∧ ci-1)
si(ai,bi,ci-1)
ai?ai
bi?bi
Ci-1
ci-1
例 2,安排课表，教语言课的教师希望将课程安排在第一或第三节；教数学课的教师希望将课程安排在第二或第三节；教原理课的教师希望将课程安排在第一或第二节。如何安排课表，使得三位教师都满意。
令 L1,L2,L3分别表示语言课排在第一、
第二、第三节。
M1,M2,M3分别表示数学课排在第一、
第二、第三节。
P1,P2,P3分别表示原理课排在第一、
第二、第三节。
三位教师都满意的条件是：
(L1∨ L3)∧ (M2∨ M3)∧ (P1∨ P2 ) 为真。
将上式写成析取范式 (用分配律 )得：
((L1∧ M2)∨ (L1∧ M3)∨ (L3∧ M2)∨
(L3∧ M3))∧ (P1∨ P2)
(L1∧ M2∧ P1)∨ (L1∧ M3∧ P1)∨
(L3∧ M2∧ P1)∨ (L3∧ M3∧ P1)∨
(L1∧ M2∧ P2)∨ (L1∧ M3∧ P2)∨
(L3∧ M2∧ P2)∨ (L3∧ M3∧ P2)
可以取 (L3 ∧ M2∧ P1),(L1∧ M3∧ P2)为 T，
得到两种排法。
本节要掌握：
析取范式、合取范式、主析取范式、主合取范式的 写法,范式的 应用 。
作业第 39页,(2) d),
(3) d),
(4) d),
(7)
1-7,命题逻辑推理
推理 就是根据一个或几个已知的判断得出一个新的判断的思维过程。称这些已知的判断为 前提 。得到的新的判断为前提的 有效结论 。
实际上，推理的过程就是证明永真蕴含式的过程，即令 H1,H2,…,Hn是已知的命题公式 (前提 )，若有
H1∧H 2∧....∧H n? C
则称 C是 H1,H2,… Hn的 有效结论,简称结论 。
如何根据前提得到结论，需要有推理的规则。下面先介绍两个 推理规则 。
规则 P(引入前提规则 )：在推理过程中，
可以随时引入前提。
规则 T(引入结论规则 )：在推理过程中，
如果前边有一个或几个公式永真蕴涵公式 S，则可将 S纳入推理过程中。
在推理过程中，还要应用教材 43页表 1-
8.3中的永真蕴涵式 I1-I16和表 1-8.4中等价公式 E1-E22 (常用的公式要熟记 )
下面主要介绍三种推理方法：
直接推理、条件论证及反证法重要的重言蕴涵式 (如教材第 43页所示 )
I1.P∧ Q?P I2,P∧ Q?Q
I3,P?P∨ Q I4,Q?P∨ Q
I5,?P?P?Q I6,Q?P?Q
I7,?(P?Q)?P I8,?(P?Q)Q
I9,P,Q?P∧ Q I10,?P∧ (P∨ Q)?Q
I11,P∧ (P?Q)?Q I12,?Q∧ (P?Q)P
I13,(P?Q)∧ (Q?R)?P?R
I14,(P∨ Q)∧ (P?R)∧ (Q?R)?R
I15,A?B?(A∨ C)?(B∨ C)
I16,A?B?(A∧ C)?(B∧ C)
重要的等价公式,
对合律 E1P?P
交换律 E2 P∧ Q?Q∧ P E3 P∨ Q?Q∨ P
结合律 E4 P∧ (Q∧ R)?(P∧ Q)∧ R E5 P∨ (Q∨ R)?(P∨ Q)∨ R
分配律 E6 P∧ (Q∨ R)?(P∧ Q)∨ (P∧ R)
E7 P∨ (Q∧ R)?(P∨ Q)∧ (P∨ R)
底 -摩根定律 E8?(P∧ Q)P∨?Q E9?(P∨ Q)P∧?Q
幂等律 E10 P∨ P?P E11 P∧ P?P
同一律 E12 P∨ F?P E13 P∧ T?P
零律 E14 P∨ T?T E15 P∧ F?F
E16 P?QP∨ Q E17?( P?Q)?P∧?Q
E18 P?QQP E19 P?(Q?R)?(P∧ Q)?R
E20 P?Q?(P?Q)∧ (Q?P) E21 P?Q?(P∧ Q)∨ (?P∧?Q )
E22?(P?Q)?PQ
吸收律 P∨ (P∧ Q)?P P∧ (P∨ Q)?P
互补律 P∨?P?T P∧?P?F
P?Q?(?P∨ Q)∧ (P∨?Q)
一,直接推理
直接推理,就是从前提直接推出结论。
上面讲到推理的过程实际上是证明永真蕴含式的过程。只不过证明的过程采用另外一种书写格式 。
格式中包含,步骤号，给定前提或得出的结论，推理时所用规则，此结论是从哪几步得到的以及所用公式。下面请看一些例子。
例题１求证 P→Q,Q→R,P?R
证明序号 前提或结论 所用规则 从哪几步得到 所用公式
(1) P P
(2) P?Q P
(3) Q T (1)(2) I11
(4) Q→R P
(5) R T (3)(4) I11
（ 注公式 I11为,P,P→Q? Q ）
例题２求证
(P∧Q)∧(Q∨R)∧?RP
(1) Q∨R P
(2)?R P
(3) Q T (1)(2) I10
(4)?(P∧Q) P
(5)?P∨?Q T (4) E8
(6)?P T (3)(5) I10
注公式 I10为,? P,P∨Q? Q
公式 E8为,?(P∧Q)P∨?Q
例题３用命题逻辑推理方法证明下面推理的有效性：
如果我学习，那么我数学不会不及格。
如果我不热衷于玩朴克，那么我将学习。
但是我数学不及格。因此，我热衷于玩朴克。
解设 P：我学习。
Q：我数学及格。
R：我热衷于玩朴克。
于是符号化为：
P→Q,?R→P,?Q? R
P→Q,?R→P,?Q? R
(1) P→Q P
(2)?Q P
(3)?P T (1)(2) I12
(4)?R→P P
(5)R T (3)(4) I12
(6) R T (5) E1
注：公式 I12为,?Q,P→QP
公式 E1 为,R?R
例题４求证 P→(Q→S),?R∨P,Q?R→S
证明 (1) P→(Q→S) P
(2)?P∨(?Q∨S) T (1) E 16
(3)?P∨(S∨?Q) T (2) E3
(4) (?P∨S)∨?Q T (3) E5
(5) Q P
(6)?P∨S T (4)(5) I 10
(7) P→S T (6) E 16
(8)?R∨P P
(9) R→P T (8) E 16
(10) R→S T (7)(9) I 13
二,条件论证
定理 1-7.1 如果 H1∧H 2∧...∧H n∧R?Ｓ，
则 H1∧H 2∧...∧H n? R→S
证明 因为 H1∧H 2∧...∧H n∧ Ｒ?Ｓ
则 (H1∧H 2∧...∧H n∧R)?S 是永真式。
根据结合律得
((H1∧H 2∧...∧H n)∧R)→S 是永真式。
根据公式 E19得
(H1∧H 2∧...∧H n)?(R→S) 是永真式。
即 H1∧H 2∧...∧H n? R→S
定理得证。 E19,P?(Q→R)?(P∧Q)→R
此定理告诉我们，如果要证明的结论是蕴涵式 (R→S) 形式，则可以把结论中蕴涵式的前件 R作为附加前提，与给定的前提一起推出后件 S即可。
我们把上述定理写成如下规则：
规则 CP( Conditional Ｐ roof)：
如果 H1∧H 2∧...∧H n∧R? S，则
H1∧H 2∧...∧H n? R→S
下面我们用条件论证方法求证例题４
P→(Q→S),?R∨P,Q? R→S
例题５ 用条件论证，证明例题４
P→(Q→S),?R∨P,Q? R→S
证明 (1) R P(附加前提 )
(2)?R∨P P
(3) P T (1)(2) I10
(4) P→(Q→S) P
(5) Q→S T (3)(4) I 11
(6) Q P
(7) S T (5)(6) I11
(8) R→S CP
与例题４相比，因为它增加了一个附加前提，
所以推理就容易些。
例题６ 用命题逻辑推理方法证明下面推理的有效性：
如果体育馆有球赛，青年大街交通就拥挤。在这种情况下，如果小王不提前出发，就会迟到。因此，小王没有提前出发也未迟到，则体育馆没有球赛。
证明 先将命题符号化。
设 P：体育馆有球赛。
Q：青年大街交通拥挤。
R：小王提前出发。
S：小王迟到。
P→Q,(Q∧?R)→S?(?R∧?S)→?P
P→Q,(Q∧?R)→S?(?R∧?S)→?P
证明
(1)?R∧?S P(附加前提 )
(2)?R T (1) I1
(3)?S T (1) I2
(4) (Q∧?R)→S P
(5)?(Q∧?Ｒ ) T(3)(4) I12
(6)?Q∨R T (5) E 8
(7)?Q T (2)(6) I10
(8) P→Q P
(9)?P T (7)(8) I12
(10)(?R∧?S)→?P CP
三,反证法
反证法的主要思想是：假设结论不成立，
可以推出矛盾的结论 (矛盾式 )。下面先介绍有关概念和定理。
定义,设 H1,H2,...,Hn是命题公式,P1，
P2,...,Pm是公式中的命题变元，如果对所有命题变元至少有一种指派，使得
H1∧H 2∧...∧H n 的真值为 T，则称公式集合 {H1,H2,… Hn}是 相容的 (也称是 一致的 )；如果对所有命题变元每一种指派，
都使得 H1∧H 2∧...∧H n的真值为 F，则称公式集合 {H1,H2,… Hn}是 不相容的 (也称是 不一致的 )。
定理 1-7.2 若要证明相容的公式集合
{H1,H2,..,Hn}可以推出公式 C，只要证明
H1∧H 2∧...∧H n∧?C是个矛盾式即可。
证明 设 H1∧H 2∧...∧H n∧?C 是矛盾式，则
(H1∧H 2∧...∧H n∧?C)是个永真式。
上式(H1∧H 2∧...∧H n)∨C
(H1∧H 2∧...∧H n)→C
所以 H1∧H 2∧...∧H n? C
实际上，要证明 H1∧H 2∧...∧H n? C，只要证明 H1∧H 2∧...∧H n∧?C可推出矛盾式即可，即
H1∧H 2∧...∧H n∧?C? R∧?R
例７ P→Q,(?Q∨R)∧?R,?(?P∧S)S
(1)S P(假设前提 )
(2) S T (1) E1
(3)?(?P∧S) P
(4) P∨?S T (3) E8
(5) P T (2)(4) I10
(6) P→Q P
(7) Q T (5)(6) I11
(8) (?Q∨R)∧?R P
(9)?Q∨R T (8) I 1
(10)?R T (8) I2
(11) R T (7)(9) I10
(12) R∧?R T (10)(11) I9
本节要 掌握三种推理方法,按照所要求格式正确地书写推理过程。
作业
第 47页,(1) b),
(2) b),e)
(3) b),e)
(4) a),c)
(5) c)
第一章 小结知识网络,命 题原子命题 复合命题联结词命题公式永真式永真蕴涵式 等价公式 范式命题逻辑推理直接推理 间接推理条件论证反证法析取合取主析取主合取本章的重点内容、及要求：
１,逻辑联结词，要熟练掌握联结词的真值表定义以及它们在自然语言中的含义。其中特别要注意,∨,和,→,
的用法。
２,会命题符号化。
３,掌握永真式的证明方法：
(1).真值表。
(2).等价变换，化简成Ｔ。
(3).主析取范式。
４,掌握永真蕴含式的证明方法，熟练记忆并会应用
43页中表 1-8.3中的永真蕴含式。
５,掌握等价公式的证明方法，熟练记忆并会应用
43页表 1-8.4中的等价公式。
６,熟练掌握范式的写法及其应用。
７,熟练掌握三种推理方法。
第一章 习题课一,命题符号化注意讲过的命题符号化方法。
P8习题 (3)
P:天下雪。 Q:我将去镇上。 R:我有时间。
a) 如果天不下雪且我有时间，那么我将去镇上。 (?P∧R)→Q
b) 我将去镇上，仅当我有时间。 Q→R
d) 天下雪，那么我不去镇上。 P→?Q
P12习题 (5)
a) 或者你没有给我写信，或者它在途中丢失了。
显然这里的“或者”是,不可兼取的或,。
令 P:你给我写信。 Q:信在途中丢失了。
表达式为,?P Q 或 (P∧ Q)∨ (?P∧?Q)
c) 我们不能既划船又跑步。
令 P:我们划船。 Q:我们跑步。
表达式为?(P∧Q )
d)如果你来了，那么他唱不唱歌将看你是否为他伴奏而定。
令 P:你来了。 Q:你为他伴奏。 R:他唱歌。
表达式为,P→((Q→R)∧(?Q→?R))
也可以写成,P→(Q?R)
P12习题 (7)
a) 假如上午不下雨，我去看电影，否则就在家里读书或看报。
令 P:上午下雨。 Q:我去看电影。 R:我在家里读书。 S:我在家里看报。
表达式为,(?P→Q)∧(P→(R ∨ S))
不可以写成,(?P→Q) ∨ (P→(R ∨ S))
(?P→Q) ∨ (P→(R ∨ S))
(P∨ Q)∨ (?P∨ (R∨ S))
(P∨ Q)∨ (?P∨ (R∨ S))
P∨ Q∨?P∨ R∨ S
P∨?P ∨ Q∨ R∨ S
T
b) 我今天进城，除非下雨。
令 P:我今天进城。 Q:今天下雨。
表达式为,?Q→P
c) 仅当你走我将留下。
令 P:你走。 Q:我留下。
表达式为,Q→P 或者?P→?Q
二,重言式的证明方法方法 1：列真值表。
方法 2：公式的等价变换，化简成,T”。
方法 3：用公式的主析取范式。
P23 (2)证明 (P→Q)→(P→(P∧ Q))是 重言式。
方法 1:
P Q P→Q P→(P∧ Q) (P→Q)→(P→(P∧ Q))
F F T T T
F T T T T
T F F F T
T T T T T
方法 2,(P→Q)→(P→(P∧ Q))
(?P∨ Q)∨ (?P∨ (P∧ Q)) (E16)
(P∧?Q)∨ ((?P∨ P)∧ (?P∨ Q)) 摩根，分配
(P∧?Q)∨ (T∧ (?P∨ Q)) 互 补
(P∧?Q)∨ (?P∨ Q) 同一
(P∨ (?P∨ Q) )∧ (?Q∨ (?P∨ Q) 分配
((P ∨?P)∨ Q) )∧ (?Q∨ (Q∨?P) 结 合、交 换
(T∨ Q) )∧ ((?Q∨ Q)∨?P) 互 补,结 合
T∧ (T∨?P) 零律、互 补
T∧ T 零律
T 幂等方法 3 (P→Q)→(P→(P∧ Q))
(?P∨ Q)∨ (?P∨ (P∧ Q)) 去 →
(P∧?Q)∨?P∨ (P∧ Q)? 后移
(P∧?Q)∨ (?P∧ (Q∨?Q))∨ (P∧ Q) 补 变 元 Q
(P∧?Q)∨ (?P∧ Q)∨ (?P∧?Q)∨ (P∧ Q) 分配
(P∧ Q)∨ (P∧?Q)∨ (?P∧ Q)∨ (?P∧?Q)整理可见，该公式的主析取范式含有全部 (四个 )小项，
这表明 (P→Q)→(P→(P∧ Q))是永真式。
三,重言蕴涵式的证明方法方法 1.列真值表。 (即列永真式的真值表 ) (略 )
方法 2.假设前件为真，推出后件也为真。
方法 3.假设后件为假，推出前件也为假。
P12(8)e)证明
(?A?(B∨ C) )∧ (D∨ E)∧ ((D∨ E)A)? B∨ C
方法 2 证明：
设前件 (?A?(B∨ C) )∧ (D∨ E)∧ ((D∨ E)A)
为真，则?A?(B∨ C),D∨ E,(D∨ E)A 均为真。由 D∨ E,(D∨ E)A 均为真用 I11得?A为真,
又由?A?(B∨ C)为真，得 B∨ C为真。所以得
(?A?(B∨ C) )∧ (D∨ E)∧ ((D∨ E)A)? B∨ C
(?A?(B∨ C) )∧ (D∨ E)∧ ((D∨ E)A)?B∨ C
方法 3 证明：设后件 B∨ C为 F,则 B与 C均 为 F，
1,如果 D∨ E 为 T,则
1).若 A为 T，则?A为 F，则 (D∨ E)A为 F，于是前件 (?A?(B∨ C) )∧ (D∨ E)∧ ((D∨ E)A)
为 F。
2),若 A为 F,则?A为 T，于是?A?(B∨ C) 为 F，
故前件 (?A?(B∨ C) )∧ (D∨ E)∧ ((D∨ E)A)
为 F。
2.如果 D∨ E 为 F,则 前件
(?A?(B∨ C) )∧ (D∨ E)∧ ((D∨ E)A) 为 F。
∴ (?A?(B∨ C) )∧ (D∨ E)∧ ((D∨ E)A)?B∨ C
四,,等价公式的证明方法方法 1：用列真值表。（不再举例）
方法 2：用公式的等价变换,(用置换定律 )
P19(7)h)证明
((A∧B)→C)∧(B→(D∨C))?(B∧(D→A))→c
左式?(?(A∧B)∨C)∧(?B∨(D∨C)) E 16
((?A∨?B)∨C)∧(?B∨(D∨C)) 摩根
((?B ∨?A)∨C)∧((?B∨D)∨C) 交换 结合
((?B ∨?A)∧(?B∨D))∨C 分配
(?B∨(?A∧D))∨C 分配
(B∧(A∨?D))∨C 摩根
(B∧(D→A))→C E16
P19(8)c)化简 (A∧B∧C)∨(?A∧ B∧C ）
上式? (A∨?A)∧( B∧C ） 分配
T∧( B∧C ） 互补
B∧C 同一提示,化简时注意使用下面 使式子变短的公式,
分配律 E6 P∧ (Q∨ R)?(P∧ Q)∨ (P∧ R)
E7 P∨ (Q∧ R)?(P∨ Q)∧ (P∨ R)
用分配律时，是 提取公因式 。
幂等律 E10 P∨ P?P E11 P∧ P?P
同一律 E12 P∨ F?P E13 P∧ T?P
零律 E14 P∨ T?T E15 P∧ F?F
吸收律 P∨ (P∧ Q)?P P∧ (P∨ Q)?P
互补律 P∨?P?T P∧?P?F
五,范式的写法及应用
P39(4)d)写出 (P?(Q∧ R))∧ (?P?(?Q∧?R))的主析取范式和主合取范式方法 1，用真值表令 A(P,Q,R)?(P?(Q∧ R))∧ (?P?(?Q∧?R))
它的真 值 表 见 下 页。
A(P,Q,R)?m0∨ m7
(?P∧?Q∧?R)∨ (P∧ Q∧ R)
A(P,Q,R)? M1∧ M2∧ M3∧ M4∧ M5∧ M6
(P∨ Q∨?R)∧ (P∨?Q∨ R)∧ (P∨?Q∨?R)∧
(?P∨ Q∨ R)∧ (?P∨ Q∨?R)∧ (?P∨?Q∨ R)
A(P,Q,R)的主析取范式中含有小项 m0,m7。
主合取范式中含有大项 M1,M2,M3,M4,M5,M6 。
P Q R P?(Q∧ R)?P?(?Q∧?R ) A(P,Q,R)
0 F F F T T T
1 F F T T F F
2 F T F T F F
3 F T T T F F
4 T F F F T F
5 T F T F T F
6 T T F F T F
7 T T T T T T
方法 2.等价变换
(P?(Q∧ R))∧ (?P?(?Q∧?R))
(?P∨ (Q∧ R))∧ (P∨ (?Q∧?R)) E16
(?P∧ P)∨ (P∧ Q∧ R))∨
(?P∧?Q∧?R))∨
((Q∧ R)∧ (?Q∧?R)) 分配
F∨ (P∧ Q∧ R))∨ (?P∧?Q∧?R)∨ F 互补
(P∧ Q∧ R))∨ (?P∧?Q∧?R) 同一
(P?(Q∧ R))∧ (?P?(?Q∧?R))
(?P∨ (Q∧ R))∧ (P∨ (?Q∧?R))
(?P∨ Q)∧ (?P∨ R))∧ (P∨?Q)∧ (P∨?R)
(?P∨ Q∨(R ∧?R))∧ (?P∨(Q ∧?Q)∨ R))
∧ (P∨?Q∨(R ∧?R))∧ (P∨(Q ∧?Q)∨?R)
(?P∨ Q∨R) ∧ (?P∨ Q∨?R))∧
(?P∨Q∨ R) ∧ (?P∨?Q∨ R)∧
(P∨?Q∨R) ∧ (P∨?Q∨?R)∧
(P∨Q∨?R) ∧ (P∨?Q∨?R)
(?P∨ Q∨R) ∧ (?P∨ Q∨?R))∧
(?P∨?Q∨ R)∧ (P∨?Q∨R) ∧
(P∨?Q∨?R)∧ (P∨Q∨?R)
范式的应用
P39(7)A,B,C,D四个人中要派两个人出差，按下述三个条件有几种派法？
①若 A去则 C和 D中要去一个人。
② B和 C不能都去。
③ C去则 D要留下。
解,设 A,B,C,D分别表示 A去,B去,C去,D去。
① A?((C∧?D)∨ (?C∧ D))
A∨ (C∧?D)∨ (?C∧ D)
②?(B∧ C)B∨?C
③ CDC∨?D
总的条件为：
(?A∨ (C∧?D)∨ (?C∧ D) )∧ (?B∨?C) ∧ (?C∨?D)
令此式为真。
将 (?A∨ (C∧?D)∨ (?C∧ D) )∧ (?B∨?C)
∧ (?C∨?D) 化成析取范式。
上式?(?A∨ (C∧?D)∨ (?C∧ D) )∧
(?C∨(?B∧?D))
(?A∧?C)∨ (C∧?D∧?C)∨ (?C∧ D∧?C)∧
(?A∧?B∧?D)∨ (C∧?D∧?B∧?D)
∨ (?C∧ D∧?B∧?D)
(?A∧?C)∨F∨ (?C∧ D)∨ (?A∧?B∧?D)∨
(C∧?D∧?B)∨ F
可以取?A∧?C为 T，得 B和 D去。
取?C∧ D为 T，得 A和 D去，或者 B和 D去。
取 C∧?D∧?B为 T，得 A和 C去 。
最后得三种派法,A和 C去,A和 D去,B和 D去 。
*补充题,有工具箱 A,B,C,D，各个箱内装的工具如下表所示。试问如何携带数量最少工具箱，而所包含的工具种类齐全。
解：设 A,B,C,D分别表示带 A,B,C,D箱。
则总的条件为：
(A∨ C)∧ (A∨ B∨ D)∧ (B∨ C)∧ (B∨ D) 为真。
改锥 扳手 钳子 锤子工具箱 改 锥 扳 手 钳 子 锤 子
A 有 有
B 有 有 有
C 有 有
D 有 有将 (A∨ C)∧ (A∨ B∨ D)∧ (B∨ C)∧ (B∨ D)写成析取范式，
上式?((A∨ C)∧ (B∨ C))∧ ((A∨ (B∨ D))∧ (B∨ D)) (交换 )
((A∧ B)∨ C))∧ (B∨ D) (分配 (提取 C),吸收 )
(A∧ B∧ B )∨ (C∧ B )∨ (A∧ B∧ D)∨ (C∧ D) (分配 )
(A∧ B)∨ (C∧ B )∨ (A∧ B∧ D)∨ (C∧ D)
分别可以取 (A∧ B),(C∧ B ),(C∧ D)为真。
于是可以得到三种携带方法：
带 A和 B箱,带 B和 C箱，带 C和 D箱。
六,逻辑推理 熟练掌握三种推理方法。
P47(2)c) (A∨B)?(C∧ D),(D∨E)?F?A?F
1.直接推理
⑴ (A∨B)?(C∧ D) P
⑵?(A∨B)∨ (C∧ D) T ⑴ E16
⑶ (?A∧?B) ∨ (C∧ D) T ⑵ E9
⑷ (?A∨ C)∧(?B∨ C)∧ (?A∨ D)∧(?B∨ D) T ⑶ E7
⑸?A∨ D T ⑷ I2
⑹ A?D T ⑸ E16
⑺ (D∨E)?F P
⑻?(D∨E)∨ F T ⑺ E16
⑼ (?D∧?E)∨ F T ⑻ E9
⑽ (?D ∨ F) ∧(?E∨ F) T ⑼ E7
⑾?D∨ F T ⑽ I1
⑿ D?F T ⑾ E16
⒀ A?F T ⑹⑿ I13
P47(2)c) (A∨B)?(C∧ D),(D∨E)?F?A?F
2.条件论证
⑴ A P (附加前提 )
⑵ A∨B T ⑴ I3
⑶ (A∨B)?(C∧ D) T
⑷ C∧ D T ⑵⑶ I11
⑸ D T ⑷ I2
⑹ D∨E T ⑸ I3
⑺ (D∨E)?F P
⑻ F T ⑹⑺ I11
⑼ A?F CP
显然此方法比直接推理简单。
P47(2)c) (A∨B)?(C∧ D),(D∨E)?F?A?F
3.反证法
⑴?(A?F) P (假设前提 )
⑵?(?A∨F) T ⑴ E16
⑶ A∧?F T ⑵ E9
⑷ A T ⑶ I1
⑸ A∨B T ⑴ I3
⑹ (A∨B)?(C∧ D) T
⑺ C∧ D T ⑵⑶ I11
⑻ D T ⑷ I2
⑼ D∨E T ⑸ I3
⑽ (D∨E)?F P
⑾ F T ⑹⑺ I11
⑿?F T ⑶ I2
⒀ F∧?F T ⑾ ⑿ I9 可见此法也比较简单补充题,请根据下面事实，找出凶手：
1,清洁工或者秘书谋害了经理。
2,如果清洁工谋害了经理，则谋害不会发生在午夜前。
3.如果秘书的证词是正确的，则谋害发生在午夜前。
4.如果秘书的证词不正确，则午夜时屋里灯光未灭。
5,如果清洁工富裕，则他不会谋害经理。
6.经理有钱且清洁工不富裕。
7.午夜时屋里灯灭了。
令 A:清洁工谋害了经理。 B:秘书谋害了经理。
C:谋害发生在午夜前。 D:秘书的证词是正确的,
E:午夜时屋里灯光灭了。 H:清洁工富裕,
G:经理有钱,
命题符号为：
A∨B,AC,D?C,?DE,HA,G∧?H,E
A∨B,AC,B?C,D?C?DE,HA,G∧?H,E
⑴ E P
⑵?DE P
⑶D T ⑴⑵ I
⑷ D T ⑶ E
⑸ D?C P
⑹ C T ⑷⑸ I
⑺ AC P
⑻?A T ⑹⑺ I
⑼ A∨B P
⑽ B T⑻⑼ I
结果是秘书谋害了经理。
第一章 命题逻辑到此结束
离散数学的性质、内容
学习此课的目的
学习此课的方法一,此课的性质、内容：
数学所 研究的对象 根据它们的取值分为：
连续的,如长度、温度、面积等。
离散的,如商店商品，学生所学课程等。
离散数学 是研究离散对象的结构以及它们之间相互关系的科学。
因为计算机不论硬件还是软件都属于离散结构，所以它所应用的数学必是离散数学。
性质,此课 是计算机科学与技术专业的重要的理论 基础课,也是该专业的 主干课 。
内容,1,数理逻辑
2,集合论
3,代数系统
4,图论
*5,组合数学
*6,形式语言与自动机
(由于时间的关系，我们只讨论前四部分内容。 )
二,学习此课的目的,
1.计算机的诞生与发展和离散数学密切相关
正如马克思所说的：“一门科学，只有当它能够运用数学时，才算真正发展了。”
计算机正是在离散数学 中的图灵机的理论指导下诞生的
(1936提出图灵机 ---1946诞生计算机 )。
计算机科学的发展十分迅速，计算机的硬件从第一代起现在发展到第四代 (电子管?晶体管?集成电路?大规模集成电路 )，第五代即将问世，正在向网络化发展。而且计算机技术发展速度越来越快。
计算机应用越来越广，所有领域几乎无所不及。
计算机科学已发展成为一门一级学科。
计算机的产业已发展成为一个高科技的新兴产业
计算机科学的发展 (硬件、软件的发展 )离不开计算机的理论,例如，程序设计语言的发展,从机器语言?
汇编语言?高级面向过程语言?面向对象语言?智能语言?…,系统软件的发展,如操作系统，从单用户
多用户?网络操作系统,…,即如 DOS
Windows? Windows NT?...; 所有这些发展都依赖于离散数学、数据结构、编译原理、操作系统、数据库原理、软件工程、网络等理论。其中离散数学是基础，其它的理论中都用到了离散数学中的基本概念、
基本思想、基本方法。
这说明了理论常常可以导致实践方面的重大进展，即理论对实践的指导作用。
计算机专业的学生学习计算机不同于非计算机专业的学生学习计算机，必须掌握离散数学的理论，才能更好地了解和从事计算机科学的研究。
2.此课是主干课，也是后继课的基础课计算机专业的后续课中都大量地应用到离散数学中的基本理论，所以要想学好专业课，必须先学好离散数学。
3.培养学生抽象的思维和逻辑推理能力和创新能力在大学学习知识很重要，但是能力的培养更重要。正如著名的物理学家劳厄所说：,重要的不是获得知识，
而是发展思维能力。教育无非是一切已学过的东西都遗忘的时候，所剩下来的东西。,剩下的就是思维能力，它可以长期起作用。
正如北京大学姜伯驹教授谈到数学时说：“数学是学习科学技术的钥匙和先决条件。”所以必须提高学生的数学修养 (数学素质 )。 数学修养 包括：理解、抽象、见识、体验。
理解能力,逻辑推理能力、不同语言对应的转换能力、
想象能力等。
抽象能力,敏锐的洞察力，灵活的联想类比、举一反三能力，特别是把实际问题转化为数学问题的能力。
见识,就是让学生见识一些重要的数学思想、数学方法以及用数学解决实际问题的著名事例。有了这样见识才会思路宽，办法多，遇到问题会自觉求助于数学。
体验,数学是一种分析问题、解决问题的实践活动。与打猎一样是活本领。像转换观点、选择方法、熟悉软件、
检验结果、发现毛病、查找原因多环节只有亲身经历才能学到手。
学到这些活本领，就是一些基本素质问题。
离散数学可以帮助学生提高数学素质。提高创造力。
三,此课的特点及学习方法,
特点,内容较杂，概念多，定理多，比较抽象，给学习带来一定难度。
学习方法,
1.准确掌握每个概念 (包括内涵及外延 )。
2.要有刻苦钻研精神,不断总结经验。
3.在理解内容的基础上，要较多地做些习题，从而再进一步加深理解所学内容。
4.注意培养分析问题和解决问题的能力第一篇 数理逻辑
逻辑 --是研究人的思维的科学。
它包含：
1.辩证逻辑,是研究人的思维中的辩证法。
例 如：用全面的和发展的观点观察事物；
具体问题具体分析；
实践是检查事物正误的唯一标准；等等。
2.形式逻辑,是研究人的思维的形式和一般规律。
这里我们只关心形式逻辑。
一,形式逻辑
人的思维过程：
概念? 判断? 推理
正确的思维：
概念清楚，判断正确，推理合乎逻辑。
人们是通过各种各样的学习 (理论学习和从实践中学习 )来掌握许多概念和判断。
而形式逻辑主要是研究推理的 。
推理：
是由若干个已知的判断 (前提 )，推出新的判断 (结论 )的思维过程。
推理方法
类比推理,由个别事实推出个别结论 。
如：地球上有空气、水，地球上有生物。
火星上有空气、水。
火星上有生物 。
归纳推理,由若干个别事实推出一般结论。
如：铜能导电。铁能导电。锡能导电。铅能导电。 ……
一切金属都导电 。
演绎推理,由一般规律推出个别事实。
形式逻辑主要是研究演绎推理的。
演绎推理 举例
例 1：
如果天下雨，则路上有水。 (一般规律 )
天下雨了。 (个别事实 )
推出结论,路上有水。 (个别结论 )
例 2：
(大前提 )：所有金属都导电。 (一般规律 )
(小前提 )：铜是金属。 (个别事实 )
推出结论,铜能导电。 (个别结论 )
二,数理逻辑
数理逻辑 是用 数学的方法 研究形式逻辑。
所谓“数学方法”：是建立一套有严格定义的符号，即建立一套形式语言，来研究形式逻辑。所以数理逻辑也称为,符号逻辑,。
它与数学的其它分支、计算机科学、人工智能、语言学等学科均有密切联系。
这里只讨论,命题逻辑,和,谓词逻辑,。
下面就前面两个例子，说明如何将推理符号化的。
数理逻辑把推理符号化之一
设 P表示：天下雨。
设 Q表示：路上有水。
设?表示,如果 … 则 …
例 1的推理过程表示为：
前提 1:P?Q (如果天下雨,则 路上有水 。 )
前提 2,P (天 下雨了。 )
结 论,Q (路上有水 。 )
(这就是第一章命题逻辑中要讨论的问题 )
数理逻辑把推理符号化之二
设 M(x),x是金属,设 C(x),x能导电,
设?x 表示,所有的 x,设 a 表示铜,
例 2的推理过程表示为：
前提,?x(M(x)?C(x)) (所有金属都导电,)
前提,M(a) (铜是金属,)
结论,C(a) (铜能导电,)
(其中符号 M(x)是谓词，所以这就是第二章“谓词逻辑”中所讨论的内容,）
使用计算机必须首先学会编“程序”，那么什么是程序？
程序＝算法＋数据算法＝逻辑＋控制可见“逻辑”对于编程序是多么重要。要想学好、使用好计算机，必须学习逻辑，此外，通过学习逻辑，掌握逻辑推理规律和证明方法,会培养学生的逻辑思维能力，提高证明问题的技巧。
数理逻辑与计算机钱学森谈“计算机与数理逻辑”
电子计算机与数理逻辑具有非常密切的关系。正是在数理逻辑中，把人类的推理过程分解成一些非常简单原始的、非常机械的动作，才使得用机器代替人类的推理的设想有了实现的可能。
有了电子计算机，使用它时，必须先进行程序设计，把整个推理、计算过程，丝毫不漏地考虑到，统统编入程序，
而机器则依次而运行；如稍有错误，将立即得到毫无意义的结果。可见必须有足够的数理逻辑的训练，熟悉推理过程的全部细节,
才能从事程序设计。
此外，程序设计是一个很细致又很麻烦的工作，如何从事程序设计，如何防止在计算过程中出错，如何很快地发现这种错误而及时加以改正，都是程序设计理论 (软件理 )中非常根本又非常重要的内容，大家都认为，
这些内容都与数理逻辑息息相关。
正如著名的计算机软件大师戴克斯特拉 (E.W.Dijkstra)曾经说过,我现在年纪大了，搞了这么多年软件，错误不知犯了多少，现在觉悟了。我想，假如我早在数理逻辑上好好下点功夫的话，我就不会犯这么多错误。不少东西逻辑学家早就说过了，可是我不知道。要是我能年轻 20岁的话，我就会回去学逻辑。
第一章 命题逻辑
这章是以,命题,为中心
主要讨论：
命题的表示、命题的演算
命题演算中的公式，及其应用
命题逻辑推理
1-1,命题与命题的真值
本节主要讨论三个问题：
命题的概念
命题的真值
原子命题与复合命题一,命题的概念
命题 是一个能确定是真的或是假的判断。（判断都是用陈述句表示）
例 1-1.1 判定下面这些句子哪些是命题。
⑴ 2是个素数。
⑵ 雪是黑色的。
⑶ 2005年人类将到达火星。
⑷ 如果 a>b且 b>c，则 a>c。
⑸ x+y<5
⑹ 请打开书！
⑺ 您去吗？
⑴⑵⑶⑷是命题二,命题的真值
一个命题所作的判断有两种可能,是正确的 判断或者 是错误的 判断 。 所以一个命题的 真值 有两个：,真,或,假,
真值 为 真,一个命题所作的判断与客观一致,
则称该命题的真值为真,记作 T (True)。
真值 为 假,一个命题所作的判断与客观不一致,则称该命题的真值为假,记作 F (False)。
例 1-1.1中 (1)(4)的真值为 真,(2)的真值为 假,
(3)暂时不能定，等到 2005年确定。
三,原子命题与复合命题
简单命题 (原子命题 ),由最简单的陈述句构成的命题 (该句再不能分解成更简单的句子了 )。通常用大写英字母表示。
例 1-1.1中的 (1),(2),(3)是原子命题。
复合命题 (分子命题 ),由若干个原子命题构成的命题。
例 1-1.1中的 (4)是由三个原子命题 (a>b、
b>c,a>c)构成的复合命题。
1-2 联结词
复合命题的构成：是用“联结词”将原子命题联结起来构成的。
归纳自然语言中的联结词，定义了六个逻辑联结词，分别是：
(1) 否定,?” (2) 合取,∧,
(3) 析取,∨,(4) 异或,”
(5) 蕴涵,?” (6) 等价,?”
一,否定,?”
表示：,… 不成立,，,不 …,。
用于：对一个命题 P的否定，写成?P,并读成,非 P”。
P的真值：与 P真值相反。
例 1-2.1 P,2是素数。
P,2不是素数。
P?P
T F
F T
二,合取,∧,
表示：,并且,、,不但 … 而且,..”、
,既 … 又,..”“尽管 … 还 …,
例 1-2.2 P：小王能唱歌。
Q：小王能跳舞。
P∧ Q：小王能歌善舞。
P∧ Q读成 P合取 Q。
P∧ Q的真值为 真,当且
仅当 P和 Q的真值均为 真 。
P Q P∧ Q
F F F
F T F
T F F
T T T
三,析取,∨,、异或,”
表示,或者,
,或者”有 二义性,看下面两个例子：
例 1-2.3,灯泡 或者 线路有故障。
例 1-2.4,第一节课上数学 或者 上英语。
例 3中的 或者 是 可兼取的或 。即 析取,∨,
例 4中的 或者 是 不可兼取的或,也称之为异或,排斥或 。即,”,?
1,析取,∨,
P：灯泡有故障。
Q：线路有故障。
例 3中的复合命题可
表示为,P∨ Q，读
成 P析取 Q,P或者 Q。
P∨ Q的真值为 F，当
且仅当 P与 Q均为 F。
P Q P∨ Q
F F F
F T T
T F T
T T T
2,异或,”
P,第一节上数学 。
Q,第一节上英语。
例 4中的复合命题可写成 P Q,读成 P异或 Q。
P Q的真值为 F，
当且仅当 P与 Q的 真值相同 。
F F F
F T T
T F T
T T F
P Q P Q?
3.异或的另一种表示
异或 是表示两个命题 不可能同时都成立。
命题“第一节课上数学 或者 上英语。”可以解释为：
“第一节课上数学而没有上英语 或者 第一节课上英语而没有上数学。”
于是有
P Q 与 (P∧?Q)∨ (Q∧?P ) 是一样的。
实际应用中必须注意,或者,的二义性。
四,蕴涵 (条件 ),?”
表示“如果 … 则 …”,
例 1-2.5,P表示：缺少水分。
Q表示：植物会死亡。
P?Q：如果 缺少水分,植物就会死亡 。
P?Q：也称之为蕴涵式，读成,P蕴涵
Q”，“如果 P则 Q”。也说成 P是 P?Q 的前件,Q是 P?Q的后件。还可以说 P是 Q
的充分条件,Q是 P的必要条件。
P?Q的真值,
P?Q的真值为假，当且仅当 P为真,Q为假。 注意,当前件 P为假时,P?Q为 T。
P Q P?Q
小王借钱不还 我替他还 （我给小王担保）
F F T
F T T
T F F
T T T
充分条件,就是只要条件成立，结论就成立，
则该条件就是 充分条件 。
上例中，,缺少水分”就是“植物会死亡”
的充分条件。在自然语言中表示充分条件的词有,如果 … 则 …,只要 … 就 …,若 … 则 …
必要条件,就是如果该条件不成立，那么结论就不成立,则该条件就是 必要条件 。
上例中，,植物死亡”就是“缺少水分”的必要条件 (植物未死亡，一定不缺少水分 )。
在自然语言中表示必要条件的词有,
只有 … 才 … ； 仅当 …,… ; …,仅当 … 。
关于充分条件和必要条件的说明：
举例,
令,P：天气好。 Q：我去公园。
1.如果天气好，我就去公园。
2.只要天气好，我就去公园。
3.天气好，我就去公园。
4.仅当天气好，我才去公园。
5.只有天气好，我才去公园。
6.我去公园，仅当天气好。
命题 1.,2.,3.写成,P?Q
命题 4.,5.,6.写成,Q?P
可见,?”既表示充分条件（即前件是后件的充分条件）；
也表示必要条件（即后件是前件的必要条件）。这一点要特别注意 !!!它决定了哪个作为前件，哪个作为后件。
五,等价 (双条件）,?”
表示“当且仅当”、“充分且必要”
例 1-2.6：
P,⊿ ABC是等边三角形。
Q,⊿ ABC是等角三角形。
P?Q,⊿ ABC是等边三角形 当且仅当它 是等角三角形。
P Q P?Q
F F T
F T F
T F F
T T T
P?Q的真值,
P?Q的真值为真，当且仅当 P与 Q的真值相同。
本节小结：
要熟练掌握这五个联结词在自然语言中所表示的含义以及它们的真值表的定义。
P Q P∧ Q P∨ Q P?Q P?Q
F F F F T T
F T F T T F
T F F T F F
T T T T T T
特别要注意“或者”的二义性，即要区分给定的“或”是“可兼取的或”还是
“不可兼取的或”。
特别要注意,?”的用法，它既表示
“充分条件”也表示“必要条件”，即要弄清哪个作为前件，哪个作为后件。
练习：填空
已知 P∧ Q为 T，则 P为 ( ),Q为 ( )。
已知 P∨ Q为 F，则 P为 ( ),Q为 ( )。
已知 P为 F，则 P∧ Q为 ( )。
已知 P为 T，则 P∨ Q为 ( )。
已知 P∨ Q为 T，且 P为 F,则 Q为 ( )。
已知 P?Q为 F，则 P为 ( ),Q为 ( )。
已知 P为 F，则 P?Q为 ( )。
已知 Q为 T，则 P?Q为 ( )。
已知?PQ为 F，则 P为 ( ),Q为 ( )。
已知 P为 T,P?Q为 T，则 Q为 ( )。
已知?Q为 T,P?Q为 T，则 P为 ( )。
已知 P?Q为 T,P为 T,则 Q为 ( ).
已知 P?Q为 F,P为 T,则 Q为 ( ).
P?P 的真值为 ( ).
P?P 的真值 为 ( )。
1-3 命题公式及命题符号化一,常值命题与命题变元
常值命题,即是我们前面所说的命题。它是有具体含义 (真值 )的。例如：,3是素数。”就是常值命题。
命题变元,用大写的英字母如 P,Q等表示任何命题。称这些字母为命题变元。
对命题变元作 指派 (给命题变元一个 解释 )：将一个常值命题赋予命题变元的过程，或者是直接赋给命题变元真值,T”或,F”的过程。
注意,命题变元本身不是命题，只有给它一个解释，才变成命题。
二,合式公式 ( wff ) (well formed formulas)
1.定义：
⑴ 单个命题变元是个合式公式。
⑵ 若 A是合式公式，则?A是合式公式。
⑶ 若 A和 B是 合式公式，则 (A∧ B)，
(A∨ B),(A?B)和 (A?B)都是合式公式。
⑷ 当且仅当有限次地应用⑴，⑵，⑶所得到的含有命题变元、联结词和括号的符号串是 合式公式 。
注意这个定义是递归的。 (1)是递归的基础，由 (1)开始，使用 (2)(3)规则，可以得到任意的合式公式。
这里所谓的合式公式可以解释为合法的命题公式之意，也称之为 命题公式,有时也简称 公式 。
下面的式子不是合式公式：
P∧ Q,PR,P∨ Q∧ R
下面的式子才是合式公式：
(P∧ Q),(?P?R),((P∨ Q)∧ R)
按照 合式公式定义最外层括号必须写。
约定,为方便，最外层括号可以不写，
上面的合式公式可以写成：
P∧ Q,?P?R,(P∨ Q)∧ R
2.命题公式的 真值表一个命题公式不是复合命题，所以它没有真值，但是给其中的所有命题变元作指派以后它就有了真值。可以以表的形式反应它的真值情况，例如命题 公式 (?P?Q)∨ Q 的真值表如下所示：
P Q?P?P?Q (?P?Q)∨ Q
F F T F F
F T T T T
T F F T T
T T F T T
由于对每个命题变元可以有两个真值 (T,F)
被指派，所以有 n个命题变元的命题公式
A(P1,P2,…,P n) 的 真值表有 2n行 。
为了有序地列出公式的真值表，在对命题变元做指派时，可以按照二进制数的次序列表。
补充,关于,二进制数,见下页。
关于二进制数简介：
由于计算机的硬件是由二个状态的逻辑元件组成的，所以它只处理二进制的信息,
二进制数：只有两个基本符号 0和 1，计算时，
逢二进一,如
0+1=1,1+1=10,10+1=11,11+1=100
0 1 10 11
+ 1 + 1 + 1 + 1
1 10 11 100
十进制数 0 1 2 3 4 5 6 7 8 9
二进制数 0 1 10 11 100 101 110 111 1000 1001
注,有效数字前加 0不影响数值，如 000=0,001=1,010=10,011=11
、,、
为了 有序地列出 A(P1,P2,…,P n)的真值表，
可以将 F看成 0，将 T看成 1，按照 二进制数 00…0,00…01,00…010,…,11…10,
11…1( 即十进制的 0,1,2,….,2 n -1)的次序进行指派列真值表。
如 A(P,Q)的真值表可按照如下次序指派：
00(F,F),01(F,T),10(T,F),11(T,T)
如 A(P,Q,R)的真值表可按照如下次序指派：
000(F,F,F),001(F,F,T),010(F,T,F),011(F,T,T)
100(T,F,F),101(T,F,T),110(T,T,F),111(T,T,T)
例如列出 P?(Q?R)的真值表
P Q R Q?R P?(Q?R)
000 F F F T T
001 F F T T T
010 F T F F T
011 F T T T T
100 T F F T T
101 T F T T T
110 T T F F F
111 T T T T T
三,命题符号化所谓命题符号化，就是用命题公式的符号串来表示给定的命题。
命题符号化的方法
1.首先要明确给定命题的含义。
2.对于复合命题，找联结词，用联结词断句，分解出各个原子命题。
3.设原子命题符号，并用逻辑联结词联结原子命题符号，构成给定命题的符号表达式。
例 1.说离散数学无用且枯燥无味是不对的。
P：离散数学是有用的。
Q：离散数学是枯燥无味的。
该命题可写成,? (?P∧ Q)
例 2.如果小张与小王都不去，则小李去。
P：小张去。 Q：小王去。 R：小李去。
该命题可写成,(?P∧?Q)?R
如果小张与小王不都去，则小李去。
该命题可写成,?(P∧ Q)?R
也可以写成,(?P∨?Q)?R
例 3,仅当 天不下雨且我有时间，才上街。
P,天下雨。 Q,我有时间。 R,我上街。
分析,由于“仅当”是表示“必要条件”
的，既,天不下雨且我有时间”，是“我上街”的必要条件。所以该命题可写成,R?(?P∧ Q)
例 4.人不犯我，我不犯人；人若犯我，我必犯人。
P：人犯我。 Q：我犯人。
该命题可写成,(?PQ)∧ (P?Q)
或写成,P?Q P是 Q的充分条件P是 Q的必要条件
P是 Q的充分且必要条件
例 5,若天不下雨，我就上街；否则在家。
P,天下雨。 Q,我上街。 R：我在家。
该命题可写成,(?P?Q)∧ (P?R).
注意,中间的联结词一定是,∧,，而不是,∨,，也不是,”。
因为原命题表示：,天不下雨时我做什么,天 下雨我又做什么,的 两种作法,其中有一种作法是假的，则我说的就是假话，所以中间的联结词一定是,∧,。
如果写成 (?P?Q)∨ (P?R)，就表明 两种作法 都是假的时候，我说的才是假话。这显然不对 。
若写成 (?P?Q) (P? R)时，当 P为 F,Q为 F时，即天没下雨而我没上街，此时我说的是假话，但是表达式
(?P?Q) (P? R) 的真值却是,T”,因为此时 (P?R)的真值 是,T”。
作业题：
第 8页：（ 3）
第 12页：（ 5）、（ 7）
第 17页：（ 1） a),d)
1-4 重言式与重言蕴涵式
一,重言式 (永真式 )与矛盾式 (永假式 )
1.例子：
P?P∨ P?P∧ P
F T F
T T F
可见不论 P取什么真值?P∨ P的真值总是为真,?P∧ P的真值总是为假。故称
P∨ P为重言式 (永真式 )，称?P∧ P为矛盾式 (永假式 )。
2,重言式 (矛盾式 )定义
A(P1,P2,…,P n) 是含有命题变元 P1,P2,…,Pn的命题公式，如不论对 P1,P2,…,Pn作任何指派，都使得 A(P1,P2,…,Pn) 为 真 (假 )，则称之为 重言式 (矛盾式 ),也称之为 永真式 (永假式 )。
3.重言式的证明方法方法 1：列真值表。
方法 2：公式的等价变换，化简成,T”。
方法 3：用公式的主析取范式。
其中方法 2 和方法 3 我们在以后讨论。
方法 1,列真值表。
例如，证明 (P∧ (P?Q))?Q 为重言式。
P Q P?Q P∧ (P?Q) (P∧ (P?Q))?Q
F F T F T
F T T F T
T F F F T
T T T T T
永真式的真值表的最后一列全是,T”。
4,永真式的性质
1).如果 A是永真式，则?A是永假式。
2).如果 A,B是永真式，则 (A∧ B),(A∨ B)、
(A?B)和 (A?B)也都是永真式。
3).如果 A是永真式，则 A的置换例式也是永真式。
置换例式,A(P1,P2,…,P n) 是含有命题变元
P1,P2,…,Pn的命题公式，如果用合式公式 X替换某个 Pi(如果 Pi在 A(P1,P2,…,P n) 中多处出现，则各处均用 X替换 )，其余变元不变，替换后得到新的公式 B，则称 B是 A(P1,P2,…,P n) 的置换例式。
例如：
公式 A,P∨ (?P∧ ((P?Q)?R))
用 (D?E)替换 A中 P得到 A的置换例式 B：
(D?E)∨ (?(D?E)∧ (((D?E)?Q)?R))
如果 A是永真式，例如 A为?P∨ P,用
(D?E)替换 A中 P，得到 A的置换例式
B,? (D?E)∨ (D?E),
显然 B也是永真式。
如果可以断定给定公式是某个 永真式的置换例式的话，则这个公式也是永真式。
二,重言 (永真 )蕴涵式有些重言 (永真 )式，如 (P∧ (P?Q))?Q，
公式中间是,?”联结词，是很重要的，
称之为 重言蕴涵式。
1.定义,如果公式 A?B是 重言式，则称 A重言 (永真 )蕴涵 B，记作 A?B。
上式可以写成 (P∧ (P?Q))?Q
注意符号,?”不是联结词，它是表示公式间的,永真蕴涵,关系，也可以看成是
,推导,关系。即 A?B可以理解成由 A可推出 B，即 由 A为真，可以推出 B也为真 。
2.重言 (永真 )蕴涵式证明方法方法 1.列真值表。 (即列永真式的真值表 )
这里就不再举例了。
下面讨论另外两种方法。
A B A?B
F F T
F T T
T F F
T T T
先看一看 A?B的真值表，如果 A?B为永真式，则真值表的第三组指派不会出现。于是有下面两种证明方法。
方法 2.假设前件为真，推出后件也为真 。
例如求证：
((A∧ B)?C)∧?D∧ (?C∨ D)A∨?B
证明,设前件 ((A∧ B)?C)∧?D∧ (?C∨ D) 为真。则 ((A∧ B)?C),?D,(?C∨ D)均真，
D为 T，则 D为 F
C∨ D为 T
((A∧ B)?C为 T
如果 A为 F，则?A为 T，所以?A∨?B为 T。
如果 B为 F，则?B为 T，所以?A∨?B 为 T。
((A∧ B)?C)∧?D∧ (?C∨ D)A∨?B
得 C为 F
得 A?B为 F
方法 3.假设后件为假，推出前件也为假 。
例如求证：
((A∧ B)?C)∧?D∧ (?C∨ D)A∨?B
证明,假设后件?A∨?B为 F,则 A与 B均为 T。
1.如 C为 F，则 (A∧ B)?C为 F，所以前件
((A∧ B)?C)∧?D∧ (?C∨ D) 为 F
2.如 C为 T，则 ⑴ 若 D为 T，则?D为 F，所以前件 ((A∧ B)?C)∧?D∧ (?C∨ D) 为假
⑵ 若 D为 F，则?C∨ D为 F，所以前件 ((A∧ B)?C)∧?D∧ (?C∨ D) 为假。
((A∧ B)?C)∧?D∧ (?C∨ D)A∨?B
3.重要的重言蕴涵式 (如教材第 43页所示 )
I1.P∧ Q?P I2,P∧ Q?Q
I3,P?P∨ Q I4,Q?P∨ Q
I5,?P?P?Q I6,Q?P?Q
I7,?(P?Q)?P I8,?(P?Q)Q
I9,P,Q?P∧ Q I10,?P∧ (P∨ Q)?Q
I11,P∧ (P?Q)?Q I12,?Q∧ (P?Q)P
I13,(P?Q)∧ (Q?R)?P?R
I14,(P∨ Q)∧ (P?R)∧ (Q?R)?R
I15,A?B?(A∨ C)?(B∨ C)
I16,A?B?(A∧ C)?(B∧ C)
上述公式的证明都比较简单，可以用假设前件为 T，推出后件也为 T的方法证明。
4,性质
1).有自反性：对任何命题公式 A，有 A?A
2).有传递性：若 A?B且 B?C，则 A?C
3).有反对称性：若 A?B且 B?A，则 A?B
符号,?”表示“等价”。
本节重点掌握,永真式及永真蕴涵式的定义、证明方法、以及常用的公式。
作业,第 23页,(2) b),(6),(8) e)
1-5 等价公式
1,例子 看下面三个公式的真值表
P Q P?Q?P∨ Q?QP
F F T T T
F T T T T
T F F F F
T T T T T
从真值表可以看出，不论对 P,Q作何指派，都使得 P?Q,?P∨ Q和?QP的真值相同，表明它们之间彼此等价。
2,定义,A,B是含有命题变元 P1,P2,…,Pn
的命题公式，如不论对 P1,P2,…,Pn作任何指派，都使得 A和 B的真值相同，则称之为 A与 B等价,记作 A?B。
显然 P?QP∨ QQP
3,重要的等价公式
⑴ 对合律P?P
⑵ 幂等律 P∨ P?P P∧ P?P
⑶ 结合律 P∨ (Q∨ R)?(P∨ Q)∨ R
P∧ (Q∧ R)?(P∧ Q)∧ R
⑷ 交换律 P∨ Q?Q∨ P P∧ Q?Q∧ P
⑸ 分配律 P∨ (Q∧ R)?(P∨ Q)∧ (P∨ R)
P∧ (Q∨ R)?(P∧ Q)∨ (P∧ R)
⑹ 吸收律 P∨ (P∧ Q)?P P∧ (P∨ Q)?P
⑺ 底 -摩根定律?(P∨ Q)P∧?Q
(P∧ Q)P∨?Q
⑻ 同一律 P∨ F?P P∧ T?P
⑼ 零律 P∨ T?T P∧ F?F
⑽ 互补律 P∨?P?T P∧?P?F
⑾ P?QP∨ Q
⑿ P?QQP
⒀ P?Q?(P?Q)∧ (Q?P)
⒁ P?Q?(?P∨ Q)∧ (P∨?Q)
⒂ P?Q?(P∧ Q)∨ (?P∧?Q )
为便于记忆，将等价公式 (前 10个 )与集合论的公式比较，请看集合公式：
⑴ 对合律 ~~A?A ~A表示 A的绝对补集
⑵ 幂等律 A∪ A?A A? A?A
⑶ 结合律 A∪ (B∪ C)?(A∪ B)∪ C
A?(B? C)?(A? B)? C
⑷ 交换律 A∪ B?B∪ A A? B?B? A
⑸ 分配律 A∪ (B? C)?(A∪ B)?(A∪ C)
A?(B∪ C)?(A? B)∪ (A? C)
⑹ 吸收律 A∪ (A? B)?A A?(A∪ B)?A
⑺ 底 -摩根定律 ~(A∪ B)?~A? ~B
~(A? B)?~A∪ ~B
⑻ 同一律 A∪ Φ?A A? E?A E表示全集
⑼ 零律 A∪ E?E A? Φ?Φ
⑽ 否定律 A∪ ~A?E A? ~A?Φ
4,等价公式的证明方法
方法 1：用列真值表。（不再举例）
方法 2：用公式的等价变换,(用置换定律 )
置换定律,A是一个命题公式,X是 A中的一部分且也是合式公式，如果 X?Y，用 Y代替 A中的 X得到公式 B，则 A?B。
应用置换定律以及前面列出的等价公式可以对给定公式进行等价变换。
例题 1,求证吸收律 P∧ (P∨ Q)?P
证明 P∧ (P∨ Q)
(P∨ F)∧ (P∨ Q) (同一律 )
P∨ (F∧ Q) (分配律 )
P∨ F (零律 )
P (同一律 )
例题 2,求证 (?P∨ Q)→(P ∧ Q)?P
证明 (?P∨ Q)→(P ∧ Q)
(?P∨ Q)∨ (P∧ Q) (公式 E16)
(P∧?Q)∨ (P∧ Q) (摩根定律 )
(P∧?Q)∨ (P∧ Q) (对合律 )
P∧ (?Q∨ Q) (分配律 )
P∧ T (互补律 )
P (同一律 )
公式 E16,P?QP∨ Q
例题 3.化简?(P∧ Q)→(?P∨ (?P∨ Q))
解 原公式
(P∧ Q)∨ ((?P∨?P)∨ Q) (E16,结合 )
(P∧ Q)∨ (?P∨ Q) (对合律，幂等律 )
(P∧ Q)∨ (Q∨?P) (交换律 )
((P∧ Q)∨ Q)∨?P (结合律 )
Q∨?P (吸收律 )
公式 E16,P?QP∨ Q
5,性质
1).有自反性：任何命题公式 A，有 A?A。
2).有对称性：若 A?B，则 B?A
3).有传递性：若 A?B且 B?C，则 A?C
4).如果 A(P1,P2,…,P n)?B(P1,P2,…,P n)，则
A(?P1,?P2,…,?Pn)?B(?P1,?P2,…,?Pn)
例 A(P,Q)?P→Q B(P,Q)P∨ Q
有 A(P,Q)?B(P,Q)
A(?P,?Q)P→?Q
B(?P,?Q)?P∨?Q
可见 A(?P,?Q)?B(?P,?Q)
6.等价公式的对偶性从前面列出的等价公式看出，有很多是成对出现的。这就是等价公式的对偶性。
⑴ 对偶式,在一个只含有联结词?,∨,
∧ 的公式 A中，将 ∨ 换成 ∧,∧ 换成 ∨,
T换成 F,F换成 T，其余部分不变，得到另一个公式 A*，称 A与 A*互为对偶式。
例如,,A A*
P P
Q∧ R?Q∨ R
(P∨ T)∧?Q (P∧ F)∨?Q
⑵ 用对偶式求公式的否定定理 1-5.1 令 A(P1,P2,…,P n)是一个只含有联结词?,∨,∧ 的命题公式，则
A(P1,P2,…,P n)?A*(?P1,?P2,…,?Pn)
此定理可以反复地使用底 -摩根定律得以证明。 下面我们 验证 一下。
令 A(P,Q)?P∨ Q A*(P,Q)?P∧ Q
A(P,Q)(P∨ Q)
A*(?P,?Q)P∧?Q
可见?A(P,Q)?A*(?P,?Q)
推论,A(?P1,?P2,…,?Pn)A*(P1,P2,…,P n)
例如，利用上述求公式的否定公式求
(((P∧ Q)∨ (P∧?Q))∨ R)
((?P∨?Q)∧ (?P∨ Q))∧?R
⑶ 对偶原理 (定理 1-5.2)：
令 A(P1,P2,…,P n),B(P1,P2,…,P n)是只含有联结词?,∨,∧ 的命题公式，则如果
A(P1,P2,…,P n)?B(P1,P2,…,P n) 则
A*(P1,P2,…,P n)?B*(P1,P2,…,Pn)
证明,因为 A(P1,P2,…,P n)?B(P1,P2,…,P n)
故 A(?P1,?P2,…,?Pn)?B(?P1,?P2,…,?Pn)
而 A(?P1,?P2,…,?Pn)A*(P1,P2,…,P n)
B(?P1,?P2,…,?Pn)B*(P1,P2,…,P n)
故?A*(P1,P2,…,P n)B*(P1,P2,…,P n)
所以 A*(P1,P2,…,P n)?B*(P1,P2,…,Pn)
下面我们验证一下对偶原理：
P∨ (Q∧ R)?(P∨ Q)∧ (P∨ R)
A B
P∧ (Q∨ R)?(P∧ Q)∨ (P∧ R)
A* B*
P∨ T?T
A B
P∧ F?F
A* B*
本节要求 掌握等价公式的证明方法及记忆公式 。
作业,第 19页 (7) f) g),(8) c)
1-6.范式范式就是命题公式形式的规范形式。这里约定在范式中 只含有联结词?,∨ 和 ∧ 。
一,析取范式与合取范式
1.合取式与析取式合取式,是用,∧,联结命题变元或变元的否定构成的式子。
如 P,?P,P∧?Q,P∧?Q∧?R
析取式,是用,∨,联结命题变元或变元的否定构成的式子。
如 P,?P,P∨?Q,P∨?Q∨?R
注,∵ P∨ P?P P∧ P?P ∴ P是合 (析 )取式,
2.析取范式公式 A如果写成如下形式：
A1∨ A2∨,..∨ An (n≥1) 其中每个 Ai
(i=1,2..n)是 合取式，称之为 A的 析取范式 。
3.合取范式公式 A如果写成如下形式：
A1∧ A2∧,..∧ An (n≥1) 其中每个 Ai
(i=1,2..n)是 析取式，称之为 A的 合取范式 。
例如,P?Q 的 析取范式与合取范式：
P?Q?(P∧ Q)∨ (?P∧?Q)----析取范式
P?Q?(?P∨ Q)∧ (P∨?Q)----合取范式
4.析取范式与合取范式的写法
⑴先用相应的公式去掉?和?。
公式 E16 P?QP∨ Q
公式 E21 P?Q?(P∧ Q)∨ (?P∧?Q)
公式 E20 P?Q?(P?Q)∧ (Q?P)
再用 E16 P?Q?(?P∨ Q)∧ (P∨?Q)
⑵ 用公式的否定公式或摩根定律将?后移到命题变元之前。
A(P1,P2,…,P n)?A*(?P1,?P2,…,?Pn)
底 -摩根定律?(P∨ Q)P∧?Q
(P∧ Q)P∨?Q
⑶ 用分配律、幂等律等公式进行整理，使之成为所要求的形式。
例如求 (P?Q)?R的 析取范式与合取范式
(P?Q)?R
((?P∨ Q)∧ (P∨?Q))∨ R
(P∧?Q)∨ (?P∧ Q)∨ R ------析取范式
(P?Q)?R((P∧ Q)∨ (?P∧?Q))∨ R
((?P∨?Q)∧ (P∨ Q))∨ R
(?P∨?Q∨ R)∧ (P∨ Q∨ R) ---合取范式二,主析取范式与主 合取范式一个公式的 析取范式与合取范式的形式是不唯一的。下面定义形式唯一的 主析取范式与主 合取范式。
㈠主析取范式
1.小项
⑴定义：在一个有 n个命题变元的合取式中，每个变元必出现且仅出现一次，
称这个合取式是个 小项 。
例如，有两个变元的小项：
P∧ Q,P∧?Q,?P∧ Q,?P∧?Q
⑵ 小项的性质
m3 m2 m1 m0
P Q P∧ Q P∧?Q?P∧ Q?P∧?Q
00 F F F F F T
01 F T F F T F
10 T F F T F F
11 T T T F F F
a).有 n个变元，则有 2n个小项。
b).每一组指派有且只有一个小项为 T。
为了记忆方便，可将各组指派对应的为 T的小项分别记作 m0,m1,m2,…,m 2n-1 上例中
m0P∧?Q m1P∧ Q
m2?P∧?Q m3?P∧ Q
2.主析取范式定义析取范式 A1∨ A2∨,..∨ An,,其中每个 Ai
(i=1,2..n)都 是 小项，称之为 主析取范式 。
3.主析取范式的写法方法 Ⅰ,列真值表
⑴列出给定公式的真值表。
⑵找出真值表中每个,T”对应的小项。
(如何 根据一组指派写对应的为,T”的项：
如果变元 P被指派为 T,P在小项中以 P形式出现；如变元 P被指派为 F,P在小项中以?P形式出现 (因要保证该小项为 T))。
⑶用,∨,联结上述小项，即可。
例如求 P?Q和 P?Q的 主析取范式
P Q P?Q P?Q
F F T T
F T T F
T F F F
T T T T
P?Q? m0∨ m1∨ m3
(?P∧?Q)∨ (?P∧ Q)∨ (P∧ Q)
P?Q?m0∨ m3
(?P∧?Q)∨ (P∧ Q)
思考题,永真式的 主析取范式是什么样？
方法 Ⅱ,用公式的等价变换
⑴先写出给定公式的析取范式
A1∨ A2∨,..∨ An 。
⑵为使每个 Ai都变成小项，对缺少变元的 Ai
补全变元，比如缺变元 R，就用 ∧ 联结永真式 (R∨?R)形式补 R。
⑶用分配律等公式加以整理。
P?QP∨ Q
(?P∧ (Q∨?Q))∨ ((P∨?P)∧ Q)
(?P∧ Q)∨ (?P∧?Q)∨ (P∧ Q)∨ (?P∧ Q)
(?P∧ Q)∨ (?P∧?Q)∨ (P∧ Q)
㈡ 主 合取范式
1.大项
⑴定义,在有 n个命题变元的析取式中，每个变元必出现且仅出现一次,称之为 大项 。
例如，有两个变元的大项及其真值表：
M0 M1 M2 M3
P Q P∨ Q P∨?Q?P∨ Q?P∨?Q
F F F T T T
F T T F T T
T F T T F T
T T T T T F
⑵ 大项的性质
a).有 n个变元，则有 2n个大项。
b).每一组指派有且只有一个大项为 F。
为了记忆方便，可将各组指派对应的为 F
的大项分别记作 M0,M1,M2,…,M 2n-1 。
上例中
M0?P∨ Q M1?P∨?Q
M2P∨ Q M3P∨?Q
2.主合取范式定义合 取范式 A1∧ A2∧,.,∧ An,,其中每个 Ai
(i=1,2..n)都 是 大项，称之为 主合取范式 。
3.主合取范式的写法方法 Ⅰ,列真值表
⑴列出给定公式的真值表。
⑵找出真值表中每个,F”对应的大项。
如何 根据一组指派写对应的为,F”的大项：
如果变元 P被指派为 F,P在大项中以 P形式出现；
如变元 P被指派为 T,P在大项中以?P形式出现
(确保该大项为 F)。
⑶用,∧,联结上述大项，即可。
例如求 P?Q和 P?Q的 主合取范式
P Q P?Q P?Q
F F T T
F T T F
T F F F
T T T T
P?Q? M2P∨ Q
P?Q?M1∧ M2
(P∨?Q )∧ (?P∨ Q)
课堂练习,
1.已知 A(P,Q,R)的真值表如图：
求它的主析取和主合取范式。
2.已知 A(P,Q,R)的主析取范式中含有下面小项 m1,m3,m5,
m7求它的和主合取范式,
P Q R A(P,Q,R)
F F F T
F F T F
F T F F
F T T T
T F F T
T F T F
T T F T
T T T T
练习答案：
1.A(P,Q,R)的主析取范式,
A(P,Q,R)? m0∨ m3∨ m4∨ m6∨ m7
(?P∧?Q∧?R)∨ (?P∧ Q∧ R)∨
(P∧?Q∧?R)∨ (P∧ Q∧?R)∨ (P∧ Q ∧ R)
A(P,Q,R)的 主合取范式：
A(P,Q,R)? M1∧ M2∧ M5
(P∨ Q∨?R)∧ (P∨?Q∨ R)∧ (?P∨ Q∨?R)
2,A(P,Q,R)? M0∧ M2∧ M4 ∧ M6
(P∨ Q∨ R)∧ (P∨?Q∨ R)∧ (?P∨ Q∨ R)
∧ (?P∨?Q∨ R)
方法 Ⅱ,用公式的等价变换
⑴先写出给定公式的合取范式
A1∧ A2∧,..∧ An 。
⑵为使每个 Ai变成大项，对缺少变元的析取式 Ai补全变元，比如缺变元 R，就用 ∨
联结永假式 (R∧?R)形式补 R。
⑶用分配律等公式加以整理。
例如，求 (P?Q)?R的主合取范式
(P?Q)?R
(?P∨ Q)∨ R
(P∧?Q)∨ R
(P∨ R)∧ (?Q∨ R)
(P∨ (Q∧?Q)∨ R)∧ ((P∧?P)∨?Q∨ R)
(P∨ Q∨ R)∧ (P∨?Q∨ R)∧
(P∨?Q∨ R)∧ (?P∨?Q∨ R)
三,范式的应用范式在逻辑设计方面有广泛的应用。
例 1.加法器的设计，有两个 n位二进制数 a,b
相加和为 s(s=a+b),a,b分别写成：
a=anan-1… ai...a2a1,
+ b=bnbn-1… bi...b2b1
s= cn sn sn-1… si…s 2 s1
其中 si是第 i位 ai,bi及 ci-1 (ci-1是第 i-1位向第 i
位的 进位 ) 的和，显然 si是 ai bi及 ci-1的函数,
写成 si(ai,bi,ci-1),它与 ai,bi,ci-1的关系如下表：
ai bi ci-1 si(ai,bi,ci-1)
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 1
在电路逻辑设计中用如下逻辑部件：
非门 与门 或门根据前边的表,列出 si(ai,bi,ci-1)的主析取范式：
si(ai,bi,ci-1)=(?ai∧?bi∧ ci-1)∨ (?ai∧ bi∧?ci-1)∨
(ai ∧?bi∧?ci-1)∨ (ai∧ bi∧ ci-1)
(在指派 001,010,100,111时 si为 1)
下面设计出 si(ai,bi,ci-1)的线路图 。
a
b
a∧ba a
b a∨b
a
si(ai,bi,ci-1)=(?ai∧?bi∧ ci-1)∨ (?ai∧ bi∧?ci-1)∨
(ai ∧?bi∧?ci-1)∨ (ai∧ bi∧ ci-1)
si(ai,bi,ci-1)
ai?ai
bi?bi
Ci-1
ci-1
例 2,安排课表，教语言课的教师希望将课程安排在第一或第三节；教数学课的教师希望将课程安排在第二或第三节；教原理课的教师希望将课程安排在第一或第二节。如何安排课表，使得三位教师都满意。
令 L1,L2,L3分别表示语言课排在第一、
第二、第三节。
M1,M2,M3分别表示数学课排在第一、
第二、第三节。
P1,P2,P3分别表示原理课排在第一、
第二、第三节。
三位教师都满意的条件是：
(L1∨ L3)∧ (M2∨ M3)∧ (P1∨ P2 ) 为真。
将上式写成析取范式 (用分配律 )得：
((L1∧ M2)∨ (L1∧ M3)∨ (L3∧ M2)∨
(L3∧ M3))∧ (P1∨ P2)
(L1∧ M2∧ P1)∨ (L1∧ M3∧ P1)∨
(L3∧ M2∧ P1)∨ (L3∧ M3∧ P1)∨
(L1∧ M2∧ P2)∨ (L1∧ M3∧ P2)∨
(L3∧ M2∧ P2)∨ (L3∧ M3∧ P2)
可以取 (L3 ∧ M2∧ P1),(L1∧ M3∧ P2)为 T，
得到两种排法。
本节要掌握：
析取范式、合取范式、主析取范式、主合取范式的 写法,范式的 应用 。
作业第 39页,(2) d),
(3) d),
(4) d),
(7)
1-7,命题逻辑推理
推理 就是根据一个或几个已知的判断得出一个新的判断的思维过程。称这些已知的判断为 前提 。得到的新的判断为前提的 有效结论 。
实际上，推理的过程就是证明永真蕴含式的过程，即令 H1,H2,…,Hn是已知的命题公式 (前提 )，若有
H1∧H 2∧....∧H n? C
则称 C是 H1,H2,… Hn的 有效结论,简称结论 。
如何根据前提得到结论，需要有推理的规则。下面先介绍两个 推理规则 。
规则 P(引入前提规则 )：在推理过程中，
可以随时引入前提。
规则 T(引入结论规则 )：在推理过程中，
如果前边有一个或几个公式永真蕴涵公式 S，则可将 S纳入推理过程中。
在推理过程中，还要应用教材 43页表 1-
8.3中的永真蕴涵式 I1-I16和表 1-8.4中等价公式 E1-E22 (常用的公式要熟记 )
下面主要介绍三种推理方法：
直接推理、条件论证及反证法重要的重言蕴涵式 (如教材第 43页所示 )
I1.P∧ Q?P I2,P∧ Q?Q
I3,P?P∨ Q I4,Q?P∨ Q
I5,?P?P?Q I6,Q?P?Q
I7,?(P?Q)?P I8,?(P?Q)Q
I9,P,Q?P∧ Q I10,?P∧ (P∨ Q)?Q
I11,P∧ (P?Q)?Q I12,?Q∧ (P?Q)P
I13,(P?Q)∧ (Q?R)?P?R
I14,(P∨ Q)∧ (P?R)∧ (Q?R)?R
I15,A?B?(A∨ C)?(B∨ C)
I16,A?B?(A∧ C)?(B∧ C)
重要的等价公式,
对合律 E1P?P
交换律 E2 P∧ Q?Q∧ P E3 P∨ Q?Q∨ P
结合律 E4 P∧ (Q∧ R)?(P∧ Q)∧ R E5 P∨ (Q∨ R)?(P∨ Q)∨ R
分配律 E6 P∧ (Q∨ R)?(P∧ Q)∨ (P∧ R)
E7 P∨ (Q∧ R)?(P∨ Q)∧ (P∨ R)
底 -摩根定律 E8?(P∧ Q)P∨?Q E9?(P∨ Q)P∧?Q
幂等律 E10 P∨ P?P E11 P∧ P?P
同一律 E12 P∨ F?P E13 P∧ T?P
零律 E14 P∨ T?T E15 P∧ F?F
E16 P?QP∨ Q E17?( P?Q)?P∧?Q
E18 P?QQP E19 P?(Q?R)?(P∧ Q)?R
E20 P?Q?(P?Q)∧ (Q?P) E21 P?Q?(P∧ Q)∨ (?P∧?Q )
E22?(P?Q)?PQ
吸收律 P∨ (P∧ Q)?P P∧ (P∨ Q)?P
互补律 P∨?P?T P∧?P?F
P?Q?(?P∨ Q)∧ (P∨?Q)
一,直接推理
直接推理,就是从前提直接推出结论。
上面讲到推理的过程实际上是证明永真蕴含式的过程。只不过证明的过程采用另外一种书写格式 。
格式中包含,步骤号，给定前提或得出的结论，推理时所用规则，此结论是从哪几步得到的以及所用公式。下面请看一些例子。
例题１求证 P→Q,Q→R,P?R
证明序号 前提或结论 所用规则 从哪几步得到 所用公式
(1) P P
(2) P?Q P
(3) Q T (1)(2) I11
(4) Q→R P
(5) R T (3)(4) I11
（ 注公式 I11为,P,P→Q? Q ）
例题２求证
(P∧Q)∧(Q∨R)∧?RP
(1) Q∨R P
(2)?R P
(3) Q T (1)(2) I10
(4)?(P∧Q) P
(5)?P∨?Q T (4) E8
(6)?P T (3)(5) I10
注公式 I10为,? P,P∨Q? Q
公式 E8为,?(P∧Q)P∨?Q
例题３用命题逻辑推理方法证明下面推理的有效性：
如果我学习，那么我数学不会不及格。
如果我不热衷于玩朴克，那么我将学习。
但是我数学不及格。因此，我热衷于玩朴克。
解设 P：我学习。
Q：我数学及格。
R：我热衷于玩朴克。
于是符号化为：
P→Q,?R→P,?Q? R
P→Q,?R→P,?Q? R
(1) P→Q P
(2)?Q P
(3)?P T (1)(2) I12
(4)?R→P P
(5)R T (3)(4) I12
(6) R T (5) E1
注：公式 I12为,?Q,P→QP
公式 E1 为,R?R
例题４求证 P→(Q→S),?R∨P,Q?R→S
证明 (1) P→(Q→S) P
(2)?P∨(?Q∨S) T (1) E 16
(3)?P∨(S∨?Q) T (2) E3
(4) (?P∨S)∨?Q T (3) E5
(5) Q P
(6)?P∨S T (4)(5) I 10
(7) P→S T (6) E 16
(8)?R∨P P
(9) R→P T (8) E 16
(10) R→S T (7)(9) I 13
二,条件论证
定理 1-7.1 如果 H1∧H 2∧...∧H n∧R?Ｓ，
则 H1∧H 2∧...∧H n? R→S
证明 因为 H1∧H 2∧...∧H n∧ Ｒ?Ｓ
则 (H1∧H 2∧...∧H n∧R)?S 是永真式。
根据结合律得
((H1∧H 2∧...∧H n)∧R)→S 是永真式。
根据公式 E19得
(H1∧H 2∧...∧H n)?(R→S) 是永真式。
即 H1∧H 2∧...∧H n? R→S
定理得证。 E19,P?(Q→R)?(P∧Q)→R
此定理告诉我们，如果要证明的结论是蕴涵式 (R→S) 形式，则可以把结论中蕴涵式的前件 R作为附加前提，与给定的前提一起推出后件 S即可。
我们把上述定理写成如下规则：
规则 CP( Conditional Ｐ roof)：
如果 H1∧H 2∧...∧H n∧R? S，则
H1∧H 2∧...∧H n? R→S
下面我们用条件论证方法求证例题４
P→(Q→S),?R∨P,Q? R→S
例题５ 用条件论证，证明例题４
P→(Q→S),?R∨P,Q? R→S
证明 (1) R P(附加前提 )
(2)?R∨P P
(3) P T (1)(2) I10
(4) P→(Q→S) P
(5) Q→S T (3)(4) I 11
(6) Q P
(7) S T (5)(6) I11
(8) R→S CP
与例题４相比，因为它增加了一个附加前提，
所以推理就容易些。
例题６ 用命题逻辑推理方法证明下面推理的有效性：
如果体育馆有球赛，青年大街交通就拥挤。在这种情况下，如果小王不提前出发，就会迟到。因此，小王没有提前出发也未迟到，则体育馆没有球赛。
证明 先将命题符号化。
设 P：体育馆有球赛。
Q：青年大街交通拥挤。
R：小王提前出发。
S：小王迟到。
P→Q,(Q∧?R)→S?(?R∧?S)→?P
P→Q,(Q∧?R)→S?(?R∧?S)→?P
证明
(1)?R∧?S P(附加前提 )
(2)?R T (1) I1
(3)?S T (1) I2
(4) (Q∧?R)→S P
(5)?(Q∧?Ｒ ) T(3)(4) I12
(6)?Q∨R T (5) E 8
(7)?Q T (2)(6) I10
(8) P→Q P
(9)?P T (7)(8) I12
(10)(?R∧?S)→?P CP
三,反证法
反证法的主要思想是：假设结论不成立，
可以推出矛盾的结论 (矛盾式 )。下面先介绍有关概念和定理。
定义,设 H1,H2,...,Hn是命题公式,P1，
P2,...,Pm是公式中的命题变元，如果对所有命题变元至少有一种指派，使得
H1∧H 2∧...∧H n 的真值为 T，则称公式集合 {H1,H2,… Hn}是 相容的 (也称是 一致的 )；如果对所有命题变元每一种指派，
都使得 H1∧H 2∧...∧H n的真值为 F，则称公式集合 {H1,H2,… Hn}是 不相容的 (也称是 不一致的 )。
定理 1-7.2 若要证明相容的公式集合
{H1,H2,..,Hn}可以推出公式 C，只要证明
H1∧H 2∧...∧H n∧?C是个矛盾式即可。
证明 设 H1∧H 2∧...∧H n∧?C 是矛盾式，则
(H1∧H 2∧...∧H n∧?C)是个永真式。
上式(H1∧H 2∧...∧H n)∨C
(H1∧H 2∧...∧H n)→C
所以 H1∧H 2∧...∧H n? C
实际上，要证明 H1∧H 2∧...∧H n? C，只要证明 H1∧H 2∧...∧H n∧?C可推出矛盾式即可，即
H1∧H 2∧...∧H n∧?C? R∧?R
例７ P→Q,(?Q∨R)∧?R,?(?P∧S)S
(1)S P(假设前提 )
(2) S T (1) E1
(3)?(?P∧S) P
(4) P∨?S T (3) E8
(5) P T (2)(4) I10
(6) P→Q P
(7) Q T (5)(6) I11
(8) (?Q∨R)∧?R P
(9)?Q∨R T (8) I 1
(10)?R T (8) I2
(11) R T (7)(9) I10
(12) R∧?R T (10)(11) I9
本节要 掌握三种推理方法,按照所要求格式正确地书写推理过程。
作业
第 47页,(1) b),
(2) b),e)
(3) b),e)
(4) a),c)
(5) c)
第一章 小结知识网络,命 题原子命题 复合命题联结词命题公式永真式永真蕴涵式 等价公式 范式命题逻辑推理直接推理 间接推理条件论证反证法析取合取主析取主合取本章的重点内容、及要求：
１,逻辑联结词，要熟练掌握联结词的真值表定义以及它们在自然语言中的含义。其中特别要注意,∨,和,→,
的用法。
２,会命题符号化。
３,掌握永真式的证明方法：
(1).真值表。
(2).等价变换，化简成Ｔ。
(3).主析取范式。
４,掌握永真蕴含式的证明方法，熟练记忆并会应用
43页中表 1-8.3中的永真蕴含式。
５,掌握等价公式的证明方法，熟练记忆并会应用
43页表 1-8.4中的等价公式。
６,熟练掌握范式的写法及其应用。
７,熟练掌握三种推理方法。
第一章 习题课一,命题符号化注意讲过的命题符号化方法。
P8习题 (3)
P:天下雪。 Q:我将去镇上。 R:我有时间。
a) 如果天不下雪且我有时间，那么我将去镇上。 (?P∧R)→Q
b) 我将去镇上，仅当我有时间。 Q→R
d) 天下雪，那么我不去镇上。 P→?Q
P12习题 (5)
a) 或者你没有给我写信，或者它在途中丢失了。
显然这里的“或者”是,不可兼取的或,。
令 P:你给我写信。 Q:信在途中丢失了。
表达式为,?P Q 或 (P∧ Q)∨ (?P∧?Q)
c) 我们不能既划船又跑步。
令 P:我们划船。 Q:我们跑步。
表达式为?(P∧Q )
d)如果你来了，那么他唱不唱歌将看你是否为他伴奏而定。
令 P:你来了。 Q:你为他伴奏。 R:他唱歌。
表达式为,P→((Q→R)∧(?Q→?R))
也可以写成,P→(Q?R)
P12习题 (7)
a) 假如上午不下雨，我去看电影，否则就在家里读书或看报。
令 P:上午下雨。 Q:我去看电影。 R:我在家里读书。 S:我在家里看报。
表达式为,(?P→Q)∧(P→(R ∨ S))
不可以写成,(?P→Q) ∨ (P→(R ∨ S))
(?P→Q) ∨ (P→(R ∨ S))
(P∨ Q)∨ (?P∨ (R∨ S))
(P∨ Q)∨ (?P∨ (R∨ S))
P∨ Q∨?P∨ R∨ S
P∨?P ∨ Q∨ R∨ S
T
b) 我今天进城，除非下雨。
令 P:我今天进城。 Q:今天下雨。
表达式为,?Q→P
c) 仅当你走我将留下。
令 P:你走。 Q:我留下。
表达式为,Q→P 或者?P→?Q
二,重言式的证明方法方法 1：列真值表。
方法 2：公式的等价变换，化简成,T”。
方法 3：用公式的主析取范式。
P23 (2)证明 (P→Q)→(P→(P∧ Q))是 重言式。
方法 1:
P Q P→Q P→(P∧ Q) (P→Q)→(P→(P∧ Q))
F F T T T
F T T T T
T F F F T
T T T T T
方法 2,(P→Q)→(P→(P∧ Q))
(?P∨ Q)∨ (?P∨ (P∧ Q)) (E16)
(P∧?Q)∨ ((?P∨ P)∧ (?P∨ Q)) 摩根，分配
(P∧?Q)∨ (T∧ (?P∨ Q)) 互 补
(P∧?Q)∨ (?P∨ Q) 同一
(P∨ (?P∨ Q) )∧ (?Q∨ (?P∨ Q) 分配
((P ∨?P)∨ Q) )∧ (?Q∨ (Q∨?P) 结 合、交 换
(T∨ Q) )∧ ((?Q∨ Q)∨?P) 互 补,结 合
T∧ (T∨?P) 零律、互 补
T∧ T 零律
T 幂等方法 3 (P→Q)→(P→(P∧ Q))
(?P∨ Q)∨ (?P∨ (P∧ Q)) 去 →
(P∧?Q)∨?P∨ (P∧ Q)? 后移
(P∧?Q)∨ (?P∧ (Q∨?Q))∨ (P∧ Q) 补 变 元 Q
(P∧?Q)∨ (?P∧ Q)∨ (?P∧?Q)∨ (P∧ Q) 分配
(P∧ Q)∨ (P∧?Q)∨ (?P∧ Q)∨ (?P∧?Q)整理可见，该公式的主析取范式含有全部 (四个 )小项，
这表明 (P→Q)→(P→(P∧ Q))是永真式。
三,重言蕴涵式的证明方法方法 1.列真值表。 (即列永真式的真值表 ) (略 )
方法 2.假设前件为真，推出后件也为真。
方法 3.假设后件为假，推出前件也为假。
P12(8)e)证明
(?A?(B∨ C) )∧ (D∨ E)∧ ((D∨ E)A)? B∨ C
方法 2 证明：
设前件 (?A?(B∨ C) )∧ (D∨ E)∧ ((D∨ E)A)
为真，则?A?(B∨ C),D∨ E,(D∨ E)A 均为真。由 D∨ E,(D∨ E)A 均为真用 I11得?A为真,
又由?A?(B∨ C)为真，得 B∨ C为真。所以得
(?A?(B∨ C) )∧ (D∨ E)∧ ((D∨ E)A)? B∨ C
(?A?(B∨ C) )∧ (D∨ E)∧ ((D∨ E)A)?B∨ C
方法 3 证明：设后件 B∨ C为 F,则 B与 C均 为 F，
1,如果 D∨ E 为 T,则
1).若 A为 T，则?A为 F，则 (D∨ E)A为 F，于是前件 (?A?(B∨ C) )∧ (D∨ E)∧ ((D∨ E)A)
为 F。
2),若 A为 F,则?A为 T，于是?A?(B∨ C) 为 F，
故前件 (?A?(B∨ C) )∧ (D∨ E)∧ ((D∨ E)A)
为 F。
2.如果 D∨ E 为 F,则 前件
(?A?(B∨ C) )∧ (D∨ E)∧ ((D∨ E)A) 为 F。
∴ (?A?(B∨ C) )∧ (D∨ E)∧ ((D∨ E)A)?B∨ C
四,,等价公式的证明方法方法 1：用列真值表。（不再举例）
方法 2：用公式的等价变换,(用置换定律 )
P19(7)h)证明
((A∧B)→C)∧(B→(D∨C))?(B∧(D→A))→c
左式?(?(A∧B)∨C)∧(?B∨(D∨C)) E 16
((?A∨?B)∨C)∧(?B∨(D∨C)) 摩根
((?B ∨?A)∨C)∧((?B∨D)∨C) 交换 结合
((?B ∨?A)∧(?B∨D))∨C 分配
(?B∨(?A∧D))∨C 分配
(B∧(A∨?D))∨C 摩根
(B∧(D→A))→C E16
P19(8)c)化简 (A∧B∧C)∨(?A∧ B∧C ）
上式? (A∨?A)∧( B∧C ） 分配
T∧( B∧C ） 互补
B∧C 同一提示,化简时注意使用下面 使式子变短的公式,
分配律 E6 P∧ (Q∨ R)?(P∧ Q)∨ (P∧ R)
E7 P∨ (Q∧ R)?(P∨ Q)∧ (P∨ R)
用分配律时，是 提取公因式 。
幂等律 E10 P∨ P?P E11 P∧ P?P
同一律 E12 P∨ F?P E13 P∧ T?P
零律 E14 P∨ T?T E15 P∧ F?F
吸收律 P∨ (P∧ Q)?P P∧ (P∨ Q)?P
互补律 P∨?P?T P∧?P?F
五,范式的写法及应用
P39(4)d)写出 (P?(Q∧ R))∧ (?P?(?Q∧?R))的主析取范式和主合取范式方法 1，用真值表令 A(P,Q,R)?(P?(Q∧ R))∧ (?P?(?Q∧?R))
它的真 值 表 见 下 页。
A(P,Q,R)?m0∨ m7
(?P∧?Q∧?R)∨ (P∧ Q∧ R)
A(P,Q,R)? M1∧ M2∧ M3∧ M4∧ M5∧ M6
(P∨ Q∨?R)∧ (P∨?Q∨ R)∧ (P∨?Q∨?R)∧
(?P∨ Q∨ R)∧ (?P∨ Q∨?R)∧ (?P∨?Q∨ R)
A(P,Q,R)的主析取范式中含有小项 m0,m7。
主合取范式中含有大项 M1,M2,M3,M4,M5,M6 。
P Q R P?(Q∧ R)?P?(?Q∧?R ) A(P,Q,R)
0 F F F T T T
1 F F T T F F
2 F T F T F F
3 F T T T F F
4 T F F F T F
5 T F T F T F
6 T T F F T F
7 T T T T T T
方法 2.等价变换
(P?(Q∧ R))∧ (?P?(?Q∧?R))
(?P∨ (Q∧ R))∧ (P∨ (?Q∧?R)) E16
(?P∧ P)∨ (P∧ Q∧ R))∨
(?P∧?Q∧?R))∨
((Q∧ R)∧ (?Q∧?R)) 分配
F∨ (P∧ Q∧ R))∨ (?P∧?Q∧?R)∨ F 互补
(P∧ Q∧ R))∨ (?P∧?Q∧?R) 同一
(P?(Q∧ R))∧ (?P?(?Q∧?R))
(?P∨ (Q∧ R))∧ (P∨ (?Q∧?R))
(?P∨ Q)∧ (?P∨ R))∧ (P∨?Q)∧ (P∨?R)
(?P∨ Q∨(R ∧?R))∧ (?P∨(Q ∧?Q)∨ R))
∧ (P∨?Q∨(R ∧?R))∧ (P∨(Q ∧?Q)∨?R)
(?P∨ Q∨R) ∧ (?P∨ Q∨?R))∧
(?P∨Q∨ R) ∧ (?P∨?Q∨ R)∧
(P∨?Q∨R) ∧ (P∨?Q∨?R)∧
(P∨Q∨?R) ∧ (P∨?Q∨?R)
(?P∨ Q∨R) ∧ (?P∨ Q∨?R))∧
(?P∨?Q∨ R)∧ (P∨?Q∨R) ∧
(P∨?Q∨?R)∧ (P∨Q∨?R)
范式的应用
P39(7)A,B,C,D四个人中要派两个人出差，按下述三个条件有几种派法？
①若 A去则 C和 D中要去一个人。
② B和 C不能都去。
③ C去则 D要留下。
解,设 A,B,C,D分别表示 A去,B去,C去,D去。
① A?((C∧?D)∨ (?C∧ D))
A∨ (C∧?D)∨ (?C∧ D)
②?(B∧ C)B∨?C
③ CDC∨?D
总的条件为：
(?A∨ (C∧?D)∨ (?C∧ D) )∧ (?B∨?C) ∧ (?C∨?D)
令此式为真。
将 (?A∨ (C∧?D)∨ (?C∧ D) )∧ (?B∨?C)
∧ (?C∨?D) 化成析取范式。
上式?(?A∨ (C∧?D)∨ (?C∧ D) )∧
(?C∨(?B∧?D))
(?A∧?C)∨ (C∧?D∧?C)∨ (?C∧ D∧?C)∧
(?A∧?B∧?D)∨ (C∧?D∧?B∧?D)
∨ (?C∧ D∧?B∧?D)
(?A∧?C)∨F∨ (?C∧ D)∨ (?A∧?B∧?D)∨
(C∧?D∧?B)∨ F
可以取?A∧?C为 T，得 B和 D去。
取?C∧ D为 T，得 A和 D去，或者 B和 D去。
取 C∧?D∧?B为 T，得 A和 C去 。
最后得三种派法,A和 C去,A和 D去,B和 D去 。
*补充题,有工具箱 A,B,C,D，各个箱内装的工具如下表所示。试问如何携带数量最少工具箱，而所包含的工具种类齐全。
解：设 A,B,C,D分别表示带 A,B,C,D箱。
则总的条件为：
(A∨ C)∧ (A∨ B∨ D)∧ (B∨ C)∧ (B∨ D) 为真。
改锥 扳手 钳子 锤子工具箱 改 锥 扳 手 钳 子 锤 子
A 有 有
B 有 有 有
C 有 有
D 有 有将 (A∨ C)∧ (A∨ B∨ D)∧ (B∨ C)∧ (B∨ D)写成析取范式，
上式?((A∨ C)∧ (B∨ C))∧ ((A∨ (B∨ D))∧ (B∨ D)) (交换 )
((A∧ B)∨ C))∧ (B∨ D) (分配 (提取 C),吸收 )
(A∧ B∧ B )∨ (C∧ B )∨ (A∧ B∧ D)∨ (C∧ D) (分配 )
(A∧ B)∨ (C∧ B )∨ (A∧ B∧ D)∨ (C∧ D)
分别可以取 (A∧ B),(C∧ B ),(C∧ D)为真。
于是可以得到三种携带方法：
带 A和 B箱,带 B和 C箱，带 C和 D箱。
六,逻辑推理 熟练掌握三种推理方法。
P47(2)c) (A∨B)?(C∧ D),(D∨E)?F?A?F
1.直接推理
⑴ (A∨B)?(C∧ D) P
⑵?(A∨B)∨ (C∧ D) T ⑴ E16
⑶ (?A∧?B) ∨ (C∧ D) T ⑵ E9
⑷ (?A∨ C)∧(?B∨ C)∧ (?A∨ D)∧(?B∨ D) T ⑶ E7
⑸?A∨ D T ⑷ I2
⑹ A?D T ⑸ E16
⑺ (D∨E)?F P
⑻?(D∨E)∨ F T ⑺ E16
⑼ (?D∧?E)∨ F T ⑻ E9
⑽ (?D ∨ F) ∧(?E∨ F) T ⑼ E7
⑾?D∨ F T ⑽ I1
⑿ D?F T ⑾ E16
⒀ A?F T ⑹⑿ I13
P47(2)c) (A∨B)?(C∧ D),(D∨E)?F?A?F
2.条件论证
⑴ A P (附加前提 )
⑵ A∨B T ⑴ I3
⑶ (A∨B)?(C∧ D) T
⑷ C∧ D T ⑵⑶ I11
⑸ D T ⑷ I2
⑹ D∨E T ⑸ I3
⑺ (D∨E)?F P
⑻ F T ⑹⑺ I11
⑼ A?F CP
显然此方法比直接推理简单。
P47(2)c) (A∨B)?(C∧ D),(D∨E)?F?A?F
3.反证法
⑴?(A?F) P (假设前提 )
⑵?(?A∨F) T ⑴ E16
⑶ A∧?F T ⑵ E9
⑷ A T ⑶ I1
⑸ A∨B T ⑴ I3
⑹ (A∨B)?(C∧ D) T
⑺ C∧ D T ⑵⑶ I11
⑻ D T ⑷ I2
⑼ D∨E T ⑸ I3
⑽ (D∨E)?F P
⑾ F T ⑹⑺ I11
⑿?F T ⑶ I2
⒀ F∧?F T ⑾ ⑿ I9 可见此法也比较简单补充题,请根据下面事实，找出凶手：
1,清洁工或者秘书谋害了经理。
2,如果清洁工谋害了经理，则谋害不会发生在午夜前。
3.如果秘书的证词是正确的，则谋害发生在午夜前。
4.如果秘书的证词不正确，则午夜时屋里灯光未灭。
5,如果清洁工富裕，则他不会谋害经理。
6.经理有钱且清洁工不富裕。
7.午夜时屋里灯灭了。
令 A:清洁工谋害了经理。 B:秘书谋害了经理。
C:谋害发生在午夜前。 D:秘书的证词是正确的,
E:午夜时屋里灯光灭了。 H:清洁工富裕,
G:经理有钱,
命题符号为：
A∨B,AC,D?C,?DE,HA,G∧?H,E
A∨B,AC,B?C,D?C?DE,HA,G∧?H,E
⑴ E P
⑵?DE P
⑶D T ⑴⑵ I
⑷ D T ⑶ E
⑸ D?C P
⑹ C T ⑷⑸ I
⑺ AC P
⑻?A T ⑹⑺ I
⑼ A∨B P
⑽ B T⑻⑼ I
结果是秘书谋害了经理。
第一章 命题逻辑到此结束
