Introduction to Proofs: An Active Exploration of Mathematical Language

Section1.3Logical Connectives

We want to understand what makes a mathematical proof. One of the foundations for proofs is logical structure. If we build a good foundation in logic, then we can better understand mathematical statements and proof structures. We have already seen the general form for an argument. Now we want to focus on types of statements used to make up an argument. In this section we will be looking at logical forms, independent of content.
If $$p$$ and $$q$$ are variables representing statements, we can combine these statements into new statements using logical connectives.

Logical Connectives: NOT, AND, OR.

• Negation.
NOT. Notation: $$\neg p\text{,}$$ read as “not $$p\text{.}$$
• Conjunction.
AND. Notation: $$p\wedge q\text{,}$$ read as “$$p$$ and $$q\text{.}$$
• Disjunction.
OR. Notation: $$p\vee q\text{,}$$ read as “$$p$$ or $$q\text{.}$$
Our goal is to determine when these new statements are true or false based on whether $$p$$ and $$q$$ are true or false. We can create a truth table that looks at all the possibilities of true or false for $$p$$ and $$q\text{.}$$ When writing a truth table, make a column for each variable, list all the possible cases of true and false, then for each case, determine whether the new statement (with the connective) is true or false.
It should make sense that if we negate T we get F, and vice versa.
Again, the truth values for an “and” statement should make sense. The only time it should be true is if both parts of the statement are true.
The truth values for an “or” statement should, mostly, make sense, as long as one part of the “or” statement is true, the whole statement is true. You may ask about the case where both parts are true. We think of this as an “inclusive or,” which means we allow both to be true. For example, “A computer science major must take Math 175 or Math 250.” You will still get a major if you take both.
There is a connective for an “exclusive or” (one or the other, not both).

Logical Connective: EXCLUSIVE OR.

• Exclusive Or.
OR, NOT BOTH. Notation: $$p\veebar q\text{,}$$ read as “$$p$$ exclusive or $$q\text{.}$$

Activity1.3.1.Exclusive Or.

Give the truth table for $$p \veebar q$$ based on a small change to the truth table for $$p \vee q\text{.}$$
Now that we can connect two statements, we can connect as many as we'd like using multiple quantifiers. For example, we could form the statement
\begin{equation*} p\vee(q\ \wedge \neg p). \end{equation*}
Make sure you use parentheses when combining statements. For example, $$\neg p\vee q$$ is not the same as $$\neg (p\vee q)\text{.}$$

Activity1.3.2.Truth Table Practice.

Give the truth table for $$\neg p\ \vee \neg q\text{.}$$

Activity1.3.3.More Truth Table Practice.

Give the truth table for $$(p \vee q) \wedge \neg(p \wedge q)\text{.}$$

Activity1.3.4.Truth Table with Three Variables.

Truth tables can have more than two variables. We just need to make sure we have a row for every possible combination of truth values for the variables. How many rows will you need in a truth table for 3 variables? Give the truth table for $$(p \wedge q) \vee r\text{.}$$
One of the things we want to be able to do is to translate English (or mathematical) sentences into logical statements. We have to be careful about how common phrases are really hidden “and”s. For example, “$$p$$ but $$q$$” is really $$p\wedge q\text{.}$$ Similarly, “neither $$p$$ nor $$q$$” is really $$\neg p\ \wedge \neg q\text{.}$$
A conditional statement has the form “if $$p$$ then $$q\text{.}$$” We use the connective $$p\rightarrow q$$ for conditional statements.

Logical Connective: IF...THEN.

• Conditional.
IF THEN. Notation: $$p\rightarrow q\text{,}$$ read as “if $$p$$ then $$q\text{.}$$
In a conditional statement $$p\rightarrow q\text{,}$$ we call $$p$$ the hypothesis, and $$q$$ the conclusion.
Before looking at the truth table, we need to understand when an if...then... statement is true or false. This is actually trickier than it seems.
Suppose I say to you “If it rains tomorrow, then class is cancelled.” When would you accuse me of lying to you? For example, if it doesn't rain and we have class, would you have thought my statement false? No. Now, you might not think my statement is true, either. But remember, statements must be either true or false. So if it is not false, then it is true.
Now, what if it doesn't rain, but I cancel class anyway? Would I have lied? No, I didn't tell you I wouldn't cancel class. So, again, this would be a true statement.
The only time you could accuse me of having made a false statement is if it rains and we don't cancel class. If we think of “it rains tomorrow” as $$p$$ and “class is cancelled” as $$q\text{,}$$ then the only time the statement is false is when $$p$$ is true and $$q$$ is false.
To better understand the truth or falsity of a conditional, let's look at another example.
Consider the mathematical statement “If $$x>2$$ then $$x^2>4$$”. Do you agree this is a true mathematical statement?
Let $$p$$ be “$$x>2$$” and $$q$$ be “$$x^2>4\text{.}$$” Consider all the cases of $$p$$ and $$q$$ being true or false.
For example, if $$x=5, x^2=25\text{,}$$ then we have the case where $$p$$ is true and $$q$$ is true.
If $$x=-5, x^2=25\text{,}$$ then we have the case where $$p$$ is false and $$q$$ is true. But remember, the original statement is still true!
If $$x=1, x^2=1\text{,}$$ then we have the case where $$p$$ is false and $$q$$ is false. But again, the original statement is still true.
It is impossible to find an $$x$$ that makes $$x>2$$ true and $$x^2>4$$ false. Thus, we never have the case where the conditional, if $$x>2$$ then $$x^2>4\text{,}$$ is false.

Activity1.3.5.Understanding Conditionals.

Give an example of a conditional statement, not one of the examples from above. Write in your own words why $$p\rightarrow q$$ must be true whenever $$p$$ is false.

Activity1.3.6.Practice with Conditionals.

Give the truth table for $$(p \rightarrow q) \wedge (q\rightarrow p)\text{.}$$
The statement $$(p \rightarrow q) \wedge (q\rightarrow p)$$ is useful in mathematics, but it is not very concise. We can simplify this statement by introducing another logical connective.

Logical Connective: IF AND ONLY IF.

• Biconditional.
IF AND ONLY IF. Notation: $$p\leftrightarrow q\text{,}$$ read as “$$p$$ if and only if $$q\text{.}$$
The biconditional is really just the combination of two conditionals: $$p\rightarrow q$$ and $$q\rightarrow p\text{.}$$ In particular, $$p\leftrightarrow q$$ and $$(p\rightarrow q)\wedge (q\rightarrow p)$$ have the same truth tables.

Activity1.3.7.Understanding Biconditionals.

Explain, in your own words, how to decide when $$p \leftrightarrow q$$ is true or false.

Activity1.3.8.Biconditional as Two Conditionals.

We read the biconditional $$p \leftrightarrow q$$ as “$$p$$ if and only if $$q\text{.}$$” Determine which of the two statements $$p \rightarrow q$$ and $$q\rightarrow p$$ means the same as “$$p$$ if $$q$$” and which means the same as “$$p$$ only if $$q\text{.}$$” Think about when each statement should be true (or false).
In mathematics we might see statements such as “$$p$$ is necessary for $$q$$” or “$$p$$ is sufficient for $$q$$”. These are really conditional statements. In particular, $$p$$ is sufficient for $$q$$ means $$p\rightarrow q\text{;}$$ and $$p$$ is necessary for $$q$$ means $$\neg p\rightarrow \neg q\text{,}$$ which, we will see shortly, is equivalent to $$q\rightarrow p\text{.}$$ So, a statement such as $$p$$ is necessary and sufficient for $$q$$ means $$p\leftrightarrow q\text{.}$$
We introduce one last connective, which is not as commonly used. It is nice to have an additional connective for practice, but this connective has a particularly nice property which we will explore in the exercises.

Logical Connective: NAND.

• Nand.
NOT BOTH. Notation: $$p//q\text{,}$$ read as “$$p$$ nand $$q\text{.}$$
Nand is really just the negation of “and”: $$\neg (p\wedge q)\text{.}$$ In particular, $$p // q$$ has the same truth table as $$\neg(p\wedge q)\text{.}$$

Definition1.3.10.

A tautology is a statement that is always true.
For example, $$p\ \vee \neg p$$ is a tautology. If you check the truth table, you will see that the only values in the column for the statement are T.

Definition1.3.11.

A contradiction is a statement that is always false.
For example, $$p\ \wedge \neg p$$ is a contradiction. If you check the truth table, you will see that the only values in the column for the statement are F.
Note that tautologies and contradictions are logical statements that are always true or always false, independent of the content of $$p\text{.}$$
If we want to make bigger statements using tautologies or contradictions, we can use $$\mathbf{t}$$ to represent a tautology and $$\mathbf{c}$$ to represent a contradiction. For example, we could find the truth table for $$p\wedge \mathbf{t}\text{.}$$

Definition1.3.14.

Two statements are logically equivalent if they have identical truth tables. If statements $$P$$ and $$Q$$ are logically equivalent, we denote it $$P\equiv Q\text{.}$$
For example, we can see that $$p$$ is logically equivalent to $$p\wedge \mathbf{t}$$ by comparing the first and last columns of Table 1.3.13.
From the definitions and truth tables of $$p\leftrightarrow q$$ and $$p // q\text{,}$$ we see that
\begin{equation*} p\leftrightarrow q\equiv(p\rightarrow q)\wedge (q\rightarrow p); \end{equation*}
\begin{equation*} p // q\equiv\neg(p\wedge q). \end{equation*}

Activity1.3.9.Logical Equivalence Practice.

Use a truth table to determine if $$\neg(p \vee q)$$ and $$\neg p\ \vee \neg q$$ are logically equivalent. What does this tell you about “distributing” negation?

Activity1.3.10.Negating Or.

Use a truth table to show $$\neg(p \vee q)$$ and $$\neg p\ \wedge \neg q$$ are logically equivalent.

Activity1.3.11.Negating And.

Use a truth table to show $$\neg(p \wedge q)$$ and $$\neg p\ \vee \neg q$$ are logically equivalent.
The equivalences in Activity 1.3.10 and Activity 1.3.11 are called DeMorgan's Laws. These are useful equivalences and are worth committing to memory. As we've seen in the above activities, we cannot simply distribute a negation sign. However, DeMorgan's Laws allow us to distribute the negation as long as we also change from “and” to “or” and vice versa. Given the importance of this concept in mathematics, it is useful at this point to convince yourself that the negation of and “and” statement is an “or” statement and vice versa using statements in English. For example, if the weather is not cold and rainy, then it is either not cold or not rainy.
One thing to be careful about with English statements is that they do not naturally contain parentheses. We often really have to think about the meaning of the statement and infer the intended parentheses. Even in the above cold and rainy sentence, we have to understand that we mean “not (cold and rainy)” rather than “(not cold) and rainy.”

Activity1.3.12.Negating Conditionals.

Use a truth truth table to show $$\neg(p \rightarrow q)$$ is logically equivalent to $$p\ \wedge\neg q\text{.}$$ This is the rule for negating an if...then. Like DeMorgan's Law, it is worth committing to memory.
The following equivalences will be useful when working with conditional statements in mathematics.
• $$\displaystyle p\rightarrow q\equiv \neg p\ \vee q$$
• $$\neg(p\rightarrow q)\equiv p\ \wedge \neg q$$
This second equivalence is the negation of the conditional. It is going to be really important that we understand that the negation of a conditional is not a conditional itself.

Activity1.3.13.Converse.

Give the truth table for $$q\rightarrow p\text{.}$$ Is it equivalent to $$p\rightarrow q\text{?}$$ The statement $$q\rightarrow p$$ is the converse of $$p\rightarrow q\text{.}$$

Activity1.3.14.Contrapositive.

Give the truth table for $$\neg q\rightarrow \neg p\text{.}$$ Is it equivalent to $$p\rightarrow q\text{?}$$ The statement $$\neg q\rightarrow \neg p$$ is the contrapositive of $$p\rightarrow q\text{.}$$

Activity1.3.15.Inverse.

What is the contrapositive of $$q\rightarrow p\text{?}$$ This is also called the inverse of $$p\rightarrow q\text{.}$$
We summarize the previous activities in the following definition.

Definition1.3.16.

A conditional statement $$p\rightarrow q$$ has
• contrapositive: $$\neg q\rightarrow \neg p\text{;}$$
• converse: $$q\rightarrow p\text{;}$$
• inverse: $$\neg p\rightarrow \neg q\text{.}$$
Consider the statement: If $$x>2$$ then $$x^2>4\text{.}$$ What is the contrapositive of this statement? What is the converse?
Contrapositive: If $$x^2\leq 4$$ then $$x\leq 2\text{;}$$ Converse: If $$x^2>4$$ then $$x>2\text{.}$$
The following is a list of important logical equivalences. All of them can be checked using truth tables.

Summary of Logical Equivalences.

Let $$p, q,$$ and $$r$$ be variables representing statements. Let $$\mathbf{t}$$ be a tautology and $$\mathbf{c}$$ be a contradiction.
1. Commutative Laws.
$$p \wedge q \equiv q \wedge p; \ \ \ p \vee q \equiv q \vee p$$
2. Associative Laws.
$$(p \wedge q)\wedge r \equiv p \wedge (q \wedge r);\ \ \ (p \vee q)\vee r \equiv p \vee (q \vee r)$$
3. Distributive Laws.
$$p \wedge (q \vee r) \equiv (p \wedge q)\vee (p \wedge r);\ \ \ p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)$$
4. Identity Laws.
$$p \wedge {\rm\textbf{t}} \equiv p;\ \ \ p \vee {\rm\textbf{c}} \equiv p$$
5. Negation Laws.
$$p\ \vee \neg p \equiv {\rm\textbf{t}};\ \ \ p\ \wedge \neg p \equiv \rm{\textbf{c}}$$
6. Double Negation Law.
$$\neg(\neg p)\equiv p$$
7. Idempotent Laws.
$$p \wedge p \equiv p;\ \ \ p \vee p \equiv p$$
8. Universal Bound Laws.
$$p \vee {\rm\textbf{t}} \equiv {\rm\textbf{t}};\ \ \ p \wedge \rm{\textbf{c}} \equiv {\rm\textbf{c}}$$
9. DeMorgan's Laws.
$$\neg(p \wedge q) \equiv \neg p \vee \neg q;\ \ \ \neg(p \vee q) \equiv \neg p\ \wedge \neg q$$
10. Absorption Laws.
$$p \vee (p \wedge q) \equiv p;\ \ \ p \wedge (p \vee q) \equiv p$$

ExercisesExercises

1.

Below is a list of pairs of statements. Determine, using a truth table, whether the two statements in each pair are logically equivalent.
1. $$p\vee q\text{;}$$ $$\neg (\neg p \ \wedge\ \neg q)$$
2. $$\neg (p\ \wedge\ q)\text{;}$$ $$\neg p\ \wedge\ \neg q$$
3. $$q\rightarrow (p\rightarrow \neg q)\text{;}$$ $$\neg(p\ \wedge\ q)$$
4. $$\neg(p\vee q)\text{;}$$ $$\neg p \vee \neg q$$
5. $$\neg (p\rightarrow q)\text{;}$$ $$\neg q\rightarrow \neg p$$
6. $$p\ \wedge\ (p\rightarrow q)\text{;}$$ $$p\ \wedge\ q$$
7. $$p\vee (q\ \wedge\ r)\text{;}$$ $$(p\vee q)\ \wedge\ (p\vee r)$$
8. $$(p\ \wedge\ q)\rightarrow r\text{;}$$ $$p\rightarrow (q\rightarrow r)$$

2.

Determine, using a truth table, whether each of the following statements is a tautology, a contradiction, or neither.
1. $$\displaystyle (p\rightarrow p)\rightarrow q$$
2. $$\displaystyle q\rightarrow (p\rightarrow q)$$
3. $$\displaystyle \neg ( p\vee (p\rightarrow q))$$
4. $$\displaystyle q\rightarrow (p \vee \neg p)$$
5. $$\displaystyle q\rightarrow (p\ \wedge\ \neg p)$$
6. $$\displaystyle \bigl(p\rightarrow (p\rightarrow q)\bigr)\rightarrow (p\rightarrow q)$$
7. $$\displaystyle \bigl( (p\ \veebar\ q)\rightarrow (r\ \veebar\ r)\bigr) \leftrightarrow (p\ \wedge\ q)$$
8. $$\displaystyle (p\vee q)\ \wedge\ (\neg p \vee r)\ \wedge\ (\neg r\vee\neg q)\ \wedge\ (p\leftrightarrow q)$$

3.

Produce truth tables for the following statements. Then abbreviate them by finding the shortest possible logically equivalent statement.
1. $$\displaystyle \neg (p \ \wedge\ q)\rightarrow (p\ \veebar \ q)$$
2. $$\displaystyle \bigl( \bigl( (\neg p\rightarrow q)\ \wedge\ (r\ \veebar \ p)\bigr) \vee \bigl( ( \neg p \rightarrow q)\ \wedge\ (r\ \veebar \ q)\bigr) \bigr) \ \wedge\ \bigl((p\leftrightarrow q)\rightarrow r\bigr)$$

4.

Using only the connectives “$$\wedge$$” and “$$\neg$$”, write statements logically equivalent to each of the following:
1. $$\displaystyle p \vee q$$
2. $$\displaystyle p\ \veebar\ q$$
3. $$\displaystyle p \rightarrow q$$
4. $$\displaystyle p \leftrightarrow q$$

5.

Using only the connective “//”, write statements logically equivalent to each of the following:
1. $$\displaystyle \neg p$$
2. $$\displaystyle p\ \wedge\ q$$
3. $$\displaystyle p \vee q$$
4. $$\displaystyle p\ \veebar\ q$$
5. $$\displaystyle p \rightarrow q$$
6. $$\displaystyle p \leftrightarrow q$$