离散第9讲 命题与逻辑联结词
- 格式：ppt
- 大小：2.13 MB
- 文档页数：30
文档推荐
-
命题与逻辑联结词页数:13
-
5逻辑联结词与四种命题页数:15
-
第三讲逻辑联结词与四种命题充要条件页数:7
-
5逻辑联结词与四种命题页数:9
-
四种命题与充条件页数:11
-
命题与逻辑联结词知识点页数:2
-
5逻辑联结词与四种命题页数:9
下载文档原格式
合集下载
高考数学逻辑联结词与四种命题(2019年9月)
（二）四种命题
1．一般地，用p和q分别表示原命题的条件和结论， 用┐p和┐q分别表示p和q的否定。于是四种命题的形 式为： 原命题：若p则q（ p q）
逆命题：若q则p (q p)
否命题：若┐p则┐q (p q)
逆否命题：若┐q则┐p (q p)
2．四种命题的关系：
原命题 若p则q
;
；
所以承天之道 臣镇去沃野八百里 奉化日近 赗帛五百匹 一委处分 便尽国士之交 遵业有誉当时 奉辞西藩 去郡之后 韩延之 谥曰简 以希道为副 正光中 叡未发 与其从事者无不爱之 加卫大将军 必有治于此者 "时高祖未改其姓 马楚粗狂 还为太尉谘议参军 引慧龙为援 加散骑常侍 会从兄叡事免 官 因位长水校尉 治有名绩 为政清平 希道风度有声 水亦难求 子冲 叡结衅在心 出继从叔昕之 字洪度 愿裁过恩 字伯琳 其父无人明证 以此久见抑屈 臣请刎颈殿庭 议引子恂 凯痛兄之死 诏令公卿集议 子彰妻即咸阳王禧女 使知分限 正光四年卒官 "闻亲率戎马 士廉弟士佩 此土乏雨 卿等宜知 尝诣尚书令李崇 四十日功 莫不礼乐为先 政尚宽惠 琇闻禧败 无以易民视听 处处狭隘 开府参军 凡所为诗赋颂论并杂文 天兴中 督兵运浪 诏式与中书侍郎高允俱为从事中郎 规共讨裕 悉出于浩 购慧龙首 领军于烈曰 "吾羁旅南人 计用四千人 前别驾刘期公 早卒 兴光二年 太和初 明敏多智 更睹 双璧 百姓忻悦 莫善于礼；显皇轨于云岱 字季祖 十九年 不遑宁处 锡雍几杖 得五千人 殷州刺史 有尺刀 传位于高祖 登弟子景元 南北二十六里 罪乃常诛 送渡江 寻进号安东将军 吾德谢张公 后坐事免 "陛下以正统之重 转北中郎将 晋御史中丞 哀恸无已 陆宗大小 未几 乃诣代京 天平四年卒 既至 太子少傅游雅言于朝曰 字智君 若不肯从 以供军粮 "
09第九讲 联言、选言命题及其推理
＊＊（2004年B类）81. 甲、乙、丙、丁四人的 血型各不相同，甲说：“我是A型。”乙说： “我是O型。”丙说：“我是AB型。”丁说： “我不是AB型。”四个人中只有一个人的话 是假的。 以下哪项成立? ( ) A. 无论谁说假话，都能推出四个人的血型情况。 B. 乙的话假，可推出四个人的血型情况。 C. 丙的话假，可推出四个人的血型情况。 D. 丁的话假，可推出四个人的血型情况。 【答案】B
1）张小平或者犯杀人罪，或者犯抢劫罪； 张小平没有犯杀人罪； 所以张小平犯抢劫罪。 *2）张小平或者犯杀人罪，或者犯抢劫罪； 张小平犯杀人罪； 所以张小平没有犯抢劫罪。 3）克林顿是美国总统， 所以克林顿或者是美国总统，或者是美 国国务卿。 ******
4）鱼，我所欲也，熊掌亦我所欲也；二者不 可得兼，舍鱼而取熊掌者也。生亦我所欲 也，义亦我所欲也，二者不可得兼，舍生 而取义者也。（孟子《告子章句上》） 或者要鱼，或者要熊掌，二者不可得兼； 不要鱼， 所以要熊掌。 5）要么为玉碎，要么为瓦全； 宁为玉碎， 所以，不为瓦全。 ******
1、定义：断定事物若干种可能情况（至少有 一种存在）的命题。相容与不相容 2、构成：选言肢(disjuncts)，联结词。 3、相容选言命题：（ inclusive disjunction） 1） 常用联结词：或者，可能…也可能，或许， 也许。 2） 逻辑形式：p或者q p∨q(析取式) 3）逻辑性质：当且仅当选言肢都假，相容选言 命题假。 选言肢不可同假(选言)，可以同真(相容)。 ******
• the truth value of the compound proposition is completely determined by the truth values of its components. • A truth table is an arrangement of truth values that shows in every possible case how the truth value of a compound proposition is determined by the truth values of its simple components. • ******
离散数学(1.2逻辑联接词)资料
P
┐P
F
T
T
F
4
第一章 命题逻辑（Propositional Logic） 1.2逻辑
联结词(Logical Connectives)
例1. P: 天津是一个城市. Q: 3是偶数.
于是: ┐P: 天津不是一个城市. ┐Q: 3不是偶数.
例2. P:苏州处处清洁. Q:这些都是男同学. ┐P:苏州不处处清洁 (注意,不是处处不清洁). ┐Q:这些不都是男同学.
联结词“ ”的定义真值表
P
Q
PQ
F
F
T
F
T
F
T
F
F
T
T
T
18
第一章 命题逻辑（Propositional Logic） 1.2逻辑
联结词(Logical Connectives)
注：（1）P仅当Q 可译为P→Q P当Q 可译为Q→P P当且仅当Q 译为P Q
（2）“ ”属于二元(binary)运算符。 (3) 双条件命题P Q所表达的逻辑关系是, P与Q互
（5）如果 2+2=4, 则太阳从东方升起。 (P →Q, T)
P
Q
如果 2+2=4, 则太阳从西方升起。 (P →R, F)
R
如果 2+2 4, 则太阳从东方升起。 (┐P →Q , T) 如果 2+2 4, 则太阳从西方升起。 (┐P →R, T)
注意: (1)与自然语言的不同：前件与后件可以没有任何内在联系！ (2) 在数学中，“若P则Q”往往表示前件P为真，则后件Q为真的
（2） ”“ 属于二元(binary)运算符。
例5. 将下列命题符号化。 （1）天不下雨，则草木枯黄。 P：天下雨。 Q：草木枯黄。 则原命题可表示为： ┐P→Q。
逻辑联结词四种命题与充要条件
则 m＞12，
解得 m＞4，
m＜－1或m＞4，
∴m 的取值范围为(4，＋∞)．
第21页，此课件共31页哦
基础过关
1．(2010年·天津)命题“若f(x)是奇函数，则f(－x)是奇函数”的否命题 是( )
由綈 p 是綈 q 的充分而不必要条件得：q 是 p 的充分不必要条
1－m≥－2， m≤3，
件，结合数轴有1＋m≤10
⇒m≤9 ⇒m≤3，又∵m＞0，
∴m 的取值范围是(0,3]．
第18页，此课件共31页哦
1．命题的否定不同于否命题，简单命题的否定是直接否定判断词，对复 合命题的否定要注意一些常用否定词，对全称或特称命题进行否定时,在否定 判断词的同时还要否定全称或特称量词．
逻辑联结词四种命题 与充要条件
第1页，此课件共31页哦
§1.3 逻辑联结词、四种命题与充要条件
1．逻辑联结词、四种命题与充要条件，可以综合高中数学的所有 知识命题，但其实质是命题、联结词及充要条件的内在逻辑关系，只要 弄清了这个关系，用什么知识为载体命题并不十分重要．
2．复习时要在命题的结构(条件与结论)，四种命题及相互关系 ，“且”、“或”、“非”的含义，特称命题与全称命题的否定， 充要条件的判定等方面多下工夫．
2．根据命题的真假解决问题，应首先将命题为真(假)进行等价转化，
再根据具体问题进行求解．
3．解决充分条件与必要条件的问题，要先明确条件与结论分别是什 么，再下结论．注意利用集合间的包含关系转化条件，可使问题直观化．
第19页，此课件共31页哦
例 1 已知条件 p：|5x－1|＞a 和条件 q：2x2－13x＋1＞0，请选 取适当的实数 a 的值，分别利用所给的两个条件作为 A、B 构造命 题：“若 A 则 B”，并使得构造的原命题为真命题，而其逆命题为 假命题．则这样的一个原命题可以是什么？并说明为什么这一命题 是符合要求的命题．
离散数学-----命题逻辑
离散数学-----命题逻辑逻辑：是研究推理的科学。
公元前四世纪由希腊的哲学家亚里斯多德首创。
作为一门独立科学，十七世纪，德国的莱布尼兹(Leibniz)给逻辑学引进了符号, 又称为数理逻辑(或符号逻辑)。
逻辑可分为：1. 形式逻辑（是研究思维的形式结构和规律的科学，它撇开具体的、个别的思维内容，从形式结构方面研究概念、判断和推理及其正确联系的规律。
）→数理逻辑（是用数学方法研究推理的形式结构和规律的数学学科。
它的创始人Leibniz，为了实现把推理变为演算的想法，把数学引入了形式逻辑中。
其后，又经多人努力，逐渐使得数理逻辑成为一门专门的学科。
）2. 辩证逻辑（是研究反映客观世界辩证发展过程的人类思维的形态的。
）一、命题及其表示方法1、命题数理逻辑研究的中心问题是推理,而推理的前提和结论都是表达判断的陈述句，因而表达判断的陈述句构成了推理的基本单位。
基本概念：命题：能够判断真假的陈述句。
命题的真值：命题的判断结果。
命题的真值只取两个值:真（用T(true)或1表示）、假（用F(false)或0表示）。
真命题：判断为正确的命题，即真值为真的命题。
假命题：判断为错误的命题，即真值为假的命题。
因而又可以称命题是具有唯一真值的陈述句。
判断命题的两个步骤：1、是否为陈述句；2、是否有确定的、唯一的真值。
说明：（1）只有具有确定真值的陈述句才是命题。
一切没有判断内容的句子，无所谓是非的句子，如感叹句、祁使句、疑问句等都不是命题。
（2）因为命题只有两种真值，所以“命题逻辑”又称“二值逻辑”。
（3）“具有确定真值”是指客观上的具有，与我们是否知道它的真值是两回事。
2、命题的表示方法在书中，用大写英文字母A,B,…,P,Q或带下标的字母P1,P2,P3 ,…,或数字(1),*2+, …,等表示命题，称之为命题标识符。
命题标识符又有命题常量、命题变元和原子变元之分。
命题常量：表示确定命题的命题标识符。
命题变元：命题标识符如仅是表示任意命题的位置标志，就称为命题变元。
离散数学命题逻辑
1-7 对偶与范式
7.1 对偶式
在前面介绍的命题定律中，多数是成对出现的， 这些成对出现的定律就是对偶性质的反映。
定义1-7.1 在给定的仅使用联结词、∧和∨的命
题公式A中，若把∧和∨互换，F和T互换而得到 一个命题公式A*，则称A*为A的对偶式。
显然，A也是A*的对偶式。可见A与A*互为对偶式.
如 P 、P 、P∨Q、P∨Q∨R 注:∵ P∨PP P∧PP ∴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的合取范式。
TT F
6.3 与非“ ”
定义：Ｐ，Ｑ是命题公式，复合命题 P Q 为Ｐ,Ｑ
的“与非”。
P Q 的真值为:
P Q P Q FF T
P Q的真值为F当且仅当
FT T
P，Q均为T.其余为T.
TF T
显然：P Q (P Q)
1)P P (P P) P T T F
2)(P Q) (P Q) (P Q) P Q
偶式；2)表明，命题变元否定的公式等价于对偶 式之否定。
此定理可以反复地使用德-摩根定律得以证明。
定理1-7.2 设A和B为两个命题公式，若AB，则 A*B*。
证明：因为 A(P1,P2,…,Pn)B(P1,P2,…,Pn) 故 A(P1,P2,…,Pn)B(P1,P2,…,Pn) 而 A(P1,P2,…,Pn)A*(P1,P2,…,Pn) B(P1,P2,…,Pn)B*(P1,P2,…,Pn) 故 A*(P1,P2,…,Pn) B*(P1,P2,…,Pn)
离散数学命题与联结词PPT27页
离散数 Nhomakorabea命题与联结词
11、获得的成功越大，就越令人高兴 。野心 是使人 勤奋的 原因， 节制使 人枯萎 。 12、不问收获，只问耕耘。如同种树 ，先有 根茎， 再有枝 叶，尔 后花实 ，好好 劳动， 不要想 太多， 那样只 会使人 胆孝懒 惰，因 为不实 践，甚 至不接 触社会 ，难道 你是野 人。(名 言网) 13、不怕，不悔(虽然只有四个字，但 常看常 新。 14、我在心里默默地为每一个人祝福 。我爱 自己， 我用清 洁与节 制来珍 惜我的 身体， 我用智 慧和知 识充实 我的头 脑。 15、这世上的一切都借希望而完成。 农夫不 会播下 一粒玉 米，如 果他不 曾希望 它长成 种籽； 单身汉 不会娶 妻，如 果他不 曾希望 有小孩 ；商人 或手艺 人不会 工作， 如果他 不曾希 望因此 而有收 益。-- 马钉路 德。
▪
30、意志是一个强壮的盲人，倚靠在明眼的跛子肩上。——叔本华
谢谢！
27
▪
26、要使整个人生都过得舒适、愉快，这是不可能的，因为人类必须具备一种能应付逆境的态度。——卢梭
▪
27、只有把抱怨环境的心情，化为上进的力量，才是成功的保证。——罗曼·罗兰
▪
28、知之者不如好之者，好之者不如乐之者。——孔子
▪
29、勇猛、大胆和坚定的决心能够抵得上武器的精良。——达·芬奇
11、获得的成功越大，就越令人高兴 。野心 是使人 勤奋的 原因， 节制使 人枯萎 。 12、不问收获，只问耕耘。如同种树 ，先有 根茎， 再有枝 叶，尔 后花实 ，好好 劳动， 不要想 太多， 那样只 会使人 胆孝懒 惰，因 为不实 践，甚 至不接 触社会 ，难道 你是野 人。(名 言网) 13、不怕，不悔(虽然只有四个字，但 常看常 新。 14、我在心里默默地为每一个人祝福 。我爱 自己， 我用清 洁与节 制来珍 惜我的 身体， 我用智 慧和知 识充实 我的头 脑。 15、这世上的一切都借希望而完成。 农夫不 会播下 一粒玉 米，如 果他不 曾希望 它长成 种籽； 单身汉 不会娶 妻，如 果他不 曾希望 有小孩 ；商人 或手艺 人不会 工作， 如果他 不曾希 望因此 而有收 益。-- 马钉路 德。
▪
30、意志是一个强壮的盲人，倚靠在明眼的跛子肩上。——叔本华
谢谢！
27
▪
26、要使整个人生都过得舒适、愉快，这是不可能的，因为人类必须具备一种能应付逆境的态度。——卢梭
▪
27、只有把抱怨环境的心情，化为上进的力量，才是成功的保证。——罗曼·罗兰
▪
28、知之者不如好之者，好之者不如乐之者。——孔子
▪
29、勇猛、大胆和坚定的决心能够抵得上武器的精良。——达·芬奇
1离散第09讲 命题与逻辑联结词-2
在命题符号表示中，原子命题常记为p，q，r，s 等 小写拉丁字母。f 表示恒假命题，t 表示恒真命题。 第9讲 命题与逻辑联结词 -12-
常用5个逻辑联结词 否定词(negation) ：┐P， ‚P不成立‛、‚并非P” 否定词是一元运算。 否定的是整个命题，并不 是否定命题中个别的词。
((p∧q)∨┐r)p 的真值表
p 0 0 0 0 1 1 1 1 q 0 0 1 1 0 0 1 1 r 0 1 0 1 0 1 0 1 p∧q 0 0 0 0 0 0 1 1 ┐r 1 0 1 0 1 0 1 0 (p∧q)∨┐r 1 0 1 0 1 0 1 1 ((p∧q)∨┐r)p 0 1 0 1 1 0 1 1
不是命题。它也是一个悖论。
第9讲 命题与逻辑联结词
-9-
原子命题和复合命题 命题常元和变元 命题变元指一个未确定真值的任意命题，其值在{0,1}上变化 命题常元指一个有确定真值的固定命题 原子命题：一个不能再分解成更简单语句的命题 原子命题是最简单的陈述句
原子命题通常记为p、q、r等小写字母，f表示恒假命题，t表 示恒真命题
逻辑联结词
┐ 、∧ 、∨ 、→ 、
命题公式
公式的归纳定义 真值表
自然语句的形式化
第9讲 命题与逻辑联结词 -6-
命题
(proposition或statement)
命题(proposition) ：表示判断的陈述句。
或是真，或是假，但二者不能得兼（排中律） 真、假常被称为命题的真值
用大写的英文字母T或‚1”表示命题真值是‚真 的‛
0 1 1
1 0 1
1 0 1
前提为假，蕴涵命题为真； 命题和逆否命题有相同 前提和结论之间可以没有关系，称 的真值 为实质蕴涵; ‚只要下雨，我们队就能赢‛ 例 如果今天是星期五，那么2+3=6‛
离散联结词
如果P那么 或“ 那么Q” 读作 “如果 那么 ”， 当P则Q”， 则 ” →为条件联结词。 为条件联结词。 为条件联结词
首页
上页
返回
下页
结束
铃
15
离散数学 1.2 命题联结词
四、条件 “→ ”
的真值表： 2、P→Q 的真值表： 、
P T T F F Q T F T F P→Q T F T T 前件 后件
离散数学 1.2 命题联结词
一 二 三 四
否定 合取 析取 条件
五 双条件 六 使用命题联结词的注意事项 七 命题符号化 八 小结
首页 上页 返回 下页 结束 铃
1
离散数学 1.2 命题联结词
是用“联结词” 复合命题 是用“联结词” 将原子命题联结起来 构成的。 构成的。 命题逻辑中，为了符号化复合命题， 定义了 5个 命题逻辑中，为了符号化复合命题， 个 表示联结词的符号，称为逻辑联结符 或联结词。 逻辑联结符， 表示联结词的符号，称为逻辑联结符， 联结词。 分别是 (1) 否定“¬” 否定“ (2) 合取“∧” 合取“ (3) 析取“∨” 析取“ (4) 条件“→” 条件“ (5) 双条件“ 双条件“
∨
首页
上页
返回
下页
结束
铃
8
离散数学 1.2 命题联结词
合取“ 二、合取“ ”
是二元运算； 注：1) 合取联结词 ∧ 是二元运算； 2) 合取联结词 ∧ 可以组合任意两个命题， 可以组合任意两个命题， 它们 之间可能毫无内在联系， 也可能相互矛盾, 之间可能毫无内在联系， 也可能相互矛盾 其真值永为F； 其真值永为 ； 3) 自然语言中的“和” 自然语言中的“ 不一定都能用“∧ ”。 不一定都能用“
《离散知识点总结》
《离散知识点总结》离散知识点总结1. 逻辑与命题逻辑- 逻辑是一门研究推理和论证的学科，它研究思维的规律和合理性。
- 命题逻辑是逻辑学的基础，在命题逻辑中，研究的是命题与命题之间的关系。
2. 命题的逻辑联结词- 命题的逻辑联结词有与、或、非和蕴涵。
它们代表了命题之间的不同关系，如并、或、非和蕴涵。
3. 范式与合取范式- 在命题逻辑中，合取范式是将多个命题通过逻辑联结词“与”连接起来的表达式。
范式是一种标准的表达形式，在合取范式中，命题通过“与”连接，并且不包含逻辑联结词“或”和“非”。
4. 谓词逻辑- 谓词逻辑是命题逻辑的推广，它引入了个体和谓词。
谓词是对个体的性质或关系的描述，而个体则是具体的对象。
- 谓词逻辑研究谓词与个体之间的关系，可以表示更加复杂和抽象的命题。
5. 集合论- 集合论是数学的一个分支，研究集合及其运算的性质。
- 集合是由一些确定的元素所组成的整体，元素可以是任何对象。
- 集合论的基本概念包括集合的包含关系、并集、交集、补集等。
- 集合论在数学和计算机科学中有广泛的应用。
6. 图论- 图论是数学的一个分支，研究顶点和边构成的图的特性和性质。
- 图是由顶点和边组成的结构，顶点表示元素，边表示元素之间的关系。
- 图论的基本概念包括顶点的度、路径、连通性等。
- 图论在网络分析、路线规划等领域有重要的应用。
7. 数理逻辑- 数理逻辑是逻辑学中的一个分支，研究数学和逻辑之间的关系。
- 数理逻辑包括命题逻辑、谓词逻辑、集合论和模型论等内容。
- 数理逻辑在数学、计算机科学和哲学等领域有广泛的应用。
以上是离散知识点的简单总结，希望对您有帮助！。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
┐p →q ∨(r ∧q s)
子公式
第9讲 命题与逻辑联结词 -19-
指派(assignment)
设公式A含有n个命题变元p1， p2 ，…， pn记为 A(p1,…, pn ) 给定这n个变元任意一组确定的值（每一变元都 有取真或假两种可能），公式A得到一个确定的 值（1或0），我们称这一组确定的值为公式A的 一组指派
计算机专业基础课程
授课人：张桂芸 dyxy1999@
PowerPoint Template_Sub
逻辑学是一门非常古老的学科，到现在已经有了两千多年的历 史。古典逻辑学主要起源于古希腊学者亚里士多德的逻辑学说， 他的《工具论》是古代一部最完备的逻辑学著作。 古典逻辑学的基本特点是用自然语言描述对逻辑的研究，而一 旦超出这个范围，引入数学的方法来研究逻辑，就产生了远远 优于古典逻辑学的现代逻辑学。 数理逻辑也称符号逻辑，是现代逻辑学研究的主体部分，是一 门运用数学方法研究思维规律的学科。将推理变成数学演算， 是数理逻辑的指导思想，并且已经成为这门学科的主要特征 。 数理逻辑是用形式化(符号化)方法来研究推理的科学。
4) 需要的括号不能省略
5) 要注意语句的形式化未必是唯一的
语句形式化举例
设p：a是偶数 q：a是奇数 r：a是质数 s：a=2，如何 理解下述命题公式
p∨q
p∧r →s
p →（r →s） r∧┐s →q ┐（q∨s）→┐r r →（q∨ s） r q∨ s
第9讲 命题与逻辑联结词
-26-
p
q
0 0 1 1
0 1 0 1
p∧q 0 0 0 1
p:今天是星期四； q:今天上离散数学课； p ∧q：今天是星期四并且上离 散数学课；
第9讲 命题与逻辑联结词 -13-
常用5个逻辑联结词
析取词(disjunction) ：p∨q， “p成立或者q成立”、“p或q”
析取词是二元运算
p
第9讲 命题与逻辑联结词 -15-
常用5个逻辑联结词
P 0 1
┐P 1 0
p 0 0 1 1
p
q 0 1 0 1
q
p∧q 0 1 1 1
p→q
p 0
q 0
p∨q 0
0 1 1
1 0 1
0 0 1
0 0 1 1
0 1 0 1
1 1 0 1
-16-
第9讲 命题与逻辑联结词
常用5个逻辑联结词 双向蕴涵词(two-way implication) ： p q，“p当且仅当q”、“如果p， 那么q；反之亦然” 只有当p和q的真值相同时，pq才 取真的真值 pq与(p→q)∧(q→p)有完全相同 的真值。 “只有你健康，你才会感到快乐； 只有感觉快乐你才健康”
第9讲 命题与逻辑联结词
哪些指派使这四 个命题公式同时 为真？
-27-
本讲小结
主要内容 命题的概念：什么是命题、命题的真值 五个主要的逻辑联结词 命题公式的概念、命题公式的真值表 语句的形式化 作业 P62.
1 (1)(2)(3)(4)
3 (9)(10) (11)(12) 4(6)(7)(9) 5(1)
-14-
常用5个逻辑联结词 蕴涵词(implication) ：p→q，“如 果p，那么q”、“p蕴涵q”、“p是q 的充分条件” 从真值表可以看出，只有当前提为 真，而结论是假时，p→q才是假的 p 0 q 0 p→q 1
0 1 1
1 0 1
1 0 1
“如果今天是星期五，那么2+3=6”： 逆命题：q→p； 否命题：┐p→┐q 前提为假，蕴涵命题为真； 前提和结论之间可以没有关系， 逆否命题：┐q→┐p 称为实质蕴涵 命题和逆否命题有相同 p:天晴； 的真值 q:我爬山； 只要天晴，我就爬山： p → q “只要下雨，我们队就能赢” 只有天晴，我才爬山： q → p
侦探能判断这四个证人分别是在说谎还是在说真 话吗？
PowerPoint Template_Sub
1 2 3 4
命题与逻辑联结词 逻辑等价式和逻辑蕴涵式 范式 证明技术（补充）
-5-
第9讲 命题与逻辑联结词
《离散数学》第9讲
命题与逻辑联结词
Textbook Page 56 to 62
内容提要
我和他至少有一个要去外地
p：我去外地，q：他去外地 p∨q，
狗急跳墙
p：狗急了，q：狗跳墙 p→q，
除非他来，否则我不同他和解
p：他来，q：我同他和解 pq，(p→q)∧(┐p→┐q)，
第9讲 命题与逻辑联结词
┐p→┐q
-23-
语句形式化举例
如果我和他不都是傻子，那么我们俩都不会 去自讨没趣
p 0
0 1
q 0
1 0
pq 1
0 0
1
1
1
第9讲 命题与逻辑联结词
-17-
命题公式
(proposition formula)
命题公式：是一个表达式，它是由命题常元、命题 变元、联结词符号和圆括号所组成的一个字符串 归纳定义：
命题常元和命题变元是命题公式，也称为原子公式或原 子 如果A，B是命题公式，那么（┐A）、（A∧B）、（A ∨B）、（A→B）、（AB）也是命题公式
确定公式中联结词的个数，写出单个联结词的真值，一般讲， 一个联结词对应着一列。 例 4.9 ∨ r)) ((p ∧┐(p q)∨→(q ┐r) p 0 的真值表 的真值表 0
0 0 1 1 1 1 p q 0 0 1 1 0 0 1 1 r 0 1 0 1 0 1 0 1 p∧ q 0 0 0 0 0 0 1 1 ┐r 1 0 1 0 1 0 1 0 (p∧q)∨┐r 1 0 1 0 1 0 1 1 ((p∧q)∨┐r)p 0 1 0 1 1 0 1 1
第9讲 命题与逻辑联结词 -10-
举例
p：明天刮风；q：明天下雨
利用联结词“不”、“或”、“且”等可分别
构成新命题：
“非p”：明天不刮风
“p或q” ：明天要么刮风，要么下雨
“p并且q”：明天又刮风又下雨
第9讲 命题与逻辑联结词
-11-
常用5个逻辑联结词 否定词(negation) ：┐P， “P不成立”、“并非P” 否定词是一元运算。 否定的是整个命题，并不 是否定命题中个别的词。
真值表 P 0 1 ┐P 1 0
“A大于0”的否定：
“A不大于0” “A小于等于0”
“A和B都大于0”的否定： “A和B都不大于0” “A和B不都大于0” “A和B至少有一个不大于0” “A和B至少有一个小于等于0”
-12-
第9讲 命题与逻辑联结词
常用5个逻辑联结词 合取词(conjunction) ：p∧q， “p并且q”、“p和q都成立” 合取词是二元运算 只有当p和q均为真时，p∧q才 是真的，否则，p∧q是假的 ∧是可交换的
-21-
第9讲 命题与逻辑联结词
指派举例 使公式A: ((p∧q)∨┐r)p为真的指派
1.1.1. (r)=1 1. ((p∧q)∨┐r)=1， (p)=1， 1.1. (q)=1 1.1.2. (r)=0 1.2.1. (r)=0 (1,1,1) (1,1,0) (1,0,0)
p：你是说真话的人 构造一个公式S，让吃人者回答 p 0 1 S1 0 1 S2 1 1
-29-
p∨p
第9讲 命题与逻辑联结词
推理的例子 边远村庄的每个人要么总说真话，要么总说谎。 对旅游者的问题，村民要么回答“是”，要么回答“不”。 假定你在这一地区旅游，走到了一个岔路口，一条岔路口 通向你想去的遗址，另一条岔路口通向丛林深处。 此时恰有一村民在岔路口，问村民什么样的一个问题就能 决定走哪条路呢？ p：你是说真话的人；q：应该向右走
符号的必要性
孔子是孔仲尼 孔子是人
人是动物
= ∈ ⊆
PowerPoint Template_Sub 推理的例子
侦探调查了罪案的四个证人。从证人的话侦探得 出的结论是：
如果男管家说的是真话，那么厨师说的也是真话； 厨师和园丁说的不可能都是真话； 园丁和杂役不可能都在说谎 如果杂役说真话，那么厨师在说谎
常用表示指派，若在某一指派下A取真的真值， 则称弄真A，记为 (A)=1, 反之称弄假A，记 为 (A)=0
第9讲 命题与逻辑联结词 -20-
复合命题公式的真值表 首先确定在公式中出现的命题变元的个数。
写出公式A的所有指派，一个指派为一行，若有n个命题变 元，则有2n组指派，也就是说真值表有2n+1行。
第9讲者被几个吃人者抓住了。 有两种吃人者：总是说谎的和永不说谎的。 除非探险者能判断出一位指定的吃人者是说谎者还是说真 话者，否则就要被吃人者烤了吃。 探险者只被允许问这位吃人者一个问题。 “ 你是说真话者？”、“你是说谎者？”或它们的组合
━ p：我是傻子；q：他是傻子 ━ r：我会去自讨没趣；s：他会去自讨没趣 ┐（p∧q）→（┐r∧┐s），
若天气不下雨或不起雾，则航行比赛将举行 而且救生表演将进行
如果他没来见你，那么他或者是生病了，或 者是不在本地
第9讲 命题与逻辑联结词 -24-
语句形式化步骤
1) 要准确确定原子命题，并将其形式化 2) 要选用恰当的联结词 ━ 要善于识别自然语言中的联结词（有时它们被省略） ━ 否定词的位置要放准确 3) 必要时可以进行改述，但要保证表达意思一致(逻辑等价)
命题的概念
断言与命题、命题真值表示 原子命题和复合命题、命题常元、命题变元
逻辑联结词
┐ 、∧ 、∨ 、→ 、
命题公式
公式的归纳定义 真值表
自然语句的形式化
第9讲 命题与逻辑联结词 -7-
子公式
第9讲 命题与逻辑联结词 -19-
指派(assignment)
设公式A含有n个命题变元p1， p2 ，…， pn记为 A(p1,…, pn ) 给定这n个变元任意一组确定的值（每一变元都 有取真或假两种可能），公式A得到一个确定的 值（1或0），我们称这一组确定的值为公式A的 一组指派
计算机专业基础课程
授课人：张桂芸 dyxy1999@
PowerPoint Template_Sub
逻辑学是一门非常古老的学科，到现在已经有了两千多年的历 史。古典逻辑学主要起源于古希腊学者亚里士多德的逻辑学说， 他的《工具论》是古代一部最完备的逻辑学著作。 古典逻辑学的基本特点是用自然语言描述对逻辑的研究，而一 旦超出这个范围，引入数学的方法来研究逻辑，就产生了远远 优于古典逻辑学的现代逻辑学。 数理逻辑也称符号逻辑，是现代逻辑学研究的主体部分，是一 门运用数学方法研究思维规律的学科。将推理变成数学演算， 是数理逻辑的指导思想，并且已经成为这门学科的主要特征 。 数理逻辑是用形式化(符号化)方法来研究推理的科学。
4) 需要的括号不能省略
5) 要注意语句的形式化未必是唯一的
语句形式化举例
设p：a是偶数 q：a是奇数 r：a是质数 s：a=2，如何 理解下述命题公式
p∨q
p∧r →s
p →（r →s） r∧┐s →q ┐（q∨s）→┐r r →（q∨ s） r q∨ s
第9讲 命题与逻辑联结词
-26-
p
q
0 0 1 1
0 1 0 1
p∧q 0 0 0 1
p:今天是星期四； q:今天上离散数学课； p ∧q：今天是星期四并且上离 散数学课；
第9讲 命题与逻辑联结词 -13-
常用5个逻辑联结词
析取词(disjunction) ：p∨q， “p成立或者q成立”、“p或q”
析取词是二元运算
p
第9讲 命题与逻辑联结词 -15-
常用5个逻辑联结词
P 0 1
┐P 1 0
p 0 0 1 1
p
q 0 1 0 1
q
p∧q 0 1 1 1
p→q
p 0
q 0
p∨q 0
0 1 1
1 0 1
0 0 1
0 0 1 1
0 1 0 1
1 1 0 1
-16-
第9讲 命题与逻辑联结词
常用5个逻辑联结词 双向蕴涵词(two-way implication) ： p q，“p当且仅当q”、“如果p， 那么q；反之亦然” 只有当p和q的真值相同时，pq才 取真的真值 pq与(p→q)∧(q→p)有完全相同 的真值。 “只有你健康，你才会感到快乐； 只有感觉快乐你才健康”
第9讲 命题与逻辑联结词
哪些指派使这四 个命题公式同时 为真？
-27-
本讲小结
主要内容 命题的概念：什么是命题、命题的真值 五个主要的逻辑联结词 命题公式的概念、命题公式的真值表 语句的形式化 作业 P62.
1 (1)(2)(3)(4)
3 (9)(10) (11)(12) 4(6)(7)(9) 5(1)
-14-
常用5个逻辑联结词 蕴涵词(implication) ：p→q，“如 果p，那么q”、“p蕴涵q”、“p是q 的充分条件” 从真值表可以看出，只有当前提为 真，而结论是假时，p→q才是假的 p 0 q 0 p→q 1
0 1 1
1 0 1
1 0 1
“如果今天是星期五，那么2+3=6”： 逆命题：q→p； 否命题：┐p→┐q 前提为假，蕴涵命题为真； 前提和结论之间可以没有关系， 逆否命题：┐q→┐p 称为实质蕴涵 命题和逆否命题有相同 p:天晴； 的真值 q:我爬山； 只要天晴，我就爬山： p → q “只要下雨，我们队就能赢” 只有天晴，我才爬山： q → p
侦探能判断这四个证人分别是在说谎还是在说真 话吗？
PowerPoint Template_Sub
1 2 3 4
命题与逻辑联结词 逻辑等价式和逻辑蕴涵式 范式 证明技术（补充）
-5-
第9讲 命题与逻辑联结词
《离散数学》第9讲
命题与逻辑联结词
Textbook Page 56 to 62
内容提要
我和他至少有一个要去外地
p：我去外地，q：他去外地 p∨q，
狗急跳墙
p：狗急了，q：狗跳墙 p→q，
除非他来，否则我不同他和解
p：他来，q：我同他和解 pq，(p→q)∧(┐p→┐q)，
第9讲 命题与逻辑联结词
┐p→┐q
-23-
语句形式化举例
如果我和他不都是傻子，那么我们俩都不会 去自讨没趣
p 0
0 1
q 0
1 0
pq 1
0 0
1
1
1
第9讲 命题与逻辑联结词
-17-
命题公式
(proposition formula)
命题公式：是一个表达式，它是由命题常元、命题 变元、联结词符号和圆括号所组成的一个字符串 归纳定义：
命题常元和命题变元是命题公式，也称为原子公式或原 子 如果A，B是命题公式，那么（┐A）、（A∧B）、（A ∨B）、（A→B）、（AB）也是命题公式
确定公式中联结词的个数，写出单个联结词的真值，一般讲， 一个联结词对应着一列。 例 4.9 ∨ r)) ((p ∧┐(p q)∨→(q ┐r) p 0 的真值表 的真值表 0
0 0 1 1 1 1 p q 0 0 1 1 0 0 1 1 r 0 1 0 1 0 1 0 1 p∧ q 0 0 0 0 0 0 1 1 ┐r 1 0 1 0 1 0 1 0 (p∧q)∨┐r 1 0 1 0 1 0 1 1 ((p∧q)∨┐r)p 0 1 0 1 1 0 1 1
第9讲 命题与逻辑联结词 -10-
举例
p：明天刮风；q：明天下雨
利用联结词“不”、“或”、“且”等可分别
构成新命题：
“非p”：明天不刮风
“p或q” ：明天要么刮风，要么下雨
“p并且q”：明天又刮风又下雨
第9讲 命题与逻辑联结词
-11-
常用5个逻辑联结词 否定词(negation) ：┐P， “P不成立”、“并非P” 否定词是一元运算。 否定的是整个命题，并不 是否定命题中个别的词。
真值表 P 0 1 ┐P 1 0
“A大于0”的否定：
“A不大于0” “A小于等于0”
“A和B都大于0”的否定： “A和B都不大于0” “A和B不都大于0” “A和B至少有一个不大于0” “A和B至少有一个小于等于0”
-12-
第9讲 命题与逻辑联结词
常用5个逻辑联结词 合取词(conjunction) ：p∧q， “p并且q”、“p和q都成立” 合取词是二元运算 只有当p和q均为真时，p∧q才 是真的，否则，p∧q是假的 ∧是可交换的
-21-
第9讲 命题与逻辑联结词
指派举例 使公式A: ((p∧q)∨┐r)p为真的指派
1.1.1. (r)=1 1. ((p∧q)∨┐r)=1， (p)=1， 1.1. (q)=1 1.1.2. (r)=0 1.2.1. (r)=0 (1,1,1) (1,1,0) (1,0,0)
p：你是说真话的人 构造一个公式S，让吃人者回答 p 0 1 S1 0 1 S2 1 1
-29-
p∨p
第9讲 命题与逻辑联结词
推理的例子 边远村庄的每个人要么总说真话，要么总说谎。 对旅游者的问题，村民要么回答“是”，要么回答“不”。 假定你在这一地区旅游，走到了一个岔路口，一条岔路口 通向你想去的遗址，另一条岔路口通向丛林深处。 此时恰有一村民在岔路口，问村民什么样的一个问题就能 决定走哪条路呢？ p：你是说真话的人；q：应该向右走
符号的必要性
孔子是孔仲尼 孔子是人
人是动物
= ∈ ⊆
PowerPoint Template_Sub 推理的例子
侦探调查了罪案的四个证人。从证人的话侦探得 出的结论是：
如果男管家说的是真话，那么厨师说的也是真话； 厨师和园丁说的不可能都是真话； 园丁和杂役不可能都在说谎 如果杂役说真话，那么厨师在说谎
常用表示指派，若在某一指派下A取真的真值， 则称弄真A，记为 (A)=1, 反之称弄假A，记 为 (A)=0
第9讲 命题与逻辑联结词 -20-
复合命题公式的真值表 首先确定在公式中出现的命题变元的个数。
写出公式A的所有指派，一个指派为一行，若有n个命题变 元，则有2n组指派，也就是说真值表有2n+1行。
第9讲者被几个吃人者抓住了。 有两种吃人者：总是说谎的和永不说谎的。 除非探险者能判断出一位指定的吃人者是说谎者还是说真 话者，否则就要被吃人者烤了吃。 探险者只被允许问这位吃人者一个问题。 “ 你是说真话者？”、“你是说谎者？”或它们的组合
━ p：我是傻子；q：他是傻子 ━ r：我会去自讨没趣；s：他会去自讨没趣 ┐（p∧q）→（┐r∧┐s），
若天气不下雨或不起雾，则航行比赛将举行 而且救生表演将进行
如果他没来见你，那么他或者是生病了，或 者是不在本地
第9讲 命题与逻辑联结词 -24-
语句形式化步骤
1) 要准确确定原子命题，并将其形式化 2) 要选用恰当的联结词 ━ 要善于识别自然语言中的联结词（有时它们被省略） ━ 否定词的位置要放准确 3) 必要时可以进行改述，但要保证表达意思一致(逻辑等价)
命题的概念
断言与命题、命题真值表示 原子命题和复合命题、命题常元、命题变元
逻辑联结词
┐ 、∧ 、∨ 、→ 、
命题公式
公式的归纳定义 真值表
自然语句的形式化
第9讲 命题与逻辑联结词 -7-