[离散数学] 集合与图论

《[离散数学] 集合与图论》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、《集合论与图论》《离散数学》系列课程之一刘田北京大学计算机系2001年2月教材•《集合论与图论》，离散数学二分册，耿素云，北大出版社，1998年2月参考书•《离散数学习题集》，耿素云，北大出版社–数理逻辑与集合论分册，1993年2月–图论分册，1990年3月内容介绍•《离散数学》–《集合论与图论》–《代数结构与组合数学》–《数理逻辑》内容介绍•《集合论与图论》–第一部分集合论•第1章集合•第2章二元关系•第3章函数•第4章自然数•第5章基数内容介绍•《集合论与图论》–第二部分图论•第7章图•第8章欧拉图与哈密顿图•第9章树•第10章图的矩阵表示•第11章平面图•第12章图

2、的着色•第13章支配、覆盖、独立、匹配•第14章带权图进度安排•第1周预备知识（数理逻辑）•第2--7周集合论（6周）•第8--17周图论（10周）•第8、15周测验（2次）•第18周（机动）成绩评定•书面作业占10%，4--5题/每次课•平时测验占30%，1小时/每次，2次•期末考试占60%作业•时间：每周日交上周作业，下周日发回•顺序：每次交一个班，1、2、3班轮流•讲解：每次作业都有课上讲解•要求：正确、完全、简洁、清楚Correct，Complete，Concise，Clear•提示：独立完成作业，可以讨论，但要杜绝抄袭答疑•时间：（待定）•地点：理科楼群#1，1

3、625室•电话：62765818•Email：–liu_tian@263.net–liutian@theory.cs.pku.edu.cn•讲义下载：–ftp://162.105.30.157/incoming/Liu_Tian/第1讲命题逻辑基础•1.命题、命题符号化•2.合式公式、真值表、永真式•3.逻辑等值式、推理定律•4.形式化证明什么是命题(proposition)•命题：真假值唯一确定的陈述句。–地球围绕太阳转。–2+2=5。–多冷啊！关上门吧！–你去锻炼身体了吗？–火星上有生命。–2002年1月1日下雪。–这句话是假的。什么是命题(续)•简单(simple)

4、命题：不含联结词的命题。•复合(compound)命题：含联结词的命题。–我痛并快乐着。–如果天气好，我就去锻炼。–老王或老李中的一个人去出差，当且仅当不是他们都去或者都不去。常用的联结词(connective)•合取(conjunction)：与，并且，而且，也•析取(disjunction)：或，要么…要么…•否定(negation)：非，不•蕴涵(conditional)：如果…就…，只有…才…，除非…不，若…则…，•等价(biconditional)：当且仅当命题符号化•简单命题：p,q,r,p,q,r,…111•联结词：–合取联结词：∧–析取联结词：∨–否定联结

5、词：¬–蕴涵联结词：→–等价联结词：↔•逻辑真值：0，1命题符号化（举例）•例1：地球围绕太阳转。解：p：地球围绕太阳转。•如果天气好，我就去锻炼。解：p：天气好；q：我去锻炼；原命题符号化结果是：p→q命题符号化（举例、续）•例3：老王或老李中的一个人去出差，当且仅当不是他们都去或者都不去。解：p：老王去出差；q：老李去出差；原命题符号化结果是：((p∧¬q)∨(¬p∧q))↔(¬((p∧q)∨(¬p∧¬q)))字母表(alphabet)•命题变元：p,q,r,p,q,r,…111•联结词：∧，∨，¬，→，↔•分隔符：（，）合式公式(well-formedformula

6、)•单个命题变项是合式公式，称为原子（atomic）公式•若A是合式公式，则(¬A)是合式公式•若A,B是合式公式，则(A∧B),(A∨B),(A→B),(A↔B)也是合式公式•只有有限次地应用上述规则形成的符号串才是合式公式合式公式（举例）•p•(¬(¬p))，¬¬p•((¬p)∧(¬p))，¬p∧¬p•(¬(p∧q))，¬(p∧q)•((¬p)∧q)，¬p∧q–约定：省略多余括号•最外层•优先级递减：¬；∧，∨；→，↔真值表(truth-table)•赋值(assignment)：给变元指定0、1值•n个变元，共有2n种不同的赋值pq¬pp∧qp∨qp→qp↔q001

7、0011011011010001001101111真值表(续)pqr(p∧q)→r¬p∨¬q∨r0001100111010110111110011101111100011111永真式(tautology)•永真式:在各种赋值下取值均为真(重言式)•永假式:在各种赋值下取值均为假(矛盾式)•可满足式：非永假式pq¬(p∧q)¬p∨¬q¬(p∧q)↔(¬p∨¬q)00111011111011111001逻辑等值式(identities)•等值：A⇔B–读作：A等值于B–含义：A与B在各种赋值下取值均相等•A⇔B当且仅当A↔B是永真