Exercises 2.5 Exercises
1.
Consider the sentence “Bob is wearing flip flops or it is cold out.”
Choosing your own letters, symbolize this statement.
Write a truth table for this statement.
In the northern United States there is an unspoken but universally acknowledged competition to be the last man in shorts and flip-flops.
2.
Let \(p\) stand for “I attended class” and \(q\) stand for “I did the homework.”
Symbolize “I attended class but I did not do the homework.”
Write a truth table for this statement.
In English, the word “but” means that two statements are simultaneously, maybe surprisingly, both true.
The statement is \(p \wedge \neg q\text{.}\)
| \(p\) | \(q\) | \(\neg q\) | \(p \wedge \neg q\) |
| \(T\) | \(T\) | \(F\) | \(T\) |
| \(T\) | \(F\) | \(T\) | \(T\) |
| \(F\) | \(T\) | \(F\) | \(F\) |
| \(F\) | \(F\) | \(T\) | \(F\) |
3.
Should the statement “Alicia is doing homework or playing video games” be symbolized as \(p \vee q\) or \(p \oplus q\text{?}\) Explain your reasoning.
Hint.Can Alicia do homework and play video games at the same time?
4.
Let \(p\) be the statement “The teachers unionize”, let \(q\) be the statement “The mayor listens to their demands”, \(r\) be “The students can go to school”, and \(s\) be “The teachers can work safely”. Symbolize “If the teachers unionize, then the mayor listens to their demands or the students can't go to school.”
Solution.5.
If \(r\) is the statement “I attended class”, \(s\) is the statement “I did the homework”, and \(t\) is the statement “I passed the exam”, symbolize (write with symbols) the statement “If I attend class but don't do the homework, then I will fail the exam.”
6.
If \(p\) is the statement “The tacos have cilantro”, \(q\) is the statement “Ash will have the tacos”, and \(r\) is the statement “Ash will have a cola”, symbolize the statement “Ash will have the tacos and a cola, if and only if the tacos don't have cilantro.”
7.
Let \(p\) be the statement “The teachers unionize”, let \(q\) be the statement “The mayor listens to their demands”, \(r\) be “The students can go to school”, and \(s\) be “The teachers can work safely”. Write the statement \((q \wedge s) \leftrightarrow p\) in English.
Solution.Solution: The mayor will listen to their demands and the teachers can work safely if and only if the teachers unionize.
8.
If \(r\) is the statement “I attended class”, \(s\) is the statement “I did the homework”, and \(t\) is the statement “I passed the exam”, write the statement \(t \leftrightarrow (\neg r \vee \neg s)\) in English.
9.
If \(p\) is the statement “The tacos have cilantro”, \(q\) is the statement “Ash will have the tacos”, and \(r\) is the statement “Ash will have a cola”, write the statement \(r \vee (p \to q)\) in English.
10.
Prove \(p \leftrightarrow q\) and \(q \leftrightarrow p\) are equivalent using a method of your choosing.
11.
In this exercise you will explore the relationship between a conditional statement \(p \to q\text{,}\) its converse \(q \to p\text{,}\) its inverse \(\neg p \to \neg q\text{,}\) and its contrapositive \(\neg q \to \neg p\text{.}\)
Prove using a truth table that a conditional is equivalent to its contrapositive.
Prove using a truth table that a conditional is not equivalent to its inverse.
There is one other equivalence among these four statements. What is it? (Find it, but you don't need to prove it.)
12.
Suppose that it whenever it rains, Alicia brings her umbrella. Answer the following questions and in both cases explain your reasoning.
If Alicia brings her umbrella, can you can conclude whether it is raining?
If Alicia does not bring her umbrella, can you conclude whether it is raining?
13.
Suppose the following sentence is true: “If an integer is odd and greater than \(2\text{,}\) then it is prime.” (This sentence is false, but that doesn't matter—suppose it is true.)
Suppose further that we have a integer, \(n\text{.}\) Can we conclude that \(n\) is odd and greater than \(2\) if...
\(n\) is prime?
\(n\) is not prime?
In both answers, explain your reasoning.
14.
Using one or more truth tables, determine which pairs of the following statements are and are not equivalent.
\(\displaystyle p \leftrightarrow q\)
\(\displaystyle \neg p \leftrightarrow q\)
\(\displaystyle p \leftrightarrow \neg q\)
\(\displaystyle \neg p \leftrightarrow \neg q\)
15.
Prove that \(\neg(q \to r) \wedge s\) and \(q \wedge (s \to r)\) are equivalent using a truth table.
Hint.Hint: You proved they were equivalent using substitution in a 2.2 example.
16.
Prove modus ponens using a truth table.
17.
Write down a truth table for the statement \((p \wedge r) \to (q \vee \neg s)\text{.}\)
18.
Write a truth table for the statement \(s \leftrightarrow \neg(t \wedge u \wedge \neg v)\text{.}\)
19.
Show that
is a rule of inference by using a truth table.
This generalizes to the technique proof by cases, which proves
by proving \(p_1 \to q\text{,}\) \(p_2 \to q\text{,}\) etc., \(p_n \to q\text{.}\)
Hint.Hint: It is enough to show that there is no row where \(p \to s\text{,}\) \(q \to s\text{,}\) and \(r \to s\) are all true while \((p \vee q \vee r) \to s\) is false.
20.
Prove that
is a tautology by using a truth table.
It is common in mathematical writing to claim that three statements are equivalent. This claim can be proven by showing that the statements imply each other “in a circle,” like in the above rule of inference. Verify for yourself that the above statement also implies that \(p\) and \(q\) are equivalent, as are \(q\) and \(r\text{.}\)
Hint.Hint: It is enough to show that there is no row where \(p \to q\text{,}\) \(q \to r\text{,}\) and \(r \to p\) are all true while \((p \leftrightarrow r)\) is false.
For this set of problems, let \(C(x)\) stand for “\(x\) is a cloobledoo,” \(G(x)\) stand for “\(x\) is green,” \(H(x,y)\) stand for “\(x\) hunts \(y\text{,}\)” and \(Q(x)\) stand for “\(x\) is a quarpake.” (You are not supposed to know what a cloobledoo or what a quarpake are, but you are encouraged to doodle what you think each looks like.)
21.
Symbolize “There is something that is green but not a cloobledoo.”
22.
Symbolize “Every green quarpake is a cloobledoo.”
23.
Symbolize “Every cloobledoo is a quarpake, but not all quarpakes are cloobledoos.”
Hint.Hint: Remember “but” means “and”. You should try to combine two simpler statements to make this one.
24.
Translate \(\forall x [C(x) \to G(x)]\) into words.
25.
Translate \(\forall x \exists y [(Q(x) \to (C(y) \wedge H(x,y))]\) into words.
26.
Translate \(\exists x \forall y [Q(x) \wedge (H(x,y) \leftrightarrow G(y))]\) into words.
Solution.Solution: This statement says:
There is a quarpake.
That quarpake hunts every thing if and only if that thing is green.
So, we can tie these two parts together: “There is a quarpake that hunts all and only those things that are green.”
27.
Negate the statement \(\forall x [C(x) \to G(x)]\) such that every negation appears to the right of every quantifier and such that your final answer contains a conjunction.
28.
Negate the statement \(\forall x \exists y [(Q(x) \to (C(y) \wedge H(x,y))]\) such that every negation appears to the right of every quantifier and such that your final answer contains a conjunction.
29.
Negate the statement \(\exists x \forall y [Q(x) \wedge (H(x,y) \leftrightarrow G(y))]\) such that every negation appears to the right of every quantifier and such that your final answer contains a conditional.
Solution.Solution: First, push the negation in through the quantifiers.
Next, negate the conjunction using DeMorgan's law.
Finally, apply material implication.
There's more we could do but we can stop here. This statement says, “Every quarpake either doesn't hunt a green thing or hunts a non-green thing.” (Chew on this for a while.) Notice this is the negation of “There is a quarpake that hunts all and only those things that are green.”
The following question set involves these predicates defined over the set of all animals. \(H(x)\) denotes “\(x\) is a horse.” \(U(x)\) denotes “\(x\) is a unicorn.” \(B(x)\) denotes “\(x\) is blue.” Finally, \(C(x,y)\) denotes “\(x\) and \(y\) are the same color.”
30.
Symbolize “Every unicorn is blue.”
31.
Symbolize “There is a horse that is not a unicorn that is not blue.”
32.
Symbolize “Every unicorn is a horse, but not every horse is a unicorn.”
33.
Translate \(\exists x [U(x) \wedge \neg B(x)]\) into English.
34.
Translate \(\exists xy [H(x) \wedge U(y) \wedge C(x,y)]\) into English.
35.
Symbolize the negation of \(\exists x [U(x) \wedge \neg B(x)]\) so that no negation appears to the left of the quantifier, and so that it involves a disjunction.
36.
Symbolize the negation of \(\exists xy [H(x) \wedge U(y) \wedge C(x,y)]\) so that no negation appears to the left of the quantifier, and so that it involves a conditional.
For the next set of problems, let \(C(x)\) be “\(x\) is continuous,” \(D(x)\) be “\(x\) is differentiable,” and \(E(x,y)\) be “\(x\) and \(y\) are equal.” These predicates are defined on the space of all functions to and from the real numbers and suppose that \(f\) is the name of a particular, known function. (In other words \(f\) is a subject, not a variable.)
37.
Symbolize “Every differentiable function is continuous.”
38.
Translate \(\exists xy [E(x,y) \to (C(x) \wedge \neg C(y))]\) into English.
39.
Symbolize the negation of \(\exists xy [E(x,y) \to (C(x) \wedge \neg C(y))]\) so that every negation appears to the right of every quantifier and your answer contains a conjunction.
40.
Symbolize the negation of \(\exists x \forall y \exists z (E(y,z) \wedge C(x))\) such that no negation appears to the left of a quantifier. Your answer should contain a conditional.
41.
Translate \(\Big( \forall xy [(E(x,y) \wedge C(x)) \to C(y)] \wedge \exists y [E(f,y) \wedge C(y)]\Big) \to C(f)\) into English.
Solution.Solution: As usual, we should break the statement down into recognizable pieces. First, note that the main connective is the conditional. This sentence says, “If ..., then \(f\) is continuous.”
The ... part of the statement consists of two quantified statements. The first deals with two functions. It says if they are equal and one is continuous, then the second is. That's true of every pair of functions because of the universal quantifier. So, the first part says “Any function that is equal to a continuous function is itself continuous.”
The second statement is of the form “Some ... are ...”. It says, “Some continuous function is equal to \(f\text{.}\)”
Combining all of the pieces, our statement says “If any function equal to a continuous function is itself continuous and there is a continuous function equal to \(f\text{,}\) then \(f\) is continuous.”
42.
Negate the following statement so that no negations appear to the left of any quantifier, and also so that your final answer's main connective is a disjunction.
43.
Back in Chapter 1 we proved that the empty set was a subset of any set using a bizarre technique called “vacuous truth” and you were told to just go with it for the time being? Now we will fully justify ourselves.
Prove that \(\forall x[P(x) \to Q(x)]\) and \(\neg \exists x[P(x) \wedge \neg Q(x)]\) are equivalent.
Explain how this proves that the empty set is a subset of any other set. In particular, tell what the predicates \(P\) and \(Q\) are in this context.