1
Read a formula unambiguously
Parse a compound statement, apply precedence correctly, and build its truth table without guessing at what → means when its hypothesis is false.
Course · Discrete Mathematics
Logic and Proof
Make a statement precise enough to be true or false, then establish it. Connectives and truth tables, logical equivalence, quantifiers and the order they come in, valid inference, and direct, contrapositive, contradiction and case proofs written out in full.
p → q ≡ ¬p ∨ q the conditional, in disjunctive form
¬(p ∧ q) ≡ ¬p ∨ ¬q De Morgan
¬∀x P(x) ≡ ∃x ¬P(x) negation flips the quantifier
p → q ≡ ¬q → ¬p contraposition: the basis of a proof method
What this course is about
- Subject
- Discrete Mathematics
- Lessons
- 14
- Format
- Interactive
Overview
What you will be able to do
By the end you can read a theorem statement exactly as written, and write a proof someone else can check.
2
Prove two statements equivalent
Either by a full truth table, or by a chain of named equivalences — and know that one separating assignment refutes the claim outright.
3
Handle quantifiers with care
Distinguish ∀x ∃y from ∃x ∀y, negate a quantified statement mechanically, and recognise the vacuous truth that catches everyone once.
4
Write the four standard proofs
Direct, contrapositive, contradiction and cases — knowing which shape of claim invites which technique, and what each one owes the reader.
Lessons
14 lessons
Propositional logic comes first, then quantifiers are added, and then all of it is turned into proofs.
Propositions and Truth ValuesWhat counts as a proposition, and what does not.Not marked
Logical ConnectivesNegation, conjunction, disjunction, exclusive or.Not marked
Truth TablesThe complete method for evaluating any compound statement.Not marked
The Conditional and Its RelativesIf-then, converse, inverse, contrapositive, and vacuous truth.Not marked
Logical EquivalenceWhen two formulas say the same thing, and the laws that rewrite one into the other.Not marked
Tautology, Contradiction, SatisfiabilityAlways true, never true, and sometimes true.Not marked
Normal Forms and Boolean AlgebraEvery formula rewritten into one of two standard shapes.Not marked
Predicates and QuantifiersTurning open sentences into propositions.Not marked
Nested QuantifiersWhy ∀x ∃y and ∃y ∀x are different claims.Not marked
Negating Quantified StatementsPush the negation inward; every quantifier flips.Not marked
Rules of InferenceValid argument forms, and the two fallacies that mimic them.Not marked
Direct ProofAssume the hypothesis, derive the conclusion, write it for a reader.Not marked
Contraposition and ContradictionTwo indirect techniques, and when each is the right one.Not marked
Cases, Counterexamples, and Writing a ProofExhaustive cases, single counterexamples, and the standard a proof must meet.Not marked
Recommended background
School algebra is enough.
Practice suggestions
Work forward. “Logical Equivalence” assumes you can build a truth table; “Contraposition and Contradiction” assumes you know what the contrapositive is and why it is equivalent.
Use the labs adversarially. Most of them let you type your own formula or edit the predicate. The fastest way to understand a claim is to spend two minutes trying to make it false and finding out you cannot.
Write the proofs out. “Rules of Inference” ends with an argument to check, and “Direct Proof”, “Contraposition and Contradiction” and “Cases, Counterexamples, and Writing a Proof” each end with a claim to prove yourself. Reading a proof and producing one are different skills, and only the second transfers to the rest of the path.
Do not be put off by the continuity and convergence definitions in “Nested Quantifiers” and “Negating Quantified Statements”. They are there because they are the hardest quantifier strings most people ever meet, and the point of those lessons is that you can read and negate them mechanically without knowing what they mean. Nothing on this path needs the calculus.
What it does not cover
Formal proof systems. This course teaches proof as mathematicians write it — rigorous prose — not natural deduction trees, sequent calculus, or a machine-checkable proof assistant.
Completeness and soundness of first-order logic, model theory, and Gödel's incompleteness theorems. Those are the subject of a logic course; this is the logic a discrete mathematics course needs.
Fuzzy, modal and intuitionistic logics. Everything here is classical and two-valued: every proposition is either true or false, and p ∨ ¬p always holds.