## Search This Blog

### Generating a minimal set algebra from a given set of sets

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:

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()