Skip to content

1. Correctness ​

A program is correct if it produces correct output for every valid input.

  • Partial correctness: if the program terminates ⇒ output is correct
  • Termination: program always terminates

2. Hoare Triple ​

Notation:

p{S}q
  • p: initial assertion
  • q: final assertion
  • S: program

Meaning:

If p is true and S terminates, then q is true.

3. Partial Correctness ​

(p∧S terminates)⇒q

Note: does NOT guarantee termination.

4. Composition Rule ​

If:

p{S1}qq{S2}r

Then:

p{S1;S2}r

5. Conditional Statements ​

5.1 If (no else) ​

text
if condition then S

Rule:

(p∧condition){S}q(p∧¬condition)⇒q

Therefore:

p{if condition then S}q

5.2 If-Else ​

text
if condition then S1 else S2

Rule:

(p∧condition){S1}q(p∧¬condition){S2}q

Therefore:

p{if condition then S1 else S2}q

5.3 Rule of Inference: If – Else If – ... – Else ​

text
if condition1 then S1
else if condition2 then S2
...
else Sn

Rule ​

Để chứng minh:

p{if-else chain}q

Ta cần chứng minh các điều sau:

(p∧condition1){S1}q(p∧¬condition1∧condition2){S2}q(p∧¬condition1∧¬condition2∧condition3){S3}q⋮(p∧¬condition1∧⋯∧¬conditionn−1){Sn}q

Kết luận ​

p{if condition1 then S1 else if condition2 then S2 ⋯ else Sn}q

6. Loop Invariant (While) ​

text
while condition do S

Definition ​

p is a loop invariant if:

(p∧condition){S}p

While Rule ​

If:

(p∧condition){S}p

Then:

p{while condition S}(¬condition∧p)

7. Intuition ​

  • Invariant = something always true during the loop
  • When loop ends:
    • condition = false
    • invariant still true

⇒ derive final result

8. Proof Checklist for While ​

  1. Initialization:
p holds before loop
  1. Maintenance:
(p∧condition){S}p
  1. Termination:
¬condition∧p⇒q

Built with ❤️ and curiosity