Discrete Math Exam #1

What is a proposition?

A statement that is either true or false, but not both. Examples: "2 + 2 = 4" (true), "The sky is green" (false).

What is the negation operator (¬)?

Returns the opposite truth value. ¬P is true when P is false, and false when P is true.

What is conjunction (∧)?

The AND operator. P ∧ Q is true only when both P and Q are true.

What is disjunction (∨)?

The OR operator. P ∨ Q is true when at least one of P or Q is true.

What is implication (→)?

The "if…then" operator. P → Q is false only when P is true and Q is false. Otherwise it's true.

What is biconditional (↔)?

The "if and only if" operator. P ↔ Q is true when P and Q have the same truth value.

What is a tautology?

A propositional formula that is always true, regardless of the truth values of its variables. Example: P ∨ ¬P.

What is a contradiction?

A propositional formula that is always false, regardless of the truth values of its variables. Example: P ∧ ¬P.

What is the converse of P → Q?

Q → P (swap the hypothesis and conclusion).

What is the contrapositive of P → Q?

¬Q → ¬P (negate both and swap). This is logically equivalent to the original.

What are De Morgan's Laws?

¬(P ∧ Q) ≡ ¬P ∨ ¬Q and ¬(P ∨ Q) ≡ ¬P ∧ ¬Q. Negation distributes over AND/OR by flipping the operator.

What is the Distributive Law (logic)?

P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R) and P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R).

What is the Absorption Law (logic)?

P ∨ (P ∧ Q) ≡ P and P ∧ (P ∨ Q) ≡ P.

How do you prove logical equivalence?

Show both formulas have identical truth tables, OR use logical equivalences to transform one into the other.

What is a predicate?

A statement containing variables that becomes a proposition when values are assigned. Example: P(x): "x > 5".

What is a domain?

The set of all possible values that a variable in a predicate can take.

What is universal quantification (∀)?

"For all" - ∀x P(x) means P(x) is true for every x in the domain.

What is existential quantification (∃)?

"There exists" - ∃x P(x) means P(x) is true for at least one x in the domain.

When is ∀x P(x) true?

When P(x) is true for every single element in the domain.

When is ∃x P(x) true?

When P(x) is true for at least one element in the domain.

What is a counterexample?

A single example that disproves a universal statement. To disprove ∀x P(x), find one x where P(x) is false.

How do you negate ∀x P(x)?

¬(∀x P(x)) ≡ ∃x ¬P(x). "Not everything" means "something is not."

How do you negate ∃x P(x)?

¬(∃x P(x)) ≡ ∀x ¬P(x). "Nothing exists" means "everything is not."

What does ∀x ∃y P(x,y) mean?

For every x, there exists a y such that P(x,y). The y can be different for each x.

What does ∃x ∀y P(x,y) mean?

There exists one x such that for all y, P(x,y) is true. One x works for every y.

Does order of quantifiers matter?

YES! ∀x ∃y P(x,y) is NOT the same as ∃y ∀x P(x,y).

What is a set?

An unordered collection of distinct elements. Example: {1, 2, 3}.

What is the empty set (∅)?

The set containing no elements. Also written as { }.

What does A ⊆ B mean?

A is a subset of B. Every element of A is also in B. A could equal B.

What does A ⊂ B mean?

A is a strict (proper) subset of B. Every element of A is in B, but A ≠ B.

What is A ∪ B (union)?

The set of all elements in A OR B (or both). Combines both sets.

What is A ∩ B (intersection)?

The set of all elements in both A AND B. Only the common elements.

What is A - B (set difference)?

The set of elements in A but not in B. Also written as A \ B.

What is Ā (complement)?

The set of all elements in the universal set that are not in A.

What is A ⊕ B (symmetric difference)?

Elements in A or B but not both. A ⊕ B = (A - B) ∪ (B - A) = (A ∪ B) - (A ∩ B).

What is A × B (Cartesian product)?

The set of all ordered pairs (a, b) where a ∈ A and b ∈ B.

What is cardinality?

The number of elements in a set. Written as |A| or #A.

What is the power set P(A)?

The set of all subsets of A. If |A| = n, then |P(A)| = 2^n.

How do you prove A = B (set equality)?

Prove A ⊆ B (every element of A is in B) AND B ⊆ A (every element of B is in A).

How do you prove A ⊆ B?

Take an arbitrary element x ∈ A and show that x ∈ B.

What is a countable set?

A set whose elements can be put in one-to-one correspondence with natural numbers (finite or countably infinite).

What is set enumeration?

Explicitly listing all elements of a set. Example: {1, 2, 3, 4, 5}.

What is A ∩ B̄ in terms of set difference?

A - B. Elements in A but not in B.

What is a direct proof?

Assume the hypothesis P is true, then use logical steps to show the conclusion Q must be true.

What is proof by contradiction?

Assume the statement you want to prove is false, then derive a contradiction. Conclude the statement must be true.

What is proof by contrapositive?

To prove P → Q, instead prove ¬Q → ¬P (which is logically equivalent).

When should you use contrapositive?

When the contrapositive is easier to prove than the original. Common for divisibility and "not" statements.

What is proof by cases?

Break the proof into exhaustive cases, prove the statement holds in each case separately.

How do you prove an equivalence P ↔ Q?

Prove both directions: P → Q AND Q → P.

What is the Division Algorithm?

For integers a and b (b > 0), there exist unique integers q and r such that a = bq + r where 0 ≤ r < b.

How do you prove "a is not divisible by b"?

Show that when you divide a by b, the remainder r ≠ 0. Or use contrapositive.

What is mathematical induction?

A proof technique for statements about natural numbers: prove base case, then prove if true for n, it's true for n+1.

What is the base case in induction?

Proving the statement holds for the smallest value (usually n = 0 or n = 1).

What is the inductive step?

Proving that if the statement holds for n (inductive hypothesis), then it holds for n+1.

What is the inductive hypothesis?

The assumption that the statement holds for n. Used in the inductive step.

What is strong induction?

Like regular induction, but the inductive hypothesis assumes the statement is true for ALL values from the base case up to n.

When should you use strong induction?

When proving P(n+1) requires knowing P(k) for multiple values k ≤ n, not just P(n).

What is the structure of an induction proof?

1) State what you're proving. 2) Base case: verify for n = base. 3) Inductive step: assume true for n, prove for n+1. 4) Conclude by induction.

What's the difference between induction and strong induction?

Regular induction: assume P(n) to prove P(n+1). Strong induction: assume P(1), P(2), …, P(n) all true to prove P(n+1).

What is the Commutative Law for sets?

A ∪ B = B ∪ A and A ∩ B = B ∩ A.

What is the Associative Law for sets?

(A ∪ B) ∪ C = A ∪ (B ∪ C) and (A ∩ B) ∩ C = A ∩ (B ∩ C).

What is the Identity Law for sets?

A ∪ ∅ = A and A ∩ U = A (where U is the universal set).

What is the Domination Law?

A ∪ U = U and A ∩ ∅ = ∅.

What is the Idempotent Law?

A ∪ A = A and A ∩ A = A.

What is the Complement Law?

A ∪ Ā = U and A ∩ Ā = ∅. Also (Ā)̄ = A (double complement).

What is De Morgan's Law for sets?

(A ∪ B)̄ = Ā ∩ B̄ and (A ∩ B)̄ = Ā ∪ B̄.

Is ∅ ⊆ A always true?

Yes, always true. The empty set is a subset of every set.

What is |∅|?

0. The empty set has no elements.

What is |P(∅)|?

1. The power set of empty set is {∅}, which has one element.

Is ∅ ∈ P(A)?

Yes, always. The empty set is always a subset of any set.

How many elements in A × B?

|A × B| = |A| × |B|.

What is A - A?

∅. No elements remain.

What is A ∩ ∅?

∅. No elements in common with empty set.

When is P → Q false?

Only when P is true and Q is false. True in all other cases.