Hints to exercises
First, it’s essential to know what is meant by the term “exclusive or”. This is the interpretation that many people give to the word “or” – where “X or Y” means either X is true or Y is true, but that it isn’t the case that both X and Y are true. This (wrong) understanding of what “or” means is common because it is often the case that X and Y represent complementary possibilities: old or new, cold or hot, right or wrong… The truth table for exclusive or (often written XOR, pronounced “ex-or”, symbolically it is usually \(\oplus\)) is
\[\begin{array}{|c|c|c|} \hline X & Y & X \,\oplus\, Y \\ \hline 1 & 1 & 0 \\ \hline 1 & 0 & 1 \\ \hline 0 & 1 & 1 \\ \hline 0 & 0 & 0 \\ \hline \end{array}\]
So it’s true when one, or the other, but not both of its inputs are true. The upshot of the last sentence is that we can write \(X \oplus Y \; \equiv \; (X \lor Y) \land {\lnot}(X \land Y)\).
The above reformulation should help.
The only question in your mind, when deciding whether a sentence is a statement, should be “Does this thing have a definite truth value?” Well?
Isn’t it just plainly false?
Try to justify why this sentence can’t be either true or false.
Since the sentences involve three variables you’ll need truth tables with 8 rows. Here’s a template.
\[\begin{array}{|c|c|c|c|c|} \hline A & B & C & (A \land B) \lor C & A \land (B \lor C) \\ \hline 1 & 1 & 1 & & \\ \hline 1 & 1 & 0 & & \\ \hline 1 & 0 & 1 & & \\ \hline 1 & 0 & 0 & & \\ \hline 0 & 1 & 1 & & \\ \hline 0 & 1 & 0 & & \\ \hline 0 & 0 & 1 & & \\ \hline 0 & 0 & 0 & & \\ \hline \end{array}\]
Sorry, I know this is probably the hardest problem in the chapter, but I’m (mostly) not going to help. Just one hint to help you get started: NAND and NOR are the negations of AND and OR (respectively) so, for example, \((X \land Y) \; \equiv \; {\lnot}(A \,\vert\, B)\).
Ask one of them what the other one would say to do.
I sometimes like to rephrase the implication \(X \implies Y\) as “\(X\)’s truth forces \(Y\) to be true.” Does that help? If we know that \(X\) being true forces \(Y\) to be true, and we also know that \(Y\) being true will force \(Z\) to be true, what can we conclude?
You should definitely be able to do this one on your own, but anyway, here’s an outline of the table:
\[\begin{array}{|c|c|c|c|} \hline A & B & A \implies B & {\lnot}A \lor B \\ \hline 1 & 1 & & \\ \hline 1 & 0 & & \\ \hline 0 & 1 & & \\ \hline 0 & 0 & & \\ \hline \end{array}\]
No help on this one other than to say that the associative property does not hold for implications.
Hmmm… This will seem like a strange hint, but if you were to hear a kid at the playground say “Oh yeah? Well, I did call your mom a fatty and you still haven’t clobbered me! Owww! OWWW!!! Stop hitting me!!”
What conditional sentence was he attempting to negate?
The way I see it there are eight possible ways to arrange “You fix the toilet” and “I’ll pay the rent” (or their respective negations) around an implication arrow. Here they all are. You decide which one sounds best.
- If you fix the toilet, then I’ll pay the rent.
- If you fix the toilet, then I won’t pay the rent.
- If you don’t fix the toilet, I’ll pay the rent.
- If you don’t fix the toilet, then I won’t pay the rent.
- If I payed the rent, then you must have fixed the toilet.
- If I payed the rent, then you must not have fixed the toilet.
- If I didn’t pay the rent, then you must have fixed the toilet.
- If I didn’t pay the rent, then you must not have fixed the toilet.
Some of those are truly strange.
Unless we’re talking about some celebrity bringing their pet Vietnamese pot-bellied pig into first class with them, or possibly a catapult of some type… The antecedent (the if part) is false, so Yay! I AM the king of Mesopotamia!! Whoo-hooh! What? I’m not? Oh. But the if-then sentence is true. Bummer.
You’ll want to use \(\vert\), the Scheffer stroke, aka NAND, because its truth table contains three \(1\)’s and one \(0\) – you’ll just need to figure out which of its inputs to negate so as to make that one \(0\) occur in the second row of the table instead of the first.
- If you do the crime, you must do the time.
- If you don’t have a good job, you must’ve done poorly in school.
- If you don’t treat others in a certain way, you can’t hope for others to treat you in that fashion,
- If there are no clouds, it can’t be raining.
- If \(\sum_{n=0}^\infty a_n\) is not a convergent series, then either \(a_n \leq b_n\), for some \(n\) or \(\sum_{n=0}^\infty b_n\) is not a convergent series.
The converse is “If I watch your back, then you’ll watch my back.” (Sounds a little dopey doesn’t it — likes its sort of a wishful thinking…) The inverse is “If you don’t watch my back, then I won’t watch your back.” (Sounds less vapid, but it means the same thing…)
The inverse says — if the integral isn’t finite, then the series doesn’t converge. You can cook-up a function that shows this to be false by (for example) creating one with vertical asymptotes that occur in between the integer \(x\)-values. Even one such pole can be enough to make the integral go infinite. The converse says that if the series converges, the integral must be finite. The counter-example we just discussed would work here too.
The contrapositive says that if the series doesn’t converge, then the integral must not be finite. If we were allowed to use discontinuous functions, it isn’t too hard to come up with an \(f\) that actually has zero area under it — just make f be identically zero except at the integer x-values where it will take the same values as the terms of the series. But wait, the function we just described isn’t ``decreasing’’ — which is probably why that hypothesis was put in there!
Could Demosthenes be telling the truth?
These “laws” should probably be layed-out in a big 3-by-3 table. Such a table would of course have 9 cells, but we won’t be using the cells on the diagonal because they would involve an operation distributing over itself. (That can’t happen, can it?) I’m going to put a few of the entries in, and you do the rest.
\[\begin{array}{c|c|c|c|} & + & \ast & \hat{} \\ \hline + & \emptyset & \begin{array}{c} x+(y\ast z) \\= (x+y) \ast (x+z)\end{array} & \begin{array}{c}x+(y^z) \\ = (x+y)^{(x+z)} \end{array} \\ \hline \ast & \begin{array}{c} x \ast (y+z) \\ = (x \ast y) + (x \ast z)\end{array} & \emptyset & \\ \hline \hat{} & & & \emptyset \\ \hline \end{array}\]
You should be able to do these on your own.
Figure 2.15 shows the negation of an AND is the same as the OR of the same inputs negated.
Figure 2.15: Circuits for De Morgan’s law.
Neither of these is particularly amenable to simplification. Nor, perhaps, is it readily apparent what “simplify” means in this context! My interpretation is that we should look for a logically equivalent expression using the fewest number of operators and if possible not using the more complicated operators (\(\implies\) and \(\iff\)). However, if we try to rewrite the first statement’s negation using only \(\land\), \(\lor\) and \(\lnot\) we get things that look a lot more complicated than \((A \lor B) \; \iff \; {\lnot}C\) — the quick way to negate a biconditional is simply to negate one of its parts.
The second statement’s negation turns out to be the same thing as exclusive or, so a particularly simple response would be to write \(A \oplus B\) although that feels a bit like cheating, so maybe we should answer with \((A \lor B) \land {\lnot}(A \land B)\) – but that answer is what we would get by simply applying the rule for negating a conditional and doing no further simplification.
“You smoke and you haven’t got lung cancer.”
“A substance glitters and it is necessarily gold.”
“There is smoke,and there isn’t fire.”
“A number is squared, and the result is not positive.”
“A matrix is square and it is not invertible.”
The ones from Wicca and George Bernard Shaw are just there for laughs.
For the remainder, you may want to contrast how restrictive they seem. For example the Christian version is (in my opinion) a lot stronger than the one from the Talmud — “treat others as you would want to be treated” restricts your actions both in terms of what you would like done to you and in terms of what you wouldn’t like done to you; “Don’t treat your fellows in a way that would be hateful to you.” is leaving you a lot more freedom of action, since it only prohibits you from doing those things you wouldn’t want done to yourself to others. The Hindus, Epictetus and the Jews (and the Wiccans for that matter) seem to be expressing roughly the same sentiment — and promoting an ethic that is rather more easy for humans to conform to!
From a logical perspective it might be nice to define open sentences:
\(W(x,y) =\) “\(x\) would want \(y\) done to him.”
\(N(x,y) =\) “\(x\) would not want \(y\) done to him.”
\(D(x,y) =\) “do \(y\) to \(x\).”
\(DD(x,y) =\) “don’t do \(y\) to \(x\).”
In which case, the aphorism from Luke would be \[ (W(you, y) \implies D(others, y)) \land (N(you, y) \implies DD(others, y)) \]
Here’s the second one:
Proof. Either Wellington is a knave or Wellington is a knight.
It’s either one thing or the other!
If Wellington is a knight it follows that Bonaparte is a knight.
That’s what he said he would tell us and if he’s a knight we can trust him.
If Bonaparte is a knight then Wellington is a knave.
True, because that is one of the things Bonaparte states.
So, if Wellington is a knight then Wellington is a knave (which is impossible!)
This is just summing up what was deduced above.
Thus, Wellington is a knave.
Because the other possibility leads to something possible.
Since Wellington is a knave, his statement “I would tell you that Bonaparte is a knight” is false.
Knave’s statements are always false!}
So Wellington would in fact tell us that Bonaparte is a knave.
He was lying when he said he would tell us B is a knight.
Since Wellington is a knave we conclude that Bonaparte is a knight.
Wait, now I’m confused…can you do this part?
Thus Bonaparte is a knight and Wellington is a knave (as claimed).
Just summarizing.
Write two-column proofs that verify each of the following logical equivalences.
Here’s the last one:
Proof. \[\begin{array}{rll} & {\lnot}(A \land B) \land {\lnot}(A \land C) & \\ && \text{De Morgan's law (times 2)}\\ \cong & ({\lnot}A \lor {\lnot}B) \land ({\lnot}A \lor {\lnot}C) \\ && \text{Distributive law}\\ \cong & {\lnot}A \lor ({\lnot}B \land {\lnot}C) \end{array}\]
Unique existence is essentially saying that there is exactly 1 element of the universe of discourse that makes \(P(x)\) true. The negation of “there is exactly 1” is “there’s either none, or at least 2”. Is that enough of a hint?
\(\forall x \, \exists y \; L(x,y)\).
This is a fairly optimistic statement “For everyone out there, there’s somebody that they are in love with.”
\(\exists x \, \forall y \; L(x, y)\).
This one, on the other hand, says something fairly strange: “There’s someone who has fallen in love with every other human being.” I don’t know, maybe the Dalai Lama? Mother Theresa?… Anyway, do the last two for yourself.
\(\forall x \, \forall y \; L(x, y)\).
\(\exists x \, \exists y \; L(x, y)\).
Here’s a couple of bonus questions. Two of the statements above have different meanings if you just interchange the order that the quantifiers appear in. What do the following mean (in contrast to the ones above)?
\(\exists y \, \forall x \; L(x, y)\).
\(\forall y \, \exists x \; L(x,y)\).
This is asking you to put a couple of things together. The first thing is that in negating a quantified statement, we get a new statement with all the quantified variables occurring in the same order but with \(\forall\)’s and \(\exists\)’s interchanged. The second issue is that the logical statement that appears after all the quantifiers needs to be negated. Since, in this statement we have a conditional, you must remember to negate that properly (its negation is a conjunction). \[\exists \epsilon>0 \, \forall \delta>0 \, \exists x \, (|x-c| < \delta) \land (|f(x)-l| \geq \epsilon).\]
The exceptions are very small prime numbers. You should be able to find them easily.
False.
True.
True.
False
True.
entree \(\longrightarrow\) beverage
\(\exists\) person \(p\) such that \(\forall\) desserts \(d\), \(p\) did not take \(d\). Yes I do. No, I got them right in the first place!}
This is what many people refer to as the transitive rule of implication. As an argument form it’s known as “hypothetical syllogism.”
Look at the lines that start with the word “Either.”
\[ \begin{array}{cl} & W \lor A \\ & {\lnot}W \\ \hline \therefore & A \\ \end{array} \] This is “disjunctive syllogism.”
Let \(C(x)\) be the open sentence “\(x\) has a car” and let \(E(x)\) be the open sentence “x escaped the flooding.” This argument is actually the particular form of universal modus ponens: (See the final question in the next set of exercises.) \[ \begin{array}{cl} & \forall x, C(x) \implies E(x) \\ & C(\mbox{Sandra}) \\ \hline \therefore & E(\mbox{Sandra}) \\ \end{array} \] At this stage in the game it would be perfectly fine to just identify this as modus ponens and not worry about the quantifiers that appear.
Valid form.
Valid form.
This looks like modus tollens. Let \(G\) refer to “guilt” and \(P\) refer to “in prison”
\[\begin{array}{cl} & \forall x, G(x) \implies P(x) \\ & {\lnot}P(\mbox{George}) \\ \hline \therefore & {\lnot}G(\mbox{George}) \\ \end{array}\]
You should note that while the form is valid, there is something terribly wrong with this argument. Is it really true that everyone who is guilty of a crime is in prison?
In the following truth table the propositional variables occupy the first three columns, the argument’s premises are in the next three columns and the conclusion is in the right-most column. The truth values have already been filled-in. You only need to identify the critical rows and verify that the conclusion is true in those rows.
\[\begin{array}{|c|c|c||c|c|c||c|} \hline A & B & C & (A \lor B) \lor C & {\lnot}A & {\lnot}B & C \\ \hline 1 & 1 & 1 & 1 & 0 & 0 & 1 \\ \hline 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ \hline 1 & 0 & 1 & 1 & 0 & 1 & 1 \\ \hline 1 & 0 & 0 & 1 & 0 & 1 & 0 \\ \hline 0 & 1 & 1 & 1 & 1 & 0 & 1 \\ \hline 0 & 1 & 0 & 1 & 1 & 0 & 0 \\ \hline 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ \hline 0 & 0 & 0 & 0 & 1 & 1 & 0 \\ \hline \end{array}\]
All of them except for one are the particular form — number 4 is the exception.
Here’s an analysis of number 5:
All fish live in water. The octopus lives in water. Therefore, the octopus is a fish.
Let \(F(x)\) be the open sentence “\(x\) is a fish” and let \(W(x)\) be the open sentence “\(x\) lives in water.”
Our argument has the form
\[\begin{array}{cl} & \forall x, F(x) \implies W(x) \\ & W(\mbox{the octopus}) \\ \hline \therefore & F(\mbox{the octopus}) \\ \end{array}\]
Clearly something is wrong — a converse error has been made — if everything that lived in water was necessarily a fish the argument would be OK (in fact it would then be the particular form of universal modus ponens). But that is the converse of the major premise given.
Disjunctive addition.
Conjunctive addition.
Constructive dilemma.
Conjunctive simplification.
Note that the conclusion could be re-expressed as the conjunction of the two conditionals that are found in the premises. This is conjunctive addition with a bit of “window dressing.”
The definition for “odd” only involves the oddness of a single integer, but the first line of our proof is a conjunction claiming that \(x\) and \(y\) are both odd. It seems that two conjunctive simplifications, followed by applications of the definition, followed by a conjunctive addition have been used in order to go from the first sentence to the second.
Disjunctive addition.