In this section, we’ll seek to answer the questions:
How can we combine statements into more complex statements?
What is a truth table?
How can we determine if two statements are logically equivalent?
In this section, we will explore ways of combining statements to form new, more complex statements. A hallmark of our approach is that we will define the truth values of the statements completely formally (though generally the way you might expect). That is to say, the truth values of the combined statements will depend only on the truth values of the atomic statements of which they are composed. Deeper exploration will require a clear notion of logical equivalence, established via truth tables.
Subsection1.2.1Logical Connectives
We begin with negation.
Definition1.2.1.
Suppose \(P\) is a statement. The negation of \(P\text{,}\) denoted \(\neg P\) and read “not \(P\)”, has the opposite truth value of \(P\) and is defined by the truth table found in Table 1.2.2.
Table1.2.2.The negation of \(P\text{,}\)\(\neg P\text{.}\)
\(P\)
\(\neg P\)
T
F
F
T
LaTeX Code1.2.3.
To typeset \(\neg P\) in \(\LaTeX\text{,}\) use \neg P in math mode.
We observe that Table 1.2.2 is our first encounter with a truth table. A truth table lists all possible truth values for a (compound) statement given all possible combinations of truth values of its atomic statements. Since there are only two possible truth values for the atomic statement \(P\text{,}\) there are only two rows in Table 1.2.2.
Activity1.2.4.
Meaningfully negate the following propositions (without just saying "It is not the case that...").
\(\pi\) is a negative real number.
Iowa is the tenth largest U.S. state by population.
17 is a prime number.
The next connective we introduce is the logical and, also known as conjunction. Then, we’ll see the logical inclusive or, also known as disjunction.
Definition1.2.5.
The conjunction of \(P\) and \(Q\text{,}\) denoted \(P \land Q\) and read “\(P\) and \(Q\)”, is true when both \(P\) and \(Q\) are true, and false otherwise. See Table 1.2.6.
Table1.2.6.The conjunction of \(P\) and \(Q\text{.}\)
\(P\)
\(Q\)
\(P \land Q\)
T
T
T
T
F
F
F
T
F
F
F
F
LaTeX Code1.2.7.
To typeset \(P \land Q\) in \(\LaTeX\text{,}\) use P \land Q in math mode.
Definition1.2.8.
The disjunction of \(P\) and \(Q\text{,}\) denoted \(P \lor Q\) and read “\(P\) or \(Q\)”, is true when \(P\) is true, \(Q\) is true, or both are true, and false otherwise. See Table 1.2.9.
Table1.2.9.The disjunction of \(P\) and \(Q\text{.}\)
\(P\)
\(Q\)
\(P \lor Q\)
T
T
T
T
F
T
F
T
T
F
F
F
LaTeX Code1.2.10.
To typeset \(P \lor Q\) in \(\LaTeX\text{,}\) use P \lor Q in math mode.
Problem1.2.11.
Determine the truth values of the following propositions.
Math 212 meets on Mondays and the capital of Iowa is Des Moines.
Math 212 meets on Mondays and the capital of Minnesota is Minneapolis.
Math 212 meets on Mondays or the capital of Minnesota is Minneapolis.
Math 212 meets on Mondays or the capital of Minnesota is St. Paul.
Observe that the “or” connective defined in Definition 1.2.8 is distinct from the so-called “exclusive or” that is often used in, e.g., computer science. The statement \(P \lor Q\) is true so long as at least one of \(P,Q\) is true —or both!
There are two more connectives to consider. As a warmup, consider the following problem.
Problem1.2.12.
A mathematician 1
This exploration due to Dr. L. Keough.
places a set of four cards on a table, each of which has a number on one side and a colored patch on the other side. She claims the following: The visible faces of the cards show 3, 8, red, and blue. Which card(s) must you turn over in order to test the truth of her claim? Carefully explain.
Definition1.2.13.
Let \(P\) and \(Q\) be statements. The implication, “\(P\) implies \(Q\)” 2
We sometimes say that \(P\) is “sufficient for” \(Q\text{.}\)
(or “if \(P\text{,}\) then \(Q\)”) is denoted \(P\Rightarrow Q\text{,}\) and is false only when \(P\) is true but \(Q\) is false. See Table 1.2.14.
To typeset \(P \Rightarrow Q\) in \(\LaTeX\text{,}\) use P \Rightarrow Q in math mode.
Problem1.2.16.
Determine the truth values of the following statements. Identify which row of Table 1.2.14 you are in.
If \(-7\) is a negative integer, then \(-5\cdot -7\) is a positive integer.
If a number \(12\) is divisible by 4 and by 6, then \(m\) is divisible by 12.
If \(9 > 5\text{,}\) then dogs do not have wings.
If \(2=4\text{,}\) then there are 57 states in the United States of America.
The formalization of mathematical logic ramps up a bit when we consider conditional statements. It is important to remember that we define the truth value of the proposition \(P \Rightarrow Q\)formally based on the structure of the conditional statement and the truth values of the constituents \(P\) and \(Q\text{.}\) That is to say that there need not be a causal relationship between \(P\) and \(Q\text{!}\)
The last two rows of Table 1.2.14 are also worth a moment of our time. They state that if the statement \(P\) 3
Often called the antecedent.
is false, then the implication\(P\Rightarrow Q\) is true. Note that this is different than saying that \(Q\) 4
Often called the consequent.
is true. When the implication \(P\Rightarrow Q\) is true because \(P\) is false, we usually say that \(P\Rightarrow Q\) is vacuously true.
Problem1.2.17.
Suppose Dr. Janssen promises that, if everyone get an A in the class, then he will bring Defender sandwiches (on pretzel buns, with everything, as God intended) to celebrate on the last day of class 5
This is purely hypothetical.
. Unfortunately, a few students finish the course with an A –, so Dr. Janssen does not bring Defenders.
Decide the truth value of the implication Make sure you can clearly explain your thinking and be able to give reasons for why the truth value you chose makes sense.
Our final logical connective is the biconditional connective.
Definition1.2.18.
Let \(P\) and \(Q\) be statements. The biconditional statement joining \(P\) and \(Q\text{,}\) read “\(P\) if and only if \(Q\)” 6
We sometimes say that \(P\) is “necessary and sufficient” for \(Q\text{.}\)
and written \(P\Leftrightarrow Q\text{,}\) is true precisely when \(P\) and \(Q\) have the same truth values, and false otherwise.
LaTeX Code1.2.19.
To typeset \(P \Leftrightarrow Q\) in \(\LaTeX\text{,}\) use P \Leftrightarrow Q in math mode.
Problem1.2.20.
First, construct a truth table for \(P\Leftrightarrow Q\) based on Definition 1.2.18. Then, determine the truth values of the following statements. Identify which row(s) of your truth table you are using.
A number is a perfect square if and only if it can be expressed as the product of an integer with itself.
A function is differentiable if and only if its graph can be drawn without lifting the pencil from the paper.
\(9 > 5\) if and only if dogs do not have wings.
\(2=4\) if and only if \(\sin(\pi) = 1\text{.}\)
Subsection1.2.2Logical Equivalence
A fundamental skill in analyzing and proving mathematical statements is the ability to carefully describe their logical structure and, when appropriate, convert the statement into a logically equivalent statement. Ideally, the new equivalent form of the statement will have a structure more amenable to a particular type of proof or solution.
Definition1.2.21.
Two statements \(P\) and \(Q\) are said to be logically equivalent if they have the same truth table. In this case, we write \(P \equiv Q\text{.}\)
Problem1.2.22.Double Negation.
Use a truth table to verify that \(P\equiv \neg (\neg P)\text{.}\)
Problem1.2.23.
Use a truth table to determine whether the following statements are logically equivalent.
Given an implication \(P\Rightarrow Q\text{,}\) one may construct some related statements.
Definition1.2.24.
Let \(P\) and \(Q\) be statements.
The converse of the statement \(P\Rightarrow Q\) is the statement \(Q\Rightarrow P\text{.}\)
The contrapositive of the statement \(P\Rightarrow Q\) is the statement \((\neg Q)\Rightarrow (\neg P)\text{.}\)
The inverse of the statement \(P\Rightarrow Q\) is the statement \((\neg P)\Rightarrow (\neg Q)\text{.}\)
Activity1.2.25.
Choose at least two conditional statements we’ve mentioned in class and state the coverse, contrapositive, and inverse of each. Based on the statements you wrote, make a conjecture 7
A conjecture is a precise educated “guess” about what is true in general.
about how the truth values of these four implications (the original conditional statement, together with its converse, contrapositive, and inverse) seem to relate.
Problem1.2.26.
Use truth tables to identify any logical equivalences between \(P\Rightarrow Q\text{,}\)\(Q\Rightarrow P\text{,}\)\((\neg Q)\Rightarrow (\neg P)\text{,}\) and \((\neg P)\Rightarrow (\neg Q)\text{.}\)
Problem1.2.27.
Show that \(P\Rightarrow Q \equiv (\neg P) \lor Q\text{.}\)
The following pairs of logical equivalences, named for British mathematician Augustus De Morgan 8
en.wikipedia.org/wiki/Augustus_De_Morgan
, allow us to convert conjunctions to disjunctions, and vice versa.
Problem1.2.28.De Morgan’s Laws for two statements.
Show that the following pairs of statements are logically equivalent.
\(\neg (P\land Q)\) and \((\neg P) \lor (\neg Q)\)
\(\neg (P\lor Q)\) and \((\neg P)\land (\neg Q)\)
Problem1.2.29.Distributive Laws.
Let \(P, Q, R\) be statements. Use truth tables to verify the following equivalences, but be careful —how many rows should your truth table contain?
We will often interested in proving conditional statements in which our antecdents or consequents have multiple cases. The following equivalences will come in handy.
