Proof by Cases and Counterexamples
Proof by cases establishes a claim by dividing its permitted inputs into exhaustive cases and proving the same conclusion in each case.
Summary
Proof by cases establishes a claim by dividing its permitted inputs into exhaustive cases and proving the same conclusion in each case. Every case uses the original assumptions together with its additional condition. Cases may overlap; complete coverage, not mutual exclusivity, is required.
| Method | Requirement | Outcome |
|---|---|---|
| Proof by cases | Cover every permitted input and establish the conclusion in each case | Proves the claim |
| Counterexample | Find one permitted input that violates the conclusion | Disproves a universal claim |
For integer parity, every integer is even or odd. If , then . If , then . With integer , both cases establish that is even.
🧠 Key Concepts
- Proof by cases
- Exhaustive case splits
- Overlapping cases
- Universal claims
- Conditional counterexamples
- Integer parity
- Algorithm correctness
- Testing limitations
🧠 Quick Check
See what you remember from the summary.
Which best describes an exhaustive case split in an algorithm correctness proof?
🧠 Flashcards Preview
Tap a card to reveal the definition.
Ready to quiz yourself?
Test what you remember with a full practice quiz on this note. Create a free account and start in seconds.
Full Notes
Read the original note content before deciding whether to save or study from it.
Proof by Cases and Counterexamples
📘 Overview Proof by cases establishes a claim by proving it under every possibility in an exhaustive case split. A counterexample disproves a universal claim by identifying one valid input for which the claim fails.
🧠 Key Idea A proof must cover every permitted input; a disproof of a universal claim needs only one permitted input that violates its conclusion. Checking several successful examples is not a proof.
⚔️ Core Details: - A case split is exhaustive when every input satisfying the original assumptions belongs to at least one case. - Each case must establish the same target conclusion using the original assumptions and that case's additional condition. - Cases may overlap; mutual exclusivity is not required. - Even case for an integer parity claim: gives
More ways to study when you copy this note
Copy this note into your library to unlock focused practice sessions and long-term review.
Answer all questions first, then see feedback at the end — the way real exams work.
Focuses each session on what you got wrong, not what you already know.
Full timed exam with all questions, no pausing, and results at the end. Built for board exam prep.
Part of 🌱 BSCS Year 1 — Computing & College Foundations
Browse this Review Set →More Computer Engineering notes
See all →More in Discrete Mathematics
See all →More from NoteLib
Browse NoteLib's public notes →Copy this note to your library and get the full Study Pack instantly — summary, key concepts, and practice quiz included.