Truth Tables
As discussed in the previous post, compound predicates are built from other predicates and propositions using logical connectives (¬, ∧, ∨, ⇒, ↔). The truth value of the compound predicate depends on the truth values of its components.
Truth tables can be used to define the meaning of logical operators and to investigate compound expressions. By investigating the truth values of compound expressions, you can establish new logical concepts. This is especially useful when it comes to rewrite rules which we will discuss a little bit later on.
Components of a Truth Table
Truth tables consists of a header and a body. When defining the meaning of a logical connective, the leftmost column lists the variable you are evaluating and the rightmost column lists the connective.
Example:
This truth table defines the conjunction connective. By looking at this truth table we can see that if P and Q both have a truth value of TRUE then the expression P ∧ Q also has a truth value of TRUE, but any other combination of P and Q means that the truth value of P ∧ Q is FALSE.
When investigating the truth value for a compound expression, the left most column headers list the variables and the rightmost header lists the compound expression.
The Body of a truth table always contains one row for every possible combination of the variables involved.
Note: The variables in a truth table are propositional variables. This allows you to work with the most simplified form of possible combinations and outcomes.
Here are truth tables for all of the logical connectives:
Note: Regarding the truth table for the Disjunction connective, this table shows the truth values for what is referred to as the inclusive or. This means that the proposition evaluates to TRUE if P and Q are both TRUE. You may encounter times when the exclusive or is specified (sometimes called XOR or EOR). This simply means that one of the criterion must be true but not both.
Equivalence and Implication
These two connectives may not be as immediately apparent or intuitive and the others so I think they warrant a bit more discussion.
Equivalence
This one isn’t too bad. It’s basically the same as the = operator (Note to self: check thesaurus for “same as”). It evaluates to TRUE if and only if the two involved propositional variables evaluate to the same truth value (either both TRUE or both FALSE).
Implication
This one is a bit more confusing because of the way “implies” is used informally versus its mathematical logical meaning. To better explain what the Implication connective means, I think it would be easier to start with what it doesn’t mean:
- It doesn’t mean “suggests”.
- It doesn’t mean “causes”.
The following sentence is completely logical under the mathematical definition of Implication:
“The sky is blue implies January is a month”
This does not mean “Since the sky is blue January is a month” or “January is a month because the sky is blue”
Note: Always remember that the ONLY time that an implies statement is FALSE is if the Antecedent (P) is TRUE but the Consequent (Q) is FALSE.
So let’s take a closer look at the Implication truth table again:
To better understand this, it might be better to evaluate the conditions in stages. We will start by examining the truth values for P. If the truth value for P is FALSE, we aren’t even going to check what the truth value for Q is because we already know that the expression is TRUE. If P is TRUE then we have to go on to evaluate if Q is TRUE, if it is the expression is TRUE, but if it isn’t then the expression is FALSE.
I like to think of this as “Innocent until proven guilty” or “True until proven false”.
Example:
Proposition: If your pet is a dog, then your pet is a male.
Suppose my pet is a dog… ok now I can check the gender… it turns out my dog is male… the statement must be true
Suppose my pet is a dog… ok now I can check the gender… it turns out my dog is female… I’ve proven the statement false
Suppose my pet is a cat… ok I could check the gender but it doesn’t really matter because the statement only applies to dogs so I wouldn’t be proving anything even if my cat was female… without evidence to prove that the statement wrong, I must assume that it is true.
Suppose my pet is a bird… same logic applies as if my pet was a cat… without evidence to prove that the statement wrong, I must assume that it is true.
Implication is probably the least intuitive of all the connectives and some of that probably comes from how we think about “implications” outside of mathematics. Let’s consider for a moment why this is.
Consider the following scenario:
I have a bag of 10 marbles. One is blue and nine are yellow.
I ask you to pick one marble out of the bag without looking and offer the following implication:
“If you pick a blue marble, the next will be yellow”
So you pick a marble:
Suppose I pick a blue marble… ok now I can pick another marble… it turns out it is yellow… The statement must be true. (T ⇒ T) = T
Suppose I pick a blue marble… ok now I can pick another marble… it turns out it is blue… The statement must be false. (T ⇒ F) = F
Those two seem pretty intuitive right? So let’s look at the tricky ones:
Suppose I pick a yellow marble… ok now I can pick another marble… it turns out it is also a yellow marble… ok so I don’t have enough information to know if the original statement is true or not. In real life if a friend asked me to do this and draw a conclusion I would say that there isn’t enough information to determine if it is TRUE or FALSE because the first marble I drew wasn’t blue so can’t actually test the hypothesis. Ahhh but let’s remember our definition of a proposition: a declarative sentence that when evaluated is either TRUE or FALSE, but not both.
By definition, our implication proposition MUST evaluate to either TRUE or FALSE, it cannot be both or neither. So now the question really becomes given this scenario, do we assume FALSE or do we assume TRUE? When it comes to implication, we always assume TRUE. This is why I use the phrase “innocent until proven guilty”. Just like in a court of law, the defendant is innocent until they can be proven guilty. Likewise when it comes to an implication, we assume that the overall statement (P ⇒ Q) is TRUE unless we can definitively prove that it is FALSE.
Predicate Strength
You can think about Implication as “ordering” the predicates that make up its operands. This order is referred to as the strength of the predicate. The “strongest” predicate is the one that implies the other. Consider P ⇒ Q, in this situation P is the stronger predicate and Q is the weaker.
Example:
The variable x is defined with a type of integer.
Consider the predicate: x > 5 ⇒ x > 0
To state that x is greater than 5 implies that x is greater than 0. This implication is TRUE regardless of the value of x, and the predicate x > 5 is the stronger predicate while x > 0 is the weaker one.
The only time that both predicates are of equal strength is when P ⇒ Q and Q ⇒ P. When the predicates are of equal strength they are equivalent: ↔
