Well, let's see. Many things to say. One thing to note is that about 20 of the 145 people on the class list did not even show up for the test.... Another is that attendance the class after the test was about 70 (of an official 145 on the class list. Very strange. Certainly is a different generation from mine, or something. Something is very different.) Another is that Whiteley thought my test was harder than his. But I looked at his and thought his was harder.... The point is, that since neither of us knows how the other's class was prepared, knows what the other's class was told to expect, knows what facts were mentioned to the other's class, neither of us is in a position to judge whose test was harder. Only a person who attended all classes in both sections can say. Did any of you attend all of my classes and all of his? :-)


MARKS(total 50):  1: 3    2: 4+3    3: 3     4: 12
5: 10   6: 4+4    7: 3     8: 4 
1. Briefly state the completeness theorem for SD+ .

In English: If \Gamma entails \zeta, then \zeta is SD+ -derivable from \Gamma.

In symbols: If \Gamma |= \omicron, then \Gamma |-- \omicron ( with an "SD+" written under the |-- ).
Either form of answer gets full marks.

2. (a) Suppose \alpha and \beta are given wff's. Using facts from class, carefully prove this:
If \alpha & \beta is a tautology , then \beta is SD+ -derivable from the empty set.

Comment: Note that you are TOLD what to do. Much faster to do such a problem than one that says "True or false? If true, explain. If false, etc."

Method 1: Suppose \alpha & \beta is a tautology. Then the empty set entails it, by defn. of entailment and of tautology. So it is SD+ -derivable from the empty set, by completeness of SD+. But then one &ER gives \beta. //

Method 2: Same first sentence. Then \beta is a tautology, by defn. of conjunction and of tautology. So the empty set entails \beta, as in Method 1. So \beta is SD+ -derivable from that set by completeness of SD+. //

(b) Show that { A -> (B -> C) } does not entail (A -> B) -> C.

First some comments: (Note that I am giving about 30 lines of comments here. The actual answer to the problem is only one line. If you wrote the right one line, you of course got full marks.) This was intended to be a problem almost everyone would get, and would get QUICKLY. Of course, this assumes some common sense on the student's part. Lookie, folks: You have 55 minutes for the whole test. Are you REALLY going to spend the time it takes to write down two whole truth tables each with eight lines, each line having five T's and/or F's in it??? When you have not been ASKED to do that, and when there is no REASON to do it? Oh, my.... If you do much of that sort of thing, then OF COURSE the test will seem too long.... (Whiteley calls this a "low-level response".)

More comments: Note that this question (like the previous one) is much easier as it stands than it would have been had I said, "Decide whether blah entails blah, and then prove it." You are actually TOLD what is to be shown; this speeds things up a LOT. ... I mentioned in class, and wrote on the board, that one of these wff's entailed the other, but that they are not logically equivalent. And I said you might want to look into that. Now, this did not mean that you SHOULD have looked into it, but it does mean that the whole situation should not be a surprise to you. I THOUGHT of giving you both wff's and asking you to show that one of them did not entail the other, but decided I wanted a QUICK question, so decided to TELL you which wff does not entail which. If you REALLY know the definition of entailment, and of conditional, this is VERY fast and easy. I guess it should take about two minutes (total) for you to read the problem, realize what has to be done, and write it down. Maybe three.

The Showing: The t.v.a. (F,F,F) satisfies the first given conditional but not the second. //

( More comments: We seek a t.v.a. that will make the second conditional false. This means C must be false (which gets rid of half of the eight t.v.a.'s already) and A -> B must be true. Also we want A -> (B -> C) to be true on this t.v.a. Well, shucks, folks. Making A false will make both these conditionals true, no? So (F,T,F) and (F,F,F) are both t.v.a.'s that satisfy the first given wff but not the second.)

3. The following statement is FALSE. Give a specific counterexample.
If { \alpha } is SD-consistent, then { \alpha , \beta } is consistent.

Comments: First: Intended to be *easy*, again.... Roughly speaking, the statement says that no matter how bad \beta is, if \alpha is "nice" then \alpha, \beta together will form a "nice" set. No way. Second: I thought of asking people to explain their counterexample. I did not do that. I KNEW that if I asked for explanation, hardly anyone would get full marks, and I wanted a question almost anyone could get full marks on.

Counterexample: Let \alpha be A and \beta be ¬A. //

Finished. I asked for no explanation, so by now the wise student has just gone on to the next test question.

(Here is an explanation: The set consisting of \alpha and \beta is obviously not satisfiable. Now if { A } were not SD-consistent, then in the language of Whiteley and our text, it would be not not SD-inconsistent, i.e., it would be SD-inconsistent. So it would be possible to SD-derive \delta and ¬ \delta from A, for some sentence \delta. But then { A } would entail both these sentences, by soundness.
Then every t.v.a. to the atoms appearing in \delta, together with the atom A,
making A true and assigning arbitrary truth values to the other atoms of \delta,
makes both \delta and its negation true. Not possible. So { A } is SD-consistent.)

4. Give an SD-derivation to show that the argument whose set of premises is
{ A v B , ¬ B } , and whose conclusion is A , is valid.

Comments: One should almost immediately think of a proof by cases ("or-elimination"). One disjunct of the premise A v B immediately gives the desired conclusion. And the other, together with the second premise, gives a pair of contradictory sentences, whence we kin git ennything we wants, including A. It should take less than 1.5 minutes to see all this, and one should already have in mind the entire proof, confident that it will work.

The derivation is essentially on p. 211 of the text (Figure 5.34). One replaces i-r by 1-10 for line numbers, supplies PREM as justification in the first two lines, replaces \alpha by A and \beta by B in line i, and \alpha by B and \beta by A in lines j-r. One also gives the two-line subderivation before the five-line one. And one alters references to line numbers in the justification field as necessary. The structure is unchanged: a proof by cases with one branch being trivial and the other being the shortest possible proof by contradiction ("not-elimination"). After all the proofs by cases and proofs by contradiction we did in class and on assignments (and all the drills you were supposed to have been doing in Symlog ), this problem should have been easy, and fast.

5. Give an SD+ -derivation of the wff (A & B) -> (P \bicond ¬ A) , from the set of premises { ¬(C v ¬ D) , (E v D) -> ¬ (A & B) } .

Comments: Of course, the first thing one does when asked to do any SD- or SD+-derivation is to ask oneself if one believes that there is a derivation, i.e. (by soundness and completeness), that there is entailment. Well, sticking out like A Sore Thumb , here, is the atom P in the conclusion, absent from all the premises. And given any t.v.a. satisfying both premises, (P \bicond ¬ A) will be false sometimes, namely, when we choose a truth value for P that is the same as the assigned truth value for A....
So if the derivation is to be doable, then any t.v.a. that satisfies both premises must make A & B false. But now we see that any such t.v.a. will indeed make D true by De Morgan and double negation, hence will make A & B false, since it satisfies the second conditional too. So we see the derivation all at once. (At least, I do....) In fact, probably there are several derivations all around a dozen lines long, since there is a shorter one below, and SD+ is such a rich system.

The T.A. who is helping me grade our test tells me that
several people in the class gave SD+ derivations here that are 15, or even 22, lines long. This is not good. When there is a 9-line derivation, you lose a LOT of time building much longer ones. Again, no wonder people who do such things think the test is too long....

One derivation:


PREM          1    ¬(C v ¬D)
PREM          2    (E v D) -> ¬(A & B)
DM 1          3    ¬C & ¬¬D
&ER 3         4    ¬¬D
DN 4          5    D
vIL 5         6    E v D
->E 2,6       7    ¬(A & B)
vIR 7         8    ¬(A & B) v (P \bicond ¬ A)
IM 8          9    (A & B) -> (P \bicond ¬ A)


6. Let \alpha, \beta be given wff's, in both part (a) and part (b).
True or false? (In both (a) and (b):
If you claim the statement is true, explain carefully.
If you claim it is false, give a specific counterexample.):

(a) If the set { \alpha , \beta } is INCONSISTENT, then ¬(\alpha & \beta) is SD+-derivable from the empty set.

(Comments: easy. There are various correct explanations. One of the shortest is below.)

True. Suppose the set is inconsistent. Then there is no t.v.a. making both \alpha and \beta true. So there is none making \alpha & \beta true. So every t.v.a. makes the negation of this sentence true. So the empty set entails the negation. So the negation is SD+-derivable from the empty set by completeness of SD+.

(b) If (\alpha -> \beta) is SD-derivable from the empty set, then
¬ \alpha is SD-derivable from the empty set,
or \beta is SD-derivable from the empty set.

Comments: Intended to be something that would trap people who are fooled by superficial appearances and who sometimes do not think about such appearances.

Answer: False. Let \alpha and \beta both be G. Then G -> G is a tautology, hence is entailed by the empty set, hence is SD-derivable from it by completeness. But G is not SD-derivable from the empty set, for if it were, it would be entailed by the empty set (by soundness), hence would be a tautology. But it is contingent. The same argument shows that the contingent sentence ¬G is not derivable.

7. Suppose we remove ONE of the 16 rules from the derivation system SD to get a new system. Call the new system SD# . Is SD# sound? Explain carefully.
(You get no marks for an answer without an explanation.)

Answer: Yes. Suppose we have an SD# derivation of a wff from a set. Then it is automatically an SD derivation -- one that just avoids using the jettisoned rule. So by soundness of SD, the set entails the wff. //

8. Let \Gamma be an SL set.
We saw in class that if there is some wff that it is IMPOSSIBLE to SD-derive from \Gamma,
then \Gamma is SD-consistent.

What if it is only ARBITRARILY HARD'' to derive wff's from \Gamma ?
More precisely:

What can you say about \Gamma if the following condition holds?:

Given ANY positive integer n, there is some wff \alpha_n
that cannot be derived from \Gamma in fewer than n lines.

Is \Gamma SD-consistent? Explain briefly.

Comments: Last problem on test. Intended to be tough. I expected that maybe no one would get it; hoped a few would. It was possible to do all the problems up to this one perfectly (none of them were hard) and get a 92% on the test, which is an A+. Note that you are not told whether even a single wff cannot be derived from \Gamma! There might be such a wff; there might not.

The idea is this: If \Gamma is SD-inconsistent, then not only can every wff be derived from \Gamma, but every wff can be derived in a certain set number of lines. For, we know we can derive some wff \delta and its negation from \Gamma. Suppose this takes m lines. Then tacking on a negation elimination of 4 lines to this derivation gives a proof of any wff \alpha you want. So ALL wff's can be derived from \Gamma in m+4 lines. Taking n to be m+17, we see that \Gamma would then not satisfy the condition stated in the problem. So, \Gamma is indeed SD-consistent.