[HD] EECS3342 F26 - 2026-11-17 (Tuedsay) - Lecture 18
Overview
The lecture reviews Event-B refinement proof obligations for the written test, focusing on why a concrete guard H must imply its abstract counterpart G and how refinement preserves invariants. Using abstract model M0 with variable n and concrete model M1 with variables a, b, and c, it works through guard strengthening, invariant-preservation proofs, and a commuting diagram connecting abstract and concrete transitions. It then introduces new island events that extend the concrete car-flow model with bridge-to-island and island-to-bridge movements.
Key takeaways
- Guard strengthening is the implication H ⇒ G: every concrete-enabled state must also enable the abstract event, so refinement may remove behaviors but cannot introduce new enabled behavior.
- For M_out, the concrete guard a + b < d relies on a + b + c = n and c = 0 to imply the abstract guard n < d; replacing < with ≤ incorrectly enables the concrete event when n = d.
- Invariant preservation for M1 combines axioms, abstract invariants, concrete and linking invariants, and the concrete guard; five invariants across two old events produce 10 proof obligations.
- A linking-invariant proof must apply the post-state substitutions from both models, since a relation such as a + b + c = n contains concrete variables and abstract variable n.
- A commuting diagram captures refinement simulation: linked pre-states take corresponding transitions and must end in post-states that still satisfy the linking invariant.
- The new island events extend the concrete model without abstract counterparts: I_in transfers one car from a to b, and I_out transfers one from b to c.
Chapters
- For the next-day written test, students need working ECS and PPY Passport logins and access to eClass.
- Two reference documents will be provided: an Event-B syntax summary and inference rules 1 and 2.
- Lab 4 is forthcoming, and its material is expected to be relevant to the later exam.
- H is the guard of an event in concrete refinement model M1; G is the corresponding guard in abstract model M0.
- The proof obligation is H implies G, meaning every state that enables the concrete event also enables its abstract counterpart.
- In a state-set picture, the states satisfying H must lie inside the states satisfying G; the guards may be equivalent, but G commonly permits additional states.
- States satisfying both H and G are cases where the concrete and abstract events are both enabled.
- States satisfying G but not H are allowed: refinement may remove abstract behaviors, provided it does not introduce new concrete behavior.
- States where G is false must also have H false; this is the contrapositive, not G implies not H, of guard strengthening.
- For the abstract M_out event, G is n < d; the correct concrete guard is a + b < d.
- The linking invariant a + b + c = n and concrete guard c = 0 establish that a + b < d implies n < d.
- Changing the concrete guard to a + b ≤ d permits n = d, enabling M1 while the abstract M0 guard is false, so guard strengthening fails.
- For a concrete event, the proof context includes axioms A, abstract invariants I, concrete invariants J, and the concrete event guard H.
- Abstract invariants refer to abstract variables, while concrete invariants can include both concrete variables and linking relations such as a + b + c = n.
- With five concrete invariants and two refined old events, M_out and M_in, the lecture counts 5 × 2 = 10 invariant-preservation obligations.
- For M_out, the concrete guard includes a + b < d and c = 0; its action increments a while leaving b and c unchanged.
- For M_in, the guard requires c > 0; its action decrements c while leaving a and b unchanged.
- A linking-invariant goal must use both models' post-state effects: for example, M_out changes n to n + 1 as well as a to a + 1.
- The proof sequence can be written directly when the substitutions are clear, but deriving prime-variable goals first helps avoid using the wrong event's updates.
- The commuting diagram pairs abstract pre-state V and concrete pre-state W through a linking invariant involving both sets of variables.
- For a matched old event such as M_out, the abstract and concrete machines each take a corresponding transition.
- The diagram's goal is for the abstract and concrete post-states, V′ and W′, to remain related by the linking invariant.
- Before the paired transitions, the concrete event's guard must imply that the corresponding abstract event is enabled in the linked abstract state.
- The refinement relationship is described as the concrete transition being simulated by the abstract transition, or equivalently the abstract transition simulating the concrete one.
- This simulation account applies to matching old events; new events without an abstract counterpart require separate treatment.
- Invariant establishment checks the concrete model's invariants from the initialization event, using the model axioms as hypotheses.
- With five concrete invariants and one initialization event, the model requires 1 × 5 = 5 establishment proof sequences.
- Initialization assigns constants rather than referring to current state variables on the right-hand side.
- M0 contains abstract variable n and old events for cars entering and leaving the compound; M1 refines those events using concrete variables a, b, and c.
- M1 also adds island events, which have no corresponding event in M0.
- The example route is mainland exit, island entry, island exit, then mainland entry, showing how old and new events can interleave.
- The mainland-exit event increments a, while mainland-entry decrements c, representing the two directions of bridge travel.
- I_in moves a car from the bridge to the island by assigning a := a − 1 and b := b + 1.
- I_out moves a car from the island back to the bridge by assigning b := b − 1 and c := c + 1.
- The I_out requirement that a = 0 belongs in its guard, not its action; guard details are deferred to the next lecture.
Transcript excerpt
0:05 All right. So, your written test will be tomorrow. Just make sure you got your ECS login and also PPY passport work both working. You're going to need a e-class tomorrow. Uh something also important to let you know. Okay. For the inference rule, you will be given what we have covered so far. Uh I'll show you. Okay. So tomorrow in the written test as soon as you start you'll see two documents available to you. One will be the event B summary just in case you got asked to specify any eventb uh syntax and you will also see the inference rule number one and number two that we have covered so far. So before the exam I expect to cover just one more set of the inference rule. I believe either one or two more but that'll be it for the course. But for tomorrow the written
0:52 test two only two right just make sure to review them. So hopefully you don't have to re uh you don't have to kind of uh reference them as often. Okay, that can save you some time. All right, I think that'll be it. And then I think your very last lab, lab number four will be released pretty soon. Okay, enjoy it. I think so going to be something you can learn. Uh and then we'll cover that in the exam. Okay, I'll talk more about the exam when we get a little bit closer. Okay, we got still got two uh two and a half more weeks to go. Okay. All right, guys. Any questions? All right, sounds good. Okay, let's now cover some stuff. But what I would like you do to do uh like us to do is to revisit very quickly. Uh so slide number
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.