Discrete Math - Test 2

DeMorgan’s Laws:
∼(p ∧ q) ≡ ?
∼(p ∨ q) ≡ ?

∼p ∨ ∼q
∼p ∧ ∼q

Conditional Statements:
∼(p → q) ≡ ?

p ∧ ∼q

Quantified Statements:
∼(∀x ∈ D, P (x)) ≡ ?
∼(∃x ∈ D s.t. P (x)) ≡ ?
∼(∀x ∈ D, P (x) → Q(x)) ≡ ?

∃x ∈ D s.t. ∼P (x)
∀x ∈ D, ∼P (x)
∃x ∈ D s.t. P (x) ∧ ∼Q(x)

Modifications of Conditional Statements:
Statement: ∀x ∈ D, P (x) → Q(x)
Converse: ?
Inverse: ?
Contrapositive: ?

∀x ∈ D, Q(x) → P (x)

∀x ∈ D, ∼P (x) → ∼Q(x)

∀x ∈ D, ∼Q(x) → ∼P (x)

Even, Odd, Prime, Composite, Divisibility:
An integer n is even iff… ?

An integer n is odd iff… ?

For integers n and d, n is divisible by d, denoted d | n, iff… ?

An integer n > 1 is prime iff… ?

An integer n > 1 is composite iff… ?

n = 2k for some integer k.
n = 2k + 1 for some integer k.
n = dk for some integer k.
for all positive integers r and s, if n = rs then r = 1 or s = 1.
there exists positive integers r and s such that n = rs, and both r ̸ = 1 and s ̸ = 1.

Proofs of Existential Statements:

Suppose we want to prove the statement ∃x ∈ D s.t. P (x). How to prove this statement?

Constructive Proof. Find one specific x-value that satisfies P(x).

Proofs of Universal Statements:

Suppose we want to prove the statement ∀x ∈ D, P(x). What are valid proof methods?

1. Direct proof .

First sentence: “Let x ∈ D.”

Goal: Show P (x) is true.

2. Proof by contradiction.

First sentence: “Assume, to the contrary, that ∃x ∈ D such that ∼P (x).”

Goal: Show that the above assumption leads to a contradiction.

Proofs of Universal Conditional Statements:

Suppose we want to prove the statement ∀x ∈ D, P (x) → Q(x). What are valid proof methods?

1. Direct proof .

First sentence: “Let x ∈ D such that P (x).”

Goal: Show Q(x) is true.

2. Proof by contraposition.

First sentence: “Let x ∈ D such that ∼Q(x).”

Goal: Show that ∼P (x) is true.

3. Proof by contradiction.

First sentence: “Assume, to the contrary, that ∃x ∈ D such that P (x) and ∼Q(x).”

Goal: Show that the above assumption leads to a contradiction.

Set Relations:

Let R be a relation on a set A.

R is reflexive iff: ?

R is symmetric iff: ?

R is transitive iff: ?

∀x ∈ A, x R x.
∀x, y ∈ A, if x R y then y R x.
∀x, y, z ∈ A, if x R y and y R z, then x R z.

We say that R is an equivalence relation iff ?

If R is an equivalence relation, then the equivalence classes are defined as ?

If R is an equivalence relation on a set A, then

For any a ∈ A, ?

For any a, b ∈ A, if a R b, then ?

What do the distinct equivalence classes of R form?

R is reflexive, symmetric and transitive.
[a] = {x ∈ A : x R a} That is, [a] is the set of all elements in A that are related to a.
a ∈ [a].
[a] = [b].
a partition of A.