[Edu-sig] Intro to CS (boolean.py)

[Kirby Urner]

Here's a simple boolean algebra module, for which
"useless Python" I'll no doubt find many more capable
versions (haven't checked yet).

Still, I like this one because it includes a broad
range of Python concepts in not-too-difficult form,
namely:

* a simple class:  the Bool class does little more than
   override the behavior of __invert__ for integers, so
   instead of getting two's complement, I get the logical
   negation, i.e. I say '~a' instead of 'not a'.

* a regular expression:  really basic, but used to find
   all occurances of a single letter variable, and replace
   it with ~variable.  This version only allows up to four
   variables a-d.

* plenty of string manipulation, which is the nuts and
   bolts of a lot of programming

* an example of eval() with a local namespace

Here's how it looks, used in shell mode:

   >>> reload(boolean)
   <module 'boolean' from 'D:\PROGRAM FILES\PYTHON22\work\boolean.py'>

   >>> boolean.truth(1,'~a')

    a | ~a
    ==|===
    0 | 1
    1 | 0

   >>> expr = "(a & ~b) | c"
   >>> boolean.truth(3,expr)

    a b c | (a & ~b) | c
    ======|=============
    0 0 0 |      0
    0 0 1 |      1
    0 1 0 |      0
    0 1 1 |      1
    1 0 0 |      1
    1 0 1 |      1
    1 1 0 |      0
    1 1 1 |      1

   >>> newexpr = boolean.demorgan(expr)
   >>> newexpr
   '~(((~a) | ~(~b)) & (~c))'
   >>> boolean.truth(3,newexpr)

    a b c | ~(((~a) | ~(~b)) & (~c))
    ======|=========================
    0 0 0 |            0
    0 0 1 |            1
    0 1 0 |            0
    0 1 1 |            1
    1 0 0 |            1
    1 0 1 |            1
    1 1 0 |            0
    1 1 1 |            1

As an intro to computer science module, it's got some
other key stuff too, in addition to exercising the above
features of Python (which features are characteristic
of many other languages).

It's got decimal to binary conversion...

   >>> from boolean import bin
   >>> bin(10)
   '1010'
   >>> bin(100)
   '1100100'
   >>> bin(3242034)
   '1100010111100000110010'

And it's got this DeMorgan's equivalence relation, whereby
you can express the same logical expression in two different
ways.  CS students know what I'm talking about.

That being said, I'm sure the code could be enchanced/improved,
features added and so on (I'm working on an improvement or
two right now).

So, have at it...

Kirby

=====

"""
Simple boolean algebra module by
Kirby Urner, Oct 13, 2001
"""

from string import replace, center
from re import sub

class Bool:
    """
    Intialize w/ 1 or 0: a,b = Bool(1), Bool(0)
    Example expressions:  a&b, a|b, ~a  (note: ~ for negation)
    returns a Bool
    """

    def __init__(self,val):
       if not (val==0 or val==1):
          raise ValueError,"Must be 1 or 0"
       self.value = val

    def __invert__(self):
       return Bool(not self.value)

    def __and__(self,other):
       return Bool(self.value & other.value)

    def __or__(self,other):
       return Bool(self.value | other.value)

    def __repr__(self):
       return repr(self.value)

def demorgan(expr):
     """
     Swap & with |, negate args, negate expression
     -- should have same truth table as original
     """
     def negate(matchobj):
	t = matchobj.group(0)
	return '(~%s)' % t
     expr = replace(expr,'&','@')
     expr = replace(expr,'|','&')
     expr = replace(expr,'@','|')
     expr = sub('[a-d]',negate,expr)
     return "~("+expr+")"

def bin(n):
     result = ''
     while 1:
         result = str(n%2)+result
         n = n//2
         if not n:  break
     return result

def truth(n,expr):
     """
     Generates truth table for n=1-4 variables a-d,
     for the passed boolean expression expr
     """
     truth_table = []
     locals = {}
     padding = n*'0'
     for i in range(2**n):
         digits = (padding + bin(i))[-n:]
         truth_table.append(tuple(digits))
     print
     print " "+("%s "*n) % tuple('abcd')[:n] + "| " + expr
     print " "+"=="*n + "|=" + "="*len(expr)
     for row in truth_table:
         for i in range(n):
            locals['abcd'[i]]=Bool(int(row[i]))
         print " "+("%s "*n) % row + "| " + \
               center(str(eval(expr,locals)),len(expr))
     print

=====