See the appropriate class handout. Enough copies were made for everyone, and brought to class.
See (a).
(think of it as a step in some ``full-dress'' proof):
(If I were writing this test, I would probably give the
sentences here
names, out of laziness. -- R.G.)
Call the first sentence below A and the second one B.
 | ||
| = |  | |
 | ||
in the attached list; any proof that uses (3.46) gets 0 marks.
(3.43)(a)
is a theorem.
Well, this is very close in the theorem list to where conjunction is first introduced. So most obvious, it seems to me, is to use the Rule of Gold.
Call the "left-hand side" of the given equivalence A. (In the following, my equal signs are not in the left margin, lined up with the angle brackets, because that was too hard to manage with LaTeX and html. -- R.G.)
A =
< (3.35),>
=< (3.25), (3.26) >
=< (3.3),>
=< ``redundant true'' >p . //
A very short, straightforward proof.
Comments:
An even shorter proof is to jump straight from the third line above to the last line via (3.2) with a Substitution. There are actually many proofs of (3.43)(a), but the shortest all seem to use Golden Rule and either (3.2) or (3.3) ( (3.3) above was hidden in "redundant true", as well as used just before it). One can start with the whole sentence and rewrite it using (3.35), instead of just the first "half" above, as I did. One person avoided (3.26) altogether and instead used (3.32) early on; this resulted in a cute, albeit weird and tricky, proof.
People were warned right on the sheet handed out with Assignment 1 printed on it that all proofs in the style of the textbook (e.g., "bullet" proofs) were to feature "equal signs" in the left margin, sentences indented between those, and reasons in angle brackets indented yet more to the right of the equal signs. Many of you did not follow this format at all; I deducted fractions of marks for missing equal signs, misplaced reasons, etc. If I print up a nice, clear warning and then do nothing when people flout it, I appear a fool.
In general, if you "solve" a problem perfectly, then add some remarks to your answer consisting of false statements, I will deduct marks. Students must be discouraged from inserting superfluous remarks in their answers along the lines of "Oh, and also, two plus two is five". Several of you, for instance, in problem 3, gratuitously told me that various sentences are THEOREMS, when they obviously were NOT. Some wrote "turnstiles" to the left of some sentences in the proof. Once one reaches a recognizable theorem at the end of such a proof, with equal signs down the left margin, it follows by Transitivity and Equanimity that all lines in the proof were theorems. But one reads such a proof from top to bottom; it is anachronistic to put turnstiles to the left of each such line before the reader has reached the end of the proof.
in the attached list. (One way is to rewrite the implications in the ``left-hand side''
as disjunctions, then `` factor out an r '' , and proceed from there.)
(3.78) 
is a theorem.
Remark:
Of the four ways to rewrite implications given in 3.57-3.61, only one
is a disjunction (one other is an implication, two others are
equivalences). So the student has been told which theorem to use first!
The remark in parentheses above TELLS the student how to do the
whole proof. Free points.
=
< (3.59) twice >
=
< (3.24) twice, then (3.46) with p:=r ,,
; then (3.24) again to get the ``r'' on the right >
=
< (3.47)(b) >
=
< (3.59) again >
. //
is true or false. If you say a statement is true, give a proof of it. If you say
a statement is false, give a counterexample to it.
is a theorem,
then either
is a theorem or 
is a theorem.
Of course, one should think semantically here either right from the
beginning or after a short look to see whether a syntactic proof will
work. What is syntactically obvious here,
within seven seconds of looking at the problem,
is that the ``if'' part is true if and only if,
by De Morgan,
is a theorem. So the question is, whether THAT implies the
``then'' part. So it boils down to this: If 
is a tautology,
does it follow that P is a tautology or Q is a tautology? And the
answer is, clearly, ``No''. The simplest example of this is Excluded
Middle (axiom (3.28)) itself. So we are quickly led to a very simple
counterexample.
Answer:
False. Let A be p , and B be 
.
We check that 
is then never true, hence its negation is a
tautology, hence by completeness a theorem. But neither nor
is a tautology (each one is false for ``half'' of all
possible states).
The above half line following "Answer:" is all that had to be written. The problem did not ask you to explain your counterexample. The very first sentence in the test said to read the instructions for each question carefully. (It is understood that one should also follow them carefully.) So, we say ``False'' since we have decided the statement is false, and then we write down our counterexample. (Of course, we think a bit before, and maybe also after, writing down the counterexample.)
Then, aware that 55 minutes is a very short time, we go on to the next question, and do not spend time explaining our counterexample.
is a
theorem,then B is a theorem.
Well, either one thinks syntactically and remembers Modus Ponens
(3.77) from Assignment 2, and sees how most of the proof should go, or
one thinks semantically and says to oneself, ``Self, If A is always
true and is always true, then by the standard truth
table definition of implication, whenever A is true (i.e., always),
B is true. So B is a tautology.'' So one quickly decides that the
given English ``if, then'' sentence is true, and then, since test
preparation sheets and class discussions have warned one that one is
not allowed to use completeness on this test to prove theoremhood, one
writes down a ``syntactic'' proof of the ``if, then'' statement. The
proof is just like the proofs of at least three derived
inference rules on the web page, and also just like proofs of at least
five more statements just like this one, given in class. So one writes
something like this:
True. Suppose A and are theorems.
Substitution in theorem (3.77) gives that
is a theorem. But by a result used countless times in class, then
is a theorem. Substn. in (3.38) and Leibniz then give that
is a theorem. But then Substn. in (3.73) and derived Leibniz with E being r give that
is a theorem. So by Equanimity, B is a theorem. //
you must explain, to get marks. A correct yes/no answer with a bad explanation
gets nothing. If you circle ``maybe'', you need not explain.
Our system of propositional logic E
has exactly 16 axioms and exactly four rules
of inference. We know that E is
both sound and complete, with respect to
the standard (``truth tables'') interpretation.
Suppose we remove one of the 16 axioms from the list, and call the new system E' . Is the new system E' sound?
Yes. No. Maybe. (It depends on which axiom is removed.)
Well, I circle ``Yes.'' Then I write something like this:
Suppose that P is a theorem in E' . Then by definition of theorem, there is a proof of P starting from the axioms of E' , using the inference rules of E' , i.e., the inference rules of E . But that proof is then a proof of P starting from the axioms of E, as well! (It just happens to be a proof that never uses the removed axiom. But most proofs we have encountered do not use anything like all 16 axioms....) So P is also a theorem in E . So it is a tautology, by our Soundness Theorem.
We have shown that any theorem of E' is a tautology. So E' is sound. //
It was also possible just to write something quite brief here, like:
If P is a theorem in the new system, then a proof of it in the new system is automatically a proof of it in our original system (a proof that avoids using a certain axiom). So it is a theorem in our original system, hence a tautology, by Soundness of our original system.
We have shown that any theorem of E' is a tautology. So E' is sound. //