Discrete Mathematics: Foundations

What is a tautology in propositional logic?

A compound proposition that is always true, regardless of the truth values of the individual propositions it contains.

Define the power set of a set S.

The set of all possible subsets of S, including the empty set and S itself.

What does it mean for a function to be injective (one-to-one)?

A function f: A -> B is injective if for every a1, a2 in A, f(a1) = f(a2) implies a1 = a2.

State De Morgan's Laws for propositional logic.

¬(p ∧ q) ≡ ¬p ∨ ¬q and ¬(p ∨ q) ≡ ¬p ∧ ¬q.

How do you form the contrapositive of the conditional statement p → q?

The contrapositive is ¬q → ¬p, which is logically equivalent to the original statement.

Describe the two steps required in a proof by weak mathematical induction.

1. Base Case: Prove the statement for the smallest value (e.g., n=1). 2. Inductive Step: Assume the statement holds for n=k and prove it holds for n=k+1.

What three properties must a relation satisfy to be considered an equivalence relation?

Reflexivity (aRa), Symmetry (aRb implies bRa), and Transitivity (aRb and bRc implies aRc).

What is the cardinality of the power set P(S) if the set S has n elements?

The cardinality is 2^n.

Define a surjective (onto) function.

A function f: A -> B is surjective if for every element b in the codomain B, there exists at least one element a in the domain A such that f(a) = b.

What is the logical negation of the statement 'For all x, P(x)'?

The negation is 'There exists an x such that NOT P(x)' (∃x ¬P(x)).