
Assignment 1  solutions, comments, marking scheme
In the following problems, give all relevant detail. Convince the
grader, by what you write, that you know what all the words in the
problem mean, and that you have noticed what you should have noticed.
Make sure also that you answer all flaming questions, with
civilized answers like "Yes" or "No".
Note to students: Much of what is below is actual instructions
from me to the grader.
Notes to the grader:
Please grade only problems 1, 4, and 5. (Solutions to 2 and 3
are shown below as well.) Maximum possible marks: 20 total.
1. Is p > (¬q \/ (p > q)) a tautology?
7 marks
Yes.
One explanation: Give the full truth table, columns for p, q
from left to right, and pairs of truth values for p,q listed
lexicographically from top to bottom. Thus:
p q p > (\not q \/ (p > q))

f f t t t t
f t t f t t
t f t t t f
t t t f t t
all t's,
in this
column
Actually one only has to look at rows 3 and 4 of the table,
since p has value f in rows 1, 2 and the conditional
p > (stuff) is automatically t then, regardless of the
value of (stuff). So, if the student just leaves out six
or eight values in rows 1, 2 above but explains in perfect
English why it is ok to ignore those rows, she should not
lose any marks for doing that. Other combinations of GOOD
English explanation with partial filling out of the truth
table, or just a full, clear, perfect English explanation
of why our conditional has value t in all four rows should
get full marks as well.
Deduct 1 mark if truth values are not lined up properly
under the right connective.
Deduct 2 marks if nothing is written in addition to the
truth table to indicate why the answer is "Yes". The
students were warned about this.
Deduct 3 marks if columns for p and q are absent!
Decide on a deduction and record for me your decision
(somewhere) if the student does everything that must be
done to show that the given wff is a tautology but does
not say "Yes" somewhere or "It is a tautology" somewhere.
I said in the instructions to the assignment that civilized
answers must be given.
Give 4 out of 7 if the p, q columns above are reversed
(i.e. first column labelled q, second p), and there are four
t's listed under the first arrow and truth values shown
under the other four connectives as well, at least as shown
in the truth table above. Do not use up
your time trying to check the other truth values. The students
were told repeatedly to list the variables alphabetically from
left to right.
Also give 4 out of 7
if p, q are listed alphabetically at the left but the pairs
of truth values are NOT listed "lexicographically" as above,
AND there are four t's under the main connective above (first
arrow), and lists of values that are as complete as the
columns shown above are given under the other
connectives as well. Do not use up time checking the other truth
values in detail. The students were also warned repeatedly about
this.
Give 5 out of 7
if everything is done as above except there
is no clear INDICATION written down (an arrow pointing to the
relevant column, the relevant column circled, or a remark like
the one typed above) that the student knows that what is
important is that the first arrow has all t's under it.
Deduct 1.5 marks for each connective
(other than the main
connective) in the solution that does not have enough truth
values written under it. (The students were also warned
about this.) Thus, JUST putting t's under the main connective
gets a score of 1 out of 7.
Do not spend forever checking entries in the truth table,
but generally deduct 1 mark for each wrong entry, as long as
it is easy to spot mistakes. Do not mark, as wrong, entries
that would be right, if the entries on which they depend
were not wrong.... Once you get to 4 or more errors, stop
counting and give 0 for the problem.
For a totally correct truth table as above,
and the answer "No", with or without
indication of the column of t's, give 0/7.
For a totally correct truth table and no "Yes" or "No",
give 4/7. The assignment paper says to give civilized
answers to the flaming questions.
Deduct no marks if someone uses T, F instead of
t, f. I told the students that this is ok FOR THIS
ASSIGNMENT ONLY.
Alternate explanation:
As I said above, and as I told folks in class,
it is also possible to give an English explanation of why
the given bool. exp. is never f, without any truth table.
Something like this:
For the given b.e. (expression, formula, wff, whatever)
to be f, the consequent must be f. But then
q must be BOTH t and f. This can't be. //
2. Does p > q tautologically imply (p /\ q) \/ ¬p ?
Yes. One explanation is a full truth table. Another is to note
that if the second expression here is f, then p must be t and
q must be f. But then the first expression above is f. So
whenever the first one is t, so is the second.
3. Are (p \/ q) \/ r and p \/ (q \/ r)
tautologically equivalent?
(In other words, do the parentheses "make
a difference"? But don't answer this second question,
in these here parentheses! Just think about it.)
Yes, they are taut. equiv. Easiest "explanation avoiding
English" is a full truth table. Each expression is t
precisely when at least one of p, q, r is t. So each is
t precisely on lines 2  8 of the truth table, when the
variables are listed alphabetically from left to right and the
triples of truth values are listed lexicographically.
Here, the connectives are all the same (disjunction), and the
parentheses do not "make a difference". This instance of (5) on
p. 37 of our text is of course a tautology; we remarked in class that
every instance of every axiom scheme on that page is a tautology.
4. Are (p > q) > r and p > (q > r)
tautologically equivalent?
(In other words, do the parentheses
"make a difference"?
Again, don't answer this question
in ( )'s; just think about it.)
7 marks for this too.
Grader:
Please make up a marking scheme similar in spirit to the
one for problem 1 above.
Answer: No.
Here I said explicitly in the instructions to this assignment
that I wanted the entire truth table in full detail for this
problem. That means 32 truth values, eight under each arrow.
IF I had not included this instruction, all a student
would have to do here, to explain the answer "No", would
be to give at least ONE triple of truth values for p, q, r,
for which the two wffs above have different truth values.
So giving row 1 or row 3 below, alone, would be enough.
Below is part of the
"joint truth table" for the two exprs. above.
p q r (p > q) > r p > (q > r)
f f f t f t t
f f t t t t t
f t f t f t f
f t t t t t t
t f f f t t t
t f t f t t t
t t f t f f f
t t t t t t t
(1) (2)
Columns 1, 2 differ in rows 1 and 3.
Mentioning either one of these rows is enough for
justification of the "No".
Moral: Here the grouping by parentheses does
make a difference. In general, if one has two DIFFERENT
boolean binary connectives, in such an expression,
the grouping by parentheses "makes a big difference"
semantically (at least, one should expect that it does).
It also makes a difference if both connectives are arrows.
Nevertheless, despite this example, MANY of you will
"prove" theorems by happily moving parentheses around
in situations like this. This will be a
horrible, bonehead error
(also known as a "fatal error" in our text)
every time it is done, and will lose TONS of marks.
I.e., I predict that MANY of you will do the boolean
analogue of the following:
(2 + 3) * 5 = 2 + (3 * 5), i.e.,
you will tell me that 25 = 17.
You will get desperate on a test and tell me that
2 + 3 * 5 = 2 + 3 * 5
(note the spacing above),
or that
p /\ q > r and p /\ q > r
(for instance) are syntactically equivalent (we will
use blank space a lot in lieu of parentheses),
which is the same as telling me that 25 = 17.
Does it feel silly claiming that 25 is 17? I hope so.
It should feel equally silly claiming something like
the above, about the syntactic equivalence.
An error like this immediately ruins a proof.
Tourlakis and I call it a
"fatal error";
graders will be instructed to
stop looking
at a proof when they come to a fatal error in it, and
give 0 marks
for any work done after the fatal error.
(In fact, the only times you should expect that moving
parentheses around in such a string of three fellows is
"harmless" are when the binary connectives are all ==,
or are all \/, or are all /\.)
5.
I claim that there is an infinite sequence of wffs
P , P , P , ... , P , ... , P , P , ... ,
1 2 3 17 n n+1
that are all tautologies,
in which
the only symbols which appear are: the boolean
variable q and ( and ) and the connective >,
and such that
the complexity of P is strictly greater than
n+1
the complexity of P , for all positive integers n.
n
Show that my claim is correct, by writing down an inductive definition
of such a sequence. (So you will have to write down who P is, and
1
what P is in terms of P .
n+1 n
6 marks.
I warned the students explicitly in the instructions at the end of
Problem 5 that I want absolute precision with brackets (also known as
parentheses) in their answers to Problem 5. No use of blank space to
indicate bracketing, no dropping of "overcoats" (my name for outermost
parentheses). Indeed, an inductive definition lacking overcoats is
doomed to being wrong.
There are MANY correct answers. Here are some:
(1) P is (q > q) , and
1
P is (q > P ) for all pos. integers n.
n+1 n
(2) P is (q > q), and
1
P is (P > P ) for all pos. integers n.
n+1 n 1
Any tautology like the P above, and letting
1
P be a conditional with ANY tautology as its
n+1
consequent (the "then" part of the "if, then"), and
P appearing in it as a "subwff" (so what the complexity
n
definitely increases), will work.
Grader: Deduct 2 marks for each error with parentheses.
If P or P is missing an "overcoat", count each as an
1 n+1
error, and deduct 4 marks accordingly. If there are extra parentheses
which should not be present in any string, deduct 2 marks for that
error. In general the grading of this last problem should be pretty
strict.
