The logical operators which we introduced in the last section have a number of properties which should be familiar to you from your study of algebra. In this section, we will discuss those properties and present truth tables for many of them as a way of familiarizing ourselves with the use of truth tables to analyze logical expressions.

p & T = pis formally analogous to the algebraic identity

x * 1 = xThe analogy is made clear by the following substitutions

- p is substituted for x
- & is substituted for *
- T is substituted for 1

To analyze a logical expression, we construct a truth table with additional columns for each sub-expression:

Here we added columns for the sub-expressions T and p & T; when p has the value T, p & T is T and when p has the value F, p & T is F. Therefore p & T has the same values as p in all cases (the first and last columns are identical): anything ANDed with T remains unchanged.

pTp & TT T T F T F

A similar identity, which has no algebraic analog, is sometimes called a "**boundedness**" identity:

p | T = TIts truth table is

We see, then, that anything ORed with T is T.

pTp | TT T T F T T

Our next identity:

p | F = pis isomorphic to the algebraic identity

x + 0 = xwith the new substitutions

- | is substituted for +
- F is substituted for 0

shows that anything ORed with F is unchanged.

pFp | FT F T F F F

Our last identity (the other **boundedness** identity):

p & F = Fis isomorphic to the algebraic identity

x * 0 = 0and has the truth table

It illustrates that anything ANDed with F is F. This and the first identity combine to explain the concept of masking.

pFp & FT F F F F F

x + y = y + xwhich mean simply that the results of these operations do not depend on the ordering of the operands. From our analogies between addition and ORing, and between multiplication and ANDing, we expect that these logical operations should commute as well:x * y = y * x

p | q = q | pWe first construct a truth table illustrating the commutative property of AND by identifying the sub-expressions p & q and q & p:p & q = q & p

p & q is only T when both p and q are T (and likewise for q & p); the equality of the last two columns of the truth table verify that AND indeed commutes.

pqp & qq & pT T T T T F F F F T F F F F F F

In a similar fashion, we see that OR commutes as well:

p | q (as well as q | p) is T unless both p and q are F, as the last two columns indicate.

pqp | qq | pT T T T T F T T F T T T F F F F

x + ( y + z ) = ( x + y ) + zwe might expect that AND and OR are associative as well:x * ( y * z ) = ( x * y ) * z

p & ( q & r ) = ( p & q ) & rSince three variables are involved, our truth table must contain eight rows. We begin by investigating the associativity of AND, identifying the sub-expressionsp | ( q | r ) = ( p | q ) | r

q & rand

p & qat the lowest level (inside the parentheses and arbitrarily working from left to right). We then include columns in our truth table for the higher level sub-expressions on either side of the equal sign:

We proceed as follows:

pqrq & rp & qp & ( q & r )( p & q ) & rT T T T T T T T T F F T F F T F T F F F F T F F F F F F F T T T F F F F T F F F F F F F T F F F F F F F F F F F

- The q & r column is filled in one row at a time using AND on the contents of the q and r columns.
- The p & q column is filled in one row at a time using AND on the contents of the p and q columns.
- The p & ( q & r ) column is filled in one row at a time using AND on the contents of the p and the q & r columns.
- The (p & q) & r column is filled in one row at a time using AND on the contents of the p & q and the r columns.
- Finally, the last two columns are compared and found equal: therefore AND is associative.

We verify the associativity of OR in exactly the same way:

Of some practical use, and not quite as self-evident, is the associativity of the XOR operator:

pqrq | rp | qp | ( q | r )( p | q ) | rT T T T T T T T T F T T T T T F T T T T T T F F F T T T F T T T T T T F T F T T T T F F T T F T T F F F F F F F

As is obvious from their truth tables, AND, OR, XOR and EQUIVALENCE are all commutative. While we have not shown it explicitly for EQUIVALENCE, it too is associative. So we can make a very useful general statement:

pqrq X rp X qp X ( q X r )( p X q ) X rT T T F F T T T T F T F F F T F T T T F F T F F F T T T F T T F T F F F T F T T T T F F T T F T T F F F F F F F

All of our commutative operators are also associative.

x * ( y + z ) = x * y + x * zSimilarly, we expect that AND distributes over OR:

p & ( q | r ) = ( p & q ) | ( p & r )Since we have three logical variables we must again have eight rows in our truth table. As always, the first three columns correspond to the logical variables p, q and r. The next three columns are for the lowest level sub-expressions

- q | r
- p & q
- p & r

We proceed in exactly the same fashion as we did with associativity:

pqrq | rp & qp & rp & ( q | r )( p & q ) | ( p & r )T T T T T T T T T T F T T F T T T F T T F T T T T F F F F F F F F T T T F F F F F T F T F F F F F F T T F F F F F F F F F F F F

- The first three columns contain all possible values for the variables p, q and r.
- The q | r column contains the results of ORing the q and r columns.
- The p & q column contains the results of ANDing the p and q columns.
- The p & r column contains the results of ANDing the p and r columns.
- The p & (q | r) column contains the results of ANDing the p column with the q | r column.
- The (p & q) | (p & r) column contains the results of ORing the p & q column with the p & r column.
- Associativity is verified by examining the last two columns and finding them equal.

p | ( q & r ) = ( p | q ) & ( p | r )The truth table verifying this fact is constructed in exactly the same fashion as the previous truth table; by this time, you should be able to understand the construction of this truth table on your own:

pqrq & rp | qp | rp | ( q & r )( p | q ) & ( p | r )T T T T T T T T T T F F T T T T T F T F T T T T T F F F T T T T F T T T T T T T F T F F T F F F F F T F F T F F F F F F F F F F

~ T = FThe latter is analogous to the algebraic relationship~ F = T

- ( -1 ) = 1where logical negation is substituted for arithmetic negation.

The next property can be expressed verbally as "either p is true or p is false":

p | ~p = TThat is, p + ~p is a tautology.

p~pp | ~pT F T F T T

The final complement property can be expressed verbally as "p cannot be both true and false":

p & ~p = FIn other words, p & ~p is a contradiction.

p~pp & ~pT F F F T F

p | q = Tand

p & q = Fimplies

q = ~pWe will not present a truth table to illustrate this property, because the first two expressions have the form of constraints (which are not what truth tables are designed for), but you can easily convince yourself that the property is valid:

- If p | q = T, then either p or q must be T.
- If p & q = F, then either p or q must be F.
- Thus if p is T, q must be F and if q is T, p must be F.
- Therefore p = ~q.

~ ~p = pis clearly isomorphic to

- ( -x ) = xand has the following truth table:

p~p~ ~pT F T F T F

p O pfor any p. For example,

p ↔ pjust as

x = x

p O qis the same as

q O pfor any p and q. Symmetry is essentially the same as commutivity, but is more often applied to operators which express equivalence relationships:

( p ↔ q ) = ( q ↔ p )(which is analogous to)

( x = y ) = ( y = x )The following truth table shows that the EQUIVALENCE relationship is symmetric:

(since the last two columns are identical).

pqp ↔ qq ↔ pT T T T T F F F F T F F F F T T

p O qand

q O rimply that

p O r.For instance, the equivalence relationship is transitive:

(( p ↔ q ) & ( q ↔ r )) → ( p ↔ r )just as numerical equality is:

(( x = y ) and ( y = z )) → ( x = z )To show this, we construct a truth table along the same lines as before:

p | q | r | p ↔ q | q ↔ r |
p ↔ r | ( p ↔ q ) & ( q ↔ r ) |
(( p ↔ q ) & ( q ↔ r )) → ( p ↔ r ) |

T | T | T | T | T | T | T | T |

T | T | F | T | F | F | F | T |

T | F | T | F | F | T | F | T |

T | F | F | F | T | F | F | T |

F | T | T | F | T | F | F | T |

F | T | F | F | F | T | F | T |

F | F | T | T | F | F | F | T |

F | F | F | T | T | T | T | T |

Here, the lowest level sub-expressions are

- p ↔ q
- q ↔ r
- p ↔ r

( p ↔ q ) & ( q ↔ r )The final column represents the transitivity of the EQUIVALENCE operator and is the result of the IMPLIES operator acting on the previous column and the p ↔ r column. Since all of the entries in the last column are T, the relationship is a tautology: it is always true.

This is a good place to note the following patterns:You should prove to yourself that IMPLIES is not symmetric, but it is reflexive and transitive.

- The p ↔ q sub-expression does not depend on r; therefore the first two rows should be the same, the second two rows should be the same, the third two rows should be the same, and the last two rows should be the same.

- The q ↔ r sub-expression does not depend on p, so the first four rows should be the same as the last four.

- The p ↔ r sub-expression does not depend on q, so the first two rows should be the same as the second two rows, and the third set of two rows should be the same as the last two rows.

These patterns can help you find mistakes in a complicated truth table.

p O p = pfor any p. Both AND and OR are idempotent:

p & p = p

pp & pT T F F p | p = p

pp | pT T F F

p | (p & q) = pand

pqp & qp | (p & q)T T T T T F F T F T F F F F F F

p & (p | q) = pThe idea here is that in both expressions, q is "absorbed" into p.

pqp | qp & (p | q)T T T T T F T T F T T F F F F F

(( p → q ) & ( q → p )) = ( p ↔ q )

The equality of the last two columns shows that EQUIVALENCE is a sort of two-way implication; hence the term biconditional. The biconditional is often expressed as "if and only if" (abbreviated as "iff").

pqp → qq → pp ↔ q( p → q ) & ( q → p )T T T T T T T F F T F F F T T F F F F F T T T T

~ ( p | q ) = ~p & ~qwhich we will abbreviate as "DeMorgan's 1" or "DeM1", and which has the following truth table:

and "DeMorgan's 2" or "DeM2":

pqp | q~p~q~ ( p | q )~p & ~qT T T F F F F T F T F T F F F T T T F F F F F F T T T T

~ ( p & q ) = ~p | ~qWe can use DeMorgan's Laws in the simplification of logical expressions. For instance,

pqp & q~p~q~ ( p & q )~p | ~qT T T F F F F T F F F T T T F T F T F T T F F F T T T T

~ ( p & ( q | ~ r ))using DeM2 (where the sub-expression q | ~r takes the place of q in the law) becomes

~ p | ~ ( q | ~ r )We then use DeM1 (where the sub-expression ~r takes the place of p in the law) and the involution property to transform this into

~ p | ( ~ q & r )Finally, we use the second distributive property (with ~p and ~q instead of p and q in the original statement of the property) to obtain

( ~ p | ~ q ) & ( ~ p | r )There are other properties, similar to DeMorgan's Laws in that they relate various expressions. We will state them here, and leave the proofs to the reader:

There are also two implications which might at first sight seem incorrect, but their truth tables prove otherwise:

p → q is equivalent to ~q → ~p p → q is equivalent to ~p | q (p & q) → r is equivalent to p → (q → r) p ↔ q is equivalent to (p & q) | (~p & ~q) The first is called

transposition, and the third is calledexportation.

- (p & q) → p
- p → (p | q)

Now that we have analyzed the logical properties we see that in general, the algorithm for completing an arbitrary truth table is:

- Determine the number of variables in the logical expression; for n variables, you will need a
truth table with 2
^{n}rows. - The first n columns (one for each variable) are then completed using the templates in the previous section; they represent all possible values of the variables.
- The lowest level sub-expressions (those deepest inside nested parentheses) are identified and columns are added to the truth table for each of them.
- The contents of these columns are filled in using the basic logical operations on the variables involved, one row at a time.
- Columns are added for higher level sub-expressions until the entire logical expression is accounted for.
- The contents of those columns are filled in using the basic logical operations on the contents of the appropriate previous columns.
- To determine the equality of logical expressions, the corresponding columns are compared to see if they are the equal.

Now that we are comfortable using truth tables to analyze logical expressions, we will see in the next section how to determine the validity of an argument.

Go to: Title Page Table of Contents Index

©2013, Kenneth R. Koehler. All Rights Reserved. This document may be freely reproduced provided that this copyright notice is included.

Please send comments or suggestions to the author.