While walking through a fictional forest, you encounter three trolls guarding a bridge. Each is either a knight, who always tells the truth, or a knave, who always lies. The trolls will not let you pass until you correctly identify each as either a knight or a knave. Each troll makes a single statement:
Spend a few minutes thinking about the Investigate problem above. What could you conclude if you knew Troll 1 really was a knave (i.e., their statement was false)? Share your initial thoughts on this.
In order to do mathematics, we must be able to talk and write about mathematics. Perhaps your experience with mathematics so far has mostly involved finding numerical answers to problems. As we embark towards more advanced and abstract mathematics, writing will play a more prominent role in the mathematical process.
In fact, the primary goal of mathematics, as an academic discipline in its own right, is to establish general mathematical truths. How can we know whether these facts, perhaps called theorems or propositions, are true? We construct valid arguments, called proofs, which establish the truth of the statements. Here, an argument is not the sort of thing you have with your Mom when you disagree about what to have for dinner. Rather, we have a technical definition of the term.
An argument is said to be valid provided the conclusion must be true whenever the premises are all true. An argument is invalid if it is not valid; that is, all the premises can be true, and the conclusion could still be false.
To determine whether we have a proof of a statement, we must decide both whether every premise is true, and whether the argument is valid: whether the conclusion follows from the premises. How can we do this?
Do you agree that the first argument is valid but the second argument is not? We will soon develop a better understanding of the logic involved in this analysis, but if your intuition agrees with this assessment, then you are in good shape.
Notice the two arguments look almost identical. Edith and Florence both eat their vegetables. In both cases, there is a connection between the eating of vegetables and cookies. Yet we claim that it is valid to conclude that Edith gets a cookie, but not that Florence does. The difference must be in the connection between eating vegetables and getting cookies. We need to be skilled at reading and comprehending these sentences. Do the two sentences mean the same thing?
Unfortunately, in everyday language we are often sloppy, and you might be tempted to say they are equivalent. But notice that just because Florence must eat her vegetables, we have not claimed that doing so would be enough (she might also need to clean her room, for example). In everyday (non-mathematical) practice, you might be tempted to say this βother directionβ is implied. In mathematics, we never get that luxury.
The arguments in the example above illustrate another important point: Even if you donβt care about the advancement of human knowledge in the field of mathematics, becoming skilled at analyzing arguments is useful. And even if you donβt want to give your grandmother a cookie. If you are using mathematics to solve problems in some other discipline, it is still necessary to demonstrate that your solution is correct. You better have a good argument that it is!
If the sentences in an argument could not be true or false, there would be no way to determine whether the argument was valid, since validity describes a relationship between the truth values of the premises and conclusions.
The goal of this section is to explore the different βshapesβ a statement can take. We will see that more complicated statements can be built up from simpler ones, in ways that entirely determine their truth value based on the truth values of their parts.
Before reading on to the main content of the section, complete this preview activity to start thinking about the types of questions this section will address.
Which of the following sentences should count as statements? That is, for which of the sentences below could you potentially claim the sentence was either true or false? Select all that apply.
You and your roommate are arguing, and they make the audacious claim that pineapple is good both on pizza and in smoothies. Which of the following are reasonable responses to this claim, from a logical point of view?
The claim that pineapple is good both on pizza and in smoothies is not claiming that it is only good at the same time. It is precisely claiming these two separate facts are both true.
The statement is half true because regardless of what you think about pineapple on pizza, we can all agree at least that pineapple is good in smoothies.
Your roommate now makes an even more outrageous claim: If a superhero movie is part of the Marvel Cinematic Universe, then it is good. Which of the following are reasonable responses to this claim, from a logical point of view?
This is false because there are good superhero movies, like Wonder Woman and Dark Knight, that are based on DC Comics, and so not part of the Marvel Cinematic Universe.
Actually, Iβve never seen that movie, but even if it were bad, that doesnβt say anything about the original statement, since it is not a Marvel movie.
The statement is true because more than half of the Marvel movies are good.
Your roommate just wonβt let up with their outrageous claims. Now they claim that either every troll is a knave, or there is at least one troll that is a knight. What can you say to this?
Yes, this is true because every troll is either a knight or a knave. If it is not the case that all trolls are knaves, then there must be some troll that is a knight.
Itβs true that if a troll said that all trolls are knaves they would have to be a knave and then it would be false that all trolls were knaves. But luckily there is another option.
A statement is any declarative sentence which is either true or false. A statement is atomic if it cannot be divided into smaller statements, otherwise it is called molecular.
The reason the sentence ββ is not a statement is that it contains a variable. Depending on what is, the sentence is either true or false, but right now it is neither. One way to make the sentence into a statement is to specify the value of the variable in some way. This could be done by setting a specific substitution, for example, β where ,β which is a true statement. Or you could capture the free variable by quantifying over it, as in, βFor all values of ,,β which is false. We will discuss quantifiers in more detail in the subsection Quantifiers and Predicates below.
You can build more complicated (molecular) statements out of simpler (atomic or molecular) ones using logical connectives. For example, this is a molecular statement:
Note that we can break this down into two smaller statements. The two shorter statements are connected by an βand.β We will consider 5 connectives: βandβ (Sam is a man, and Chris is a woman), βorβ (Sam is a man, or Chris is a woman), βifβ¦, thenβ¦β (if Sam is a man, then Chris is a woman), βif and only ifβ (Sam is a man if and only if Chris is a woman), and βnotβ (Sam is not a man). The first four are called binary connectives (because they connect two statements) while βnotβ is an example of a unary connective (since it applies to a single statement).
These molecular statements are, of course, still statements, so they must be either true or false. The crucial observation here is that which truth value the molecular statement achieves is completely determined by the type of connective and the truth values of the parts. We do not need to know what the parts actually say or whether they have some material connection to each other, only whether those parts are true or false.
To analyze logical connectives, it is enough to consider propositional variables (sometimes called sentential variables), usually capital letters in the middle of the alphabet: . We think of these as standing in for (usually atomic) statements, but there are only two values the variables can achieve: true or false.β1β
In computer programming, we should call such variables Boolean variables.
We also have symbols for the logical connectives: ,,,,.
Each of the above definitions can be represented in a table, called a truth table. We simply list what the truth value of the statement is for each possible combination of truth values of the parts.
For example, we can use the truth table for to decide whether the statement, βIf 5 is even, then 6 is even,β is true or false. Here is the statement β5 is even,β and is the statement β6 is even.β Since 5 is not even, the statement is false. Since 6 is even, the statement is true. The truth table tells us that the statement is true when is false and is true (the 3rd row). So the statement, βIf 5 is even, then 6 is even,β is true. (If you donβt like that the statement is true, hold on to that thought, and we will hopefully resolve it soon.)
Note that for us, or is the inclusive or (and not the sometimes used exclusive or) meaning that is in fact true when both and are true. As for the other connectives, βandβ behaves as you would expect, as does negation. The biconditional (if and only if) might seem a little strange, but you should think of this as saying the two parts of the statements are equivalent in that they have the same truth value.
This leaves only the implication which has a slightly different meaning in mathematics than in ordinary usage. However, implications are so common and useful in mathematics that we must develop a level of fluency with their use which warrants a whole section (Section 1.2).
True. The first part is true, so the entire statement is true. As soon as we see one true statement in a disjunction, we can stop checking and declare the entire statement true.
True. Donβt be worried that there isnβt a good reason that 17 being prime causes 19 to be prime. That is not what we mean by a conditional statement. Since the βthenβ part is true, we know that the statement overall is true.
True. The βifβ part of the statement is false. Thatβs all we need. I bet you donβt even know what my favorite number is, and you donβt need to. The statement is true.
The way we define logical connectives and their truth value is very precise and technical. Often, language is not. Part of learning how to communicate mathematics is learning the cultural norms of mathematical language and how to translate statements in ordinary language into these technical statements. This will get easier with practice, so make sure you are talking to lots of people about the math you are studying.
Do you agree this is the same statement as β4 is prime, and 5 is primeβ? Notice that it would not make sense to write this as where is β4β and is β5 is primeβ. But if we let be the statement, β4 is prime,β then both parts of the conjunction are statements.
Again, we canβt just put what is on one side of the βorβ as a statement. But if we let be β4 is primeβ and be β5 is prime,β, then we can write this as . That is, either 4 is prime or 5 is prime, and it is not the case that both 4 is prime and 5 is prime.
Here is another way you could phrase the same statement: If you pass the class, then it must be the case that you attended every day and that you did the homework. If we agree that this is just a clearer way to state the original statement, then we could illustrate its structure as .
Notice that this is not the same as saying, βEvery number is even, or every number is odd.β Of course, saying, β3 is even or odd,β is the same as saying, β3 is even, or 3 is odd.β Language is confusing!
We donβt yet have the logical technology to translate this statement as anything more than , where is the statement, βEvery number is even or odd.β Luckily, that technology is available, starting... now!
This will require considering a new sort of basic sentence called a predicate, which is like a statement, but contains a free variable. When you replace that variable with a constant of some sort, then the sentence becomes a statement proper. Think of a predicate as making a claim about the values that are substituted for the βplaceholderβ variable(s).
A predicate can be made into a (true or false) statement by evaluating it at some constant(s), or we can claim that some or all possible constants would make the resulting statement true or false. This is done using quantifiers.
The universal quantifier is written and is read, βfor all.β The existential quantifier is written and is read, βthere existsβ or βfor some.β
We usually write predicates similar to how you write a function, although with capital letters. For example, we might use the predicate to represent β is primeβ. We can then say that is true (since 7 is prime) and that is false. Or using quantifiers, we can (falsely) claim that all numbers are prime by writing or (truthfully) claim that there is at least one prime number, by writing .
Before we even start using symbols, it is helpful to rephrase this in a way that captures the logical structure of the statement. What is the claim saying? Given any number, it will either be the case that the number is even, or that the number is odd. In particular, we are not claiming that either all numbers are even or all numbers are odd.
Note that if we incorrectly interpreted the statement as claiming that either all numbers are even or all numbers are odd, we could write that as . This is not the same!
Just like we did for propositional logic and the logical connectives, we should decide what it means for a quantified predicate to be true or false. We say is true if is true no matter what constant we substitute for . And similarly, is true if there is at least one value for which is true.
However, we must be careful here. Consider the statement
.
You would read this, βFor every there is some such that is less than .β Note that is a predicate with two free variables; we have chosen to write it with the symbol between the variables instead of the funky-looking or .
Is this statement true? The answer depends on our domain of discourse. When we say βfor allβ , do we mean all positive integers or all real numbers or all elephants or...? Usually, this information is implied by the context of the statement. In discrete mathematics, we almost always quantify over the natural numbers, , so letβs take that for our domain of discourse here.
For the statement to be true, we need, no matter what natural number we select, for there to be some natural number that is strictly smaller. Perhaps we could let be ? But here is the problem: what if ? Then , and that is not a number! (in our domain of discourse). Thus we see that the statement is false because there is a number less than or equal to all other numbers. In symbols,
We will explore some rules for working with quantifiers and other connectives in Section 1.3. For now, we will focus on translating between informal statements in ordinary language and the more precise language of logic. There is no perfect algorithm for doing this translation, but here are a few useful rules of thumb.
To make sense of this, think about what we mean by statements like these in terms of sets. We claim that the set of mammals is contained in, or is a subset of, the set of hairy things. What we mean by β is a subset of β is precisely that every element of is an element of . This can also be expressed by saying that βif is an element of , then is also an element of .β
Again, it is helpful to think of how to express such statements in terms of sets. To say that some cats can swim is to say that there are things that belong both to the set of cats and to the set of swimming things. Such animals belong to the intersection of these two sets, which you can describe as belonging to the first set and the second set. Existential statements of this form claim that the intersection of the two sets is not empty.
It is always a good idea to be precise in mathematics. Sometimes though, we can relax a bit, as long as we all agree on a convention. An example of such a convention is to assume that sentences containing predicates with free variables are intended as statements, where the variables are universally quantified.
For example, do you believe that if a shape is a square, then it is a rectangle? But how can that be true if it is not a statement? To be a little more precise, we have two predicates: for β is a squareβ and for β is a rectangleβ. The sentence we are looking at is
.
This is neither true nor false, as it is not a statement. But come on! We all know that we meant to consider the statement,
,
and this is what our convention tells us to consider. We call the resulting statement the universal generalization of the original sentence.
Given a sentence with free variables, the universal generalization of that sentence is the statement obtained by adding enough universal quantifiers to the beginning of the sentence so that all free variables become bound.
Similarly, we will often be a bit sloppy about the distinction between a predicate and a statement. For example, we might write, let be the statement, β is prime,β which is technically incorrect. It is implicit that we mean that we are defining to be a predicate, which for each becomes the statement, is prime.
Classify each of the sentences below as an atomic statement, a molecular statement, or not a statement at all. If the statement is molecular, say what kind it is (conjuction, disjunction, conditional, biconditional, negation).
Determine whether each molecular statement below is true or false, or whether it is impossible to determine. Assume you do not know what my favorite number is (but you do know which numbers are prime).
Your friend believes that you cannot fool everyone at the same time. What is another way of saying this, and how would you write that in symbols (using to say you can fool at time ).
Regardless of your beliefs of how many people can be fooled at various times, what could you conclude if we reinterpret to mean and only quantify over the natural numbers (so means βFor all natural numbers,β and means βThere exists a natural numberβ)? Select all of the following that apply.
Suppose is some binary predicate defined on a very small domain of discourse: just the integers 1, 2, 3, and 4. For each of the 16 pairs of these numbers, is either true or false, according to the following table ( values are rows, values are columns).