离散数学二元关系知识点

离散数学二元关系习题及答案

【篇一：离散数学关系部分经典练习及答案】

t>一、单项选择题

1．设集合a = {1, a }，则a的幂集p(a) = ( )． a．{{1}, {a}}b．{?,{1}, {a}}

c．{?,{1}, {a}, {1, a }}d．{{1}, {a}, {1, a }}

2．若集合a的元素个数为10，则其幂集的元素个数为（ ）．

a．1024 b．10c．100d．1 7．集合a={1, 2, 3, 4, 5, 6, 7, 8}上的关系r={x，y|x+y=10且x, y?a}，则r的性质为（ ）． a．自反的b．对称的

c．传递且对称的d．反自反且传递的

8．设集合a = {1，2，3，4，5，6 }上的二元关系r ={?a , b??a , b?a , 且a +b = 8}，则r具有的性质为（ ）． a．自反的 b．对称的

c．对称和传递的d．反自反和传递的

9．如果r1和r2是a上的自反关系，则r1∪r2，r1∩r2，r1-r2中自反关系有（ ）个． a．0 b．2c．1d．3

10．设集合a={1 , 2 , 3 , 4}上的二元关系 r = {?1 , 1?，?2 , 2?

集合论部分

第四章、二元关系和函数

集合的笛卡儿积与二元关系有序对

定义由两个客体x 和y，按照一定的顺序组成的

二元组称为有序对，记作

实例：点的直角坐标(3,4)

有序对性质

有序性 （当x y时）

与 相等的充分必要条件是= x=u y=v

例1 <2, x+5> = <3y4, y>，求x, y.

解 3y 4 = 2, x+5 = y y = 2, x = 3

定义一个有序n (n3) 元组 是一个

有序对，其中第一个元素是一个有序n-1元组，即

= < , x n>

当n=1时, 形式上可以看成有序 1 元组.

实例 n 维向量是有序 n元组.

笛卡儿积及其性质

定义设A,B为集合，A与B 的笛卡儿积记作A B，即A B ={ | x A y B }

例2 A={1,2,3}, B={a,b,c}

A B ={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>,

<3,a>,<3,b>,<3,c>}

B A ={,,,,,,

, ,}

A={}, P(A)A={<,>, <{},>}

性质：

不适合交换律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

平顶山学院毕业论文(设计)

引言

在日常生活中，关系一词是大家在生活学习和工作中经常遇到和处理的概念，我们都熟知关系一词的含义，例如兄弟关系、上下级关系、位置关系等.在数学中关系可抽象为表达集合中元素之间的关系，如“4大于2”，“P在点a，b之间”.

在离散数学中关系是刻画元素之间相互联系的一个重要的概念，广泛应用于计算机科学技术如计算机程序的输入、输出关系，数据库的数据特性关系，其中关系数据库就是以关系及其运算作为理论基础的.近世代数利用等价关系将代数系统进行分类，进而加以研究.关系也是点集拓扑中一个重要概念，通过关系分类来研究集合元素之间的某种联系.熟练掌握关系的定义和性质,也是学好近世代数和点集拓扑的基础.

最基本的关系就是二元关系，就是集合中两个元素之间的某种相关性.例如

B可以从事?，有三个人A,B,C和四项工作?，?，?，?.已知A可以从事?和?，

C可以从事?和?，那么人和工作之间的对应关系可以记作:

R???A,??,?A,??,?B,??,?C,??,?C,???.

这是人的集合?A,B,C?到工作的集合??，?，?，??之间的二元关系.

一 基础知识

定义1?? 设A,B为集合，用A中元素为第一元素，B中元素为第二元素，

第四章 二元关系和函数

第一节、集合的笛卡儿积与二元关系

有序对ordered pair定义:有两个元素x,y(允许x=y)按给定顺序排列组成

的二元组合称为一个有序对 ,记作<x,y>其中x是它的第一元素,y是它的第二元素。例、平面直角坐标系中的一个点的坐标就构成为一个有序 实数对,我们可用<x,y>表示。 注:有序对是讲究次序的,例<1,3>和<3,1>是表示平面 上两个不同的点,这与集合不同,{1,3}和{3,1}是两个相等的 集合。 性质1:如x y即<x,y> <y ,x>。 性质2:<x,y>=<a,b>的充要条件是x=a,y=b.

n元有序对有序对可推广到n个元素，设A1, A2, …, An是 集合，a1 A1, a2 A2, …, an An是元素，定义有 序n元组(ordered n-tuple)为<, an>,注意这是一个归纳(inductive) 定义，将有序 n元组的定义归结为有序 n-1 元组 的定义。 显然有 =

总结 离散数学知识点

第二章 命题逻辑

1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假；

5.求范式时，为保证编码不错，命题变元最好按P,Q,R的顺序依次写； 6.真值表中值为1的项为极小项，值为0的项为极大项；

7.n个变元共有2n个极小项或极大项，这2n为(0~2n-1)刚好为化简完后的主析取加主合取；

8.永真式没有主合取范式，永假式没有主析取范式；

9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P规则，T规则

①真值表法；②直接证法；③归谬法；④附加前提法；

第三章 谓词逻辑

1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n个个体，多元谓词描述个体之间的关系； 2.全称量词用蕴含→，存在量词用合取^;

3.既有存在又有全称量词时，先消存在量词，再消全称量词；

第四章 二元关系 和函数1 2 3 4 5 6 7笛卡尔积与二元关系 关系的运算

关系的性质 关系的闭包 等价关系和偏序关系 函数的定义和性质 函数的复合和反函数

二元关系和函数1DEFINITION 1.

笛卡尔积与二元关系

设n为一正整数，由n个元素x1,x2,…,xn按 一定顺序排列成的一个序列<x1,x2,…,xn>称 为有序n元组。(The ordered n-tuple <x1,x2,…,xn> is the ordered collection that has x1 as its first element, x2 as its second element, … , and xn as its nth element.)2

笛卡尔积与二元关系DEFINITION 2.

设A,B为集合，用A中元素为第一元素，B 中元素为第二元素，构成有序对，所有这样 的有序对组成的集合叫做A和B的笛卡尔积， 记做A×B. (Let A and B be sets. The Cartesian product of A and B, denoted by A×B, is the set of all ordere

第四章 二元关系 和函数1 2 3 4 5 6 7笛卡尔积与二元关系 关系的运算

关系的性质 关系的闭包 等价关系和偏序关系 函数的定义和性质 函数的复合和反函数

二元关系和函数1DEFINITION 1.

笛卡尔积与二元关系

设n为一正整数，由n个元素x1,x2,…,xn按 一定顺序排列成的一个序列<x1,x2,…,xn>称 为有序n元组。(The ordered n-tuple <x1,x2,…,xn> is the ordered collection that has x1 as its first element, x2 as its second element, … , and xn as its nth element.)2

笛卡尔积与二元关系DEFINITION 2.

设A,B为集合，用A中元素为第一元素，B 中元素为第二元素，构成有序对，所有这样 的有序对组成的集合叫做A和B的笛卡尔积， 记做A×B. (Let A and B be sets. The Cartesian product of A and B, denoted by A×B, is the set of all ordere

离散数学第一章知识点总结（仅供参考）

1.判断给定的句子是否为命题的基本步骤：首先应是陈述句；其次要有唯一的真值。 例：（1）我正在说谎。

不是命题。因为无法判定其真假值，若假设它为假即我正在说谎，则意味着它的反为真，即我正在说实话，二者相矛盾；若假定它为真即我正在说实话，则意味着它的反为假，我正在说谎，二者也相矛盾。这其实是一个语义上的悖论。悖论不是命题 （2）x-y ＞2。

不是命题。因为x, y的值不确定，某些x, y使x?y＞2为真，某些x, y使x?y＞2为假，即x?y＞2的真假随x, y的值的变化而变化。因此x?y＞2的真假无法确定，所以x?y＞2不是命题。

2.命题可以分为两种类型：原子命题（不能再分解为更简单命题，又可称为简单命题）； 复合命题(通过联结词、标点符号将原子命题联结而成的命题） 3.命题常元：一个命题标识符如果表示确定的简单命题，就称为命题常元

命题变元：如果一个命题标识符只表示任意简单命题的位置标志，就称它为命题变元 注：当命题变元P用一个特定的简单命题取代时，P才能确定真值，这时也称对P进行指派

4.联接词：（1）否定联

用C程序实现对二元关系性质的判定

ＩＴ技术

数字技术与应用

用Ｃ程序实现对二元关系性质的判定

岳晓红

（陇东学院信息工程学院　　甘肃庆阳　　７４５０００）

摘　要：本文利用Ｃ语言程序实现了对离散数学中二元关系的５种性质的判断。在计算机相关专业的教学中可以培养学生的理论和计算机操作相结合的学习能力。

关键词：Ｃ语言　　离散数学　　二元关系中图分类号：Ｏ１４１．１２文献标识码：Ａ文章编号：１００７－９４１６（２０１１）０２－００７１－０２

Ｔｏ　Ｊｕｄｇｅ　ｔｈｅ　Ｐｒｏｐｅｒｔｙ　ｏｆ　Ｂｉｎａｒｙ　Ｒｅａｌｔｉｏｎｓ　ｂｙ　Ｃ　ｐｒｏｇｒａｍ

Ｙｕｅ　Ｘｉａｏｈｏｎｇ

（Ｓｃｈｏｏｌ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ　　Ｑｉｎｇｙａｎｇ　ｇａｎｓｕ　　７４５０００）

Ａｂｓｔｒａｃｔ：Ｔｈｅ　ｐａｐｅｒ　ｐｒｅｓｅｎｔｓ　ｓｏｍｅ　ｗａｙｓ　ｔｏ　ｊｕｄｇｅ　ｔｈｅ　５　ｐｒｏｐｅｒｔｉｅｓ　ｏｆ　ｂｉｎａｒｙ　ｒｅｌａｔｉｏｎｓ　ｉｎ　ｔｈｅ　ｄｉｓｃｒｅｔｅ　ｍａｔｈｅｍａｔｉｃｓ，　ａｎｄ　ｔｈｅｙ　ｃａｎ　ｂｅ　ａｐｐｌｉｅｄ　ｔｏ　ｃｕｌｔｉｖａｔｅ　ｔｈｅ　ｓｔｕｄｅｎｔｓ’ａｂｉｌｉｔｉｅｓ　ｂｙ　ｉｎｔｅｇｒａｔｉｎｇ　ｔｈ

离散数学

第三章 --- 二元关系

Functions 函数

在实际问题中， 在实际问题中，我们感兴趣的往往不是一般的关 系，而是具有某些特殊性质的关系。为了更好的处理 而是具有某些特殊性质的关系。 这些关系，有必要深入研究关系的性质。 这些关系，有必要深入研究关系的性质。对A上的关系 上的关系 来说，主要的性质有：自反性、非自反性、对称性、 来说，主要的性质有：自反性、非自反性、对称性、 反对称性、传递性。 反对称性、传递性。

2011-2-27

Hongzhi Qiao, XiDian Univ.

离散数学

第三章 --- 二元关系上的关系R, 对A上的关系 ，若对任意的 上的关系 上自反的关系； 称R为A上自反的关系；若对任意的 为 上自反的关系 则称R为 上非自反的关系 则称 为A上非自反的关系 这个定义也可以写成： 这个定义也可以写成： 在A上是自反的 上是自反的 在A上是非自反的 上是非自反的2011-2-27 Hongzhi Qiao, XiDian Univ.

Functions 函数

都有 都有

,则 ，

离散数学

第三章 --- 二元关系如果R是 上自反的 上自反的， 如果 是A上自反的，

Functions 函数

则关系矩阵M(R)的主对角线元素都