Discrete Structures Final Review!

What is a prime number?

• A number is prime if its only factors are 1 and itself

• A number is prime if its only factor is 1

• A number is prime if it has factors other than 1 and itself

• A number with more than 2 factors

p: "Brando is at school"
q: "Brando is at work"
Which statement reads "Brando is either at school or work?"

• p → q

• p ∧ q

• p ⇔ q

• p ∨ q

What is the negation of (p ∨ q)?

• ¬p ∨ q

• ¬p ∧ ¬q

• ¬p ∨ ¬q

• p ∧ ¬q

Answer explanation

¬(p ∨ q) is logically equivalent to ¬p ∧ ¬q (De Morgan's Law)

What is the negation of p → q?

• p ⇔ q

• ¬p → ¬q

• p ∧ ¬q

• ¬p ∨ ¬q

Answer explanation

¬(p → q) is logically equivalent to p ∧ ¬q (De Morgan's law)

T/F (¬p) → (p→q) is a tautology

• True

• False

Section (1) is the...

• Algorithm Description

• Algorithm Analysis

• Problem Specification

Section (2) is the

• Problem Specification

• Algorithm Analysis

• Algorithm Description

Section (3) is the...

• Algorithm Analysis

• Problem Specification

• Algorithm Description

T/F ¬(∀x, P(x)) = ∃x s.t. ¬P(x)

• True

• False

Answer explanation

De Morgan's Laws. Move the negation right, flip the operator!

What is the negation of ∀x C(x)?
(such that no negation is to the left of a quantifier)

• ¬∀x C(x)

• ∀x ¬C(x)

• ∃x ¬C(x)

• ¬∃x C(x)