blob: 176ade62a5da11e6afa10767d3ecb0188f06643d (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
|
import numpy as np
from dataclasses import dataclass
@dataclass
class BinaryRelation:
matrix: np.array
reflexive: bool = False
antireflexive: bool = False
symmetric: bool = False
antisymmetric: bool = False
transitive: bool = False
def check_reflexivity(relation: BinaryRelation):
diagonal = np.diagonal(relation.matrix)
result = diagonal[diagonal == True].shape[0] == diagonal.shape[0]
relation.reflexive = result
def check_antireflexivity(relation: BinaryRelation):
diagonal = np.diagonal(relation.matrix)
result = diagonal[diagonal == False].shape[0] == diagonal.shape[0]
relation.antireflexive = result
def check_symmetry(relation: BinaryRelation):
relation.symmetric = (relation.matrix == relation.matrix.T).all()
def check_antisymmetry(relation: BinaryRelation):
relation.antisymmetric = True
multiplied = np.multiply(relation.matrix, relation.matrix.T)
n = multiplied.shape[0]
for i in range(n):
for j in range(n):
if i != j and multiplied[i][j] != False:
relation.antisymmetric = False
def check_transitivity(relation: BinaryRelation):
multiplied = relation.matrix @ relation.matrix
relation.transitive = (multiplied <= relation.matrix).all()
def is_equivalence(relation: BinaryRelation) -> bool:
return relation.reflexive and relation.symmetric and relation.transitive
def is_quasiorder(relation: BinaryRelation) -> bool:
return relation.reflexive and relation.transitive
def is_partial_order(relation: BinaryRelation) -> bool:
return relation.reflexive and relation.antisymmetric and relation.transitive
def is_strict_order(relation: BinaryRelation) -> bool:
return relation.antireflexive and relation.antisymmetric and relation.transitive
def reflexive_closure(relation: BinaryRelation) -> BinaryRelation:
matrix = np.copy(relation.matrix)
for i in range(matrix.shape[0]):
matrix[i][i] = True
return BinaryRelation(matrix)
def symmetric_closure(relation: BinaryRelation) -> BinaryRelation:
matrix = np.copy(relation.matrix)
n = matrix.shape[0]
for i in range(n):
for j in range(n):
if matrix[i][j]:
matrix[j][i] = True
return BinaryRelation(matrix)
def transitive_closure(relation: BinaryRelation) -> BinaryRelation:
matrix = np.copy(relation.matrix)
n = matrix.shape[0]
for _ in range(n):
for i in range(n):
for j in range(n):
for k in range(n):
if matrix[i][k] and matrix[k][j]:
matrix[i][j] = True
return BinaryRelation(matrix)
def main():
n = int(input("Введите размер матрицы: "))
l = []
print(f"На следующих {n} строках введите матрицу:")
for _ in range(n):
l.extend(map(int, input().split()))
matrix = np.array(l, dtype=np.bool8).reshape(n, n)
relation = BinaryRelation(matrix)
check_reflexivity(relation)
check_antireflexivity(relation)
check_symmetry(relation)
check_antisymmetry(relation)
check_transitivity(relation)
print("Указанное бинарное отношение обладает следующими свойствами:")
if relation.reflexive: print("- Рефлексивность;")
if relation.antireflexive: print("- Антирефлексивность;")
if relation.symmetric: print("- Симметричность;")
if relation.antisymmetric: print("- Антисимметричность;")
if relation.transitive: print("- Транзитивность.")
classes = []
if is_equivalence(relation): classes.append("эквивалентностью")
if is_quasiorder(relation): classes.append("квазипорядком")
if is_partial_order(relation): classes.append("частичным порядком")
if is_strict_order(relation): classes.append("строгим порядком")
if classes:
print(f"Отношение является {', '.join(classes)}")
else:
print("Отношение не относится ни к какому особому виду")
print("Рефлексивное замыкание:")
print(np.array(reflexive_closure(relation).matrix, dtype=np.int8))
print("Симметричное замыкание:")
print(np.array(symmetric_closure(relation).matrix, dtype=np.int8))
print("Транзитивное замыкание:")
print(np.array(transitive_closure(relation).matrix, dtype=np.int8))
print("Эквивалентное замыкание:")
eq = transitive_closure(symmetric_closure(reflexive_closure(relation)))
print(np.array(eq.matrix, dtype=np.int8))
if __name__ == "__main__":
main()
|
