Home / Courses / Discrete Mathematics / Unit 1

Discrete Mathematics Unit 1: Logic & propositional calculus

Logic is the grammar of mathematics. It defines exactly what "and," "or," "if…then" and "for all" mean.

Covers: Statements, truth tables, logical equivalence, quantifiers

Study guide

A proposition is a statement that is either true or false. Logical connectives build compound statements: negation ¬p, conjunction p ∧ q (and), disjunction p ∨ q (or, inclusive), the conditional p → q (if p then q), and the biconditional p ↔ q (if and only if). A truth table lists the truth value of a compound statement for every combination of its parts.

The conditional p → q is false only when p is true and q is false; it's "vacuously" true when p is false. Related statements: the converse q → p, the inverse ¬p → ¬q, and the contrapositive ¬q → ¬p. Only the contrapositive is logically equivalent to the original.

Two statements are logically equivalent if they have the same truth table. Key equivalences include De Morgan's laws, ¬(p ∧ q) ≡ ¬p ∨ ¬q and ¬(p ∨ q) ≡ ¬p ∧ ¬q; p → q ≡ ¬p ∨ q; and the distributive and double-negation laws. A tautology is always true and a contradiction is always false.

Predicates contain variables, like P(x): "x > 3." Quantifiers turn them into propositions: the universal quantifier ∀x P(x) says P is true for every x in the domain, and the existential quantifier ∃x P(x) says it's true for at least one. Negation swaps them: ¬∀x P(x) ≡ ∃x ¬P(x), and ¬∃x P(x) ≡ ∀x ¬P(x). With nested quantifiers, order matters: ∀x∃y is different from ∃y∀x.

An argument is valid if the conclusion is true in every row of the truth table where all the premises are true. Common valid forms include modus ponens (from p → q and p, conclude q) and modus tollens (from p → q and ¬q, conclude ¬p). Affirming the consequent (from p → q and q, concluding p) is a fallacy. Any truth table can be written as a formula: for each row where the output is true, write an "and" of the variables (negating those that are false in that row), then join all these terms with "or." The result is in disjunctive normal form.

p NOR q means ¬(p ∨ q), and p NAND q means ¬(p ∧ q). Each one alone can express every connective. For example, ¬p ≡ p NOR p, and p ∧ q ≡ (¬p) NOR (¬q) by De Morgan's law. "p only if q," "q is necessary for p," and "p is sufficient for q" all mean p → q. "p unless q" means ¬q → p. "Or" in logic is inclusive unless the problem says exclusive or (⊕), which is true when exactly one part is true.

Key ideas

• A proposition is a statement that is true or false.
• p → q is false only when p is true and q is false.
• The contrapositive ¬q → ¬p is equivalent to p → q; the converse q → p is not.
• De Morgan's laws: ¬(p ∧ q) ≡ ¬p ∨ ¬q, ¬(p ∨ q) ≡ ¬p ∧ ¬q.
• Negating quantifiers swaps them: ¬∀x P(x) ≡ ∃x ¬P(x).

Formulas and rules

Common mistakes

• Treating the converse as equivalent to the original.
• Negating "all are" as "none are" instead of "some aren't."

Words to know

Conditional p → q

False only when p is true and q is false.

Contrapositive of p → q

¬q → ¬p (equivalent to p → q)

Converse of p → q

q → p (not equivalent)

De Morgan: ¬(p ∧ q)

¬p ∨ ¬q

Negation of ∀x P(x)

∃x ¬P(x)

Proposition

A statement that is true or false.

Conjunction (p ∧ q)

True only when both are true.

Disjunction (p ∨ q)

True when at least one is true.

Biconditional (p ↔ q)

True when p and q have the same truth value.

Inverse of p → q

¬p → ¬q (not equivalent).

Tautology

A statement that is always true.

Contradiction (logic)

A statement that is always false.

Universal quantifier (∀)

"For all."

Existential quantifier (∃)

"There exists."

Sample practice questions

17 more questions like these, from level 1 to 5, are in the practice set.