Proving Program Correctness: Assertions and Loop Invariants
Program correctness links execution to explicit assumptions and guarantees. An assertion is a logical predicate describing a program state.
Summary
Program correctness links execution to explicit assumptions and guarantees. An assertion is a logical predicate describing a program state. A Hoare triple states that execution of command from a state satisfying will satisfy if execution terminates.
| Concept |
|---|
🧠 Key Concepts
- Assertions
- Hoare Triples
- Assignment Rule
- Invariant Initialization
- Invariant Maintenance
- Exit Obligation
- Partial Correctness
- Total Correctness
- Loop Variants
🧠 Quick Check
See what you remember from the summary.
Which best describes the guarantee expressed by a Hoare triple ?
🧠 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.
Proving Program Correctness: Assertions and Loop Invariants
📘 Overview Program correctness connects a program's execution to explicit preconditions and postconditions. Assertions describe required program states, while loop invariants support proofs across any number of iterations. Total correctness additionally requires a proof of termination.
🧠 Key Idea A loop invariant must hold before the loop, survive every iteration, and imply the required postcondition when the loop exits. These obligations establish partial correctness; a separate termination argument establishes total correctness.
⚔️ Core Details: - Hoare triple: means command , started in a state satisfying precondition
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.