1 import fbool
2 import ct
3 from string import *
4 from terme import *
5
6 def implicants(f):
7 """
8
9 Funció que retorna el conjunt de tots els implicants primers
10 possibles de f. S'assumeix que la representació́ de f està en FNDP.
11
12 >>> implicants([(0, 0, 1), (0, 1, 0), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)])
13 [(2, 0, 1), (2, 1, 0), (1, 0, 2), (1, 2, 0), (1, 2, 1), (1, 1, 2), (1, 2, 2)]
14 """
15 conjunt_I=[]
16 conjunt=f
17 while conjunt!=[]:
18 conjunt_temporal=[]
19 for i in range(0, len(conjunt)-1):
20 for j in range(i+1, len(conjunt)):
21 if son_reduibles(conjunt[i],conjunt[j]):
22 ct.afegeix(conjunt_temporal,implicant(conjunt[i],conjunt[j]))
23 if conjunt_temporal!=[]:
24 conjunt_I=ct.unio(conjunt_I, conjunt_temporal)
25 conjunt=conjunt_temporal
26 return conjunt_I
27
28
29 def termes_minimals(m):
30 """
31 Funció que retorna un conjunt minimal de termes que representen a m.
32
33 termes_minimals([(0, 0, 1), (0, 1, 0), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)])
34 [(2, 0, 1), (2, 1, 0), (1, 2, 2)]
35
36 """
37
38 p=primers(implicants(m))
39 r=[]
40
41
42 i=0
43 while i<len(m):
44 representat=False
45 j=0
46 while not representat and j<len(p):
47 if representa(p[j],m[i]):
48 representat=True
49 else:
50 j+=1
51 if not representat:
52 r=ct.afegeix(r,m[i])
53 i+=1
54 m=ct.diferencia(m,r)
55
56
57 i=0
58 while i<len(m):
59 contador=0
60 j=0
61 while j<len(p) and contador<2:
62 if representa(p[j],m[i]):
63 contador+=1
64 unic=p[j]
65 j+=1
66 if contador==1:
67 r=ct.afegeix(r,unic)
68 m=ct.diferencia(m,[terme for terme in m if representa(unic,terme)])
69 else:
70 i+=1
71
72
73 i=0
74 while i <len(m):
75 j=0
76 maxim=(0,)
77 while j<len(p):
78 if representa(p[j],m[i]) and potencia(maxim) < potencia(p[j]):
79 maxim=p[j]
80 j+=1
81 if maxim:
82 r=ct.afegeix(r,maxim)
83 m=ct.diferencia(m,[terme for terme in m if representa(maxim,terme)])
84 else:
85 i+=1
86
87 return r
88
89 def primers(c):
90 """
91 Funció que, donat un conjunt d’implicants c retorna el conjunt obtingut
92 en eliminar els implicants redundants de c.
93
94 A tal es crea un clon del conjunt c, diguem-ne r. Recorrent tots i
95 cadascun dels implicants de c i, per a cada implicant i, s'eliminent
96 del conjunt r tots aquells elements que estan representats per i. En
97 finalitzar el recorregut, r contè els implicants sense redundància, ès
98 a dir, els implicants primers.
99 >>> primers([(2, 0, 1), (2, 1, 0), (1, 0, 2), (1, 2, 0), (1, 2, 1), (1, 1, 2), (1, 2, 2)])
100 [(2, 1, 0), (2, 0, 1), (1, 2, 2)]
101 """
102 r=[]
103 for terme_c in c:
104 r=fbool.afegeix(c,terme_c)
105 return r
106
107
108 def minimitza(f):
109 """
110 Aquesta funció té com a paràmetre una
111 funció booleana expressada en FNDP i retorna
112 una funció booleana equivalent a f però minimal.
113
114 >>> minimitza(['110','000','101', '100','111'])
115 [(2, 0, 0), (1, 2, 2)]
116
117 >>> minimitza(['1101','0001','1011', '1001','1111'])
118 [(2, 0, 0, 1), (1, 2, 2, 1)]
119 """
120
121 llista_de_termes = fbool.crea(f)
122 return termes_minimals(llista_de_termes)
