# MATH 3600 - HW21a

## Boolean Logic

This worksheet combines a number of techniques that we have studied this semester to create a program that evaluates and displays Truth Tables.

On March 12, I posted Chapter 1 of the book "A Primer for Logic and Proof" by Holly P. Hirst and Jeffrey L. Hirst, professors in the Mathematical Sciences Department at Appalacian State University.  This chapter focuses on the Propositional Calculus, the first level of logical underpinnings for mathematical proofs. This Sage worksheet provides a program that computes and displays the abreviated Truth Tables for statements in the Propositional Calculus.  This should be a useful tool in studying the logical foundations of mathematics.

Exercise 1:  Read the handout and examine the structure of the following code.  Insure that you have a reasonably good idea about what's going on.

# 1. Boolean_Lex(proposition): # Converts proposition, a string, to a list of tokens # # 2. Build_Var_Dict(tokens): # Builds the dictionary of variable values # Each key is the variable's name and its # value is a list of the values by row. # The set of values is generated using # sample_with_replacement. # # 3. Init_Table(tokens,var_values_dict): # Builds the initialized Truth Table # tokens is the list of tokens and # var_values_dict is the dictionary of # variable values. # There is a column in the table for # every token in the original proposition. # The entries for 'VAR' tokens are True and False. # For all other tokens the entry is None. # # 4. Display_Table(tokens,table): # uses print_header(token_list): # and print_row(tokens,values): # # 5. Boolean_Parser(token_list): # Creates a modified copy of the original proposition. # The modification converts the infix notation to # Reverse Polish Notation. # This routine uses a Stack and a simple Operator # Precedence Grammar, defined by setup_OP_function(): # Both Stack and step_OP_function only need to be # defined once. # # 6. Boolean_Calculator(input_list): # This is an RPN calculator that evaluates Boolean expressions. # It assumes that the input_list is a valid Reverse Polish # expression consisting only of Boolean values (True and False) # and the Boolean operators 'NOT', 'AND', 'OR', 'LPAR', 'RPAR', # 'IMP', and 'IFF'. It also uses a Stack. # Except for the definition of the operations this is # essentially the same as the RPN calculator in HW09. # # 7. Boolean_Evaluate(rpn,table,var_values_dict): # This routine uses the Boolean_Calculator to evaluate all # operator entries in the Truth Table for all the possible # combinations of Boolean values for the variables. # # 8. Display_Truth_Table(proposition): # This routine takes a proposition, string, then uses all # the preceding machinery to generate and display the # proposition's Truth Table.
# This block defines a Lexical function for Boolean Propositions # that converts a string consisting of variables, parentheses, # the unary operator '~' (not), and the binary infix operators # '&', '|', '->', and '<->' (and, or, implies, iff) to a list of # tokens and positions. # # A token is a tuple that consists of a token code, the original # string for the token and the position of the token in the # proposition. # # The token codes are: # 'VAR', 'NOT', 'AND', 'OR', 'IMP', 'IFF', 'LPAR', and 'RPAR'. # # It will flag invalid characters and discard both invalid characters # and white space. # Version 2.0 # Daniel D. Warner # March 12, 2014 def Boolean_Lex(input_string): tokens = [] state = 0 nt = 0 k = 0 while k < len(input_string): ch = input_string[k] # print k,ch if state == 0: if ch.isalpha(): word = ch state = 1 elif ch == '~': tokens.append(('NOT',ch, nt)) nt += 1 elif ch == '&': tokens.append(('AND',ch,nt)) nt += 1 elif ch == '|': tokens.append(('OR',ch,nt)) nt += 1 elif ch == '(': tokens.append(('LPAR',ch,nt)) nt += 1 elif ch == ')': tokens.append(('RPAR',ch,nt)) nt += 1 elif ch == '-': word = ch state = 2 elif ch == '<': word = ch state = 3 elif ch in ' \t': # skip white space pass else: # invalid character print 'Invalid Character',ch pass k += 1 elif state == 1: if ch.isalnum(): word += ch k += 1 else: tokens.append(('VAR',word,nt)) nt += 1 state = 0 elif state == 2: word += ch if ch == '>': tokens.append(('IMP',word,nt)) nt += 1 k += 1 else: print '*** Invalid String ***' print state,word state = 0 elif state == 3: word += ch if ch == '-': state = 4 k += 1 else: print '*** Invalid String ***' print state,word state = 0 elif state == 4: word += ch if ch == '>': tokens.append(('IFF',word,nt)) nt += 1 k += 1 else: print '*** Invalid String ***' print state,word state = 0 else: print '*** Invalid State ***' print state,word,ch,k state = 0 k += 1 else: if state==1: tokens.append(('VAR',word,nt)) return tokens
prop_list = ['a&b','a|b','a->b','abe&~b','~a<->b','a->(b|cat)'] print prop_list
for p in prop_list: print p tokens = Boolean_Lex(p ) print tokens print
def sample_with_replacement(n, list, sample, table): if n == 0: table.append(sample) else: for item in list: sample_with_replacement(n-1,list,sample+[item],table) def Build_Var_Dict(tokens): var_list = [] for token in tokens: if token=='VAR' and token not in var_list: var_list.append(token) nv = len(var_list) var_values_table = [] sample_with_replacement(nv,[True,False],[],var_values_table) # print var_values_table var_values_dict = {} for k,var in enumerate(var_list): var_vals = [] for rk in range(len(var_values_table)): val = var_values_table[rk] var_vals.append(val[k]) var_values_dict[var] = var_vals return var_values_dict
for p in prop_list: print p tokens = Boolean_Lex(p ) # print tokens var_values_dict = Build_Var_Dict(tokens) print var_values_dict print
def Init_Table(tokens,var_values_dict): nrows = 2^len(var_values_dict) # print brows table = [] for k in range(nrows): row =[] for token in tokens: if token=='VAR': u = token v = var_values_dict[u] row.append(v[k]) else: row.append(None) table.append(row) return table
def print_header(token_list): header = "" for token in token_list: header += ' '+token print header print ' '+(len(header)-1)*'-' def print_row(tokens,values): # print tokens # print values row = '' for k,token in enumerate(tokens): # print k,values[k] w = len(token) # print w,(w//2+w%2)+(w//2) if token=='LPAR' or token=='RPAR': row += ' ' else: if values[k] == True: char = 'T' elif values[k] == False: char = 'F' else: char = '-' row += (w//2+w%2)*' '+char+(w//2)*' ' print row def Display_Table(tokens,table): print_header(tokens) # print nrows for row in table: print_row(tokens,row) #print row
for p in prop_list: # print p tokens = Boolean_Lex(p ) # print tokens var_values_dict = Build_Var_Dict(tokens) # print var_values_dict table = Init_Table(tokens, var_values_dict) # print table Display_Table(tokens,table) print
''' This block defines a Stack class Each instance is initialized with an empty list, called _s. The class provides 5 methods: push, pop, peek, clear, and display. Daniel D. Warner October 4, 2011 ''' class Stack: def __init__(self): self._s = [] def push(self,x): self._s.append(x) def pop(self): if 0 < len(self._s): return self._s.pop() else: return None def peek(self): if 0 < len(self._s): return self._s[-1] else: return None def clear(self): self._s = [] def display(self): print self._s
def setup_OP_function(): ''' The Operator Precedence function for the Boolean Parser. The arguments are the token on the input and the token on the top of the stack. f(row,column) f(sp,op) ''' global ops ops = ['NOT', 'AND', 'OR', 'LPAR', 'RPAR', 'IMP', 'IFF', '#'] global opc opc = {'NOT':0, 'AND':1, 'OR':2, 'LPAR':3, 'RPAR':4, 'IMP':5, 'IFF':6, '#':7} global OP_f OP_f = (('P', 'R', 'R', 'P', 'R', 'R', 'R', 'R'),\ ('P', 'R', 'R', 'P', 'R', 'R', 'R', 'R'),\ ('P', 'R', 'R', 'P', 'R', 'R', 'R', 'R'),\ ('P', 'P', 'P', 'P', 'D', 'P', 'P', 'E'),\ ('E', 'E', 'E', 'E', 'E', 'E', 'E', 'E'),\ ('P', 'P', 'P', 'P', 'R', 'R', 'R', 'R'),\ ('P', 'P', 'P', 'P', 'R', 'R', 'R', 'R'),\ ('P', 'P', 'P', 'P', 'E', 'P', 'P', 'F')) # print OP_f setup_OP_function()
def Boolean_Parser(token_list): global opc global OP_f RPN = [] S = Stack() S.push(('#','#',7)) token_list.append(('#','#',7)) k = 0 while k < len(token_list): token = token_list[k] if token=='VAR': RPN.append(token) k += 1 else: input_op = opc[token] stok = S.pop() stack_op = opc[stok] action = OP_f[stack_op][input_op] if action=='P': S.push(stok) S.push(token) k += 1 elif action=='R': RPN.append(stok) elif action=='D': k += 1 elif action=='F': break else: print '*** Error ***' token_list.pop() return RPN
for p in prop_list: print p tokens = Boolean_Lex(p ) # print tokens var_values_dict = Build_Var_Dict(tokens) # print var_values_dict table = Init_Table(tokens, var_values_dict) # print table # Display_Table(tokens,table) rpn = Boolean_Parser(tokens) print rpn print
# This block defines an RPN Calculator # This version assumes that the input_list is a valid # Reverse Polish expression consisting only of Boolean # values (True and False) and the Boolean operators # 'NOT', 'AND', 'OR', 'LPAR', 'RPAR', 'IMP', 'IFF' # Daniel D. Warner # April 4, 2010 def Boolean_Calculator(input_list): S = Stack() while 0 < len(input_list): token = input_list.pop(0) if token == 'AND': y = S.pop() x = S.pop() S.push(x and y) elif token == 'OR': y = S.pop() x = S.pop() S.push(x or y) elif token == 'NOT': x = S.pop() S.push(not x) elif token == 'IMP': y = S.pop() x = S.pop() if x and (not y): S.push(False) else: S.push(True) elif token == 'IFF': y = S.pop() x = S.pop() if (x and y) or ((not x) and (not y)): S.push(True) else: S.push(False) else: S.push(token) # S.display() return S.pop()
def Boolean_Evaluate(rpn,table,var_values_dict): # This routine uses the Boolean_Calculator to evaluate # the rpn expressions for all operator entries in the # table for all the possible combinations of Boolean # values for the variables. These possible combinations # were previously computed and stored in var_values_dict. for k in range(len(table)): input = [] for token in rpn: if token == 'VAR': var = token var_values = var_values_dict[var] val = var_values[k] input.append(val) else: input.append(token) rpn_val = Boolean_Calculator(copy(input)) col = token table[k][col] = rpn_val # print input return table
def Display_Truth_Table(proposition): # Display the Truth Table for the given proposition. # Convert the proposition string to a list of tokens tokens = Boolean_Lex(proposition) # print tokens # Build the dictionary of variable values var_values_dict = Build_Var_Dict(tokens) # print var_values_dict # Initialize the Truth table table = Init_Table(tokens, var_values_dict) # Display_Table(tokens,table) # Convert the infix proposition to Reverse Polish rpn = Boolean_Parser(tokens) # print rpn # Evaluate the Boolean Expressions and complete the Truth Table truth_table = Boolean_Evaluate(rpn,table,var_values_dict) Display_Table(tokens,truth_table)
for p in prop_list: Display_Truth_Table(p) print

Exercise 2:  Construct several compound propositions other than those shown above, and display their abreviated Truth Table.