
The exercises on pp. 48  50
A lot of them are too easy, and/or not very interesting,
and are problems of a sort which I would not likely ask
on test or exam.
Problems 1, 2 are ok but too easy.
Ignore problem 3 (boring and too easy).
Perhaps it is smart to do problem 6 before problem 5. In fact,
one should show more than we are asked to show in problem 6: Show, in
fact, that if A is a wff then (A) is NEVER a wff.
If you do 4 or 5, do it by induction  I don't like this
"analysis of formulacalculation" approach to such proofs.
Exer. 7 is too easy.
Exer. 8 should be straightforward.
Everyone should be able to identify VERY quickly which of the
wffs (wff schemes) in exer. 10 are tautologies and which not. For
instance, A \/ B > A /\ B is NOT a tautology.
Acc. to GT, and I agree with him, to show this we must provide
an *instance* of this scheme which is not a tautology. Well, here
is one: p \/ q > p /\ q is not a tautology (Proof: Let
v(q) = t and v(every other boolean variable) be f. v extends to
a state mapping WFF to {t, f}, and its value at the above
conditional is f.)
I retyped the rest of this file, below, on 28 Jan.,
or typed new stuff, or both.
Last week, I claimed that exercises 11  14 are all easy
as well. I had another look at them and decided that maybe they are
not SO easy. So I type something about them below.
Unfortunately, I don't know what GT means by a "truthtable
shortcut"  I could not locate a discussion of this notion in
the book. I think he means a combination of English reasoning with
examination of the lines of the truth table which the English
discussion indicates as being crucial lines.
Here are some quick indications of solutions to some of the exercises
on pp. 4850:
Exer. 10, first bullet:
I asked myself, "Self, is there a wff A s.t. this wff is f
in some state, for some wff B?"
Well, I replied, if so, then A would have to be f in some state
v and v( ((A > B) > A) ) also = t  that's the only way
the conditional in this first bullet can be f.
But then v(A > B) would also have to be f. But that cannot be,
if v(A) is f. So this first wff in exer. 10 is a tautology,
regardless of who the wffs A and B are.
One can pretty easily argue that the second, fourth and sixth wffs
in exer. 10 are tautologies, regardless of who A and B and C are.
Perhaps there isn't a shorter way for the sixth one than to
check out all eight possibilities for combinations of possible
values for A, B, C under a state v.
I would type the second wff in exer. 10 as
A /\ B > A \/ B to stress that the main connective
is >. (For GT, it has lowest priority, so is applied
LAST.) Or I would use parentheses. And I expect you folks to
use lots of space, as above, or parentheses, too. GT regards >
as having lower priority/precedence than /\ and \/, so he means
the above by what is in the book. One easily checks that this wff
is a tautology no matter who A and B are, but that the third wff
in exer. 10 is not: Take for instance A to be top and B to be
bottom. Then that third wff has value f under ANY state v. (Or,
take A arbitrary and take B to be &neg; A.) I would type the
third wff as
A \/ B > A /\ B. Again, lots and lots of space around
the arrow.
The fourth wff is what all logic books call "contrapositive"  or,
rather, it is a wff which is a tautology, and whose tautologicality
reflects the fact that A > B and &neg;B > &neg; A are
semantically equivalent (another way I like, of saying tautologically
equivalent). An analysis of all four possibilities for values t, f
for A, B shows that this fourth wff has value t in any state v, no
matter who the wffs A, B are.
To see that the fifth wff is not always a tautology, recall that, as
we saw in class,
v( P ==(Q == R) ) = f iff an ODD number of P, Q, R have value f
under the state v.
So for such a "double biconditional" to have value f, it's enough
if all three of P, Q, R have value f under the state v.
So: Take A to be bottom, in the fifth wff in exercise 10.
Then all three conjunctions in that wff have value f in ANY
state v. So the wff as a whole has value f in any state v.
(Check that.)
By the way, I cheated a bit in exercise 10. I have seen the last
two wffs in it before. I happen to know that the sixth wff in it is
a tautology for any A,B,C, and that the fifth is not, because I have
encountered these wffs before and just remember those facts. (But
then I still had to come up with the arguments above. :))
Proof for exercise 13:
The only way v(A > B) can be f for a given state v is for
v(A) to be t and v(B) to be f. So we must show:
If v is a state such that v(C) = t and
(**) v(A > (B == C)) = t,
then the above cannot happen. One way to show that is to assume
that all of the above things DO happen and arrive at a logical
contradiction. So:
Assume that. Then from v(A) = t and (**), we have that
v(B == C) = t. But then, since v(C) = t, we also have that
v(B) = t. But v(B) = f. Contradiction.
This proves the given tautological implication.
I might not give such a problem on a test because I would not want
the nightmare of grading it or asking someone else to grade it. I
know that almost no one in North America under the age of 40 can
write decent English, and would not want to subject a grader to
tons of dreadful English. ...
Consider exercise 14:
The second given set is not satisfiable, no matter who A,B,C are.
Proof: If a state v satisfied that set, then v(B) and v(C) would both
necessarily be f. So for the two disjunctions to have value t under
v, v(A) would have to be t and v(&neg;A) would also have to be t.
Good luck finding such a state v. //
The first set is also not satisfiable, no matter who A and B are.
I leave the proof to you.
The third set may be satisfiable and may not, depending on who
A,B,C are. If C is top and either A or B is also top, one sees
easily that EVERY state satisfies the given set.
If A and B are unsatisfiable (i.e., contradictions) then NO state v
satisfies the given set. (E.g., if A and B are both bottom.) Or
if C is a contradiction and A is a tautology, then the second wff
shown in the set is unsatisfiable, so the whole set is unsatisfiable.
Exercise 15:
Tourlakis states, right after definining substitution [p:= D]
recursively, that is has the highest priority in an expression, i.e.,
it is the strongest magnet. Thus, when he writes
A * B [p:=C], the substitution wins the "me first" fight with the
connective *, where * is any of /\, \/, > or ==. So the
substitution is done in B first to get some wff Q, and then the
final result above is A * Q. If we want the * to happen first,
i.e., if we want the substitution to happen in the whole wff
A * B, then we must indicate that by putting the overcoat on A * B:
(A * B) [p:=C]. Without the parentheses here, the wff six lines
above is
(A * B [p:=C]). The substitution takes precedence.
I will always make clear by the way I write such things exactly
what subwff of a given wff each substitution applies to.
Note, by the way, that using lots of space three lines up from here
is clear, whereas it would actually be WRONG to put parentheses
around B: B is a wff. (B) isn't!
The first wff in exer. 15 is thus p \/ (q > r). (I sloppily
omit the outer overcoat, as GT also did.)
The stuff to the right of the second "bullet" is just nonsense.
Third bullet: (top \/ q)
Fourth bullet: p \/ q /\ r[q:=A] is p \/ (q /\ r), because
the substitution takes place first, in r, and q does not occur in
the wff r. (For GT, /\ "beats" \/, so when he writes his fourth
bullet, he means
(p \/ (q /\ r[q:=A])) (I carefully put all coats).)
Fifth bullet: p \/ (A /\ r)
Exer. 16 takes work. Induction on complexity, plus noting
that bottom is taut. equivalent to (&neg;(p \/ &neg;p)).
etc. etc. It's a nice exercise, but it would take FAR too long
to answer on a 55minute test. It could be a possible problem
on a 3hour exam. But I think I would not give it because the
induction on complexity is sort of tiresome, not fun to grade.
Similar comments for exers. 1720.
