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 formula-calculation" 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 "truth-table 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. 48-50: 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 55-minute test. It could be a possible problem on a 3-hour 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. 17-20.