Skip to main content

Section B.1 Mathematical Statements

Puzzle 331.

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:

Troll 1: If I am a knave, then there are exactly two knights here.

Troll 2: Troll 1 is lying.

Troll 3: Either we are all knaves or at least one of us is a knight.

Which troll is which?

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 answers to problems. As we embark towards more advanced and abstract mathematics, writing will play a more prominent role in the mathematical process.

Communication in mathematics requires more precision than many other subjects, and thus we should take a few pages here to consider the basic building blocks: mathematical statements.

Subsection B.1.1 Atomic and Molecular Statements

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.

Example B.1.1.

These are statements (in fact, atomic statements):

  • Telephone numbers in the USA have 10 digits.

  • The moon is made of cheese.

  • 42 is a perfect square.

  • Every even number greater than 2 can be expressed as the sum of two primes.

  • \(3+7 = 12\)

And these are not statements:

  • Would you like some cake?

  • The sum of two squares.

  • \(1+3+5+7+\cdots+2n+1\text{.}\)
  • Go to your room!

  • \(3+x = 12\)

The reason the sentence “\(3 + x = 12\)” is not a statement is that it contains a variable. Depending on what \(x\) 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 specifying a specific substitution, for example, “\(3+x = 12\) where \(x = 9\text{,}\)” which is a true statement. Or you could capture the free variable by quantifying over it, as in, “for all values of \(x\text{,}\) \(3+x = 12\text{,}\)” which is false. We will discuss quantifiers in more detail at the end of this section.

You can build more complicated (molecular) statements out of simpler (atomic or molecular) ones using logical connectives. For example, this is a molecular statement:

Telephone numbers in the USA have 10 digits and 42 is a perfect square.

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 absolutely key 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, only whether those parts are true or false. So to analyze logical connectives, it is enough to consider propositional variables (sometimes called sentential variables), usually capital letters in the middle of the alphabet: \(P, Q, R, S, \ldots\text{.}\) 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  We also have symbols for the logical connectives: \(\wedge\text{,}\) \(\vee\text{,}\) \(\imp\text{,}\) \(\iff\text{,}\) \(\neg\text{.}\)

In computer programing, we should call such variables Boolean variables.
Logical Connectives.
  • \(P \wedge Q\) is read “\(P\) and \(Q\text{,}\)” and called a conjunction.
  • \(P \vee Q\) is read “\(P\) or \(Q\text{,}\)” and called a disjunction.
  • \(P \imp Q\) is read “if \(P\) then \(Q\text{,}\)” and called an implication or conditional.
  • \(P \iff Q\) is read “\(P\) if and only if \(Q\text{,}\)” and called a biconditional.
  • \(\neg P\) is read “not \(P\text{,}\)” and called a negation.

The truth value of a statement is determined by the truth value(s) of its part(s), depending on the connectives:

Truth Conditions for Connectives.
  • \(P \wedge Q\) is true when both \(P\) and \(Q\) are true
  • \(P \vee Q\) is true when \(P\) or \(Q\) or both are true.
  • \(P \imp Q\) is true when \(P\) is false or \(Q\) is true or both.
  • \(P \iff Q\) is true when \(P\) and \(Q\) are both true, or both false.
  • \(\neg P\) is true when \(P\) is false.

Note that for us, or is the inclusive or (and not the sometimes used exclusive or) meaning that \(P \vee Q\) is in fact true when both \(P\) and \(Q\) 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 conditional \(P \imp Q\) which has a slightly different meaning in mathematics than it does in ordinary usage. However, implications are so common and useful in mathematics, that we must develop fluency with their use, and as such, they deserve their own subsection.

Subsection B.1.2 Implications

Implications.

An implication or conditional is a molecular statement of the form

\begin{equation*} P \imp Q \end{equation*}

where \(P\) and \(Q\) are statements. We say that

  • \(P\) is the hypothesis (or antecedent).
  • \(Q\) is the conclusion (or consequent).

An implication is true provided \(P\) is false or \(Q\) is true (or both), and false otherwise. In particular, the only way for \(P \imp Q\) to be false is for \(P\) to be true and \(Q\) to be false.

Easily the most common type of statement in mathematics is the implication. Even statements that do not at first look like they have this form conceal an implication at their heart. Consider the Pythagorean Theorem. Many a college freshman would quote this theorem as “\(a^2 + b^2 = c^2\text{.}\)” This is absolutely not correct. For one thing, that is not a statement since it has three variables in it. Perhaps they imply that this should be true for any values of the variables? So \(1^2 + 5^2 = 2^2\text{???}\) How can we fix this? Well, the equation is true as long as \(a\) and \(b\) are the legs or a right triangle and \(c\) is the hypotenuse. In other words:

If \(a\) and \(b\) are the legs of a right triangle with hypotenuse \(c\text{,}\) then \(a^2 + b^2 = c^2\text{.}\)

This is a reasonable way to think about implications: our claim is that the conclusion (“then” part) is true, but on the assumption that the hypothesis (“if” part) is true. We make no claim about the conclusion in situations when the hypothesis is false. 2 

However, note that in the case of the Pythagorean Theorem, it is also the case that if \(a^2 + b^2 = c^2\text{,}\) then \(a\) and \(b\) are the legs of a right triangle with hypotenuse \(c\text{.}\) So we could have also expressed this theorem as a biconditional: “\(a\) and \(b\) are the legs of a right triangle with hypotenuse \(c\) if and only if \(a^2 + b^2 = c^2\text{.}\)”

Still, it is important to remember that an implication is a statement, and therefore is either true or false. The truth value of the implication is determined by the truth values of its two parts. To agree with the usage above, we say that an implication is true either when the hypothesis is false, or when the conclusion is true. This leaves only one way for an implication to be false: when the hypothesis is true and the conclusion is false.

Example B.1.2.

Consider the statement:

If Bob gets a 90 on the final, then Bob will pass the class.

This is definitely an implication: \(P\) is the statement “Bob gets a 90 on the final,” and \(Q\) is the statement “Bob will pass the class.”

Suppose I made that statement to Bob. In what circumstances would it be fair to call me a liar? What if Bob really did get a 90 on the final, and he did pass the class? Then I have not lied; my statement is true. However, if Bob did get a 90 on the final and did not pass the class, then I lied, making the statement false. The tricky case is this: what if Bob did not get a 90 on the final? Maybe he passes the class, maybe he doesn't. Did I lie in either case? I think not. In these last two cases, \(P\) was false, and the statement \(P \imp Q\) was true. In the first case, \(Q\) was true, and so was \(P \imp Q\text{.}\) So \(P \imp Q\) is true when either \(P\) is false or \(Q\) is true.

Just to be clear, although we sometimes read \(P \imp Q\) as “\(P\) implies \(Q\)”, we are not insisting that there is some causal relationship between the statements \(P\) and \(Q\text{.}\) In particular, if you claim that \(P \imp Q\) is false, you are not saying that \(P\) does not imply \(Q\text{,}\) but rather that \(P\) is true and \(Q\) is false.

Example B.1.3.

Decide which of the following statements are true and which are false. Briefly explain.

  1. If \(1=1\text{,}\) then most horses have 4 legs.

  2. If \(0=1\text{,}\) then \(1=1\text{.}\)

  3. If 8 is a prime number, then the 7624th digit of \(\pi\) is an 8.

  4. If the 7624th digit of \(\pi\) is an 8, then \(2+2 = 4\text{.}\)

Solution

All four of the statements are true. Remember, the only way for an implication to be false is for the if part to be true and the then part to be false.

  1. Here both the hypothesis and the conclusion are true, so the implication is true. It does not matter that there is no meaningful connection between the true mathematical fact and the fact about horses.

  2. Here the hypothesis is false and the conclusion is true, so the implication is true.

  3. I have no idea what the 7624th digit of \(\pi\) is, but this does not matter. Since the hypothesis is false, the implication is automatically true.

  4. Similarly here, regardless of the truth value of the hypothesis, the conclusion is true, making the implication true.

It is important to understand the conditions under which an implication is true not only to decide whether a mathematical statement is true, but in order to prove that it is. Proofs might seem scary (especially if you have had a bad high school geometry experience) but all we are really doing is explaining (very carefully) why a statement is true. If you understand the truth conditions for an implication, you already have the outline for a proof.

Direct Proofs of Implications.

To prove an implication \(P \imp Q\text{,}\) it is enough to assume \(P\text{,}\) and from it, deduce \(Q\text{.}\)

Perhaps a better way to say this is that to prove a statement of the form \(P \imp Q\) directly, you must explain why \(Q\) is true, but you get to assume \(P\) is true first. After all, you only care about whether \(Q\) is true in the case that \(P\) is as well.

There are other techniques to prove statements (implications and others) that we will encounter throughout our studies, and new proof techniques are discovered all the time. Direct proof is the easiest and most elegant style of proof and has the advantage that such a proof often does a great job of explaining why the statement is true.

Example B.1.4.

Prove: If two numbers \(a\) and \(b\) are even, then their sum \(a+b\) is even.

Solution

Suppose the numbers \(a\) and \(b\) are even. This means that \(a = 2k\) and \(b=2j\) for some integers \(k\) and \(j\text{.}\) The sum is then \(a+b = 2k+2j = 2(k+j)\text{.}\) Since \(k+j\) is an integer, this means that \(a+b\) is even.

Notice that since we get to assume the hypothesis of the implication, we immediately have a place to start. The proof proceeds essentially by repeatedly asking and answering, “what does that mean?” Eventually, we conclude that it means the conclusion.

This sort of argument shows up outside of math as well. If you ever found yourself starting an argument with “hypothetically, let's assume …,” then you have attempted a direct proof of your desired conclusion.

An implication is a way of expressing a relationship between two statements. It is often interesting to ask whether there are other relationships between the statements. Here we introduce some common language to address this question.

Converse and Contrapositive.
  • The converse of an implication \(P \imp Q\) is the implication \(Q \imp P\text{.}\) The converse is NOT logically equivalent to the original implication. That is, whether the converse of an implication is true is independent of the truth of the implication.

  • The contrapositive of an implication \(P \imp Q\) is the statement \(\neg Q \imp \neg P\text{.}\) An implication and its contrapositive are logically equivalent (they are either both true or both false).

Mathematics is overflowing with examples of true implications which have a false converse. If a number greater than 2 is prime, then that number is odd. However, just because a number is odd does not mean it is prime. If a shape is a square, then it is a rectangle. But it is false that if a shape is a rectangle, then it is a square.

However, sometimes the converse of a true statement is also true. For example, the Pythagorean theorem has a true converse: if\(a^2 + b^2 = c^2\text{,}\) then the triangle with sides \(a\text{,}\) \(b\text{,}\) and \(c\) is a right triangle. Whenever you encounter an implication in mathematics, it is always reasonable to ask whether the converse is true.

The contrapositive, on the other hand, always has the same truth value as its original implication. This can be very helpful in deciding whether an implication is true: often it is easier to analyze the contrapositive.

Example B.1.5.

True or false: If you draw any nine playing cards from a regular deck, then you will have at least three cards all of the same suit. Is the converse true?

Solution

True. The original implication is a little hard to analyze because there are so many different combinations of nine cards. But consider the contrapositive: If you don't have at least three cards all of the same suit, then you don't have nine cards. It is easy to see why this is true: you can at most have two cards of each of the four suits, for a total of eight cards (or fewer).

The converse: If you have at least three cards all of the same suit, then you have nine cards. This is false. You could have three spades and nothing else. Note that to demonstrate that the converse (an implication) is false, we provided an example where the hypothesis is true (you do have three cards of the same suit), but where the conclusion is false (you do not have nine cards).

Understanding converses and contrapositives can help understand implications and their truth values:

Example B.1.6.

Suppose I tell Sue that if she gets a 93% on her final, then she will get an A in the class. Assuming that what I said is true, what can you conclude in the following cases:

  1. Sue gets a 93% on her final.

  2. Sue gets an A in the class.

  3. Sue does not get a 93% on her final.

  4. Sue does not get an A in the class.

Solution

Note first that whenever \(P \imp Q\) and \(P\) are both true statements, \(Q\) must be true as well. For this problem, take \(P\) to mean “Sue gets a 93% on her final” and \(Q\) to mean “Sue will get an A in the class.”

  1. We have \(P \imp Q\) and \(P\text{,}\) so \(Q\) follows. Sue gets an A.

  2. You cannot conclude anything. Sue could have gotten the A because she did extra credit for example. Notice that we do not know that if Sue gets an \(A\text{,}\) then she gets a 93% on her final. That is the converse of the original implication, so it might or might not be true.

  3. The contrapositive of the converse of \(P \imp Q\) is \(\neg P \imp \neg Q\text{,}\) which states that if Sue does not get a 93% on the final, then she will not get an A in the class. But this does not follow from the original implication. Again, we can conclude nothing. Sue could have done extra credit.

  4. What would happen if Sue does not get an A but did get a 93% on the final? Then \(P\) would be true and \(Q\) would be false. This makes the implication \(P \imp Q\) false! It must be that Sue did not get a 93% on the final. Notice now we have the implication \(\neg Q \imp \neg P\) which is the contrapositive of \(P \imp Q\text{.}\) Since \(P \imp Q\) is assumed to be true, we know \(\neg Q \imp \neg P\) is true as well.

As we said above, an implication is not logically equivalent to its converse, but it is possible that both the implication and its converse are true. In this case, when both \(P \imp Q\) and \(Q \imp P\) are true, we say that \(P\) and \(Q\) are equivalent and write \(P \iff Q\text{.}\) This is the biconditional we mentioned earlier.

If and only if.

\(P \iff Q\) is logically equivalent to \((P \imp Q) \wedge (Q \imp P)\text{.}\)

Example: Given an integer \(n\text{,}\) it is true that \(n\) is even if and only if \(n^2\) is even. That is, if \(n\) is even, then \(n^2\) is even, as well as the converse: if \(n^2\) is even, then \(n\) is even.

You can think of “if and only if” statements as having two parts: an implication and its converse. We might say one is the “if” part, and the other is the “only if” part. We also sometimes say that “if and only if” statements have two directions: a forward direction \((P \imp Q)\) and a backwards direction (\(P \leftarrow Q\text{,}\) which is really just sloppy notation for \(Q \imp P\)).

Let's think a little about which part is which. Is \(P \imp Q\) the “if” part or the “only if” part? Consider an example.

Example B.1.7.

Suppose it is true that I sing if and only if I'm in the shower. We know this means both that if I sing, then I'm in the shower, and also the converse, that if I'm in the shower, then I sing. Let \(P\) be the statement, “I sing,” and \(Q\) be, “I'm in the shower.” So \(P \imp Q\) is the statement “if I sing, then I'm in the shower.” Which part of the if and only if statement is this?

What we are really asking for is the meaning of “I sing if I'm in the shower” and “I sing only if I'm in the shower.” When is the first one (the “if” part) false? When I am in the shower but not singing. That is the same condition on being false as the statement “if I'm in the shower, then I sing.” So the “if” part is \(Q \imp P\text{.}\) On the other hand, to say, “I sing only if I'm in the shower” is equivalent to saying “if I sing, then I'm in the shower,” so the “only if” part is \(P \imp Q\text{.}\)

It is not terribly important to know which part is the “if” or “only if” part, but this does illustrate something very, very important: there are many ways to state an implication!

Example B.1.8.

Rephrase the implication, “if I dream, then I am asleep” in as many different ways as possible. Then do the same for the converse.

Solution

The following are all equivalent to the original implication:

  1. I am asleep if I dream.

  2. I dream only if I am asleep.

  3. In order to dream, I must be asleep.

  4. To dream, it is necessary that I am asleep.

  5. To be asleep, it is sufficient to dream.

  6. I am not dreaming unless I am asleep.

The following are equivalent to the converse (if I am asleep, then I dream):

  1. I dream if I am asleep.

  2. I am asleep only if I dream.

  3. It is necessary that I dream in order to be asleep.

  4. It is sufficient that I be asleep in order to dream.

  5. If I don't dream, then I'm not asleep.

Hopefully you agree with the above example. We include the “necessary and sufficient” versions because those are common when discussing mathematics. In fact, let's agree once and for all what they mean.

Necessary and Sufficient.
  • “\(P\) is necessary for \(Q\)” means \(Q \imp P\text{.}\)
  • “\(P\) is sufficient for \(Q\)” means \(P \imp Q\text{.}\)
  • If \(P\) is necessary and sufficient for \(Q\text{,}\) then \(P \iff Q\text{.}\)

To be honest, I have trouble with these if I'm not very careful. I find it helps to keep a standard example for reference.

Example B.1.9.

Recall from calculus, if a function is differentiable at a point \(c\text{,}\) then it is continuous at \(c\text{,}\) but that the converse of this statement is not true (for example, \(f(x) = |x|\) at the point 0). Restate this fact using “necessary and sufficient” language.

Solution

It is true that in order for a function to be differentiable at a point \(c\text{,}\) it is necessary for the function to be continuous at \(c\text{.}\) However, it is not necessary that a function be differentiable at \(c\) for it to be continuous at \(c\text{.}\)

It is true that to be continuous at a point \(c\text{,}\) it is sufficient that the function be differentiable at \(c\text{.}\) However, it is not the case that being continuous at \(c\) is sufficient for a function to be differentiable at \(c\text{.}\)

Thinking about the necessity and sufficiency of conditions can also help when writing proofs and justifying conclusions. If you want to establish some mathematical fact, it is helpful to think what other facts would be enough (be sufficient) to prove your fact. If you have an assumption, think about what must also be necessary if that hypothesis is true.

Subsection B.1.3 Predicates and Quantifiers

Puzzle 332.

Consider the statements below. Decide whether any are equivalent to each other, or whether any imply any others.

  1. You can fool some people all of the time.

  2. You can fool everyone some of the time.

  3. You can always fool some people.

  4. Sometimes you can fool everyone.

It would be nice to use variables in our mathematical sentences. For example, suppose we wanted to claim that if \(n\) is prime, then \(n+7\) is not prime. This looks like an implication. I would like to write something like

\begin{equation*} P(n) \imp \neg P(n+7) \end{equation*}

where \(P(n)\) means “\(n\) is prime.” But this is not quite right. For one thing, because this sentence has a free variable (that is, a variable that we have not specified anything about), it is not a statement. A sentence that contains variables is called a predicate.

Now, if we plug in a specific value for \(n\text{,}\) we do get a statement. In fact, it turns out that no matter what value we plug in for \(n\text{,}\) we get a true implication in this case. What we really want to say is that for all values of \(n\text{,}\) if \(n\) is prime, then \(n+7\) is not. We need to quantify the variable.

Although there are many types of quantifiers in English (e.g., many, few, most, etc.) in mathematics we, for the most part, stick to two: existential and universal.

Universal and Existential Quantifiers.

The existential quantifier is \(\exists\) and is read “there exists” or “there is.” For example,

\begin{equation*} \exists x (x \lt 0) \end{equation*}

asserts that there is a number less than 0.

The universal quantifier is \(\forall\) and is read “for all” or “every.” For example,

\begin{equation*} \forall x (x \ge 0) \end{equation*}

asserts that every number is greater than or equal to 0.

As with all mathematical statements, we would like to decide whether quantified statements are true or false. Consider the statement

\begin{equation*} \forall x \exists y (y \lt x)\text{.} \end{equation*}

You would read this, “for every \(x\) there is some \(y\) such that \(y\) is less than \(x\text{.}\)” Is this true? The answer depends on what our domain of discourse is: when we say “for all” \(x\text{,}\) do we mean all positive integers or all real numbers or all elements of some other set? Usually this information is implied. In discrete mathematics, we almost always quantify over the natural numbers, 0, 1, 2, …, so let's take that for our domain of discourse here.

For the statement to be true, we need it to be the case that no matter what natural number we select, there is always some natural number that is strictly smaller. Perhaps we could let \(y\) be \(x-1\text{?}\) But here is the problem: what if \(x = 0\text{?}\) Then \(y = -1\) and that is not a number! (in our domain of discourse). Thus we see that the statement is false because there is a number which is less than or equal to all other numbers. In symbols,

\begin{equation*} \exists x \forall y (y \ge x)\text{.} \end{equation*}

To show that the original statement is false, we proved that the negation was true. Notice how the negation and original statement compare. This is typical.

Quantifiers and Negation.

\(\neg \forall x P(x)\) is equivalent to \(\exists x \neg P(x)\text{.}\)

\(\neg \exists x P(x)\) is equivalent to \(\forall x \neg P(x) \text{.}\)

Essentially, we can pass the negation symbol over a quantifier, but that causes the quantifier to switch type. This should not be surprising: if not everything has a property, then something doesn't have that property. And if there is not something with a property, then everything doesn't have that property.

Implicit Quantifiers.

It is always a good idea to be precise in mathematics. Sometimes though, we can relax a little 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: \(S(x)\) standing for “\(x\) is a square” and \(R(x)\) standing for “\(x\) is a rectangle”. The sentence we are looking at is,

\begin{equation*} S(x) \imp R(x)\text{.} \end{equation*}

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,

\begin{equation*} \forall x (S(x) \imp R(x))\text{,} \end{equation*}

and this is what our convention tells us to consider.

Similarly, we will often be a bit sloppy about the distinction between a predicate and a statement. For example, we might write, let \(P(n)\) be the statement, “\(n\) is prime,” which is technically incorrect. It is implicit that we mean that we are defining \(P(n)\) to be a predicate, which for each \(n\) becomes the statement, \(n\) is prime.

Exercises B.1.4 Exercises

1.

For each sentence below, decide whether it is an atomic statement, a molecular statement, or not a statement at all.

  1. Customers must wear shoes.

    • atomic statement

    • molecular statement

    • not a statement

  2. The customers wore shoes.

    • atomic statement

    • molecular statement

    • not a statement

  3. The customers wore shoes and they wore socks.

    • atomic statement

    • molecular statement

    • not a statement

Solution
  1. This is not a statement. It is an imperative sentence, but is not either true or false. It doesn’t matter that this might actually be the rule or not. Note that “The rule is that all customers must wear shoes” is a statement.

  2. This is a statement, as it is either true or false. It is an atomic statement because it cannot be divided into smaller statements.

  3. This is again a statement, but this time it is molecular. In fact, it is a conjunction, as we can write it as “The customers wore shoes and the customers wore socks.”

2.

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

  1. The sum of the first 100 odd positive integers.
  2. Everybody needs somebody sometime.
  3. The Broncos will win the Super Bowl or I'll eat my hat.
  4. We can have donuts for dinner, but only if it rains.
  5. Every natural number greater than 1 is either prime or composite.
  6. This sentence is false.
3.

Suppose \(P\) and \(Q\) are the statements: \(P\text{:}\) Jack passed math. \(Q\text{:}\) Jill passed math.

  1. Translate “Jack and Jill both passed math” into symbols.

  2. Translate “If Jack passed math, then Jill did not” into symbols.

  3. Translate “\(P \vee Q\)” into English.

  4. Translate “\(\neg(P \wedge Q) \imp Q\)” into English.

  5. Suppose you know that if Jack passed math, then so did Jill. What can you conclude if you know that:

    1. Jill passed math?
    2. Jill did not pass math?
Solution
  1. \(P \wedge Q\text{.}\)
  2. \(P \imp \neg Q\text{.}\)
  3. Jack passed math or Jill passed math (or both).

  4. If Jack and Jill did not both pass math, then Jill did.

    1. Nothing else.
    2. Jack did not pass math either.
4.

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 that 13 is prime).

  1. If 13 is prime, then 13 is my favorite number.

    • True

    • False

    • Not enough information

  2. If 13 is my favorite number, then 13 is prime.

    • True

    • False

    • Not enough information

  3. If 13 is not prime, then 13 is my favorite number.

    • True

    • False

    • Not enough information

  4. 13 is my favorite number or 13 is prime.

    • True

    • False

    • Not enough information

  5. 13 is my favorite number and 13 is prime.

    • True

    • False

    • Not enough information

  6. 7 is my favorite number and 13 is not prime.

    • True

    • False

    • Not enough information

  7. 13 is my favorite number or 13 is not my favorite number.

    • True

    • False

    • Not enough information

Solution
  1. It is impossible to tell. The hypothesis of the implication is true. Thus the implication will be true if the conclusion is true (if 13 is my favorite number) and false otherwise.

  2. This is true, no matter whether 13 is my favorite number or not. Any implication with a true conclusion is true.

  3. This is true, again, no matter whether 13 is my favorite number or not. Any implication with a false hypothesis is true.

  4. For a disjunction to be true, we just need one or the other (or both) of the parts to be true. Thus this is a true statement.

  5. We cannot tell. The statement would be true if 13 is my favorite number, and false if not (since a conjunction needs both parts to be true to be true).

  6. This is definitely false. 13 is prime, so its negation (13 is not prime) is false. At least one part of the conjunction is false, so the whole statement is false.

  7. This is true. Either 13 is my favorite number or it is not, but whichever it is, at least one part of the disjunction is true, so the whole statement is true.

5.

In my safe is a sheet of paper with two shapes drawn on it in colored crayon. One is a square, and the other is a triangle. Each shape is drawn in a single color. Suppose you believe me when I tell you that if the square is blue, then the triangle is green. What do you therefore know about the truth value of the following statements?

  1. The square and the triangle are both blue.

    • True

    • False

    • Not enough information

  2. The square and the triangle are both green.

    • True

    • False

    • Not enough information

  3. If the triangle is not green, then the square is not blue.

    • True

    • False

    • Not enough information

  4. If the triangle is green, then the square is blue.

    • True

    • False

    • Not enough information

  5. The square is not blue or the triangle is green.

    • True

    • False

    • Not enough information

Solution

The main thing to realize is that we don’t know the colors of these two shapes, but we do know that we are in one of three cases: We could have a blue square and green triangle. We could have a square that was not blue but a green triangle. Or we could have a square that was not blue and a triangle that was not green. The case in which the square is blue but the triangle is not green cannot occur, as that would make the statement false.

  1. This must be false. In fact, this is the negation of the original implication.

  2. This might be true or might be false.

  3. True. This is the contrapositive of the original statement, which is logically equivalent to it.

  4. We do not know. This is the converse of the original statement. In particular, if the square is not blue but the triangle is green, then the original statement is true but the converse is false.

  5. True. This is logically equivalent to the original statement.

6.

Again, suppose the statement “if the square is blue, then the triangle is green” is true. This time however, assume the converse is false. Classify each statement below as true or false (if possible).

  1. The square is blue if and only if the triangle is green.

    • True

    • False

    • Not enough information

  2. The square is blue if and only if the triangle is not green.

    • True

    • False

    • Not enough information

  3. The square is blue.

    • True

    • False

    • Not enough information

  4. The triangle is green.

    • True

    • False

    • Not enough information

Solution

The only way for an implication \(P\imp Q\) to be true but its converse to be false is for \(Q\) to be true and \(P\) to be false. Thus:

  1. False.

  2. True.

  3. False.

  4. True.

7.

Consider the statement, “If you will give me a cow, then I will give you magic beans.” Decide whether each statement below is the converse, the contrapositive, or neither.

  1. If you will give me a cow, then I will not give you magic beans.

    • Converse

    • Contrapositive

    • Neither

  2. If I will not give you magic beans, then you will not give me a cow.

    • Converse

    • Contrapositive

    • Neither

  3. If I will give you magic beans, then you will give me a cow.

    • Converse

    • Contrapositive

    • Neither

  4. If you will not give me a cow, then I will not give you magic beans.

    • Converse

    • Contrapositive

    • Neither

  5. You will give me a cow and I will not give you magic beans.

    • Converse

    • Contrapositive

    • Neither

  6. If I will give you magic beans, then you will not give me a cow.

    • Converse

    • Contrapositive

    • Neither

Solution

The converse is “If I will give you magic beans, then you will give me a cow.” The contrapositive is “If I will not give you magic beans, then you will not give me a cow.” All the other statements are neither the converse nor contrapositive.

8.

Consider the statement “If Oscar eats Chinese food, then he drinks milk.”

  1. Write the converse of the statement.

  2. Write the contrapositive of the statement.

  3. Is it possible for the contrapositive to be false? If it was, what would that tell you?

  4. Suppose the original statement is true, and that Oscar drinks milk. Can you conclude anything (about his eating Chinese food)? Explain.

  5. Suppose the original statement is true, and that Oscar does not drink milk. Can you conclude anything (about his eating Chinese food)? Explain.

9.

You have discovered an old paper on graph theory that discusses the viscosity of a graph (which for all you know, is something completely made up by the author). A theorem in the paper claims that “if a graph satisfies condition (V), then the graph is viscous.” Which of the following are equivalent ways of stating this claim? Which are equivalent to the converse of the claim?

  1. A graph is viscous only if it satisfies condition (V).

    • Original

    • Converse

    • Neither

  2. A graph is viscous if it satisfies condition (V).

    • Original

    • Converse

    • Neither

  3. For a graph to be viscous, it is necessary that it satisfies condition (V).

    • Original

    • Converse

    • Neither

  4. For a graph to be viscous, it is sufficient for it to satisfy condition (V).

    • Original

    • Converse

    • Neither

  5. Satisfying condition (V) is a sufficient condition for a graph to be viscous.

    • Original

    • Converse

    • Neither

  6. Satisfying condition (V) is a necessary condition for a graph to be viscous.

    • Original

    • Converse

    • Neither

  7. Every viscous graph satisfies condition (V).

    • Original

    • Converse

    • Neither

  8. Only viscous graphs satisfy condition (V).

    • Original

    • Converse

    • Neither

Solution
  1. Equivalent to the converse.

  2. Equivalent to the original theorem.

  3. Equivalent to the converse.

  4. Equivalent to the original theorem.

  5. Equivalent to the original theorem.

  6. Equivalent to the converse.

  7. Equivalent to the converse.

  8. Equivalent to the original theorem.

10.

Write each of the following statements in the form, “if …, then ….” Careful, some of the statements might be false (which is alright for the purposes of this question).

  1. To lose weight, you must exercise.

  2. To lose weight, all you need to do is exercise.

  3. Every American is patriotic.

  4. You are patriotic only if you are American.

  5. The set of rational numbers is a subset of the real numbers.

  6. A number is prime if it is not even.

  7. Either the Broncos will win the Super Bowl, or they won't play in the Super Bowl.

Solution
  1. If you have lost weight, then you exercised.

  2. If you exercise, then you will lose weight.

  3. If you are American, then you are patriotic.

  4. If you are patriotic, then you are American.

  5. If a number is rational, then it is real.

  6. If a number is not even, then it is prime. (Or the contrapositive: if a number is not prime, then it is even.)

  7. If the Broncos don't win the Super Bowl, then they didn't play in the Super Bowl. Alternatively, if the Broncos play in the Super Bowl, then they will win the Super Bowl.

11.

Which of the following statements are equivalent to the implication, “if you win the lottery, then you will be rich,” and which are equivalent to the converse of the implication?

  1. Either you win the lottery or else you are not rich.

  2. Either you don't win the lottery or else you are rich.

  3. You will win the lottery and be rich.

  4. You will be rich if you win the lottery.

  5. You will win the lottery if you are rich.

  6. It is necessary for you to win the lottery to be rich.

  7. It is sufficient to win the lottery to be rich.

  8. You will be rich only if you win the lottery.

  9. Unless you win the lottery, you won't be rich.

  10. If you are rich, you must have won the lottery.

  11. If you are not rich, then you did not win the lottery.

  12. You will win the lottery if and only if you are rich.

12.

Let \(P(x)\) be the predicate, “\(3x+1\) is even.”

  1. Is \(P(5)\) true or false?

    • True

    • False

    • Neither (not a statement)

  2. What, if anything, can you conclude about \(\exists x P(x)\) from the truth value of \(P(5)\text{?}\)

  3. What, if anything, can you conclude about \(\forall x P(x)\) from the truth value of \(P(5)\text{?}\)

Solution

\(P(5)\) is the statement “\(3\cdot 5 + 1\) is even”, which is true. Thus the statement \(\exists x P(x)\) is true (for example, 5 is such an \(x\)). However, we cannot tell anything about \(\forall x P(x)\) since we do not know the truth value of \(P(x)\) for all elements of the domain of discourse. In this case, \(\forall x P(x)\) happens to be false (since \(P(4)\) is false, for example).

13.

Let \(P(x)\) be the predicate, “\(4x+1\) is even.”

  1. Is \(P(5)\) true or false?

    • True

    • False

    • Not enough information

  2. What, if anything, can you conclude about \(\exists x P(x)\) from the truth value of \(P(5)\text{?}\)

  3. What, if anything, can you conclude about \(\forall x P(x)\) from the truth value of \(P(5)\text{?}\)

14.

For a given predicate \(P(x)\text{,}\) you might believe that the statements \(\forall x P(x)\) or \(\exists x P(x)\) are either true or false. How would you decide if you were correct in each case? You have four choices: you could give an example of an element \(n\) in the domain for which \(P(n)\) is true or for which \(P(n)\) if false, or you could argue that no matter what \(n\) is, \(P(n)\) is true or is false.

  1. What would you need to do to prove \(\forall x P(x)\) is true?

  2. What would you need to do to prove \(\forall x P(x)\) is false?

  3. What would you need to do to prove \(\exists x P(x)\) is true?

  4. What would you need to do to prove \(\exists x P(x)\) is false?

Solution
  1. The claim that \(\forall x P(x)\) means that \(P(n)\) is true no matter what \(n\) you consider in the domain of discourse. Thus the only way to prove that \(\forall x P(x)\) is true is to check or otherwise argue that \(P(n)\) is true for all \(n\) in the domain.

  2. To prove \(\forall x P(x)\) is false all you need is one example of an element in the domain for which \(P(n)\) is false. This is often called a counterexample.

  3. We are simply claiming that there is some element \(n\) in the domain of discourse for which \(P(n)\) is true. If you can find one such element, you have verified the claim.

  4. Here we are claiming that no element we find will make \(P(n)\) true. The only way to be sure of this is to verify that every element of the domain makes \(P(n)\) false. Note that the level of proof needed for this statement is the same as to prove that \(\forall x P(x)\) is true.

15.

Suppose \(P(x,y)\) 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, \(P(x,y)\) is either true or false, according to the following table (\(x\) values are rows, \(y\) values are columns).

1 2 3 4
1 T F F F
2 F T T F
3 T T T T
4 F F F F

For example, \(P(1,3)\) is false, as indicated by the F in the first row, third column.

Use the table to decide whether the following statements are true or false.

  1. \(\forall x \exists y P(x,y)\text{.}\)

    • True

    • False

    • Not enough information

  2. \(\forall y \exists x P(x,y)\text{.}\)

    • True

    • False

    • Not enough information

  3. \(\exists x \forall y P(x,y)\text{.}\)

    • True

    • False

    • Not enough information

  4. \(\exists y \forall x P(x,y)\text{.}\)

    • True

    • False

    • Not enough information

Solution
  1. \(\forall x \exists y P(x,y)\) is false because when \(x = 4\text{,}\) there is no \(y\) which makes \(P(4,y)\) true.

  2. \(\forall y \exists x P(x,y)\) is true. No matter what \(y\) is (i.e., no matter what column we are in) there is some \(x\) for which \(P(x,y)\) is true. In fact, we can always take \(x\) to be \(3\text{.}\)

  3. \(\exists x \forall y P(x,y)\) is true. In particular \(x=3\) is such a number, so that no matter what \(y\) is, \(P(x,y)\) is true.

  4. \(\exists y \forall x P(x,y)\) is false. In fact, no matter what \(y\) (column) we look at, there is always some \(x\) (row) which makes \(P(x,y)\) false.

16.

Translate into symbols. Use \(E(x)\) for “\(x\) is even” and \(O(x)\) for “\(x\) is odd.”

  1. No number is both even and odd.

  2. One more than any even number is an odd number.

  3. There is prime number that is even.

  4. Between any two numbers there is a third number.

  5. There is no number between a number and one more than that number.

Solution
  1. \(\neg \exists x (E(x) \wedge O(x))\text{.}\)
  2. \(\forall x (E(x) \imp O(x+1))\text{.}\)
  3. \(\exists x(P(x) \wedge E(x))\) (where \(P(x)\) means “\(x\) is prime”).
  4. \(\forall x \forall y \exists z(x \lt z \lt y \vee y \lt z \lt x)\text{.}\)
  5. \(\forall x \neg \exists y (x \lt y \lt x+1)\text{.}\)
17.

Translate into English:

  1. \(\forall x (E(x) \imp E(x +2))\text{.}\)
  2. \(\forall x \exists y (\sin(x) = y)\text{.}\)
  3. \(\forall y \exists x (\sin(x) = y)\text{.}\)
  4. \(\forall x \forall y (x^3 = y^3 \imp x = y)\text{.}\)
Solution
  1. Any even number plus 2 is an even number.

  2. For any \(x\) there is a \(y\) such that \(\sin(x) = y\text{.}\) In other words, every number \(x\) is in the domain of sine.

  3. For every \(y\) there is an \(x\) such that \(\sin(x) = y\text{.}\) In other words, every number \(y\) is in the range of sine (which is false).

  4. For any numbers, if the cubes of two numbers are equal, then the numbers are equal.

18.

Suppose \(P(x)\) is some predicate for which the statement \(\forall x P(x)\) is true. Is it also the case that \(\exists x P(x)\) is true? In other words, is the statement \(\forall x P(x) \imp \exists x P(x)\) always true? Is the converse always true? Assume the domain of discourse is non-empty.

Hint

Try an example. What if \(P(x)\) was the predicate, “\(x\) is prime”? What if it was “if \(x\) is divisible by 4, then it is even”? Of course examples are not enough to prove something in general, but that is entirely the point of this question.

19.

For each of the statements below, give a domain of discourse for which the statement is true, and a domain for which the statement is false.

  1. \(\forall x \exists y (y^2 = x)\text{.}\)
  2. \(\forall x \forall y (x \lt y \imp \exists z (x \lt z \lt y))\text{.}\)
  3. \(\exists x \forall y \forall z (y \lt z \imp y \le x \le z)\text{.}\)
Hint

First figure out what each statement is saying. For part (c), you don't need to assume the domain is an infinite set.

20.

Consider the statement, “For all natural numbers \(n\text{,}\) if \(n\) is prime, then \(n\) is solitary.” You do not need to know what solitary means for this problem, just that it is a property that some numbers have and others do not.

  1. Write the converse and the contrapositive of the statement, saying which is which. Note: the original statement claims that an implication is true for all \(n\text{,}\) and it is that implication that we are taking the converse and contrapositive of.

  2. Write the negation of the original statement. What would you need to show to prove that the statement is false?

  3. Even though you don't know whether 10 is solitary (in fact, nobody knows this), is the statement “if 10 is prime, then 10 is solitary” true or false? Explain.

  4. It turns out that 8 is solitary. Does this tell you anything about the truth or falsity of the original statement, its converse or its contrapositive? Explain.

  5. Assuming that the original statement is true, what can you say about the relationship between the set \(P\) of prime numbers and the set \(S\) of solitary numbers. Explain.