Quiz 2 solutions and notes.

In the following, we use the words NOT, FORALL, EXISTS, INTERSECT, and
UNION in place of the corresponding predicate logic and set theory
symbols, due to the limitations of the ASCII character set.

Problem 1.
	Line 3:
		The previous line was

			NOT FORALL x NOT ( NOT P(x) \/ Q(x) ).

		The comment in brackets says to use one of DeMorgan's
		laws.  One could use either of the following versions
		of one of his laws:

			NOT (p \/ q) <=> NOT p /\ NOT q

			p \/ q <=> NOT (NOT p /\ NOT q)
		
		Using the first version is easier here because it
		gives us fewer double negations to deal with.  In any
		case, with a=NOT P(x), and b=Q(x), applying the law
		gives us one of the following new expressions, inside
		the NOT FORALL x:

			NOT NOT P(x) /\ NOT Q(x)
		
			NOT NOT (NOT NOT P(x) /\ NOT Q(x))

		in either case, the double-negations can be
		immediately removed, giving just

			P(x) /\ NOT Q(X)

		after the NOT FORALL.  Therefore we have just
			
			NOT FORALL x P(x) /\ NOT Q(x)

		in the blank on line 3.  (You could leave in some of
		the double negations, but they have to come out
		sometime before line 5.)

	Line 4:
		The previous line was

			NOT FORALL x P(x) /\ NOT Q(x)

		and the comment in brackets tells you what to do next.
		Just split the forall into two parts.  That is, the
		sub-expression

			FORALL x P(x) /\ NOT Q(x)

		becomes

			(FORALL x P(x)) /\ (FORALL x NOT Q(x)).

		It is very important to leave in the first set of
		parentheses, as these delimit the scope of that first
		FORALL.  The second set are redundant, however.

		It is also very important to leave in the initial NOT,
		which applies to that *entire* subexpression
		corresponding to the initial FORALL.  This must be
		indicated with a new *additional* set of parentheses,
		or else the NOT will only apply to the first FORALL,
		and the meaning will be wrong!

			NOT ((FORALL x P(x)) /\ (FORALL x NOT Q(x)))

	Line 5:
		This line just applies one of DeMorgan's laws, namely
		the one that takes
	
			NOT (a /\ b)
		to
			NOT a \/ NOT b,

		to the result of the previous line.  If you wrote
		anything with "DeMorgan", or if you wrote the rule 

			NOT (P /\ Q) <=> NOT P \/ NOT Q,

		or an equivalent, it was accepted.

	Line 6:

		The previous line was

			NOT (FORALL x P(x)) \/ NOT (FORALL x NOT Q(x)).

		The comment says to use the rule in which a FORALL
		expression is replaced by an EXISTS expression.
		Looking ahead to line 7, we can see that we end up
		with an expression that has a FORALL around the P(x)
		part, and an EXISTS around the Q(x) part.  So in line
		6, we will be changing the second subexpression, the
		one that contains Q(x):

			NOT (FORALL x NOT Q(x)).

		Applying the rule to this part, we get:

			EXISTS x Q(x)

		and plugging this back in to the formula gives

			NOT (FORALL x P(x)) \/ EXISTS x Q(x).

		As an additional check, we can see from line 7 that
		this can be directly transformed into the final
		answer,

			(FORALL x P(x)) -> EXISTS x Q(x)

Problem 2.
	
	Some students were confused by the meaning of the
	parenthetical remark, "You can assume that A and B and U are
	chosen such that all the values in each list are different
	from each other."

	First, having some remark like this was necessary because if
	it was not included at all, then the order of the numeric
	quantities (values) in the two lists "a)" and "b)" would not
	be well-defined, because some of them might be the same.

	For example, if A and B were disjoint, then we would have

		|A INTERSECT B| = |{}|
		|A XOR B| = |A UNION B| = |A| + |B|.

	If A=B, we would have

		|A UNION B| = |A INTERSECT B| = |A|
		|A - B| = |{}|.

	If A=U, we would have

		|A| = |U|.

	The single remark "All the values in each list are different
	from each other" suffices to rule out all three of the above
	cases, which would otherwise have to be ruled out by three
	separate restrictions.

	Some people thought that by "each list," I meant "each set"
	(referring to sets A and B), and that by "values," I was
	referring to the "elements" or "members" of those sets.

	However, I will not consider this to be a valid interpretation
	of the question, for the following reasons:

		1.  "List" is not another word for "set".  "Set" is
			the very specific type of discrete structure
			that we have been studying, and we never
			introduced "list" as an interchangable term
			for "set".

		2. I used the word "list" earlier in the paragraph
			when I said "the following lists of
			quantities", referring to list a) and list b).
			I intentionally used the word "list" again in
			the parenthetical remark in order to make the
			connection with the earlier sentence.

		3. If the remark had meant "All the elements in sets A
			and B are different from each other," that
			would have been partly redundant, because
			within any single set (A or B), all of the
			elements are already different from each
			other, by the definition of a set as
			containing no repetitions.

		4. If I had meant that A and B had no elements in
			common, I would have just said that, or "You
			can assume that sets A and B are disjoint."

		5. If A and B were disjoint, it would have been
			impossible to write all the given quantities
			in order of increasing size, since many of
			then would have actually been equal.  So the
			question would have been impossible to answer.
			This should have been a clue that you were
			misinterpreting the problem.

		6. From the grading, it seems that the great majority
			of students did interpret the problem
			correctly.

	Also, some people were confused by the expression |A|+|B|,
	thinking that "+" was some set operation not previously
	defined.  However, the arguments to that expression were the
	cardinalities, |A| and |B|.  The problem statement specified
	that A and B are finite sets, and you should know that the
	cardinality of any finite set is just an ordinary integer.
	Therefore, |A|+|B| just denotes the sum of two numbers.

	The (one and only) correct solution to problem 2 was:

		a) |{}|, |A INTERSECT B|, |A|, |A UNION B|, |U|.
		b) |{}|, |A - B|, |A XOR B|, |A UNION B|, |A|+|B|.

	although partial credit was given for partially correct
	answers.