左孝凌离散数学1.5重言式与蕴含式PPT课件
- 格式：ppt
- 大小：246.00 KB
- 文档页数：10
下载文档原格式
合集下载
1-5重言式与蕴含式
理解识记（可采用上述类似方法）
第一章 数理逻辑 1-5 重言式与蕴含式
2、蕴含式－性质1 、蕴含式－性质
定理1-5.4 设P、Q为任意两个命题公式，P ⇔ Q 为任意两个命题公式， 、 为任意两个命题公式 的充分必要条件是P 的充分必要条件是 ⇒ Q且Q ⇒ P。 且 。 总结两个命题公式等价的证明方法？ 总结两个命题公式等价的证明方法？
第一章 数理逻辑 1-5 重言式与蕴含式
1、重言式－举例 、重言式－
例题1 证明 证明((P ∨ S) ∧ R) ∨ ¬ ((P ∨ S) ∧ R) 是 重言式。 重言式。
第一章 数理逻辑 1-5 重言式与蕴含式
1、重言式－性质2 、重言式－性质
定理1-5.3 设A，B为两个命题公式，A ⇔ B当且 为两个命题公式， ， 为两个命题公式 当且 仅当A 为一个重言式。 仅当 ↔ B为一个重言式。 为一个重言式
1-5 重言式与蕴含式
讲授人： 讲授人：胡 盛
本节
重点
重言式、矛盾式和蕴含式。 重言式、矛盾式和蕴含式。
难点
重言式的推导方法 。
要求
掌握重言式与蕴含式的概念； 掌握重言式与蕴含式的概念； 掌握重言式与等价式的关系； 掌握重言式与等价式的关系； 掌握重言式与蕴含的关系。 掌握重言式与蕴含的关系。
第一章 数理逻辑 1-5 重言式与蕴含式
1、重言式－性质1 、重言式－性质
任何两个重言式 合取或析取， 两个重言式的 定理 1-5.1 任何两个重言式的合取或析取，仍 然是一个重言式。 然是一个重言式。 重言式
定理1 一个重言式 重言式， 同一分量都用 都用任何 定理1-5.2 一个重言式，对同一分量都用任何
合式公式置换，其结果仍为一重言式。 合式公式置换，其结果仍为一重言式。 对于矛盾式， 对于矛盾式，有和定理 1-5.1，定理 1-5.2同样 ， 同样 的结果。 的结果。
第一章 数理逻辑 1-5 重言式与蕴含式
2、蕴含式－性质1 、蕴含式－性质
定理1-5.4 设P、Q为任意两个命题公式，P ⇔ Q 为任意两个命题公式， 、 为任意两个命题公式 的充分必要条件是P 的充分必要条件是 ⇒ Q且Q ⇒ P。 且 。 总结两个命题公式等价的证明方法？ 总结两个命题公式等价的证明方法？
第一章 数理逻辑 1-5 重言式与蕴含式
1、重言式－举例 、重言式－
例题1 证明 证明((P ∨ S) ∧ R) ∨ ¬ ((P ∨ S) ∧ R) 是 重言式。 重言式。
第一章 数理逻辑 1-5 重言式与蕴含式
1、重言式－性质2 、重言式－性质
定理1-5.3 设A，B为两个命题公式，A ⇔ B当且 为两个命题公式， ， 为两个命题公式 当且 仅当A 为一个重言式。 仅当 ↔ B为一个重言式。 为一个重言式
1-5 重言式与蕴含式
讲授人： 讲授人：胡 盛
本节
重点
重言式、矛盾式和蕴含式。 重言式、矛盾式和蕴含式。
难点
重言式的推导方法 。
要求
掌握重言式与蕴含式的概念； 掌握重言式与蕴含式的概念； 掌握重言式与等价式的关系； 掌握重言式与等价式的关系； 掌握重言式与蕴含的关系。 掌握重言式与蕴含的关系。
第一章 数理逻辑 1-5 重言式与蕴含式
1、重言式－性质1 、重言式－性质
任何两个重言式 合取或析取， 两个重言式的 定理 1-5.1 任何两个重言式的合取或析取，仍 然是一个重言式。 然是一个重言式。 重言式
定理1 一个重言式 重言式， 同一分量都用 都用任何 定理1-5.2 一个重言式，对同一分量都用任何
合式公式置换，其结果仍为一重言式。 合式公式置换，其结果仍为一重言式。 对于矛盾式， 对于矛盾式，有和定理 1-5.1，定理 1-5.2同样 ， 同样 的结果。 的结果。
离散数学 重言式与蕴涵式
14. (P ⇄ Q) ∧(Q ⇄ R) (P ⇄ R) A B (A ∧ C) (B ∧ C)
逗号的作用： 将各个前提
分开
A B (A ∨ C) (B ∨ C)
作业：P23 (8)d,e,f (9)
假设后件为F,则P为F，P 为T，分两种情形讨论：
1. Q为T，则 Q 为F ， 前件Q ∧(PQ) 为F；
所以P为F，即 P为T。
前故件蕴为含T式时成，立后。件必 为T，从而蕴涵式成 立
2. Q为F，则 (PQ) 为F ， 前件Q ∧(PQ) 为F。
故蕴含后式件成为立F时。，前件 必为F，从而蕴涵 式成立
5.若AB且CB，则(A∨C) B
P21表1-5.2
1. P ∧ Q P 3. P P ∨ Q 8. P ∧(P Q) Q
课堂练习 Ｐ23(1)c (2)a,b
10. P ∧(P ∨ Q) Q
11. (P Q) ∧ (Q R) (P R)
13. (P Q) ∧(R S) (P ∧ R) (Q ∧ S)
例3 语言推证： (P∨Q) ∧(P R) ∧(Q R) R
几个重要的性质：
1. 设P、Q为任意两个命题公式， P Q 的充分必要条件为 P Q且 Q P 2. A B且A为重言式，则B必是重言式
3. 若A B且B C，则A C 4. 若A B且A C，则A (B ∧ C)
教材P22
Q P 逆反式
如何证明 P Q ?
要证P Q，即证P Q为永真式，而条件式为假只有 一种情况，即前件为真，而后件为假。
2. 蕴涵式的特征 例1：用真值表证明蕴涵式：Q P Q 成立
（1）当前
P
Q
PQ
Q (P Q)
离散数学课堂PPT左孝凌版
简单命题（或原子命题）：简单陈述句表示 的命题。用P，Q，R,…,Pi,Qi,Ri,…表示。
例 P:2是偶数。 Q:雪是黑色的。 命题常量（或命题常元）：简单命题。 命题变项（或命题变元）：真值可以变化的
简单陈述句。不是命题。 例：x+y>5
命题变项也用P，Q，R,…, Pi,Qi,Ri,…表示。 复合命题：由简单命题用联结词联结而成的命题。
∧表示自然语言中的“既……又……”， “不仅……而且……”， “虽然……但是”
P Q P ∧Q
TT
T
TF
F
FT
F
FF
F
例3将下列命题符号化。 （1）李平既聪明又用功。 （2）李平虽然聪明，但不用功。 （3）李平不但聪明，而且用功。 （3）李平不是不聪明，而是不用功。
解：设P：李平聪明；Q：李平用功。 （1）P∧Q （2）P∧ᄀQ （3）P∧Q （4）ᄀ（ᄀP）∧ᄀQ
⇔T→( (Q∧ᄀQ) ∧R)
（排中律）
⇔T→(F∧R)
（矛盾律 ）
⇔T→F
（零律）
⇔ᄀT∨F
（蕴涵等值式）
⇔F∨F⇔F
（等幂律）
3. 证明 (P→Q) ∧ᄀP
⇔(ᄀP∨Q) ∧ᄀP
（蕴涵等价值式）
⇔ᄀP
（吸收律）
1-5 重言式与蕴涵式
定义1－ 给定一命题公式 ，若无论对分量作什么样的指 派，其对应的真值永为T，则称该命题公式 为重言式或永真式。
解：（1）－（4）设P：2+2＝4；Q：3是奇数。
（1）P⇄Q 真命题
（2）P⇄ᄀQ 假命题
（3）ᄀP⇄Q 假命题
（4）ᄀP⇄ᄀQ 真命题
（5）设P：两圆的面积相等；Q：两圆的面积相同。
例 P:2是偶数。 Q:雪是黑色的。 命题常量（或命题常元）：简单命题。 命题变项（或命题变元）：真值可以变化的
简单陈述句。不是命题。 例：x+y>5
命题变项也用P，Q，R,…, Pi,Qi,Ri,…表示。 复合命题：由简单命题用联结词联结而成的命题。
∧表示自然语言中的“既……又……”， “不仅……而且……”， “虽然……但是”
P Q P ∧Q
TT
T
TF
F
FT
F
FF
F
例3将下列命题符号化。 （1）李平既聪明又用功。 （2）李平虽然聪明，但不用功。 （3）李平不但聪明，而且用功。 （3）李平不是不聪明，而是不用功。
解：设P：李平聪明；Q：李平用功。 （1）P∧Q （2）P∧ᄀQ （3）P∧Q （4）ᄀ（ᄀP）∧ᄀQ
⇔T→( (Q∧ᄀQ) ∧R)
（排中律）
⇔T→(F∧R)
（矛盾律 ）
⇔T→F
（零律）
⇔ᄀT∨F
（蕴涵等值式）
⇔F∨F⇔F
（等幂律）
3. 证明 (P→Q) ∧ᄀP
⇔(ᄀP∨Q) ∧ᄀP
（蕴涵等价值式）
⇔ᄀP
（吸收律）
1-5 重言式与蕴涵式
定义1－ 给定一命题公式 ，若无论对分量作什么样的指 派，其对应的真值永为T，则称该命题公式 为重言式或永真式。
解：（1）－（4）设P：2+2＝4；Q：3是奇数。
（1）P⇄Q 真命题
（2）P⇄ᄀQ 假命题
（3）ᄀP⇄Q 假命题
（4）ᄀP⇄ᄀQ 真命题
（5）设P：两圆的面积相等；Q：两圆的面积相同。
离散数学PPT课件 16重言式与重言蕴涵(ppt文档)
• 注意符号“”不是联结词，它是表示公 式间的“永真蕴涵”关系，也可以看成是
“推导”关系。即AB可以理ቤተ መጻሕፍቲ ባይዱ成由A可推 出B，即由A为真，可以推出B也为真。
2.重言(永真)蕴涵式证明方法 方法1.列真值表。(即列永真式的真值表) 这里就不再举例了。
下面讨论另外两种方法。
先看一看AB的真 值表，如果AB为 永真式，则真值表 的第三组指派不会 出现。于是有下面 两种证明方法。
式B，则称B是A(P1,P2,…,Pn) 的置换例式。
• 例如： 公式A：P∨(P∧((PQ)R)) 用(DE)替换A中P得到A的置换例式 B: (DE)∨((DE)∧(((DE)Q)R))
• 如果A是永真式，例如A为P∨P，用 (DE)替换A中P，得到A的置换例式 B： (DE)∨(DE) ， 显然B也是永真式。
I1.P∧QP I3. PP∨Q
I2. P∧QQ I4. QP∨Q
I5. PPQ
I6. QPQ
I7. (PQ)P
I8. (PQ)Q
I9. P,Q P∧Q
I10. P∧(P∨Q)Q
I11. P∧(PQ)Q I12. Q∧(PQ)P
I13. (PQ)∧(QR)PR
AB FF FT TF TT
A B T T F T
方法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
得C为F 得AB为F
F
T
TF F
F
T
TT T
T
T
永真式的真值表的最后一列全是“T”。
“推导”关系。即AB可以理ቤተ መጻሕፍቲ ባይዱ成由A可推 出B，即由A为真，可以推出B也为真。
2.重言(永真)蕴涵式证明方法 方法1.列真值表。(即列永真式的真值表) 这里就不再举例了。
下面讨论另外两种方法。
先看一看AB的真 值表，如果AB为 永真式，则真值表 的第三组指派不会 出现。于是有下面 两种证明方法。
式B，则称B是A(P1,P2,…,Pn) 的置换例式。
• 例如： 公式A：P∨(P∧((PQ)R)) 用(DE)替换A中P得到A的置换例式 B: (DE)∨((DE)∧(((DE)Q)R))
• 如果A是永真式，例如A为P∨P，用 (DE)替换A中P，得到A的置换例式 B： (DE)∨(DE) ， 显然B也是永真式。
I1.P∧QP I3. PP∨Q
I2. P∧QQ I4. QP∨Q
I5. PPQ
I6. QPQ
I7. (PQ)P
I8. (PQ)Q
I9. P,Q P∧Q
I10. P∧(P∨Q)Q
I11. P∧(PQ)Q I12. Q∧(PQ)P
I13. (PQ)∧(QR)PR
AB FF FT TF TT
A B T T F T
方法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
得C为F 得AB为F
F
T
TF F
F
T
TT T
T
T
永真式的真值表的最后一列全是“T”。
左孝凌离散数学1.5重言式与蕴含式PPT课件
从而┐Q（P→Q）为假.
②若Q为假，则┐Q为真，P→Q为假，
从而┐Q（P→Q）为假.
根据① ②，所以 ┐Q（P→Q）┐P
4）法4： （┐Q（P→Q）） → ┐P
┐ （┐Q（ ┐ P ∨ Q）） ∨ ┐P
（Q ∨（P ┐ Q）） ∨ ┐P
（（Q ∨P） （Q ∨ ┐ Q ）） ∨ ┐P
（Q ∨P） ∨ ┐P
4
第一章 命题逻辑（Propositional Logic） 1.5重
言式与蕴含式(Tautology and Implication)
判别命题公式的类型有两种方法: 真值表法和等值
演算法.
等值演算法是将所给命题公式通过等值演算化为最
简单的形式, 然后再进行判别.
例1.判别下列命题公式的类型.
(1). Q∨┓((┓P∨Q)∧P) (重言式)
重言式与蕴含式(Tautology and Implication)
• 小结：本节介绍了命题公式的分类，重言式、矛盾式与蕴 含式的概念及其性质，等价式与蕴涵式的关系。
• 重点掌握: （1）用等值演算法判别命题公式的类型。 （2）重言式、矛盾式与蕴涵式的性质。 （3）等价式与蕴涵式的关系。
• 作业: P23 (1)c,d ,(2) a ,(8). • 预习:1.6 • 思考题:1) 为什么要引入联结词?
2) 什么是最小联结词组? ,,, c
21
1. 真值表指派 2. 真值表及其构成方法 3. 等价公式及等价置换 4. 命题公式的分类 5. 蕴含式判定及其性质
小结
（1）若A在其各种赋值下的取值均为真，则称A是重言式或永真式, 记 为T或1。 （2）若A在其各种赋值下的取值均为假，则称A是矛盾式或永假式, 记 为F或0。
离散数学课件重言式与蕴含式
1-6.5 联结词是否够用
每种联结词对应一种四个T或 的组合 的组合， 每种联结词对应一种四个 或F的组合， 总共可以有2 种组合， 总共可以有 4=16种组合，似乎需要 种组合 似乎需要16 种联结词才够用。 种联结词才够用。 事实上，我们定义的这九种就够用了。 事实上，我们定义的这九种就够用了。 请看P27 表1-6.5 请看
1-5.2蕴含式(implication)
例：见P21 例1 课上做表1-5.2的11式 的 式 课上做表 看表1-5.2，记住常用的蕴含式。 ，记住常用的蕴含式。 看表
1-5.2蕴含式(implication)
定理1-5.4：设P、Q为任意两个命题公式，P⇔Q ： 为任意两个命题公式， ⇔ 定理 、 为任意两个命题公式 的充分必要条件是P⇒Q且Q⇒P 。 的充分必要条件是 ⇒ 且 ⇒ 证明： 为重言式， 证明：由定理 1-5.3 ，P ⇔Q，则P Q为重言式， ， 为重言式 因为由表1-4.7 P Q ⇔(P→Q)∧(Q→P)，故 因为由表 → ∧ → ， (P→Q)为T且 (Q →P)为T，即P⇒Q且Q⇒P 成 → 为 且 为 ， ⇒ 且 ⇒ 立。 反之， 反之，若P⇒Q且Q⇒P 成立，则(P→Q)为T且 ⇒ 且 ⇒ 成立， (Q→P)为T，因此 为重言式， ，因此P Q为T， P Q为重言式， 为 ， 为重言式 即P⇔Q。 ⇔ 。 这个定理也可作为两个公式等价的定义。 这个定理也可作为两个公式等价的定义。
1-5重言式与蕴含式 重言式与蕴含式
1-5.1重言式（tautology） 重言式（ 重言式 ） 定义1-5.2 [矛盾式 矛盾式]: 定义 矛盾式 给定一个命题公式， 给定一个命题公式，若无论对分量 作怎样的指派，其对应的真值永为F， 作怎样的指派，其对应的真值永为 ， 则称该命题公式为矛盾式或永假公式 矛盾式或永假公式。 则称该命题公式为矛盾式或永假公式。
【精品】离散数学PPT课件(完整版)
一个简单命题.
13
联结词与复合命题(续)
3.析取式与析取联结词“∨” 定义 设 p,q为二命题，复合命题“p或q”称作p与q 的析取式，记作p∨q. ∨称作析取联结词，并规 定p∨q为假当且仅当p与q同时为假.
例 将下列命题符号化 (1) 2或4是素数. (2) 2或3是素数. (3) 4或6是素数. (4) 小元元只能拿一个苹果或一个梨. (5) 王晓红生于1975年或1976年.
15
联结词与复合命题(续)
4.蕴涵式与蕴涵联结词“” 定义 设 p,q为二命题，复合命题 “如果p,则q” 称 作p与q的蕴涵式，记作pq，并称p是蕴涵式的 前件，q为蕴涵式的后件. 称作蕴涵联结词，并 规定，pq为假当且仅当 p 为真 q 为假.
16
联结词与复合命题(续)
pq 的逻辑关系：q 为 p 的必要条件 “如果 p，则 q ” 的不同表述法很多：
19
例 求下列复合命题的真值 (1) 2 + 2 ＝ 4 当且仅当 3 + 3 ＝ 6. (2) 2 + 2 ＝ 4 当且仅当 3 是偶数. (3) 2 + 2 ＝ 4 当且仅当 太阳从东方升起. (4) 2 + 2 ＝ 4 当且仅当 美国位于非洲. (5) 函数 f (x) 在x0 可导的充要条件是它在 x0
解 令 p：王晓用功，q：王晓聪明，则 (1) p∧q (2) p∧q (3) p∧q.
12
例 (续)
令 r : 张辉是三好学生，s :王丽是三好学生 (4) r∧s. (5) 令 t : 张辉与王丽是同学，t 是简单命题 .
说明: (1)~(4)说明描述合取式的灵活性与多样性. (5) 中“与”联结的是两个名词，整个句子是
若 p，就 q 只要 p，就 q p 仅当 q 只有 q 才 p 除非 q, 才 p 或 除非 q, 否则非 p. 当 p 为假时，pq 为真 常出现的错误：不分充分与必要条件
13
联结词与复合命题(续)
3.析取式与析取联结词“∨” 定义 设 p,q为二命题，复合命题“p或q”称作p与q 的析取式，记作p∨q. ∨称作析取联结词，并规 定p∨q为假当且仅当p与q同时为假.
例 将下列命题符号化 (1) 2或4是素数. (2) 2或3是素数. (3) 4或6是素数. (4) 小元元只能拿一个苹果或一个梨. (5) 王晓红生于1975年或1976年.
15
联结词与复合命题(续)
4.蕴涵式与蕴涵联结词“” 定义 设 p,q为二命题，复合命题 “如果p,则q” 称 作p与q的蕴涵式，记作pq，并称p是蕴涵式的 前件，q为蕴涵式的后件. 称作蕴涵联结词，并 规定，pq为假当且仅当 p 为真 q 为假.
16
联结词与复合命题(续)
pq 的逻辑关系：q 为 p 的必要条件 “如果 p，则 q ” 的不同表述法很多：
19
例 求下列复合命题的真值 (1) 2 + 2 ＝ 4 当且仅当 3 + 3 ＝ 6. (2) 2 + 2 ＝ 4 当且仅当 3 是偶数. (3) 2 + 2 ＝ 4 当且仅当 太阳从东方升起. (4) 2 + 2 ＝ 4 当且仅当 美国位于非洲. (5) 函数 f (x) 在x0 可导的充要条件是它在 x0
解 令 p：王晓用功，q：王晓聪明，则 (1) p∧q (2) p∧q (3) p∧q.
12
例 (续)
令 r : 张辉是三好学生，s :王丽是三好学生 (4) r∧s. (5) 令 t : 张辉与王丽是同学，t 是简单命题 .
说明: (1)~(4)说明描述合取式的灵活性与多样性. (5) 中“与”联结的是两个名词，整个句子是
若 p，就 q 只要 p，就 q p 仅当 q 只有 q 才 p 除非 q, 才 p 或 除非 q, 否则非 p. 当 p 为假时，pq 为真 常出现的错误：不分充分与必要条件
离散数学-1-5重言式与蕴含式
同理，可假定后件Q的真值取0，若可由推 出P的真值必为0,即证明了Q P 。
整理ppt
7
三、蕴含式证明
例题1：推证Q ∧(P→Q) P
证法一：（由假定前件为真推出后件必为真） 假定Q ∧(P→Q)为1，则 Q 为1且P→Q为1，由Q 为1可
知Q为0，此时由P→Q为1可知，P必为0，故P为真 证法二: (由假定后件为假推出前件必为假） 假定P为0,则P为1。对Q的情况做如下讨论： （1）：若Q为0,则P→Q为0, Q ∧(P→Q) 为0 （2）：若Q为1,则 Q为0, Q ∧(P→Q) 为0
(3) 若真值表最后一列中至少有一个1， 则公式为可满足式。
整理ppt
3
一、公式的真假值分类
定理1.5.1及证明 P19 定理1.5.2及证明 P19 定理1.5.3及证明 P20
整理ppt
4
二、(永真/重言)蕴含式
形如A→B重言式在我们将要学习的推理理 论中有着十分重要的作用。
定义1-5.3 当且仅当P→Q是一个重言式时， 我们称“P蕴含Q”，并记作PQ。 （注：本课约定，“P →Q”读作P蕴含Q，
“P Q”读作P永真/重言蕴含Q。） *注：其中“”同样是一种元语言符号，用
来表示蕴涵式为重言式。
整理ppt
5
二、 (永真/重言)蕴含式
P→Q是不对称的， P→Q与Q→P一般是不等价的。 对P→Q来说：
Q→P 称为它的逆换式。（前、后件取逆序） P→Q 称为它的反换式。（前、后件取其否定） Q→P 称为它的逆反式。（前、后件取逆序及否定）
整理ppt
四、一些重要的（重言）蕴含式
Q ∧(P→Q) P (拒取式) P∧(P∨Q )Q (析取三段论) (P→Q) ∧(Q→R) P→R (假言三段论)
整理ppt
7
三、蕴含式证明
例题1：推证Q ∧(P→Q) P
证法一：（由假定前件为真推出后件必为真） 假定Q ∧(P→Q)为1，则 Q 为1且P→Q为1，由Q 为1可
知Q为0，此时由P→Q为1可知，P必为0，故P为真 证法二: (由假定后件为假推出前件必为假） 假定P为0,则P为1。对Q的情况做如下讨论： （1）：若Q为0,则P→Q为0, Q ∧(P→Q) 为0 （2）：若Q为1,则 Q为0, Q ∧(P→Q) 为0
(3) 若真值表最后一列中至少有一个1， 则公式为可满足式。
整理ppt
3
一、公式的真假值分类
定理1.5.1及证明 P19 定理1.5.2及证明 P19 定理1.5.3及证明 P20
整理ppt
4
二、(永真/重言)蕴含式
形如A→B重言式在我们将要学习的推理理 论中有着十分重要的作用。
定义1-5.3 当且仅当P→Q是一个重言式时， 我们称“P蕴含Q”，并记作PQ。 （注：本课约定，“P →Q”读作P蕴含Q，
“P Q”读作P永真/重言蕴含Q。） *注：其中“”同样是一种元语言符号，用
来表示蕴涵式为重言式。
整理ppt
5
二、 (永真/重言)蕴含式
P→Q是不对称的， P→Q与Q→P一般是不等价的。 对P→Q来说：
Q→P 称为它的逆换式。（前、后件取逆序） P→Q 称为它的反换式。（前、后件取其否定） Q→P 称为它的逆反式。（前、后件取逆序及否定）
整理ppt
四、一些重要的（重言）蕴含式
Q ∧(P→Q) P (拒取式) P∧(P∨Q )Q (析取三段论) (P→Q) ∧(Q→R) P→R (假言三段论)
左孝凌离散数学课件1知识讲解176页PPT
40、人类法律，事物有规律，这是不 容忽视 的。— —爱献 生
46、我们若已接受最坏的，就再没有什么损失。——卡耐基 47、书到用时方恨少、事非经过不知难。——陆游 48、书籍把我们引入最美好的社会，使我们认识各个时代的伟大智者。——史美尔斯 49、熟读唐诗三百首，不会作诗也会吟。——孙洙 50、谁和我一样用功，谁就会和我一样成功。——莫扎特
左孝凌离散数学课件1知识讲解
36、如果我们国家的法律中只有某种 神灵， 而不是 殚精竭 虑将神 灵揉进 宪法， 总体上 来说， 法律就 会更好 。—— 马克·吐 温 37、纲纪废弃之日，便是暴政兴起之 时。— —威·皮 物特
38、若是没有公众舆论的支持，法律 是丝毫 没有力 量的。 ——菲 力普斯 39、一个判例造出另一个判例，它们 迅速累 聚，进
46、我们若已接受最坏的，就再没有什么损失。——卡耐基 47、书到用时方恨少、事非经过不知难。——陆游 48、书籍把我们引入最美好的社会，使我们认识各个时代的伟大智者。——史美尔斯 49、熟读唐诗三百首，不会作诗也会吟。——孙洙 50、谁和我一样用功，谁就会和我一样成功。——莫扎特
左孝凌离散数学课件1知识讲解
36、如果我们国家的法律中只有某种 神灵， 而不是 殚精竭 虑将神 灵揉进 宪法， 总体上 来说， 法律就 会更好 。—— 马克·吐 温 37、纲纪废弃之日，便是暴政兴起之 时。— —威·皮 物特
38、若是没有公众舆论的支持，法律 是丝毫 没有力 量的。 ——菲 力普斯 39、一个判例造出另一个判例，它们 迅速累 聚，进
左孝凌离散数学课件
01
集合论
集合的基本概念
总结词
集合是离散数学中的基本概念，它是由一组确定的、不同的、互不相同的元素所组成的 。
详细描述
集合是离散数学中一个最基本的概念，它是由一组确定的、不同的、互不相同的元素所 组成的。这些元素可以是数字、字母、图形等，它们在集合中表示不同的个体或对象。
集合的运算和性质
总结词
详细描述
邻接矩阵是一种常用的图表示方法，通过二维矩阵表示节点之间的关系，矩阵中的元素表示边的权重 或连接状态；邻接表是一种更有效的图表示方法，通过链表或数组等数据结构表示节点和其相邻节点 之间的关系。
图的连通性
总结词
图的连通性是指图中任意两个节点之间是否 存在路径。
详细描述
图的连通性分为强连通和弱连通两种情况。 强连通是指图中任意两个节点之间都存在有 向路径；弱连通是指图中任意两个节点之间 都存在无向路径。判断图的连通性是图论中 的重要问题之一。
左孝凌离散数学课件
THE FIRST LESSON OF THE SCHOOL YEAR
• 离散数学简介 • 集合论 • 图论 • 逻辑学 • 离散概率论 • 离散统计学
目录CONTENTS
01
离散数学简介
离散数学的起源和定义
总结词
离散数学的起源可以追溯到古代数学，它与连续数学相对应，研究的是非连续的、分离的对象。
置信区间
置信区间是指根据样本数据估计 总体参数的可能范围，用于衡量 估计的准确性。
单侧检验和双侧检
验
单侧检验是指只检验一个方向的 假设，而双侧检验则是同时检验 两个方向的假设。
感谢观看
THANKS
THE FIRST LESSON OF THE SCHOOL YEAR
重言式与蕴含式
2020/6/29
基本永真蕴含式
2020/6/29
2020/6/29
等价式与蕴含式的关系: 定理1.5.4: 设P,Q为任意两个命题公式,PQ的充
要条件为PQ且QP. 证：若PQ，则PQ为永真式
因为 PQ （P→Q）（Q→P） 所以 P→Q，Q→P为永真式,从而 PQ，QP. 反之，若PQ，QP，则P→Q，Q→P为永真式, 所以（P→Q）（Q→P）为永真式， 从而 PQ为永真式，即PQ.
2020/6/29
3) （A→B）（A→C） （┐AB）（┐AC） ┐A（BC） A→BC
4) （A→B）（C→B） （┐AB）（┐CB） （┐A┐C）B ┐（AC）B AC→B
2020/6/29
小结：本节介绍了命题公式的分类，重言式、 矛盾式与蕴含式的概念及其性质，等价式与蕴 涵式的关系。
原命题 逆换式 反换式 逆反式 PQ QP P Q Q P
它们之间具有如下关系:
PQ
Q
P
由P21 表1-5.1
QP P Q 可以得出
因此, 要证明P Q有三种方法:
1)真值表法:即列出PQ的真值表,观察其是否永为真。
2)直接证法:假定前件P是真，推出后件Q是真。
3)间接证法:假定后件是假，推出前件是假,即证 Q P
（3）若A不是矛盾式则称A为可满足式(satisfiable)。 注: 由定义可知,重言式一定是可满足式,反之不真.
2020/6/29
判别命题公式的类型有两种方法: 真值表法和等值
演算法.
等值演算法是将所给命题公式通过等值演算化为最
简单的形式, 然后再进行判别.
例1.判别下列命题公式的类型.
(1). Q∨┓((┓P∨Q)∧P)
基本永真蕴含式
2020/6/29
2020/6/29
等价式与蕴含式的关系: 定理1.5.4: 设P,Q为任意两个命题公式,PQ的充
要条件为PQ且QP. 证：若PQ，则PQ为永真式
因为 PQ （P→Q）（Q→P） 所以 P→Q，Q→P为永真式,从而 PQ，QP. 反之，若PQ，QP，则P→Q，Q→P为永真式, 所以（P→Q）（Q→P）为永真式， 从而 PQ为永真式，即PQ.
2020/6/29
3) （A→B）（A→C） （┐AB）（┐AC） ┐A（BC） A→BC
4) （A→B）（C→B） （┐AB）（┐CB） （┐A┐C）B ┐（AC）B AC→B
2020/6/29
小结：本节介绍了命题公式的分类，重言式、 矛盾式与蕴含式的概念及其性质，等价式与蕴 涵式的关系。
原命题 逆换式 反换式 逆反式 PQ QP P Q Q P
它们之间具有如下关系:
PQ
Q
P
由P21 表1-5.1
QP P Q 可以得出
因此, 要证明P Q有三种方法:
1)真值表法:即列出PQ的真值表,观察其是否永为真。
2)直接证法:假定前件P是真，推出后件Q是真。
3)间接证法:假定后件是假，推出前件是假,即证 Q P
（3）若A不是矛盾式则称A为可满足式(satisfiable)。 注: 由定义可知,重言式一定是可满足式,反之不真.
2020/6/29
判别命题公式的类型有两种方法: 真值表法和等值
演算法.
等值演算法是将所给命题公式通过等值演算化为最
简单的形式, 然后再进行判别.
例1.判别下列命题公式的类型.
(1). Q∨┓((┓P∨Q)∧P)
左孝凌离散数学 ppt课件
2020/4/11
1.1.1 命题
数理逻辑研究的中心问题是推理（inference),而 推理的前提和结论都是表达判断的陈述句，因而表达
判断的陈述句构成了推理的基本单位。 基本概念
✓ 命题：能够判断真假的陈述句。 ✓ 命题的真值：命题的判断结果。命题的真值只取两个 值:真（用T(true)或1表示）、假（用F(false)或0表示） 。 ✓ 真命题：判断为正确的命题，即真值为真的命题。 ✓ 假命题：判断为错误的命题，即真值为假的命题。
❖ 上个世纪30年代以后，数理逻辑进入一个崭新的发展 阶段，逻辑学不仅与数学结合，还与计算机科学等密 切关联。
第一章 命题逻辑（Propositional Logic）
1.1 命题及其表示方法
• 1.1.1 命题（Proposition) • 1.1.2 命题的表示方法 • 1.1.3 命题的分类
逻辑可分为：1. 形式逻辑（通过数学方法） 数理逻辑 2. 辩证逻辑 指引进一套符号体系的方法。
辩证逻辑是研究反映客观世界辩证发展过程的人类思 维的形态的。
❖ 形式逻辑是研究思维的形式结构和规律的科学，它撇 开具体的、个别的思维内容，从形式结构方面研究概 念、判断和推理及其正确联系的规律。
❖ 数理逻辑是用数学方法研究推理的形式结构和推理的 规律的数学学科。它的创始人Leibniz，为了实现把推 理变为演算的想法，把数学引入了形式逻辑。其后， 又经多人努力，逐渐使得数理逻辑成为一门专门的学 科。
结果才为真，否则为假。 自然语言中的表示“并且”意思的联结词，如“既… 又…”、“不但…而且…”、“虽然…但是…”、“一面…一 面…”、 “…和…”、 “…与…”等都可以符号化为∧ 。
18
例3. 将下列命题符号化.
1.1.1 命题
数理逻辑研究的中心问题是推理（inference),而 推理的前提和结论都是表达判断的陈述句，因而表达
判断的陈述句构成了推理的基本单位。 基本概念
✓ 命题：能够判断真假的陈述句。 ✓ 命题的真值：命题的判断结果。命题的真值只取两个 值:真（用T(true)或1表示）、假（用F(false)或0表示） 。 ✓ 真命题：判断为正确的命题，即真值为真的命题。 ✓ 假命题：判断为错误的命题，即真值为假的命题。
❖ 上个世纪30年代以后，数理逻辑进入一个崭新的发展 阶段，逻辑学不仅与数学结合，还与计算机科学等密 切关联。
第一章 命题逻辑（Propositional Logic）
1.1 命题及其表示方法
• 1.1.1 命题（Proposition) • 1.1.2 命题的表示方法 • 1.1.3 命题的分类
逻辑可分为：1. 形式逻辑（通过数学方法） 数理逻辑 2. 辩证逻辑 指引进一套符号体系的方法。
辩证逻辑是研究反映客观世界辩证发展过程的人类思 维的形态的。
❖ 形式逻辑是研究思维的形式结构和规律的科学，它撇 开具体的、个别的思维内容，从形式结构方面研究概 念、判断和推理及其正确联系的规律。
❖ 数理逻辑是用数学方法研究推理的形式结构和推理的 规律的数学学科。它的创始人Leibniz，为了实现把推 理变为演算的想法，把数学引入了形式逻辑。其后， 又经多人努力，逐渐使得数理逻辑成为一门专门的学 科。
结果才为真，否则为假。 自然语言中的表示“并且”意思的联结词，如“既… 又…”、“不但…而且…”、“虽然…但是…”、“一面…一 面…”、 “…和…”、 “…与…”等都可以符号化为∧ 。
18
例3. 将下列命题符号化.
重言式与蕴含式
（4）若A B，C B ，则AC B 以上性质在推理中常用。 特别说明：如果推导蕴含，则可以用等价的式 子替换，因为“等价”比“蕴含”强，好比 “大于等于”与“等于”的关系。
作业（1-5）
P23. (1) b) c) (2) b) 说明： （6）~（8）先不做，因为有效性 第八节讲。
定理1-5.3 设A、B为两个命题，AB当且仅当 A B 为一个重言式。 证明：若AB，则A、B有相同的真值， 由双条件定义 A B 永为T。 若A B为重言式，则A B永为T， 故 A、B有相同的真值，即AB。 上例是重言式，则(PQ) (PQ) 德.摩根律得证
1-5.2蕴含式(implication)
设P、Q、R为命题公式，则有 （1）P Q Q P 交换性 （2）（PQ）R P（QR） 结合性 （3）P(QR)(PQ)(PR) 分配性 （4） PQ （PQ ）（PQ） （5） PQ （P Q）由定义得到 （6） PP F，FP P，TP P
1-5重言式与蕴含式
1-5.1重言式（tautology）
定义1-5.1 [重言式]:
给定一个命题公式，若无论对分量 作怎样的指派，其对应的真值永为T， 则称该命题公式为重言式或永真公式。
1-5重言式与蕴含式
1-5.1重言式（tautology）
定义1-5.2 [矛盾式]:
给定一个命题公式，若无论对分量 作怎样的指派，其对应的真值永为F， 则称该命题公式为矛盾式或永假公式。
1-6其它联结词
定义1-6.1不可兼析取(Exclusive OR)： 设P和Q是两个命题公式，复合命题 PQ称作P和Q的不可兼析取。 PQ的真 值为T，当且仅当P与Q的真值不相同时为 T，否则， PQ的真值为F。真值表如下：
作业（1-5）
P23. (1) b) c) (2) b) 说明： （6）~（8）先不做，因为有效性 第八节讲。
定理1-5.3 设A、B为两个命题，AB当且仅当 A B 为一个重言式。 证明：若AB，则A、B有相同的真值， 由双条件定义 A B 永为T。 若A B为重言式，则A B永为T， 故 A、B有相同的真值，即AB。 上例是重言式，则(PQ) (PQ) 德.摩根律得证
1-5.2蕴含式(implication)
设P、Q、R为命题公式，则有 （1）P Q Q P 交换性 （2）（PQ）R P（QR） 结合性 （3）P(QR)(PQ)(PR) 分配性 （4） PQ （PQ ）（PQ） （5） PQ （P Q）由定义得到 （6） PP F，FP P，TP P
1-5重言式与蕴含式
1-5.1重言式（tautology）
定义1-5.1 [重言式]:
给定一个命题公式，若无论对分量 作怎样的指派，其对应的真值永为T， 则称该命题公式为重言式或永真公式。
1-5重言式与蕴含式
1-5.1重言式（tautology）
定义1-5.2 [矛盾式]:
给定一个命题公式，若无论对分量 作怎样的指派，其对应的真值永为F， 则称该命题公式为矛盾式或永假公式。
1-6其它联结词
定义1-6.1不可兼析取(Exclusive OR)： 设P和Q是两个命题公式，复合命题 PQ称作P和Q的不可兼析取。 PQ的真 值为T，当且仅当P与Q的真值不相同时为 T，否则， PQ的真值为F。真值表如下：
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
A
B
互为充分必要条件
X Y X （X Y）（X Y）（X Y）（X Y）
A
B
A
B
00 1
1
1
1
01 1
1
1
1
10 0
0
0
1
11 0
1
1
1
• 例2 ：证明（（Q → P） ∧ （ ﹁ P→Q ） ∧（QQ） ） P T
证明： 直接证明该式T 很长 根据定理1.5.3，只需证
（（Q → P） ∧ （ ﹁ P→Q ） ∧（QQ） ） P 左 （ ﹁ Q ∨ P） ∧ （ P ∨ Q ） ∧T
言式与蕴含式(Tautology and Implication)
1.5.1 命题公式的分类 1.5.2 重言式与矛盾式的性质 1.5.3 蕴含式
3
第一章 命题逻辑（Propositional Logic） 1.5重
言式与蕴含式(Tautology and Implication)
1.5.1 命题公式的分类 重言式或永真式 矛盾式或永假式 可满足式
Q P 。 • 4）等价代换法：即利用等价代换证明PQ为永真
13
P Q P Q
01
1
11
1
10
0
00
1
直接证法： 要想让P →Q 为永真，那 么当P为真时， Q只能为真
间接证法：要 想让P →Q为永 真，那么当Q 为假时，只能 P只能为假
第一章 命题逻辑（Propositional Logic） 1.5重
（ ﹁ Q ∨ P） ∧ （ Q ∨P ） P ∨（ ﹁ Q ∧ Q） P ∨F P
小结： 证明A B的方法
按定义。即根据真值表，二者具有相同真值 要证明 A B T 只需证明A B 即可，反之亦然 用等价代换推导法A …… B
第一章 命题逻辑（Propositional Logic） 1.5重言
第一章 命题逻辑（Propositional Logic） 1.5重
言式与蕴含式(Tautology and Implication)
原命题 逆换式 反换式 逆反式
PQ QP P Q Q P
• 它们之间具有如下关系: PQ Q P 由P21 表1-5.1 QP P Q 可以得出
• 因此, 要证明P Q有四种方法: • 1)真值表法:即列出PQ的真值表,观察其是否为永真。 • 2)直接证法:假定前件P是真，推出后件Q是真。 • 3)间接证法:假定后件是假，推出前件是假,即证
从而┐Q（P→Q）为假.源自②若Q为假，则┐Q为真，P→Q为假，
从而┐Q（P→Q）为假.
根据① ②，所以 ┐Q（P→Q）┐P
4）法4： （┐Q（P→Q）） → ┐P
• 定理1.5.3： A,B是两个命题公式，A B的充要条件是A B
为重言式。
证明: 若AB为重言式， 则AB永为T，即A，B的真值表相同， 所以AB。 反之，若A B，则A，B真值表相同， 所以AB永为T，所以AB为重言式。举例
8
例如：验证（X Y）（X Y）与
A
B
（X Y）（X Y） T
4
第一章 命题逻辑（Propositional Logic） 1.5重
言式与蕴含式(Tautology and Implication)
判别命题公式的类型有两种方法: 真值表法和等值
演算法.
等值演算法是将所给命题公式通过等值演算化为最
简单的形式, 然后再进行判别.
例1.判别下列命题公式的类型.
(1). Q∨┓((┓P∨Q)∧P) (重言式)
离散数学( ) Discrete Mathematics
1
第一章 命题逻辑（Propositional Logic） 1.5重言
式与蕴含式(Tautology and Implication)
一、命题公式的分类 二、蕴含式 三、蕴含式的性质
第一章 命题逻辑（Propositional Logic） 1.5重
•例题1 证明((P∨S)∧R)V┐((P∨S)∧R)为重言式。
证明： 因为PV┐PT（否定律，）为重言式，根据定理1.5.2
如以((P∨S)∧R)置换P即得 ((P∨S)∧R)V┐((P∨S)∧R) T
-
7
第一章 命题逻辑（Propositional Logic） 1.5重
言式与蕴含式(Tautology and Implication)
式与蕴含式(Tautology and Implication)
1.5.3 蕴含式( Implication)（一类特殊的重言式）
•定义1.5.2：当且仅当P Q是一个重言式时，我们称“P蕴含Q”， 并记作P Q.
例如：（P ∧Q ）→Q ﹁ （P ∧Q ） ∨Q ﹁ P ∨（ ﹁ Q ∨ Q） ﹁ P ∨T T，故（P ∧Q ） Q
得）
证明:设A和B为两个重言式,则不论A和B的分量指派任何真值,总有A为 T,B为T,故A ∧ B T,A ∨ B T
• 定理1.5.2: 一个重言式(矛盾式),对同一分量都用任何合式公式置换,其结果
仍为一重言式(矛盾式).
证明: 由于重言式(矛盾式)的真值与对变元的赋值无关，故对同一变 元以任何合式公式置换后，重言式(矛盾式)的真值仍永为T（F）。举例6
言式与蕴含式(Tautology and Implication)
例: 证明┐Q（P→Q）┐P
1) 法1：真值表 即证明（┐Q（P→Q）） → ┐P为永真
2) 法2：若 ┐Q(P→Q)为真，
则 ┐Q，P→Q均为真，
所以Q为假，P为假，所以┐P为真。
3) 法3：若┐P为假，
则P为真，再分二种情况：
①若Q为真，则┐Q为假, （P→Q）为真
定义1.5.1 设A为任一命题公式， （1）若A在其各种赋值下的取值均为真，则称A是重言
式或永真式, 记为T或1。 （2）若A在其各种赋值下的取值均为假，则称A是矛盾
式或永假式, 记为F或0。 （3）若A不是矛盾式则称A为可满足式(satisfiable)。注:
由定义可知,重言式一定是可满足式,反之不真.
(2). (P∨┓P) (Q∧┓Q)∧R (矛盾式)
(3). (P Q)∧┓P.
(可满足式)
5
第一章 命题逻辑（Propositional Logic） 1.5重
言式与蕴含式(Tautology and Implication)
1.5.2 重言式与矛盾式的性质 • 定理1.5.1: 任何两个重言式的合取或析取,仍然是一重言式.（由幂等律立