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