引言
1、什么是离散数学？
离散数学是研究数学中适用于研究离散对象的那一部分。（这里“离散”的含义是指不同的连接在一起的元素。）
可数集合里发生事的数学方面都是离散数学的研究对象。
离散数学成为一门课程，于上世纪60年代、70年代，与计算机发展并驾齐驱，其内容与传统数学有很大区别；过去的高等数学是连续数学，这里表现的离散结构，是计算机表现的量，现实生活中也有十分广泛的应用。
离散数学特点：散、抽象、应用广泛、
注重数理逻辑推理。
2、对离散数学的认识与离散数学的应用
a、极度抽象抽象到把所有男生都看作1，把所有
女士都看成0来研究,
b、行云流水有了数学分析、高等代数、概率论
知识，关键是数理逻辑思维的能力，方法得当
可以轻松的学习
c、由难变易放下包袱，解放思想，办法多多
d、非常聪明学过离散数学，思维方式上一个新
台阶，对后续课程的学习，以后就业、工作、个性发展等帮助收益匪浅。
e、地位重要从20世纪80年代起，离散数学越
来越受到宠爱，有人戏称，微积分在科学中的皇位有朝一日会让给离散数学的，从应用角度看，很多重大实用项目（如信息技术、战争、密码学、作弊与反作弊技术、催眠术、经济理论等等）的理论模型正是离散数学模型；通过离散数学的理论推导、算法设计与分析、编程与软件制作，上机并付诸实现，离散数学是一种高技术
f、科大王树禾：
“离散数学是数学领域当中数学思想最为活泼、最为深刻和充满矛盾的地方，对数学基础的奠定与巩固，离散数学有着不可替代的作用。同时它富含的文化和人文哲理则是人类现代文明的重要成分。离散数学是一种高文化。”
同时，离散数学是通向所有数学学科计算机学科高级课程的必经之路；考研、就业选择、生活中的推理，离散数学无时不在。
3、离散数学的内容
离散数学每年都有新东西，很容易进入学科前沿，即使过去很过老的内容都有新发现。本专业分四个部分学习
一、集合论
二、代数系统
三、图论
四、数理逻辑
一、关于集合论
集合论的概念和符号是描述数学问题的有力
具。集合是全部数学的最基本的概念之一，是整个数学大夏的基础，数学的每个分支都在使用集合论的语言进行表述和推理。
从1874年开始，29岁的德国数学家康托（GEORG CANTOR）在《数学杂志》上发表了一系列文章，奠定了集合论的发展，同时也受到抨击，称其为“病理学”，当作数学上的疾病……
当时集合论称为朴素的集合论，由于未做完整刻化，导致理论上的不一致，从而产生一些悖论。
例如：RUSSEL的理发师悖论
一个乡村理发师，自夸手艺本村无人可与之相比，宣称他当然不给自己修面的人修面，但却给本村所有自己不修面的人修面；
一天他发生了疑问，他是否应当给自己修面？
由例如：“这句话是谎话”
解决这些问题需要一定的方法，一定的指导思想。19世纪初，一些数学家建立的一系列公理化系统，在此基础上发展研究；发展到形式集合论，但仍然有问题，公理化集合论的相容性当时并没有证明。
POICORE评论说：为了防备狼，羊群已经用篱笆圈起来了，但却不知道羊圈里有没有狼。
集合论尽管有这么多的欠缺和不足，但仍然是数学思想最惊人的产物，与计算机科学及其应用有着极其密切的联系，；集合论在程序语言、数据处理、编译原理等领域中都得到广泛的应用，并且还得到了发展。
二、关于代数系统
高等数学的一个新台阶。
过去学的是运算是+、-、?、÷低级运算，通过代数系统的学习，了解什么是真正运算，也就是抽
象的运算（如1+1=1，1+1=0），这一部分内容也是抽
象代数的内容，是高等数学学习的高级化，也是后续
课程学习的一个转折点。思维的升华与飞跃
三、第三部分是图论
既古老又有发展前途，有很多看似简单但还没解决
的问题，例如
哥尼斯堡七桥问题……
欧洲 18世纪瑞士数学家欧拉
四色问题：1852年伦敦一个叫高思里（GUTHRIE）
的学生
提出如下猜想：
任给一无色地图，每国涂一色，邻国须异色，四
色足矣。
1879年，英国数学家肯菩（KEMPLE）发表了极为巧妙的论证，宣称四色猜想成立，不幸的是，十年后被指出错误；
1976年，英国数学家阿佩尔（APPEL）和哈肯
（HAKEN）
用计算机证实了四色猜想成立，他们用了一百亿个逻辑判断，耗用了1200多个机时，但这种不可视的证明存在用肉眼看不出其真伪的缺点，至于手写证明，还有待于诸辈努力。
粗看四色猜想，平易近人到如此程度，一致于可以向公路上和我们随机相遇的人用不了三分钟就能讲清楚题目的条件和结论；即使是文盲，也可以画出许多实例来验证四色猜想对一些特例可以成立，但它的严格证明，百余年间不知耗费了多少精明的数学家的脑汁，皆不得其结果！
？中国哲学家（狂人）黎鸣的惊人之处在于，他说他在老子和康德思想的共同启发下，只需要一支笔几张纸，就能简洁明快，完全漂亮地证明“四色”定理！
黎鸣,研究哲学,你也可以叫我“思想狂徒”、“哲学乌鸦”。南昌人,1961年毕业于江西大学物
理系,后进入中国科技大学研究生院控制论与系统工程专业。长期进行逻辑学、控制论、文化人
类学等方向的研究,最重要的学术贡献：把哲学的基础从二元论转化为三元论。创立了以“三”为基础的运算规则，并在此基础上重构了逻辑学，从而完成了逻辑学的三元论和多元论转向，以及哲学的第四次
转型——人学的转型。
哲学家黎鸣自称受老子《道德经》启发已破译“四色定理”自称证明“四色”定理来源老子“三生万物”构想。
时报综合报道“如果破解四色定理失败，黎鸣先生愿按照协议，文明地进行自杀；如果破解四色定理成功，方舟子先生愿按照协议，文明地进行自杀……”“哲学乌鸦”之称的黎鸣先生曾经以《西
方哲学死了》震惊四座，8月9日在自己博客又抛出了这份“耸人听闻”的生死对决协议，回击学术打假斗士方舟子的质疑，从而让一学术论战越来越演变成文人相轻的闹剧。
又例如：追捕逃犯问题
1987年，王树禾提出如下追捕问题：逃犯若干，在公路网上流窜，应至少派几名行警，才能把这些罪犯捉拿归案？
又如婚配模型中国邮路问题
四、数理逻辑
LEIBNIZ是数理逻辑的首席创始人，他力主思维计算化，也是计算机发展的基础，通过对数理逻辑的学习，可以使你思维更具理性，更具有跳跃性，头脑更聪明。
例如：中科院考研题2002年（8分）
“鸟会飞，鸭子不是鸟；所以鸭子不会飞”
问上述推理是否正确，并给出证明
例，命题：条条大路通罗马，信计专业学生只有考研才是最好的出路吗？
随着计算机理论的发展，离散数学内容在不断丰富：如组合数学、数论
关于数论 特别是研究方法，离散数学的地位 对人类社会贡献
哥德巴赫猜想
德国的一位中学 教师，名叫哥德巴赫，也是数学家。 一七四二年，哥德巴赫发现，每一个大偶数都可以写成两个素数的和。 他对许多偶数进行了检验，都说明这是确实的。但是这需要给予证明。 因为尚未经过证明，只能称之为猜想。他自己却不能够证明它，就写信请 教那赫赫有名的大数学家欧拉，请他来帮忙作出证明。一直到死，欧拉也 不能证明它。从此这成了一道难题，吸引了成千上万数学家的注意。两百 多年来，多少数学家企图给这个猜想作出证明，都没有成功。
FERMAT 大定理
17世纪法国大数学家
n
n n z y x =+ 3≥n 不定方程无
整数解
1637年前后“我对此命题有一个十分美妙的证明，这里空白太小，写不下”
358年来
引无数英雄竞折腰
1994年普林斯顿大学数学家ANDREW WILES 证明； 96年获沃尔夫奖；98年
FIELDS 奖：毕生为世界数学做出突出贡献不超过40岁的长者。 通过学习，提高认识。
FERMAT 猜想
122
+=n
n F
65537,257,17,5,343210=====F F F F F
67004176415
?=F
……
以上是离散数学的一些认知，带着这些问题去学
习，可以事半功倍。
4、 学习方法的补充：
（1）、笔记 （2）、练习
（3）、课外参考书
第一部分集合论
（第一章…第三章）
一、集合的概念与运算（§1。1 §1。2。）
1、集合：集合是数学中最基本的概念，一般只是
说明。(原生概念)
教材上，集合就是具有某种特点的研究对象的聚合，其中每一个研究对象称为这个集合中的元素。
例、全体男生；全体正整数；602寝室的全体生物
CANTOR是这样描述的：所谓集合，是指我们无意中将一些确定的（元素）、彼此完全不同的客体的总和而考虑为一个整体。这些客体，叫做该集合的元素。或者看作：
集合，是不加定义的一个概念
元素，组成集合的个体
表示方法：用大写字母A，B，C，……，表示集合（抽象）
a等表示元素：用小写字母a,b,c,…，i
设A是一个集合，a是集合A中的元素，
记为
A a∈
、
否则
A a?
。
集合的具体表示：
1）、列举法：A = {}
n
a
a
a,
,
,
2
1
（外延）
2）、描述法（特征法）：
B =
}
{具有的性质
x
x（内含）
例：B =
} {0
2
3
2=
+
-x
x
x
常用集合：Z：全体整数
N: 自然数，从零开始，
Q
Z
N,
,+
+，R
2、子集与幂集
1）、子集：集合中若干元素组成的集合。
A是B的子集，称为B
A?（包含于）
B
A?
定义为
B
x
A
x∈
?
∈
?,。
空集：
φ
不含任何元素，
φ
是任何集合的子集，
即 A A ??φ,。
另
B A = <===> A B B A ??且
（Th1。1）（定义）
例：设A =
}{b a ,，B = }{{}b a b a ,,,,
问二者之间的关系是什么？
解：A ≠B ,
B A B A ?∈且,
∴A 既是B 的子集又是B 的元素。
2）、幂集：集合A 上所有子集构成的集合，称为A
的幂集;记为)(A P ，
即
}
{A
x x A P ?
=
)(
e.g. A =
}{b a ,,
P （A ）= }{{
}b a b a ,,,,φ
e.g. B = }{3,2,1,
P(B)=
}{{}}{{}}{{}}
{B ,3,2,3,1,2,1,3,2,1,φ
e.g.
φ
,
A = P(φ)=}{φ,
B = P(A)=
}
{}{φφ, C = P(B) = ? , P(C) = ?
3、有限集、无限集
基：有限集A所含元素的个数。
记为A
。
思考：
问题1、若A= n , 则)
(A
P = ?
问题2、给定一个集合A，怎样找出其所有的子集？
（用计算机编程的形式）
如
}
{d c b a A,,
,
=
4、集合的运算
1）、并与交
交：
B
A = }
{B
x
A
x
x∈
∈且
并：
B
A = }
{B
x
A
x
x∈
∈或
（二目运算）
2）、全集与补集
全集：研究对象的全体，记为U
补集：集合A之补集，
浅论离散数学的实际应用 摘要： 离散数学是现代数学的重要分支，是研究离散量的结构及相互关系的学科，它在计算机理论研究及软、硬件开发的各个领域都有着广泛的应用。作为一门重要的专业基础课，对于我们电子专业的同学来说，学习离散数学史有其重要现实意义：它不仅能为我们的专业课学习打下基础，也为我们今后将要从事的软、硬件开发和应用研究打下坚实的基础，同时也有助于培养我们的抽象思维、严格的逻辑推理和创新能力。离散数学的应用非常广泛，本文主要研究其在我们所学的重要课程中的应用：数字电路中的门电路设计、软件技术基础中的一些技术以及解决现实生活中的一些问题的应用。 关键字：离散数学、电路设计、软件技术、应用 1.什么是离散数学 1.1简介 离散数学(Discrete mathematics)是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。1.2离散数学的内容 离散数学是传统的逻辑学，集合论（包括函数），数论基础，算法设计，组合分析，离散概率，关系理论，图论与树，抽象代数（包括代数系统，群、环、域等），布尔代数，计算模型（语言与自动机）等汇集起来的一门综合学科。离散数学的应用遍及现代科学技术的诸多领域，它通常研究的领域包括：数理逻辑、集合论、代数结构、关系论、函数论、图论、组合学、数论等。 2.离散数学在门电路设计中的应用 2.1 逻辑门的概念 逻辑门是集成电路中的基本组件。简单的逻辑门可由晶体管组成。这些晶体管的组合可以使代表两种信号的高低电平在通过它们之后产生高电平或者低电平的信号。高、低电平可以分别代表逻辑上的“真”与“假”
第一章命题逻辑的基本概念 一、判断下列语句是否是命题，若是命题是复合命题则请将其符号化 （1）中国有四大发明。 （2）2是有理数。 （3）“请进！” （4）刘红和魏新是同学。 （5）a+b （6）你去图书馆吗？ （7）如果买不到飞机票，我哪儿也不去。 （8）侈而惰者贫，而力而俭者富。（韩非：《韩非子?显学》） （9）火星上有生命。 （10）这朵玫瑰花多美丽啊！ 二、将下列命题符号化，其中p:2<1,q:3<2 （1）只要2<1，就有3<2。 （2）如果2<1，则3≥2。 （3）只有2<1，才有3≥2。 （4）除非2<1，才有3≥2。 （5）除非2<1，否则3≥2。 （6）2<1仅当3<2。 三、将下列命题符号化 (1)小丽只能从筐里拿一个苹果或一个梨。 (2)王栋生于1992年或1993年。 - 1 -
四、设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。（1）p∨(q∧r) （2）（p?r）∧(﹁q∨s) （3）（?p∧?q∧r）?(p∧q∧﹁r) (4)（?r∧s）→(p∧?q) 五．判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。” 六、用真值表判断下列公式的类型： (1) p∧(p→q)∧(p→?q) (2) (p∧r) ?(?p∧?q) (2)((p→q) ∧(q→r)) →(p→r) - 2 -
第二章命题逻辑等值演算 一、用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ?(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 二、用等值演算法证明下面等值式 (1)(p→q)∧(p→r)?(p→(q∧r)) (2)(p∧?q)∨(?p∧q)?(p∨q) ∧?(p∧q) - 3 -
集合论部分 第四章、二元关系和函数 集合的笛卡儿积与二元关系有序对 定义由两个客体x 和y，按照一定的顺序组成的 二元组称为有序对，记作
不适合交换律A B B A (A B, A, B) 不适合结合律 (A B)C A(B C) (A, B)对于并或交运算满足分配律 A(B C)=(A B)(A C) (B C)A=(B A)(C A) A(B C)=(A B)(A C) (B C)A=(B A)(C A) 若A或B中有一个为空集，则A B就是空集. A=B= 若|A|=m, |B|=n, 则 |A B|=mn 证明A(B C)=(A B)(A C) 证任取
离散数学（第五版）清华大学出版社第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)
一、请给出一个集合A，并给出A上既具有对称性，又具有反对称性的关系。（10分）解：A={1,2} R={（1,1），（2,2）} 二、请给出一个集合A，并给出A上既不具有对称性，又不具有反对称性的关系。（10分）集合A={1,2,3} A上关系{<1,2>,<2,1>,<1,3>}，既不具有对称性，又不具有反对称性 三、设A={1，2}，请给出A上的所有关系。（10分） 答：A上的所有关系: 空关系，{<1,1>,<1,2>,<2,1>,<2,2>} {<1,1>} {<1,2>} {<2,1>} {<2,2>} {<1,1>,<1,2>} {<1,1>,<2,1>} {<1,1>,<2,2>} {<1,2>,<2,1>} {<1,2>,<2,2>} {<2,1>,<2,2>} {<1,1>,<1,2>,<2,1>} {<1,1>,<1,2>,<2,2>}
{<1,2>,<2,1>,<2,2>} {<1,1>,<2,1>,<2,2>} 四、设A={1，2，3}，问A 上一共有多少个不同的关系。（10分） 设A={1，2，3}，A 上一共有2^(3^2)=2^9=512个不同的关系。 五、证明： 命题公式G 是恒真的当且仅当在等价于它的合取范式中，每个子句均至少包含一个原子及其否定。（10分） 证明：设公式G 的合取范式为：G ’=G1∧G2∧…∧Gn 若公式G 恒真，则G ’恒真，即子句Gi ；i=1,2,…n 恒真 为其充要条件。 Gi 恒真则其必然有一个原子和它的否定同时出现在Gi 中，也就是说无论一个解释I 使这个原子为1或0 ，Gi 都取1值。 若不然，假设Gi 恒真，但每个原子和其否定都不同时出现在Gi 中。则可以给定一个解释I ，使带否定号的原子为1，不带否定号的原子为0，那么Gi 在解释I 下的取值为0。这与Gi 恒真矛盾。 因此，公式G 是恒真的当且仅当在等价于它的合取范式中，每个子句均至少包含一个原子及其否定。 六、若G=(P ，L)是有限图，设P(G)，L(G)的元数分别为m ，n 。证明：n ≤2m C ，其中2m C 表 示m 中取2的组合数。（10分） 证明：如果G=(P,L)为完全图，即对于任意的两点u 、v （u ≠v ）,都有一条边uv ，则此时对于元数为m 的P(G)，L(G)的元数取值最大为C m 2。因此，若G=(P,L)为一有限图，设P(G)的元数为m ，则有L(G)
《离散数学》模拟试题3 一、填空题（每小题2分，共20分） 1. 已知集合A ={φ，1，2}，则A得幂集合p（A）=_____ _。 2. 设集合E ={a, b, c, d, e}, A= {a, b, c}, B = {a, d, e}, 则A∪B =___ ___， A∩B =____ __，A－B =___ ___，～A∩～B =____ ____。 3. 设A，B是两个集合，其中A= {1, 2, 3}, B= {1, 2}，则A－B =____ ___， ρ（A）－ρ（B）=_____ _ _。 4. 已知命题公式R Q P G→ ∧ ? =) (，则G的析取范式为。 5. 设P：2＋2＝4，Q：3是奇数；将命题“2＋2＝4，当且仅当3是奇数。”符号化 ，其真值为。 二、单项选择题（选择一个正确答案的代号填入括号中，每小题4分，共16分。） 1. 设A、B是两个集合，A＝{1,3,4}，B＝{1,2}，则A－B为（）. A.{1} B. {1, 3} C. {3,4} D. {1,2} 2. 下列式子中正确的有（）。 A. φ＝0 B. φ∈{φ} C. φ∈{a,b} D. φ∈φ 3. 设集合X＝{x, y}，则ρ（X）＝（）。 A. {{x},{y}} B. {φ,{x},{y}} C. {φ,{x},{y},{x, y}} D. {{x},{y},{x, y}} 4. 设集合A＝{1,2,3}，A上的关系R＝{(1,1),(2,2),(2,3),(3,3),(3,2)}， 则R不具备（）. 三、计算题（共50分） 1. （6分）设全集E＝N，有下列子集：A＝{1，2，8，10}，B＝{n|n2<50 ，n∈N}，C＝ {n|n可以被3整除，且n<20 ，n∈N}，D＝{n|2i，i<6且i、n∈N}，求下列集合：（1）A∪(C∩D) （2）A∩(B∪(C∩D)) （3）B－(A∩C) （4）(～A∩B) ∪D 2. （6分）设集合A＝{a, b, c}，A上二元关系R1，R2，R3分别为：R1＝A×A， R2 ＝{(a，a)，(b，b)}，R3 ＝{(a，a)}，试分别用 定义和矩阵运算求R1·R2 ，22R，R1·R2 ·R3 ， (R1·R2 ·R3 )－1 。 3.（6分）化简等价式（﹁P∧（﹁Q∧R））∨（Q∧R）∨（P∧R）. 4.(8分) 设集合A＝{1,2,3}，R为A上的二元关系，且 M R＝ 写出R的关系表达式，画出R的关系图并说明R的性质. 5. （10分）设公式G的真值表如下. 试叙述如何根据真值表求G的 主析取范式和主合取范式，并 写出G的主析取范式和主合取范式. 1 0 0 1 1 0 1 0 0
一、 填空 10% （每小题 2分） 1、}0|{>∧∈=+ x Z x x Z ，*表示求两数的最小公倍数的运算（Z 表示整数集合），对于*运算 的幺元是 ，零元是 。 2、代数系统
A 、1； B 、2； C 、3； D 、4 。 三、判断10% （每小题 2分） 1、（ ）设S={1,2}，则S 在普通加法和乘法运算下都不封闭。 2、（ ）在布尔格是域。 4、（ ）一条回路和任何一棵生成树至少有一条公共边。 5、（ ）没T 是一棵m 叉树，它有t 片树叶，i 个分枝点，则(m-1)i = t-1。 四、证明 38% 1、（8分）对代数系统
离散数学作业布置 第1次作业（P15） 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 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，所以这一段的论述为真。 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 所以公式类型为永真式，最后一列全为1 （5）公式类型为可满足式（方法如上例），最后一列至少有一个1 （6）公式类型为永真式（方法如上例，最后一列全为1）。 第2次作业（P38） 2.3 用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ﹁(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 解：(1) ﹁(p∧q→q) ?﹁(﹁(p∧q) ∨q) ?(p∧q) ∧﹁q?p∧(q ∧﹁q) ? p∧0 ?0 所以公式类型为矛盾式 (2)（p→(p∨q)）∨(p→r) ? (﹁p∨(p∨q))∨(﹁p∨r) ?﹁p∨p∨q∨r?1 所以公式类型为永真式 (3) (p∨q) → (p∧r) ?￢(p∨q) ∨ (p∧r) ? (￢p∧￢q) ∨(p∧r) 易见, 是可满足式, 但不是重言式. 成真赋值为: 000,001, 101, 111
命题逻辑的基本概念 一、单项选择题 1．下列语句中不是命题的有（ ）. A 9+5≤12 B. 1+3=5 C. 我用的电脑CPU 主频是1G 吗D.我要努力学习。 2. 下列语句是真命题为( )． A. 1+2=5当且仅当2是偶数 B. 如果1+2=3，则2是奇数 C. 如果1+2=5，则2是奇数 D. 你上网了吗 3. 设命题公式)(r q p ∧→?,则使公式取真值为1的p ，q ，r 赋值分别是 ( ) 0,0,1)D (0 ,1,0)C (1 ,0,0)B (0 ,0,0)A ( 4. 命题公式q q p →∨ )(为 ( ) (A) 矛盾式 (B) 仅可满足式 (C) 重言式 (D) 合取范式 5. 设p:我将去市里,q ：我有时间． 命题“我将去市里，仅当我有时间时”符号化为为( ) q p q p q p p q ?∨??→→)D ()C ()B ()A (6．设P ：我听课,Q ：我看小说. “我不能一边听课，一边看小说”的符号为（ ） A. Q P ?→ ； B. Q P →?； C. P Q ?∧? ； D. )(Q P ∧? 二、判断下列语句是否是命题，若是命题是复合命题则请将其符号化 （1）中国有四大发明。 （2）2是有理数。 （3）“请进！” （4）刘红和魏新是同学。 （5）a+b （6）如果买不到飞机票，我哪儿也不去。 （8）侈而惰者贫，而力而俭者富。（韩非：《韩非子显学》） （9）火星上有生命。 （10）这朵玫瑰花多美丽啊！ 二、将下列命题符号化，其中p:2<1,q:3<2 （1）只要2<1，就有3<2。 （2）如果2<1，则32。 （3）只有2<1，才有32。 （4）除非2<1，才有32。 （5）除非2<1，否则32。
离散数学作业 软件0943 张凌晨38 李成16 1.设S={1,2,3,4}，定义S上的二元运算*如下： x*y=(xy) mod 5任意x,y属于S 求运算*的运算表. 解(xy) mod 5表示xy除以5的余数，所以运算表如下： 2.设*为Z+上的二元运算，任意x,y属于Z+， x*y=min(x,y),即x和y之中的较小数. (1)求4*6,7*3. (2)*在Z+上是否满足交换律、结合律和幂等律？ (3)求*运算的单位元、零元及Z+中所有可逆元素的逆元.
解 (1)由题得：4*6=min(4,6)=4； 7*3=min(7,3)=3. (2)由题分析知： *运算是取x和y之中的较小数，即x和y调换位置不影响结果，所以*在Z+上满足交换律. *运算满足结合律，因为任意x,y属于Z+，有 (x*y)*z=min(x,y)*z=min(min(x,y),z) x*(y*z)=x*min(y,z)=min(x,min(y,z)) 无论x,y,z三数中哪个较小，*运算的最终结果都是较小的那个，所以满足结合律. *运算满足幂等律，因为在Z+上任意 x*x=min(x,x)=x (3)在Z+中最小的数字是1 任意x属于Z+，有 x*1=1=1*x 所以1是*运算的零元，*运算没有单位元，也没有可逆元素的逆元。
3．令S={a,b},S 上有四个二元运算：*，&,@和#，分别由下表确定. (1)这四个运算中哪些运算满足交换律、结合律、幂等律？ (2)求每个运算的单位元、零元及所有可逆元素的逆元. 解 （1）*，&和@满足交换律；*，@和#满足结合律；#满足幂等律。 （2）*运算没有单位元和可逆元素，a 是零元；&运算的单位元为a ,没有零元,每个元素都是自己的逆元；@运算和#运算没有单位元, 零元和可逆元素.
离散数学（第五版）清华大学出版社第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为真命题。
离散数学(屈婉玲版)第四章部分答案
4.1 （1）设S={1，2}，R 是S 上的二元关系，且xRy 。如果R=Is ，则（A ）；如 果R 是数的小于等于关系，则（B ），如果R=Es ，则（C ）。 （2）设有序对
华南理工大学网络教育学院 2014–2015学年度第一学期 《离散数学》作业 （解答必须手写体上传，否则酌情扣分） 1．设命题公式为?Q∧（P→Q）→?P。 （1）求此命题公式的真值表； （2）求此命题公式的析取范式； （3）判断该命题公式的类型。 解：（1）真值表如下： P Q ?Q P →Q ?Q∧（P→Q）?P ?Q∧（P→Q）→?P 0 0 1 1 1 1 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 1 0 1 0 0 1 （2）?Q∧（P→Q）→?P??(?Q∧(?P∨ Q)) ∨? P ?( Q∨? (?P∨ Q)) ∨? P ?? ( ?P∨ Q) ∨ (Q∨?P) ?1（析取范式） ?(?P∧? Q) ∨ (?P∧ Q) ∨ (P∧? Q) ∨（P∧ Q）（主析取范式） （3）该公式为重言式 2．用直接证法证明 前提：P∨Q，P→R，Q→S 结论：S∨R 解：（1）?S P (2)Q →S P (3) ? Q (1)(2) (4)P∨ Q P
(5)P (3)(4) (6) P → R P (7)R (5)(6) (8)?S→ R （1）（7） 即SVR得证 3．在一阶逻辑中构造下面推理的证明 每个喜欢步行的人都不喜欢坐汽车。每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车。因而有的人不喜欢步行。 令F(x)：x喜欢步行。G(x)：x喜欢坐汽车。H(x)：x喜欢骑自行车。 解：前题：?x (F (x) →?G(x)), ?x (G (x) ∨H (x)) ? x ?H (x) 结论:? x ?F (x) 证：（1）? x ?F (x) p (2) ?H (x) ES(1) (3) ?x (G (x) ∨H (x))P (4)G(c) vH(c)US(3) (5)G(c) T(2,4)I (6)?x (F (x) →?G(x)), p (7)F (c) →?G(c) US(6) (8) ?F (c) T(5,7)I (9)( ? x) ?F (x) EG(8) 4．用直接证法证明： 前提：（?x）（C（x）→W（x）∧R（x）），（?x）（C（x）∧Q（x）） 结论：（?x）（Q（x）∧R（x））。 证： （1）（?x）（C（x）∧Q（x））P (2) C (c) ∧Q（c）ES(1) (3)（?x）（C（x）→W（x）∧R（x））P
离散数学作业7 离散数学数理逻辑部分形成性考核书 面作业 本课程形成性考核书面作业共3次,内容主要分别就是集合论部分、图论部分、数理逻辑部分的综合练习,基本上就是按照考试的题型(除单项选择题外)安排练习题目,目的就是通过综合性书面作业,使同学自己检验学习成果,找出掌握的薄弱知识点,重点复习,争取尽快掌握。本次形考书面作业就是第三次作业,大家要认真及时地完成数理逻辑部分的综合练习作业。 要求:将此作业用A4纸打印出来,手工书写答题,字迹工整,解答题要有解答过程,要求本学期第17周末前完成并上交任课教师(不收电子稿)。并在07任务界面下方点击“保存”与“交卷”按钮,以便教师评分。 一、填空题 1.命题公式()P Q P →∨的真值就是 T 或1 . 2.设P :她生病了,Q :她出差了.R :我同意她不参加学习、 则命题“如果她生病或出差了,我就同意她不参加学习”符号化的结果为 (P ∨Q)→R . 3.含有三个命题变项P ,Q ,R 的命题公式P ∧Q 的主析取范式就是 )()(R Q P R Q P ?∧∧∨∧∧ . 4.设P (x ):x 就是人,Q (x ):x 去上课,则命题“有人去上课.” 可符号化为 ))()((x Q x P x ∧? . 5.设个体域D ＝{a , b },那么谓词公式)()(y yB x xA ?∨?消去量词后的等值式为 ))()(())()((b B a B b A a A ∧∨∨ . 6.设个体域D ＝{1, 2, 3},A (x )为“x 大于3”,则谓词公式(?x )A (x ) 的真值为 F 或0 . 7.谓词命题公式(?x )((A (x )∧B (x )) ∨C (y ))中的自由变元为 y . 8.谓词命题公式(?x )(P (x ) →Q (x ) ∨R (x ,y ))中的约束变元为 x . 三、公式翻译题 1.请将语句“今天就是天晴”翻译成命题公式. P 。，P 则今天是天晴设答:: 2.请将语句“小王去旅游,小李也去旅游.”翻译成命题公式. Q 。P ；，Q P ∧则小李去旅游小王去旅游设答::: 3.请将语句“如果明天天下雪,那么我就去滑雪”翻译成命题公式. Q 。P ；，Q P →则我去滑雪明天下雪设答;:: 4.请将语句“她去旅游,仅当她有时间.”翻译成命题公式.
4、1 (1)设S={1,2},R 就是S 上的二元关系,且xRy 。如果R=Is,则(A);如果R 就是数的小于等于关系,则(B),如果R=Es,则(C)。 (2)设有序对
离散数学（第五版）清华大学出版社第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的真值是确定的（客观存在的），只是现在不知道而已。
《离散数学》课程教学大纲 一、《离散数学》课程说明 课程英文名称：Discrete mathematics 课程类型：考试课 课程性质：专业技术基础课 总学时： 72学时 适用对象：计算机科学与技术专业本科生 先修课程：高等数学线性代数 （一）课程简介 离散数学，是现代数学的一个重要分支，是以研究离散量的结构和相互间的关系为主要目标，其研究对象一般是有限个或可数个元素。 《离散数学》内容主要包括:集合、映射与运算，关系，命题逻辑，谓词逻辑，代数结构，图论，以及几类特殊的图和组合计数.通过该课程可以培养学生的抽象思维和慎密的概括能力，是计算机专业的必修课。 （二）课程性质、目的和任务 《离散数学》课程是为计算机科学与技术专业的学生开设的一门专业基础课程。随着计算机科学的发展和计算机应用领域的日益广泛，迫切需要适当的数学工具来解决计算机科学各个领域中提出的有关离散量的理论问题，离散数学就是适应这种需要而建立的，它综合了计算机科学中所用到的研究离散量的各个数学课题，并进行系统、全面的论述，从而为研究计算机科学及相关学科提供了有利的理论基础和工具。是学习后续专业课程不可缺少的数学工具，如：高级语言、数据结构、编译原理、操作系统、可计算性理论、人工智能、形式语言与自动机、信息管理与检索以及开关理论等，离散数学也是研究自动控制、管理科学、电子工程等的重要工具。 教学的目的是进一步提高学生的抽象思维和逻辑推理能力，为从事计算机的应用提供必要的描述工具和理论基础。并为后续课程的学习打下良好的基础。 （三）与其他课程的联系 除要求学生具有矩阵和矩阵运算方面的一些知识外，离散数学基本上是一门体系独立自行封闭的基础数学课程，但由于它内容抽象，理论性较强，因此它需要学生先期有较好的数学思维的训练。最好将此课程安排在高等数学和线性代数课程之后。
离散数学作业答案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】
离散数学集合论部分形成性考核书面作 业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数 理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题 目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识 点，重点复习，争取尽快掌握。本次形考书面作业是第一次作业，大家要认真及时地 完成集合论部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答 过程，要求本学期第11周末前完成并上交任课教师（不收电子稿）。并在03任务界 面下方点击“保存”和“交卷”按钮，完成并上交任课教师。 一、填空题 1．设集合{1,2,3},{1,2} ==，则P(A)- A B P(B )={{3},{1,3},{2,3},{1,2,3}}，A? B={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3,2>} ． 2．设集合A有10个元素，那么A的幂集合P(A)的元素个数为 1024 ． 3．设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元关系， 则R的有序对集合为{<2,2>,<2,3>,<3,2>,<3,3>} ． 4．设集合A={1, 2, 3, 4 }，B={6, 8, 12}，A到B的二元关系 R＝} ∈ y x∈ y < > = {B , , x , 2 y A x 那么R－1＝{<6,3>,<8,4>} 5．设集合A=｛a, b, c, d｝，A上的二元关系R={
离散数学课后习题答案第四章
第十章部分课后习题参考答案 4．判断下列集合对所给的二元运算是否封闭： （1） 整数集合Z 和普通的减法运算。 封闭,不满足交换律和结合律，无零元和单位元 （2） 非零整数集合普通的除法运算。不封闭 （3） 全体n n ?实矩阵集合 （R ）和矩阵加法及乘法运算，其中n 2。 封闭 均满足交换律，结合律，乘法对加法满足分配律； 加法单位元是零矩阵，无零元； 乘法单位元是单位矩阵，零元是零矩阵； （4）全体n n ?实可逆矩阵集合关于矩阵加法及乘法运算，其中n 2。不封闭 （5）正实数集合 和 运算，其中 运算定义为： 不封闭 因为 +?-=--?=R 1111111ο （6）n 关于普通的加法和乘法运算。 封闭，均满足交换律，结合律，乘法对加法满足分配律 加法单位元是0，无零元； 乘法无单位元（1>n ），零元是0；1=n 单位元是1 （7）A = {},,,21n a a a Λ n 运算定义如下： 封闭 不满足交换律，满足结合律， （8）S = 关于普通的加法和乘法运算。 封闭 均满足交换律，结合律，乘法对加法满足分配律 （9）S = {0,1},S 是关于普通的加法和乘法运算。 加法不封闭，乘法封闭；乘法满足交换律，结合律 （10）S = ,S 关于普通的加法和乘法运算。 加法不封闭，乘法封闭，乘法满足交换律，结合律
10．令S={a ，b}，S 上有四个运算：*，分别有表10.8确定。 (a) (b) (c) (d) (1)这4个运算中哪些运算满足交换律，结合律，幂等律？ (a) 交换律，结合律，幂等律都满足， 零元为a,没有单位元； (b)满足交换律和结合律，不满足幂等律，单位元为a,没有零元 b b a a ==--11, (c)满足交换律,不满足幂等律,不满足结合律 a b a b b a b a a b b a ====οοοοοο)(,)( b b a b b a οοοο)()(≠ 没有单位元, 没有零元 (d) 不满足交换律，满足结合律和幂等律 没有单位元, 没有零元 (1) 求每个运算的单位元，零元以及每一个可逆元素的逆元。 见上 16．设V=〈 N ，+ ，〉，其中+ ， 分别代表普通加法与乘法，对下面给定的每个集合确定它是否 构成V 的子代数，为什么？ （1）S 1= 是 （2）S 2= 不是 加法不封闭 （3）S 3 = {-1，0，1} 不是，加法不封闭 第十一章部分课后习题参考答案 8.设S={0，1，2，3}， 为模4乘法，即 "?x,y ∈S, x y=(xy)mod 4