Logical Expressions

Harold Nelson

10/7/2020

This may be your first real experience with a mathematical system that doesn’t involve numbers.

The atomic elements in this system are statements instead of numbers.

Instead of addition and multiplication, we have conjunction (and) and disjunction (or). If \(x\) is a number, we encounter \(-x\). If p is a statement, we encounter not p.

In what follows, we will use the python notation for and, or, and not. Conveniently, python just uses these English words.

Truth Tables

I assume that from reading the text you are familiar with the concept of a truth table and the way an author writing 50 years ago would display and use them. We will use python to explore the same concepts and issues. The heart of what follows is a list of the truth values, which we will call TV. Iteration over this list can be used to produce truth tables or even to substitute for them.

TV = [True, False]

Exercise

Use a for loop iterating over TV to display the truth value for negation.

Answer

print("P    ", "Not P")
## P     Not P
for P in TV:
    print(P, not P)
## True False
## False True

Exercise

Use a nested for loop to display the truth table for P and Q.

Answer

print("P  ", "Q  ", "P and Q")
## P   Q   P and Q
for P in TV:
    for Q in TV:
        print(P,  Q, P and Q)
## True True True
## True False False
## False True False
## False False False

Exercise

Use a nested for loop to display the truth table for P or Q.

Answer

print("P  ", "Q  ", "P or Q")
## P   Q   P or Q
for P in TV:
    for Q in TV:
        print(P,  Q, P or Q)
## True True True
## True False True
## False True True
## False False False

Logical Equivalence

These three operators can be combined with multiple logical variables to generate complex “compound” logical expressions. We will focus on the way to determine if two logical expressions are identical independently of the particular statements which appear in them.

It is well known that the logical expression not (P and Q) is equivalent to not P or not Q. You could prove this to yourself by thinking carefully about the meanings of these two expressions. But the mathematical approach used in the finite math text proceeds as follows.

  1. Create a truth table with two columns representing the two expressions.

  2. Examine the two columns visually. If they agree in every row, then they are equivalent. If they disagree in any row, then they are not equivalent.

Exercise

Do this in python. Don’t worry about the spacing. Just look at the last two columns.

Answer

print("P  ", "Q  ", "not(P and  Q)", "not P or not Q")
## P   Q   not(P and  Q) not P or not Q
for P in TV:
    for Q in TV:
        print(P,  Q, not ( P and Q), not P or not Q)
## True True False False
## True False True True
## False True True True
## False False True True

A Better Way

We’ve just used a 2020 tool to accomplish a 1970 task.

Here’s a 2020 method. Instead of creating two columns, create two lists and ask if they are equal.

Here’s what I mean.

exp1 = []
exp2 = []
for P in TV:
    for Q in TV:
        exp1.append(not(P and Q))
        exp2.append(not P or not Q)
exp1 == exp2 
## True

If you’re feeling nostalgic about 1970, you could print out the two lists and compare them visually. I’d rather not.

Exercise

We just used our pythonic trick to prove one of DeMorgan’s two laws.

Do the same for the second one.

Answer

exp1 = []
exp2 = []
for P in TV:
    for Q in TV:
        exp1.append(not(P or Q))
        exp2.append(not P and not Q)
exp1 == exp2 
## True

Another Example

Use this method to decide if P and not Q is logically equivalent to not P or Q.

Answer

exp1 = []
exp2 = []
for P in TV:
    for Q in TV:
        exp1.append(P and not Q)
        exp2.append(not P or Q)
exp1 == exp2 
## False

Associativity

In the mathematics of real numbers we know that \[ x + (y + z) = (x+y)+z\] no matter what the values of these three variables are. We say that addition is associative.

Exercise

Is and associative? We’ll need a third variable, call it R. The question is whether P and (Q and R) is equal to (P and Q) and R.

Do this in python. You need to add a level to our nested for loops.

Answer

exp1 = []
exp2 = []
for P in TV:
    for Q in TV:
        for R in TV:
            exp1.append(P and (Q and R))
            exp2.append((P and Q) and R)
exp1 == exp2 
## True

The Distributive Law

In the mathematics of real numbers we know that \[ x *(y + z) = (x*y)+(x*z)\] no matter what the values of these three variables are. We say that multiplication distributes over addition.

Is there something analogous in the mathematics of logic. Does and distribute over or? Does or distribute over and?

Check the “and over or” case.

Answer

exp1 = []
exp2 = []
for P in TV:
    for Q in TV:
        for R in TV:
            exp1.append(P and (Q or R))
            exp2.append((P and Q) or (P and R))
exp1 == exp2 
## True

Now check the or over and case.

Answer

exp1 = []
exp2 = []
for P in TV:
    for Q in TV:
        for R in TV:
            exp1.append(P or (Q and R))
            exp2.append((P or Q) and (P or R))
exp1 == exp2 
## True

Generalization

The code above works well, but it would be better if one did not have to examine the code to see where to modify it to use different logical expressions. Could we rewrite this as a function? How can we supply the logical expressions as arguments? To do this use python’s ability to use functions as parameters of other functions. Write a function compare(f,g), where f and g are functions which return logical values. The function compare returns True if f and g are logically equivalent and False if they are not.

Answer


def compare(f,g):
    
    # Note that f and g are functions.
    
    TV = [True,False]
    # Initialize empty lists
    exp1 = [] 
    exp2 = []

    # Loop through possible values of p and q
    for P in TV:
    
        for Q in TV:
        
            exp1.append(f(P,Q))
            exp2.append(g(P,Q))

    # Determine conclusion
    if exp1 == exp2:
    
        conclusion = "Yes - Equivalent"
        
    else:
    
        conclusion = "No - Not Equivalent"

    return conclusion

Exercise

Let’s try this. We need two functions which return logical values.

Answer

def f1(a,b):

    return not a and not b
    
def f2(c,d):

    return not(c or d)
    
compare(f1,f2)    
## 'Yes - Equivalent'

A Final Note for Today

There is a symmetry in the distributive laws in this mathematical system.

Do you see the same symmetry in the mathematics of numbers? Does addition distribute over multiplication? Try one numerical using 3, 4, and 5.

Answer

\[exp1 = 3 + (4 * 5)\]

\[exp2 = (3+4) * (3+5)\] Calculate the two expressions in python.

print(3 + (4 *5))
## 23
print((3 + 4) * (3 + 5))
## 56

This second distributive law is not a feature of real number mathematics.