离散数学命题与联结词27页PPT

P
Q
0
0
0
1
1
0
1
1
P→Q 1 1 0 1
如： P:雪是黑的。
Q:太阳从东方升起 。
P → Q:如果雪是黑的，则太阳从东方升起 。
命题P→Q是假, 当且仅当P是真而Q是假。
11/20/2020
chapter1
14
1.2 联结词
条件与汉语中“如果…，就…”相类似，但有所区别: (1)自然语言中，“如果P则Q”，往往P和Q有一定的因果 关系，而条件复合命题P→Q中 P和Q 可以完全不相关。 (2)自然语言中，“如果P则Q”，当P为0、Q为1时，整个 句子真值难以确定；而条件复合命题P→Q中，当P为0时， 复合命题的真值为1。 P则Q的逻辑含义:P是Q的充分条件,的表示 命题变元——常用P、Q、R、S等大写字母或加下标的大 写字母P1, Q2, R10, ……表示来表示一个命题，称为命题 变元。 如： P:巴黎在法国。
Q:煤是白色的。
11/20/2020
chapter1
4
1.1 命题及其表示法
3、命题相关概念 简单命题（原子命题）——不能再分解的命题。 复合命题——由若干个简单命题复合而成的命题。 真值表——把组成复合命题的各命题变元的真值的所有 组合及其相对应的复合命题的真值列成表，称为真值表。
11/20/2020
chapter1
6
1.1 命题及其表示法
【例3 】求公式 (P→R)∨(Q→R)的真值表。 解：∵公式含有３个命题变元P、Q、R,
∴真值表有２3=8行。其真值表如下表 所示：
11/20/2020
chapter1
7
1.2 联结词
命题和原子命题常可通过一些联结词构成新命题, 这

A＝B C或A＝B C或A＝B C，则公式A是n＋1层公式， n max( i, j)。
例（1）p q r (2)r q p q p
第23页/共292页
1.2 命题公式及其赋值
( p q) r
p：2是素数，q：3是偶数，r：2是有理数 p：2是素数，q：3是偶数，r：2是无理数
例2.等值等价式p q p q q p
等值演算的应用： 1.验证等值式 ( p q) ( p r) p (q r) 2.判定公式的类型 ( p q) p q,( p ( p q)) r, p ((( p q) p) q) 3.解决工作生活中的判断问题
甲、已、丙3人根据口音对王教授是哪人进行了判断： 甲说：王教授不是苏州人，是上海人 已说：王教授不是上海人，是苏州人 丙说：王教授既不是上海人，也不是杭州人
例：1.如果3＋3＝6，那么雪是白的。 2.除非我能工作完成了，我才去看电影。 3.只要天下雨，我就回家。 4.我回家仅当天下雨。 p→q的逻辑关系为q是p的必要条件或p是q的充分条件。
第15页/共292页
1.1 命题和命题联结词
5).等价词 由命题p、q和 组成的复合命题记作p q,读作“p当且仅当q”。 是自然语言中的“充要条件”，“当且仅当”的逻辑抽象。
1.3 命题公式的等值式
定义1.设A和B是两个命题公式，若A B为重言式， 则称公式A, B是等值的公式，记作A B。
例1.证明（p q) (q p); p p p.
注意： 和 的区别 是公式间的关系符号，如：p q 是命题联结词.p q
第28页/共292页
1.3 命题公式的等值式
1.1 命题和命题联结词
例：1）海洋的面积比陆地的面积大。 例 q2:）： 22p6:6海 9洋 9。 。的面积比陆地的面积大。 r3:）火火星星上上有有生生命命。。 s4:）三三角角形形的的内内角角和和等等于 于118800。 。 55））你你喜 喜欢 欢数学吗吗？？ 66））我我们 们要 要努 努力力学学习习。。 77））啊啊， ，我 我的 的天天哪哪！！ 88））我我正 正在 在说 说谎 谎。。

第14页/共44页
因为只有陈述句才能够表达对事物有“肯定” 或“否定”的思维方式，我们把这种“肯定”和 “否定”称为真值（Truth）。例如陈述句“今天 下雨”，这是一个判断。如果今天真的下雨，则 这个判断的值为真(true)；如果今天没有下雨，则 这个判断的值为假（false）。
我们把具有这种特点的句子叫命题，它是形 式语言中的基本单位。
第5页/共44页
期末总评: 平时30%(考勤10%+作业15%+课堂表现5%)+
期末考试70%
凡主动找老师问问题和认真订正作业 中的错误者都适当加分。
第6页/共44页
对抄袭和作弊行为的管理
高等院校和任何学术交流都严禁任何方式的抄 袭和作弊行为。学生在考试中有任何作弊行为， 将根据学院《学生考试作弊行为处理规定（修 订）》条例由教务处给予处罚。
说明：1、“∨” 属于二元(binary)运算符. 2、联结词“∨”的定义真值表如下：
P
Q
PQ
0
0
0
0
1
1
1
0
1
1
1
1
第29页/共44页
日常语言中的“（或者）…或者…”、“可能… 可能…”等词均可符号化为“ ∨”。
说明:析取又称为逻辑“或”。它可分为可兼或和不 可兼或。联结词 “∨”代表的是可兼或，还有不可 兼或。
第19页/共44页
1.1.2 命题的分类
命题可分为原子命题和复合命题。 定义1-2 凡不能再分解的命题称为原子命题(简单命题 )
由原子命题和联结词联结而成的命题称为复合命题 . 例1-1中，（1）～（4）是原子命题。
例1-1中，（5）是复合命题。
第20页/共44页

联结词可以嵌套使用，在嵌套使用时，规定如下优先顺序： ( )，┐，∧，∨，→， ，对于同一优先级的联结词，先出现 者先运算。
例1.7 令 P : 北京比天津人口多 Q:22 4 R : 乌鸦是白色的
求下列复合命题的真值：
1P Q P Q R 2Q R P R 3P R P R
解 P，Q，R的真值分别为1，1，0。容易算出 (1)、(2)、(3)的真值分别为1，1，0。
2．在自然语言中，“如果P，则Q”中的前件P与后件Q往 往具有某种内在联系。而在数理逻辑中，P与Q可以无任何内 在联系。
3．在数学或其它自然科学中，“如果P，则Q”往往表达 的是前件P为真，后件Q也为真的推理关系。但在数理逻辑中， 作为一种规定，当P为假时，无论Q是真是假，P→Q均为真。 也就是说，只有P为真Q为假这一种情况使得复合命题P→Q为 假。
PQ 的真值定义为 PQ为真当且仅当P, Q同真值 因此, P, Q一真一假时, P Q为假。
复合命题P Q的真值表： P
0 0 1 1
Q
P Q
0
1
1
0
0
0
1
1
例1.6 将下列命题符号化，并指出它们的真值：
3如 两 圆O1 , O2的面积相等，则它们的半径相等；反之亦然. 4当王小红心情愉快时，她就唱歌；反之当她唱歌时，
真值为真的命题称为真命题；真值为假的命题为假命题。
说明：
1. 命题必须是陈述性语句，而不能是疑问句、命令句、 感叹句等；
2. 命题语句或者为真或者为假，二者必取其一，即命 题的真值是唯一的
判断句子是否为命题的标准： (1)陈述句 (2)有唯一的真值
例1 判断下列句子是不是命题: (1) 4是素数。
第一部分 数理逻辑

R 0 1 0 1 0 1 0 1
Assignments（作业）
第30页: 4
1.3 公式分类与等价式
1.3.1 公式分类 1.3.2 等价公式（等值演算） 1.3.3 基本等价式----命题定律 1.3.4 代入规则和替换规则 1.3.5 证明命题公式等价的方法
1.3.1 公式分类
定义1.13 设A是一个命题公式，对A所有可能的解释： (1)若A都为真，称A为永真式或重言式。
(2)若A都为假，称A为永假式或矛盾式。
(3)若至少存在一个解释使得A为真，称A为可满足式。
例1 从上一节真值表可知，命题公式(PQ)(P∨Q)为 重言式，(PQ)∧Q为矛盾式，PQ)∧R为可满足式。
注： 1、 永真式必为可满足式，反之则不然；永真式的否定是永 假式，反之亦然； 2、 决定一个公式是否是一个永真式、永假式或可满足式有 三种方法：真值表法（适用于变元少而简单的公式）、求主范
1.否定词(negation connective )﹁
定义1.4 复合命题“非P”称为命题P的否定，记作
P，读作非P。 P为真当且仅当P为假。
例3 设 P：离散数学是计算机专业的核心课程， 则 P:离散数学不是计算机专业的核心课 程。
2.合取词(conjunction connective )∧
命题符号化的目的在于用五个联结词将日 常语言中的命题转化为数理逻辑中的形式命题， 其关键在于对自然语言中语句之间的逻辑关系 以及命题联结词的含义要有正确的理解，使用 适当的联结词： （1）确定语句是否是一个命题；
（2）找出句中连词，用适当的命题联结词表
示。
Assignments（作业）
第30页: 3（偶数小题）
定义1.12 设A是含有n个命题变元的命题 公式，将命题公式A在所有赋值之下取值的情 况汇列成表，称为A的真值表( truth table )。 为列出一个公式的真值表，我们约定： ①命题变元按字典序排列；②对公式的每个 解释，以二进制从小到大列出；③当公式较 复杂时，可先列出子公式的真值，最后列出 所给公式的真值。

解 令P：我得到这本小说；Q：我今夜就读完它。
于是上述命题可表示为P→Q。
7
5．等值“”
定义2.2.5 设P和Q是两个命题，则它们的等值命
题是一个复合命题，称为等值式复合命题，记作“P Q” （读作“P当且仅当Q”）。
当P和Q的真值相同时,PQ取真,否则取假。
例10
P
Q
P Q
0
0
1
0
1
0
1
0
0
德.摩根定律
E11
PQP∨Q
E12
P Q (P∧Q)∨(P∧Q)
E13
P (QR) (P∧Q) R
E14
P Q (PQ)∧(QP)
E15
PQQP
23
三、等价式的判别
有两种方法：真值表方法，命题演算方法
1、真值表方法
例1 用真值表方法证明 E10： (PQ) PQ
解 令：A= (PQ)，B= PQ，构造A，B
一个复合命题，记作“P→Q”（读作“如果P，则Q”）。
当P为真，Q为假时，P→Q为假，否则 P→Q为真。
P
Q
P→Q
0
0
1
0
1
1
1
0
0
1
1
1
例8 若P：雪是黑色的；Q：太阳从西边升起；
R：太阳从东边升起。则P→Q和P→R所表示的命题都是真的.
例9 将命题“如果我得到这本小说，那么我今夜
就读完它。”符号化。
对于上述五种联结词，应注意到： 复合命题的真值只取决于构成它的各原子命题的真 值，而与这些原子命题的内容含义无关。
9
命题符号化
利用联结词可以把许多日常语句符号化。基本步骤如下：

联结词
用于组合命题的逻辑运算 符，如“与”、“或”、 “如“析取三段论”、“假 言推理”等。
命题演算系统的应用
逻辑推理
命题演算系统是逻辑推理 的基础，可用于解决各种 逻辑推理问题，如逻辑谜 题、推理题目等。
人工智能
命题演算系统在人工智能 领域中有着广泛的应用， 如知识表示、自然语言处 理、智能搜索等。
在数学中的应用
集合论
集合论中的集合关系可以用命题 逻辑来描述和证明。
离散概率论
离散概率论中的概率推理可以用 命题逻辑来描述和证明。
离散优化
离散优化问题中的约束条件和目 标函数可以用命题逻辑来描述和
求解。
THANKS
03 命题逻辑的基本规则
推理规则
肯定前件式（Modus Ponens）：如 果P→Q为真，且P为真，则可以推出 Q为真。
假言推理（Hypothetical Syllogism ）：如果P→Q为真，且Q→R为真， 则可以推出P→R为真。
否定后件式（Modus Tollens）：如 果P→Q为真，且Q为假，则可以推出 P为假。
02
常见的联结词有“与”、“或” 、“非”、“如果...那么...”等。
联结词的性质
联结词具有逻辑性，能够表达命题之 间的逻辑关系。
不同的联结词具有不同的逻辑性质， 能够表达不同的逻辑关系。
联结词的分类
根据联结词的性质，可以将联结词分为合取、析取、否定等 类型。
合取联结词表示命题之间的同时存在关系，如“与”；析取 联结词表示命题之间的至少存在一个的关系，如“或”；否 定联结词表示命题的否定关系，如“非”。
通过将自然语言转换为命题逻辑形 式，实现自然语言的理解和生成。
在计算机科学中的应用

离散概率分布的定义
离散概率分布是描述随机事件在有限或可数无限的可 能结果集合中发生的概率的数学工具。
离散概率分布的种类
常见的离散概率分布包括二项分布、泊松分布、几何 分布等。
离散概率分布的应用
离散概率分布在统计学、计算机科学、物理学等领域 都有广泛的应用。
参数估计和假设检验
参数估计
参数估计是根据样本数据推断总体参数的过 程，包括点估计和区间估计两种方法。
假设检验
假设检验是用来判断一个假设是否成立的统计方法 ，包括参数检验和非参数检验两种类型。
参数估计和假设检验的应 用
在统计学中，参数估计和假设检验是常用的 数据分析方法，用于推断总体特征和比较不 同总体的差异。
方差分析和回归分析
方差分析
方差分析是一种用来比较不同组数据的平均值是否存在显著差异 的统计方法。
《离散数学讲义》ppt课件
目 录
• 离散数学简介 • 集合论 • 图论 • 离散概率论 • 逻辑学 • 离散统计学 • 应用案例分析
01
离散数学简介
离散数学的起源和定义
起源
离散数学起源于17世纪欧洲的数学研 究，最初是为了解决当时的一些实际 问题，如组合计数和图论问题。
定义
离散数学是研究离散对象（如集合、 图、树、逻辑等）的数学分支，它不 涉及连续的变量或函数。
联结词：如与(&&)、或(||)、非(!)等，用 于组合简单命题。
03
04
命题公式：由简单命题通过联结词组合而 成的复合命题。
命题逻辑的推理规则
05
06
肯定前件、否定后件、析取三段论、合取 三段论等推理规则。
谓词逻辑
个体词
表示具体事物的符号。

联结词与复合命题
1.否定式与否定联结词“”
定义 设p为命题，复合命题 “非p”（或 “p
的 否定”）称为p的否定式，记作p，符号称 作否定联结词，并规定p 为真当且仅当p为 假.
例如：p：10是素数，则p：10不是素数.
2. 合取式与合取联结词“∧” 定义 设p, q为二命题,复合命题“p并且q ”(或
若 p，就 q 只要 p，就 q
p 仅当 q 只有 q 才 p
除非 q, 才 p 或 除非 q, 否则非 p，
当p为假时，p q为真 常出现的错误：分不清充分条件与必要条件！
例1.5 设 p :天冷，q :小王穿羽绒服，
将下列命题符号化
(1) 只要天冷，小王就穿羽绒服.
pq
(2) 因为天冷，所以小王穿羽绒服. (3) 若小王不穿羽绒服，则天不冷.
“p与q ”)称为p与q 的合取式，记作p∧q，∧称 作合取联结词，并规定 p∧q为真当且仅当p 与 q 同时为真.
注意: 描述合取式的灵活性与多样性， 分清简单命题与复合命题.
例1.3 将下列命题符号化.
(1)丁楠既聪明又用功.
(2)丁楠不仅聪明，而且用功.
(3)丁楠虽然聪明，但不用功.
(4)丁楠不是不聪明，而是不用功.
4. 蕴涵式与蕴涵联结词“”
定义 设p, q为二命题，复合命题“如果p,则q” 称作p与q的蕴涵式，记作p q，并称p是蕴涵 式的前件，q为蕴涵式的后件. 称作蕴涵联结 词，并规定，p q为假当且仅当p为真q为假.
p q 的逻辑关系：q 为 p 的必要条件 “如果 p，则 q”的不同表述法很多：
注意感:叹句、祈使句、疑问句都不是命题！
陈述句中的悖论 以及判断结果不惟一确定的也

逻辑运算符“析取”， 与汉语中“或”含义 相当，但有细微的区 别
1.1 命题及联结词
运算符“析取” 与汉语的“或”几乎一致但有 区别：哪些老师讲离散数学？有人回答如下：
(16)“讲离散数学的老师是杨老师或吴老师”， 分解为
“讲离散数学的老师是杨老师”或 “讲离散数学的老师是吴老师”， 这两个原子命题有可能都是对的， 这种“或”称为“可同时为真的或”， 或简称为“可兼或”。 这种“或”表示可表 示为“析取”
1.1 命题及联结词
定义1.4条件:当p是1 ,q是0时,pq为0,即10 为0,其他情况为1。
逻辑运算符“如果…那么”， 如老妈说：“如果期终考了年级前10 名，那么奖励1000元”。 p:期终考了年级前10名 q:奖励1000元 则上面的语句表示为pq。 先考虑值为0即假的情况： 当p为1即“期终考了年级前10”， 且q为0即“没有奖励1000元” 这时老妈的话是假话空话，
这个例题有点不正点！ “郎才当且仅当女貌”，
可以表示为“郎才女貌”
1.2命题公式
对错明确的陈述语句称为命题，其真值t/f 0/1 C运算：加+、减-、乘x、除/、余数%， 命题逻辑：合、析、否定、条件、双条件(版) C语言中用变量x表示某些数，如x*x+x+10是表达式，
命题逻辑中用变量p,q,r表示任意命题，由命题常元与 此类变量所构成表达式，称为“命题公式”。
无论p/q取何值，这两个公式的值，与前面各例 不同，此表是将运算结果写在联结词的下方！
1.3 等值式
定义1.3.1等值： 对于合法的命题公式A、B， 若无论其中的命题变元取何值，A 、B值总相等， 称为两个公式等值，记为AB (边播边板)
目的:
1．掌握离散数学五大核心内容（集合论、数 理逻辑、代数结构、图论、组合数学）的基本概 念、基本理论、基本方法，训练提高学生的概括 抽象能力、逻辑思维能力、归纳构造能力，培养 学生严谨、完整、规范的科学态度和学习思维习 惯。

20
例1.6求下列复合命题的真值1 0(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连续.
1
0 0
21
以上给出了5个联结词：, , , , ，组成 一个联结词集合{, , , , }， 联结词的优先顺序为：, , , , ; ① ② ③ 如果出现的联结词同级，又无括号时，则按从左 到右的顺序运算; 若遇有括号时，应该先进行括 号中的运算.
25
7
例1.1
下列句子中哪些是命题？ 真命题 假命题 真值不确定 疑问句 感叹句 祈使句 悖论 (3)—(7)都不是命题
8
(1) (3)
(4) (5) (6) (7)
2 是无理数. (2) 2 + 5 ＝8.
x + 5 ＞ 3.
你有铅笔吗？ 这只兔子跑得真快呀！ 请不要讲话！ 我正在说谎话.
命题的分类
10
联结词与复合命题
1.否定式与否定联结词“”
定义 设p为命题，复合命题 “非p”（或 “p 的 否定”）称为p的否定式，记作p，符号称
作否定联结词，并规定p 为真当且仅当p为
假.
例如：p：10是素数，则p：10不是素数.
11
2. 合取式与合取联结词“∧” 定 义 设 p, q 为 二 命 题 , 复 合 命 题 “ p 并 且 q ”( 或 “ p 与 q ”) 称为 p 与 q 的合取式，记作 p∧q ，∧ 称 作合取联结词，并规定 p∧q为真当且仅当p 与

逻辑学
逻辑学是一门研究思维形式及思维规律的科学。逻辑规律就 是客观事物在人的主观意识中的反映。 辩证逻辑：以辩证法认识论的世界观为基础的逻辑学。
形式逻辑：对思维的形式结构和规律进行研究的类似于 语法的一门工具性学科。
思维的形式结构包括概念、判断和推理 之间的结构和联系。
概念：思维的基本单元。 判断：通过概念对事物是否具有某
2021/4/22
33
32
小结
命题演算的合式公式 命题的翻译
2021/4/22
33
33
〈概念语言〉：1879年发
表，仅88页。“也许是自
古以来最重要的一部逻辑学
著作”。首次制定了一个现
Leibniz (1646-1746) 代的逻辑系统，包括：命题
演算系统和一阶谓词演算系
统。
Frege (1848-1925)
2021/4/22
33
4
数理逻辑实例
公安人员审查一件盗窃案，己知： 甲或乙盗窃了手机； 若甲盗窃了手机，则作案时间不能发生在午夜前； 若乙的证词正确，则午夜时屋里的灯光未灭； 若乙的证词不正确，则作案时间发生在午夜之前； 午夜时屋里的灯光灭了。
33
16
合取-举例（2）
合取的概念与自然语言中的“与”意义相似，但并不完全相
同P：我们去看电影。
Q：房间里有十张桌子。
上述命题的合取为：
P∧Q：我们去看电影与房间里有十张桌子。
在自然语言中，上述命题是没有意义的，因为P与Q没有内 在联系，但作为数理逻辑中P和Q的合取P∧Q来说，它仍可 成为一个新的命题，只要按照定义，在P、Q分别取真值后， P∧Q的真值也必确定。
这个例子中的“或”字，只表示了习题的近似数目，不 能用联结词“析取”表达，是个原子命题。