关系的定义与性质

一、关系的定义

定 义 A i 是 n 个 集 合 ， 集 合 A 1 × A 2 × . . A n 的 一 个 子 集 F ， 称 为 A 1 , A 2 . . . A n 上 的 一 个 n 元 关 系 。 特 别 地 ， 集 合 A × B 的 一 个 子 集 R ， 称 为 集 合 A 与 B 上 的 一 个 元 关 系 ( b i n a r y r e l a t i o n ) , 简 称 为 关 系 。 对 于 x ∈ A , y ∈ B , R 是 A 与 B 上 的 一 个 二 元 关 系 ， 著 ( x , y ) ∈ R ， 则 称 x ， y 有 关 系 R ， 记 为 x R y ; 着 ( x , y ) ∉ R , 则 称 x ， y 没 有 关 系 R 。 若 B = A ， 则 R 称 为 A 上 的 二 元 关 系 定义A_i是n个集合，\\ 集合A_1×A_2×..A_n的一个子集F， 称为A_1,A_2...A_n上的一个n元关系。\\ 特别地，集合A×B的一个子集R，称为集合A与B上 的一个元关系(binary relation),简称为关系。\\ 对于x\in A, y\in B, R是A与B上的一个二元关系，\\ 著(x,y)\in R，则称x， y有关系R，记为xRy; 着(x,y)\notin R,则称x，y没有关系R。\\ 若B=A，则R称为A上的二元关系 定义Ai​是n个集合，集合A1​×A2​×..An​的一个子集F，称为A1​,A2​...An​上的一个n元关系。特别地，集合A×B的一个子集R，称为集合A与B上的一个元关系(binaryrelation),简称为关系。对于x∈A,y∈B,R是A与B上的一个二元关系，著(x,y)∈R，则称x，y有关系R，记为xRy;着(x,y)∈/​R,则称x，y没有关系R。若B=A，则R称为A上的二元关系

二、关系的性质：

∗ A × A 的 任 一 子 集 都 是 A 上 的 一 个 关 系 ， 若 ∣ A ∣ = n , 则 A 上 的 关 系 有 （ 2 n 2 ） 个 * A×A的任一子集都是A上的一个关系，若|A|=n,则A上的关系有（2^{n^2}）个 ∗A×A的任一子集都是A上的一个关系，若∣A∣=n,则A上的关系有（2n2）个
A × A 的 子 集 的 个 数 ， 也 就 是 A × A 的 幂 集 中 元 素 的 个 数 ： 2 n 2 A×A 的子集的个数，也就是A×A的幂集中元素的个数：2^{n^2} A×A的子集的个数，也就是A×A的幂集中元素的个数：2n2
$\ast A上的三个特殊的关系$

1. $空关系\Phi$
2. 全 域 关 系 E A = A × A 全域关系E_A=A×A 全域关系EA​=A×A
3. 恒 等 关 系 I A = { ( x , x ) ∣ x ∈ A } 恒等关系I_A=\{(x,x)|x\in A\} 恒等关系IA​={(x,x)∣x∈A}

∗ 集 合 A 的 元 素 个 数 为 n , R 是 A 上 的 二 元 关 系 ， 则 有 R i = R j ( 0 ≤ i ≤ j ≤ 2 n 2 ) *集合A的元素个数为n,R是A上的二元关系，则有R^i=R^j(0\leq i\leq j \leq 2^{n^2}) ∗集合A的元素个数为n,R是A上的二元关系，则有Ri=Rj(0≤i≤j≤2n2)
鸽 巢 原 理 ： m 个 鸽 子 飞 进 n 个 巢 ， 至 少 有 一 个 巢 有 ⌈ m n ⌉ 个 或 以 上 个 鸽 子 n 个 数 取 n − 1 个 值 ， 则 必 有 两 个 值 相 等 R i 和 R j 仍 然 是 A 上 的 二 元 关 系 ， 所 以 当 R 的 次 幂 的 个 数 大 于 2 n 2 时 一 定 不 能 再 生 成 新 的 关 系 鸽巢原理：m个鸽子飞进n个巢，至少有一个巢有\lceil \frac{m}{n} \rceil 个或以上个鸽子\\ n个数取n-1个值，则必有两个值相等\\ R^i和R^j仍然是A上的二元关系，所以当R的次幂的个数大于 2^{n^2}时一定不能再生成新的关系 鸽巢原理：m个鸽子飞进n个巢，至少有一个巢有⌈nm​⌉个或以上个鸽子n个数取n−1个值，则必有两个值相等Ri和Rj仍然是A上的二元关系，所以当R的次幂的个数大于2n2时一定不能再生成新的关系

三、二元关系的关系矩阵表示：

关 系 矩 阵 的 表 示 与 行 列 表 示 的 集 合 A , B 中 的 元 素 顺 序 有 关 , 在 关 系 中 如 果 有 ( A i , B j ) , 则 关 系 矩 阵 中 a i , j = 1 , 否 则 为 0 例 . A = { 1 , 2.3.4 } 上 二 元 关 系 R = < 2 ， 4 > ， < 3 ， 3 > ， < 4 ， 2 > ， R 的 关 系 矩 阵 M r 中 m 2 , 4 = ( 1 ) ; m 3 , 4 = ( 0 ) 关系矩阵的表示与行列表示的集合A,B中的元素顺序有关,\\ 在关系中如果有(A_i,B_j) ,则关系矩阵中a_{i,j}=1,否则为0\\例. A=\{1,2.3.4\}上二元关系R={ <2，4>，<3，3>，<4，2> }，R的关系矩阵Mr中m_{2,4}=(1);m_{3,4}= (0) 关系矩阵的表示与行列表示的集合A,B中的元素顺序有关,在关系中如果有(Ai​,Bj​),则关系矩阵中ai,j​=1,否则为0例.A={1,2.3.4}上二元关系R=<2，4>，<3，3>，<4，2>，R的关系矩阵Mr中m2,4​=(1);m3,4​=(0)
M R ∗ S = M R × M S 当 计 算 加 法 时 使 用 逻 辑 加 M_{R*S}=M_{R}×M_{S}当计算加法时使用逻辑加 MR∗S​=MR​×MS​当计算加法时使用逻辑加

四、二元关系的关系图表示：

$$试用有向图表示关系，如果R中有元素（a，b）,则有一条a到b的有向边$$

关系的图与矩阵表示特点：

注意：对称关系与反对称关系不是完全对立的，有些关系既是对称也是反对称的，例如：空关系和恒等关系
传递性：

反对称关系的定义：$集合A上的关系R是反对称的，如果xRy,yRx则必有x=y$

空关系，恒等关系，完全关系是传递的

$\ast 反自反和传递性来推导出反对称$
$$\begin{gathered} 用反证法证明。 \\ 如果关系R不是反对称，则：xRy且yRx。 \\ 又R是传递，所以xRx，即R自反，与题目矛盾。 \end{gathered}$$

二元关系的性质

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！