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.

Table1.3.1.Truth table for \(\neg p\text{.}\)

\(p\)

\(\neg p\)

T

F

F

T

It should make sense that if we negate T we get F, and vice versa.

Table1.3.2.Truth table for \(p\wedge q\text{.}\)

\(p\)

\(q\)

\(p\wedge q\)

T

T

T

T

F

F

F

T

F

F

F

F

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.

Table1.3.3.Truth table for \(p\vee q\text{.}\)

\(p\)

\(q\)

\(p\vee q\)

T

T

T

T

F

T

F

T

T

F

F

F

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

Make sure you use parentheses when combining statements. For example, \(\neg p\vee q\) is not the same as \(\neg (p\vee q)\text{.}\)

Table1.3.4.Truth table for \(\neg p\vee q\) and \(\neg (p\vee q)\text{.}\)

\(p\)

\(q\)

\(\neg p\)

\(\neg p \vee q\)

\(p \vee q\)

\(\neg (p \vee q)\)

T

T

F

T

T

F

T

F

F

F

T

F

F

T

T

T

T

F

F

F

T

T

F

T

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.

Table1.3.6.Truth table for \(p\rightarrow q\text{.}\)

\(p\)

\(q\)

\(p\rightarrow q\)

T

T

T

T

F

F

F

T

T

F

F

T

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.

Table1.3.8.Truth table for \(p\leftrightarrow q\text{.}\)

\(p\)

\(q\)

\(p\leftrightarrow q\)

T

T

T

T

F

F

F

T

F

F

F

T

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{.}\)

Table1.3.9.Truth table for \(p // q\text{.}\)

\(p\)

\(q\)

\(p//q\)

T

T

F

T

F

T

F

T

T

F

F

T

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{.}\)

Table1.3.13.Truth table for \(p\wedge \mathbf{t}\text{.}\)

\(p\)

\(\mathbf{t}\)

\(p\wedge \mathbf{t}\)

T

T

T

F

T

F

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.

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

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.