-
Notifications
You must be signed in to change notification settings - Fork 1
/
DNF_Generator.py
177 lines (151 loc) · 4.25 KB
/
DNF_Generator.py
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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
################### Q1 PART B
###### AKASH SHARMA , 2017327
'''
ASSUMPTIONS-----------------------------------------------
Symbols to used in the input propositional logic:
1) + for disjunction
2) . for conjunction
3) ~ for negation
4) * for implication
5) = for bi-implication
6) Additional terms like '(' and ')'
7) small ascii characters as binary variables
[NO SPACES IN BETWEEN TO BE USED and NO NULL PROPOSITION]
----------------------------------------------------------
'''
#importing modules
from tabulate import tabulate
import copy
#Helper functions
def flip(x):
#fliping the bit
if(x==1):
return 0
else:
return 1
def generateTT(vars,values,varmap):
#tabulate the truth table
varss=vars
for i in range(len(values)):
varss[i].append(values[i])
print(tabulate(varss, headers=list(varmap.keys())+["Result"]))
def generateSOP(vars,values,varmap):
#generating DNF (or SOP)
ans=""
miniansarr=[]
for i in range(len(values)):
if(values[i]==1):
minians=""
for j in range(len(vars[i])-1):
if(vars[i][j]==1):
minians+=str(list(varmap.keys())[j])+"."
else:
minians+="~"+str(list(varmap.keys())[j])+"."
minians=minians[:len(minians)-1]
miniansarr.append("("+minians+")")
for i in miniansarr:
ans+=(i+"+")
ans=ans[:len(ans)-1]
if(ans==""):
print("0")
else:
print(ans)
# Main Function <----
print("Enter the proposition with appropriate syntax")
inp=input()
#preprocessing of string -> "==" into "="
inp=inp.replace("==","=")
#preprocessing - reading chars, storing variables
props=inp
no_of_variables=0
var=[]
varmap={}
#calculating number of variables
for i in range(len(inp)):
if(ord(inp[i])>=97 and ord(inp[i])<=122) and inp[i] not in varmap:
no_of_variables+=1
var.append(0)
varmap[inp[i]]=no_of_variables-1
'''
-------------------------------------------------------------------------------
Operator precedence in propositional logic used in creating the postfix order
1)~
2).
3)+
4)*
5)==
'(' and ')' parenthesis are given the highest priority pairwise
-------------------------------------------------------------------------------
'''
#infix to postfix formation using stack
outp=[]
stack=[]
precedence={'~':5,'.':4,'+':3,'*':2,'=':1,'(':0,')':0}
for i in range(len(inp)):
if (ord(inp[i])>=97 and ord(inp[i])<=122):
outp.append(inp[i])
elif(inp[i]=='('):
stack.append(inp[i])
elif(inp[i]==')'):
x=stack.pop()
while x!='(' and len(stack)>0:
outp.append(x)
x=stack.pop()
else:
while len(stack)>0 and precedence[stack[len(stack)-1]]>=precedence[inp[i]]:
x= stack.pop()
outp.append(x)
stack.append(inp[i])
while len(stack)>0:
outp.append(stack.pop())
print(outp)
# evaluating postfix expression with all possible binary combinations
vartable=[]
values=[]
number_of_values=(2**no_of_variables)
#forming 2**n generations (n -> no of variables) and each generation will have unique binary combination for each variable
for i in range(number_of_values):
valuesInString=bin(i)[2:].zfill(no_of_variables)
for j in range(len(valuesInString)):
var[j]= int(valuesInString[j])
evalexpr=[]
# replacing variables with binary values
for j in range(len(outp)):
if (ord(outp[j])>=97 and ord(outp[j])<=122):
evalexpr.append(var[varmap[outp[j]]])
else:
if outp[j]=="~":
evalexpr.append(outp[j])
else:
evalexpr.append(outp[j])
result=[]
#evaluating the final result
for j in range(len(evalexpr)):
if ((evalexpr[j])==1) or ((evalexpr[j])==0):
result.append(evalexpr[j])
else:
a1=0
a2=0
if(evalexpr[j]=='~'):
result[len(result)-1]=(flip(result[len(result)-1]))
else:
a2=result.pop()
a1=result.pop()
if(evalexpr[j]=='.'):
result.append(a1&a2)
if(evalexpr[j]=='+'):
result.append(a1|a2)
if(evalexpr[j]=='*'):
result.append(flip(a1)|a2)
if(evalexpr[j]=='='):
result.append((a1&a2)|(flip(a1)&flip(a2)))
a=copy.deepcopy(var)
vartable.append(a)
values.append(result.pop())
# generating final results
print("\n")
print("Generating Truth Table --------------")
generateTT(vartable,values,varmap)
print("\n")
print("Generating DNF -----------------")
generateSOP(vartable,values,varmap)