运用编程计算A上的关系R={<a,b>,<b,a>,<b,c>,<c,d>}的自反闭包、对称闭包、传递闭包,其中A={a,b,c,d}.
时间: 2024-05-01 20:20:04 浏览: 75
首先,我们需要定义一个二维列表来表示关系R,其中列表的行表示元素对,列表的列表示元素。
```python
R = [['a', 'b'], ['b', 'a'], ['b', 'c'], ['c', 'd']]
```
接下来,我们分别计算自反闭包、对称闭包和传递闭包。
1. 自反闭包
自反闭包是指将关系R中的每个元素都加上一个形如 <a,a> 的元素,使得关系R成为自反关系。
遍历A中的每个元素,若该元素在R中不存在,则将其与自身形成一个元素对,并加入到R中。
```python
for a in A:
if [a, a] not in R:
R.append([a, a])
```
此时,R变成了以下形式:
```python
R = [['a', 'b'], ['b', 'a'], ['b', 'c'], ['c', 'd'], ['a', 'a'], ['b', 'b'], ['c', 'c'], ['d', 'd']]
```
2. 对称闭包
对称闭包是指将关系R中所有的对称元素对都加上其反向对,使得关系R成为对称关系。
遍历关系R中的每个元素对,若其反向对不存在于R中,则将其反向对加入到R中。
```python
for pair in R:
if [pair[1], pair[0]] not in R:
R.append([pair[1], pair[0]])
```
此时,R变成了以下形式:
```python
R = [['a', 'b'], ['b', 'a'], ['b', 'c'], ['c', 'd'], ['a', 'a'], ['b', 'b'], ['c', 'c'], ['d', 'd'], ['b', 'a'], ['c', 'b'], ['d', 'c']]
```
3. 传递闭包
传递闭包是指将关系R中所有可传递的元素对都加入到R中,使得关系R成为传递关系。
首先,我们需要定义一个函数来判断两个元素对是否可传递。若存在一个中间元素,使得第一个元素与中间元素有关系,中间元素与第二个元素有关系,则两个元素对可传递。
```python
def is_transitive(pair1, pair2):
if pair1[1] == pair2[0]:
return True
return False
```
接下来,我们使用一个嵌套循环遍历所有元素对,对于每个元素对,再遍历一遍所有元素对,若两个元素对可传递,则将其加入到R中。
```python
for pair1 in R:
for pair2 in R:
if is_transitive(pair1, pair2):
if [pair1[0], pair2[1]] not in R:
R.append([pair1[0], pair2[1]])
```
此时,R变成了以下形式:
```python
R = [['a', 'b'], ['b', 'a'], ['b', 'c'], ['c', 'd'], ['a', 'a'], ['b', 'b'], ['c', 'c'], ['d', 'd'], ['b', 'a'], ['c', 'b'], ['d', 'c'], ['a', 'c'], ['a', 'd'], ['b', 'd']]
```
因此,关系R的自反闭包、对称闭包和传递闭包分别为:
$$R_{ref}=\{<a,a>,<b,b>,<c,c>,<d,d>,<a,b>,<b,a>,<b,c>,<c,d>\}$$
$$R_{sym}=\{<a,a>,<b,b>,<c,c>,<d,d>,<a,b>,<b,a>,<b,c>,<c,b>,<c,d>,<d,c>\}$$
$$R_{tran}=\{<a,a>,<b,b>,<c,c>,<d,d>,<a,b>,<b,a>,<b,c>,<c,d>,<a,c>,<a,d>,<b,d>\}$$
阅读全文