# Dysjunctive Normal Form using Python

Page 1 of 1

## 8 Replies - 4203 Views - Last Post: 28 February 2009 - 08:04 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=85540&amp;s=1dd56927d90e76cbe6b4f0dc07d6419c&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 troegs

Reputation: 1
• Posts: 40
• Joined: 05-December 08

# Dysjunctive Normal Form using Python

Posted 09 February 2009 - 01:00 AM

Alright. this is the next level to a previous posting. I am currently tasked with finding, (and later simplifying) the dysjunctive normal form (DNF) of a boolean function given a set of inputs. the inputs will always be a factorial of two i/e 2, 4, 8, 16.... up to 256. Here is the code I have so far for the initial validation of the input:
f=open("test.txt","r")
i=0
for lines in f:
i=i+1
count = 0
while i > 1:
i = i / 2
count +=1
print "there are ", count, " variables in the boolean function"

functionString = ""

li = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j"]

i = 0
while i < count:
if i == (count - 1):
functionString = functionString + li[i]
else:
functionString = functionString + li[i] + ","
i+=1

print 'the function is f(', functionString, ')'

So, given an input text file that looks like this:
0
1
0
0
1
0
1
1

the return when running the program would be as follows:
there are  3  variables in the boolean function
the function is f( a,b,c )

What I need now is a way of determining what the DNF of the input would be. I know that the DNF is as follows:
f(a,b,c) = a’b’c | ab’c’ | abc’ | abc (where the and operation is simply when no symbol is present, ' is the "not" operator, and | is the or operator.

I realize this is combining python knowledge with some mid level college math so not expecting an overflow of responses but any help would be greatly appreciated. anyone looking for a challenge this thread is for you! For those braniacs that think this is a simple brain teaser, please enlighten me!

T.

This post has been edited by troegs: 09 February 2009 - 01:01 AM

Is This A Good Question/Topic? 0

## Replies To: Dysjunctive Normal Form using Python

### #2 dcp

Reputation: 0
• Posts: 17
• Joined: 29-July 06

## Re: Dysjunctive Normal Form using Python

Posted 21 February 2009 - 11:22 PM

I'm not sure I understand your input. When I type "a'.b'.c+a.b'.c'+a.b.c'+a.b.c" into http://www.izyt.com/...ogic/applet.php, I do not get the same truth table. Can you elaborate on how your input file of 2^3 inputs relates to your 3 variables?

troegs, on 9 Feb, 2009 - 03:00 AM, said:

Alright. this is the next level to a previous posting. I am currently tasked with finding, (and later simplifying) the dysjunctive normal form (DNF) of a boolean function given a set of inputs. the inputs will always be a factorial of two i/e 2, 4, 8, 16.... up to 256. Here is the code I have so far for the initial validation of the input:
f=open("test.txt","r")
i=0
for lines in f:
i=i+1
count = 0
while i > 1:
i = i / 2
count +=1
print "there are ", count, " variables in the boolean function"

functionString = ""

li = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j"]

i = 0
while i < count:
if i == (count - 1):
functionString = functionString + li[i]
else:
functionString = functionString + li[i] + ","
i+=1

print 'the function is f(', functionString, ')'

So, given an input text file that looks like this:
0
1
0
0
1
0
1
1

the return when running the program would be as follows:
there are  3  variables in the boolean function
the function is f( a,b,c )

What I need now is a way of determining what the DNF of the input would be. I know that the DNF is as follows:
f(a,b,c) = a’b’c | ab’c’ | abc’ | abc (where the and operation is simply when no symbol is present, ' is the "not" operator, and | is the or operator.

I realize this is combining python knowledge with some mid level college math so not expecting an overflow of responses but any help would be greatly appreciated. anyone looking for a challenge this thread is for you! For those braniacs that think this is a simple brain teaser, please enlighten me!

T.

### #3 troegs

Reputation: 1
• Posts: 40
• Joined: 05-December 08

## Re: Dysjunctive Normal Form using Python

Posted 23 February 2009 - 03:45 AM

dcp, on 21 Feb, 2009 - 10:22 PM, said:

I'm not sure I understand your input. When I type "a'.b'.c+a.b'.c'+a.b.c'+a.b.c" into http://www.izyt.com/...ogic/applet.php, I do not get the same truth table. Can you elaborate on how your input file of 2^3 inputs relates to your 3 variables?

Not really sure. The disconnect as far as consistency goes is likely due to the fact I was constantly changing my input file, but when typing the example just grabbed something off the instructor's guide for the project. I've since gotten it all done. Ended up having the best reduction from DNF of my class.

I'd post the code however unless you're familiar with sage it would look like rubbish as it uses many of its own methods. The program itself uses python as a base language but adds some extra stuff to increase math applications of python.

Not to mention the only version I have on this comp is still pretty cloogy as I haven't split anything into def's. It's one long program. A result of me continually adding code once I got the last addition working. I don't have the cleaned up copy on this comp. I'll post it in a day or two when midterms are over and I remember to do so.

### #4 Thura

Reputation: 3
• Posts: 25
• Joined: 27-February 08

## Re: Dysjunctive Normal Form using Python

Posted 23 February 2009 - 10:17 AM

Wow, it took me around 6 hours to finish it off ! Here is my answer ...
It could contains several bugs, as I finished it just now and haven't tested throughly ...

#! /usr/bin/python
from __future__ import with_statement
from math import *
import sys

__author__  ="thurahaling06@gmail.com"
__date__	="\$Feb 23, 2009 7:20:18 PM\$"

NOT_EXPR = '\''
AND_EXPR = ''
OR_EXPR  = '|'

charlist = [chr(i) for i in range(97,123)]	 # return a list from a to z

def getVarNum(truth_values):
"""Take truth values of a boolean function in string format  and \
return the number of variables required to describe it in DNF."""
length = len(truth_values)
return int(ceil(log10(length) / log10(2)))

def getFuncRepr(truth_values):
"""Take the truth values of a boolean function in string format  and \
return the string representation of the function."""
count = getVarNum(str(truth_values))
functionStr = "f("
for i in range(0, count):
if i == (count -1):
functionStr = functionStr + charlist[i]
else:
functionStr = functionStr + charlist[i] + ","
functionStr = functionStr + ")"
return functionStr

def getTruthTable(truth_values):
"""Take the truth values of a boolean function in string format  and \
return the truth table for that function in a list."""
# We will return the truth table in dictionary format , for example,
# [[(0, 0, 0), 0], [(0, 0, 1), 1], [(0, 1, 0), 0], [(0, 1, 1), 0], [(1, 0, 0), 1], [(1, 0, 1), 0], [(1, 1, 0), 1], [(1, 1, 1), 1]]
# Since we don't know the exact number of variables for the function, we will first write the python expression to  a str
# Then, evaluate it using eval ...
# Is there any smarter way of doing this in python ?

# First, get the require variable numbers and store them in a list
var_list = []
count = getVarNum(truth_values)
for m in range(0, count):
var_list.append(charlist[m])

# Ok, start writing the expression
truth_table_expr = '[[('
for x in var_list:
truth_table_expr += x + ','
truth_table_expr += ')] '
# Now, the expression is [[(a,b, ...)]

for x in var_list:
truth_table_expr += ' for ' + x + ' in range(0,2)'
truth_table_expr += (']')

# truth_table = [[(a,b, ... )]  for a in range(0,2) for b in range(0,2) ...]
truth_table = eval(truth_table_expr)

n = 0
for val in str(truth_values):
truth_table[n].append(val)
n += 1

return truth_table

def printTruthTable(truth_values,output='Q'):
"""Takethe truth values of a boolean function in string  format  and \
print the truth table for that function."""
count = getVarNum(truth_values)
truth_table = getTruthTable(truth_values)
global charlist

for i in range(0,count):
print charlist[i],'\t ',
print output
print "-" * ( 8 * ( count + 1 ) )
for val in truth_table:
for i in range(0, count):
print val[0][i], '\t','|',
print val[1],'\t','|'

def getDNF(truth_values):
"""Takethe truth values of a boolean function in string format  and \
return the string representation of DNF (Disjunctive Normal Form) value of that function."""
DNF = ""
count = getVarNum(truth_values)
truth_table = getTruthTable(truth_values)
global charlist, AND_EXPR, OR_EXPR, NOT_EXPR

for val in truth_table:
if int(val[1]):
for i in range(0,count):
if val[0][i]:
DNF += charlist[i]
else:
DNF += charlist[i] + NOT_EXPR
DNF += AND_EXPR
i += 1
DNF += OR_EXPR
DNF = DNF.rstrip(OR_EXPR + AND_EXPR + NOT_EXPR + ' ') #strip unnecessary operators on the right side
return DNF

if __name__ == "__main__":

truth_values = ''
#Parse the string from the file
with open("/home/thura/tmp/tmp2", 'r') as f:
for line in f:
truth_values = truth_values + line.strip()

truth_values = '01001011010010110100101101001011'
printTruthTable(truth_values)
print "The DNF value is for the function ", getFuncRepr(truth_values)," is ", getDNF(truth_values),'.'

### #5 tombeek

Reputation: 0
• Posts: 2
• Joined: 27-February 09

## Re: Dysjunctive Normal Form using Python

Posted 27 February 2009 - 06:08 AM

The Python code in the last entry is much better than the C or Javalike syntax of the code at the beginning. This is a useful academic exercise. Are there any practical uses for this?

### #6 troegs

Reputation: 1
• Posts: 40
• Joined: 05-December 08

## Re: Dysjunctive Normal Form using Python

Posted 28 February 2009 - 03:37 PM

tombeek, on 27 Feb, 2009 - 05:08 AM, said:

The Python code in the last entry is much better than the C or Javalike syntax of the code at the beginning. This is a useful academic exercise. Are there any practical uses for this?

OUCH. Not sure if I mentioned it in my initial post on this thread of if I mentioned it in others, (I had started several threads on this topic) That I literally didn't know the first thing about python coming into this assignment I had to do and yes the code looks "java like" due to that being the only language I knew up to this point.

As far as practical uses, my question had only to do with part of the assignment we did. The next part was continuing the algorithm to simplify and reduce the DNF. The main reason I can think to do this offhand would be the reduction of processes on a processor to speed up execution. I ended up implementing the Cline Mckloskey (not sure if I got those names quite right) algorithm to simplify the DNF. The exercise also helped in highlighting how current logic constraints still give the human brain the edge in solving certain problems as full simplification is considered NP hard.

Not sure if that was what you're asking though.

### #7 tombeek

Reputation: 0
• Posts: 2
• Joined: 27-February 09

## Re: Dysjunctive Normal Form using Python

Posted 28 February 2009 - 04:25 PM

troegs, on 28 Feb, 2009 - 02:37 PM, said:

tombeek, on 27 Feb, 2009 - 05:08 AM, said:

The Python code in the last entry is much better than the C or Javalike syntax of the code at the beginning. This is a useful academic exercise. Are there any practical uses for this?

OUCH. Not sure if I mentioned it in my initial post on this thread of if I mentioned it in others, (I had started several threads on this topic) That I literally didn't know the first thing about python coming into this assignment I had to do and yes the code looks "java like" due to that being the only language I knew up to this point.

As far as practical uses, my question had only to do with part of the assignment we did. The next part was continuing the algorithm to simplify and reduce the DNF. The main reason I can think to do this offhand would be the reduction of processes on a processor to speed up execution. I ended up implementing the Cline Mckloskey (not sure if I got those names quite right) algorithm to simplify the DNF. The exercise also helped in highlighting how current logic constraints still give the human brain the edge in solving certain problems as full simplification is considered NP hard.

Not sure if that was what you're asking though.

tombeek, on 28 Feb, 2009 - 03:22 PM, said:

troegs, on 28 Feb, 2009 - 02:37 PM, said:

tombeek, on 27 Feb, 2009 - 05:08 AM, said:

The Python code in the last entry is much better than the C or Javalike syntax of the code at the beginning. This is a useful academic exercise. Are there any practical uses for this?

OUCH. Not sure if I mentioned it in my initial post on this thread of if I mentioned it in others, (I had started several threads on this topic) That I literally didn't know the first thing about python coming into this assignment I had to do and yes the code looks "java like" due to that being the only language I knew up to this point.

As far as practical uses, my question had only to do with part of the assignment we did. The next part was continuing the algorithm to simplify and reduce the DNF. The main reason I can think to do this offhand would be the reduction of processes on a processor to speed up execution. I ended up implementing the Cline Mckloskey (not sure if I got those names quite right) algorithm to simplify the DNF. The exercise also helped in highlighting how current logic constraints still give the human brain the edge in solving certain problems as full simplification is considered NP hard.

Not sure if that was what you're asking though.

Wow! Sorry for the "Ouch!" Didn't expect that. I thought I was recognizing an improvement. There is nothing wrong with any programing language, whether it be C, C++, or Java. Python provides some much easier ways of doing things, such as as looping.

Your question and material is A+ stuff; very smart. Good on you mate!

Best,
Tom

### #8 Thura

Reputation: 3
• Posts: 25
• Joined: 27-February 08

## Re: Dysjunctive Normal Form using Python

Posted 28 February 2009 - 07:58 PM

Quote

That I literally didn't know the first thing about python coming into this assignment I had to do and yes the code looks "java like" due to that being the only language I knew up to this point.

My code seems a bit more pythonic since I have been playing with python for the past 6 months ... I also did use Javalike syntax like you when I first started learning python

### #9 troegs

Reputation: 1
• Posts: 40
• Joined: 05-December 08

## Re: Dysjunctive Normal Form using Python

Posted 28 February 2009 - 08:04 PM

Ya no worries about the "ouch" I was more joking than anything. Actually I was pretty happy with the FINAL result. As far as pyhon goes I love it. This is in part due to the language in general, but I also has to do with how the professor does these assignments. We were given what the input would be, and what the program should generally do with that input. It allowed for much more creativity, unlike my java class that lays out the methods we must create, how the output must be literally character by character line by line. So the combination of the flexibility of python, combined with the much more enjoyable experience of learning/using it has made me a fan. I'll be using it whenever I can for what I can.