DISCRETE STRUCTURE

MIDTERM EXAM

Proposition

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

Truth Value

The value true (T) or false (F) assigned to a proposition.

Negation (¬p)

The statement that has the opposite truth value of p.

Contradiction

A compound proposition that is always false.

Conjunction (p ∧ q

A compound statement that is true only if both p and q are true.

Disjunction (p ∨ q)

A compound statement that is true if at least one of p or q is true.I

Implication (p → q)

A statement that is false only when p is true and q is false.

Biconditional (p ↔ q)

A statement that is true when p and q have the same truth value.

Tautology

A compound proposition that is always true.

Contingency

A compound proposition that is sometimes true and sometimes false.

Logical Equivalence

Two propositions that have the same truth values in all cases.

De Morgan’s Laws

Rules that state ¬(p ∧ q) ≡ (¬p ∨ ¬q) and ¬(p ∨ q) ≡ (¬p ∧ ¬q).

Converse

The statement formed by switching the hypothesis and conclusion of an implication.

Inverse

The statement formed by negating both the hypothesis and conclusion.

Contrapositive

The statement formed by negating and reversing the implication.

Set

A well-defined collection of distinct elements.

Element

An object that belongs to a set.

Subset (⊆)

A set whose elements are all contained in another set.

Proper Subset (⊂)

A subset that is not equal to the original set.

Universal Set (U)

The set that contains all elements under discussion.

Empty Set (∅)

A set that contains no elements.

Union (A ∪ B)

The set containing elements in A, B, or both.

Intersection (A ∩ B)

The set containing elements common to both A and B.

Set Difference (A − B)

The set of elements in A but not in B.

Complement (Aᶜ)

The set of elements not in A but in the universal set.

Disjoint Sets

Sets that have no elements in common.

Power Set

The set of all possible subsets of a given set.

Cardinality

The number of elements in a set.

Finite Set

A set with a limited number of elements.

Infinite Set

A set with an unlimited number of elements.

Proof

A logical argument that demonstrates the truth of a statement.

Theorem

A statement that has been proven true.

Lemma

A proven statement used to help prove another theorem.

Direct Proof

A proof that starts from known facts and proceeds logically to the conclusion.

Indirect Proof

A proof that uses negation or alternative reasoning methods.

Proof by Contradiction

A proof that assumes the statement is false and leads to a contradiction.

Proof by Contrapositive

A proof that shows ¬q → ¬p instead of p → q.

Proof by Cases

• A proof that divides the problem into separate cases.

Counterexample

A specific example that disproves a universal statement.

Vacuous Proof

A proof where the hypothesis is false, making the implication true.