Name (PRINTED):
Student ID #:
Section # (or TA's:
name and time)

CMSC 250

Exam #1

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$

   
   
   
   (Yes or 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.

   
   
   
   
   
   
   

   **** 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
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20
   21
   22

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''

   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''

   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''

   There is no largest nor smallest integer.

   Domain: Z = {all integers}

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

   
   
   
   
   
   
   
   

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

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

   3. $10110111$ (in 8-bit 2's complement) = (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
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20
   21
   22

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

   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

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