离散数学复习).ppt

Ch1命题逻辑 命题：表示判断的具有确定真值的陈述句。 联结词 否定 ? 合取 ∧ 析取： ∨ 条件 ? 双条件 ? 1、只有你主修计算机科学或者不是新生，才能从校园内 访问因特网。2、除非你已满16周岁，否则只要你身高不足4英尺就不能乘公园滑行铁道。3、只要充分考虑一切论证，就能得到可靠见解。4、只有充分考虑一切论证，才能得到可靠见解。5、我们不能既唱歌又看书。6、如果天下雨，我出不出去看你是否同意而定。7、我唱歌，仅当你伴奏。8、或者你没有给我写信，或者信在路上丢失了。9、如果天下雨，我就在家看书，否则我就去看电影。10、只有你考试不及格或者缺考，才能参加补考。11、除非你缺考，否则只要你考试不满60分就必须参加 补考。 推理理论 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) Ch2谓词逻辑 原子命题拆成：客体 ＋谓词 全称量词　“?”，存在量词　“?” 翻译注意： 特性谓词的位置：在全称量词的作用域内作条件句的前件，在存在量词的作用域内作合取项。 1、所有的人都犯错误。2、有且仅有一个偶质数。3、有些人对所有酒都感兴趣。4、所有的人都对某些酒感兴趣。5、尽管有人可恶，但并不是所有的人都可恶。6、对于任意实数，存在更大的实数。7、某些火车比所有飞机慢，但至少有一架飞机比所有火车快。 8、并非所有的人都喜欢喝酒。 量化断言与命题的关系 假设个体域D={a1, a2，…，an} (?x) (P(x)) ?　P(a1) ∧ P(a2) ∧ … ∧ P(an) (? x)(P(x)) ?　P(a1) ∨ P(a2) ∨ … ∨ P(an) 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= ? 关系性质的证明方法： 要证明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 关系的的运算： ? 、? 、－(相对补)、～ (绝对补)、 ?(对称差) 关系的复合、关系的逆、关系的闭包运算 函数 函数的概念 入射、满射、双射 逆函数(当f 是双射函数时逆函数才有意义。) 复合函数(注意写法与关系的复合不同。) 求gof时，若ranf 不包含于 domg，则gof为空 1、令gof是一个复合函数，则 (1)若g 和f 是满射的,则 gof 是满射的； (2)若g 和f 是入射的,则 gof 是入射的； (3)若g 和f 是双射的,则 gof 是双射的。 2、令gof是复合函数，则  (1)若gof 是满射的,则g是满射的； (2)若gof 是入射的,则f是入射的； (3)若gof 是双射的,则g是满射的，f是入射的。 Ch5 代数系统 运算的性质(封闭性、交换性、结合性、分配律、吸收律、等幂律) 特殊的元素(幺元、零元、逆元) 广群、半群、独异点、群和子群 阿贝尔群和循环群 证明a是b的逆元? a * b= b * a =e例如：(a * b)-1=b-1 * a-1 群中满足消去律 群中不可能有零元。 任何一个循环群必定是阿贝尔群。 群G,*中的幺元 e 必定也是其子群S,*中的幺元。 子群的判定定理：当Ｓ是有限集： *在Ｓ上封闭 当Ｓ是无限集： ?a，b∈S， 　　　　　　　　　　　　　　　　 有a*b