离散数学（第五版）清华大学出版社第2章习题解答 2.1 本题没有给出个体域,因而使用全总个体域. (1) 令F(x):x是鸟 G(x):x会飞翔. 命题符号化为 ?x(F(x)→G(x)). (2)令F(x):x为人. G(x):x爱吃糖 命题符号化为 ??x(F(x)→G(x)) 或者 ?x(F(x)∧?G(x)) (3)令F(x):x为人. G(x):x爱看小说. 命题符号化为 ?x(F(x)∧G(x)). (4) F(x):x为人. G(x):x爱看电视. 命题符号化为 ??x(F(x)∧?G(x)). 分析1°如果没指出要求什么样的个体域，就使用全总个休域，使用全总个体域时，往往要使用特性谓词。（1）-（4）中的F(x)都是特性谓词。 2°初学者经常犯的错误是，将类似于（1）中的命题符号化为 27 ?x(F(x)∧G(x)) 即用合取联结词取代蕴含联结词，这是万万不可的。将（1）中命题叙述得更透彻些，是说“对于宇宙间的一切事物百言，如果它是鸟，则它会飞翔。”因而符号化应该使用联结词→而不能使用∧。若使用∧，使（1）中命题变成了“宇宙间的一切事物都是鸟并且都会飞翔。”这显然改变了原命题的意义。
3°（2）与（4）中两种符号化公式是等值的，请读者正确的使用量词否定等值式，证明（2），（4）中两公式各为等值的。 2.2 (1)d (a),(b),(c)中均符号化为 ?xF(x) 其中F(x):(x+1)2=x2+2x+1,此命题在(a),(b),(c)中均为真命题。 （2）在(a),(b),(c)中均符号化为 ?xG(x) 其中G(x):x+2=0，此命题在（a）中为假命题，在(b)(c)中均为真命题。 （3）在(a),(b),(c)中均符号化为 ?xH(x) 其中H(x):5x=1.此命题在(a),(b)中均为假命题，在(c)中为真命题。 分析1°命题的真值与个体域有关。 2°有的命题在不同个体域中，符号化的形式不同，考虑命题 “人都呼吸”。 在个体域为人类集合时，应符号化为 ?xF(x) 这里，F(x):x呼吸，没有引入特性谓词。 在个体域为全总个体域时，应符号化为 ?x(F(x)→G(x)) 这里，F(x):x为人，且F(x)为特性谓词。G(x):x呼吸。 28 2．3 因题目中未给出个体域，因而应采用全总个体域。 （1）令：F(x):x是大学生，G(x):x是文科生，H(x):x是理科生，命题符号化为?x(F(x)→(G(x)∨H(x)) （2）令F(x):x是人，G(y):y是化，H(x):x喜欢，命题符号化为 ?x(F(x)∧?y(G(y)→H(x,y))) （3）令F(x):x是人，G(x):x犯错误，命题符号化为 ??x(F(x)∧?G(x)), 或另一种等值的形式为 ?x(F(x)→G(x)
一、判断题 (正确的在括号内填写“√”，错误的写“×”) （ ）1、“只有天下大雨，他才乘班车上班”与“除非天下大雨，否则他不乘班车上班”所表达的逻辑关系是一样的。 （ ）2、公式B A ,含相同的命题变项,若B A ∨是重言式,则A 与B 都是重言式。 （ ）3、在命题逻辑中，任何命题公式的主合取范式都是存在的，并且是惟一的。 （ ）4、永真式的主合取范式是1，矛盾式的主析取范式是0。 （ ）5、同一个谓词公式，在不同个体域中，真值不一定相同。 二、单项选择题 1、下列命题是复合命题的是（ ） A 、黄色和蓝色可以调配成绿色； B 、李辛与李未是兄弟； C 、黄色和蓝色都是常用颜色； D 、张辉与王力是同学 ； 2、设p:天下大雨，q:小王乘公共汽车上班，命题“只有天下大雨，小王才乘公共汽车上班”的符号化形式为（ ） A 、p →q ； B 、q →p ； C 、p →┐q ； D 、┐p →q ； 3、公式()p q r ∧?∨的公式类型为（ ） A 、重言式； B 、矛盾式； C 、非重言式的可满足式； 4、下列联结词集是联结词完备集的是（ ） A 、{,,}∧∨→； B 、{,}?→； C 、{,,}∨→?； D 、{,,,}∧∨→?； 5、设解释I 如下：个体域D={a,b},F(a,a)=(b,b)=0,F(a,b)=F(b,a)=1，在解释I 下，下列公式中真值为1的是（ ） A 、(,)x yF x y ??； B 、(,)x yF x y ??； C 、(,)x yF x y ??； D 、(,)y xF x y ??； 三、填空题 1、公式)(q p ??与)()(q p q p ∧?∨?∧共同的成真赋值为 。 2、设命题公式A 为含命题变项,p q r ,的重言式，则公式(())A p q r ∨∧→的类型为 。
第一章 命题逻辑 习题1.11．解 ⑴不是陈述句，所以不是命题。 ⑵x 取值不确定，所以不是命题。 ⑶问句，不是陈述句，所以不是命题。 ⑷惊叹句，不是陈述句，所以不是命题。 ⑸是命题，真值由具体情况确定。 ⑹是命题，真值由具体情况确定。 ⑺是真命题。 ⑻是悖论，所以不是命题。 ⑼是假命题。 2．解 ⑴是复合命题。设p ：他们明天去百货公司；q ：他们后天去百货公司。命题符号化为q p ∨。 ⑵是疑问句，所以不是命题。 ⑶是悖论，所以不是命题。 ⑷是原子命题。 ⑸是复合命题。设p ：王海在学习；q ：李春在学习。命题符号化为p ∧q 。 ⑹是复合命题。设p ：你努力学习；q ：你一定能取得优异成绩。p →q 。 ⑺不是命题。 ⑻不是命题 ⑼。是复合命题。设p ：王海是女孩子。命题符号化为：?p 。 3．解 ⑴如果李春迟到了，那么他错过考试。 ⑵要么李春迟到了，要么李春错过了考试，要么李春通过了考试。 ⑶李春错过考试当且仅当他迟到了。 ⑷如果李春迟到了并且错过了考试，那么他没有通过考试。 4．解 ⑴?p →(q ∨r )。⑵p →q 。⑶q →p 。⑷q → p 。 习题1.2 1．解 ⑴是1层公式。 ⑵不是公式。 ⑶一层： p ∨q ，?p 二层：?p ?q 所以，)()(q p q p ??→∨是3层公式。 ⑷不是公式。 ⑸(p →q )∧?(?q ?( q →?r ))是5层公式，这是因为 一层：p →q ，?q ，?r 二层：q →?r 三层：?q ?( q →?r ) 四层：?(?q ?( q →?r )) 2．解 ⑴A =(p ∨q )∧q 是2层公式。真值表如表2-1所示： 表2-1 ⑵p q p q A →→∧= )(是3层公式。真值表如表2-2所示：
一、培养目标 信息科学技术学院(以下简称信息学院)本科培养方案面向电子信息科学与技术、计算机科学与技术、自动化、微电子学、示范性软件学院的计算机软件等五个专业，从2003级开始实行多学科交叉背景下、通识教育基础上的宽口径专业教育，构建具有各专业共性基础的学院平台课程体系以及具有一定特长的专业核心课程体系，强调对学生进行基本理论、基础知识、基本能力(技能)以及健全人格、综合素质和创新精神培养，为学生提供增强基础、选择专业的机制，培养基础厚、专业面宽、具有自主学习能力的复合型人才。 从2011级开始，信息学院对培养方案进行了全面修订，进一步将学科交叉范围扩大到专业核心课程体系，为学生提供更加灵活的选课机制和更加宽广的专业空间；并将继续深入研究和不断改进课程内容和教学方法，加强实践环节，更好地培养适应时代要求的信息科学技术专业人才。 信息学院致力于为学生全面参与教育教学、科学研究、文化艺术、社会服务等活动创造条件，提倡学生在参与中发现自己的能力和兴趣，最大限度地发展自己的智力和潜能，鼓励学生敢于面对挑战、不断探索、努力创造、追求卓越，并提供一种基础和环境，促使学生养成独立工作的能力和终身学习的习惯。 二、基本要求 信息学院各专业通过各种教育教学活动发展学生个性，培养学生具有健全人格；具有成为高素质、高层次、多样化、创造性人才所具备的人文精神以及人文、社科方面的背景知识；具有国际化视野；具有创新精神；具有提出、解决带有挑战性问题的能力。具有进行有效的交流与团队合作的能力；在信息科学技术领域掌握扎实的基础理论、相关领域基础理论和专门知识及基本技能，具有在相关领域跟踪、发展新理论、新知识、新技术的能力，能从事相关领域的科学研究、技术开发、教育和管理等工作。 电子信息科学与技术专业的本科生运用所掌握的理论知识和技能，从事信号获取、处理和应用，通信及系统和网络，模拟及数字集成电路设计和应用，微波及电磁技术理论、信号与信息处理的新型电子材料、器件和系统，包括信息光电子和光子器件、微纳电子器件、微光机电系统、大规模集成电路和电子信息系统芯片的理论和应用等方面的科研、开发与教育工作。 微电子学专业的本科生运用所掌握的理论知识和技能，从事大规模模拟及数字集成电路设计和应用，工艺开发，EDA工具开发，新型电子材料、微纳电子器件和系统，量子信息和电子信息系统的理论和应用等方面的科研、开发与教育工作。培养基础扎实，创新能力突出，有国际视野的微纳电子专业人才。 计算机科学与技术专业的本科生运用所掌握的理论知识和技能，从事计算机科学理论、计算机系统结构、计算机网络、计算机软件及计算机应用技术等方面的科研、开发与教育工作。 自动化专业的本科生运用所掌握的理论知识和技能，从事国民经济、国防和科研各部门的运动控制、过程控制、机器人智能控制、导航制导与控制，现代集成制造系统、模式识别与智能系统、生物信息学、人工智能与神经网络、系统工程理论与实践、新型传感器、电子与自动检测系统、复杂网络与计算机应用系统等领域的科学研究、技术开发、教育及管理等工作。 计算机软件专业的本科毕业生应该具备扎实的软件理论和软件工程专业基础知识，具有良好的工具使用与实验能力、软件分析与开发能力、过程控制与管理能力、团队协作与沟通能力。 三、学制与学位授予
选择题 1.设P :他在听音乐，Q :他学习，将命题“他在学习或在听音乐”符号化正确的是（ ） A.P →Q B.P ∧Q C.P ∨Q D.Q →?P 2.下列命题公式不是．． 永真式的是( ) A.()P Q P →→ B.()P Q →∨P C.P ?∨()Q P → D.()P Q P →→ 3.下列等价式正确的是（ ） A.()()()()x A x x A x ????? B.()()()(())A x B x x A B x →???→ C.()(())()()x A x B x A x B ?→??→ D.()(())()()x A x B x A x B ?→??→ 4.设A(x):x 是鸟，B(x):x 会飞，命题“有的鸟不会飞”符号化为（ ） A.()(()x A x ??∧())B x B.()(()x A x ??∧())B x C.()(()())x A x B x ??→ D.()(()())x A x B x ??→ 5.设X ={,{},{,}}a a ??，则下列陈述正确的是（ ） A.a X ∈ B.{,}a X ?? C.{{,}}a X ?? D.{}X ?∈ 6.设A B B = ,则有（ ） A.A B A = B.A B -=? C.A B B = D.A B ? 7.设A =｛a ,{b , c }｝,则其幂集P （A ）的元素总个数为（ ） A.3 B.4 C.6 D.8 8.在整数集Z 上，下列定义的运算满足结合律的是（ ） A.1a b b *=+ B.1a b a *=- C.1a b ab *=- D.1a b a b *=++ 9.设
清华大学计算机系培养方案一
信息科学技术学院 本科指导性教学计划 第一年 课程编号课程名称学分周学时考核方式说明及主要先修课 12090043 军事理论与技能训练3 3 考查 秋季学期 课程编号课程名称学分周学时考核方式说明及主要先修课 107 1 体育(1) 1 2 考查 10610183 思想道德修养与法律基础3 2 考查 10640532 英语（1） 2 2 考查 10420874 一元微积分 4 4 考试 10420904 几何与代数(1) 4 4 考试 0412 工程图学基础 2 2 考试 2选1 20240023 离散数学(2) 3 3 考试 程序设计课组 3 3 考试选１门，详见附录2 30210041 信息科学技术概论 1 1 考查 文化素质选修课≥1 1
合计≥21 注：计算机科学与技术专业必修“离散数学(2)”，其它专业必修“工程图学基础”。 春季学期 课程编号课程名称学分周学时考核方式说明及主要先修课 107 1 体育(2) 1 2 考查 10610193 中国近现代史纲要 3 2 考试 10640682 英语（2） 2 2 考查 10420884 多元微积分 4 4 考试先修一元微积分 10421002 几何与代数(2) 2 2 考试 大学物理课组1 4 4 考试先修一元微积分 20220214 电路原理 4 4 考试 20220221 电路原理实验 1 1 考查 合计≥21 夏季学期 课程编号课程名称学分周学时考核方式说明及 主要先修课 - 3 -
- 4 - 21510192 电子工艺实习（集中） 2 考查 2周 程序训练课组 2 考查 3周 合计： 4 第二年 秋季学期 课程编号 课程名称 学分 周学时 考核方式 说明及 主要先修课 107 1 体育(3) 1 2 考查 10610204 马克思主义基本原理 4 3 考试 10420892 高等微积分B 2 2 考试 10420252 复变函数引论 2 2 考试 304 3 复分析 3 3 考试 大学物理课组2 4 4 考试 见附录2 10430782 物理实验A(1) 2 2 考查 10430801 物理实验B(1) 1 1 考查 电子基础课组１ 3 3 考试 电子基础课组２ 3 3 考试 21550012 电子技术实验 2 2 考查 文化素质选修课 ≥1 2 10420262 数理方程引论 2 2 考查 20240013 离散数学(1) 3 3 考试 3选1 选1门，详见2选1，大学 2选1，一元微
离散数学（第五版）清华大学出版社第1章习题解答 1．1 除（3），（4），（5），（11）外全是命题，其中，（1），（2），（8），（9），（10），（14），（15）是简单命题，（6），（7），（12），（13）是复合命题。 分析首先应注意到，命题是陈述句，因而不是陈述句的句子都不是命题。 本题中，（3）为疑问句，（5）为感叹句，（11）为祈使句，它们都不是陈述句，所以它们都不是命题。 其次，4）这个句子是陈述句，但它表示的判断结果是不确定。又因为（1），（2），（8），（9），（10），（14），（15）都是简单的陈述句，因而作为命题，它们 都是简单命题。（6）和（7）各为由联结词“当且仅当”联结起来的复合命题，（12）是由联结词“或”联结的复合命题，而（13）是由联结词“且”联结起来 的复合命题。这里的“且”为“合取”联结词。在日常生活中，合取联结词有许 多表述法，例如，“虽然……，但是……”、“不仅……，而且……”、“一面……，一面……”、“……和……”、“……与……”等。但要注意，有时“和”或“与” 联结的是主语，构成简单命题。例如，（14）、（15）中的“与”与“和”是联结 的主语，这两个命题均为简单命题，而不是复合命题，希望读者在遇到“和”或“与”出现的命题时，要根据命题所陈述的含义加以区分。 1．2 （1）p: 2是无理数，p为真命题。 （2）p:5能被2整除，p为假命题。 （6）p→ｑ。其中，p:2是素数，q：三角形有三条边。由于p与q都是真 命题，因而p→ｑ为假命题。 （7）p→ｑ，其中，p：雪是黑色的，q：太阳从东方升起。由于p为假命 题，q为真命题，因而p→ｑ为假命题。 （8）p:2000年10月1日天气晴好，今日（1999年2月13日）我们还不 知道p的真假，但p的真值是确定的（客观存在的），只是现在不知道而已。（9）p：太阳系外的星球上的生物。它的真值情况而定，是确定的。 1 （10）p：小李在宿舍里. p的真值则具体情况而定，是确定的。 （12）p∨q，其中，p:4是偶数，q:4是奇数。由于q是假命题，所以，q 为假命题，p∨q为真命题。
离散数学（第五版）清华大学出版社第1章习题解答1．1除（3），（4），（5），（11）外全是命题，其中，（1），（2），（8），（9），（10），（14），（15）是简单命题，（6），（7），（12），（13）是复合命题。 分析首先应注意到，命题是陈述句，因而不是陈述句的句子都不是命题。 本题中，（3）为疑问句，（5）为感叹句，（11）为祈使句，它们都不是陈述句，所以它们都不是命题。 其次，4）这个句子是陈述句，但它表示的判断结果是不确定。又因为（1），（2），（8），（9），（10），（14），（15）都是简单的陈述句，因而作为命题，它们都是简单命题。（6）和（7）各为由联结词“当且仅当”联结起来的复合命题，（12）是由联结词“或”联结的复合命题，而（13）是由联结词“且”联结起来的复合命题。这里的“且”为“合取”联结词。在日常生活中，合取联结词有许多表述法，例如，“虽然……，但是……”、“不仅……，而且……”、“一面……，一面……”、“……和……”、“……与……”等。但要注意，有时“和”或“与” 联结的是主语，构成简单命题。例如，（14）、（15）中的“与”与“和”是联结的主语，这两个命题均为简单命题，而不是复合命题，希望读者在遇到“和”或“与”出现的命题时，要根据命题所陈述的含义加以区分。 1．2（1）p:2是无理数，p为真命题。 （2）p:5能被2整除，p为假命题。 （6）p→q。其中，p:2是素数，q：三角形有三条边。由于p与q都是真命题，因而p→q为假命题。 （7）p→q，其中，p：雪是黑色的，q：太阳从东方升起。由于p为假命可编辑范本 题，q为真命题，因而p→q为假命题。 （8）p:2000年10月1日天气晴好，今日（1999年2月13日）我们还不知道p的真假，但p的真值是确定的（客观存在的），只是现在不知道而已。
离散数学（第五版）清华大学出版社第6章习题解答 6.1 A:⑨; B:⑨; C:④; D:⑥; E:③ 分析对于给定的集合和运算判别它们是否构成代数系统的关键是检查集合对 给定运算的封闭性,具体方法已在 5.3节做过说明. 下面分别讨论对各种不同代数系纺的判别方法. 1°给定集合S和二元运算°,判定
离散数学（第五版）清华大学出版社第7章习题解答 7.1 (1),(2),(3),(5)都能构成无向图的度数列,其中除(5)外又都能构成无向简单图的度数列. 分析1°非负整数列d,d ,L,d 能构成无向图的度数列当且仅当n di为 1 2n∑ i=1偶数,即d1,d2,L,dn中的奇数为偶数个.（1）,(2),(3),(5)中分别有4个,0个,4个,4 个奇数,所以,它们都能构成无向图的度数列,当然,所对应的无向图很可能是非简 单图.而(4)中有 3 个奇数,因而它不能构成无向图度数列.否则就违背了握手定理的推论. 2°(5) 虽然能构成无向图的度数列,但不能构成无向简单度数列.否则,若存在无向简单图G,以1,3,3,3 为度数列,不妨设G 中顶点为v1,v2,v3,v4,且d(vi)=1,于是d(v2)=d(v3)=d(v4)=3.而v1只能与v2,v3,v4之一相邻,设v1与v2相邻,这样一来,除v2能达到3度外, v3,v4都达不到3度,这是矛盾的. 在图7.5所示的4个图中,(1) 以1为度数列,(2)以2为度数列,(3)以3为度数列,(4)以4为度数列(非简单图). 7.2 设有几简单图D以2,2,3,3为度数列,对应的顶点分别为v1,v2,v3,v4,由于d(v)=d+(v)+d_(v),所示,d+(v)-d-(v)=2-0=2,d+(v )=d(v )-d-(v ) 11222=2-0=2,d+(v)=d(v)-d-(v)=3-2=1,d+(v)=d(v)-d-(v)=3-3=0 333444 81 由此可知,D 的出度列为2,2,1,0,且满足d+(v)= d-(v).请读者画出 ∑i∑ｉ 一个有向图.以2,2,3,3为度数列,且以0,0,2,3为入度列,以2,2,1,0为出度列. 7.3 D 的入度列不可能为1,1,1,1.否则,必有出度列为2,2,2,2(因为d(v)=d+(v)+d-(v)),)此时,入度列元素之和为4,不等于出度列元素之和8,这违背握手定理.类似地讨论可知,1,1,1,1也不能为D的出席列. 7.4 不能. N阶无向简单图的最大度Δ≤n-1.而这里的n个正整数彼此不同,因而这n个数不能构成无向简单图的度数列,否则所得图的最大度大于n,这与最大度应该小于等于n-1矛盾.
第一章部分课后习题参考答案 16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 （1）p∨(q∧r)?0∨(0∧1) ?0 （2）（p?r）∧(﹁q∨s) ?（0?1）∧(1∨1) ?0∧1?0. （3）（?p∧?q∧r）?(p∧q∧﹁r) ?（1∧1∧1）? (0∧0∧0)?0 (4)（?r∧s）→(p∧?q) ?（0∧1）→(1∧0) ?0→0?1 17．判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。” 答：p: π是无理数 1 q: 3是无理数0 r: 2是无理数 1 s:6能被2整除 1 t: 6能被4整除0 命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。 19．用真值表判断下列公式的类型： （4）(p→q) →(?q→?p) （5）(p∧r) ?(?p∧?q) （6）((p→q) ∧(q→r)) →(p→r) 答：（4） p q p→q ?q ?p ?q→?p (p→q)→(?q→?p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式 （5）公式类型为可满足式（方法如上例） （6）公式类型为永真式（方法如上例） 第二章部分课后习题参考答案 3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ?(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 答：(2)（p→(p∨q)）∨(p→r)?(?p∨(p∨q))∨(?p∨r)??p∨p∨q∨r?1 所以公式类型为永真式
离散数学(第五版)清华大学出版社第 4章习题解答 离散数学清华大学出版社第4章习题解答4．1 A：⑤；B：③；C：①；D：⑧；E：⑩4．2 A：②；B：③；C：⑤；D：⑩；E：⑦4．3 A：②；B：⑦；C：⑤；D：⑧；E：④分析题都涉及到关系的表示。先根据题意将关系表示成集合表达式，然后再进行相应的计算或解答，例如，题中的Is ={,}, Es ={,,,} Is ={,,}; 而题中的R={,,,,}. 为得到题中的R须求解方程x+3y=12，最终得到R={,,}. 求RoR有三种方法，即集合表达式、关系矩阵和关系图的主法。下面题的关系分别加以说明。1°集合表达式法将domR,domRUran,ranR的元素列出来，如图所示。然后检查R的每个有序对，若∈R，则从domR中的x到ranR中的y画一个箭头。若danR中的x
经过2步有向路径到达ranR中的y，则∈RoR。图可知RoR={,,,,,}. 如果求FoG，则将对应于G中的有序对的箭头画在左边，而将对应于F中的有序对的箭头画在右边。对应的三个集合分别为domG,ranUdomF,ranF，然后，同样地寻找domG到ranF的2步长的有向路径即可。2°矩阵方法若M是R的关系矩阵，则RoR的关系矩阵就是M·M，也可记作M，在计算2 48 乘积时的相加不是普通加法，而是逻辑加，即0+0=0，0+1=1+0=1+1=1，根据已知条件得?1 0 0 1? ?1 0 0 1? ?1 0 0 1? ?1 0 0 0? ?1 0 0 0? ?1 0 0 1? 2 ?? ?? ?? M =?????=?? ?0 0 0 1? ?0 0 0 1? ?1 0 0 0? ?1 0 0 0? ?1 0 0 0? ?1 0 0 1? M2中含有7个1，说明RoR中含有7个有序对。图图3°关系图方法n’’ 设G是R的关系图。为求R 的关系图G ，无将G 的结点复制到G 中，然后依次检查G的
课程编号：04061101 《离散数学》课程教学大纲 学时：64学分：4 一、教学大纲的说明 1、授课对象：计算机科学与技术专业，四年制本科 2、课程性质：学科基础类必修课 3、任务及要求： 《离散数学》是计算机专业的一门重要专业基础课程。通过本课程的学习，使学生系统理解数理逻辑、集合论、代数系统、图论的基本概念和基本理论，为学生将来从事的软、硬件开发和应用研究打下坚实的基础，培养学生的抽象思维、严格的逻辑推理和创新能力。要求学生熟悉和习惯抽象的符号表示及演算形式，具有使用数学语言和符号系统处理问题的能力、综合运用所学知识分析和解决实际问题的能力，为学习后续课程奠定必要的理论基础。 4、与其它课程的联系： 先修课程：高等数学、线性代数 后续课程：数据结构、操作系统、数据库系统原理 二、教学大纲 1、课程内容： (1) 命题逻辑：命题的概念，命题的符号化，联结词的概念，命题公式的分类及其类型的判定，命 题公式的等值演算，联结词全功能集，对偶式的概念，范式、主范式的概念和性质，推理规则，推理的证明。 (2) 一阶逻辑：个体、个体域、谓词、量词的概念，一阶逻辑中命题的符号化，谓词公式的概念及 其解释，谓词公式类型的判定，约束变项与自由变项的形式和意义，换名规则和代替规则，谓词公式等值式，前束范式，一阶逻辑推理规则，一阶逻辑推理的证明。 (3) 集合的基本概念和运算：集合、子集、全集的概念，集合间关系的概念和性质，幂集的概念和 计算，集合的基本运算，集合中元素的计数问题，包含排斥原理。 (4) 二元关系和函数：有序对的概念，笛卡尔集的概念和计算，二元关系的定义及其表示形式，关 系的各种运算，关系的性质的概念及性质的判定，关系的闭包的概念及闭包的计算，等价关系的概念，等价类、商集、划分的定义和性质，偏序关系的概念及其哈斯图表示，偏序集的最大（小）元、极大（小）元、上（下）界、上（下）确界，函数的定义和性质，函数的复合运算，反函数。 (5) 代数系统的一般性质：二元运算的概念和性质，幺元、零元、逆元的概念和计算，代数系统及 其子代数的概念，代数系统的同态与同构。 (6) 几个典型的代数系统：半群、独异点、群的概念，子群的概念和判定，循环群和置换群的概念
离散数学（第五版）清华大学出版社第4章习题解答4．1 A：⑤；B：③；C：①；D：⑧；E：⑩ 4．2 A：②；B：③；C：⑤；D：⑩；E：⑦ 4．3 A：②；B：⑦；C：⑤；D：⑧；E：④ 分析题4.1-4.3 都涉及到关系的表示。先根据题意将关系表示成集合表达式，然后再进行相应的计算或解答，例如，题4.1中的 Is ={<1,1>,<2,2>}, Es ={<1,1>,<1,2>,<2,1>,<2,2>} Is ={<1,1>,<1,2>,<2,2>}; 而题4.2中的 R={<1,1>,<1,4>,<2,1>,<3,4>,<4,1>}. 为得到题4.3中的R须求解方程x+3y=12，最终得到 R={<3,3>,<6,2>,<9,1>}. 求RoR有三种方法，即集合表达式、关系矩阵和关系图的主法。下面由题 4.2的关系分别加以说明。 1°集合表达式法 将domR,domRUran,ranR的元素列出来，如图4.3所示。然后检查R的每个有序对，若