ASSIGNMENT 1

Comments from the markers (and instructor) on common errors and the
marking scheme used.

The average was 66%.

QUESTION 1

Refer to the 'Solutions to Homework Assignment #1' for the symbols
used.

    Part (a) S & (S -> D)
If the answer is of the form something & something, one mark
for S and two for (S -> D).
    Even though S & D <=> S & (S -> D), that answer (alone) got 2
marks only, since it did not reflect the structure of the
initial statement. However, if one showed or stated that these
were equivalent, then the full 3 marks were given.

S & (D -> S) <=> S & (~S -> ~D) got 2 marks. Lots of people
made this mistake: "whenever" does not mean "then", but rather
means "if". 

   Part (b) W xor H <=> (W V H) & ~(W & H).
The answer W V H got 2 marks. This is kind of close.
The answer W & H got 0 marks.

   Part (c) L & B
Most people did not catch that "even though" = "but" = "and".
Indeed, there was no idea of implication in the statement.
Although "even though" has different connotations from "and", they
represent the same logical connection.

The following answers were very generously awarded 1 mark.
(B V ~B) -> L <=> L
L V ~B & B (this is not even a legal formula, since parentheses are missing!)
B -> L
L -> B

QUESTION 2(a)

A proof only using a truth table got -5.
A proof partially using a truth table got -2.
A proof without justifications (p.10 of text) got -3.
Misnaming the justification got -1 (each, not counting
repetitions unless such a repetition made the the argument truly
horrible).
A 'natural deduction'-style proof got -1:  Proving "<=>"
is very different from proving "=>".

If one said that the formulae were not equivalent, but gave
a "reasonable" explanation, 2 marks were given.

QUESTION 2(b)

The question clearly stated that a proof of non-equivalent was
to be done by providing a counter-example to the equivalence.
People who "overproved" the non-equivalence got 1 mark for
trying. By "overproving", I mean attempting to prove the
non-equivalence by 'getting as close as possible' to showing
equivalence, and then, when stuck, giving up and claiming
'well, this is how far one can get, and the two sides of the
supposed equivalence could simply not work out to match'.
This takes a lot of work (worth 1 mark), but does not prove
anything.  Although your attempted proof did not work out, 
maybe some other proof would.

A wrong counter-example got -3.
One without justification got -2.

If one said that the formulae were equivalent, but gave
a "reasonable" explanation, 2 marks were given.

QUESTION 3:

5 marks for the correct answer,
(there were several answers considered correct 
translations from English)

Marks were taken off depending on how far students' solutions
were from the correct ones. 

QUESTION 4:

Most people understood question 4. Mistakes were made when they
skipped a few steps, like commutativity, etc.

QUESTION 5:

This was not very well done.  People in general don't understand the
difference between predicates and functions. Most people had lines
like 

h(x) /\ t(x),

where h and t are the head and tail functions.  This is meaningless
because h(x) represents an element of the domain, so it doesn't have a
truth value.  Students should review the definitions of terms and
formulae in predicate logic.

Another common mistake was using an "n" constant symbol which
wasn't part of the set of symbols they were given.  So a lot of them
tried to use it to represent the end of the sequence instead of P(1). 

There seems to be some problems translating between predicate logic
and english.  Few people could properly answer 5(d).  Some people
wrote something like 
"Forall x there exists a y such that ...".
This was penalized because the purpose of the question was to
translate the logical formula into plain English.

QUESTION 6:

I.  Not reading the question.
Specifically, 6(a) asked for two things: an answer and a justification.
	If you answered "unsatisfiable", then you needed to prove that
all interpretations make the formula false.  If you answered "valid", then 
you needed to prove the formula true for ANY interpretation. If you
answered "neither", then you needed to provide one example to show that the
formula is satisfiable and one to show that it is not valid. In other
words, INT1 would be an interpretation which makes the formula true, and
INT2 would be an interpretation which makes the formula false.
	Many people gave MORE than the required number of examples. One 
will do.  Providing more than one equivalent example is not
helpful. (EXAMPLE: INT1 over the integers has R(x,y) = "x < y" while
INT2 over the integers has R(x,y) = "x > y". These are equivalent up
to renaming variables.) 

II.  Errors regarding the scope of quantifiers.
	There is a marked difference between:
\forall x \forall y [ R(x,y) -> R(y,x) ] and
\forall x \forall y R(x,y) -> \forall x \forall y R(y,x)
and yet many people wrote things like

Let R(x,y) = "x is a brother of y". Then \forall x \forall y R(x,y) is
false and therefore the implication is true.
	Sure, the implication *is* true (for a domain consisting only 
of males), but not for that reason. It's true because "brother" is a
commutative relationship, like addition, multiplication, "cousin",
"sibling". The correct argument would be:

Let R(x,y) = "x is a brother of y". Let the domain be all male humans.
Certainly, if x is a brother of y, since x and y are both male, y is a
brother of x. Then R(x,y) -> R(y,x) and since x and y are arbitrary
male humans, by universal generalization, we must have that \forall x
\forall y [R(x,y) -> R(y,x)].
	Remember that \forall x \forall y R(x,y) is not true if there
is a single pair (u,v) such that ~R(u,v). Similarly, 
\forall x \forall y ~R(x,y) is not true if there is a single pair
(u,v) such that R(u,v).

III. Incorrect proof of a valid formula.
	The following argument is WRONG: "Let INT1 be an
interpretation consisting of... (some explanation). We can show that
the formula is true under INT1.  (Proof included.) Let INT2 be another
interpretation consisting of... We can show that the formula is true
under INT2.... Since the formula is true under INT1 and INT2, it must
be true under all interpretations; therefore the formula is valid."
	How many interpretations of a given formula exist? An infinite
number. So if you try to check that each one satisfies the formula
separately, you'll never, ever finish.  You must give a proof that
works for all interpretations.

IV. Obvious logic statements were made which are false.

	Here is a part of a typical (incorrect) solution for 6(a):

Let R(x,y) = "x < y". Let the domain be Z. Since for any integer x, there
is another integer y greater than x, it follows that \forall x \forall y
R(x,y) is true. For the same reason, \forall x \forall y R(y,x) is true.
Since true implies true, the implication is true.
        Sometimes a little common sense will help you to check your
answer:  you know that (2 < 3) -> (3 < 2) is false, so you should realize
that \forall x \forall y(R(x,y) -> R(y,x)) is false under this
interpretation.

Marking scheme for #6:

6(a)  3 marks for the correct answer; 3 marks for a correct example showing
that the formula is satisfiable; 3 marks for a correct example showing that
the formula is not valid.

	The correct answer received either 0 or 3. For each example,
if you were close but the details were wrong, you got 2; if you wrote
something which was in the ballpark, you got 1. If you got the answer
wrong, but made decent explanations, you got between 2 and 5,
depending on the quality of the explanation.

6(b) 3 marks for the correct answer; 6 marks for the proof.

	If you got the wrong answer, you got 2 unless your explanation was
extremely good, in which case, you may have gotten up to 4. Your proof
received between 0 and 6 depending on how many flaws it had.

In both cases, you got 0 for writing nothing and 1 for writing next to
nothing. Most of you received 2+2=4 if you wrote something meaningful but
incorrect. You had to really work hard to get less than 4/18 on question 6.