This is a Python program which generates the minimal set algebra which contains all the elements/sets of the set C. In this program Omega is the universal set. Then C is a subset of the powerset of Omega. The program generates the minimal set algebra C3 which contains all the elements of C. A set algebra is also known as a field of sets. Of course here Omega and C are both finite sets.

` ````
import itertools as it
Empty = frozenset({})
def main():
# Omega ---> the universal set
Omega = frozenset({1, 2, 3, 4, 5, 6})
# C ---> a set of subsets of Omega
# C = {frozenset({1}), frozenset({1,3})}
# C = {frozenset({1,2}), frozenset({2,3,4}), frozenset({5})}
C = {frozenset({1, 2}), frozenset({2, 3, 5})}
# Now we generate the sets C1, C2, C3
# C3 is the minimal boolean algebra
# which contains all the elements of C
print("=" * 60)
C1 = gen_C1(Omega, C)
C2 = gen_C2(Omega, C1)
C3 = gen_C3(Omega, C2)
print("The set of sets C is given as input.")
print("Size: ", len(C), "---> C = ", make_lst(C))
print("Added all complements to C ---> result: C1")
print("Size: ", len(C1), "---> C1 = ", make_lst(C1))
print("Added all intersections to C1 ---> result: C2")
print("Size: ", len(C2), "---> C2 = ", make_lst(C2))
print("Added all unions of disjoint sets to C2 ---> result: C3")
print("Size: ", len(C3), "---> C3 = ", make_lst(C3))
print("Checking if C3 is indeed a set algebra ---> ", is_set_algebra(Omega, C3))
print("=" * 60)
def make_lst(C):
P = []
for A in C:
P.append(str(set(A)) if not Empty == A else "{}")
return P
def powerset(Omega):
n = len(Omega)
ps = set({})
for k in range(0, n + 1):
z = it.combinations(Omega, k)
for t in z:
ps.add(frozenset(t))
return ps
def gen_C1(Omega, C):
ps = powerset(Omega)
C1 = frozenset({})
C1 = C1 | {Empty}
C1 = C1 | {Omega}
for A in C:
C1 = C1 | {A}
C1 = C1 | {Omega - A}
return C1
def gen_C2(Omega, C1):
P = Empty
k = 0
while (True):
k = k + 1
sz1 = len(P)
Z = Empty
S = C1 if k == 1 else P
for A in S:
for B in S:
Z = Z | {A & B}
P = P | Z
sz2 = len(P)
if sz2 == sz1:
break
return P
def gen_C3(Omega, C2):
P = Empty
k = 0
while True:
k = k + 1
sz1 = len(P)
Z = Empty
S = C2 if k == 1 else P
for A in S:
for B in S:
# print("A=",A)
# print("B=",B)
if A & B == Empty or A & B == A or A & B == B:
# print("Adding to Z ...")
Z = Z | {A | B}
P = P | Z
sz2 = len(P)
if sz2 == sz1:
break
return P
def is_set_algebra(Omega, U):
if Omega not in U:
return False
if Empty not in U:
return False
for A in U:
B = Omega - A
if B not in U:
return False
for A in U:
for B in U:
if not (A | B in U):
return False
if not (A & B in U):
return False
return True
if __name__ == "__main__":
main()
```

## No comments:

## Post a Comment