This chapter reviews elementary propositional logic, the calculus of combining statements that can be true or false using logical operations. It also reviews the connection between logic and set theory.

The fundamental elements of propositional logic are
*propositions*—statements that can be either
true or false—and logical operations that act on one proposition
(unary operations) or two propositions (binary operations).
A proposition is like a variable that can take two values, the
value "true" and the value "false."
Logical operators combine propositions to make other propositions,
following rules that are outlined in this chapter.
In this chapter, lowercase italic letters like p, q,
and r stand for propositions, the letter
T stands for true, and the
letter F stands for false.
The letter T also stands for a proposition that is always true,
and the letter F stands for a proposition that is always false.
The logical operators we review are !,
|, &, →, and
↔.
We also review some simple identities for logical operators,
the order of operations for evaluating compound propositions,
and logical arguments.

Suppose we have two propositions, p and q.
The propositions are *equal* or
logically equivalent
if they always have the same truth value.
That is, p and q are logically equivalent
if p is true whenever q is true, and vice versa,
and if p is false whenever q is false, and vice versa.
If p and q are logically equivalent, we
write p = q.

Logical operations act on propositions, turning them into other propositions. Unary operations act on a single proposition; binary operations act on two propositions.

The simplest logical operation is negation. Negation operates on a single proposition—it is unary. The logical negation of the proposition p, is !p. The operator ! is sometimes represented by the symbol ¬, a minus sign (−), a tilde (˜), or the word "not." The negation of p is sometimes called the inverse of p. If p is a proposition, so is !p: !p is true when p is false, and !p is false when p is true. Another way to state this relation is !T = F, and !F = T. Logical negation is like a negative sign in arithmetic (a negative sign, not a minus sign, which operates on a pair of numbers),

The logical operation |, also called or and logical disjunction, is an operation on two propositions (a binary operation) that results in another proposition: the proposition (p | q) is true if p is true or if q is true or if both p and q are true. The operation | is sometimes represented by a vee (∨) or by the word "or." We can say what | does by saying what value it takes for each of the four combinations of true and false its arguments can have:

(T | T) = T, (T | F) = T, (F | T) = T, (F | F) = F.

This can be summarized in a truth table, which displays in tabular form the value of (p | q) for each combination of values of p and q:

The first two columns of the table show the truth values of p and q individually; the third column gives the corresponding truth values of (p | q). For example, the entry corresponding to p being true and q being true is T, because (T | T) = T. The logical operator | is analogous to addition in arithmetic.

The logical operation &, also called logical conjunction, combines two propositions to produce another. The proposition (p & q) is true if both p is true and q is true; it is false if either p is false or q is false (or both): (T & T) = T, (T & F) = F, (F & T) = F, (F & F) = F. The operation & is sometimes represented by a wedge (∧) or the word "and." Here is the truth table for &:

The logical operator & is analogous to multiplication in arithmetic. All the remaining logical operations can be defined in terms of !, |, and &; for that reason (and their simplicity) the operations !, | and & are considered fundamental while the others are not.

Just like putting a minus sign in front of an algebraic symbol, the operation of negation takes precedence over all other operations, so, for example, (p | !q) is interpreted as (p | (!q)).

The following identities are useful:

- (p | !p) = T
- (p & !p) = F
- (p & p) = (p | p) = p.

The last identity says that both (p & p) and (p | p) are logically equivalent to p: If p is true, so are (p & p) and (p | p). If p is false, so are (p & p) and (p | p).

The proposition (p → q), also written (if p then q) and (p implies q), is true if p is false, if q is true, or both. The proposition (p → q), called a conditional, is logically equivalent to ( (!p) | q). Here is the truth table for (p → q):

In logic, the proposition (p → q) is
true whenever p is false, which some people find counter-intuitive.
In fact, that (F → T) and (F → F) are both true is
a matter of definition, but the definition does not disagree with common usage:
Think of (p → q) as the assertion
(if p then q), that is, "if p is true,
then q is also true."
This assertion says nothing about the truth of q when p is false,
only that if p is true, q must also be true.
Therefore, when p is false, the assertion cannot be wrong.
If p is true, q must also be true, or the assertion is incorrect.

Finally, the proposition (p ↔ q), also written (p IFF q) and (p if and only if q), is true if both p and q are true, or if both p and q are false; otherwise, the proposition is false. That is, (p ↔ q) is logically equivalent to

(p & q) | ( !p & !q ).

p ↔ q is also logically equivalent to

(p → q) & (q → p).

Thus (T ↔ T) = T, (T ↔ F) = F, (F ↔ T) = F, and (F ↔ F) = T. Here is the truth table for (p ↔ q):

Recall that two propositions are equal (or logically equivalent), p = q, if they always have the same value. Every proposition involving the operations !, |, &, →>, and ↔ has a logically equivalent proposition that uses only the operations !, |, and &. Here are some identities:

p → q = !p | q.

p ↔ q = (p & q) | (!p & !q).

Here are some useful identities that combine ! with & and |:

- !(p | q) = !p & !q
- !(p & q) = !p | !q.

These are called de Morgan's Laws.
They are analogous to de Morgan's Laws in set theory, discussed in

The logical operations & and | behave much like multiplication and addition, respectively, and the operation ! behaves like a negative sign. They are associative, distributive, and commute with themselves (but not each other). Here are the associative relations: if p, q, and r are propositions, then both of the following are true:

- ( (p & q) & r ) = ( p & ( q & r ) ) = ( p & q & r )
- ( (p | q) | r ) = ( p | ( q | r ) ) = ( p | q | r ).

These are much like the arithmetic identities (a×b)×c = a×(b×c) = a×b×c and (a+b)+c = a+(b+c) = a+b+c. & and | also commute with themselves (but not with each other) as follows:

- ( p | q ) = ( q | p )
- ( p & q ) = ( q & p )

Those relations are like the arithmetic identities a×b = b×a and a+b = b+a. Moreover, & and | satisfy distributive relationships:

- ( p & (q | r) ) = ( (p & q) | (p & r) )
- ( p | (q & r) ) = ( (p | q) & (p | r) ).

Those relationships are like the arithmetic identity a×(b+c) = a×b + a×c.

The *converse* of the proposition (p → q) is the
proposition (q → p).
The *contrapositive* of the proposition (p → q)
is ( !q → !p ).
The proposition (p → q) is
logically equivalent
to its
contrapositive, which we can prove as follows, using the identities above:

(p → q) = ( !p | q )

= ( !p | !(!q) )

= ( !(!q) | !p )

= ( !q → !p ).

There are at least two strategies to find a truth table for complicated combinations of propositions: simply plug in all combinations of values of true and false for the propositions it is built from, or try to simplify the proposition using the identities presented previously.

Since a 2 by 2 truth table has 4 cells, each of which can contain either T or F, by the Fundamental Rule of Counting there are only

2×2×2×2 = 2^{4} = 16

possible 2 by 2 truth tables. So, no matter how complicated a logical expression involving two propositions might appear to be, it boils down to—is logically equivalent to—one of 16 possibilities. What are those possibilities? We've seen many of them already. For example, the proposition could be identically true, no matter what p and q are. The proposition

(p ↔ p) & (q ↔ q) = T;

that is, its truth table has T in all four cells. Similarly, a compound proposition involving p and q could be identically false—have F in all four cells of its truth table. An example is

(p & !p) | (q & !q) = F.

Or the proposition could be logically equivalent to p, or to q, or to p|q, or to p&q, and so on. Any compound proposition built from p and q using the logical operations !, |, &, →, and ↔ is logically equivalent to one of the following propositions:

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

For example,

(q → p) = (p | !q),

the eleventh of these. And

(p ↔ !(q → !p)) = (!p | q),

the tenth proposition on the list.

There is only one way to fill all four cells with T and only
one way to fill all four with F; those correspond to the first two
propositions in the list.
There are _{4}C_{2} = 6 ways to put T in two
cells and F in two; those correspond to propositions 3–8.
There are _{4}C_{1} = 4 ways to put T in three
of the cells and F in one; those are propositions 9–12.
And there are _{4}C_{1} = 4 ways to put T in one
of the cells and F in three: the last four propositions.

If we start with three propositions, p,
q and r
(instead of just p and q)
and combine them using logical operations,
the truth table for the resulting proposition has 2×2×2 = 8 cells,
one for each combination of T and F for each of the three propositions we start
with.
Each of those cells can contain either T or F, so there are
2^{8} = 256 possible truth tables involving three basic propositions.
In general, the truth table for a compound proposition involving *k* basic
propositions has 2^{k} cells, each of which can contain T or F, so there
are 2^{2k} possible truth tables for compound propositions
that combine *k* basic propositions.
Of those, there are _{22k}C_{t}
truth tables that have T in *t* of the cells and F in the rest.

The following exercise checks whether you can determine whether a logical proposition is true or false.

The following exercises test your ability to find truth tables for compound propositions built from the propositions p and q and the operations !, |, &, → and ↔.

The following exercises check whether you can reduce a compound proposition into a logically equivalent proposition that uses only the fundamental logical operations !, | and &.

Recall from
*conclusion* is true.
A logical argument is valid
if its premises logically imply
its conclusion; that is, the argument is valid if the conclusion must be true
on the assumption that the premises are true.

An argument can be logically valid even if its premises are false.
If a logical argument is *invalid*, the conclusion can be false even if
the premises are true.
Logical arguments can be viewed as compound
propositions.
If the argument is valid, the compound proposition that the
conjunction of the premises
implies the conclusion is always true.
That is, an argument with premises p_{1}, p_{1}, …
p_{n} and conclusion q is logically valid if the compound
proposition

(p_{1} & p_{2} & … & p_{n} )
→ q

is logically equivalent to T. Otherwise, the argument is invalid.

Here is an example of a valid logical argument:

- If the weather forecast calls for rain, I will not wear sandals.
- The forecast calls for rain.
- Therefore, I will not wear sandals.

The structure of this argument is as follows. Let p denote the proposition that the forecast calls for rain, and let q denote the proposition that I will wear sandals. The argument has two premises:

- p → !q
- p

The conclusion of the argument is !q. The argument asserts that if these two premises are true, then the conclusion is true. The argument is valid if the compound proposition

[(p → !q) & p ] → !q

is always true, whether or not p and/or q are true.

Here is the truth table for that compound proposition:

This compound proposition is always true, no matter the values of p and q; therefore, this is a valid logical argument.

Here is an example of an invalid logical argument:

- If the weather forecast calls for rain, I will not wear sandals.
- The forecast does not call for rain.
- Therefore, I will wear sandals.

The structure of this argument is as follows. Let p denote the proposition that the forecast calls for rain, and let q denote the proposition that I will wear sandals. The argument has two premises:

- p → !q
- !p

The conclusion of the argument is q. The argument asserts that if these two premises are true, then the conclusion is true. The argument is valid if the compound proposition

[(p → !q) & (!p) ] → q

is always true, whether or not p and/or q are true.

That compound proposition is logically equivalent to p | q; the truth table for that is:

The compound proposition is not always true—it is false if p and q are both false (i.e., if the forecast does not call for rain, and I do not wear sandals). Therefore, this is an invalid argument.

For a review of what it means for an argument to be sound, see
Recall from

- The Moon is made of cheese.
- The Moon is more than a billion years old.
- Anything more than a billion years old made from cheese is stale.
- Therefore, the Moon is stale.

This argument is logically valid, though factually incorrect—because at least one
of its premises is false.
That is, the argument is logically valid, but not
sound.
An argument is *sound* if its premises are in fact true, and the argument is
logically valid.
The logical structure of the previous argument can be untangled in the following way.
Here are the propositions in the argument:

- p
_{1}. The Moon is made of cheese. - p
_{2}. The Moon is more than a billion years old. - p
_{3}. Anything made from cheese and more than a billion years old is stale. - p
_{4}. Hidden premise: if the Moon is made from cheese and more than a billion years old, then the Moon is stale. This premise is implied*mathematically*by p_{3}, but it is not derived by logical operations (!, |, &) from p_{1}, p_{2}, and p_{3}. That is, if p_{3}is true, so is p_{4}, as a matter of mathematics. - q. The Moon is stale.

The argument is thus

(p_{1} & p_{2} &
p_{4} )
→ q.

But we can write

p_{4} = (
(p_{1} & p_{2} ) → q ).

Clearly,

(p_{1} & p_{2} &
(
(p_{1} & p_{2} ) →
q ))
→ q

is always true, so the argument is logically valid.

A classical *syllogism*, a three-line argument, is as follows:

- Socrates is a man.
- All men are mortal.
- Therefore, Socrates is mortal.

This argument also has a "hidden premise," namely, that if Socrates is a man then Socrates is mortal. This premise is implied mathematically by the second premise in the argument, but is it not derivable from the second premise using only the logical operations !, | and &.

The following exercise tests your ability to identify the structure of a logical argument from a verbal description, and to determine whether that argument is valid.

The following exercises test your ability to determine whether an argument is logically valid.

There is an intimate connection between logical operations and set operations:
Every logical operation can be represented as an operation on sets by thinking
of propositions as subsets of the outcome space **S**.
The subset corresponding to p is the collection of outcomes for
which p is true.

Suppose we have two propositions, p and q.
Let P be the subset of **S** corresponding to
p, and let
Q be the subset of **S** corresponding to q.
The subset corresponding to !p is the complement of the subset
corresponding to p, P^{c}.
The subset corresponding to the proposition (p | q)
is the union of the set
corresponding to p and the set corresponding to q,
(P ∪ Q).
The subset of **S** corresponding to the proposition
(p & q) is the intersection
of the set corresponding to p and the set corresponding to
q, PQ.
The set corresponding to the proposition
(p → q) is (P^{c} ∪ Q).
If P is a subset of Q, then

(P^{c} ∪ Q) =
(Q^{c} ∪ Q) = **S**,

because then P^{c} contains Q^{c}.
Thus if P is a subset of Q,
(p → q) is always true.
The set corresponding to the proposition (p ↔ q) is
(PQ ∪ (P^{c}Q^{c})).
If P = Q, then

(PQ ∪ P^{c}Q^{c}) =
(P ∪ P^{c}) = **S**,

so in that case, (p ↔ q) is always true.

A proposition p is a statement that can be true (T) or false (F). Logical operations turn propositions into other propositions; examples include !, |, &, →, ↔. They operate as shown in the following table:

operation name | values |
---|---|

!, −, ˜, ¬, not | !T = F; !F = T |

|, ∨, or | (T | T) = T; (T | F) = T; (F | T) = T; (F | F) = F |

&, ∧, and | (T & T) = T; (T & F) = F; (F & T) = F; (F & F) = F |

→, implies, if-then | (T → T) = T; (T → F) = F; (F → T) = T; (F → F) = T |

↔, IFF | (T ↔ T) = T; (T ↔ F) = F; (F ↔ T) = F; (F ↔ F) = T |

The logical operations satisfy associative, commutative, and distributive laws. | is like addition and & is like multiplication. All the logical operations can be reduced to !, | and &.

A logical argument consists of one or more premises and a conclusion. The argument is logically valid if the truth of the premises guarantees that the conclusion is true; that is, if the conjunction of the premises implies the conclusion. An argument can be logically valid even if its premises are false. If an argument is logically valid and its premises are true, the argument is sound.

Logical propositions can be thought of as events: The proposition is true if and only if the event occurs. Then logical ! becomes the set complement, logical & becomes the set intersection, logical | becomes the set union, and the rest of the associations follow from these three.

- &, ∧, logical conjunction, and
- compound proposition
- conclusion
- contrapositive
- converse
- ↔, IFF, if and only if
- → implies, if-then
- logically equivalent, =
- logically valid
- logical argument
- logical operation
- !, ˜, −, ¬, not
- |, ∨, |, logical disjunction, or
- premise
- proposition, logical proposition
- sound argument
- structure of a logical argument
- syllogism
- truth table