On Truth Tables

Previously, we began a discussion centered on propositional logic. To that end, we constructed a working definition for propositional logic. We said it was the rules by which we construct mathematical statements that evaluate to either True or False. As well, I mentioned the practical application can be demonstrated through truth tables. Further, along the way, we need to dig a little deeper into connectives. There's a fair amount of ground to cover so let's get started!

A Little Context

What if I told you propositional logic was simply an abstraction for how circuits function? Maybe a natural follow up question would be something like, what kind of circuits and that would be a good question indeed.

I tend to view propositional logic as the abstracted substrate for computational circuits. Thus, propositional logic is fundamentally a means to model circuits at the heart of electronics. More precisely, computers. Fortunately, the abstraction can function at multiple levels of resolution too.

For example, I can state This is an essay on discrete mathematics which is a simple, low-resolution proposition. Either this statement is true or it is false. In fact, we can see the truth value is True in this case. Agreed?

Next, I could assert This is an essay on discrete mathematics and it was written by Dr. Jason M. Pittman. Here, we introduced a connective (and) to increase the resolution slightly. Now, for the entire compound propositional statement to be true, both propositions must be individually true. I'd say we still have a True as the outcome but there's always the possibility that I'm Tom Cruise and thus the statement could be False.

Lastly, I might state If this is an essay on discrete mathematics, then I am a computer scientist and my name is Dr. Jason M. Pittman. That's three propositions coupled with two connectives. Further, we've seen the and before but the conditional phrase if, then is new. We call this connective an implication because the truth condition of the first clause implies the truth condition of the second. More specifically, when the if clause is True, the then* clause must also be True. Admittedly, such a compound statement is not so easily evaluated by sight, though. Maybe we need a tool, a way to model the outcomes.

Truth Tables

Okay, by using a truth table, we can decode the rules of a given connective and model the set of possible truth values for any propositional statement. I believe truth tables are the real power in propositional logic. They certainly are the definitive model for computation.

Statement: This is an essay on discrete mathematics and it was written by Dr. Jason M. Pittman

Model: p /\ q
Truth Table:

| p | q | p /\ q |
| T | T | ? |
| T | F | ? |
| F | T | ? |
| F | F | ? |

The individual propositions represented by P and Q (a) can only be True or False and (b) always have the same paired states. That is, P and Q cannot take on any other outcomes.

Now, we simply apply the connective rule and cross evaluate by row, top to bottom. The results should be True, followed by three False.

How about the double connective statement we constructed earlier with three propositions? Give building the truth table a try and let me know your results!

In the meantime, we can look at our simple and truth table to imagine how our model applies to computation. An obvious example would be the following programming idiom for playing the game of picking a number between 1 and 10.

function pick_a_number:
if p > 1 && q < 10
do something
else do something else

Another example is how the processor runs this code (assuming the code was correct, complete, and so forth). Voltage off or on corresponds directly to our concept of propositional and after all.

Can you think of other examples?