CMSC 250

Exam #1 ANSWERS

Monday, Oct. 4, 2004

Write all answers legibly in the space provided. The number of points possible for each question is indicated in square brackets - the total number of points on the exam is 100, and you will have exactly 50 minutes to complete this exam. You may not use calculators, textbooks or any other aids during this exam. If you need more space for any answer, ask for an extra paper - these extra papers must be turned in and you must mark so we can find the answer corresponding to a question. The ``cheatsheet'' (which is the last page of the exam) can be ripped off and used during the exam, and the back of the cheat sheet can be used for scratch paper.

1. [20 pnts.] Use a COMPLETE truth table to determine if the following two statements are logically equivalent. Use 1 for ``true'' and 0 for ``false'' to create the complete truth table.
   • $(A \wedge \sim B) \rightarrow \hspace{.1in} \sim Z$
   • $(Z \wedge (A \vee B)) \rightarrow \hspace{.06in} Z$

   						Statement 1			Statement 2
   A	B	Z	$\sim B$	$\sim Z$	$A \wedge \sim B$	$(A \wedge \sim B) \rightarrow \sim Z$	$A \vee B$	$Z \wedge (A \vee B)$	$(Z \wedge (A \vee B)) \rightarrow Z$
   1	1	1	0	0	0	1	1	1	1
   1	1	0	0	1	0	1	1	0	1
   1	0	1	1	0	1	0	1	1	1
   1	0	0	1	1	1	1	1	0	1
   0	1	1	0	0	0	1	1	1	1
   0	1	0	0	1	0	1	1	0	1
   0	0	1	1	0	0	1	0	0	1
   0	0	0	1	1	0	1	0	0	1

   
   
   
   (NO) These statements are logically equivalent.

   
   
   

   Explain why you selected this answer for the logically equivalent question - indicate how specific rows/columns indicated this answer to you.

   
   
   

   ANSWER: The 3rd line in the column marked as Statement 1 is different from the 3rd line of the column marked as Statement 2. Every line of the column marked as Statement 1 must be the same as the corresponding line of the column marked as Statement 2 for the two statements to be logically equivalent.

   
   
   

   **** This area is for grading purposes (points lost per page)- Do not write below this line ****

   
   
   
   
   

   
   

   

   
   

2. [24 pnts.] Use only those rules given on the ``cheatsheet'' to prove that the following is a valid argument. It is a Valid Argument - you only need to prove that it is. You may assume that the domain D is not empty.

   P1	$\forall x \in D, (G(x) \wedge \sim Q(x)) \rightarrow R(x)$
   P2	$\exists x \in D, (P(x) \vee Q(x)) \rightarrow (M(x) \wedge N(x))$
   P3	$\forall x \in D, \sim M(x) \wedge G(x)$
   	Therefore $\exists y \in D, \sim R(y) \rightarrow M(y)$

   line	Statement	Reason	Line #s
   1	$(P(a) \vee Q(a)) \rightarrow (M(a) \wedge N(a))$	$\exists$ instantiation	P2
   2	$\sim M(a) \wedge G(a)$	$\forall$ instantiation	P3
   3	$\sim M(a)$	Conj Simp	2
   4	$\sim M(a) \vee \sim N(a)$	Disj Add	3
   5	$\sim (M(a) \wedge N(a))$	DeMorgan's	4
   6	$\sim (P(a) \vee Q(a))$	MT	5,1
   7	$\sim P(a) \wedge \sim Q(a)$	DeMorgan's	6
   8	$\sim Q(a)$	Conj Simp	7
   9	$G(a)$	Conj Simp	2
   10	$G(a) \wedge \sim Q(a)$	Conj Add	8,9
   11	$R(a)$	$\forall$ MP	P1,10
   12	$R(a) \vee M(a)$	Disj Add	11
   13	$\sim R(a) \rightarrow M(a)$	Def of Impl and DN	12
   14	$\exists x \in D, \sim R(x) \rightarrow M(x)$	$\exists$ generalization	13

   OR

   line	Statement	Reason	Line #s
   1	$\vert\sim [\exists y \in D, \sim R(y) \rightarrow M(y)]$	Assume
   2	$\vert\forall y \in D, \sim [\sim R(y) \rightarrow M(y)]$	neg of quantifiers1
   3	$\vert(P(a) \vee Q(a)) \rightarrow (M(a) \wedge N(a))$	$\exists$ inst	P2
   4	$\vert\sim (\sim R(a) \rightarrow M(a))$	$\forall$ inst	2
   5	$\vert\sim R(a) \wedge \sim M(a)$	Def of Impl	4
   6	$\vert\sim R(a)$	Conj Simp	5
   7	$\vert\sim (G(a) \wedge \sim Q(a))$	$\forall$ MT	6,P1
   8	$\vert\sim G(a) \vee Q(a)$	DM and DN	7
   9	$\vert\sim M(a) \wedge G(a)$	$\forall$ inst	P3
   10	$\vert G(a)$	Conj Simp	9
   11	$\vert Q(a)$	Disj Syll and DN	8,10
   12	$\vert P(a) \vee Q(a)$	Disj Add	11
   13	$\vert M(a) \wedge N(a)$	MP	12,3
   14	$\vert M(a)$	Conj Simp	13
   15	$\vert\sim M(a)$	Conj Simp	9
   16	$\vert M(a) \wedge \sim M(a)$	Conj Add	14,15
   17	$\exists y \in D, \sim R(y) \rightarrow M(y)$	CCW with Contra and DN	1-16

   OR

   line	Statement	Reason	Line #s
   1	$(P(a) \vee Q(a)) \rightarrow (M(a) \wedge N(a))$	$\exists$ instantiation	P2
   2	$\sim M(a) \wedge G(a)$	$\forall$ instantiation	P3
   3	$\vert\sim R(a)$	Assume
   4	$\vert\sim (G(a) \wedge \sim Q(a))$	$\forall$ MT	P1
   5	$\vert\sim G(a) \vee Q(a)$	DM and DN	4
   6	$\vert G(a)$	Conj Simp	2
   7	$\vert Q(a)$	Disj Syll and DN	5,6
   8	$\vert P(a) \vee Q(a)$	Disj Add	7
   9	$\vert M(a) \wedge N(a)$	MP	8,1
   10	$\vert M(a)$	Conj Simp	9
   11	$\sim R(a) \rightarrow M(a)$	CCW w/out Contr	3-10
   12	$\exists x \in D, \sim R(x) \rightarrow M(x)$	$\exists$ generalization	11

3. [16 pnts.] Translate each of the following to quantified predicate calculous notation. You may only use the domains and predicates given for that question. The NOT (``$\sim$``) may only appear immediately before a predicate - it may not appear immediately before a parenthesis or before a quantifier.

   There is a building that is taller than every other building.

   Domain: B = {all buildings}

   Predicate: T(x,y) = ``x is taller than y''

   $\exists x \in B, \forall y \in B, T(x,y) \vee x=y$

   Every dog and every cat is owned by some person who is nice.

   Domain: A = {all animals}, P= {all people}

   Predicates: D(x) = ``x is a dog'', C(x) = ``x is a cat'',

   O(x,y) = ``x is owned by person y'', N(x) = ``x is nice''

   $\forall x \in A, D(x) \vee C(x) \rightarrow \exists y \in P, O(x,y) \wedge N(y)$

   No child obeys his parents all of the time.

   Domain: A = {all people}, T= {all times}

   Predicates: C(x) = ``x is a child'', O(x,t) = ``x is obeying his parents at time t''

   $\forall x \in A, C(x) \rightarrow \exists t \in T, \sim O(x,t)$

   may think first: $\sim (\exists x \in A, C(a) \wedge \forall t \in T, O(x,y))$

   There is no largest nor smallest integer.

   Domain: Z = {all integers}

   Predicate: L(x,y) = ``integer x is larger than integer y''

   $(\forall x \in Z, \exists y \in Z, L(y,x)) \wedge (\forall z \in Z, \exists w \in Z, L(z,w))$

   OR

   $\forall x \in Z, \exists y,w \in Z, L(x,y) \wedge L(w,x)$

   
   
   
   
   
   
   
   

4. [6 pnts.] Translate each of the following to the base indicated.
   1. $24_8$ = 20 $_{10}$

   2. $178_{10}$ = B2 $_{16}$

   3. $10110111$ (in 8-bit 2's complement) = -73 (in regular decimal)

5. [20 pnts.] Give the formal proof to show that the following argument is valid or give truth values to the variables to show that the argument is not valid.

   P1	$(J \wedge K) \rightarrow L$
   P2	$(J \rightarrow L) \rightarrow M$
   P3	$\sim K \vee N$
   	Therefore $K \rightarrow (M \wedge N)$

   line	Statement	Reason	Line #s
   1	$\vert K$	Assume
   2	$\vert N$	DN and Disj Syll	1,P3
   3	$\vert$ $\vert\sim M$	Assume
   4	$\vert$ $\vert \sim (J \rightarrow L)$	MT	P2,3
   5	$\vert$ $\vert J \wedge \sim L$	def of impl	4
   6	$\vert$ $\vert J$	conj simp	5
   7	$\vert$ $\vert J \wedge K$	conj add	1,6
   8	$\vert$ $\vert L$	MP	P1,7
   9	$\vert$ $\vert\sim L$	Conj Simp	5
   10	$\vert$ $\vert L \wedge \sim L$	Conj Add	8,9
   11	$\vert M$	CCW with contra.	3-10
   12	$\vert M \wedge N$	Conj Add	2,11
   13	$K \rightarrow (M \wedge N)$	CCW without contra.	1-12

   OR

   line	Statement	Reason	Line #s
   1	$\sim (J \wedge K) \vee L$	Def of Impl	P1
   2	$(\sim J \vee \sim K) \vee L$	DM	1
   3	$(\sim J \vee L) \vee \sim K$	Comm and Assoc	2
   4	$(J \rightarrow L) \vee \sim K$	Def of Impl	3
   5	$\sim K \vee (J \rightarrow L)$	Comm	4
   6	$K \rightarrow (J \rightarrow L)$	Def of Impl	5
   7	$K \rightarrow M$	Hypo Syll	6,P2
   8	$\sim K \vee M$	Def of Impl	7
   9	$(\sim K \vee M) \wedge (\sim K \vee N)$	Conj Add	8,P3
   10	$\sim K \vee (M \wedge N)$	Distrib	9
   11	$K \rightarrow (M \wedge N)$	Def of Impl	10

   OR

   line	Statement	Reason	Line #s
   1	$\vert K$	Assume
   2	$\vert N$	DN and DS	1,P3
   3	$\vert\sim (J \wedge K) \vee L$	Def of Impl	P1
   4	$\vert(\sim J \vee \sim K) \vee L$	DM	3
   5	$\vert\sim K \vee (\sim J \vee L)$	Comm and Assoc	4
   6	$\vert K \rightarrow (\sim J \vee L)$	Def of Impl	5
   7	$\vert K \rightarrow (J \rightarrow L)$	Def of Impl	6
   8	$\vert K \rightarrow M$	Hypo Syll	7,P2
   9	$\vert M$	MP	1,8
   10	$\vert M \wedge N$	Conj Add	2,9
   11	$K \rightarrow (M \wedge N)$	CCW w/out Contra	1-10

6. [14 pnts.] Use an Euler diagram to determine if each of the following represents a valid argument form. Make sure to label the parts of the diagram. If it is invalid, you must draw a diagram that is not supportive of the conclusion. If it is a valid argument, draw a diagram that does support the conclusion (since you can't draw one that doesn't).

   No people like dirty water.

   No things that swim like dirty water.

   -----

   therefore: No people are things that swim.

   Circle One: Valid (Invalid)

   

   NOTE: P = People, S = Things that Swim, LDW = Things that Like Dirty Water

   All even integers have another integer that divides them.

   All perfect squares have another integer that divides them.

   -----

   therefore: Some perfect squares are even integers.

   Circle One: Valid (Invalid)

   

   Note: E = Even, PS = Perfect Squares, HI = Have another Integer that divides them

This page intentionally blank - to be used for scratch if needed.
Nothing on this page will be graded.
You may rip the last page off to use during the exam - do not turn it in with your exam paper.

Theorem 1.1.1 - Epp Textbook p. 14

Given any statement variables $p$, $q$, and $r$, a tautology $t$ and a contradiction $c$,
the following logical equivalences hold:
1. Commutative laws:	$p \wedge q \equiv q \wedge p$	$p \vee q \equiv q \vee p$
2. Associative laws:	$(p \wedge q) \wedge r \equiv p \wedge (q \wedge r)$	$(p \vee q) \vee r \equiv p \vee (q \vee r)$
3. Distributive laws:	$p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)$	$p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)$
4. Identity laws:	$p \wedge t \equiv p$	$p \vee c \equiv p$
5. Negation laws:	$p \vee \sim p \equiv t$	$p \wedge \sim p \equiv c$
6. Double Negative law:	$\sim (\sim p) \equiv p$
7. Idempotent laws:	$p \wedge p \equiv p$	$p \vee p \equiv p$
8. DeMorgan's laws:	$\sim (p \wedge q) \equiv \sim p \vee \sim q$	$\sim (p \vee q) \equiv \sim p \wedge \sim q$
9. Universal bounds laws:	$p \vee t \equiv t$	$p \wedge c \equiv c$
10. Absorption laws:	$p \vee (p \wedge q) \equiv p$	$p \wedge (p \vee q) \equiv p$
11. Negations of t and c:	$\sim t \equiv c$	$\sim c \equiv t$

Table 1.3.1 - Epp Textbook p. 40

Modus Ponens	Modus Tollens		Disjunctive	$p \vee q$	$p \vee q$
$p \rightarrow q$	$p \rightarrow q$		Syllogism	$\sim q$	$\sim p$
$p$	$\sim q$			Therefore $p$	Therefore $q$
Therefore $q$	Therefore $\sim p$
Conjunctive	$p$		Hypothetical	$p \rightarrow q$
Addition	$q$		Syllogism	$q \rightarrow r$
	Therefore $p \wedge q$			Therefore $p \rightarrow r$
Disjunctive	$p$	$q$	Dilemma:	$p \vee q$
Addition	Therefore $p \vee q$	Therefore $p \vee q$	Poof by	$p \rightarrow r$
			Division	$q \rightarrow r$
			into Cases	Therefore $r$
Conjunctive	$p \wedge q$	$p \wedge q$	Rule of	$\sim p \rightarrow c$
Simplification	Therefore $p$	Therefore $q$	Contradiction	Therefore $p$
Closing C.W.	$\vert p$ Assumed		Closing C.W.	$\vert p$ Assumed
without	$\vert q$ derived		with	$\vert x \wedge \sim x$ derived
contradiction	Therefore $p \rightarrow q$		contradiction	Therefore $\sim p$

Other Equivalences and Other Rules of Inference

Definition	$p \rightarrow q$	$\equiv$	$\sim p \vee q$
of Implication	$\sim (p \rightarrow q)$	$\equiv$	$p \wedge \sim q$
Definition of	$A \leftrightarrow B$	$\equiv$	$(A \rightarrow B) \wedge (B \rightarrow A)$
Biconditional	$\sim (A \leftrightarrow B)$	$\equiv$	$(A \wedge \sim B) \vee (B \wedge \sim A)$
Negation of	$\sim \forall x\,\, P(x)$	$\equiv$	$\exists x \,\, \sim P(x)$
Quantifiers	$\sim \exists x\,\, P(x)$	$\equiv$	$\forall x \,\, \sim P(x)$
Universal	$\forall x \in D, P(x) \rightarrow Q(x)$
Modus Ponens	$P(a)$	$\rightarrow$	$Q(a)$
Universal	$\forall x \in D, P(x) \rightarrow Q(x)$
Modus Tollens	$\sim Q(a)$	$\rightarrow$	$\sim P(a)$
Universal Instantiation	$\forall x \in D, P(x)$	$\rightarrow$	$P(a)$
Existential Generalization	$P(a)$ where $a \in D$	$\rightarrow$	$\exists x \in D, P(x)$
Universal Generalization**	$P(a)$ where $a \in D$	$\rightarrow$	$\forall x \in D, P(x)$
Existential Instantiation **	$\exists x \in D, P(x)$	$\rightarrow$	$P(a)$ where $a \in D$

** NOTE: Remember the special circumstances required for the rules marked by the stars.

Table 5.2.1 - Subset Relations

Given any sets $A$, $B$, and $C$:
1. Inclusion for Intersection:	$(A \cap B) \subseteq A$
	$(A \cap B) \subseteq B$
2. Inclusion for Union:	$A \subseteq (A \cup B)$
	$B \subseteq (A \cup B)$
3. Transitive Property of Subsets:	$(A \subseteq B)\wedge (B \subseteq C) \rightarrow A \subseteq C$

Theorem 5.2.2 - Set Identities

Given any sets $A$, $B$, and $C$, the universal set $U$ and the empty set $\emptyset$:
1. Commutative laws:	$A \cap B = B \cap A$
	$A \cup B = B \cup A$
2. Associative laws:	$(A \cap B) \cap C = A \cap (B \cap C)$
	$(A \cup B) \cup C = A \cup (B \cup C)$
3. Distributive laws:	$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
	$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$
4. Intersection with U (Identity):	$A \cap U = A$
5. Double Complement law:	$(A')' = A$
6. Idempotent laws:	$A \cap A = A$
	$A \cup A = A$
7. De Morgan's laws:	$(A \cup B)' = A' \cap B'$
	$(A \cap B)' = A' \cup B'$
8. Union with U (Universals Bounds):	$A \cup U = U$
9. Absorption laws:	$A \cup (A \cap B) = A$
	$A \cap (A \cup B) = A$
10. Alternative Representation for Set Diff:	$A - B = A \cap B'$

Table 5.2.3 - Subset Intersection and Union

Given any sets $A$, $B$ :
1. $A \subseteq B \rightarrow (A \cap B = A)$	Intersection with Subset
2. $A \subseteq B \rightarrow (A \cup B = B)$	Union with Subset

Table 5.3.3 (plus others) - Properties of $\emptyset$ and Universal set

Given any sets $A$, $B$, and $C$, the universal set $U$ and the empty set $\emptyset$:
1. Union with $\emptyset$:	$A \cup \emptyset = A$
2. Intersection and Union with Complement	$A \cap A' = \emptyset$
	$A \cup A' = U$
3. Intersection with $\emptyset$ :	$A \cap \emptyset = \emptyset$
4. Complement of Union and $\emptyset$:	$U' = \emptyset$
	$\emptyset' = U$
5. Every set is subset of Universal	$\forall A \in \{Sets\}, A \subseteq U$
6. Empty set is subset of every set	$\forall A \in \{Sets\}, \emptyset \subseteq A$
7. Definition of Empty Set	$\forall A \in \{Sets\}, A = \emptyset \leftrightarrow \forall x \in U, x \not \in A$

Things from Ch. 4

Theorem 4.1.1	$\sum_{k=m}^n a_k + \sum_{k=m}^n b_k = \sum_{k=m}^n (a_k+b_k)$
Theorem 4.1.1	$c \cdot \sum_{k=m}^n a_k = \sum_{k=m}^n (c \cdot a_k)$
Theorem 4.1.1	$\prod_{k=m}^n a_k \cdot \prod_{k=m}^n b_k = \prod_{k=m}^n (a_k \cdot b_k)$
Theorem 4.2.2	$\sum_{i=1}^m i = \frac{m(m+1)}{2}$
Theorem 4.2.3	$\sum_{i=0}^n r^i = \frac{r^{n+1} - 1}{r - 1}$

Web Accessibility