[HD] EECS3342 F26 - 2026-10-29 (Thursday) - Lecture 13
Overview
Jackie Wang develops a proof workflow for formal-model obligations: read an inference rule as a justification for replacing a goal with simpler obligations, discard irrelevant hypotheses using monotonicity, and finish each proof branch with an exactly matching axiom. He works through invariant preservation for an M_out event, explains how OR_L splits a disjunctive hypothesis into independent branches, and introduces Peano arithmetic rules; he also notes that Written Test 2 is scheduled for November 18 and will include the covered inference rules.
Key takeaways
- MON is a sound way to simplify a proof sequence by dropping irrelevant hypotheses, but those hypotheses cannot simply be ignored when matching another rule.
- Inference-rule matching is exact: the M_out example must first be reduced to the single hypothesis that n is natural before P2 can prove that n + 1 is natural.
- OR_L converts a hypothesis P or Q into two separate proof obligations, and both the P case and the Q case must succeed.
- Proofs may branch into trees, but every leaf must terminate in an axiom rule; recursive rules are intermediate steps.
- For Written Test 2 on November 18, students will receive the covered inference rules in a PDF, so the priority is learning how to recognize and apply each rule.
Chapters
- Jackie Wang says TAs are grading the single short-answer question from Written Test 1 across 81 submissions, with results expected by the following Thursday or Tuesday at the latest.
- Written Test 2 is scheduled for November 18, about three weeks after this October 29 lecture, and will cover additional bridge-controller material.
- Lab 3 is due the following Wednesday; students can inspect programming-test submissions during the Wednesday lab review from 1:30 to 3:30 p.m.
- Wang revisits how model changes, such as adding an invariant or event or changing a guard, affect generated proof obligations.
- With two events and two invariants, invariant preservation generates four obligations; the class works through obligation 1 for M_out.
- The example collects axioms, pre-state invariants, the event guard, and the selected post-state invariant into a single proof sequence.
- An inference rule has a name, antecedents above a horizontal bar, and a consequence below it.
- To prove the consequence, it is sufficient to prove the antecedent obligations, which may be one sequence or several.
- A rule with no antecedents is an axiom rule: its consequence is accepted as true by definition.
- The MON rule allows a proof to use fewer hypotheses while keeping the same goal.
- H1 and H2 represent groups of hypotheses, not necessarily single predicates; the proof can drop one group judged irrelevant.
- Wang presents monotonicity as a common early step because generated obligations often contain more hypotheses than a particular goal needs.
- A sequence, written as hypotheses turnstile goal, is the implication to be proved; it does not have a rule name.
- An inference rule is a licensed proof step that rewrites a consequence into its antecedent obligations.
- A proof may use multiple valid rule orders, while each individual rule's formal pattern must still be respected.
- For the M_out invariant-preservation example, the goal concerns whether n + 1 is a natural number.
- Wang recommends identifying the goal's relevant variables and then selecting hypotheses that can actually help establish it.
- The hypothesis that n is a natural number is relevant to the goal, while predicates about other variables can be discarded if they do not contribute.
- Monotonicity reduces the example to the sequence n is a natural number, turnstile n + 1 is a natural number.
- The reduced sequence matches the P2 successor rule, which establishes that the successor of a natural number is also natural.
- Applying P2 directly to the original sequence is invalid because its hypotheses do not match the rule exactly; irrelevant hypotheses must first be removed with MON.
- A complex proof can begin with many hypotheses, retain only a relevant subset through monotonicity, and then apply further inference rules.
- A proof branch is complete when its final sequence matches an axiom rule's consequence and required hypotheses.
- Axioms act as base cases; recursive inference rules make progress toward those base cases.
- OR_L applies when a disjunction appears among the hypotheses to the left of the turnstile.
- The rule turns one sequence containing P or Q into two independent obligations: prove the goal assuming P, and prove it assuming Q.
- Both branches must be discharged; completing one branch can earn credit even if the other branch remains incomplete.
- When OR_L splits P or Q, the goal is repeated in each branch, once under P and once under Q.
- Any other hypotheses, represented as H, are copied into both branches; H can also be empty.
- The branches are independent, so success under only one disjunct is not enough to prove the original sequence.
- Wang illustrates OR_L with a reactor whose reliability must be established under either normal temperature or high temperature.
- The normal-temperature branch proves that the reactor remains functional; the high-temperature branch proves that its shutdown system operates.
- The example emphasizes that safety under a disjunctive operating condition requires proving both cases.
- The course site has a first inference-rule reference sheet under the bridge-controller notes, with two additional sets planned later.
- For Written Test 2, Wang says the covered rules will be provided in a PDF; students do not need to memorize them but should learn to apply them.
- The sheet distinguishes green axiom rules, which have no antecedents, from red recursive rules that advance a proof.
- P1 establishes that zero is a natural number, while P2 establishes that if n is natural, then n + 1 is natural.
- The arithmetic rules cover incrementing and decrementing inequalities; Wang recommends reasoning through boundary conditions rather than memorizing them blindly.
- For a less-than-or-equal condition, splitting into strict-less-than and equality cases can make a decrement argument easier to verify.
- Proof branches ultimately end with an axiom rule, while recursive rules are used along the way; the remaining rules are scheduled for the next class.
Transcript excerpt
0:05 All right. So, I'm going to meet with the TA tomorrow Friday about grading the only short answer question for your written test one. I got two TAs to really grade the 81 submissions. I'm hoping that they can get it done. If not by next Thursday's class, for sure by the Tuesday's class after. But, I'll keep you guys posted. Well, I'll just ask them to see if they can make it priority to make it quick. I know the drop deadline is coming the week after, but it's a compulsory course. I think uh most likely everybody will just stay, which is good. Okay. But, I'll give you I'll keep you posted. And the only scheduled test that's left for the course is right here. Okay? If you look at the semester calendar here, okay, let's now have a quick look ahead.
0:53 So, we are now here on the 29th of October. We're going to do lecture 13 today. And your written test number two will be November 18th. So, it will be about 1 2 3 about 3 weeks away 3 weeks away. So, we definitely going to cover many more materials related to bridge controller, and then we'll cover that in the written test two. I'll keep I will release the guide and practice question in advance at least 1 week. So, you can also take a look. Exam, I believe the schedule has been released. You can check. I'm going to put a time in my iPad notes maybe next time. I just didn't have time to check today. But, you can definitely check. Okay? And then we can definitely schedule maybe something during the exam period maybe to help you review or some extended office hour. I'll keep I'll keep you posted.
1:42 Hello. Are you guys in 3342?
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.