08 — Discrete Mathematics for Computer Science Free Online FlashCards

What is a proposition?

A proposition is a declarative statement that is either true or false, but not both.

When is an implication P → Q false?

P → Q is false only when P is true and Q is false.

Apply De Morgan’s law to ¬(P ∧ Q).

¬(P ∧ Q) ≡ ¬P ∨ ¬Q. Negating a conjunction negates each part and changes “and” to “or.”

How is ¬(∀x P(x)) rewritten?

¬(∀x P(x)) ≡ ∃x ¬P(x). Not every object has a property exactly when at least one object lacks it.

How many elements does 𝒫(A) have when A has n elements?

If A has n elements, its power set 𝒫(A) has 2ⁿ elements.

What is the Cartesian product A × B?

A × B = {(a,b) | a ∈ A and b ∈ B}; it contains every ordered pair with first component from A and second from B.

How can you prove two sets A and B are equal?

Prove A ⊆ B and B ⊆ A. Equivalently, show for an arbitrary x that x ∈ A ↔ x ∈ B.

What properties define an equivalence relation?

An equivalence relation is reflexive, symmetric, and transitive; it partitions a set into equivalence classes.

What properties define a partial order?

A partial order is reflexive, antisymmetric, and transitive.

What does it mean for a function to be injective?

A function is injective when distinct inputs have distinct outputs: f(a₁) = f(a₂) implies a₁ = a₂.

What does it mean for a function to be surjective?

A function is surjective when every element of its codomain is produced by at least one input.

How is the composition (g ∘ f)(a) defined?

For f : A → B and g : B → C, (g ∘ f)(a) = g(f(a)). Apply f first, then g.