河北工业大学计算机科学技术与软件学院离散数学
Discrete Mathematics
郭永芳
guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn
离散数学是计算机出现以后迅速发展起来的一门数学分支。计算机科学就是算法的科学，而计算机所处理的对象是离散的数据，所以离散对象的处理就成了计算机科学的核心，而研究离散对象的科学恰恰就是离散数学。
离散数学是什么？
Guoyongfang.2006@yahoo.com.cn
离散数学是什么？
离散数学是现代数学的一个重要分支，
是计算机类专业的重要课程。它以 研究离散量的结构及其相互间的关系 为主要目标，其研究对象一般是有限个或可数个元素，因此离散数学可以充分描述计算机学科离散性的特点。
Guoyongfang.2006@yahoo.com.cn
关于离散数学的一些应用一个邮递员从邮局出发，要走完他所管辖的街道，他应该怎样选择什么样的路径，这就是著名的 "中国邮递员问题
"，由中国离散数学家管梅谷教授提出，
著名离散数学家 J,Edmonds和他的合作者给出了一个解答。
Guoyongfang.2006@yahoo.com.cn
一个班级的学生共计选修 A,B,C、
D,E,F六门课程，其中一部分人同时选修 D,C,A，一部分人同时选修 B,C、
F，一部分人同时选修 B,E，还有一部分人同时选修 A,B，期终考试要求每天考一门课，六天内考完，为了减轻学生负担，要求每人都不会连续参加考试，
试设计一个考试日程表。
关于离散数学的一些应用
Guoyongfang.2006@yahoo.com.cn
一个人带着一只狼、一只羊和一捆草要渡河，由于船太小，人做摆渡者一次只能运送一个,乘客,,很显然，如果人不在，狼要吃羊，羊要吃草，问人怎样才能把它们平安地渡过河去？
关于离散数学的一些应用
Guoyongfang.2006@yahoo.com.cn
网络计划技术我们还会遇到更复杂的调度和安排问题。例如，在生产原子弹的曼哈顿计划中，涉及到很多工序，许多人员的安排，很多元件的生产，怎样安排各种人员的工作，以及各种工序间的衔接，从而使整个工期的时间尽可能短？这些都是离散数学典型例子。
关于离散数学的一些应用
Guoyongfang.2006@yahoo.com.cn
一个通讯网络怎样布局最节省？美国的贝尔实验室和 IBM公司都有世界一流的离散数学家在研究这个问题，这个问题直接关系到巨大的经济利益。
我们知道，用形状相同的方型砖块可以把一个地面铺满（不考虑边缘的情况），但是如果用不同形状，而又非方型的砖块来铺一个地面，能否铺满呢？
这不仅是一个与实际相关的问题，也涉及到很深的离散数学问题。
关于离散数学的一些应用
Guoyongfang.2006@yahoo.com.cn
航空调度和航班的设定也是离散数学的问题。怎样确定各个航班以满足不同旅客转机的需要，同时也使得每个机场的航班起落分布合理。此外，在一些航班有延误等特殊情况下，
怎样作最合理的调整，这些都是离散数学的问题。
对于城市的交通管理，交通规划，哪些地方可能是阻塞要地，哪些地方应该设单行道，
立交桥建在哪里最合适，红绿灯怎样设定最合理，如此等等，全是离散数学的问题。
关于离散数学的一些应用
Guoyongfang.2006@yahoo.com.cn
离散数学中有一个著名问题：是否存在稳定婚姻的问题。假如能找到两对夫妇（如张
（男） --李（女）和赵（男） --王（女）），
如果张（男）更喜欢王（女），而王（女）也更喜欢张（男），那么这样就可能有潜在的不稳定性。离散数学的方法可以找到一种婚姻的安排方法，使得没有上述的不稳定情况出现
（当然这只是理论上的结论）。这种离散数学的方法却有一个实际的用途：美国的医院在确定录取住院医生时，他们将考虑申请者的志愿的先后次序，同时也给申请排序。按这样的次序考虑出的总的方案将没有医院和申请者两者同时后悔的情况。实际上，高考学生的最后录取方案也可以用这种方法。
关于离散数学的一些应用
Guoyongfang.2006@yahoo.com.cn
总之，离散数学无处不在，它的主要应用就是在各种复杂关系中找出最优的方案。所以离散数学完全可以看成是一门量化的关系学,一门量化了的运筹学,一门量化了的管理学 。
关于离散数学的一些应用
Guoyongfang.2006@yahoo.com.cn
离散数学是理论性较强的学科，学习离散数学的关键是 对离散数学（集合论、数理逻辑和图论）有关基本概念的准确掌握，对基本原理及基本运算的运用，并要多做练习 。
如何学习离散数学
Guoyongfang.2006@yahoo.com.cn
离散数学课程设置计算机系核心课程信息类专业必修课程其它类专业的重要选修课程
Guoyongfang.2006@yahoo.com.cn
离散数学相关课程数字逻辑、计算机图像处理、数据结构、编译技术、算法分析与设计、人工智能、数据库,……
Guoyongfang.2006@yahoo.com.cn
离散数学的内容安排第一篇：数理逻辑命题逻辑、谓词逻辑第二篇：集合论集合与关系、寒暑第三篇：代数系统代数结构第四篇：图论图论
Guoyongfang.2006@yahoo.com.cn
离散数学课程安排课堂讲授,64学时上机实验,8学时考试课期末考试,70%
平时成绩：出勤 +作业 +实验 =30%
Guoyongfang.2006@yahoo.com.cn
第一篇 数理逻辑数理逻辑是用数学的方法研究思维规律的一门学科。由于它使用了一套符号，简洁的表达出各种推理的逻辑关系，
因此数理逻辑一般又称为符号逻辑。
数理逻辑和计算机的发展有着密切的联系，它为机器证明、自动程序设计、
计算机辅助设计等计算机应用和理论研究提供必要的理论基础。
Guoyongfang.2006@yahoo.com.cn
为什么研究数理逻辑？
数理逻辑,用数学的方法来研究推理规律的科学 。
程序＝算法＋数据算法＝逻辑＋控制
Guoyongfang.2006@yahoo.com.cn
数理逻辑的内容,
古典数理逻辑：
命题逻辑、谓词演算现代数理逻辑：
公理化集合论、递归论、模型论、证明论
Guoyongfang.2006@yahoo.com.cn
命题逻辑 (Proposition Logic)
研究以命题为基本单位构成的前提和结论之间的可推导关系。
Guoyongfang.2006@yahoo.com.cn
什么是命题？
在数理逻辑中，为了表达概念，陈述理论和规则，
常常需要应用语言进行描述，但是日常使用的自然语言，往往叙述时不够确切，也容易产生二义性，因此就需要引入一种目标语言，这种目标语言和一些公式符号，就形成了数理逻辑的形式符号体系。
所谓目标语言就是表达判断的一些语言的汇集，
而判断就是对事物有肯定或否定的一种思维形式，因此能表达判断的语言是陈述句，它称作命题。
Guoyongfang.2006@yahoo.com.cn
具有 确切真值 的 陈述句 称为 命题,该命题可以取一个,值,,称为 真值 。
,真,和,假,两种，分别用,Ｔ,(或,1”)和,Ｆ,(或,0”)
表示。
什么是命题？
Guoyongfang.2006@yahoo.com.cn
命题及其表示方法命题的语句形式陈述句非命题语句：
疑问句命令句（祈使句）
感叹句
Guoyongfang.2006@yahoo.com.cn
例题：
加拿大是一个国家。
北京是中国的首都。
1＋ 101＝ 110。
３＋２ ≥ 10。
我喜欢踢足球。
Guoyongfang.2006@yahoo.com.cn
例题：
全体立正！
这朵花真漂亮！
你想喝水吗？
X=0
我正在说的这句话是谎话 。
Guoyongfang.2006@yahoo.com.cn
悖论罗素悖论：
城里所有不自己刮脸的男人都由我给他们刮脸，我也只给这些人刮脸。
悖论：悖论是自相矛盾的命题。即如果承认这个命题成立，就可推出它的否定命题成立；反之，如果承认这个命题的否定命题成立，又可以推出这个命题成立。
Guoyongfang.2006@yahoo.com.cn
悖论另一个悖论的例子是：某国有一条法律，每一个旅游者都要回答卫兵一个问题：你来这里做什么？如果旅游者回答对了就放行。
如果回答错了，他就要被绞死。一天，有个旅游者回答：我来这里是要被绞死的。
卫兵听了后则慌了神，因为如果他们不把这个人绞死，这个旅游者就回答错了，就得受绞刑。可是，如果卫兵绞死他，旅游者就说对了，那就不应该绞死他。
Guoyongfang.2006@yahoo.com.cn
命题及其表示命题的符号表示：
大写英文字母,P,Q,R、
数字,[12],[13]
命题真值（ Truth Values）的表示：
真,1,T
假,0,F
命题标识符：表示命题的符号命题常量：命题标识符表示确定的命题命题变量：命题标识符只表示任意命题的位置标志,不是命题指派：对命题变元用一个特定的命题取代
Guoyongfang.2006@yahoo.com.cn
原子命题和复合命题原子命题：不能分解为更简单的陈述语句的命题。
复合命题,可以 分解 为更为简单命题的命题。由联结词、标点符号和原子命题复合构成的命题。
而且这些简单命题之间是通过如,或者,,
,并且,,,不,,,如果,..则,..”,,当且仅当,等这样的关联词和标点符号复合而构成一个复合命题。
Guoyongfang.2006@yahoo.com.cn
原子命题和复合命题
今天天气很冷。
今天天气很冷并且刮风。
今天天气很冷并且刮风，但室内暖和。
Guoyongfang.2006@yahoo.com.cn
1.2 联结词（否定）
定义,设 P为一命题,P的否定是一个新的命题，记作?P。 相当于自然语言中的
,非,,,不,等。
例如：
P：天津是直辖市。
P,天津不是直辖市。
P：雪是黑的。
P,雪不是黑的。
Guoyongfang.2006@yahoo.com.cn
否定 联结词特点：若 P为 T，则?P为 F；若 P为 F，则?P为 T。
否定 是一个一元运算
P ┐ P
F T
T F
Guoyongfang.2006@yahoo.com.cn
1.2 联结词（合取）
定义：两个命题 P和 Q的合取相当于一个复合命题，记作 P ∧ Q。 ∧ 相当于自然语言中的“与”,但并不完全相同。
例如：
P：今天下雨。
Ｑ,明天下雨。
P ∧ Q：今天和明天都下雨。
Guoyongfang.2006@yahoo.com.cn
合取 联结词特点：Ｐ和Ｑ同时为Ｔ时,P ∧ Q为Ｔ。
合取 是二元运算
P Q P∧Q
F F F
F T F
T F F
T T T
Guoyongfang.2006@yahoo.com.cn
1.2 联结词（析取）
定义：两个命题 P和 Q的合取相当于一个复合命题，记作 P ∨ Q。 ∨ 相当于自然语言中的“可兼或”。
例如：
P：今天下雨。
Ｑ,明天下雨。
P ∨ Q：今天或明天下雨。
Guoyongfang.2006@yahoo.com.cn
1.2 联结词（析取）
排斥或例如：我今天上午去学校或者在家休息。
可兼或例如：他可能是１００米冠军或４００米冠军。
其它：
例如：他中午吃了两个或三个包子。
Guoyongfang.2006@yahoo.com.cn
1.2 联结词（析取）
特点：当且仅当Ｐ、Ｑ同时为Ｆ时,P ∨ Q记作Ｆ，否则 P ∨ Q记作Ｔ。
析取 是二元运算
P Q P∨ Q
F F F
F T T
T F T
T T T
Guoyongfang.2006@yahoo.com.cn
1.2 联结词（条件）
定义：给定两个命题Ｐ和Ｑ，其条件命题是一个复合命题，记作 P→ Q,读作 如果Ｐ，
那么Ｑ 或者读作 若Ｐ则Ｑ。
例如：
P：今天下雨。
Ｑ,明天下雨。
P→ Q,如果今天下午，那么明天下雨。
Guoyongfang.2006@yahoo.com.cn
1.2 联结词（条件）
在自然语言中,,如果．．．,与,那么．．．,之间常常是有因果联系的，否则就没有意义。但是对于条件命题 P→ Q而言，
只要Ｐ和Ｑ能够分别确定真值,P→Q 即成为命题 。
在自然语言中，若前提为假，则不论结论是真或假，这个语句的意义往往无法判断 。 在条件命题中，规定为“善意的推定,,即前提为Ｆ时，条件命题的真值都取为Ｔ。
Guoyongfang.2006@yahoo.com.cn
1.2 联结词（条件）
特点,P→Q 为假当且仅当 P为真 Q为假二元运算
P Q P→ Q
F F T
F T T
T F F
T T T
Guoyongfang.2006@yahoo.com.cn
1.2 联结词（双条件）
定义：给定两个命题Ｐ和Ｑ，其复合命题 P
Q称作双条件命题,读作Ｐ当且仅当
Ｑ。
例如：
P：今天下雨。
Ｑ,明天下雨。
P? Q,今天下雨，当且仅当明天下雨。
Guoyongfang.2006@yahoo.com.cn
1.2 联结词（双条件）
特点,P?Q为真当且仅当 P,Q同为真假二元运算，可以不顾因果关系，而只根据联结词定义确定真值。
P Q P? Q
F F T
F T F
T F F
T T T
Guoyongfang.2006@yahoo.com.cn
联结词小结联接词 记号 记法 真值结果否定 ┐ ┐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同为真假
Guoyongfang.2006@yahoo.com.cn
联结词
⑴ 用复合命题表示如下图所示的开关电路图 1 图 2 图 3
P Q P
P
Q
A∧B A∨B A
设,A：开关Ｐ闭合； B：开关Ｑ闭合。
Guoyongfang.2006@yahoo.com.cn
联结词
⑵．用复合命题表示如下图所示的逻辑电路。
P
Q
P
Q
P
QP?
QP?
P?
Guoyongfang.2006@yahoo.com.cn
联结词
伦敦不是一个城市。
今天下雨或者刮风。
3是奇数并且 3是素数。
如果河水泛滥，那么庄稼将被毁坏。
ａ ＋ｂ＝ａ当且仅当ｂ＝ 0。
符号化下述命题：
Guoyongfang.2006@yahoo.com.cn
联结词
设 P：伦敦是一个城市。
则命题可表示为 ┐ P。
设 P：今天下雨。 Q：今天刮风。
则命题可表示为 P∨ Q。
设 P,3是奇数。 Q,3是素数。
则命题可表示为 P∧ Q。
设 P：河水泛滥。 Q：庄稼被毁坏。
则命题可表示为 P→ Q。
设 P：ａ＋ｂ＝ａ。 Q：ｂ＝ F。
则命题可表示为 P?Q。
Guoyongfang.2006@yahoo.com.cn
1-3 命题公式与翻译命题公式：
设 P和 Q是任意两个命题，则 ┐ P,P∨ Q，
P∧ Q,P?（ Q ∧ P）都是复合命题。
若 P和 Q是命题变元，则上述各式均称作命题公式。 P和 Q分别称作命题公式的分量。
注意：命题公式是没有真假的，仅当在一个公式中命题变元用确定的命题带入时，才得到一个命题。这个命题的真值，依赖于代换变元的那些命题的真值。
Guoyongfang.2006@yahoo.com.cn
命题演算的合式公式命题演算的合式公式,
1.命题变元本身是一个合式公式；
2.如 P是公式，则 (┐P) 也是合式公式；
3.如 P,Q是公式，则 (P∧Q),(P∨Q),(P→Q),
(P?Q)也是合式公式 ；
4.命题公式仅由有限步使用规则 1-3后产生的结果。
Guoyongfang.2006@yahoo.com.cn
符号串,((P∧ (Q∨ R))→ (Q∧ (┐ S∨ R))) ；
(┐ (P∧ Q))； (P→ (┐ (P∧ Q)))；
(((P→ Q)∧ (R→ Q))→ (P→ R))。
等都是命题公式。
符号串,(P→ Q)∧┐ Q)； (P→ Q；
(┐ P∨ Q∨ (R； P∨ Q∨ 。
等都不是合法的命题公式。
命题公式与翻译
Guoyongfang.2006@yahoo.com.cn
命题公式与翻译为了不使句子产生混淆，作如下约定,
命题联结词之优先级如下：
1,否定 → 合取 → 析取 → 条件 → 双条件
2,同级的联结词,按其出现的先后次序 (从左到右 )
3,若运算要求与优先次序不一致时,可使用括号 ；同级符号相邻时,也可使用括号 。
括号中的运算为最优先级 。
Guoyongfang.2006@yahoo.com.cn
命题公式与翻译设命题 P：明天上午七点下雨；
Q：明天上午七点下雪；
R：我将去学校。
符号化下述语句：
如果明天上午七点不是雨夹雪，则我将去学校 。
┐ (P∧Q)→R
如果明天上午七点不下雨并且不下雪，则我将去学校。
(┐ P∧┐Q)→R
Guoyongfang.2006@yahoo.com.cn
命题公式与翻译
如果明天上午七点下雨或下雪，则我将不去学校。
(P∨Q)→┐R
明天上午我将雨雪无阻一定去学校。
(P∧Q∧R)∨(┐P∧Q∧R)∨
(P∧┐Q∧R)∨(┐P∧┐Q∧R) 。
或 ((P∧Q)∨(┐P∧Q)∨(P∧┐Q)
∨(┐P∧┐Q))∧R
Guoyongfang.2006@yahoo.com.cn
命题公式与翻译设命题 P：你陪伴我；
Q：你代我叫车子；
R：我将出去。
符号化下述语句：
⑴．除非你陪伴我或代我叫车子，否则我将不出去。
⑵．如果你陪伴我并且代我叫辆车子，则我将出去。
⑶．如果你不陪伴我或不代我叫辆车子，我将不出去。
解,句子⑴可符号化为,┐( P∨Q)→┐R 。
句子⑵可符号化为,(P∧Q)→R 。
句子⑶可符号化为,(┐ P∨┐Q)→┐R 。
Guoyongfang.2006@yahoo.com.cn
例如：
1.上海到北京的 14次列车是下午 5点半开或
6点开。
2.他虽聪明，但不用功。
3.我既不看电视也不外出，我在睡觉。
4.如果你来了，那么他唱不唱歌将看你是否伴奏而定。
命题公式与翻译
Guoyongfang.2006@yahoo.com.cn
命题公式与翻译自然语言中的一些联结词，如,与,,
,且,,,或,,,除非,等等都各有其具体含义，因此需分不同情况翻译成适当的逻辑联结词。为了便于正确表达命题间的相互关系，又是也常常采用列出,真值表,的方法，进一步分析各命题，以此寻找逻辑联结词，使原来的命题能够正确地用形式符号予以表达。
Guoyongfang.2006@yahoo.com.cn
1－ 4 真值表与等价公式真值表 在命题公式中，对于分量指派真值得各种可能组合，就确定了这个命题公式的各种真值情况，把它汇列成表，就是命题公式的真值表。
一般来说，若有ｎ个命题变元，则应有 2n个不同的解释。
Guoyongfang.2006@yahoo.com.cn
例,设有公式,G＝ (P∧ Q)→ R 其中,P,Q
,R是 G的所有命题变元，则其真值表如下：
P Q R P∧Q (P∧Q)→R
F F F F T
F F T F T
F T F F T
F T T F T
T F F F T
T F T F T
T T F T F
T T T T T
真值表与等价公式
Guoyongfang.2006@yahoo.com.cn
真值表与等价公式该真值表可简化为：
P Q R (P∧Q)→R
F F F T
F F T T
F T F T
F T T T
T F F T
T F T T
T T F F
T T T T
Guoyongfang.2006@yahoo.com.cn
真值表
1,┐ P ∨Q
2,┐ Q → ┐ P
3,(p →Q ) ∧ (Q →P )
4,(p ∧ Q) ∨ ( ┐ p ∧ ┐ Q)
Guoyongfang.2006@yahoo.com.cn
真值表与等价公式例,列出公式：
G＝ P∧┐ P的真值表。
解：公式 G仅含 一 个命题变元，所以真值表如下
P P∧┐ P
F F
T F
Guoyongfang.2006@yahoo.com.cn
真值表与等价公式例,列出公式：
G＝ P ∨ ┐ P的真值表。
解：公式 G仅含 一 个命题变元，所以真值表如下
P P ∨ ┐ P
F T
T T
Guoyongfang.2006@yahoo.com.cn
1-4 真值表与等价公式有一类公式，不论命题变元作何种指派，其真值用为真（假），我们把这类公式记作 T（ F）。
Guoyongfang.2006@yahoo.com.cn
真值表与等价公式某些命题公式在分量的不同指派下，
其对应的真值与另一个命题公式完全相同。
Guoyongfang.2006@yahoo.com.cn
等价给定两个命题公式 A和 B，设 P1,P2,…,
Pn为所有出现于 A和 B中的原子变元，若给 P1，
P2,…,Pn任一组真值指派,A和 B的真值都相同，则称 A和 B是等价的或逻辑相等。记作 A
B?
Guoyongfang.2006@yahoo.com.cn
等价的证明证明,
P? Q (┐ P ∨Q) ∧ (P ∨ ┐ Q)?
Guoyongfang.2006@yahoo.com.cn
等价定义 1-4.3
如果 X是合式公式 A的一部分，且 X本身也是一个合式公式，则称 X为公式 A的子公式。
定理 1-4.1
设 X是合式公式 A的子公式，若 X等价于 Y，如果将 A中的 X用 Y来置换，所得到的公式 B与
A等价。
Guoyongfang.2006@yahoo.com.cn
小结证明等价的方法：
1.使用真值表
2.使用等价置换
Guoyongfang.2006@yahoo.com.cn
证明：
┐ (P→ Q)＝ P∧ ┐ Q
(P→ Q) ∧ (R→ Q) ＝ (P ∨ R) → Q
化简下式：
（ A ∧ B ∧ C） ∨ （ ┐ A ∧ B ∧ C）
如果 AVC=BVC，是否有 A=B？如果 A ∧ C=
B ∧ C是否有 A=B？如果 ┐ A = ┐ B，是否有 A=B。
真值表与等价公式
Guoyongfang.2006@yahoo.com.cn
1-5 重言式与蕴含式定义 1-5.1
给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为 T，则称该命题公式为重言式或永真式。
定义 1-5.2
给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为 F，则称该命题公式为矛盾式或永假式。
Guoyongfang.2006@yahoo.com.cn
定理 1-5.1
任何两个重言式的合取或析取，仍然是一个重言式。
定理 1-5.2
一个重言式，对同一个分量都用任何合式公式置换，其结果仍为一重言式。
定理 1-5.3
设 A,B是两个命题公式,A等价于 B当且仅当 A当且仅当 B为一个重言式。
1-5 重演式与蕴含式
Guoyongfang.2006@yahoo.com.cn
小结证明等价的方法：
1.使用真值表
2.使用等价置换
3.设 A,B是两个命题公式,A等价于 B当且仅当 A当且仅当 B为一个重言式。
Guoyongfang.2006@yahoo.com.cn
蕴含式定义 1-5.3
当且仅当 P→Q 是一个重言式时，我们称
,P蕴含 Q”，并记作 P Q。
逆换式,Q→P
反换式,┐ P→ ┐ Q
逆反式,┐ Q→ ┐ P
Guoyongfang.2006@yahoo.com.cn
除真值表外,还有两种方法：
① 前件真导后件真方法设公式的前件为真,若能推导出后件也为真,则条件式是永真式,故蕴涵式成立 。
因为欲证 A?B,即证 A?B是永真式 。 对于
A?B,除在 A取真和 B取假时,A?B为假外,
余下 A?B皆为真 。 所以,若 A?B的前件 A
为真,由此可推出 B亦为真,则 A?B是永真式,即 A?B。
蕴含式证明方法
Guoyongfang.2006@yahoo.com.cn
② 后件假导前件假方法设条件式后件为假，若能推导出前件也为假，则条件式是永真式，即蕴涵式成立。
因为若 A→ B的后件 B取假，由此可推出 A取假，即推证了,?BA。又因
A→ BB→?A，故 A?B成立。
蕴含式证明方法
Guoyongfang.2006@yahoo.com.cn
例题
（ 1）试验证 P?Q,Q逻辑蕴含 P
（ 2）（ P → Q）? P → （ P ∧ Q ）
Guoyongfang.2006@yahoo.com.cn
常用蕴含式
P ∧ Q? P P ∧ Q? Q
P? P ∨ Q ┐ P? P → Q
Q? P → Q
┐ （ P → Q ）? P
┐ （ P → Q ）? ┐ Q
P ∧ （ P → Q ）? Q
Guoyongfang.2006@yahoo.com.cn
┐ Q ∧ （ P → Q ）? ┐ P
┐ P ∧( P∨Q )?Q
(P→ Q) ∧ （ Q→ R）?P→ R
(P∨Q ) ∧ ( P→ R) ∧( Q→ R)?R
( P→ Q) ∧( R→ S)?(P∧ R)→ (Q∧ S)
(P?Q)∧ (Q?R)?(P?R)
常用蕴含式
Guoyongfang.2006@yahoo.com.cn
等价式与蕴含式之间的关系定理 1-5.4
设 P,Q为任意两个命题公式,P等价于 Q的充分必要条件是 P蕴含 Q，且 Q蕴含 P。
Guoyongfang.2006@yahoo.com.cn
小结证明等价的方法：
1.使用真值表
2.使用等价置换
3.设 A,B是两个命题公式,A等价于 B当且仅当 A当且仅当 B为一个重言式。
4.设 P,Q为任意两个命题公式,P等价于 Q
的充分必要条件是 P蕴含 Q，且 Q蕴含 P。
Guoyongfang.2006@yahoo.com.cn
蕴含的几个性质设 A,B,C为合式公式
1.若 A蕴含 B且 A是重言式，则 B必为重言式。
2.若 A蕴含 B,B蕴含 C，则 A蕴含 C，即蕴含关系是传递的。
3.若 A蕴含 B，且 A蕴含 C，则 A蕴含 B合取 C。
4.若 A蕴含 B，且 C蕴含 B，则 A析取 C蕴含 B。
Guoyongfang.2006@yahoo.com.cn
例题如果我学习，那么我数学不会不及格。
如果我不热衷于玩扑克，那么我将学习。
但我数学不及格。
因此我热衷于玩扑克。
Guoyongfang.2006@yahoo.com.cn
例题如果 6是偶数，则 7被 2除不尽。
或 5不是素数，或 7被 2除尽。
但 5是素数。
所以 6是奇数。
Guoyongfang.2006@yahoo.com.cn
证,P∨┐((P∨┐Q)∧Q)
P∨┐(P∨┐Q)∨┐Q
(P∨┐Q)∨┐(P∨┐Q)
T
重言式与蕴含式
P∨┐ ((P∨┐ Q)∧ Q) 是永真公式。
Guoyongfang.2006@yahoo.com.cn
联结词小结联接词 记号 记法 真值结果否定 ┐ ┐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同为真假
Guoyongfang.2006@yahoo.com.cn
1-6其他联结词设 P和 Q是任两个原子命题,
① 由合取非联结词 ↑ 和 P,Q连接成 P↑ Q，
称它为 P和 Q的合取非式复合命题,读作
,P合取非 Q”。 P↑ Q的真值由命题 P和 Q
的真值确定：当且仅当 P和 Q均为 Ｔ 时,
P↑ Q为 Ｆ,否则 P↑ Q为 Ｔ 。,合取非,
又常称为,与非,。
Guoyongfang.2006@yahoo.com.cn
② 由析取非联结词 ↓ 和 P,Q连接成 P↓ Q，
称它为 P和 Q的析取非式复合命题，读作
,P析取非 Q”。 P↓ Q的真值由 P和 Q的真值确定：当且仅当 P和 Q均为Ｆ时，
P↓ Q为Ｔ，否则 P↓ Q为Ｆ。,析取非,
又常称为,或非,。
1-6其他联结词
Guoyongfang.2006@yahoo.com.cn
③ 由条件非联结词?和 P,Q连接成 P?Q，称它为 P和 Q的条件非式复合命题，读作,P
条件非 Q”。 P?Q的真值由 P和 Q的真值确定：当且仅当 P为 Ｔ 而 Q为 Ｆ 时,P?Q为
Ｔ ；否则 P?Q为 Ｆ 。
1-6其他联结词
Guoyongfang.2006@yahoo.com.cn
④ 由双条件非联结词?把 P,Q连接成 P?Q，
称它为 P和 Q的双条件非式复合命题，读作,P双条件非 Q”。 P?Q的真值由 P和 Q
的真值确定：当且仅当 P和 Q的真值不同时,P?Q为 Ｔ,否则 P?Q为 Ｆ 。,双条件非,又常称为,异或,,也常用符号?
表示之。
1-6其他联结词
Guoyongfang.2006@yahoo.com.cn
联结词的真值关系
P Q P? Q P? Q P? Q P? Q
0 0
0 1
1 0
1 1
1 1 0 0
1 0 0 1
1 0 1 1
0 0 0 0
Guoyongfang.2006@yahoo.com.cn
联结词的等价关系由表可知,① P?Q(P?Q)
② P?Q(P?Q)
③ P?Q(P?Q)
④ P?Q(P?Q)
Guoyongfang.2006@yahoo.com.cn
与非、或非和异或的性质与非,或非以及异或在计算机科学中是经常使用的 3个联结词,因此,掌握它们的性质是十分必要的 。 令 P,Q和 R是原子命题变元 。
① 与非的性质
(a) P↑ Q?Q↑ P
(b) P↑ PP
(c) (P↑ Q)↑ (P↑ Q)?P∧ Q
(d) (P↑ P)↑ (Q↑ Q)?P∨ Q
Guoyongfang.2006@yahoo.com.cn
② 或非的性质
(a) P↓ Q?Q↓ P
(b) P↓ PP
(c) (P↓ Q)↓ (P↓ Q)?P∨ Q
(d) (P↓ P)↓ (Q↓ Q)?P∧ Q
从上述的性质可知，联结词?,?和?可分别用联结词?或者?取代，读者可以自行验证,?和?
都不满足结合律。
与非、或非和异或的性质
Guoyongfang.2006@yahoo.com.cn
③
(a) P?Q?Q?P
(b) P?(Q?R)?(P?Q)?R
(c) P∧ (Q?R)?(P∧ Q)?(P∧ R)
(d) P?P?F,F?P?P,T?PP
(e) 若 P?Q?R，则 Q?R?P,P?P?Q，且
P?Q?R?F。
与非、或非和异或的性质
Guoyongfang.2006@yahoo.com.cn
以上所有性质，用真值表或命题定律都是不难证明的。
至此，已有了 9个联结词，是否还需要扩充呢？
事实上，两上命题变无 P和 Q，与 9个联结词一共可构成 类命题公式，如下表示之：
Guoyongfang.2006@yahoo.com.cn
P Q F T P Q P Q P? Q P? Q P? Q P? Q
0 0
0 1
1 0
1 1
0
0
0
0
1
1
1
1
0
0
1
1
0
1
0
1
1
1
0
0
1
0
1
0
0
0
0
1
1
1
1
0
0
1
1
1
1
0
0
0
所用的联结词
序号 1 2 3 4 5 6 7 8 9 10
续 表
P Q P? Q P? Q P? Q P? Q Q? P Q? P
0 0
0 1
1 0
1 1
1
1
0
1
0
0
1
0
1
0
0
1
0
1
1
0
1
0
1
1
0
1
0
0
所用的联结词
序号 11 12 13 14 15 16
Guoyongfang.2006@yahoo.com.cn
从列表可知,除命题常元 F,T及命题变元本身外,命题联结词一共有 9个就够了 。
Guoyongfang.2006@yahoo.com.cn
联结词功能完全组已知有 9个联结词就够用了,能不能少呢？ 若能少,表明有些联结词的逻辑功能可由其他联结词替代 。 事实上,也确实如此,因为有下列等价式：
P?Q(P?Q)
P?Q(P?Q)
P?Q(P?Q)
P?Q(P?Q)
可见,扩充的 4个联结词?,?,?和?能由原有 5
个联结词分别替代之 。
Guoyongfang.2006@yahoo.com.cn
又由命题定律：
P?Q?(?P?Q)?(?Q?P)
P?QP?Q
P?Q(?PQ)
P?Q(?PQ)
可知，原有 5个联结词?,?,?,?和?又能由联结词组 {?,?}或 {?,?}取代。那么，究竟最少用几个联结词？就是说，用最少的几个联结词就能等价表示所有的命题公式。或者说，用最少的几个联结词就能替代所有联结词的功能。
这便是所要定义的联结词功能完全组。
Guoyongfang.2006@yahoo.com.cn
最小联结词组：
｛ ┐,∨ ｝
｛ ┐,∧ ｝
｛ ↑ ｝
｛ ↓ ｝
Guoyongfang.2006@yahoo.com.cn
一、对偶给定的命题公式中，将联结词 ∨ 换成
∧,将 ∧ 换成 ∨,若有特殊变元 F和
T亦相互取代，所得公式 A*称为 A的对偶式。
显然,A也为 A*的对偶式。
1－ 7 对偶与范式
Guoyongfang.2006@yahoo.com.cn
对偶与范式例,写出下列表达式的对偶式
1) (P ∨ Q) ∧ R
2) ┐ (P ∨ Q) ∧ (P ∨ ┐ (Q ∧ S))
解,这些表达式的对偶式是
1) (P ∧ Q) ∨ R
2) ┐ (P ∧ Q) ∨ (P ∧ ┐ (Q ∨ S))
Guoyongfang.2006@yahoo.com.cn
定理 设 A和 A*是对偶式,P1,P2,?,Pn是出现在 A和 A*中的原子变元，则
┐ A（ P1,P2,?,Pn ）
A*（ ┐ P1,┐ P2,?,┐ Pn）
A（ ┐ P1,┐ P2,?,┐ Pn）
┐ A*（ P1,P2,?,Pn ）
对偶与范式
Guoyongfang.2006@yahoo.com.cn
对偶与范式定理 设 P1,P2,?,Pn是出现在公式 A和 B中的所有原子变元，如果 A B，则 A* B*
Guoyongfang.2006@yahoo.com.cn
二、范式由于同一个命题公式可以有不同的 表达形式,
而不同的表达形式可以显示很不同的 特征 。
某种特定类型的表达可以显示出从某一角度考虑极为重要的 性质 。但上述的不同表达形式却对我们研究命题演算带来了一定的困难。
因此，从理论上讲，有必要对命题公式的标准形式问题进行一个深入的研究，使公式达到规范化。为此，引入范式这一概念，范式给各种千变万化的公式提供了一个统一的表达形式，同时，范式的研究对命题演算的发展起了极其重要的作用。
对偶与范式
Guoyongfang.2006@yahoo.com.cn
定义 一个命题公式称为合取范式，当且仅当它具有形式：
A1∧A 2∧? ∧A n (n≥1)
其中 A1,A2,?,An都是由命题变元或其否定所组成的析取式。
定义 一个命题公式称为 析 取范式，当且仅当它具有形式：
A1∨A 2∨? ∨A n (n≥1)
其中 A1,A2,?,An都是由命题变元或其否定所组成的 合 取式。
对偶与范式
Guoyongfang.2006@yahoo.com.cn
对偶与范式求公式,(P∨┐ Q)→ R的析取范式和合取范式。
解,(P∨┐Q)→R
＝ ┐ (P∨┐Q)∨R
＝ (┐P∧Q)∨R─── 析取范式
(P∨┐Q)→R
＝ (┐P∧Q)∨R
＝ (┐P∨R)∧(Q∨R)─── 合取范式
Guoyongfang.2006@yahoo.com.cn
任何一个命题公式，求它的合取范式合析取范式，可以通过下面三个步骤进行：
1）将公式中的联结词化归成 ∧,∨ 及 ┐ 。
2）利用德 · 摩根律将否定符号 ┐ 直接移到各个命题变元之前。
3）利用分配律、结合律归约为合取范式或析取范式。
对偶与范式
Guoyongfang.2006@yahoo.com.cn
定义 n个命题变元的合取式，称作 布尔合取或小项,其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。
性质,
1）每一个小项当其真值指派与编码相同时，
其真值为 T，在其余 2n－ 1种指派情况下均为 F。
2）任意两个不同小项的合取式永假。
3）全体小项的析取式永真。
对偶与范式
Guoyongfang.2006@yahoo.com.cn
定义 对于给定的命题公式，如果有一个等价公式，它仅由小项的析取所组成，则该等价式称作原式的 主析取范式 。
定义 在真值表中，一个公式的真值为 T的指派所对应的小项的析取，即为此公式的主析取范式 。
对偶与范式
Guoyongfang.2006@yahoo.com.cn
求一个命题公式的主析取范式的方法：
1）公式的真值表
2）基本等价公式推出步骤：
1）化归为析取范式
2）除去析取范式中所有永假的析取项。
3）将析取式中重复出现的合取项合相同的变元合并。
4）对合取项补入没有出现的命题变元，即添加
（ P ∨┐ P）式，然后，应用分配律展开公式。
对偶与范式
Guoyongfang.2006@yahoo.com.cn
定义 n个命题变元的析取式，称作布尔析取或大项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。
性质：
1）每一个大项当其真值指派与编码相同时，
其真值为 F，在其余 2n－ 1种指派情况下均为 T。
2）任意两个不同大项的析取式永永真。
3）全体大项的合取式永假。
对偶与范式
Guoyongfang.2006@yahoo.com.cn
定义 对于给定的命题公式，如果有一个等价公式，它仅由大项的合取所组成，则该等价式称作原式的 主合取范式 。
定义 在真值表中，一个公式的真值为 F的指派所对应的大项的合取，即为此公式的 主合取范式 。
对偶与范式
Guoyongfang.2006@yahoo.com.cn
求一个命题公式的主合取范式的方法：
1）公式的真值表
2）基本等价公式推出步骤：
1）化归为合取范式
2）除去合取范式中所有永真的合取项。
3）合并相同的析取项和相同的变元。
4）对析取项补入没有出现的命题变元，即添加
（ P ∨┐ P）式，然后，应用分配律展开公式。
对偶与范式
Guoyongfang.2006@yahoo.com.cn
对偶与范式
P Q R 极小项 极大项
0 0 0 m0=┐P∧┐Q∧┐R M0=P∨Q∨R
0 0 1 m1=┐P∧┐Q∧R M1=P∨Q∨┐R
0 1 0 m2=┐P∧Q∧┐R M2=P∨┐Q∨R
0 1 1 m3=┐P∧Q∧R M3=P∨┐Q∨┐R
1 0 0 m4=P∧┐Q∧┐R M4=┐P∨Q∨R
1 0 1 m5=P∧┐Q∧R M5=┐P∨Q∨┐R
1 1 0 m6=P∧Q∧┐R M6=┐P∨┐Q∨R
1 1 1 m7=P∧Q∧R M7=┐P∨┐Q∨┐
R
Guoyongfang.2006@yahoo.com.cn
对偶与范式含有 n个命题变元的极小项 mi和极大项
Mi，可以看作含有 n个命题变元的公式，
因此共有 2n个不同的解释。
这 2n个不同的解释中，有且仅有一个解释使得 mi为 1，即对 mi中以变元形式出现的变元指派为 1，以变元的否定形式出现的变元指派为 0；
2n个不同的解释中，有且仅有一个解释使得 Mi为 0，即对 Mi中以变元形式出现的变元指派为 0，以变元的否定形式出现的变元指派为 1。
Guoyongfang.2006@yahoo.com.cn
mi=┐ Mi； Mi=┐ mi；
i=0,1,2,…,2n-1
Mi∨ Mj=T； mi∧ mj=F；
i≠j； i,j? {0,1,2,…,2n-1}；1m i
12
0i
n
。0M i
12
0i
n
对偶与范式
Guoyongfang.2006@yahoo.com.cn
例 2.1.4.3 设
G=(P→ Q)∧
R，求出它的主析取范式和主合取范式。
P Q R P→Q (P→Q)∧R
0 0 0 1 0
0 0 1 1 1
0 1 0 1 0
0 1 1 1 1
1 0 0 0 0
1 0 1 0 0
1 1 0 1 0
1 1 1 1 1
解,首先列出其真值表如下：
对偶与范式
Guoyongfang.2006@yahoo.com.cn
(1).求主析取范式
(a).从真值表知，该公式 G恰有三个解释使其公式取值为,真,。为此，选出已给公式取值为,1”所在行所对应的变元取值如下：
2,0 0 1 4,0 1 1 8,1 1 1
(b).将上面选出的各行变元取值,还原,成相应的原子命题符号，值为,1”者,还原,成原变量，值为,0”者,还原,成原变量的否定，并构成相应的极小项。则有：
2.┐ P∧┐ Q∧ R该极小项恰有唯一的一组解释 {0,0,1}使其取值为,真,。
4.┐ P∧ Q∧ R该极小项恰有唯一的一组解释 {0,1,1}使其取值为,真,。
8.P∧ Q∧ R该极小项恰有唯一的一组解释 {1,1,1}使其取值为,真,。
对偶与范式
Guoyongfang.2006@yahoo.com.cn
(c).则上述极小项的析取为对应的主析取范式。
G＝ (P→ Q)∧ R
＝ (┐ P∧┐ Q∧ R)∨ (┐ P∧ Q∧ R)∨ (P∧ Q∧ R)
(2).求主合取范式
(a).从真值表知，该公式 G恰有五个解释使其公式取值为,假,。
为此，选出已给公式取值为,0“所在行所对应的变元之值如下：
1.0 0 0 3.0 1 0 5.1 0 0 6.1 0 1 7.1 1 0
(b).将上面选出的各行变元之值,还原,成相应的原子命题符号，值为,1”者,还原,成原变量的否定，值为,0”者,还原,
成原变量，并构成相应的极大项。则有
1.P∨ Q∨ R该极大项恰有唯一的一组解释 {0,0,0}使其取值为,假,。
对偶与范式
Guoyongfang.2006@yahoo.com.cn
3.P∨┐ Q∨ R该极大项恰有唯一的一组解释 {0,1,0}使其取值为,假,。
5.┐ P∨ Q∨ R该极小项恰有唯一的一组解释 {1,0,0}使其取值为,假,。
6.┐ P∨ Q∨┐ R该极大项恰有唯一的一组解释 {1,0,1}使其取值为,假,。
7.┐ P∨┐ Q∨ R该极大项恰有唯一的一组解释 {1,1,0}使其取值为,假,。
(c).则上述极大项的合取为对应的主合取范式。
G=(P→ Q)∧ R
＝ (P∨ Q∨ R)∧ (P∨┐ Q∨ R)∧ (┐ P∨ Q∨ R)
∧ (┐ P∨ Q∨┐ R)∧ (┐ P∨┐ Q∨ R)。
对偶与范式
Guoyongfang.2006@yahoo.com.cn
例 2.1.4.4 利用公式的等价求 G＝ (P→ Q)∧ R的主析取范式和主合取范式。
解,G＝ (P→ Q)∧ R＝ (┐ P∨ Q)∧ R
＝ (┐ P∨ Q∨ (R∧┐ R))∧
((┐ P∧ 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)
－－－－－主合取范式对偶与范式
Guoyongfang.2006@yahoo.com.cn
G＝ (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)
＝ (┐P∧┐Q∧R)∨(┐P∧Q∧R)∨(P∧Q∧R)
—— 主析取范式对偶与范式
Guoyongfang.2006@yahoo.com.cn
若 为 G的主析取范式,则为 ┐ G的主析取范式,其中,
mji(i=1,2,…,2n-k)是 mi(i=0,1,…,2n-1)中去掉 mli(i=1,2,…,k)后剩下的极小项,则,
m j
i
n k2
1i
G?
m l ik
1i
G?
i
n
i
n
i
n
j
k2
1i
j
k2
1i
j
k2
1i
Mm)m(GG
为 G的主合取范式。
对偶与范式
Guoyongfang.2006@yahoo.com.cn
若 为 G的主 合 取范式,则为 ┐ G的主 合 取范式,其中,
Mji(i=1,2,…,2n-k)是 Mi(i=0,1,…,2n-1)中去掉 Mli(i=1,2,…,k)后剩下的极 大 项,则,
为 G的主析合取范式。
M
1
G l
i
k
i
M12
1
G j
i
n
i
i
n
i
n
i
n
j
k2
1i
j
k2
1i
j
k2
1i
mM)M(GG
对偶与范式
Guoyongfang.2006@yahoo.com.cn
设 G＝ (P∧ Q)∨ (┐ P∧ R)∨ (Q∧ R)，求其对应的主析取范式和主合取范式。
解,G＝ (P∧Q)∨(┐P∧R)∨(Q∧R)
＝ (P∧Q∧(┐R∨R))∨
(┐P∧(┐Q∨Q)∧R)∨((┐P∨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)
＝ m1∨m 3∨m 6∨m 7 ----主析取范式对偶与范式
Guoyongfang.2006@yahoo.com.cn
设 G＝ (P∧ Q)∨ (┐ P∧ R)∨ (Q∧ R)，求其对应的主析取范式和主合取范式。
解,G＝ (P∧Q)∨(┐P∧R)∨(Q∧R)
＝ (P∧Q∧(┐R∨R))∨
(┐P∧(┐Q∨Q)∧R)∨((┐P∨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)
＝ m1∨m 3∨m 6∨m 7 ----主析取范式对偶与范式
Guoyongfang.2006@yahoo.com.cn
任何命题公式都存在唯一一个与之等价的 主析取范式 和主合取范式 ；
命题公式是永真公式当且仅当 它的主析取范式包含所有的极小项，此时无主合取范式或者说主合取范式为,空,；
命题公式是永假公式 当且仅当 它的主合取范式包含所有的极大项，此时无主析取范式或者说主析取范式为,空,；
两个命题公式是相等的 当且仅当 它们的主析取范式相等 (即含有相同的极小项 )和主合取范式相等 (即含有相同的极大项 )。
对偶与范式
Guoyongfang.2006@yahoo.com.cn
1-8 推理理论命题演算的一个主要任务在于提供一种正确的思维规律，即 推理规则,应用此规则从一些前提中推导出一个结论来，这种推导过程称为 演绎 或 形式证明 。 定义 1-8.1 设 A和 C是两个命题公式,当且仅当 A → C为一重言式,即 A?C,称 C是 A
的 有效 结论 。 或 C可由 A逻辑地推出 。
Guoyongfang.2006@yahoo.com.cn
推理理论上述定义可推广到 n个前提的情况 。 设 H1，
H2,…,Hn,C是命题公式,当且仅当
H1∧ H2∧ … ∧ Hn?C
称为 C是一组前提 H1,H2,…,Hn,的有效结论 。
Guoyongfang.2006@yahoo.com.cn
推理理论推理的方法,
1,真值表法
2,直接证法
3,间接证法
Guoyongfang.2006@yahoo.com.cn
P ∧ Q? P P ∧ Q? Q
P? P ∨ Q ┐ P? P → Q
P,（ P → Q ）? Q
┐ Q,（ P → Q ）? ┐ P
┐ P,P ∨ Q? Q
(P→ Q) ∧ （ Q→ R）?P→ R
Guoyongfang.2006@yahoo.com.cn
推理理论一、真值表法,设 P1,P2,…,Pn是出现在前提
H1,H2,…,Hn和结论 C中的一切命题变元,假定对
P1,P2,…,Pn作 了全部的真值指派，这样就能对应地确定 H1,H2,…,Hn和 C的 所有 真值,列出这个真值表，
即可看出公式是否成立。 判断方法如下：
1.对所有 H1,H2,…,Hn 都具有真值 T的行 (表示前提为真的行 ),如果在每一个这样的行中,C 也具有真值 T,则 C 是
H1,H2,…,Hn 的 结论 。
Guoyongfang.2006@yahoo.com.cn
推理理论
2,对所有 C具有真值为 F的行 (表示结论为假的行 ),如果在每一个这样的行中，
H1,H2,…,Hn 中至少有一个公式的真值为
F(前提也为假 )，则 H是 H1,H2,…,Hn 的 结论,
Guoyongfang.2006@yahoo.com.cn
推理理论判断下列 H是否是前提 G1,G2的逻辑结果
(1) H,Q； G1,P； G2,P→Q ；
(2) H,┐ P； G1,P→Q ； G2,┐ Q；
(3) H,Q； G1,┐ P； G2,P→Q 。
Guoyongfang.2006@yahoo.com.cn
推理理论解,建立真值表如下：
P Q G1 G2 H
0 0 0 1 0
0 1 0 1 1
1 0 1 0 0
1 1 1 1 1
(1)
P Q G1 G2 H
0 0 1 1 1
0 1 1 0 1
1 0 0 1 0
1 1 1 0 0
(2)
P Q G1 G2 H
0 0 1 1 0
0 1 1 1 0
1 0 0 0 0
1 1 0 1 1
(3)
Guoyongfang.2006@yahoo.com.cn
二、直接证法,由一组前提，利用一些公认的推理规则，根据已知的等价或蕴含公式，推演得到有效的结论。
规则 P(前提引入规则 )：前提在推导的过程中可以随时引入。
规则 T(逻辑结果引用规则 )：在推导的过程中,如果有一个或多个公式蕴含着公式 S，则 公式 S可以 引入推导之中 。
推理理论
Guoyongfang.2006@yahoo.com.cn
证明,符号化上述语句,Г ={P∨Q→R,R→S,┐S},G=┐Q 。证明
Г?G。
如果马会飞或羊吃草，则母鸡就会是飞鸟；如果母鸡是飞鸟，那么烤熟的鸭子还会跑；烤熟的鸭子不会跑。所以羊不吃草。
推理理论
Guoyongfang.2006@yahoo.com.cn
证明,符号化上述语句,Г ={P∨Q→R,R→S,┐S},G=┐Q 。证明
Г?G。
证：⑴ ┐ S P
⑵ R→S P
⑶ ┐ R T,⑴,⑵,I
⑷ P∨Q→R P
⑸ ┐ (P∨Q) T,⑶,⑷,I
⑹ ┐ P∧┐Q T,⑸,E
⑺ ┐ Q T,⑹,I
推理理论
Guoyongfang.2006@yahoo.com.cn
推理理论证：
⑴ P∨Q P
⑵ ┐ P→Q T,(1),E
⑶ Q→S P
设前提 Г ={P∨Q,P→R,Q→S},公式 G=S∨R 。 证明
Г?G。
Guoyongfang.2006@yahoo.com.cn
推理理论
⑷ ┐ P→S T,⑵,⑶,I
⑸ ┐ S→P T,⑷,E
⑹ P→R P
⑺ ┐ S→R T,⑸,⑹,I
⑻ S∨R T,⑺,E
Guoyongfang.2006@yahoo.com.cn
推理理论三、间接证法定义 1-8.2 假设公式 H1,H2,…,Hn是 中的 命题变元 为 P1,P2,…,Pn,对于 P1,P2,…,Pn 的一些真值指派，如果能 使 H1∧H 2∧ … ∧H n的真值为 T，则称公式 H1,H2,…,Hn 是 相容 的 。 如果 对 P1,P2,…,Pn 的每一组真值指派使得
H1∧H 2∧ … ∧H n 的真 值为 F,则称公式
H1,H2,…,Hn 是 不相容 的
Guoyongfang.2006@yahoo.com.cn
推理理论
1,间接证法一,设有一组前提
H1,H2,…,Hn,要推出结论 C,即证
H1∧H 2∧ … ∧H n? C,记作 S? C,即
┐ C→┐S 为永真,或 C ∨ ┐S 为永真,
故 ┐ C∧S 为永假 。 因此要证明
H1∧H 2∧ … ∧H n? C,只 要 证 明
H1∧H 2∧ … ∧H n 与 ┐ C 不相容 的 。
Guoyongfang.2006@yahoo.com.cn
推理理论证,⑴ ┐(┐ P) P(附加前提 )
⑵ P T,⑴,E
⑶ P→Q P
⑷ Q T,⑵,⑶,I
⑸ ┐ (Q∨R) P
⑹ ┐ Q∧┐R T,⑸,E
⑺ ┐ Q T,⑹,I
⑻ Q∧┐Q T,⑷,⑺,I
设 Г ={P→Q,┐(Q∨R)},G=┐P 。 证明,Г?G。
Guoyongfang.2006@yahoo.com.cn
推理理论证,⑴ ┐(┐( P∧Q)) P(附加前提 )
⑵ P∧Q T,⑴,E
⑶ P T,⑵,I
⑷ ┐P∧┐Q P
┐ P T,⑷,I
⑹ P∧┐P T,⑶,⑸,I
设 Г ={┐P∧┐Q},G=┐(P∧Q) 。证明,Г?G。
Guoyongfang.2006@yahoo.com.cn
推理理论
2,间接证法二,若要 证 H1∧H 2∧ … ∧H n?
（ R→C ） 。 H1,H2,…,Hn,为 S,即证 S?（ R→C) 或 S?
（ ┐ R∨ C ）,故 S→ (┐ R∨ C) 为 永 真 式 。 因为
S→ (┐ R∨ C) ┐S ∨ (┐ R∨ C) （ ┐ S∨ ┐ R ） ∨ C
┐(S∧ R)∨ C (S∧ R)→C,所以若将 R作附加前提,如有 (S∧ R)? C,即证得 S?（ R→C) 。 由 (S∧ R)
C,证得 S?（ R→C) 称为 CP规则 。
Guoyongfang.2006@yahoo.com.cn
推理理论
⑴ ┐ S P(附加前提 )
⑵ Q→S P
⑶ ┐ Q T,⑴,⑵,I
设前提 Г ={P∨Q,P→R,Q→S},公式 G=S∨R 。 证明
Г?G。
利用规则 CP将 ┐ S作为附加前提引进。
Guoyongfang.2006@yahoo.com.cn
推理理论
⑷ P∨Q P
⑸ P T,⑶,⑷,I
⑹ P→R P
⑺ R T,⑸,⑹,I
⑻ S∨R CP,⑴,⑺,E
Guoyongfang.2006@yahoo.com.cn
推理理论证,⑴ R P(附加前提 )
⑵ ┐ R∨P P
⑶ P T,⑴,⑵,I
设 Г ={P→(Q→S),┐R∨P,Q},G=R→S 。证明：
Г?G。
Guoyongfang.2006@yahoo.com.cn
推理理论
⑷ P→(Q→S) P
⑸ Q→S T,⑶,⑷,I
⑹ Q P
⑺ S T,⑸,⑹,I
⑻ R→S CP,⑴,⑺
Guoyongfang.2006@yahoo.com.cn
第一章作业
P23 1-5习题（ 2） (3)
P27 1-7习题 (4).a.e（ 7）（ 8）
P47 1-8习题 (1).b (2).c (3).d
Discrete Mathematics
郭永芳
guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn
离散数学是计算机出现以后迅速发展起来的一门数学分支。计算机科学就是算法的科学，而计算机所处理的对象是离散的数据，所以离散对象的处理就成了计算机科学的核心，而研究离散对象的科学恰恰就是离散数学。
离散数学是什么？
Guoyongfang.2006@yahoo.com.cn
离散数学是什么？
离散数学是现代数学的一个重要分支，
是计算机类专业的重要课程。它以 研究离散量的结构及其相互间的关系 为主要目标，其研究对象一般是有限个或可数个元素，因此离散数学可以充分描述计算机学科离散性的特点。
Guoyongfang.2006@yahoo.com.cn
关于离散数学的一些应用一个邮递员从邮局出发，要走完他所管辖的街道，他应该怎样选择什么样的路径，这就是著名的 "中国邮递员问题
"，由中国离散数学家管梅谷教授提出，
著名离散数学家 J,Edmonds和他的合作者给出了一个解答。
Guoyongfang.2006@yahoo.com.cn
一个班级的学生共计选修 A,B,C、
D,E,F六门课程，其中一部分人同时选修 D,C,A，一部分人同时选修 B,C、
F，一部分人同时选修 B,E，还有一部分人同时选修 A,B，期终考试要求每天考一门课，六天内考完，为了减轻学生负担，要求每人都不会连续参加考试，
试设计一个考试日程表。
关于离散数学的一些应用
Guoyongfang.2006@yahoo.com.cn
一个人带着一只狼、一只羊和一捆草要渡河，由于船太小，人做摆渡者一次只能运送一个,乘客,,很显然，如果人不在，狼要吃羊，羊要吃草，问人怎样才能把它们平安地渡过河去？
关于离散数学的一些应用
Guoyongfang.2006@yahoo.com.cn
网络计划技术我们还会遇到更复杂的调度和安排问题。例如，在生产原子弹的曼哈顿计划中，涉及到很多工序，许多人员的安排，很多元件的生产，怎样安排各种人员的工作，以及各种工序间的衔接，从而使整个工期的时间尽可能短？这些都是离散数学典型例子。
关于离散数学的一些应用
Guoyongfang.2006@yahoo.com.cn
一个通讯网络怎样布局最节省？美国的贝尔实验室和 IBM公司都有世界一流的离散数学家在研究这个问题，这个问题直接关系到巨大的经济利益。
我们知道，用形状相同的方型砖块可以把一个地面铺满（不考虑边缘的情况），但是如果用不同形状，而又非方型的砖块来铺一个地面，能否铺满呢？
这不仅是一个与实际相关的问题，也涉及到很深的离散数学问题。
关于离散数学的一些应用
Guoyongfang.2006@yahoo.com.cn
航空调度和航班的设定也是离散数学的问题。怎样确定各个航班以满足不同旅客转机的需要，同时也使得每个机场的航班起落分布合理。此外，在一些航班有延误等特殊情况下，
怎样作最合理的调整，这些都是离散数学的问题。
对于城市的交通管理，交通规划，哪些地方可能是阻塞要地，哪些地方应该设单行道，
立交桥建在哪里最合适，红绿灯怎样设定最合理，如此等等，全是离散数学的问题。
关于离散数学的一些应用
Guoyongfang.2006@yahoo.com.cn
离散数学中有一个著名问题：是否存在稳定婚姻的问题。假如能找到两对夫妇（如张
（男） --李（女）和赵（男） --王（女）），
如果张（男）更喜欢王（女），而王（女）也更喜欢张（男），那么这样就可能有潜在的不稳定性。离散数学的方法可以找到一种婚姻的安排方法，使得没有上述的不稳定情况出现
（当然这只是理论上的结论）。这种离散数学的方法却有一个实际的用途：美国的医院在确定录取住院医生时，他们将考虑申请者的志愿的先后次序，同时也给申请排序。按这样的次序考虑出的总的方案将没有医院和申请者两者同时后悔的情况。实际上，高考学生的最后录取方案也可以用这种方法。
关于离散数学的一些应用
Guoyongfang.2006@yahoo.com.cn
总之，离散数学无处不在，它的主要应用就是在各种复杂关系中找出最优的方案。所以离散数学完全可以看成是一门量化的关系学,一门量化了的运筹学,一门量化了的管理学 。
关于离散数学的一些应用
Guoyongfang.2006@yahoo.com.cn
离散数学是理论性较强的学科，学习离散数学的关键是 对离散数学（集合论、数理逻辑和图论）有关基本概念的准确掌握，对基本原理及基本运算的运用，并要多做练习 。
如何学习离散数学
Guoyongfang.2006@yahoo.com.cn
离散数学课程设置计算机系核心课程信息类专业必修课程其它类专业的重要选修课程
Guoyongfang.2006@yahoo.com.cn
离散数学相关课程数字逻辑、计算机图像处理、数据结构、编译技术、算法分析与设计、人工智能、数据库,……
Guoyongfang.2006@yahoo.com.cn
离散数学的内容安排第一篇：数理逻辑命题逻辑、谓词逻辑第二篇：集合论集合与关系、寒暑第三篇：代数系统代数结构第四篇：图论图论
Guoyongfang.2006@yahoo.com.cn
离散数学课程安排课堂讲授,64学时上机实验,8学时考试课期末考试,70%
平时成绩：出勤 +作业 +实验 =30%
Guoyongfang.2006@yahoo.com.cn
第一篇 数理逻辑数理逻辑是用数学的方法研究思维规律的一门学科。由于它使用了一套符号，简洁的表达出各种推理的逻辑关系，
因此数理逻辑一般又称为符号逻辑。
数理逻辑和计算机的发展有着密切的联系，它为机器证明、自动程序设计、
计算机辅助设计等计算机应用和理论研究提供必要的理论基础。
Guoyongfang.2006@yahoo.com.cn
为什么研究数理逻辑？
数理逻辑,用数学的方法来研究推理规律的科学 。
程序＝算法＋数据算法＝逻辑＋控制
Guoyongfang.2006@yahoo.com.cn
数理逻辑的内容,
古典数理逻辑：
命题逻辑、谓词演算现代数理逻辑：
公理化集合论、递归论、模型论、证明论
Guoyongfang.2006@yahoo.com.cn
命题逻辑 (Proposition Logic)
研究以命题为基本单位构成的前提和结论之间的可推导关系。
Guoyongfang.2006@yahoo.com.cn
什么是命题？
在数理逻辑中，为了表达概念，陈述理论和规则，
常常需要应用语言进行描述，但是日常使用的自然语言，往往叙述时不够确切，也容易产生二义性，因此就需要引入一种目标语言，这种目标语言和一些公式符号，就形成了数理逻辑的形式符号体系。
所谓目标语言就是表达判断的一些语言的汇集，
而判断就是对事物有肯定或否定的一种思维形式，因此能表达判断的语言是陈述句，它称作命题。
Guoyongfang.2006@yahoo.com.cn
具有 确切真值 的 陈述句 称为 命题,该命题可以取一个,值,,称为 真值 。
,真,和,假,两种，分别用,Ｔ,(或,1”)和,Ｆ,(或,0”)
表示。
什么是命题？
Guoyongfang.2006@yahoo.com.cn
命题及其表示方法命题的语句形式陈述句非命题语句：
疑问句命令句（祈使句）
感叹句
Guoyongfang.2006@yahoo.com.cn
例题：
加拿大是一个国家。
北京是中国的首都。
1＋ 101＝ 110。
３＋２ ≥ 10。
我喜欢踢足球。
Guoyongfang.2006@yahoo.com.cn
例题：
全体立正！
这朵花真漂亮！
你想喝水吗？
X=0
我正在说的这句话是谎话 。
Guoyongfang.2006@yahoo.com.cn
悖论罗素悖论：
城里所有不自己刮脸的男人都由我给他们刮脸，我也只给这些人刮脸。
悖论：悖论是自相矛盾的命题。即如果承认这个命题成立，就可推出它的否定命题成立；反之，如果承认这个命题的否定命题成立，又可以推出这个命题成立。
Guoyongfang.2006@yahoo.com.cn
悖论另一个悖论的例子是：某国有一条法律，每一个旅游者都要回答卫兵一个问题：你来这里做什么？如果旅游者回答对了就放行。
如果回答错了，他就要被绞死。一天，有个旅游者回答：我来这里是要被绞死的。
卫兵听了后则慌了神，因为如果他们不把这个人绞死，这个旅游者就回答错了，就得受绞刑。可是，如果卫兵绞死他，旅游者就说对了，那就不应该绞死他。
Guoyongfang.2006@yahoo.com.cn
命题及其表示命题的符号表示：
大写英文字母,P,Q,R、
数字,[12],[13]
命题真值（ Truth Values）的表示：
真,1,T
假,0,F
命题标识符：表示命题的符号命题常量：命题标识符表示确定的命题命题变量：命题标识符只表示任意命题的位置标志,不是命题指派：对命题变元用一个特定的命题取代
Guoyongfang.2006@yahoo.com.cn
原子命题和复合命题原子命题：不能分解为更简单的陈述语句的命题。
复合命题,可以 分解 为更为简单命题的命题。由联结词、标点符号和原子命题复合构成的命题。
而且这些简单命题之间是通过如,或者,,
,并且,,,不,,,如果,..则,..”,,当且仅当,等这样的关联词和标点符号复合而构成一个复合命题。
Guoyongfang.2006@yahoo.com.cn
原子命题和复合命题
今天天气很冷。
今天天气很冷并且刮风。
今天天气很冷并且刮风，但室内暖和。
Guoyongfang.2006@yahoo.com.cn
1.2 联结词（否定）
定义,设 P为一命题,P的否定是一个新的命题，记作?P。 相当于自然语言中的
,非,,,不,等。
例如：
P：天津是直辖市。
P,天津不是直辖市。
P：雪是黑的。
P,雪不是黑的。
Guoyongfang.2006@yahoo.com.cn
否定 联结词特点：若 P为 T，则?P为 F；若 P为 F，则?P为 T。
否定 是一个一元运算
P ┐ P
F T
T F
Guoyongfang.2006@yahoo.com.cn
1.2 联结词（合取）
定义：两个命题 P和 Q的合取相当于一个复合命题，记作 P ∧ Q。 ∧ 相当于自然语言中的“与”,但并不完全相同。
例如：
P：今天下雨。
Ｑ,明天下雨。
P ∧ Q：今天和明天都下雨。
Guoyongfang.2006@yahoo.com.cn
合取 联结词特点：Ｐ和Ｑ同时为Ｔ时,P ∧ Q为Ｔ。
合取 是二元运算
P Q P∧Q
F F F
F T F
T F F
T T T
Guoyongfang.2006@yahoo.com.cn
1.2 联结词（析取）
定义：两个命题 P和 Q的合取相当于一个复合命题，记作 P ∨ Q。 ∨ 相当于自然语言中的“可兼或”。
例如：
P：今天下雨。
Ｑ,明天下雨。
P ∨ Q：今天或明天下雨。
Guoyongfang.2006@yahoo.com.cn
1.2 联结词（析取）
排斥或例如：我今天上午去学校或者在家休息。
可兼或例如：他可能是１００米冠军或４００米冠军。
其它：
例如：他中午吃了两个或三个包子。
Guoyongfang.2006@yahoo.com.cn
1.2 联结词（析取）
特点：当且仅当Ｐ、Ｑ同时为Ｆ时,P ∨ Q记作Ｆ，否则 P ∨ Q记作Ｔ。
析取 是二元运算
P Q P∨ Q
F F F
F T T
T F T
T T T
Guoyongfang.2006@yahoo.com.cn
1.2 联结词（条件）
定义：给定两个命题Ｐ和Ｑ，其条件命题是一个复合命题，记作 P→ Q,读作 如果Ｐ，
那么Ｑ 或者读作 若Ｐ则Ｑ。
例如：
P：今天下雨。
Ｑ,明天下雨。
P→ Q,如果今天下午，那么明天下雨。
Guoyongfang.2006@yahoo.com.cn
1.2 联结词（条件）
在自然语言中,,如果．．．,与,那么．．．,之间常常是有因果联系的，否则就没有意义。但是对于条件命题 P→ Q而言，
只要Ｐ和Ｑ能够分别确定真值,P→Q 即成为命题 。
在自然语言中，若前提为假，则不论结论是真或假，这个语句的意义往往无法判断 。 在条件命题中，规定为“善意的推定,,即前提为Ｆ时，条件命题的真值都取为Ｔ。
Guoyongfang.2006@yahoo.com.cn
1.2 联结词（条件）
特点,P→Q 为假当且仅当 P为真 Q为假二元运算
P Q P→ Q
F F T
F T T
T F F
T T T
Guoyongfang.2006@yahoo.com.cn
1.2 联结词（双条件）
定义：给定两个命题Ｐ和Ｑ，其复合命题 P
Q称作双条件命题,读作Ｐ当且仅当
Ｑ。
例如：
P：今天下雨。
Ｑ,明天下雨。
P? Q,今天下雨，当且仅当明天下雨。
Guoyongfang.2006@yahoo.com.cn
1.2 联结词（双条件）
特点,P?Q为真当且仅当 P,Q同为真假二元运算，可以不顾因果关系，而只根据联结词定义确定真值。
P Q P? Q
F F T
F T F
T F F
T T T
Guoyongfang.2006@yahoo.com.cn
联结词小结联接词 记号 记法 真值结果否定 ┐ ┐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同为真假
Guoyongfang.2006@yahoo.com.cn
联结词
⑴ 用复合命题表示如下图所示的开关电路图 1 图 2 图 3
P Q P
P
Q
A∧B A∨B A
设,A：开关Ｐ闭合； B：开关Ｑ闭合。
Guoyongfang.2006@yahoo.com.cn
联结词
⑵．用复合命题表示如下图所示的逻辑电路。
P
Q
P
Q
P
QP?
QP?
P?
Guoyongfang.2006@yahoo.com.cn
联结词
伦敦不是一个城市。
今天下雨或者刮风。
3是奇数并且 3是素数。
如果河水泛滥，那么庄稼将被毁坏。
ａ ＋ｂ＝ａ当且仅当ｂ＝ 0。
符号化下述命题：
Guoyongfang.2006@yahoo.com.cn
联结词
设 P：伦敦是一个城市。
则命题可表示为 ┐ P。
设 P：今天下雨。 Q：今天刮风。
则命题可表示为 P∨ Q。
设 P,3是奇数。 Q,3是素数。
则命题可表示为 P∧ Q。
设 P：河水泛滥。 Q：庄稼被毁坏。
则命题可表示为 P→ Q。
设 P：ａ＋ｂ＝ａ。 Q：ｂ＝ F。
则命题可表示为 P?Q。
Guoyongfang.2006@yahoo.com.cn
1-3 命题公式与翻译命题公式：
设 P和 Q是任意两个命题，则 ┐ P,P∨ Q，
P∧ Q,P?（ Q ∧ P）都是复合命题。
若 P和 Q是命题变元，则上述各式均称作命题公式。 P和 Q分别称作命题公式的分量。
注意：命题公式是没有真假的，仅当在一个公式中命题变元用确定的命题带入时，才得到一个命题。这个命题的真值，依赖于代换变元的那些命题的真值。
Guoyongfang.2006@yahoo.com.cn
命题演算的合式公式命题演算的合式公式,
1.命题变元本身是一个合式公式；
2.如 P是公式，则 (┐P) 也是合式公式；
3.如 P,Q是公式，则 (P∧Q),(P∨Q),(P→Q),
(P?Q)也是合式公式 ；
4.命题公式仅由有限步使用规则 1-3后产生的结果。
Guoyongfang.2006@yahoo.com.cn
符号串,((P∧ (Q∨ R))→ (Q∧ (┐ S∨ R))) ；
(┐ (P∧ Q))； (P→ (┐ (P∧ Q)))；
(((P→ Q)∧ (R→ Q))→ (P→ R))。
等都是命题公式。
符号串,(P→ Q)∧┐ Q)； (P→ Q；
(┐ P∨ Q∨ (R； P∨ Q∨ 。
等都不是合法的命题公式。
命题公式与翻译
Guoyongfang.2006@yahoo.com.cn
命题公式与翻译为了不使句子产生混淆，作如下约定,
命题联结词之优先级如下：
1,否定 → 合取 → 析取 → 条件 → 双条件
2,同级的联结词,按其出现的先后次序 (从左到右 )
3,若运算要求与优先次序不一致时,可使用括号 ；同级符号相邻时,也可使用括号 。
括号中的运算为最优先级 。
Guoyongfang.2006@yahoo.com.cn
命题公式与翻译设命题 P：明天上午七点下雨；
Q：明天上午七点下雪；
R：我将去学校。
符号化下述语句：
如果明天上午七点不是雨夹雪，则我将去学校 。
┐ (P∧Q)→R
如果明天上午七点不下雨并且不下雪，则我将去学校。
(┐ P∧┐Q)→R
Guoyongfang.2006@yahoo.com.cn
命题公式与翻译
如果明天上午七点下雨或下雪，则我将不去学校。
(P∨Q)→┐R
明天上午我将雨雪无阻一定去学校。
(P∧Q∧R)∨(┐P∧Q∧R)∨
(P∧┐Q∧R)∨(┐P∧┐Q∧R) 。
或 ((P∧Q)∨(┐P∧Q)∨(P∧┐Q)
∨(┐P∧┐Q))∧R
Guoyongfang.2006@yahoo.com.cn
命题公式与翻译设命题 P：你陪伴我；
Q：你代我叫车子；
R：我将出去。
符号化下述语句：
⑴．除非你陪伴我或代我叫车子，否则我将不出去。
⑵．如果你陪伴我并且代我叫辆车子，则我将出去。
⑶．如果你不陪伴我或不代我叫辆车子，我将不出去。
解,句子⑴可符号化为,┐( P∨Q)→┐R 。
句子⑵可符号化为,(P∧Q)→R 。
句子⑶可符号化为,(┐ P∨┐Q)→┐R 。
Guoyongfang.2006@yahoo.com.cn
例如：
1.上海到北京的 14次列车是下午 5点半开或
6点开。
2.他虽聪明，但不用功。
3.我既不看电视也不外出，我在睡觉。
4.如果你来了，那么他唱不唱歌将看你是否伴奏而定。
命题公式与翻译
Guoyongfang.2006@yahoo.com.cn
命题公式与翻译自然语言中的一些联结词，如,与,,
,且,,,或,,,除非,等等都各有其具体含义，因此需分不同情况翻译成适当的逻辑联结词。为了便于正确表达命题间的相互关系，又是也常常采用列出,真值表,的方法，进一步分析各命题，以此寻找逻辑联结词，使原来的命题能够正确地用形式符号予以表达。
Guoyongfang.2006@yahoo.com.cn
1－ 4 真值表与等价公式真值表 在命题公式中，对于分量指派真值得各种可能组合，就确定了这个命题公式的各种真值情况，把它汇列成表，就是命题公式的真值表。
一般来说，若有ｎ个命题变元，则应有 2n个不同的解释。
Guoyongfang.2006@yahoo.com.cn
例,设有公式,G＝ (P∧ Q)→ R 其中,P,Q
,R是 G的所有命题变元，则其真值表如下：
P Q R P∧Q (P∧Q)→R
F F F F T
F F T F T
F T F F T
F T T F T
T F F F T
T F T F T
T T F T F
T T T T T
真值表与等价公式
Guoyongfang.2006@yahoo.com.cn
真值表与等价公式该真值表可简化为：
P Q R (P∧Q)→R
F F F T
F F T T
F T F T
F T T T
T F F T
T F T T
T T F F
T T T T
Guoyongfang.2006@yahoo.com.cn
真值表
1,┐ P ∨Q
2,┐ Q → ┐ P
3,(p →Q ) ∧ (Q →P )
4,(p ∧ Q) ∨ ( ┐ p ∧ ┐ Q)
Guoyongfang.2006@yahoo.com.cn
真值表与等价公式例,列出公式：
G＝ P∧┐ P的真值表。
解：公式 G仅含 一 个命题变元，所以真值表如下
P P∧┐ P
F F
T F
Guoyongfang.2006@yahoo.com.cn
真值表与等价公式例,列出公式：
G＝ P ∨ ┐ P的真值表。
解：公式 G仅含 一 个命题变元，所以真值表如下
P P ∨ ┐ P
F T
T T
Guoyongfang.2006@yahoo.com.cn
1-4 真值表与等价公式有一类公式，不论命题变元作何种指派，其真值用为真（假），我们把这类公式记作 T（ F）。
Guoyongfang.2006@yahoo.com.cn
真值表与等价公式某些命题公式在分量的不同指派下，
其对应的真值与另一个命题公式完全相同。
Guoyongfang.2006@yahoo.com.cn
等价给定两个命题公式 A和 B，设 P1,P2,…,
Pn为所有出现于 A和 B中的原子变元，若给 P1，
P2,…,Pn任一组真值指派,A和 B的真值都相同，则称 A和 B是等价的或逻辑相等。记作 A
B?
Guoyongfang.2006@yahoo.com.cn
等价的证明证明,
P? Q (┐ P ∨Q) ∧ (P ∨ ┐ Q)?
Guoyongfang.2006@yahoo.com.cn
等价定义 1-4.3
如果 X是合式公式 A的一部分，且 X本身也是一个合式公式，则称 X为公式 A的子公式。
定理 1-4.1
设 X是合式公式 A的子公式，若 X等价于 Y，如果将 A中的 X用 Y来置换，所得到的公式 B与
A等价。
Guoyongfang.2006@yahoo.com.cn
小结证明等价的方法：
1.使用真值表
2.使用等价置换
Guoyongfang.2006@yahoo.com.cn
证明：
┐ (P→ Q)＝ P∧ ┐ Q
(P→ Q) ∧ (R→ Q) ＝ (P ∨ R) → Q
化简下式：
（ A ∧ B ∧ C） ∨ （ ┐ A ∧ B ∧ C）
如果 AVC=BVC，是否有 A=B？如果 A ∧ C=
B ∧ C是否有 A=B？如果 ┐ A = ┐ B，是否有 A=B。
真值表与等价公式
Guoyongfang.2006@yahoo.com.cn
1-5 重言式与蕴含式定义 1-5.1
给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为 T，则称该命题公式为重言式或永真式。
定义 1-5.2
给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为 F，则称该命题公式为矛盾式或永假式。
Guoyongfang.2006@yahoo.com.cn
定理 1-5.1
任何两个重言式的合取或析取，仍然是一个重言式。
定理 1-5.2
一个重言式，对同一个分量都用任何合式公式置换，其结果仍为一重言式。
定理 1-5.3
设 A,B是两个命题公式,A等价于 B当且仅当 A当且仅当 B为一个重言式。
1-5 重演式与蕴含式
Guoyongfang.2006@yahoo.com.cn
小结证明等价的方法：
1.使用真值表
2.使用等价置换
3.设 A,B是两个命题公式,A等价于 B当且仅当 A当且仅当 B为一个重言式。
Guoyongfang.2006@yahoo.com.cn
蕴含式定义 1-5.3
当且仅当 P→Q 是一个重言式时，我们称
,P蕴含 Q”，并记作 P Q。
逆换式,Q→P
反换式,┐ P→ ┐ Q
逆反式,┐ Q→ ┐ P
Guoyongfang.2006@yahoo.com.cn
除真值表外,还有两种方法：
① 前件真导后件真方法设公式的前件为真,若能推导出后件也为真,则条件式是永真式,故蕴涵式成立 。
因为欲证 A?B,即证 A?B是永真式 。 对于
A?B,除在 A取真和 B取假时,A?B为假外,
余下 A?B皆为真 。 所以,若 A?B的前件 A
为真,由此可推出 B亦为真,则 A?B是永真式,即 A?B。
蕴含式证明方法
Guoyongfang.2006@yahoo.com.cn
② 后件假导前件假方法设条件式后件为假，若能推导出前件也为假，则条件式是永真式，即蕴涵式成立。
因为若 A→ B的后件 B取假，由此可推出 A取假，即推证了,?BA。又因
A→ BB→?A，故 A?B成立。
蕴含式证明方法
Guoyongfang.2006@yahoo.com.cn
例题
（ 1）试验证 P?Q,Q逻辑蕴含 P
（ 2）（ P → Q）? P → （ P ∧ Q ）
Guoyongfang.2006@yahoo.com.cn
常用蕴含式
P ∧ Q? P P ∧ Q? Q
P? P ∨ Q ┐ P? P → Q
Q? P → Q
┐ （ P → Q ）? P
┐ （ P → Q ）? ┐ Q
P ∧ （ P → Q ）? Q
Guoyongfang.2006@yahoo.com.cn
┐ Q ∧ （ P → Q ）? ┐ P
┐ P ∧( P∨Q )?Q
(P→ Q) ∧ （ Q→ R）?P→ R
(P∨Q ) ∧ ( P→ R) ∧( Q→ R)?R
( P→ Q) ∧( R→ S)?(P∧ R)→ (Q∧ S)
(P?Q)∧ (Q?R)?(P?R)
常用蕴含式
Guoyongfang.2006@yahoo.com.cn
等价式与蕴含式之间的关系定理 1-5.4
设 P,Q为任意两个命题公式,P等价于 Q的充分必要条件是 P蕴含 Q，且 Q蕴含 P。
Guoyongfang.2006@yahoo.com.cn
小结证明等价的方法：
1.使用真值表
2.使用等价置换
3.设 A,B是两个命题公式,A等价于 B当且仅当 A当且仅当 B为一个重言式。
4.设 P,Q为任意两个命题公式,P等价于 Q
的充分必要条件是 P蕴含 Q，且 Q蕴含 P。
Guoyongfang.2006@yahoo.com.cn
蕴含的几个性质设 A,B,C为合式公式
1.若 A蕴含 B且 A是重言式，则 B必为重言式。
2.若 A蕴含 B,B蕴含 C，则 A蕴含 C，即蕴含关系是传递的。
3.若 A蕴含 B，且 A蕴含 C，则 A蕴含 B合取 C。
4.若 A蕴含 B，且 C蕴含 B，则 A析取 C蕴含 B。
Guoyongfang.2006@yahoo.com.cn
例题如果我学习，那么我数学不会不及格。
如果我不热衷于玩扑克，那么我将学习。
但我数学不及格。
因此我热衷于玩扑克。
Guoyongfang.2006@yahoo.com.cn
例题如果 6是偶数，则 7被 2除不尽。
或 5不是素数，或 7被 2除尽。
但 5是素数。
所以 6是奇数。
Guoyongfang.2006@yahoo.com.cn
证,P∨┐((P∨┐Q)∧Q)
P∨┐(P∨┐Q)∨┐Q
(P∨┐Q)∨┐(P∨┐Q)
T
重言式与蕴含式
P∨┐ ((P∨┐ Q)∧ Q) 是永真公式。
Guoyongfang.2006@yahoo.com.cn
联结词小结联接词 记号 记法 真值结果否定 ┐ ┐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同为真假
Guoyongfang.2006@yahoo.com.cn
1-6其他联结词设 P和 Q是任两个原子命题,
① 由合取非联结词 ↑ 和 P,Q连接成 P↑ Q，
称它为 P和 Q的合取非式复合命题,读作
,P合取非 Q”。 P↑ Q的真值由命题 P和 Q
的真值确定：当且仅当 P和 Q均为 Ｔ 时,
P↑ Q为 Ｆ,否则 P↑ Q为 Ｔ 。,合取非,
又常称为,与非,。
Guoyongfang.2006@yahoo.com.cn
② 由析取非联结词 ↓ 和 P,Q连接成 P↓ Q，
称它为 P和 Q的析取非式复合命题，读作
,P析取非 Q”。 P↓ Q的真值由 P和 Q的真值确定：当且仅当 P和 Q均为Ｆ时，
P↓ Q为Ｔ，否则 P↓ Q为Ｆ。,析取非,
又常称为,或非,。
1-6其他联结词
Guoyongfang.2006@yahoo.com.cn
③ 由条件非联结词?和 P,Q连接成 P?Q，称它为 P和 Q的条件非式复合命题，读作,P
条件非 Q”。 P?Q的真值由 P和 Q的真值确定：当且仅当 P为 Ｔ 而 Q为 Ｆ 时,P?Q为
Ｔ ；否则 P?Q为 Ｆ 。
1-6其他联结词
Guoyongfang.2006@yahoo.com.cn
④ 由双条件非联结词?把 P,Q连接成 P?Q，
称它为 P和 Q的双条件非式复合命题，读作,P双条件非 Q”。 P?Q的真值由 P和 Q
的真值确定：当且仅当 P和 Q的真值不同时,P?Q为 Ｔ,否则 P?Q为 Ｆ 。,双条件非,又常称为,异或,,也常用符号?
表示之。
1-6其他联结词
Guoyongfang.2006@yahoo.com.cn
联结词的真值关系
P Q P? Q P? Q P? Q P? Q
0 0
0 1
1 0
1 1
1 1 0 0
1 0 0 1
1 0 1 1
0 0 0 0
Guoyongfang.2006@yahoo.com.cn
联结词的等价关系由表可知,① P?Q(P?Q)
② P?Q(P?Q)
③ P?Q(P?Q)
④ P?Q(P?Q)
Guoyongfang.2006@yahoo.com.cn
与非、或非和异或的性质与非,或非以及异或在计算机科学中是经常使用的 3个联结词,因此,掌握它们的性质是十分必要的 。 令 P,Q和 R是原子命题变元 。
① 与非的性质
(a) P↑ Q?Q↑ P
(b) P↑ PP
(c) (P↑ Q)↑ (P↑ Q)?P∧ Q
(d) (P↑ P)↑ (Q↑ Q)?P∨ Q
Guoyongfang.2006@yahoo.com.cn
② 或非的性质
(a) P↓ Q?Q↓ P
(b) P↓ PP
(c) (P↓ Q)↓ (P↓ Q)?P∨ Q
(d) (P↓ P)↓ (Q↓ Q)?P∧ Q
从上述的性质可知，联结词?,?和?可分别用联结词?或者?取代，读者可以自行验证,?和?
都不满足结合律。
与非、或非和异或的性质
Guoyongfang.2006@yahoo.com.cn
③
(a) P?Q?Q?P
(b) P?(Q?R)?(P?Q)?R
(c) P∧ (Q?R)?(P∧ Q)?(P∧ R)
(d) P?P?F,F?P?P,T?PP
(e) 若 P?Q?R，则 Q?R?P,P?P?Q，且
P?Q?R?F。
与非、或非和异或的性质
Guoyongfang.2006@yahoo.com.cn
以上所有性质，用真值表或命题定律都是不难证明的。
至此，已有了 9个联结词，是否还需要扩充呢？
事实上，两上命题变无 P和 Q，与 9个联结词一共可构成 类命题公式，如下表示之：
Guoyongfang.2006@yahoo.com.cn
P Q F T P Q P Q P? Q P? Q P? Q P? Q
0 0
0 1
1 0
1 1
0
0
0
0
1
1
1
1
0
0
1
1
0
1
0
1
1
1
0
0
1
0
1
0
0
0
0
1
1
1
1
0
0
1
1
1
1
0
0
0
所用的联结词
序号 1 2 3 4 5 6 7 8 9 10
续 表
P Q P? Q P? Q P? Q P? Q Q? P Q? P
0 0
0 1
1 0
1 1
1
1
0
1
0
0
1
0
1
0
0
1
0
1
1
0
1
0
1
1
0
1
0
0
所用的联结词
序号 11 12 13 14 15 16
Guoyongfang.2006@yahoo.com.cn
从列表可知,除命题常元 F,T及命题变元本身外,命题联结词一共有 9个就够了 。
Guoyongfang.2006@yahoo.com.cn
联结词功能完全组已知有 9个联结词就够用了,能不能少呢？ 若能少,表明有些联结词的逻辑功能可由其他联结词替代 。 事实上,也确实如此,因为有下列等价式：
P?Q(P?Q)
P?Q(P?Q)
P?Q(P?Q)
P?Q(P?Q)
可见,扩充的 4个联结词?,?,?和?能由原有 5
个联结词分别替代之 。
Guoyongfang.2006@yahoo.com.cn
又由命题定律：
P?Q?(?P?Q)?(?Q?P)
P?QP?Q
P?Q(?PQ)
P?Q(?PQ)
可知，原有 5个联结词?,?,?,?和?又能由联结词组 {?,?}或 {?,?}取代。那么，究竟最少用几个联结词？就是说，用最少的几个联结词就能等价表示所有的命题公式。或者说，用最少的几个联结词就能替代所有联结词的功能。
这便是所要定义的联结词功能完全组。
Guoyongfang.2006@yahoo.com.cn
最小联结词组：
｛ ┐,∨ ｝
｛ ┐,∧ ｝
｛ ↑ ｝
｛ ↓ ｝
Guoyongfang.2006@yahoo.com.cn
一、对偶给定的命题公式中，将联结词 ∨ 换成
∧,将 ∧ 换成 ∨,若有特殊变元 F和
T亦相互取代，所得公式 A*称为 A的对偶式。
显然,A也为 A*的对偶式。
1－ 7 对偶与范式
Guoyongfang.2006@yahoo.com.cn
对偶与范式例,写出下列表达式的对偶式
1) (P ∨ Q) ∧ R
2) ┐ (P ∨ Q) ∧ (P ∨ ┐ (Q ∧ S))
解,这些表达式的对偶式是
1) (P ∧ Q) ∨ R
2) ┐ (P ∧ Q) ∨ (P ∧ ┐ (Q ∨ S))
Guoyongfang.2006@yahoo.com.cn
定理 设 A和 A*是对偶式,P1,P2,?,Pn是出现在 A和 A*中的原子变元，则
┐ A（ P1,P2,?,Pn ）
A*（ ┐ P1,┐ P2,?,┐ Pn）
A（ ┐ P1,┐ P2,?,┐ Pn）
┐ A*（ P1,P2,?,Pn ）
对偶与范式
Guoyongfang.2006@yahoo.com.cn
对偶与范式定理 设 P1,P2,?,Pn是出现在公式 A和 B中的所有原子变元，如果 A B，则 A* B*
Guoyongfang.2006@yahoo.com.cn
二、范式由于同一个命题公式可以有不同的 表达形式,
而不同的表达形式可以显示很不同的 特征 。
某种特定类型的表达可以显示出从某一角度考虑极为重要的 性质 。但上述的不同表达形式却对我们研究命题演算带来了一定的困难。
因此，从理论上讲，有必要对命题公式的标准形式问题进行一个深入的研究，使公式达到规范化。为此，引入范式这一概念，范式给各种千变万化的公式提供了一个统一的表达形式，同时，范式的研究对命题演算的发展起了极其重要的作用。
对偶与范式
Guoyongfang.2006@yahoo.com.cn
定义 一个命题公式称为合取范式，当且仅当它具有形式：
A1∧A 2∧? ∧A n (n≥1)
其中 A1,A2,?,An都是由命题变元或其否定所组成的析取式。
定义 一个命题公式称为 析 取范式，当且仅当它具有形式：
A1∨A 2∨? ∨A n (n≥1)
其中 A1,A2,?,An都是由命题变元或其否定所组成的 合 取式。
对偶与范式
Guoyongfang.2006@yahoo.com.cn
对偶与范式求公式,(P∨┐ Q)→ R的析取范式和合取范式。
解,(P∨┐Q)→R
＝ ┐ (P∨┐Q)∨R
＝ (┐P∧Q)∨R─── 析取范式
(P∨┐Q)→R
＝ (┐P∧Q)∨R
＝ (┐P∨R)∧(Q∨R)─── 合取范式
Guoyongfang.2006@yahoo.com.cn
任何一个命题公式，求它的合取范式合析取范式，可以通过下面三个步骤进行：
1）将公式中的联结词化归成 ∧,∨ 及 ┐ 。
2）利用德 · 摩根律将否定符号 ┐ 直接移到各个命题变元之前。
3）利用分配律、结合律归约为合取范式或析取范式。
对偶与范式
Guoyongfang.2006@yahoo.com.cn
定义 n个命题变元的合取式，称作 布尔合取或小项,其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。
性质,
1）每一个小项当其真值指派与编码相同时，
其真值为 T，在其余 2n－ 1种指派情况下均为 F。
2）任意两个不同小项的合取式永假。
3）全体小项的析取式永真。
对偶与范式
Guoyongfang.2006@yahoo.com.cn
定义 对于给定的命题公式，如果有一个等价公式，它仅由小项的析取所组成，则该等价式称作原式的 主析取范式 。
定义 在真值表中，一个公式的真值为 T的指派所对应的小项的析取，即为此公式的主析取范式 。
对偶与范式
Guoyongfang.2006@yahoo.com.cn
求一个命题公式的主析取范式的方法：
1）公式的真值表
2）基本等价公式推出步骤：
1）化归为析取范式
2）除去析取范式中所有永假的析取项。
3）将析取式中重复出现的合取项合相同的变元合并。
4）对合取项补入没有出现的命题变元，即添加
（ P ∨┐ P）式，然后，应用分配律展开公式。
对偶与范式
Guoyongfang.2006@yahoo.com.cn
定义 n个命题变元的析取式，称作布尔析取或大项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。
性质：
1）每一个大项当其真值指派与编码相同时，
其真值为 F，在其余 2n－ 1种指派情况下均为 T。
2）任意两个不同大项的析取式永永真。
3）全体大项的合取式永假。
对偶与范式
Guoyongfang.2006@yahoo.com.cn
定义 对于给定的命题公式，如果有一个等价公式，它仅由大项的合取所组成，则该等价式称作原式的 主合取范式 。
定义 在真值表中，一个公式的真值为 F的指派所对应的大项的合取，即为此公式的 主合取范式 。
对偶与范式
Guoyongfang.2006@yahoo.com.cn
求一个命题公式的主合取范式的方法：
1）公式的真值表
2）基本等价公式推出步骤：
1）化归为合取范式
2）除去合取范式中所有永真的合取项。
3）合并相同的析取项和相同的变元。
4）对析取项补入没有出现的命题变元，即添加
（ P ∨┐ P）式，然后，应用分配律展开公式。
对偶与范式
Guoyongfang.2006@yahoo.com.cn
对偶与范式
P Q R 极小项 极大项
0 0 0 m0=┐P∧┐Q∧┐R M0=P∨Q∨R
0 0 1 m1=┐P∧┐Q∧R M1=P∨Q∨┐R
0 1 0 m2=┐P∧Q∧┐R M2=P∨┐Q∨R
0 1 1 m3=┐P∧Q∧R M3=P∨┐Q∨┐R
1 0 0 m4=P∧┐Q∧┐R M4=┐P∨Q∨R
1 0 1 m5=P∧┐Q∧R M5=┐P∨Q∨┐R
1 1 0 m6=P∧Q∧┐R M6=┐P∨┐Q∨R
1 1 1 m7=P∧Q∧R M7=┐P∨┐Q∨┐
R
Guoyongfang.2006@yahoo.com.cn
对偶与范式含有 n个命题变元的极小项 mi和极大项
Mi，可以看作含有 n个命题变元的公式，
因此共有 2n个不同的解释。
这 2n个不同的解释中，有且仅有一个解释使得 mi为 1，即对 mi中以变元形式出现的变元指派为 1，以变元的否定形式出现的变元指派为 0；
2n个不同的解释中，有且仅有一个解释使得 Mi为 0，即对 Mi中以变元形式出现的变元指派为 0，以变元的否定形式出现的变元指派为 1。
Guoyongfang.2006@yahoo.com.cn
mi=┐ Mi； Mi=┐ mi；
i=0,1,2,…,2n-1
Mi∨ Mj=T； mi∧ mj=F；
i≠j； i,j? {0,1,2,…,2n-1}；1m i
12
0i
n
。0M i
12
0i
n
对偶与范式
Guoyongfang.2006@yahoo.com.cn
例 2.1.4.3 设
G=(P→ Q)∧
R，求出它的主析取范式和主合取范式。
P Q R P→Q (P→Q)∧R
0 0 0 1 0
0 0 1 1 1
0 1 0 1 0
0 1 1 1 1
1 0 0 0 0
1 0 1 0 0
1 1 0 1 0
1 1 1 1 1
解,首先列出其真值表如下：
对偶与范式
Guoyongfang.2006@yahoo.com.cn
(1).求主析取范式
(a).从真值表知，该公式 G恰有三个解释使其公式取值为,真,。为此，选出已给公式取值为,1”所在行所对应的变元取值如下：
2,0 0 1 4,0 1 1 8,1 1 1
(b).将上面选出的各行变元取值,还原,成相应的原子命题符号，值为,1”者,还原,成原变量，值为,0”者,还原,成原变量的否定，并构成相应的极小项。则有：
2.┐ P∧┐ Q∧ R该极小项恰有唯一的一组解释 {0,0,1}使其取值为,真,。
4.┐ P∧ Q∧ R该极小项恰有唯一的一组解释 {0,1,1}使其取值为,真,。
8.P∧ Q∧ R该极小项恰有唯一的一组解释 {1,1,1}使其取值为,真,。
对偶与范式
Guoyongfang.2006@yahoo.com.cn
(c).则上述极小项的析取为对应的主析取范式。
G＝ (P→ Q)∧ R
＝ (┐ P∧┐ Q∧ R)∨ (┐ P∧ Q∧ R)∨ (P∧ Q∧ R)
(2).求主合取范式
(a).从真值表知，该公式 G恰有五个解释使其公式取值为,假,。
为此，选出已给公式取值为,0“所在行所对应的变元之值如下：
1.0 0 0 3.0 1 0 5.1 0 0 6.1 0 1 7.1 1 0
(b).将上面选出的各行变元之值,还原,成相应的原子命题符号，值为,1”者,还原,成原变量的否定，值为,0”者,还原,
成原变量，并构成相应的极大项。则有
1.P∨ Q∨ R该极大项恰有唯一的一组解释 {0,0,0}使其取值为,假,。
对偶与范式
Guoyongfang.2006@yahoo.com.cn
3.P∨┐ Q∨ R该极大项恰有唯一的一组解释 {0,1,0}使其取值为,假,。
5.┐ P∨ Q∨ R该极小项恰有唯一的一组解释 {1,0,0}使其取值为,假,。
6.┐ P∨ Q∨┐ R该极大项恰有唯一的一组解释 {1,0,1}使其取值为,假,。
7.┐ P∨┐ Q∨ R该极大项恰有唯一的一组解释 {1,1,0}使其取值为,假,。
(c).则上述极大项的合取为对应的主合取范式。
G=(P→ Q)∧ R
＝ (P∨ Q∨ R)∧ (P∨┐ Q∨ R)∧ (┐ P∨ Q∨ R)
∧ (┐ P∨ Q∨┐ R)∧ (┐ P∨┐ Q∨ R)。
对偶与范式
Guoyongfang.2006@yahoo.com.cn
例 2.1.4.4 利用公式的等价求 G＝ (P→ Q)∧ R的主析取范式和主合取范式。
解,G＝ (P→ Q)∧ R＝ (┐ P∨ Q)∧ R
＝ (┐ P∨ Q∨ (R∧┐ R))∧
((┐ P∧ 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)
－－－－－主合取范式对偶与范式
Guoyongfang.2006@yahoo.com.cn
G＝ (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)
＝ (┐P∧┐Q∧R)∨(┐P∧Q∧R)∨(P∧Q∧R)
—— 主析取范式对偶与范式
Guoyongfang.2006@yahoo.com.cn
若 为 G的主析取范式,则为 ┐ G的主析取范式,其中,
mji(i=1,2,…,2n-k)是 mi(i=0,1,…,2n-1)中去掉 mli(i=1,2,…,k)后剩下的极小项,则,
m j
i
n k2
1i
G?
m l ik
1i
G?
i
n
i
n
i
n
j
k2
1i
j
k2
1i
j
k2
1i
Mm)m(GG
为 G的主合取范式。
对偶与范式
Guoyongfang.2006@yahoo.com.cn
若 为 G的主 合 取范式,则为 ┐ G的主 合 取范式,其中,
Mji(i=1,2,…,2n-k)是 Mi(i=0,1,…,2n-1)中去掉 Mli(i=1,2,…,k)后剩下的极 大 项,则,
为 G的主析合取范式。
M
1
G l
i
k
i
M12
1
G j
i
n
i
i
n
i
n
i
n
j
k2
1i
j
k2
1i
j
k2
1i
mM)M(GG
对偶与范式
Guoyongfang.2006@yahoo.com.cn
设 G＝ (P∧ Q)∨ (┐ P∧ R)∨ (Q∧ R)，求其对应的主析取范式和主合取范式。
解,G＝ (P∧Q)∨(┐P∧R)∨(Q∧R)
＝ (P∧Q∧(┐R∨R))∨
(┐P∧(┐Q∨Q)∧R)∨((┐P∨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)
＝ m1∨m 3∨m 6∨m 7 ----主析取范式对偶与范式
Guoyongfang.2006@yahoo.com.cn
设 G＝ (P∧ Q)∨ (┐ P∧ R)∨ (Q∧ R)，求其对应的主析取范式和主合取范式。
解,G＝ (P∧Q)∨(┐P∧R)∨(Q∧R)
＝ (P∧Q∧(┐R∨R))∨
(┐P∧(┐Q∨Q)∧R)∨((┐P∨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)
＝ m1∨m 3∨m 6∨m 7 ----主析取范式对偶与范式
Guoyongfang.2006@yahoo.com.cn
任何命题公式都存在唯一一个与之等价的 主析取范式 和主合取范式 ；
命题公式是永真公式当且仅当 它的主析取范式包含所有的极小项，此时无主合取范式或者说主合取范式为,空,；
命题公式是永假公式 当且仅当 它的主合取范式包含所有的极大项，此时无主析取范式或者说主析取范式为,空,；
两个命题公式是相等的 当且仅当 它们的主析取范式相等 (即含有相同的极小项 )和主合取范式相等 (即含有相同的极大项 )。
对偶与范式
Guoyongfang.2006@yahoo.com.cn
1-8 推理理论命题演算的一个主要任务在于提供一种正确的思维规律，即 推理规则,应用此规则从一些前提中推导出一个结论来，这种推导过程称为 演绎 或 形式证明 。 定义 1-8.1 设 A和 C是两个命题公式,当且仅当 A → C为一重言式,即 A?C,称 C是 A
的 有效 结论 。 或 C可由 A逻辑地推出 。
Guoyongfang.2006@yahoo.com.cn
推理理论上述定义可推广到 n个前提的情况 。 设 H1，
H2,…,Hn,C是命题公式,当且仅当
H1∧ H2∧ … ∧ Hn?C
称为 C是一组前提 H1,H2,…,Hn,的有效结论 。
Guoyongfang.2006@yahoo.com.cn
推理理论推理的方法,
1,真值表法
2,直接证法
3,间接证法
Guoyongfang.2006@yahoo.com.cn
P ∧ Q? P P ∧ Q? Q
P? P ∨ Q ┐ P? P → Q
P,（ P → Q ）? Q
┐ Q,（ P → Q ）? ┐ P
┐ P,P ∨ Q? Q
(P→ Q) ∧ （ Q→ R）?P→ R
Guoyongfang.2006@yahoo.com.cn
推理理论一、真值表法,设 P1,P2,…,Pn是出现在前提
H1,H2,…,Hn和结论 C中的一切命题变元,假定对
P1,P2,…,Pn作 了全部的真值指派，这样就能对应地确定 H1,H2,…,Hn和 C的 所有 真值,列出这个真值表，
即可看出公式是否成立。 判断方法如下：
1.对所有 H1,H2,…,Hn 都具有真值 T的行 (表示前提为真的行 ),如果在每一个这样的行中,C 也具有真值 T,则 C 是
H1,H2,…,Hn 的 结论 。
Guoyongfang.2006@yahoo.com.cn
推理理论
2,对所有 C具有真值为 F的行 (表示结论为假的行 ),如果在每一个这样的行中，
H1,H2,…,Hn 中至少有一个公式的真值为
F(前提也为假 )，则 H是 H1,H2,…,Hn 的 结论,
Guoyongfang.2006@yahoo.com.cn
推理理论判断下列 H是否是前提 G1,G2的逻辑结果
(1) H,Q； G1,P； G2,P→Q ；
(2) H,┐ P； G1,P→Q ； G2,┐ Q；
(3) H,Q； G1,┐ P； G2,P→Q 。
Guoyongfang.2006@yahoo.com.cn
推理理论解,建立真值表如下：
P Q G1 G2 H
0 0 0 1 0
0 1 0 1 1
1 0 1 0 0
1 1 1 1 1
(1)
P Q G1 G2 H
0 0 1 1 1
0 1 1 0 1
1 0 0 1 0
1 1 1 0 0
(2)
P Q G1 G2 H
0 0 1 1 0
0 1 1 1 0
1 0 0 0 0
1 1 0 1 1
(3)
Guoyongfang.2006@yahoo.com.cn
二、直接证法,由一组前提，利用一些公认的推理规则，根据已知的等价或蕴含公式，推演得到有效的结论。
规则 P(前提引入规则 )：前提在推导的过程中可以随时引入。
规则 T(逻辑结果引用规则 )：在推导的过程中,如果有一个或多个公式蕴含着公式 S，则 公式 S可以 引入推导之中 。
推理理论
Guoyongfang.2006@yahoo.com.cn
证明,符号化上述语句,Г ={P∨Q→R,R→S,┐S},G=┐Q 。证明
Г?G。
如果马会飞或羊吃草，则母鸡就会是飞鸟；如果母鸡是飞鸟，那么烤熟的鸭子还会跑；烤熟的鸭子不会跑。所以羊不吃草。
推理理论
Guoyongfang.2006@yahoo.com.cn
证明,符号化上述语句,Г ={P∨Q→R,R→S,┐S},G=┐Q 。证明
Г?G。
证：⑴ ┐ S P
⑵ R→S P
⑶ ┐ R T,⑴,⑵,I
⑷ P∨Q→R P
⑸ ┐ (P∨Q) T,⑶,⑷,I
⑹ ┐ P∧┐Q T,⑸,E
⑺ ┐ Q T,⑹,I
推理理论
Guoyongfang.2006@yahoo.com.cn
推理理论证：
⑴ P∨Q P
⑵ ┐ P→Q T,(1),E
⑶ Q→S P
设前提 Г ={P∨Q,P→R,Q→S},公式 G=S∨R 。 证明
Г?G。
Guoyongfang.2006@yahoo.com.cn
推理理论
⑷ ┐ P→S T,⑵,⑶,I
⑸ ┐ S→P T,⑷,E
⑹ P→R P
⑺ ┐ S→R T,⑸,⑹,I
⑻ S∨R T,⑺,E
Guoyongfang.2006@yahoo.com.cn
推理理论三、间接证法定义 1-8.2 假设公式 H1,H2,…,Hn是 中的 命题变元 为 P1,P2,…,Pn,对于 P1,P2,…,Pn 的一些真值指派，如果能 使 H1∧H 2∧ … ∧H n的真值为 T，则称公式 H1,H2,…,Hn 是 相容 的 。 如果 对 P1,P2,…,Pn 的每一组真值指派使得
H1∧H 2∧ … ∧H n 的真 值为 F,则称公式
H1,H2,…,Hn 是 不相容 的
Guoyongfang.2006@yahoo.com.cn
推理理论
1,间接证法一,设有一组前提
H1,H2,…,Hn,要推出结论 C,即证
H1∧H 2∧ … ∧H n? C,记作 S? C,即
┐ C→┐S 为永真,或 C ∨ ┐S 为永真,
故 ┐ C∧S 为永假 。 因此要证明
H1∧H 2∧ … ∧H n? C,只 要 证 明
H1∧H 2∧ … ∧H n 与 ┐ C 不相容 的 。
Guoyongfang.2006@yahoo.com.cn
推理理论证,⑴ ┐(┐ P) P(附加前提 )
⑵ P T,⑴,E
⑶ P→Q P
⑷ Q T,⑵,⑶,I
⑸ ┐ (Q∨R) P
⑹ ┐ Q∧┐R T,⑸,E
⑺ ┐ Q T,⑹,I
⑻ Q∧┐Q T,⑷,⑺,I
设 Г ={P→Q,┐(Q∨R)},G=┐P 。 证明,Г?G。
Guoyongfang.2006@yahoo.com.cn
推理理论证,⑴ ┐(┐( P∧Q)) P(附加前提 )
⑵ P∧Q T,⑴,E
⑶ P T,⑵,I
⑷ ┐P∧┐Q P
┐ P T,⑷,I
⑹ P∧┐P T,⑶,⑸,I
设 Г ={┐P∧┐Q},G=┐(P∧Q) 。证明,Г?G。
Guoyongfang.2006@yahoo.com.cn
推理理论
2,间接证法二,若要 证 H1∧H 2∧ … ∧H n?
（ R→C ） 。 H1,H2,…,Hn,为 S,即证 S?（ R→C) 或 S?
（ ┐ R∨ C ）,故 S→ (┐ R∨ C) 为 永 真 式 。 因为
S→ (┐ R∨ C) ┐S ∨ (┐ R∨ C) （ ┐ S∨ ┐ R ） ∨ C
┐(S∧ R)∨ C (S∧ R)→C,所以若将 R作附加前提,如有 (S∧ R)? C,即证得 S?（ R→C) 。 由 (S∧ R)
C,证得 S?（ R→C) 称为 CP规则 。
Guoyongfang.2006@yahoo.com.cn
推理理论
⑴ ┐ S P(附加前提 )
⑵ Q→S P
⑶ ┐ Q T,⑴,⑵,I
设前提 Г ={P∨Q,P→R,Q→S},公式 G=S∨R 。 证明
Г?G。
利用规则 CP将 ┐ S作为附加前提引进。
Guoyongfang.2006@yahoo.com.cn
推理理论
⑷ P∨Q P
⑸ P T,⑶,⑷,I
⑹ P→R P
⑺ R T,⑸,⑹,I
⑻ S∨R CP,⑴,⑺,E
Guoyongfang.2006@yahoo.com.cn
推理理论证,⑴ R P(附加前提 )
⑵ ┐ R∨P P
⑶ P T,⑴,⑵,I
设 Г ={P→(Q→S),┐R∨P,Q},G=R→S 。证明：
Г?G。
Guoyongfang.2006@yahoo.com.cn
推理理论
⑷ P→(Q→S) P
⑸ Q→S T,⑶,⑷,I
⑹ Q P
⑺ S T,⑸,⑹,I
⑻ R→S CP,⑴,⑺
Guoyongfang.2006@yahoo.com.cn
第一章作业
P23 1-5习题（ 2） (3)
P27 1-7习题 (4).a.e（ 7）（ 8）
P47 1-8习题 (1).b (2).c (3).d
