[HD] EECS3342 F26 - 2026-11-12 (Thursday) - Lecture 17
Overview
The lecture develops Event-B refinement from abstract model M0, which counts cars in an island-bridge compound with N, to concrete model M1, which separates traffic into A, B, and C. It derives ML_out guards from the abstract condition N < D and linking invariant A + B + C = N, explains why concrete guards must imply abstract guards, and outlines the guard-strengthening proof obligation using the models’ axioms and invariants.
Key takeaways
- The linking invariant A + B + C = N lets M1 translate M0’s capacity guard N < D into the concrete guard A + B < D when ML_out also requires C = 0.
- The safety invariant A = 0 or C = 0 and the ML_in guard C > 0 together imply A = 0, so a separate A = 0 guard may be redundant if that implication is formally proved.
- A concrete refinement guard must imply its abstract counterpart, H ⇒ G; otherwise M1 could enable an event that M0 disables and thereby introduce new behavior.
- Complete before-after predicates include unchanged-variable conditions: ML_in changes C but preserves A and B, while ML_out changes A but preserves B and C.
- In the predicate example x > 0 implies x ≥ 0, so the strict inequality is stronger; true is weakest and false strongest in the implication-based ordering.
- The ML_out guard-strengthening proof draws on D ∈ ℕ, D > 0, N ∈ ℕ, N ≤ D, M1’s typing and safety invariants, the linking invariant, and both concrete guards.
Chapters
- For M0, alternative inference paths can produce different unprovable sequences, and the chosen failure should guide a realistic model correction.
- A proposed condition that the number of cars in the island-bridge compound is always greater than zero is invalid because zero cars is possible.
- The first refinement splits the compound into an island and a bridge, represented by concrete variables A, B, and C.
- M1 types A, B, and C as natural numbers, each greater than or equal to zero.
- Linking invariant 14 connects abstract and concrete states with A + B + C = N.
- Safety invariant 15, A = 0 or C = 0, prevents traffic in opposing directions from meeting on the bridge.
- ML_out represents a car moving from the mainland onto the bridge, so its action increments A by one.
- The first safety guard is C = 0, which rules out cars simultaneously moving from the bridge toward the mainland.
- The guard’s purpose is to prevent opposing traffic from occupying the one-way bridge at the same time.
- M0 enables ML_out only when its abstract count satisfies N < D, where D is the capacity limit.
- Combining N < D with linking invariant 14 and the ML_out guard C = 0 gives A + B = N.
- Substitution yields the concrete capacity guard A + B < D, showing how M1 guards derive from abstract guards and invariants.
- ML_in moves a car from the bridge back to the mainland and decrements C, so its guard must include C > 0.
- The class considers whether ML_in also needs A = 0 to prevent opposing traffic on the bridge.
- Given C > 0 and safety invariant 15, A = 0 follows; the proposed proof uses disjunction-left reasoning to establish whether the extra guard is redundant.
- The abstract model M0 tracks N, while the concrete model M1 tracks A, B, and C; the example sets capacity D to 2.
- After initialization, both models have zero-valued state, and linking invariant 14 holds because 0 + 0 + 0 = 0.
- The transition comparison checks whether corresponding states remain linked as events execute.
- From the initial state, abstract ML_out changes N from 0 to 1 while concrete ML_out changes A from 0 to 1.
- B and C remain zero, so the post-state satisfies linking invariant 14: 1 + 0 + 0 = 1.
- The example illustrates that corresponding abstract and concrete event executions should produce related post-states.
- For concrete ML_in, the explicit action C′ = C − 1 must be accompanied by unchanged-variable conditions A′ = A and B′ = B.
- For ML_out, A′ = A + 1 while B′ = B and C′ = C.
- Concrete event actions describe M1 variables only; abstract N is not included in an M1 before-after predicate.
- In refinement proof obligations, V and V′ denote abstract variables, while W and W′ denote concrete variables; here they correspond to N and A, B, C.
- I denotes abstract invariants, which use abstract variables and constants; J denotes concrete invariants, which can also include abstract variables through linking invariants.
- G represents an abstract event guard, H a concrete guard, and E and its concrete counterpart represent event effects.
- Invariant preservation for M0 remains relevant, but the additional invariant-preservation obligations for refinement are treated separately.
- Concrete invariants must be consistent with the earlier model’s invariants, a topic reserved for a later class.
- The lecture introduces guard strengthening as the main new refinement concept and advises reviewing its proof before the next class.
- If P implies Q, P is stronger than Q because every value satisfying P also satisfies Q, while Q may allow more values.
- For P(x) defined as x > 0 and Q(x) as x ≥ 0, P implies Q, but Q does not imply P because Q also allows zero.
- True is the weakest predicate because every value satisfies it; false is the strongest because no value satisfies it.
- For corresponding events, guard strengthening requires H ⇒ G: the concrete guard must imply the abstract guard.
- This means M1 cannot enable an event in a state where M0 disables its abstract counterpart.
- Reversing the implication could let concrete ML_out occur under a condition forbidden by M0, introducing behavior that the abstract model does not permit.
- The ML_out obligation uses axioms D ∈ ℕ and D > 0, plus abstract invariants N ∈ ℕ and N ≤ D.
- Its concrete invariant hypotheses include A, B, and C in ℕ, linking invariant A + B + C = N, and safety invariant A = 0 or C = 0.
- The concrete guards A + B < D and C = 0 must jointly entail the abstract guard N < D.
- A parallel guard-strengthening obligation for ML_in is provided as practice, using the relevant axioms, invariants, and guards.
- The slides contain proof sequences and inference-rule references; students are advised to hide the hints and select rules independently.
- Written Test 2 coverage is announced through slide 58, including inference-rule application, proof-obligation generation, and the M0 invariant work.
Transcript excerpt
0:05 All right, let's now uh do a quick recap, okay? And then we'll move on with refinement number one. So last time we actually revisit this first attempt for initial model M0 and we said that when we try to prove about dela freedom from this particular sequence here we can either do eqlr or eql and then from each of these we will be able to arrive two different um provable sequence. One of them will be n larger than zero the other one will be d larger than zero. So these are both mathematically valid unprovable secret. You might arrive by applying different inference rule. However, we have to judge which one we want to use to go back to the original model and fix it.
0:53 Right? That's something we kind of talked about last time and we kind of did a justification and this one here doesn't seem to be realistic. You cannot say the number of cars in the island compound bridge uh the uh island bridge compound should always be greater than zero. It could be zero, right? It's definitely possible, right? We talk about it. So please review it. And then we also talk about if you go for this particular unprovable sequence, how can we interpret that and go back to the original model and fix it? And when once we fix the model, we will be able to regenerate the proof obligation. So you want to make sure for written test number two, you should be able to know how to apply the inference rule and also if I ask you about a particular proof obligation, you should know how to generate a sequence accordingly. Right? So I think uh written test uh written
1:41 test number two is also very relevant to
This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.
In this course
Related notes
Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Jackie Wang.