Introduction to Proofs: An Active Exploration of Mathematical Language

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.

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.

\(p\)	\(\neg p\)
T	F
F	T

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

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

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

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.

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.

To better understand the truth or falsity of a conditional, let's look at another example.

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.

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.

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.

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

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.

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

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.

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

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.

We summarize the previous activities in the following definition.

The following is a list of important logical equivalences. All of them can be checked using truth tables.