离散数学复习(08)省公开课一等奖全国示范课微课金奖PPT课件.pptx

该【离散数学复习(08)省公开课一等奖全国示范课微课金奖PPT课件 】是由【liaoyumen】上传分享，文档一共【20】页，该文档可以免费在线阅读，需要了解更多关于【离散数学复习(08)省公开课一等奖全国示范课微课金奖PPT课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。Ch1命题逻辑
数理逻辑：研究一个形式语言，其本质是将数学中逻辑证实加以符号化，因而推进各数学分支快速发展。
命题：表示判断含有确定真值陈说句。
命题只要能判断真假，不一定已知真假
非陈说性语句不是命题
方程不是命题
悖论不是命题
第1页
联结词
否定 
合取 ∧ 析取： ∨
条件  双条件 ⇄
翻译提醒：
不可兼或：  (P ⇄Q )
当 P则Q(假如P，那么Q) : P Q
P仅当 Q(仅当Q，则P) : P Q
除非P不然Q： P  Q
只要Ｐ，就有Ｑ： P  Q
只有Ｐ，才能Ｑ： Q  P
定义普通翻译为双条件
优先级：
　高
　低
第2页
1、只有你主修计算机科学或者不是新生，才能从校园内 访问因特网。2、除非你已满16周岁，不然只要你身高不足4英尺就不能乘公园滑行铁道。3、只要充分考虑一切论证，就能得到可靠看法。4、只有充分考虑一切论证，才能得到可靠看法。5、我们不能既唱歌又看书。6、假如天下雨，我出不出去看你是否同意而定。7、我唱歌，仅当你伴奏。8、或者你没有给我写信，或者信在路上丢失了。9、假如天下雨，我就在家看书，不然我就去看电影。10、只有你考试不及格或者缺考，才能参加补考。11、除非你缺考，不然只要你考试不满60分就必须参加 补考。
第3页
推理理论
P规则
T规则
证实方法：
直接证法
反证法
CP规则(CP规则能够连续使用)
1、 A ∨B C ∧ D , D∨E  F A F
2、 P∨Q,  Q∨R, R S  PS
3、 P (Q∨R) ,Q   P, S   R  P   S
4、A(BC),(C∧D) E,  F (D∧ E) A(BF)
第4页
原子命题拆成：客体 ＋谓词
全称量词　“”，存在量词　“”
翻译注意：
特征谓词位置：在全称量词作用域内作条件句前件，在存在量词作用域内作合取项。
1、全部人都犯错误。2、有且仅有一个偶质数。3、有些人对全部酒都感兴趣。4、全部人都对一些酒感兴趣。5、尽管有些人可恶，但并不是全部人都可恶。6、对于任意实数，存在更大实数。7、一些火车比全部飞机慢，但最少有一架飞机比全部火车快。 8、并非全部人都喜欢喝酒。
Ch2谓词逻辑
第5页
量化断言与命题关系
假设个体域D={a1, a2，…，an}
(x) (P(x)) 　P(a1) ∧ P(a2) ∧ … ∧ P(an)
( x)(P(x)) 　P(a1) ∨ P(a2) ∨ … ∨ P(an)
谓词演算推理理论
消去、添加量词规则
全称指定 US 全称推广 UG 存在指定 ES 存在推广 EG
在谓词推理中，必须注意两点：
不能在量词作用域内使用等价式和蕴含式
在同一证实中，若既要使用存在指定，又要使用全称指定，则先用存在指定，后用全称指定。
第6页
谓词推理理论
P规则、T规则、 US、UG、ES、EG
证实方法：直接证法 反证法 CP规则
1、(x)(P(x) Q(x))  (x)P(x) (x)Q(x)
2、( x)A(x) (x)B(x)  (x)(A(x) B(x))
3、(x)P(x) (x)(P(x)∨Q(x) R(x)), (x)P(x),(x)Q(x)
 (x)(y)(R(x) ∧R(y))
4、(x) (A(x)∨B(x))  (x)A(x)∨(x)B(x)
5、 ( x)(F(x) ∧S(x)) (y)(M(y) W(y)),
(y)(M(y) ∧  W(y))  (x)(F(x)  S(x))
6、(x)(F(x)∧H(x)), (x)(G(x)H(x)) 
(x)(G(x) F(x))
第7页
Ch3 集合与关系
定理 集合A和B相等充分必要条件是这两个集合互为子集。
集合运算　 、 、－(相对补)、～ (绝对补)、 (对称差)
运算性质
序偶与笛卡儿积
1、若C≠  ， 则 A⊆B⇔ A×C⊆B×C
2、设A,B为两个集合，若A∩B≠  ，则
(A∩B)×(A∪B)⊆(A×A)∪(B×B)
3、证实 P(A)∩P(B)=P(A∩B)
4、设A和B是论域E子集，B=A AB=E ∧
AB= 
第8页
关系性质证实方法：
要证实R在X上自反
假设x∈X ，证出 <x,x>∈R
要证实R在X上对称
对x,y ∈X,设<x,y>∈R ，证出 < y, x >∈R
要证实R在X上传递
对x,y,z∈X,设<x,y>∈R ∧< y, z >∈R ，证出 <x,z>∈R
要证实R在X上反自反
假设x∈X，证出 <x,x>∉R ）
要证实R在X上反对称
对x,y∈X，设<x,y>∈R∧< y, x >∈R ，证出 x＝y
关系性质
自反、对称、传递、反自反、反对称
第9页
关系运算：
 、 、－(相对补)、～ (绝对补)、 (对称差)
关系复合、关系逆、关系闭包运算
集合划分与覆盖
划分能够确定一个等价关系
覆盖能够确定一个相容关系
等价关系与等价类及其性质
序关系
偏序关系、哈斯图、极大元、极小元、最大元、最小元、上界、下界、上确界、下确界
第10页