From owner-cse191-sp08-list@LISTSERV.BUFFALO.EDU  Mon Feb  4 10:12:56 2008
Date:         Mon, 4 Feb 2008 10:12:09 -0500
From: "William J. Rapaport" <rapaport@cse.Buffalo.EDU>
Subject: 191: Distribution of quantifiers over ^,v
To: CSE191-SP08-LIST@LISTSERV.BUFFALO.EDU

------------------------------------------------------------------------
Subject: 191: Distribution of quantifiers over ^,v
------------------------------------------------------------------------

Notes:  

Below, "A" & "E" are used for the universal & existential quantifiers,
respectively.

"equiv" is used for the triple-bar
	
"!equiv" is used for the **negation** of the triple-bar; 
i.e., "P !equiv Q" means:  P is not equivalent to Q  (If I were writing
this in a different medium, I'd use the triple bar with a slash through
it.)

"LHS" refers to the left-hand side of an equivlence;
"RHS" refers to the right-hand side.

------------------------------------------------------------------------

Theorem:	
	(a)  Ax[P(x) ^ Q(x)] equiv (AxP(x) ^ AxQ(x))

	(b)  Ax[P(x) v Q(x)] !equiv (AxP(x) V AxQ(x))

	(c)  Ex[P(x) ^ Q(x)] !equiv (ExP(x) ^ ExQ(x))	

	(d)  Ex[P(x) v Q(x)] equiv (ExP(x) v ExQ(x))
	
------------------------------------------------------------------------
proof:	(a) see Rosen, p. 39

	(b) counterexample:	Let domain = Z
				Let P(x) = x is even
				Let Q(x) = x is odd

		Then:  LHS is T, but RHS is F

	(c) counterexample:	Let domain = Z
				Let P(x) = x is even
				Let Q(x) = x is odd
				
		Then:  LHS is F, but RHS is T

	(d) to prove this, need rule of inference that from p
	    can infer (pvq) (i.e., (p -> (pvq)) is a tautology)

	Show:  LHS & RHS always have same t-val:

	Case 1:  Suppose LHS is T & show RHS is T:

		Since LHS is T, there is some x in domain that satisfies
		(P(x) v Q(x)).  Call it "a".

		That is, (P(a) v Q(a)) is T.

		Case 1a:  Suppose P(a) is T

			Then ExP(x) is T
			So, by the rule of inference above,
				(ExP(x) v ExQ(x)) is T

		Case 1b:  Suppose Q(a) is T

			Then ExQ(x) is T
                        So, by the rule of inference above,
                                (ExP(x) v ExQ(x)) is T

		So, in either case, the RHS of the original equiv is T

	Case 2:  Suppose RHS is T & show LHS is T:

		Since RHS is T,  and it is a disjunction, then at least
		one of its disjuncts must be T:

		So, either ExP(x) is T or ExQ(x) is T.

		If ExP(x) is T, there's something in the domain that is P;
		call it "a".  So:  P(a) is T

		If ExQ(x) is T, there's something in the domain that is Q;
		call it "b".  So:  Q(b) is T

		Case 2a:	Suppose P(a) is T
			Then by the rule of inference, (P(a) v Q(a)) is T
			So, Ex(P(x) v Q(x)) is T.

		Case 2b:	Suppose Q(b) is T
			Then by the rule of inference, (P(b) v Q(b)) is T
			So, Ex(P(x) v Q(x)) is T

		So, in either case, the LHS of the original equiv is T

QED.