CS202 Question 2

Name: ______________________________________

Pledge: _______________________________________________________________________

Signature: _____________________________________________________________________

There are 75 minutes for this exam and 100 points on the test; don’t spend too long on any one question!

The 12 short answer questions require only a sentence or two for full credit; the three long answer questions have their own page, and obviously require more. The questions are organized by topic, so the long answer questions are scattered throughout the exam (questions 5, 14, and

15. . The long answer questions are worth about half of the test score; the short answer questions are all worth 4 points each, and constitute the other half. The reference sheet is on page 2.

All work must be on these exam pages.

Good luck!

_____ / 33

Part II: Structures _____ / 16

_____ / 51

Total _____ / 100

CS 202 · Exam 1 Reference Sheet · Set and logical identities

Sets (Rosen, p. 89) Boolean logic (Rosen, p. 24)

A U A A

A I U Identity laws p

p p

p

F

T

I U A U U A Domination

laws

F · F · T · T

p p

A A A A A A I U Idempotent

laws p p p p p p

A A = Complementation law p p ≡

A B B A A B B A I

I U

U Commutative

laws p q q p p q q p

C B A

C B A C B A

C B A I I

I I U U

U U Associative

laws r q p r q p r q p r q p

C A

B A

C B A C A

B A

C B A U I U

I U I U I

U I Distributive

laws r p

q p

r q p r p

q p

r q p

B A B A B A B A U

I I

U DeMorgan’s

laws q

p

q p q

p

q p

A B A A A B A A U I I U Absorption

laws p q p p p q p p

A A U A A I U Complement

laws

F

T

p

p p

p

Rules of inference (Rosen, p. 58)

Rule of Inference Tautology

q p p q p

p Addition

p q p p

q p Simplification

q p q p q p

q p Conjunction

q q p p q

q p p Modus ponens

p q p q p

q p q Modus tollens

r p r q q p r p

r q q p Hypothetical syllogism

q p q p q

p

q p Disjunctive syllogism

r q r p q p r q

r p

q p Resolution

Q1. (4 points): What is the converse of p→q?

Q2. (4 points): Given the Boolean proposition p↔q, write an equivalent compound proposition using only the operators ¬, ∧, and ∨.

Q3. (4 points): State the negation of the following quantified statement: y

Q x P y x