当前位置：文档之家 › 离散数学1.1 命题与联结词

离散数学1.1 命题与联结词

  • 格式：pptx
  • 大小：122.49 KB
  • 文档页数：16

下载文档原格式

  / 16

合集下载

离散数学第一章 命题逻辑

离散数学第一章 命题逻辑

令Q表示：张亮是跳远运动员。
于是命题，张亮可能是跳高或跳远运动员就可以用P∨Q来表示，因为这里的或是可 兼或。 逻辑联结词析取也是个二元运算符。
1.1 命题和联结词
逻辑联结词单条件—“→”
设P是一个命题，Q是一个命题，由联结词→把P、Q连接成P→Q，称P→Q为P、 Q的条件式复合命题，把P和Q分别称为P→Q的前件和后件，或者前提和结论。 P→Q读作“如果P则Q”或“如果P那么Q”。其中P被称为前件，Q被称为为后件。 很多时候联结词→也被称为蕴涵。 P→Q的真值是这样定义的，当且仅当P→Q的前件P的真值为T，后件Q的真值为F
1.1 命题和联结词
逻辑联结词否定—“┓”
设P是一个命题，则联结词┓和命题P构成┓P，┓P为命题P的否定式复合 命题，读作“非P”。联结词┓是自然语言中的“非”、“不”和“没有” 等的逻辑抽象。 其真值是这样定义的，若P的真值是T，那么┓P的真值是F；若P的真值 是F，则┓P的真值是T。命题P与其否定┓P的如表1.1所示。
1.2 合式公式与真值表
例1.4 令P表示：小明现在正在睡觉。
令Q表示：小明现在正在打球。 于是命题，小明现在正在睡觉或者正在打球不能用P∨Q来表示。因为这里自然语言陈述的或是 排斥或，这种意义的或我们用另一个逻辑联结词“异或”“”来表示，后面我们将给出它的 定义。
1.1 命题和联结词
逻辑联结词析取——“∨”
例1.5 将句子“他昨晚做了20或者30道作业题”表示为复合命题。 在此例中，该句子不能被表示成复合命题，因为这里的“或”表示的是近似或者猜 测的意思。 例1.6 令P表示：张亮是跳高运动员。
P F F T T Q F T F T P∧Q F F F T P 0 0 1 1 Q 0 1 0 1 P∧Q 0 0 0 1

离散数学课件第一章(第1讲)

离散数学课件第一章(第1讲)

3)区分“可兼或”与“不可兼或（异或，排斥或）” 析取联结词为可兼或 例如： 灯泡有故障或开关有故障。 今天下雨或打雷。 以上例句均为可兼或。
“不可兼或”表示为：▽ (异或),当P和Q均为“T”时， 则P异或Q为“F”。
P
Q
P▽Q
F
F
F
F
T
T
T
F
T
T
T
F
例： 他通过电视看杂技或到剧场看杂技。 他乘火车去北京或乘飞机去北京。
§1 命题与命题联结词
1 命题
《定义》： 具有唯一值的陈述句叫命题。 讨论定义：
(1)命题的值： 命题值可以是真的，也可以是假的，但不能同时 既为真又为假。
(2)命题的真假值表示： 命题中所有的“真”用“Ｔ ” 或“ 1”表示 命题中所有的“假”用“Ｆ ”或 “0 ”表示。
(3)命题分类： ⅰ)原子命题：一个命题，不能分解成为更简单的命题。
(2) 合取词（“合取”、 “与”运算） 1) 符号 “Λ” 设Ｐ，Ｑ为两个命题，则ＰΛＱ称Ｐ与Ｑ的合取， 读作： “Ｐ与Ｑ” “Ｐ与Ｑ的合取” “Ｐ并且Ｑ”
2) 合取运算真值表
P Q PΛ Q
FF
F
FT
F
TF
F
TT
T
QΛP F F F T
注： ①当且仅当Ｐ和Ｑ的真值均为 Ｔ ，则ＰΛＱ 的真值 为 Ｔ 。否则，其真值为 Ｆ 。
第一篇 数理逻辑
逻辑：通常指人们思考问题，从某些已知条件出发推出合 理的结论的规律。 数理逻辑：用数学方法来研究推理的规律。包括命题逻辑 和谓词逻辑。 数理逻辑研究方法：采用一套数学的符号系统来描述和处 理思维的形式和规律。
第一章 命题逻辑
§1.命题与命题联结词 §2.命题公式与真值表 §3.命题公式的翻译 §4. 等价式与蕴含式 §5.对偶与范 式 §6.命题逻辑的推理理论 §7.其他联结词

离散数学II

离散数学II
b)：相同的运算符，从左到右次序计算时，括号 可省去。
c)：最外层括号可省。 如，(¬((P ∧ ¬Q) ∨R) →((R ∨P)∨Q))
¬(P ∧ ¬Q∨R) →R ∨P∨Q
21/73
1.1 命题与命题联结词
• 例1.3：符号化下列命题。
a)：他既有理论知识又有实践经验 b)：i. 如果明天不是雨夹雪则我去学校
26/73
1.2 公式的解释与真值表
• 原子命题在不指派真值时称为命题变元，而
复合命题由原子命题和联结词构成，可以看 作是命题变元的函数，且该函数的值仍为 “真”或“假”，可以称为真值函数（True Value Function）或命题公式。但不是说原 子命题和联结词的一个随便的组合都可以为 命题公式，我们用递归的方法来定义命题公 式。
• 例，(¬ P∧Q)，(P→(¬P ∧Q)) ，(((P∧Q) ∧(R
∨Q)) ↔(P →R))是命题公式 (P →Q )∧¬ Q)， (P →Q， (¬ P∨Q ∨(R， P∨Q ∨不是命题公式
28/73
1.2 公式的解释与真值表
• 注意：
– 如果G是含有n个命题变元 P1, P2, …,Pn的公式， 通常记为G（P1, …,Pn）或简记为G。
汇集起来的一门综合学科。离散数学的应用遍
及现代科学技术的诸多领域。
–离散数学是随着计算机科学的发展而逐步建立
起来的一门新兴的工具性学科，形成于上上个
世纪七十年代。
2/73
引言
• 课程意义
–离散数学是计算机科学的数学基础，其基本概念、 理论、方法大量地应用在数字电路、编译原理、数 据结构、操作系统、数据库系统、算法设计、人工 智能、计算机网络等专业课程中，是这些课程的基 础课程。

离散数学作业 第一章

离散数学作业 第一章

第一章命题逻辑1.1命题与命题联结词P6.T2.判断下列语句是否为命题，为什么？若是命题判断是原子命题还是复合命题，并把复合命题符号化，要求符号化到原子命题。

（1）他们明天或后天去百货公司。

（2）你能告诉我，我什么时候一定会死吗？你不能！（3）如果这个语句是命题，那么它是一个假命题。

（4）李刚和李春是兄弟。

（5）王海和李春在学习。

（6）只要努力学习，就一定能取得优异成绩。

（7）李春对李刚说：“今天天气真好呀！”（8）你知道这是个真命题还是假命题就请告诉我！（9）王海不是女孩子。

答案解⑴是复合命题。

设p：他们明天去百货公司；q：他们后天去百货公司。

命p∨。

题符号化为q⑵是疑问句，所以不是命题。

⑶是悖论，所以不是命题。

⑷是原子命题。

⑸是复合命题。

设p：王海在学习；q：李春在学习。

命题符号化为p∧q。

⑹是复合命题。

设p：你努力学习；q：你一定能取得优异成绩。

p→q。

⑺不是命题。

⑻不是命题⑼。

是复合命题。

设p：王海是女孩子。

命题符号化为：⌝p。

P7.T4.设p表示命题“天下大雨”，q表示命题“他乘公共汽车上班”，r表示命题“他骑自行车上班”。

请将下列命题符号化。

（1）如果天不下大雨，他乘坐公共汽车或者骑自行车上班。

（2）只要天下大雨，他就乘公共汽车上班。

（3）只要天下大雨，他才乘公共汽车上班。

（4）除非天下大雨，否则他不乘公共汽车上班。

答案解⑴⌝p→(q∨r)。

⑵p→q。

⑶q→p。

⑷q → p。

1.2命题公式及其分类P10.T4.构造下列公式的真值表，并据此说明它是重言式、矛盾式或者仅为可满足式。

（1）p ∨⌝（p ∧q ）。

（2）（p ∧q ）∧⌝（p ∨q ）。

（3）（p →q ）↔（⌝p ↔q ）。

（4）（（p →q ）∧（q →r ））→（p →r ）。

答案解 ⑴设)(q p p A ∧⌝∨=，其真值表如表2-1所示：故)(q p p A ∧⌝∨=为重言式。

⑵设A =(p ∧q )∧⌝(p ∨q )，其真值表如表2-2所示：表2-2故∧∧⌝∨为矛盾式。

《离散数学》--随堂练习(2019)

《离散数学》--随堂练习(2019)

第一章命题逻辑1.1 命题与联结词1、在下面句子中，是命题的是( A )A．明年“五一”是晴天。

B．这朵花多好看呀！。

C．这个男孩真勇敢啊！ D．明天下午有会吗？2. 在下面句子中，是命题的是( B )A．1＋101＝110 B．中国人民是伟大的。

C．这朵花多好看呀！ D．计算机机房有空位吗？3. 在下面句子中( A )是命题A．如果天气好，那么我去散步。

B．天气多好呀！C．x=3。

D．明天下午有会吗？4．下面的命题不是简单命题的是( A )A．3是素数或4是素数 B．2018年元旦下大雪C．刘宏与魏新是同学 D．圆的面积等于半径的平方与π之积5．下面的表述与众不一致的一个是( C )A．P：广州是一个大城市 B．⌝P：广州是一个不大的城市C．⌝P：广州是一个很不小的城市 D．⌝P：广州不是一个大城市6．设，P：他聪明；Q：他用功。

在命题逻辑中，命题：“他既聪明又用功。

”可符号化为：( A )A．P ∧Q B．P→QC．P∨⌝Q D．P∧⌝Q7．设：P ：刘平聪明。

Q：刘平用功。

在命题逻辑中，命题：“刘平不但聪明，而且用功”可符号化为：( A )A．P ∧Q B．⌝P∨QC．P∨⌝Q D．P∧⌝Q8．设：P：他聪明；Q：他用功。

则命题“他虽聪明但不用功。

”在命题逻辑中可符号化为( D )A．P ∧Q B．P→QC．P∨⌝Q D．P∧⌝Q9．设：P：我们划船。

Q：我们跑步。

在命题逻辑中，命题：“我们不能既划船又跑步。

”可符号化为：( B )A．P→Q B．⌝（P ∧Q）C．P∨Q D．P∧⌝Q10．设：P：王强身体很好；Q：王强成绩很好。

命题“王强身体很好，成绩也很好。

”在命题逻辑中可符号化为( D )A．P ∨Q B．P→QC．P∧⌝Q D．P∧Q11．设：P：你努力；Q：你失败。

则命题“除非你努力，否则你将失败。

”在命题逻辑中可符号化为( C )A ．Q →PB ．P → QC ．⌝ P →QD ．Q ∨⌝P12．设：p ：派小王去开会。

《离散数学》课件-第1章命题逻辑

《离散数学》课件-第1章命题逻辑
3
例题 • 判断下列句子中那些是命题？若是命题的，判断其真值。
1. 北京是中国的首都。 2. 2+3=6。 3. 3-x=5。 4. 请关上门。 5. 几点了？
Y真 Y假 N 真值不确定 N 祈使句
6. 除地球外的星球有生物。
N 疑问句
7. 多漂亮的花啊！
Y 真值确定, 但未知
8. 我只给所有不给自己理发的人理发。N 感叹句
p q pq
TT F TF T FT T FF T
23
其它联结词
• 定义1.1.10 设p、q是任意两个命题, p q可表示复合命题“p和q的或非”, 称为或非联结词。命题p q 称为p和q的或非式。当且仅当p和q的真值同时 为假时，p q的真值为真. Nhomakorabea•
p q的真值表
p q pq
TT F TF F FT F FF T
6
联结词
• （一）否定
• 定义1.1.4 设p是一个命题，p表示一个新命题“非p”。命题p 称为p的否定。当且仅当p的真值为假时，p的真值为真。
• p的真值表：
p p
T
F
F
T
• 例如：p：今天是晴天。则 p：今天不是晴天。 • “非”，“不”，“没有”，“无”，“并非”等都可用来表示。
7
联结词• （二）合取
•
p q :电灯不亮是灯泡或线路有问题所致。
•
p：派小王去开会，q：派小李去开会，
•
(p q)(p q): 派小王或小李中的一人去开会
10
联结词
• （四）蕴涵
• 定义1.1.7 设p、q表示任意两个命题, p q 可表示复合命
题“如果p，则q”。当且仅当p的真值为真，q的真值为假时，

离散数学课件 第一章

离散数学课件 第一章
离 散 数 学
主讲教师 李红军 北京林业大学 理学院
BEIJING FOREST UNIVERSITY
教材及参考资料
教材：
1耿素云，屈婉玲，张立昂编著，离散数学，清华大学出版 社, 2008年3月（第4版） 2耿素云,屈婉玲编著.离散数学(修订版).高等教育出版社, 2004年
参考资料：
1 左孝凌编著，离散数学，上海科学技术出版社
1.1 命题与联结词 命题：能判断真假而不是可真可假的陈述句。 命题的真值：命题为真或者假的判断。 真命题：真值为真的命题。 假命题：真值为假的命题。 注：任何命题的真值都是惟一的；
用“1”表示真，用“0”表示假。
例 1.1 ：判断下列句子哪些是命题.
(1)
3 是有理数。
(2) 2是素数。 (3) X＋Y>10。
1 3
m z 1 r m 1
z m 1
1 2
1
3
比赛结束，三位观众各猜对了一半，并且没有并列名次.问：中 国、美国、日本的各排名第几？ 设z1:中国第一;z2 :中国第三；r1:日本第一； m1:美国第一；m2:美国第二； m3:美国第三.
例1的参考答案 m1 z3 1 r1 m3 1 z1 m2 1
对偶原理
A和A*是互为对偶式，P1， P2 ，……Pn是出现在A和A*的原子变元，则 A（P1，…，Pn） A*（ P1，…， Pn） A（ P1，…， Pn） A*（P1，…，Pn）
即公式的否定等值于其变元否定的对偶式。 例：A为PQ，则A*为PQ， 则（PQ） PQ
真值表
将命题公式A在所有赋值下取值情况列成表
试考虑求公式A的真值表的步骤？ 例1 求下列公式的真值表，并求出成真赋值和成假赋值. 1) p(¬ r∧q) 2) (p∨q)(¬ p q)

离散数学知识点总结（1）-命题逻辑

离散数学知识点总结（1）-命题逻辑

离散数学知识点总结（1）-命题逻辑⼀、命题命题：陈述句，有唯⼀真值/⾮真既假（不⼀定知道）简单命题/命题常元：真值确定。

命题变元p：常⽤来表⽰命题。

只有明确表⽰某个命题时才有具体的含意和确定的真值。

命题联结词/命题运算符：否定联结词┐、合取联结词∧、析取联结词∨、蕴含联结词→、与⾮联结词、或⾮联结词p→q：当且仅当p真q假时，p→q为假（因此它和┐p∨q等值）。

即p为假时，p→q必定为真⟷：当且仅当、充要条件、反之亦然⼆、命题公式命题公式/命题形式/合式公式/公式：（1）可满⾜式：⾮重⾔的可满⾜式重⾔式/永真式（2）⽭盾式/永假式（不存在成真指派）命题公式不是命题，只有当公式中的每⼀个命题变项都被赋以确定的真值时，公式的真值才被确定，从⽽成为⼀个命题。

三、命题逻辑的等值演算A⟺B：A和B有等值关系。

对任意真值指派，A与B取值相同。

A⟷B为永真式。

等值关系⼀般通过真值表法或者等值演算法得到。

⽽不等值，只能通过真值表法，找到某个真值指派使得⼀个为真⼀个为假德摩根律：┐(A∨B)⟺┐A∧┐B、┐(A∧B)⟺┐A∨┐B蕴含等值式：A→B⟺┐A∨B吸收律：A∨(A∧B)⟺A、A∧(A∨B)⟺A归谬式：(A→B)∧(A→┐B)⟺┐A例题：p→(q→r)⟺┐p∨(┐q∨r)⟺(┐p∨┐q)∨r⟺┐(p∧q)∨r⟺(p∧q)→r四、范式由有限个⽂字的析取所组成的公式称为析取式；由有限个⽂字的合取所组成的公式称为合取式形如A1∨A2∨…∨A n的公式称为析取范式DNF（其中A i为合取式）；形如A1∧A2∧…∧A n的公式称为合取范式CNF（其中A i为析取式）任⼀命题公式都存在着与之等值的析取范式和合取范式，但析取范式和合取范式可能不是惟⼀的。

极⼩项q1∧q2∧…∧q n：⼀共2n种解释，每个极⼩项只在⼀个解释下为真。

每个极⼩项对应⼀个⼆进制数，该⼆进制数正是该极⼩项真值为真的指派，即m0可表⽰┐q1∧┐q2∧…∧┐q n极⼤项q1∨q2∨…∨q n：⼀共2n种解释，每个极⼤项只在⼀个解释下为假。

离散数学_命题逻辑_1.1

离散数学_命题逻辑_1.1

1.1命题与联结词
例1.1 判断下列语句是否是命题 不是命题 (7) x+8>0。 (8)你出去么？ 不是命题 (9)5或6是素数。 不是命题 (10)如果行列式的两行对应成比 真命题 例，则行列式的值为0。 (11)角A与角B相等当且仅当A与角 假命题 B是对顶角。
1.1命题与联结词


2.命题的特点 命题一定是陈述句,但陈述句不一定是命 题。 命题的真值有时明确给出，有时还要依 靠环境、条件、实际情况等因素才能确 定其真值。
什么是离散？离散就是不连续。
线与点。 人的说话声，鸟叫声等；计算机里储存声音。 生活中，人眼见到的图像(非计算机里的)；计 算机里用灰度值(从0到255)表示的图像。 计算机不能处理连续信息的，这是由计算机的 本质：0和1，决定的。因此，如果要用计算机 来处理连续信息，必须经过离散化。


离散数学的地位


离散数学的特点

提高抽象思维、严格推理以及综合归纳 分析能力 以研究离散量的结构和相互关系为主要 目标
显著特征是符号化和形式化


离散数学的用途

又称“计算机数学”，因为离散数学的 主要应用领域是计算机。
数理逻辑——数字逻辑电路、密码学 图论(包括树)——数据结构、操作系统 、编译 原理、计算机网络 集合论和关系代数——软件工程和数据库原理
其他分支
代数系统
图论
形式语言与 自动机
数理逻辑
集合论
离散数学 的构成
数理逻辑 命题逻辑
离散数学
集合论 集合及其运算 二元关系
谓词逻辑
函数
代数系统
图论 图的基本概念
群、环、域
Euler图与Hamilton图

离散数学第一章 命题逻辑

离散数学第一章 命题逻辑
4/5/2014 8:53 PM chapter1 10
1.2 联结词
2、合取 ∧
Proposition Logic 命题逻辑
P∧Q是P和Q的合取, 读做“P与Q”或“P并且Q”。
P 0 0 1 1 Q 0 1 0 1 P ∧Q 0 0 0 1
如： P: 王华的成绩很好。
Q: 王华的品德很好。 P∧Q: 王华的成绩很好并且品德很好。
对，成立，则真值为真，T，1
错，不成立，则真值为假，F，0
断言是一陈述语句。一个命题是一个或真或假而不能 两者都是的断言。如果命题是真, 我们说它的真值为真； 如果命题是假，我们说它的真值是假。
4/5/2014 8:53 PM chapter1 2
1.1 命题及其表示法
【例1 】判定下列各语句是否为命题： （是） (a) 巴黎在法国。 （是） （是） (c) 3+2=5 (d) 别的星球上有生物。 （是） (b) 煤是白色的。 (e) 全体立正。 (f) 明天是否开大会？
从真值表可知P∨Q为真, 当且仅当P或Q至少有一为真。
4/5/2014 8:53 PM chapter1 12
1.2 联结词
Proposition Logic 命题逻辑
“或”字常见的含义有两种: 一种是“可兼或”, 如上
例中的或, 它不排除小王既喜欢唱歌又喜欢跳舞这种情况。
一种是“排斥或”（异或）, 例如“人固有一死, 或重于泰 山, 或轻于鸿毛”中的“或”, 它表示非此即彼, 不可兼得。 运算符∨表示可兼或, 排斥或以后用另一符号表达。 如：(1)小李明天出差去上海或去广州。
所以,“如果P则Q”, “只要P则Q”,只有Q才P”, “仅当Q 则P”都可符号化为P→Q 的形式。

离散数学

离散数学

第一章命题逻辑1.1 命题及其表示方法1.2 联结词1.3 命题公式与翻译1.4 真值表与等价公式1.5 重言式与蕴含式1.6 其它联结词1.7 对偶与范式1.8 推理理论1.1 命题及其表示方法命题：具有确定真值的陈述句命题的类型（原子命题和复合命题）命题的表示（一个命题标识符（比如P）表示确定的命题）重点：如何判断语句是否为命题。

1.2 联结词否定⌝合取∧析取∨条件→双条件↔重点：五种联结词的含义、真值表1.3 命题公式与翻译命题公式符号化：所谓命题的符号化就是把一个用文字叙述的句子相应地写成由命题标识符、联结词和括号表示的合式公式。

命题符号化的重要性命题符号化是很重要的，一定要掌握好，在命题推理中最先遇到的就是符号化一个问题，解决不好，等于说推理的首要前提没有了。

重点：命题的符号化符号化应该注意下列事项:①确定给定句子是否为命题。

②句子中连词是否为命题联结词。

③要正确地表示原子命题和适当选择命题联结词。

1.4 真值表与等价公式真值表的构造方法(1) 找出公式中所含的全体命题变元P1, P2, …, Pn, (若无下角标就按字典顺序排列), 列出2n个赋值. 赋值从00…0开始, 然后按二进制加法依次写出各赋值, 直到11…1为止.(2) 按从低到高的顺序写出公式的各个层次.(3) 对应各个赋值计算出各层次的真值, 直到最后计算出公式的真值.等价关系的含义等价式的判别方法•真值表法•等价演算法基本等价式（必须掌握）(1)对合律（双重否定）：⌝⌝P⇔P(2)幂等律：P∧P⇔P，P∨P⇔P(3)结合律：(P∧Q)∧R⇔P∧(Q∧R)，(P∨Q)∨R⇔P∨(Q∨R)(4)交换律：P∧Q⇔Q∧P，P∨Q⇔Q∨P(5)分配律：P∧(Q∨R)⇔(P∧Q)∨(P∧R)，P∨(Q∧R)⇔(P∨Q)∧(P∨R)(6)德·摩根律：⌝ (P∧Q) ⌝⇔P∨⌝Q，⌝ (P∨Q) ⌝⇔P∧⌝Q(7)吸收律：P∧(P∨Q)⇔P，P∨(P∧Q)⇔P(8)同一律：P∧T⇔P，P∨F⇔P(9)零律：P∧F⇔F，P∨T⇔T(10)否定律：P∧⌝P⇔F，P∨⌝P⇔T(11) 条件式转化律：P→Q⌝⇔P∨Q，P→Q⌝⇔Q→⌝P(12) 双条件式转化律：P↔Q ⇔(P→Q)∧(Q→P) ⇔(P∧Q)∨(⌝P∧⌝Q)⌝ (P↔Q) ⇔P⌝↔Q ⌝⇔P↔Q(13) 输出律(CP规则)：P→(Q→R) ⇔(P∧Q)→R重点：等价式的证明、基本等价式1.5 重言式与蕴含式重言式或永真公式定义1-5.1 给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为真，则称该命题公式为重言式或永真公式。

离散数学考试大纲

离散数学考试大纲

离散数学考试大纲1 命题演算基础1．1 命题与联结词①命题②联结词③合式公式④命题的符号化1.2 真假性①解释②等价公式③联结词的完备集④对偶式和内否式。

1.3 范式及其应用①范式②主范式2 命题演算的推理理论2.1 命题演算的公理系统①公理系统的组成部分②公理系统的推理过程2.2 命题演算的假设推理系统①假设推理系统的组成②假设推理系统的推理过程2.3 命题演算的归结推理法①归结证明过程②归结证明方法3 谓词演算基础3.1 谓词和个体①个体②谓词③语句的符号化3.2 函数和量词①函数项②量词3.4 永真性和可满足性①真假性②同真假性③永真性和可满足性④范式4 谓词演算的推理理论4.1 谓词演算的永真公理系统①公理系统的组成部分②公理系统的推理过程4.2 谓词演算的假设推理系统①假设推理系统的组成及证明方法②定理的推导过程4.3 谓词演算的归结系统①置换②归结反演系统③霍恩子句逻辑程序5递归函数论5.1 数论函数和数论谓词5.2 函数的构造6 集合6．1 集合的基本概念①集合；②子集合；③空集合；④集合的相等。

6．2 集合的基本运算①集合的运算；②集合的交；③集合的并；④集合的差；⑤集合的对称差；⑥集合的广义交；⑦集合的广义并；⑧幂集合。

6．3 全集和集合的补①全集；②集合的补；③德·摩根定律。

6．4 自然数与自然数集①自然数；②自然数集；③数学归纳法；④集合的归纳定义。

6．5 包含与排斥原理①有限集；②包含与排斥原理。

7 关系7．1 集合的笛卡尔积集①有序对；②集合的笛卡尔积集；③有序n(n≥2)元组；④n重(n≥2)笛卡尔积集。

7．2 二元关系的基本概念①二元关系；②二元关系的表示；③二元关系的图形表示；④二元关系的矩表示；⑤二元关系的运算；⑥二元关系的复合运算；⑦二元关系的逆关系。

7．3 二元关系的性质①二元关系的性质；②自反的二元关系；③反自反的二元关系；④对称的二元关系；⑤反对称的二元关系；⑥传递的二元关系。

离散数学(第二版) (1)

离散数学(第二版) (1)
论(conclusion)或后件(consequent)。 “→”是一个二元运算。 条件联结词→的定义如表1.1.4
所示。
表1.1.4
第1章 命题逻辑
第1章 命题逻辑 5. 双条件联结词
定义1.1.6 如果 P和Q是命题， 那么“P当且仅当 Q” 是一个复合命题， 记做 P Q， 称为P和Q的双条件命题
表1.1.1
第1章 命题逻辑
第1章 命题逻辑
2. 合取联结词
定义1.1.3 如果 P和Q是命题， 那么“P并且Q”是一个 复合命题， 记做P∧Q， 称为P和Q 的合取(conjunction)。 符号∧用于表示合取联结词。 P∧Q 为T， 当且仅当P、 Q
均为T。 “∧”是一个二元运算符。 合取联结词∧的定义如表
第1章 命题逻辑
定义1.1.1 一个具有真或假但不能两者都是的断言称为 命题。
如果一个命题所表达的判断为真， 则称其真值(truth value)为“真”， 用大写字母T或数字1表示； 如果一个命题 所表达的判断为假， 则称其真值为“假”， 用大写字母F或 数字0表示。 为简便起见， 本书在构建真值表时一般用0表示 “假”， 用1表示“真”。
(biconditional proposition)。
词。 P Q为T， 当且仅当 P和Q 的真值相同。
1.1.5所示。
表1.1.5
第1章 命题逻辑
第1章 命题逻辑
1.2 命 题 公 式
1.2.1 命题公式及其符号化
定义1.2.1 用于代表取值为真(T、 1)或假(F、 0)之一 的变量， 称为命题变元， 通常用大写字母或带下标或上标的
大写字母表示， 如 P、 Q、 R、 P1、 P2等。 将T和F称为命

离散数学命题与联结词

离散数学命题与联结词
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 与

离散数学-命题

离散数学-命题

例2 将下列命题符号化. (1) 王晓既用功又聪明. (2) 王晓不仅聪明，而且用功. (3) 王晓虽然聪明，但不用功. 解: 令 p： 王晓聪明，q：王晓用功，则 (1) p∧q (2) p∧q (3) p∧q.
(4) 张辉与王丽都是三好生. (5) 张辉与王丽是同学. 解： 令 r : 张辉是三好学生，s :王丽是三好学生
(5) 王晓红生于1975年或1976年.
令v :王晓红生于1975年,w:王晓红生于1976年,
则 (5) 可符号化为 (v∧w)∨(v∧w),
又可符号化为 v∨w , 为什么?
(4), (5) 为排斥或.
4.蕴涵式与蕴涵联结词“” 定义 设 p,q 为二命题，复合命题 “如果 p, 则 q” 称作 p 与 q 的蕴涵式，记作 pq，并称 p 是蕴涵式 的前件， q 为蕴涵式的后件 . 称作蕴涵联结词，
练习： 将下列命题符号化：
（1）只要不下雨，我就骑自行车上班。
（2）只有不下雨，我才骑自行车上班。
（3）除非下雨，否则我就骑自行车上班。
（4）如果下雨，我就不骑自行车上班。 解：令p：天下雨，q：我骑自行车上班，则： （ 1） ¬ p→q （2）q→¬ p （ 3） ¬ p→q （4）p→¬ q
1.2.ppt
0， 0. 它们的真值分别为 1， 0，1，
以上给出了5个联结词：, , , , ， 组成一个联结词集合{, , , , }， 联结词的优先顺序为：, , , , ; 如果出
现的联结词同级，又无括号时，则按从左到右
的顺序运算; 若遇有括号时，应该先进行括号
中的运算.
注意: 本书中使用的 括号全为圆括号.
离散数学
数理逻辑 集合论 代数结构 图论 组合分析初步 形式语言和自动机初步

离散数学第五版第一章(耿素云、屈婉玲、张立昂编著)

离散数学第五版第一章(耿素云、屈婉玲、张立昂编著)
何情况下真值相同。
12
命题与联结词
2. 合取 符号：
定义1.2：设p，q为二命题，复合命题“p并且q”（或“p与q”）称为p 与q的合取式，记作pq ，符号称为合取联结词。并规定pq 为真当且仅当p与q同时为真时为真。 真值表：
P Q 0 0 0 1 1 0 1 1 P 0 0 0 1
Q
p:天下雨。 q:我骑自行车上班。 s:2+2=4。 t:太阳从东方升起
r:太阳从西方升起。
19
命题与联结词
5. 等价 符号：
定义1.5：设p ，q为二命题，复合命题“p 当且仅当 q” 称为p与q的等 价式，记作p q ，符号 称为等价联结词。并规定p q为真当且仅当p与q同时为真或同时为假。 真值表：
25
等值式
一、等值 1. 定义2.1
设A、B是两个命题公式，若A，B构成的等价式AB为重 言式，则称A与B是等值的，记作AB。
2.
注意
不是联结符，它是用来说明A与B的等值，要与区分清楚。
3.
如何判断两个命题公式是否等值？
方法一：通过真值表比较在各相同赋值情况下，真值是否相同。 方法二：将A，B构成 AB等价式，判断其是否为重言式。
② 设P: 明天下雨, Q: 明天下雪, R: 我去学校。 则 (i) “如果明天不是雨夹雪则我去学校”可写成 (ii) “如果明天不下雨并且不下雪则我去学校”可写成 (iii) “如果明天下雨或下雪则我不去学校”可写成 (iv) “ 当 且 仅 当 明 天 不 下 雪 并 且 不 下 雨 时 我 才 去 学 23 校 ; ; ; ;
p:张明正在睡觉。 q:张明正在游泳
p q
排斥或
p:李强是位排球队员。 q:李强是位足球队员 pq 相容或 p:张静挑选202房间。 q:张静挑选203房间 （ p q）（p q）
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

• 在命题逻辑中允许前件和后件间无必然的因果关系。
4. 条件联结词
• P：天下雨；Q：马路湿；
P
Q
P →Q
Q →P
P →Q：如果天下雨，则马路湿。 下面讨论P→Q 的真值： • 如果天下雨，则马路湿； • 如果天下雨，则马路不湿； • 如果天不下雨，则马路湿；(善意推断) • 如果天不下雨，则马路不湿； • • P：2+2=4；Q：雪是黑的； P →Q：如果2+2=4，则雪是黑的。

原子命题的符号表示：大小写英文字母：P、Q、R、 p 、q 、r、…… 带下标的大写字母：Pi，Qi，Ri，……

例如： P：北京是中国的首都。
• 命题常元：一个命题标识符P，如果表示一个确定的命题，则称 P为原子命题常元，简 称命题常元； • 命题变元：若P只表示任意命题的位置标志，或表示不确定的命题，或以原子命题为值 的变元P，称P为原子命题变元，简称命题变元。 命题变元是以命题的真值为值的变元。 命题变元不是命题。 • 命题指派：将一个命题变元 P 用一特定命题去代替，它才能确定真值，叫做对 P 的指派 或解释，记为 S(P) 或 I(P)。
是命题，真 不是命题
不是命题 是命题，真值不确定
• 请勿喧哗！
• 明天去哪里？ • 有外星人
• 曹操是明朝人
• 6+8>14 • 今天下雨 • 今天我休息 • 11+1=100
是命题，假
是命题，假 是命题，真值不确定 是命题，真值不确定 是命题，真值不确定
1.1 命题与联结词
二、命题标识符
• 命题标识符：表示原子命题的符号称为命题标识符，简称命题符。
1.1 命题与联结词 总结
• • • 复合命题的真值只取决于构成它们的各原子命题的真值，与它们 的内容、含义无关。 ∧ 、∨ 、 具有对称性；而 ┐ 、→ 没有对称性； 联结词都有从已知命题得到新的命题的作用，它们具有操作或运 算的意义。联结词可以被看做是一、二元运算或一、二元函数。
•
• •
这真开心！
你听懂了吗？ 请止步！
C : 1+1=1
• 现在是六点钟
一个陈述句能否分辨其真假与是否现 在能判断它是真是假是两件事。 • 张校长的头发有一万根
“自指谓”的陈述句 （结论是对自身而言） 不是命题 • 我所说的是假的
例:
判断下列语句哪些是命题。若是命题，指出真值。
• 巴黎在法国
P T T F F
Q T F T F
P∧Q T F F F
Q∧P T F F F
• P：今天下雨。
• Q：明天下雨。
• P∧Q：今天下雨而且明天下雨。 • P∧Q：今天与明天都下雨。
• P∧Q：这两天都下雨。
3. 析取联结词
• 设P 和Q是两个命题，由联结词∨把P，Q 连接成P∨Q，读做“P 或Q ”。 称 P ∨Q 为P，Q 的析取式复合命题。 析取联结词是“或”、“或者”的逻辑抽象。 • 析取联结词是表示可兼或，即二者可同时发生，不排斥二者发生的情况。 • 析取联结词不表示不可兼或排斥或，即非此即彼。
T
T F F
T
F T F
T
F T T
T
T F T
5. 双条件联结词
• 令P 和Q 是两个命题，由联结词把P，Q 连接成P Q，读做“P 当且仅当Q ”。称P Q 为 P 和Q 的双条件式复合命题。
• 双条件联结词又常称为同或，并用符号⊙表示。 • 双条件联结词是自然语言中的“充分必要条件”、“当且仅当”等的逻辑抽象。
第1章 命题逻辑
第1章 命题逻辑
1.1 命题与联结词 1.2 命题公式、翻译和真值表
1.3 公式分类与等价式
1.4 对偶式与蕴含式 1.5 联结词的扩充与功能完全组 1.6 公式标准型----范式 1.7 公式的主范式 1.8 命题逻辑的推理理论
1.1 命题与联结词
1.1 命题与联结词
一、命题的概念
• • • 命题：非真必假的陈述句。 具有真假意义的陈述句，且真或者假二者必居其一，也只居其一。 命题的真或假称为命题的真值。 真用T或1表示 假用F或0表示
命题的注意事项
自然语言中的感叹句、疑问句和祈使 句不是命题。 判定命题的真值会因人、因时、因地、 因标准而异。 • A : 1+1=2 B : 1+1=10
“P 条件Q ”。称P →Q 为P 和Q 的条件式复合命题， 把 P 和Q 分别称为P →Q 的前件 和后件， 或者前提和结论。
• 联结词→是自然语言中“如果…，则…”，“若…，才能…”等的逻辑抽象，是充分条
件。
• 在自然语言中，前件为假，不管结论真假，整个语句的意义往往无法判断。在命题逻
辑中，当P 为F，P →Q 为T，称为“善意推定”。
P T T F F
Q T F T F
PQ T F F T
QP T F F T
• 三角形是等边三角形当且仅当三角形的三
个内角相等。
• 2+2=4当且仅当太阳是恒星。
1.1 命题与联结词
四、命题分类 • • • 命题分两类：原子命题和复合命题 复合命题：由原子命题和联结词复合而成 判断一个命题是否为复合命题，其关键是联结词是否出现，出现联 结词则是复合命题，不出现联结词则是原子命题。
P
T T F
Q
T F T
P∨Q
T T T
Q∨P
T T T
• • •
今天晚上我在家看电视或去剧场看戏。 （排斥或）----不是命题联结词 他可能是100米或400米赛跑的冠军。 （可兼或）----是命题联结词 他昨天做了二十或三十道题。 （表示近似数）----不是联结词
F
F
F
F
4. 条件联结词
• 设P 和Q 是两个命题，由联结词→把P，Q 连接成P →Q，读做 “如果P，则Q ” 或者
1.1 命题与联结词
三、联结词 联结词是逻辑联结词或命题联结词的简称，它是自然语言中连词的逻辑抽象，用它 和原子命题构成复合命题。 否定联结词 合取联结词 析取联结词 条件联结词 双条件联结词 ┐ ∧ ∨ →
. 否定联结词
• 设P 是一个命题，由联结词 ┐和命题P 构成 ┐P， 读“非P ”。 ┐P 为命题P 的 否定式复合命题。 • 联结词 ┐是自然语言中的“非”、“不”和“没有”等的逻辑抽象。
P T F
┐P
•
• •
P ：上海是一个大城市。
┐P：上海并不是一个大城市。 ┐P：上海是一个不大的城市。
F T
2. 合取联结词
• 令P 和Q 是两个命题，由联结词∧把P，Q 连接成P∧Q，读做“P 与Q ”， 或“P 合取Q ”。称P∧Q为P 和Q 的合取式复合命题。 • 联结词∧是自然语言中的“并且”，“既…又…”等的逻辑抽象。