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:
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 |:
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:
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:
Those relations are like the arithmetic identities a×b = b×a and a+b = b+a. Moreover, & and | satisfy distributive relationships:
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 = 24 = 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:
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 4C2 = 6 ways to put T in two cells and F in two; those correspond to propositions 3–8. There are 4C1 = 4 ways to put T in three of the cells and F in one; those are propositions 9–12. And there are 4C1 = 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 28 = 256 possible truth tables involving three basic propositions. In general, the truth table for a compound proposition involving k basic propositions has 2k cells, each of which can contain T or F, so there are 22k possible truth tables for compound propositions that combine k basic propositions. Of those, there are 22kCt 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 that an argument is a sequence of statements. One statement is the conclusion. The other statements are premises given as evidence that the 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 p1, p1, … pn and conclusion q is logically valid if the compound proposition
(p1 & p2 & … & pn ) → q
is logically equivalent to T. Otherwise, the argument is invalid.
Here is an example of a valid logical argument:
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:
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:
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
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 An argument can be logically valid even if one or more of its premises are false. For example, consider the argument:
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:
The argument is thus
(p1 & p2 & p4 ) → q.
But we can write
p4 = ( (p1 & p2 ) → q ).
Clearly,
(p1 & p2 & ( (p1 & p2 ) → q )) → q
is always true, so the argument is logically valid.
A classical syllogism, a three-line argument, is as follows:
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, Pc. 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 (Pc ∪ Q). If P is a subset of Q, then
(Pc ∪ Q) = (Qc ∪ Q) = S,
because then Pc contains Qc. Thus if P is a subset of Q, (p → q) is always true. The set corresponding to the proposition (p ↔ q) is (PQ ∪ (PcQc)). If P = Q, then
(PQ ∪ PcQc) = (P ∪ Pc) = 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:
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.