Properties of Logical Operators

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.

Identities

The identities help to give us a feel for how the logical operators behave in simple situations. The first identity:
p & T = p
is formally analogous to the algebraic identity
x * 1 = x
The analogy is made clear by the following substitutions
• p is substituted for x
• & is substituted for *
• T is substituted for 1
We will call such an analogy an "isomorphism", a word whose meaning derives from Greek words which mean same ("iso") shape ("morph"). Many of our logical properties are isomorphic to algebraic properties.

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

 p T p & T T T T F T F
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.

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

p | T = T
Its truth table is
 p T p | T T T T F T T
We see, then, that anything
ORed with T is T.

Our next identity:

p | F = p
is isomorphic to the algebraic identity
x + 0 = x
with the new substitutions
• | is substituted for +
• F is substituted for 0
Its truth table
 p F p | F T F T F F F
shows that anything ORed with F is unchanged.

Our last identity (the other boundedness identity):

p & F = F
is isomorphic to the algebraic identity
x * 0 = 0
and has the truth table
 p F p & F T F F F F F
It illustrates that anything ANDed with F is F. This and the first identity combine to explain the concept of masking.

Commutativity

You are familiar with the commutative properties of addition and multiplication:
x + y = y + x

x * y = y * x

which 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:
p | q = q | p

p & q = q & p

We first construct a truth table illustrating the commutative property of AND by identifying the sub-expressions p & q and q & p:
 p q p & q q & p T T T T T F F F F T F F F F F F
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.

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

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

Associativity

Since addition and multiplication are both associative:
x + ( y + z ) = ( x + y ) + z

x * ( y * z ) = ( x * y ) * z

we might expect that AND and OR are associative as well:
p & ( q & r ) = ( p & q ) & r

p | ( q | r ) = ( p | q ) | r

Since three variables are involved, our truth table must contain eight rows. We begin by investigating the associativity of AND, identifying the sub-expressions
q & r
and
p & q
at 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:
 p q r q & r p & q p & ( q & r ) ( p & q ) & r T 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
We proceed as follows:
1. The q & r column is filled in one row at a time using AND on the contents of the q and r columns.
2. The p & q column is filled in one row at a time using AND on the contents of the p and q columns.
3. 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.
4. 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.
5. 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:

 p q r q | r p | q p | ( q | r ) ( p | q ) | r T 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
Of some practical use, and not quite as self-evident, is the associativity of the XOR operator:
 p q r q X r p X q p X ( q X r ) ( p X q ) X r T 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
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:
All of our commutative operators are also associative.

Distribution

Algebraically, we say that multiplication distributes over addition:
x * ( y + z ) = x * y + x * z
Similarly, 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
and the last two columns are for the highest level sub-expressions on either side of the equal sign:
 p q r q | r p & q p & r p & ( 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
We proceed in exactly the same fashion as we did with associativity:
1. The first three columns contain all possible values for the variables p, q and r.
2. The q | r column contains the results of ORing the q and r columns.
3. The p & q column contains the results of ANDing the p and q columns.
4. The p & r column contains the results of ANDing the p and r columns.
5. The p & (q | r) column contains the results of ANDing the p column with the q | r column.
6. The (p & q) | (p & r) column contains the results of ORing the p & q column with the p & r column.
7. Associativity is verified by examining the last two columns and finding them equal.
It is interesting to note that OR distributes over AND even though addition does not distribute over multiplication:
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:
 p q r q & r p | q p | r p | ( 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

Complements

The following logical properties illustrate some of the more obvious characteristics of the logical constants and operators:
~ T = F

~ F = T

The latter is analogous to the algebraic relationship
- ( -1 ) = 1
where 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 = T

 p ~p p | ~p T F T F T T

That is, p + ~p is a
tautology.

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

p & ~p = F

 p ~p p & ~p T F F F T F

In other words, p & ~p is a contradiction.

Uniqueness of the Complement

The following property illustrates the uniqueness of the complement operator (NOT):

p | q = T
and
p & q = F
implies
q = ~p
We 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:
1. If p | q = T, then either p or q must be T.
2. If p & q = F, then either p or q must be F.
3. Thus if p is T, q must be F and if q is T, p must be F.
4. Therefore p = ~q.
This property is an example of an argument.

Involution

The involution property
~ ~p = p
is clearly isomorphic to
- ( -x ) = x
and has the following truth table:
 p ~p ~ ~p T F T F T F

Reflexivity

An operator "O" is reflexive if
p O p
for any p. For example,
p ↔ p
just as
x = x

Symmetry

An operator "O" is symmetric if
p O q
is the same as
q O p
for 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:
 p q p ↔ q q ↔ p T T T T T F F F F T F F F F T T
(since the last two columns are identical).

Transitivity

An operator "O" is transitive if
p O q
and
q O r
imply 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
The next highest level sub-expression is
( 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:

• 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.

You should prove to yourself that IMPLIES is not symmetric, but it is reflexive and transitive.

Idempotence

The idea of idempotence of an operator "O" is essentially the following:
p O p = p
for any p. Both AND and OR are idempotent:
p & p = p

 p p & p T T F F

p | p = p

 p p | p T T F F

Absorption

The absorption properties are
p | (p & q) = p

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

and
p & (p | q) = p

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

The idea here is that in both expressions, q is "absorbed" into p.

Biconditional

We list the biconditional as a property, although it more properly is an expression of EQUIVALENCE in terms of IMPLIES:
(( p → q ) & ( q → p )) = ( p ↔ q )
 p q p → q q → p p ↔ 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
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").

DeMorgan's Laws

Our final properties are called "DeMorgan's Laws" and describe how AND and OR can be related (if you have enough NOTs!):
~ ( p | q ) = ~p & ~q
which we will abbreviate as "DeMorgan's 1" or "DeM1", and which has the following truth table:
 p q p | q ~p ~q ~ ( p | q ) ~p & ~q T 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
and "DeMorgan's 2" or "DeM2":
~ ( p & q ) = ~p | ~q

 p q p & q ~p ~q ~ ( p & q ) ~p | ~q T 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

We can use DeMorgan's Laws in the simplification of logical expressions. For instance,
~ ( 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:
 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 called exportation.

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

• (p & q) → p
• p → (p | q)

Summary

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

1. Determine the number of variables in the logical expression; for n variables, you will need a truth table with 2n rows.
2. 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.
3. The lowest level sub-expressions (those deepest inside nested parentheses) are identified and columns are added to the truth table for each of them.
4. The contents of these columns are filled in using the basic logical operations on the variables involved, one row at a time.
5. Columns are added for higher level sub-expressions until the entire logical expression is accounted for.
6. The contents of those columns are filled in using the basic logical operations on the contents of the appropriate previous columns.
7. 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.