离散数学第五章

离散数学第8章 函数

CHAPTER Eight

离散数学Discrete Mathematics

6/2/2013 9:02 PM

Discrete Math. , Chen Chen

离散数学第8章 函数

CHAPTER Eight

第八章 函数§8.1 函数的定义与性质

§8.2 函数的复合与反函数§8.3 双射函数与集合的基数§8.4一个电话系统的描述实例

6/2/2013 9:02 PM

Discrete Math. , Chen Chen

离散数学第8章 函数

§8.1 函数的定义与性质

CHAPTER Eight

定义8.1 设 F 为二元关系，若 x domF 都存在唯一的 y ranF 使xFy 成立, 则称F为函数。 对于函数F, 如果 xFy,则记y =F(x),并称y为 F 在 x 的值。 例8.1 设F1={<x1,y1>, <x2,y1>, <x3,y2>},F2={<x1,y1>, <x1,y2>}. 则F1是函数， 而F2不是函数。

定义8.2 设F、G是函数，则 F=G F G∧ G F.

注：如果F=G,那么它们满足：(1

离散数学第8章 函数

CHAPTER Eight

离散数学Discrete Mathematics

6/2/2013 9:02 PM

Discrete Math. , Chen Chen

离散数学第8章 函数

CHAPTER Eight

第八章 函数§8.1 函数的定义与性质

§8.2 函数的复合与反函数§8.3 双射函数与集合的基数§8.4一个电话系统的描述实例

6/2/2013 9:02 PM

Discrete Math. , Chen Chen

离散数学第8章 函数

§8.1 函数的定义与性质

CHAPTER Eight

定义8.1 设 F 为二元关系，若 x domF 都存在唯一的 y ranF 使xFy 成立, 则称F为函数。 对于函数F, 如果 xFy,则记y =F(x),并称y为 F 在 x 的值。 例8.1 设F1={<x1,y1>, <x2,y1>, <x3,y2>},F2={<x1,y1>, <x1,y2>}. 则F1是函数， 而F2不是函数。

定义8.2 设F、G是函数，则 F=G F G∧ G F.

注：如果F=G,那么它们满足：(1

2.1 等值式

一、等值式的概念

两公式什么时候代表了同一个命题呢？抽象地看，它们的真假取值完全相同时即代表了相同的命题。

设公式A,B共同含有n个命题变项，可能A或B有哑元，若A与B有相同的真值表，则说明在2n个赋值的每个赋值下，A与B的真值都相同。于是等价式AB应为重言式。

定义2.1 设A,B式两个命题公式，若A,B构成的等价式A

B是等值的，记作A

B.

B为重言式，则称A与

定义中给出的符号不是联结词符，它是用来说明A与B等值（AB是重言式）的一种记法，因而是元语言符号。此记号在下文中频繁出现，千万不要将它与混为一谈，同时也要注意它与一般等号=的区别。 判断等值式有如下方法： 1.真值表

2.等值演算

3.范式

二、用真值表判断公式的等值

例2.1 判断下面两个公式是否等值：

┐(p∨q)与┐p∧┐q

解 用真值表法判断┐(p∨q)

(┐p∧┐q)是否为重言式。此等价式的真值表如表2.1

(┐p∧┐q)。

所示，从表中可知它是重言式，因而┐(p∨q)与┐p∧┐q等值，即┐(p∨q)

其实，在用真值表法判断AB是否为重言式时，真值表的最后一

《离散数学》复习资料 2014年12月

一、单项选择题（每小题3分，本题共15分）

1．若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是( A )．

A． A?B，且A?B B．B?A，且A?B C．A?B，且A?B D．A?B，且A?B 2．设有向图（a）、（b）、（c）与（d）如图一所示，则下列结论成立的是 ( D )．

图一 A．（a）是强连通的 B．（b）是强连通的

C．（c）是强连通的 D．（d）是强连通的 3．设图G的邻接矩阵为

?01100??10011???

?10000???01001????01010??则G的边数为( B )．

A．6 B．5 C．4 D．3

4．无向简单图G是棵树，当且仅当( A )．

A．G连通且边数比结点数少1 B．G连通且结点数比边数少1 C．G的边数比结点数少1 D．G中没有回路． 5．下列公式 ( C

离散数学标准化作业纸 专业班级 学号 姓名 第一章 命题逻辑的基本概念

一、判断下列语句是否是命题，若是命题是复合命题则请将其符号化 （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）

第二部分 集合论

引言

集合是数学中最为基本的概念，又是数学各分支、自然科学及社会科学各领域的最普遍采用的描述工具。集合论是离散数学的重要组成部分，是现代数学中占有独特地位的一个分支。

G.康托尔是作为数学分支的集合论的奠基人。1870年前后，他关于无穷序列的研究导致集合论的系统发展。1874年他发表了关于实数集合不能与自然数集合建立一一对应的有名的证明。1878年，他引进了两个集合具有相等的“势”的概念。然而，朴素集合论中包含着悖论。第一个悖论是布拉利-福尔蒂的最大序数悖论。1901年罗素发现了有名的罗素悖论。1932年康托尔也发表了关于最大基数的悖论。 集合论的现代公理化开始于1908年E.策梅罗所发表的一组公理，经过A.弗兰克尔的加工，这个系统称为策梅罗-弗兰克尔集合论（ZF），其中包括1904年策梅罗引入的选择公理。另外一种系统是冯*诺伊曼-伯奈斯-哥德尔集合论。公理集合论中一个有名的猜想是连续统假设（CH）。K.哥德尔证明了连续统假设与策梅罗-弗兰克尔集合论的相容性，P.J.科恩证明了连续统假设与策梅罗-弗兰克尔集合论的独立性。现在把策梅罗-弗兰克尔集合论与选择公理一起称为ZFC系统。

本部分主要介绍朴素集合论的

第一讲 引言

一、课程内容

·数理逻辑：是计算机科学的基础，应熟练掌握将现实生活中的条件化成逻辑公式，并能做适当的推理，这对程序设计等课程是极有用处的。 ·集合论：数学的基础，对于学习程序设计、数据结构、编译原理等几乎所有计算机专业课程和数学课程都很有用处。熟练掌握有关集合、函数、关系等基本概念。 ·代数结构：对于抽象数据类型、形式语义的研究很有用处。培养数学思维，将以前学过的知识系统化、形式化和抽象化。熟练掌握有关代数系统的基本概念，以及群、环、域等代数结构的基本知识。 ·图论：对于解决许多实际问题很有用处，对于学习数据结构、编译原理课程也很有帮助。要求掌握有关图、树的基本概念，以及如何将图论用于实际问题的解决，并培养其使用数学工具建立模型的思维方式。 ·讲课时间为两个学期，第一学期讲授数理逻辑与集合论，第二学期讲授代数结构和图论。考试内容限于书中的内容和难度，但讲课内容不限于书中的内容和难度。

二、数理逻辑发展史

1. 目的

·了解有关的背景，加深对计算机学科的全面了解，特别是理论方面的了解，而不限于将计算机看成是一门技术或工程性的学科。 ·通过重要的历史事件，了解计算机科学中的一些基本思维方式和一些基本问题。

2. 数理

1 单选(2分)

关于计算机程序，下列叙述正确的是（ ）。 A.只有可执行程序（.exe）才能在计算机中运行。

B.计算机程序是用自然语言书写的关于问题求解的方法和步骤的描述。

C.计算机程序编程人员利用某种计算机程设计语言，根据用户业务需求来编写完成，从概念上讲，计算机程序有数据和代码两部分。 D.用高级程序设计语言书写的程序都可以直接在计算机中运行。 E.从本质上讲，计算机程序是在计算机中运行的指令序列。 正确答案： C、E 2单选(2分)

世界上第一个计算机高级程序设计语言是（ ）。 A.Pascal B.ALGOL C.C D.FORTRAN E.Basic

正确答案： D 你选对了 3 单选(2分)

与计算机硬件系统紧密相关的程序设计语言是（ ）。 A.符号语言 B.脚本语言 C.汇编语言 D.机器语言 E.高级语言

正确答案： D 你选对了 4 单选(2分)

关于计算机软件开发，下列叙述正确的是（ ）。 A.软件开发就是编写程序。

B.软件开发中的生命周期和原型法不能混合使用。

C.软件开发包括几个典型的阶段，包括：需求分析，系统设计，系统实施，系统测试，运行和维护等。 D.软件开发

二、质量 填空

1．小明用量程是200g 的天平测一石块的质量，天平平衡时如图26 所示，由此可知小明使用天平的错误之处是______________________________________

.

超出天平的测量范围（超量程） 2．（2012自贡）台秤是一种称量质量的工具，使用前，将台秤放在水平面上，游码置于零刻线，调节 使秤杆水平平衡，某次称量的情况如下图所示，被称货物的质量是 kg。

平衡螺母 2.2

3．(2012梅州)如图8所示的台秤是称量物体质量的工具。使用前，应先将台秤放在水平面

上，游码置于零刻度，先调节 使秤杆水平平衡，图示中被称量物体的质量是 kg。

调零螺丝 2.2

4.（2012南通）天平调平时，应该调节指针指在 ，使用天平时物体应该放在 。

分度盘的中线处 左盘 选择 5．（2012茂名）小明做“用托盘天平测物体质量”实验时，用已调节好的天平测量物体质量，发现指针静止时指在分度盘的中央刻度线左侧，要使天平平衡，他接着应该 A．把横梁右端螺母向右旋出一些 B．把横梁右端螺母向

第五章习题

一 历年考研真题

07年昆明理工

1、 在自然数集合N上，下列哪种运算是可结合的。（ ） A. a*b=a-b B.a*b=max(a,b) C. a*b=a+2b D.a*b=|a-b|

2 、设Z为整数集合，+为普通加法，则代数系统中,Z对加法的幺元为 _______,Z对+的零元为_______,对任意x∈N,x-1=_______。 3、设是一个代数系统,其中*是一个二元运算使任意a,b∈A,有a*b=a.

(1)证明*运算是可结合的。 （2）说明*运算是否可交换。 06年清华大学

1设是二元代数，元素a∈A有左逆元al-1和右逆元ar-1，若运算?满足（ ）律，则al-1=ar-1

A.结合 B.交换 C.等幂 D. 分配

2 设?为实数集R上的二元运算，?x,y∈R有x?y=x+y-2xy,说明运算?是否为可交换的、可结合的？确定运算?的幺元、零元和所有幂等元及可逆元素的逆元。

二、本章复习纲要

1、已知集合A={1，2，…,10},下面定义的哪些运算关于集合A是不封闭的.( )

A. x*y=max(x,y) B. x*y=min(x,y) C