一、实验目的

熟悉关系的性质，掌握求判断关系性质的方法。

二、实验内容

本实验要求从键盘输入一个关系的关系矩阵，判断该关系是否是自反的、对称的、传递的、反自反的、反对称的。用C语言或MATLAB实现。

三、实验源程序

#define _CRT_SECURE_NO_WARNINGS//避免scanf编译不通过
#include <stdio.h>
#include <stdlib.h>
void Input();//输入关系矩阵
bool Ref();//判断是否自反
bool NoRef();//判断是否反自反
bool Sym();//判断是否对称
bool NoSym();//判断是否反对称
bool Tra();//判断是否传递
int matrix[100][100]{ 0 };
int line;
int main()
{
	Input();
	if (Ref())
		printf("该关系是自反的\n");
	if (NoRef())
		printf("该关系是反自反的\n");
	if (Sym())
		printf("该关系是对称的\n");
	if (NoSym())
		printf("该关系是反对称的\n");
	if (Tra())
		printf("该关系是传递的！\n");
	return 0;
}
 
void Input()
{
	printf("请输入关系矩阵的行列数(行列数小于等于100)：\n");
	scanf("%d", &line);
	if (line > 100 || line < 1)//判断行列数是否合法
	{
		printf("非法输入！\n");
		exit(0);
	}
	printf("请输入关系矩阵：\n");
	for (int i = 0;i < line;i++)
	{
		for (int j = 0;j < line;j++)
		{
			scanf("%d", &matrix[i][j]);
			if (matrix[i][j] >= 2 || matrix[i][j] < 0)
			{
				printf("输入关系矩阵错误\n");
				exit(0);
			}
		}
	}
}
bool Tra()
{
	for (int i = 0;i < line;i++)
	{
		for (int j = 0;j < line;j++)//二重数组遍历关系矩阵
		{
			if (matrix[i][j] == 1)//如果第i行j列的元素是1
			{
				for (int k = 0;k < line;k++)//开始搜索第j行为1的元素
				{
					if (matrix[j][k] == 1)
					{
						if (matrix[i][k] != 1)
							return false;//如果存在这种情况：第i行第j
//列和第j行第k列的元素均为1，但是第i行第k列的元素不为1，则不具有传递性
					}
				}
			}
		}
	}
	return true;
}
bool Ref()
{
	for (int i = 0;i < line;i++)
	{
		if (matrix[i][i] != 1)
			return false;//只要主对角线元素存在非1元素，即不具有自反性
	}
	return true;
}
bool NoRef()
{
	for (int i = 0;i < line;i++)
	{
		if (matrix[i][i] != 0)//只要对角线存在非0元素，即不具有反自反性
			return false;
	}
	return true;
}
bool Sym()
{
	for (int i = 0;i < line;i++)
	{
		for (int j = 0;j < line;j++)
		{
			if (matrix[i][j] != matrix[j][i])
	//只要第i行第j列元素和第j行第i列元素不相等，即不是对称矩阵，则不具有对称性
				return false;
		}
	}
	return true;
}
bool NoSym()
{
	for (int i = 0;i < line;i++)
	{
		for (int j = 0;j < line;j++)
		{
			if (matrix[i][j] == matrix[j][i] 
			        && (matrix[i][j] == 1 || matrix[j][i] == 1))
	//只要存在两个对称位置元素中，存在一个为1，另一个同样为1，则不具有反对称性
				return false;
		}
	}
	return true;
}

四、实验分析

实验要求利用关系矩阵判断五个性质，我们要了解这些性质在关系矩阵的体现是什么。正如源代码中的注释。之后，码代码是很简单的。

一、实验目的

熟悉关系的性质，掌握求判断关系性质的方法

二、实验内容

定义1 设R是集合X上的二元关系，对任意的x∈X，都满足<x,x>∈R，则R是自反的。
定义2 设R是集合X上的二元关系，对任意的x∈X，都满足<x,x>R，则R是反自反的。
定义3 设R是集合X上的二元关系，对任意的x,y∈X，满足<x,y>∈R<y,x>∈R，则R是对称的。
定义4 设R是集合X上的二元关系，对任意的x,y∈X，满足<x,y>∈R∧<y,x>∈Rx＝y,则R是反对称的。X`
定义5 设R是集合X上的二元关系，对任意的x,y,z∈X，满足<x,y>∈R∧<y,z>∈R<x,z>∈R,则R是传递的。
本实验要求从键盘输入一个关系的关系矩阵，判断该关系是否是自反的、对称的、传递的、反自反的、反对称的。用C语言或MATLAB实现。

三、实验源程序及结果截图
1.实验源程序：

#include <stdio.h>
#include <stdlib.h>

int main() {
	int i,j,n;
	//输入关系矩阵，只能输入0或1，若不是0或1，提示输入错误并结束程序 
	printf("请输入关系矩阵阶数n：\n");
	scanf("%d",&n);
	int a[n][n];
	printf("请输入关系矩阵真值（0或1）：\n");
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			scanf("%d",&a[i][j]);
		}
	}
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			if(a[i][j]!=0&&a[i][j]!=1){
				printf("输入错误！");
				return 0;
			}
		}
	}
	//判断是否为自反矩阵（自反矩阵主对角线元素全为1） 
	for(i=0;i<n;i++){
		if(a[i][i]!=1)break; 	
	}
	if(i==n)printf("该关系矩阵是自反的\n");
	else if(i<n)printf("该关系矩阵不是自反的\n");
	//判断是否为反自反矩阵（反自反矩阵主对角线元素全为0）
	 for(i=0;i<n;i++){
		if(a[i][i]!=0)break; 	
	}
	if(i==n)printf("该关系矩阵是反自反的\n");
	else if(i<n)printf("该关系矩阵不是反自反的\n");
	//判断是否为对称矩阵（对称矩阵a[i][j]==a[j][i]）
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			if(a[i][j]!=a[j][i])break;			
		}
	}
	if(i>=n&&j>=n)printf("该关系矩阵是对称的\n");
	else  printf("该关系矩阵不是对称的\n");
	//判断是否为反对称矩阵（反对称矩阵中i!=j时，a[i][j]和a[j][i]不能同时为1）
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			if(i!=j){
				if(a[i][j]==1&&a[j][i]==1)break;
			}			
		}
	}
	if(i>=n&&j>=n)printf("该关系矩阵是反对称的\n");
	else  printf("该关系矩阵不是反对称的\n");
	//判断是否为传递矩阵（传递矩阵若a[i][j]==1并且a[j][k]==1则a[i][k]一定为1）
	int k;
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			for(k=0;k<n;k++){
				if(a[i][j]==1&&a[j][k]==1){
					if(a[i][k]!=1)break;
				}
			}
						
		}
	}
	if(i>=n&&j>=n&&k>=n)printf("该关系矩阵是传递的\n");
	else  printf("该关系矩阵不是传递的\n");
	return 0;
}

一、常见的关系的性质

---

在 自然数集 N = { 0 , 1 , 2 , ⋯   } N=\{ 0, 1,2, \cdots \} N={0,1,2,⋯} 上 , 如下关系的性质 :

1. 小于等于关系 ：

小于等于关系 :

符号化描述 : ≤ = { < x , y > ∣ x ∈ N ∧ y ∈ N ∧ x ≤ y } \leq = \{ <x, y> | x \in N \land y \in N \land x \leq y \} ≤={<x,y>∣x∈N∧y∈N∧x≤y}

关系性质 : 自反 , 反对称 , 传递

2. 大于等于关系 ：

大于等于关系 :

符号化描述 : ≥ = { < x , y > ∣ x ∈ N ∧ y ∈ N ∧ x ≥ y } \geq = \{ <x, y> | x \in N \land y \in N \land x \geq y \} ≥={<x,y>∣x∈N∧y∈N∧x≥y}

关系性质 : 自反 , 反对称 , 传递

3. 小于关系 ：

小于关系 :

符号化描述 : < = { < x , y > ∣ x ∈ N ∧ y ∈ N ∧ x < y } < = \{ <x, y> | x \in N \land y \in N \land x < y \} <={<x,y>∣x∈N∧y∈N∧x<y}

关系性质 : 反自反 , 反对称 , 传递

4. 大于关系 ：

大于关系 :

符号化描述 : > = { < x , y > ∣ x ∈ N ∧ y ∈ N ∧ x > y } > = \{ <x, y> | x \in N \land y \in N \land x > y \} >={<x,y>∣x∈N∧y∈N∧x>y}

关系性质 : 反自反 , 反对称 , 传递

5. 整除关系 :

整除关系 :

符号化描述 : ∣ = { < x , y > ∣ x ∈ N ∧ y ∈ N ∧ x ∣ y } | = \{ <x, y> | x \in N \land y \in N \land x | y \} ∣={<x,y>∣x∈N∧y∈N∧x∣y}

关系性质 : 反对称 , 传递

$x|y$ 中的 $|$ 符号是整除的意思 , $x$ 整除 $y$ ;

• $x$ 整除 $y$ , $x$ 是除数 (分子) , $y$ 是被除数 (分母) ; $\frac{y}{x}$

• $y$ 能被 $x$ 整除 , $x$ 是除数 (分子) , $y$ 是被除数 (分母) ; $\frac{y}{x}$

• 整除关系中 , 一定要注意 , 只能非 $0$ 整除 $0$ , $0$ 不能整除非 $0$ , 即 $0$ 只能作被除数 , 不能作除数 ;

参考 : 【集合论】二元关系 ( 特殊关系类型 | 空关系 | 恒等关系 | 全域关系 | 整除关系 | 大小关系 ) 三、 整除关系

6. 恒等关系 :

恒等关系 :

符号化描述 : I N = { < x , y > ∣ x ∈ N ∧ y ∈ N ∧ x = y } I_N = \{ <x, y> | x \in N \land y \in N \land x = y \} IN​={<x,y>∣x∈N∧y∈N∧x=y}

关系性质 : 自反 , 对称 , 反对称 , 传递

7. 全域关系 :

全域关系 :

符号化描述 : E N = { < x , y > ∣ x ∈ N ∧ y ∈ N } = N × N E_N = \{ <x, y> | x \in N \land y \in N \} = N \times N EN​={<x,y>∣x∈N∧y∈N}=N×N

关系性质 : 自反 , 对称 , 传递

自反 , 反对称的关系 , 称为偏序关系 ;

二、关系的性质示例

---

关系图关系判定 :

• ① 自反 : 关系图中所有顶点 都有环 ;
• ② 反自反 : 关系图中所有顶点 都没有环 ;
• ③ 对称 : 两个顶点之间 有 $0$ 个或 $2$ 个有向边 ;
• ④ 反对称 : 两个顶点之间 有 $0$ 个或 $1$ 个有向边 ;
• ⑤ 传递 : 前提 $a\to b,b\to c$ 不成立 默认传递 , 前提 $a\to b,b\to c$ 成立 必须满足 $a\to c$ 存在 ;

1. R 1 = { < a , a > , < a , b > , < b , c > , < a , c > } R_1 = \{ <a, a> , <a, b> , <b , c> , <a,c> \} R1​={<a,a>,<a,b>,<b,c>,<a,c>} :

绘制上述关系的关系图 : 反对称 , 传递

自反/反自反 : 有的顶点有环 , 有的顶点没有环 , 自反和反自反都不成立 ;

对称/反对称 : 顶点之间都是 $1$ 条有向边 , 顶点之间只有 $0/1$ 条边 , 是 反对称 的 ;

传递 : $a\to b,b\to c$ 成立 , $a\to c$ 存在 , 传递性 成立 ;

2. R 2 = { < a , a > , < a , b > , < b , c > , < c , a > } R_2 = \{ <a, a> , <a, b> , <b , c> , <c,a> \} R2​={<a,a>,<a,b>,<b,c>,<c,a>} :

绘制上述关系的关系图 : 反对称

自反/反自反 : 有的顶点有环 , 有的顶点没有环 , 自反和反自反都不成立 ;

对称/反对称 : 顶点之间都是 $1$ 条有向边 , 顶点之间只有 $0/1$ 条边 , 是 反对称 的 ;

传递 : $a\to b,b\to c$ 成立 , $a\to c$ 不存在 , 传递性 不成立 ;

3. R 3 = { < a , a > , < b , b > , < a , b > , < b , a > , < c , c > } R_3 = \{ <a, a> , <b, b> , <a,b> , <b,a> , <c,c> \} R3​={<a,a>,<b,b>,<a,b>,<b,a>,<c,c>} :

绘制上述关系的关系图 : 自反 , 对称 , 传递

自反/反自反 : 所有顶点都有环 , 自反性 成立 ;

对称/反对称 : 顶点之间都是 $0$ 或 $2$ 条有向边 , 顶点之间只有 $0/2$ 条边 , 是 对称 的 ;

传递 : 传递性 成立 ;

• 前提 $a\to b,b\to a$ , 对应存在 $a\to a$
• 前提 $b\to a,a\to b$ , 对应存在 $b\to b$

4. R 4 = { < a , a > , < a , b > , < b , a > , < c , c > } R_4 = \{ <a, a> , <a,b> , <b,a> , <c,c> \} R4​={<a,a>,<a,b>,<b,a>,<c,c>} :

绘制上述关系的关系图 : 对称

自反/反自反 : 有的顶点有环 , 有的顶点没有环 , 自反和反自反都不成立 ;

对称/反对称 : 顶点之间都是 $0$ 或 $2$ 条有向边 , 顶点之间只有 $0/2$ 条边 , 是 对称 的 ;

传递 : 传递性 不成立 ;

• 前提 $a\to b,b\to a$ , 对应存在 $a\to a$
• 前提 $b\to a,a\to b$ , 不存在对应的 $b\to b$ , 这里传递性不成立 ;

5. R 5 = { < a , a > , < a , b > , < b , b > , < c , c > } R_5 = \{ <a, a> , <a,b> , <b,b> , <c,c> \} R5​={<a,a>,<a,b>,<b,b>,<c,c>} :

绘制上述关系的关系图 : 自反 , 反对称 , 传递

自反/反自反 : 所有顶点都有环 , 自反性 成立 ;

对称/反对称 : 顶点之间都是 $0$ 或 $1$ 条有向边 , 顶点之间只有 $0/1$ 条边 , 是 反对称 的 ;

传递 : 前提不成立 , 传递性 成立 ;

6. R 6 = { < a , a > , < b , a > , < b , c > , < a , a > } R_6 = \{ <a, a> , <b,a> , <b,c> , <a,a> \} R6​={<a,a>,<b,a>,<b,c>,<a,a>} :

绘制上述关系的关系图 : 没有任何关系

自反/反自反 : 有的顶点有环 , 有的顶点没有环 , 自反和反自反都不成立 ;

对称/反对称 : 顶点之间都是 $1$ 或 $2$ 条有向边 , 顶点之间只有 $0/1$ 条边是反对称 , 顶点之间只有 $0/2$ 条边是对称 , 上述对称/反对称都不成立 ;

传递 : 前提 $a\to b,b\to c$ , 不存在对应的 $a\to c$ , 这里传递性不成立 ;

三、关系运算性质

---

讨论问题 : 指定性质的关系 之间进行运算 , 其结果的性质 ; 如 自反的两个关系 进行逆序合成运算 , 结果扔是自反的 ;

下图中表格的含义是 : 如 第二列 “自反” 与 第三列 “$R_1\cup R_2$” , 交叉的表格位置 , 代表 关系 $R_1$ 与关系 $R_2$ 是自反的 , 其有序对交集是否是自反的 , 如果是 $1$ , 说明是自反的 , 如果没有值 , 说明不是自反的 ;

	自反	反自反	对称	反对称	传递
$R_1^{-1},R_2^{-1}$	$1$	$1$	$1$	$1$	$1$
$R_1\cup R_2^{-1}$	$1$	$1$	$1$
$R_1\cap R_2$	$1$	$1$	$1$	$1$	$1$
$R_1\circ R_2,R_2\circ R_1$	$1$
$R_1-R_2,R_2-R_1$		$1$	$1$	$1$
$\sim R_1,\sim R_2$			$1$