Difficulty: Foundational. Prerequisites: none, though comfort with basic algebra helps.
Chapters 1 and 2 of CS 18200 cover the two pillars everything else in this course rests on: formal logic (how to build and evaluate statements, how to prove things) and discrete structures (sets, functions, sequences, sums, matrices). If you can manipulate logical equivalences, apply rules of inference, and work comfortably with set operations and function properties, the later chapters on induction, counting and probability become far more approachable.
Proposition
A declarative statement that is either true or false, never both. Think of it as any sentence you could stamp "T" or "F" on without ambiguity.
Negation (¬p)
The logical opposite of a proposition p. In simple terms, if p is true, ¬p is false, and vice versa.
Conjunction (p ∧ q)
True only when both p and q are true. Think of it as the logical "and."
Disjunction (p ∨ q)
True when at least one of p or q is true. This is the logical "or" (inclusive).
Implication (p → q)
False only when p is true and q is false; true in every other case. In simple terms, a promise that is only broken when the condition holds but the result does not.
Biconditional (p ↔ q)
p and q have the same truth value. Think of it as "p if and only if q."
Converse
Given p → q, the converse is q → p. The converse does not share the same truth value as the original.
Contrapositive
Given p → q, the contrapositive is ¬q → ¬p. This one does share the same truth value as the original implication.
Inverse
Given p → q, the inverse is ¬p → ¬q. Like the converse, it does not share the truth value of the original.
Predicate
A statement whose truth value depends on the value of one or more variables. In simple terms, a proposition with blanks to fill in.
Universal quantifier (∀)
"For all." The statement holds for every element in the domain.
Existential quantifier (∃)
"There exists." At least one element in the domain makes the statement true.
Tautology
A compound proposition that is always true, regardless of the truth values of its components.
Contradiction
A compound proposition that is always false.
Set
An unordered collection of distinct elements. Think of it as a bag where duplicates are ignored and order does not matter.
Cardinality (|A|)
The number of elements in a set A.
Power set (P(A))
The set of all subsets of A. If |A| = k, then |P(A)| = 2^k.
Function
A mapping from one set (the domain) to another (the co-domain) where each input maps to exactly one output.
Injective (one-to-one)
A function where no two different inputs map to the same output. In simple terms, every output is used at most once.
Surjective (onto)
A function where every element of the co-domain is mapped to by at least one element of the domain.
Bijective
A function that is both injective and surjective. Think of it as a perfect pairing between domain and co-domain.
Sequence
An ordered list of elements, typically defined by a formula or a recurrence relation.
Recurrence relation
A rule that defines each term in a sequence using previous terms. The Fibonacci sequence is the classic example.
Negation (¬p): flips the truth value of p.
Conjunction (p ∧ q): true only when both are true.
Disjunction (p ∨ q): true when at least one is true.
Implication (p → q): false only when p is true and q is false. Equivalent phrasings include "if p then q," "p is sufficient for q," "q is necessary for p," "q unless ¬p," and "p only if q."
Biconditional (p ↔ q): true when p and q share the same truth value. Read as "p if and only if q."
¬ (Not)
∧ (And)
∨ (Or)
→ (Implication)
↔ (Biconditional)
Original: p → q
Converse: q → p (different truth value from the original)
Contrapositive: ¬q → ¬p (same truth value as the original)
Inverse: ¬p → ¬q (different truth value from the original)
The contrapositive is the only variant logically equivalent to the original. This is a high-frequency exam point.
Identity: p ∧ T ≡ p, and p ∨ F ≡ p
Domination: p ∨ T ≡ T, and p ∧ F ≡ F
Idempotent: p ∨ p ≡ p, and p ∧ p ≡ p
Double negation: ¬(¬p) ≡ p
Commutative: p ∨ q ≡ q ∨ p, and p ∧ q ≡ q ∧ p
Associative: (p ∨ q) ∨ r ≡ p ∨ (q ∨ r), and (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
Distributive: p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r), and p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
De Morgan's Laws: ¬(p ∧ q) ≡ ¬p ∨ ¬q, and ¬(p ∨ q) ≡ ¬p ∧ ¬q
Absorption: p ∨ (p ∧ q) ≡ p, and p ∧ (p ∨ q) ≡ p
Negation: p ∨ ¬p ≡ T, and p ∧ ¬p ≡ F
p → q ≡ ¬p ∨ q
p → q ≡ ¬q → ¬p
p ∨ q ≡ ¬p → q
p ∧ q ≡ ¬(p → ¬q)
¬(p → q) ≡ p ∧ ¬q
(p → q) ∧ (p → r) ≡ p → (q ∧ r)
(p → r) ∧ (q → r) ≡ (p ∨ q) → r
(p → q) ∨ (p → r) ≡ p → (q ∨ r)
(p → r) ∨ (q → r) ≡ (p ∧ q) → r
p ↔ q ≡ (p → q) ∧ (q → p)
p ↔ q ≡ ¬p ↔ ¬q
p ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q)
¬(p ↔ q) ≡ p ↔ ¬q
A predicate is a statement containing variables that becomes a proposition once values are assigned. Quantifiers bind those variables over a domain.
Universal (∀x P(x)): P(x) is true for every x in the domain.
Existential (∃x P(x)): there is at least one x in the domain for which P(x) is true.
Negating quantifiers flips them: ¬∀x P(x) ≡ ∃x ¬P(x), and ¬∃x P(x) ≡ ∀x ¬P(x). Nested quantifiers follow the same pattern, working from the outside in.
Modus Ponens: from p and p → q, conclude q.
Modus Tollens: from ¬q and p → q, conclude ¬p.
Hypothetical Syllogism: from p → q and q → r, conclude p → r.
Disjunctive Syllogism: from p ∨ q and ¬p, conclude q.
Addition: from p, conclude p ∨ q.
Simplification: from p ∧ q, conclude p.
Conjunction: from p and q (separately), conclude p ∧ q.
Resolution: from p ∨ q and ¬p ∨ r, conclude q ∨ r.
Universal Instantiation: from ∀x P(x), conclude P(c) for any element c.
Universal Generalization: from P(c) for an arbitrary c, conclude ∀x P(x).
Existential Instantiation: from ∃x P(x), conclude P(c) for some particular c.
Existential Generalization: from P(c) for a specific c, conclude ∃x P(x).
Direct proof: assume p is true, then use definitions, axioms and previously proven results to show q is true. The standard approach for p → q.
Proof by contradiction: assume ¬p (the negation of what you want to prove), then derive a contradiction of the form r ∧ ¬r. Since the assumption leads to an impossibility, p must be true.
Proof by contraposition: instead of proving p → q directly, prove the logically equivalent ¬q → ¬p. Useful when the negation of q gives you something concrete to work with.
Exhaustive proof (proof by cases): break the problem into a finite number of cases and prove each one individually. Every possible case must be covered.
Existence proof (constructive): to prove ∃x P(x), find a specific witness "a" such that P(a) is true.
Existence proof (non-constructive): prove ∃x P(x) without producing a witness, typically by contradiction. You show that assuming no such x exists leads to a contradiction.
Uniqueness proof: first show ∃x P(x), then show that for any y ≠ x, P(y) is false. Two steps: existence, then uniqueness.
Union (A ∪ B): all elements in A or B (no duplicates).
Intersection (A ∩ B): elements in both A and B.
Difference (A - B): elements in A that are not in B.
Complement (Ā): all elements not in A. Equivalent to U - A, where U is the universal set.
Subset (A ⊆ B): every element of A is also in B. Proper subset (A ⊂ B) adds the condition A ≠ B.
Superset (A ⊇ B): B ⊆ A.
Cardinality |A|: the count of elements in A.
Power set P(A): the set of all subsets of A. |P(A)| = 2^|A|.
A function f: A → B maps each element of A (the domain) to exactly one element of B (the co-domain). The range is the subset of B that is mapped to.
Injective (one-to-one): distinct inputs always produce distinct outputs. The co-domain need not be fully covered.
Surjective (onto): every element in the co-domain is hit by at least one input.
Bijective: both injective and surjective. A bijection has an inverse function f⁻¹.
Composition: (f ∘ g)(x) = f(g(x)).
Ceiling ⌈x⌉: the smallest integer ≥ x.
Floor ⌊x⌋: the largest integer ≤ x.
A set with the same cardinality as the integers is countably infinite. A set with the same cardinality as the reals is uncountably infinite. The union of two countable sets is countable.
Written {a_n}, where a_n is a formula giving the nth term (e.g. a_n = 1/n).
A geometric sequence has the form a_n = a · r^n, where a and r are real numbers.
Sequences can be defined recursively. The Fibonacci sequence: F_n = F_(n-1) + F_(n-2), with F_0 = 0 and F_1 = 1.
To solve a recurrence relation, expand terms until you spot the pattern, then write the closed form.
∑(k=0 to n) ar^k = a(r^(n+1) - 1) / (r - 1), for r ≠ 1
∑(k=0 to n) k = n(n+1)/2
∑(k=1 to n) k² = n(n+1)(2n+1)/6
∑(k=1 to n) k³ = n²(n+1)²/4
∑(k=0 to ∞) x^k = 1/(1-x), for |x| < 1
∑(k=1 to ∞) kx^(k-1) = 1/(1-x)², for |x| < 1
When the lower bound is offset (e.g. starting at 50 instead of 1), split the sum: ∑(k=50 to 100) k² = ∑(k=1 to 100) k² – ∑(k=1 to 49) k².
A 3×2 matrix has 3 rows and 2 columns.
Addition/Subtraction: matrices must have the same dimensions; operate element by element.
Multiplication: the number of columns in the first matrix must equal the number of rows in the second. The result has dimensions (rows of first) × (columns of second). Each entry is the dot product of the corresponding row and column.
Matrix multiplication is not commutative (AB ≠ BA in general).
The identity matrix has ones on the main diagonal and zeros elsewhere.
Students often confuse the converse (q → p) with the contrapositive (¬q → ¬p). Only the contrapositive is logically equivalent to the original implication.
An implication p → q is true whenever p is false, regardless of q. Many students expect a false hypothesis to make the implication false.
Injective does not mean surjective. A one-to-one function can leave elements in the co-domain unmapped.
The empty set is a subset of every set. Students frequently forget this.
⚠️ The final has 4 questions on Logic and Proofs and 4 on Sets, Functions, Sequences, Sums, Matrices. These two chapters carry the highest question count on the exam.
⚠️ De Morgan's Laws appear in nearly every exam cycle, both for propositional logic and for set operations.
⚠️ Know the equivalence p → q ≡ ¬p ∨ q cold. It is the bridge between implications and disjunctions that many proof questions rely on.
⚠️ Be able to apply the summation formulas with an offset starting index (split the sum into two).
⚠️ Matrix multiplication: know the dimension-matching rule and remember that multiplication is not commutative.
True or false: the converse of p → q has the same truth value as p → q.
Fill in the blank: ¬(p ∨ q) ≡ ___.
True or false: the empty set is a subset of every set.
Fill in the blank: if |A| = 4, then |P(A)| = ___.
True or false: matrix multiplication is commutative.
Answers: 1. False (only the contrapositive is equivalent). 2. ¬p ∧ ¬q (De Morgan's). 3. True. 4. 16. 5. False.
Q: Show that p → q is logically equivalent to ¬p ∨ q using a truth table or equivalence laws.
A: By definition, p → q is false only when p is true and q is false. Rewriting: p → q ≡ ¬p ∨ q. You can verify with a four-row truth table: both expressions produce identical columns.
Q: Let A = {1, 2, 3} and B = {2, 3, 4}. Find A ∪ B, A ∩ B, A - B, and |P(A)|.
A: A ∪ B = {1, 2, 3, 4}. A ∩ B = {2, 3}. A - B = {1}. |P(A)| = 2³ = 8.
Q: Determine whether f(x) = 2x + 1, mapping integers to integers, is injective, surjective, or bijective.
A: Injective: if 2a + 1 = 2b + 1 then a = b, so yes. Surjective: even integers have no pre-image (e.g. no integer x gives 2x + 1 = 4), so no. Therefore injective but not bijective.
Q: Evaluate ∑(k=1 to 50) k using the closed-form formula.
A: n(n+1)/2 = 50(51)/2 = 1275.
Q: Using Modus Tollens, what can you conclude from ¬q and p → q?
A: ¬p.
Logical equivalences and proof techniques are the foundation for Chapter 5 (Induction and Recursion): every induction proof is, at its core, a chain of implications. Set operations and cardinality feed directly into Chapter 6 (Counting), where you count elements of unions and intersections using the subtraction rule. Functions and their properties (injection, surjection) reappear in Chapter 7 (Probability) when defining sample spaces and random variables.
CS 18200, CS 182, Purdue, Foundations of Computer Science, discrete mathematics, propositional logic, truth table, logical equivalence, De Morgan's Law, modus ponens, modus tollens, hypothetical syllogism, disjunctive syllogism, resolution, universal quantifier, existential quantifier, predicate logic, direct proof, proof by contradiction, contrapositive proof, set theory, union, intersection, complement, power set, cardinality, injective, surjective, bijective, one-to-one, onto, inverse function, composition, floor function, ceiling function, sequence, geometric sequence, Fibonacci, recurrence relation, summation formula, matrix multiplication, identity matrix