[HD] EECS3342 F26 - 2026-09-15 (Tuesday) - Lecture 2

Overview

Jackie Wang connects EECS 3342’s Event-B and Rodin work to formal methods, contrasting theorem proving in 3342 with model checking in the winter 4315 course. The lecture reviews propositional logic through practical Java examples: unlike logical conjunction, Java’s short-circuit operators make left-to-right evaluation and guard ordering essential for avoiding division-by-zero and array-index errors; it then derives implication rules and the contrapositive equivalence.

Key takeaways

Mathematical conjunction evaluates operands independently, so an earlier condition such as y ≠ 0 does not make x/y well-defined in the separate right-hand operand.
Java’s left-to-right short-circuit operator && can make a condition a runtime guard, but only when safety checks occur before the expression they protect.
For array access, the safe condition order is i >= 0 && i < A.length && A[i] > 10; checking only i < A.length still allows negative indices.
EECS 3342 focuses on theorem proving with Event-B and Rodin, while winter-course EECS 4315 introduces model checking with tools such as TLA+ and Java Pathfinder.
A model checker can return a counterexample trace when a property fails, but an oversized state space can prevent a result through the state-explosion problem.
An implication P ⇒ Q is false only when P is true and Q is false, and its contrapositive ¬Q ⇒ ¬P is logically equivalent to it.

Chapters

0:00 Course Reminders, Lab Deadlines, and Programming-Test Preparation

Jackie Wang directs students to the syllabus, lecture digests, notes template, and two open letters about effective study strategies.
Lab 1 is due the following Wednesday, Lab 2 the week after, and the single programming test is scheduled for November 7.
The programming test comes before reading week; Wang recommends prioritizing programming practice before shifting to conceptual study.

3:07 Finding EECS 3342 Materials in eClass

The lecture-site calendar identifies upcoming lectures, lab deadlines, and the November 7 programming test.
Students can access lecture digests through the compass icon and consult the optional textbook for additional reading.
An optional live session the next day offers help from TAs; Wang recommends asking him directly about course-policy questions.

5:08 Lab 2: Model the Celebrity Problem from Its English Description

Lab 2 asks students to formalize the celebrity problem by translating its English description into an Event-B specification.
Students should read the problem independently, sketch their interpretation, and explain how the provided context and machine together represent it.
The Event-B summary PDF explains mathematical notation and Rodin syntax; Wang warns that axiom four was especially difficult for students in the previous year.
Students should begin before every related concept is covered in lecture, submit before the deadline, and claim their lab credits.

9:57 Discrete Mathematics, Variables, and Universes of Discourse

The math review will span about 40 slides and several lectures, covering propositional logic, predicate logic, sets, relations, and functions.
Formal methods use discrete mathematics because computer systems operate on discrete states, commonly represented in binary.
A variable’s universe of discourse is its permitted range; examples include X ranging from 1 to 10 and Y from 1 to 5.

13:23 EECS 3342 Theorem Proving and Paper Proofs

EECS 3342 emphasizes theorem proving: use constants, axioms, variables, and invariants to establish desirable system properties.
Rodin may automatically discharge simple proof obligations, but complex models such as a bridge controller can require manual guidance.
The course practices paper proofs, including sequent-style proofs, rather than training students to interact extensively with automated provers.
Wang contrasts this with tool-specific proof interaction in systems such as Isabelle, which is beyond this course’s scope.

18:24 Model Checking, Counterexamples, and State Explosion

The winter 4315 course introduces model checking, an automated approach that checks whether a model satisfies a stated property.
Examples include TLA+, used by Amazon, and Java Pathfinder; a model checker explores possible variable states to find violations.
A result of “no” can include a counterexample execution trace that exposes how a property fails.
A checker may fail to terminate when the state space is too large, a challenge called the state-explosion problem; Wang recommends combining verification with testing.

24:49 Propositional Logic and Rodin Notation

In propositional logic, each proposition evaluates to true or false; predicate logic later adds variables with ranges and quantification.
Conjunction is true only when both operands are true, while disjunction is false only when both operands are false.
Rodin’s Event-B summary provides syntax for symbols such as negation, as well as set notation including singleton sets and set comprehension.

29:03 Why Java && and || Differ from Logical Conjunction and Disjunction

Mathematical conjunction is commutative and evaluates its operands independently; Java’s && evaluates left to right and may skip the right operand.
For Java conjunction, a false left operand makes the result false immediately, enabling short-circuit evaluation.
Logical formulas require each operand to be well-defined in isolation, whereas Java short-circuiting can prevent an unsafe expression from running.
Wang assigns students to work out the corresponding short-circuit rule for Java’s || operator.

35:59 Guarding Division: Why y ≠ 0 Works Differently in Logic and Java

The formula y ≠ 0 ∧ x/y > 1 is not well-defined as a mathematical conjunction if the division’s validity cannot rely on the first operand.
In Java, y != 0 && x/y > 1 checks the left side first and skips the division when y equals zero.
The condition y != 0 is a guarding constraint for the division on the right, preventing a division-by-zero exception.
The example shows why logical equivalence does not imply identical evaluation behavior in a programming language.

41:55 Array Bounds Checks Must Precede Array Access

For a Java array of length 10, checking i < A.length does not rule out negative indices before evaluating A[i].
If i is -2, the first test passes and A[-2] can throw an array-index-out-of-bounds exception; if i is 100, the first test fails and short-circuiting skips the access.
The safe ordering is i >= 0 && i < A.length && A[i] > 10, placing both bounds checks before the array access.
Replacing Java’s && with mathematical conjunction does not provide the same protection because the operands are treated independently.

50:24 Event-B Guards and the Course’s Implication Notation

Multiple guards on an Event-B event are implicitly conjoined, a fact that matters when reasoning about refinements and the bridge-controller example.
For this course, implication is written with a double arrow and “if and only if” with a double-headed equivalence symbol.
Wang asks students to review the chosen notation rather than rely on alternate arrow conventions from earlier math courses.

53:08 Implication Truth Table Through the Contract Analogy

For P ⇒ Q, P is the antecedent and Q the consequent; the contract analogy treats P as promised terms and Q as duties conditional on those terms.
The implication is false only when P is true and Q is false, the case where the promise applies but the duty is not fulfilled.
When P is false, the implication is true regardless of Q: without the promised terms, the contract has not been violated.
The truth table is useful because implications recur in function properties, relations, and later system specifications.

1:01:24 Zero and Identity Laws for Implication

The zero law of implication is false ⇒ P ≡ true for any proposition P.
The identity law is true ⇒ P ≡ P, so the consequent determines the result when the antecedent is true.
Wang notes that these laws can simplify proof obligations encountered later in the course.

1:05:25 English Forms of Implication, Converse, and Contrapositive

The statement P ⇒ Q can also be phrased as “Q if P,” “P only if Q,” “P is sufficient for Q,” or “Q is necessary for P.”
The inverse of P ⇒ Q is ¬P ⇒ ¬Q, while the converse is Q ⇒ P.
The contrapositive is ¬Q ⇒ ¬P; unlike the inverse and converse, it is logically equivalent to the original implication.
Wang postpones the five English phrasings for a truth-table walkthrough in the next lecture.

1:10:27 Equivalent-Style Proof of the Contrapositive Theorem

Wang proves P ⇒ Q ≡ ¬Q ⇒ ¬P by rewriting expressions in steps that preserve their meaning.
The proof begins with P ⇒ Q and applies the implication definition P ⇒ Q ≡ ¬P ∨ Q.
Commutativity of disjunction and double negation rewrite ¬P ∨ Q as ¬¬Q ∨ ¬P.
Applying the implication definition again yields ¬Q ⇒ ¬P; Wang identifies equivalent-style rewriting as one proof style used in the course.

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.