472,347 Members | 1,726 Online

# Building truth tables

Well I would like to make a little program that given a certain
logical expression gives the complete truth table.

It's not too difficult in fact, I just have some doubts on how to
design it.

I thought something like that:

class Term:

class Table:

def and(...
def or(...
But I'm not convinced...
I would like something like that more or less:
a,b,c = Term()

table([a,b,c], impl(and(or(a,b)),c))

Any idea??
Thanks
Sep 26 '08 #1
5 6462 2008/9/26 andrea <ke******@gmail.com>:
Well I would like to make a little program that given a certain
logical expression gives the complete truth table.

It's not too difficult in fact, I just have some doubts on how to
design it.

I thought something like that:

class Term:

class Table:

def and(...
def or(...
As a quick and dirty solution, I'd write a function that takes a
function as a parameter.

Starting with a helper function to separate the bits of an integer
into a list of bools:

def int_to_bool(i, bits):
# Extract the bits of i to a boolean array.
# 'bits' is the number of signifcant bits.
result = []
for j in range(0, bits):
result.append(i & 1)
i >>= 1
result.reverse()
return result

Now I'd define a function such as:
def table(f, n):
# Calculate a truth table for function f taking n boolean parameters
result = []
for i in range(0, math.pow(2, n)):
for j in range(0, n):
params = int_to_bool(i, n)
result.append(params + [(f(*params))])
return result

Now you could define the function you want as a separate function, or
just use a lambda:

table(lambda a, b, c:(a or b) and c, 3)
[[0, 0, 0, 0], [0, 0, 1, 0], [0, 1, 0, 0], [0, 1, 1, 1], [1, 0, 0, 0],
[1, 0, 1, 1], [1, 1, 0, 0], [1, 1, 1, 1]]

Each element in the result is the state of the parameters followed by
the result of the function.

I stress that this is quick and dirty -- I'm sure somebody will be
along with something better soon!
--
Tim Rowe
Sep 26 '08 #2
On Sep 26, 11:40*am, "Tim Rowe" <digi...@gmail.comwrote:
2008/9/26 andrea <kerny...@gmail.com>:
Well I would like to make a little program that given a certain
logical expression gives the complete truth table.
It's not too difficult in fact, I just have some doubts on how to
design it.
I thought something like that:
class Term:
class Table:
* def and(...
* def or(...

As a quick and dirty solution, I'd write a function that takes a
function as a parameter.

Starting with a helper function to separate the bits of an integer
into a list of bools:

def int_to_bool(i, bits):
* * * * # Extract the bits of i to a boolean array.
* * * * # 'bits' is the number of signifcant bits.
* * * * result = []
* * * * for j in range(0, bits):
* * * * * * * * result.append(i & 1)
* * * * * * * * i >>= 1
* * * * result.reverse()
* * * * return result

Now I'd define a function such as:
def table(f, n):
* * * * # Calculate a truth table for function f taking n booleanparameters
* * * * result = []
* * * * for i in range(0, math.pow(2, n)):
* * * * * * * * for j in range(0, n):
* * * * * * * * * * * * params = int_to_bool(i,n)
* * * * * * * * result.append(params + [(f(*params))])
* * * * return result

Now you could define the function you want as a separate function, or
just use a lambda:

table(lambda a, b, c:(a or b) and c, 3)
[[0, 0, 0, 0], [0, 0, 1, 0], [0, 1, 0, 0], [0, 1, 1, 1], [1, 0, 0, 0],
[1, 0, 1, 1], [1, 1, 0, 0], [1, 1, 1, 1]]

Each element in the result is the state of the parameters followed by
the result of the function.

I stress that this is quick and dirty -- I'm sure somebody will be
along with something better soon!

--
Tim Rowe
Good idea. If you want prefixed operators: 'and( a, b )' instead of
'a and b', you'll have to write your own. ('operator.and_' is bitwise
only.) It may be confusing to mix prefix with infix: 'impl( a and b,
c )', so you may want to keep everything prefix, but you can still use
table( f, n ) like Tim said.
Sep 26 '08 #3
On 26 Set, 20:01, "Aaron \"Castironpi\" Brady" <castiro...@gmail.com>
wrote:
>
Good idea. *If you want prefixed operators: 'and( a, b )' instead of
'a and b', you'll have to write your own. *('operator.and_' is bitwise
only.) *It may be confusing to mix prefix with infix: 'impl( a and b,
c )', so you may want to keep everything prefix, but you can still use
table( f, n ) like Tim said.
After a while I'm back, thanks a lot, the truth table creator works,
now I just want to parse some strings to make it easier to use.

Like

(P \/ Q) -S == S

Must return a truth table 2^3 lines...

I'm using pyparsing and this should be really simple, but it doesn't
allow me to recurse and that makes mu stuck.
The grammar BNF is:

Var :: = [A..Z]
Exp ::= Var | !Exp | Exp \/ Exp | Exp -Exp | Exp /\ Exp | Exp ==
Exp

I tried different ways but I don't find a smart way to get from the
recursive bnf grammar to the implementation in pyparsing...
Any hint?
Oct 24 '08 #4
On Oct 24, 5:53*am, andrea <kerny...@gmail.comwrote:
On 26 Set, 20:01, "Aaron \"Castironpi\" Brady" <castiro...@gmail.com>
wrote:
Good idea. *If you want prefixed operators: 'and( a, b )' instead of
'a and b', you'll have to write your own. *('operator.and_' is bitwise
only.) *It may be confusing to mix prefix with infix: 'impl( a and b,
c )', so you may want to keep everything prefix, but you can still use
table( f, n ) like Tim said.

After a while I'm back, thanks a lot, the truth table creator works,
now I just want to parse some strings to make it easier to use.

Like

(P \/ Q) -S == S

Must return a truth table 2^3 lines...

I'm using pyparsing and this should be really simple, but it doesn't
allow me to recurse and that makes mu stuck.
The grammar BNF is:

Var :: = [A..Z]
Exp ::= Var | !Exp *| Exp \/ Exp | Exp -Exp | Exp /\ Exp | Exp ==
Exp

I tried different ways but I don't find a smart way to get from the
recursive bnf grammar to the implementation in pyparsing...
Any hint?
Use Forward to create a recursive grammar. Look at the examples page
on the pyparsing wiki, and there should be several samples of
recursive grammars.

Here is a very simple recursive grammar, with no precedence to your
operators:

from pyparsing import oneOf, alphas, Forward, ZeroOrMore, Group,
Optional
var = oneOf(list(alphas))
op = oneOf(r"\/ /\ -==")
expr = Forward()
expr << Optional('!') + ( var | Group('(' + expr + ')') ) +
ZeroOrMore(op + expr)

test = "(P \/ Q) -S == S"

print expr.parseString(test).asList()

prints:

[['(', 'P', '\\/', 'Q', ')'], '->', 'S', '==', 'S']
Since these kinds of expressions are common, pyparsing includes a
helper method for defining precedence of operations infix notation:

from pyparsing import operatorPrecedence, opAssoc

expr = operatorPrecedence(var,
[
(r'!', 1, opAssoc.RIGHT),
(r'\/', 2, opAssoc.LEFT),
(r'/\\', 2, opAssoc.LEFT),
(r'->', 2, opAssoc.LEFT),
(r'==', 2, opAssoc.LEFT),
])

print expr.parseString(test).asList()

prints:

[[[['P', '\\/', 'Q'], '->', 'S'], '==', 'S']]

HTH,
-- Paul
Oct 25 '08 #5
On Oct 24, 5:53*am, andrea <kerny...@gmail.comwrote:
On 26 Set, 20:01, "Aaron \"Castironpi\" Brady" <castiro...@gmail.com>
wrote:
Good idea. *If you want prefixed operators: 'and( a, b )' instead of
'a and b', you'll have to write your own. *('operator.and_' is bitwise
only.) *It may be confusing to mix prefix with infix: 'impl( a and b,
c )', so you may want to keep everything prefix, but you can still use
table( f, n ) like Tim said.

After a while I'm back, thanks a lot, the truth table creator works,
now I just want to parse some strings to make it easier to use.

Like

(P \/ Q) -S == S

Must return a truth table 2^3 lines...

I'm using pyparsing and this should be really simple, but it doesn't
allow me to recurse and that makes mu stuck.
The grammar BNF is:

Var :: = [A..Z]
Exp ::= Var | !Exp *| Exp \/ Exp | Exp -Exp | Exp /\ Exp | Exp ==
Exp

I tried different ways but I don't find a smart way to get from the
recursive bnf grammar to the implementation in pyparsing...
Any hint?
Tell you what. At the risk of "carrot-and-stick, jump-how-high"
tyranny, I'll show you some output of a walk-through. It should give
you an idea of the process. You can always ask for more hints.

( ( ( !( R ) /\ ( !( P \/ Q ) ) ) -S ) == S )
(((!(R)/\(!(P\/Q)))->S)==S)
(((!R/\(!(P\/Q)))->S)==S)
n1 := !R
(((n1/\(!(P\/Q)))->S)==S)
n2 := P\/Q
(((n1/\(!(n2)))->S)==S)
(((n1/\(!n2))->S)==S)
n3 := !n2
(((n1/\(n3))->S)==S)
(((n1/\n3)->S)==S)
n4 := n1/\n3
(((n4)->S)==S)
((n4->S)==S)
n5 := n4->S
((n5)==S)
(n5==S)
n6 := n5==S
(n6)
n6
{'n1': (<function not_ at 0x00A04070>, '!R', ('R',)),
'n2': (<function or_ at 0x00A040F0>, 'P\\/Q', ('P', 'Q')),
'n3': (<function not_ at 0x00A04070>, '!n2', ('n2',)),
'n4': (<function and_ at 0x00A040B0>, 'n1/\\n3', ('n1', 'n3')),
'n5': (<function imp_ at 0x00A04130>, 'n4->S', ('n4', 'S')),
'n6': (<function eq_ at 0x00A04170>, 'n5==S', ('n5', 'S'))}
{'Q': True, 'P': True, 'S': True, 'R': True} True
{'Q': True, 'P': True, 'S': False, 'R': True} False
{'Q': True, 'P': True, 'S': True, 'R': False} True
{'Q': True, 'P': True, 'S': False, 'R': False} False
{'Q': False, 'P': True, 'S': True, 'R': True} True
{'Q': False, 'P': True, 'S': False, 'R': True} False
{'Q': False, 'P': True, 'S': True, 'R': False} True
{'Q': False, 'P': True, 'S': False, 'R': False} False
{'Q': True, 'P': False, 'S': True, 'R': True} True
{'Q': True, 'P': False, 'S': False, 'R': True} False
{'Q': True, 'P': False, 'S': True, 'R': False} True
{'Q': True, 'P': False, 'S': False, 'R': False} False
{'Q': False, 'P': False, 'S': True, 'R': True} True
{'Q': False, 'P': False, 'S': False, 'R': True} False
{'Q': False, 'P': False, 'S': True, 'R': False} True
{'Q': False, 'P': False, 'S': False, 'R': False} True

Before you trust me too much, you might want to check at least some of
these, to see if the starting (complicated) expression is evaluated
correctly. I didn't.
Oct 25 '08 #6

This thread has been closed and replies have been disabled. Please start a new discussion.

### Similar topics

 7 by: Good Man | last post by: Hi there I'm in the planning stages of creating a database, and I have two options here. Which makes more sense, and/or provides better... 1 by: rsd | last post by: how do you specify the "colspan" attribut of a
cell when building the table/rows/cells dynamicly? ie: lets say we have the follwoing code: ... 0 by: Mac MCCall | last post by: I am doing work for a community that currently has four different MS-Access databases which are at four separate locations but have a great deal of... 0 by: matt | last post by: (first -- does anyone know of a good CR group?) hello, i am new to CR. i have created one report that queries the db and presents the data to... 1 by: Franck | last post by: Hi, I'd like to know if it's possible to get server side relationship when building Link Tables in my AccessFront End. Basic Sample : In my Sql... 2 by: wujtehacjusz | last post by: Dear All I am very new to MS SQL Server and I am wondering is there some tool which would allow me to build pivot tables in SQL more easily. At... 6 by: ambanks04 | last post by: ok taking computer science class anybody know what to do i am not computer literate CoSc 111.003 Spring 2008 Assignment 4 1) Each... 7 by: papacologne | last post by: Given the truth values of the propositions p and q, display the truth values of the conjunction, disjunction, exclusive or, conditional statement,... 0 by: better678 | last post by: Question: Discuss your understanding of the Java platform. Is the statement "Java is interpreted" correct? Answer: Java is an object-oriented... 0 by: Naresh1 | last post by: What is WebLogic Admin Training? WebLogic Admin Training is a specialized program designed to equip individuals with the skills and knowledge... 0 by: jalbright99669 | last post by: Am having a bit of a time with URL Rewrite. I need to incorporate http to https redirect with a reverse proxy. I have the URL Rewrite rules made... 0 by: Matthew3360 | last post by: Hi there. I have been struggling to find out how to use a variable as my location in my header redirect function. Here is my code. ... 2 by: Matthew3360 | last post by: Hi, I have a python app that i want to be able to get variables from a php page on my webserver. My python app is on my computer. How would I make it... 0 by: AndyPSV | last post by: HOW CAN I CREATE AN AI with an .executable file that would suck all files in the folder and on my computerHOW CAN I CREATE AN AI with an .executable... 0 by: Arjunsri | last post by: I have a Redshift database that I need to use as an import data source. I have configured the DSN connection using the server, port, database, and... 0 by: WisdomUfot | last post by: It's an interesting question you've got about how Gmail hides the HTTP referrer when a link in an email is clicked. While I don't have the specific... 0 by: Matthew3360 | last post by: Hi, I have been trying to connect to a local host using php curl. But I am finding it hard to do this. I am doing the curl get request from my web...