[HD] EECS3342 F26 - 2026-09-17 (Thursday) - Lecture 3

Overview

Jackie Wang reviews how English phrases such as “only if,” “necessary,” and “unless” encode propositional implication, then introduces predicate logic using Rodin-style quantifier specifications. The lecture explains why universal quantification uses implication and existential quantification uses conjunction, demonstrates empty-range behavior and quantified examples, and begins proof strategies; it also covers course resources, labs, and preparation for the programming test.

Key takeaways

P → Q is false only when P is true and Q is false; this truth-table rule determines that “Q if P” means P → Q and “P only if Q” also means P → Q.
A biconditional P ↔ Q requires both P → Q and Q → P, so a proof must establish each direction rather than just one.
In Rodin-style predicate specifications, ∀i uses R(i) → P(i), while ∃i uses R(i) ∧ P(i); the different operators correctly handle values outside the range.
An empty range makes a universal claim vacuously true and an existential claim false, because there is no counterexample to find and no witness to provide, respectively.
To disprove a universal claim, give an in-range counterexample; to prove an existential claim, give one in-range witness satisfying the property.
When two quantified variables range over sets of sizes 3 and 8, evaluating the property requires checking 24 value pairs.

Chapters

0:00 Course Priorities: Labs, Rodin, and the Programming Test

Lab 1 is due the following Wednesday, and Jackie Wang recommends starting Lab 2 early as preparation for the course’s only programming test.
The programming test is scheduled before reading week; students have nearly three weeks to learn Rodin syntax and formal specification.
The course does not require manual proofs in Rodin, and a practice question and guide are expected by the following Thursday.

2:28 Using the Lecture Digest to Review Event-B Concepts

The lecture digest is available from the lecture site by selecting the compass icon for the September 15 class.
It provides key terms, definitions, common pitfalls, learning outcomes, suggested exercises, and links to relevant notes pages and recording timestamps.
The digest supplements rather than reproduces the lecture; students should use the recording to work through examples and note that the digest is text-only.

6:22 Reading English Implication Through the Truth Table

Jackie Wang presents several equivalent phrasings of P → Q: “Q if P,” “P only if Q,” “P is sufficient for Q,” and “Q is necessary for P.”
The implication is false only when P is true and Q is false; when P is false, the implication is true regardless of Q.
The truth table is the recommended way to identify which proposition is the antecedent and which is the consequent.

13:49 Translating “X Is Positive If Y Is at Most 10”

For “X is larger than zero if Y is less than or equal to 10,” the condition after “if” is the antecedent.
The correct formula is (Y ≤ 10) → (X > 0), not the implication in the reverse direction.
Wang recommends matching the sentence’s “if” structure to P → Q before inserting logical symbols.

16:21 Biconditional as Two Implications

P ↔ Q combines P → Q and Q → P, so both directions must hold.
“P only if Q” expresses P → Q, while “P if Q” expresses Q → P.
A proof by biconditional should establish both implications; this differs from rewriting expressions step by step using logical equivalences.

25:00 Why P Implies Q Is Equivalent to Q or Not P

The phrase “Q unless not P” describes the three truth-table rows in which P → Q is true.
The formula Q ∨ ¬P is false only when both alternatives are false, which gives P true and Q false—the implication’s sole false row.
Wang uses De Morgan’s law to show that ¬(Q ∨ ¬P) simplifies to P ∧ ¬Q.

32:14 Predicate Logic Adds Variables and a Universe of Discourse

Predicate logic extends propositional logic by allowing variables to range over a specified universe of discourse.
A variable’s range might be the integers, natural numbers, positive integers, or a bounded interval such as 1 through 10.
The lecture shifts from propositional implication to the universal and existential quantifiers.

33:15 Rodin Quantifier Syntax: Implication for All, Conjunction for Exists

Rodin-style specifications separate a variable’s range condition R from the property P being asserted.
Universal quantification is written as ∀i · R(i) → P(i): values outside the range do not matter.
Existential quantification is written as ∃i · R(i) ∧ P(i): a witness must satisfy both the range and the property.

42:22 A Set-Counting Preview: Choosing Three from Five

Wang poses a preview problem for the upcoming sets-and-relations material: how many size-three sets can be formed from {1, 2, 3, 4, 5}?
Examples include {1, 2, 3} and {1, 4, 5}; each valid set must contain exactly three elements.
The class is asked to think about a systematic counting method before the problem is revisited next week.

45:09 Empty Ranges Make Universal Claims True and Existential Claims False

An empty range makes R(i) false for every possible i, so no element can serve as an existential witness.
The existential form R(i) ∧ P(i) is false for every i when the range is empty, regardless of P.
The universal form R(i) → P(i) is true for every i because false implies anything; this is vacuous truth.

53:45 Integer, Natural-Number, and Positive-Number Ranges

The integers include negative values, zero, and positive values; the natural numbers in this course start at zero.
Positive integers begin at one, so the course distinguishes them from natural numbers by excluding zero.
Choosing the right range is a modeling decision that determines which values a quantified claim must cover.

56:22 Multiple Bound Variables Create Cartesian-Product Cases

A quantifier can bind more than one variable, such as i ranging over {1, 2, 3} and j ranging from 4 through 11.
There are 3 possible i-values and 8 possible j-values, so evaluating a property over both requires considering 3 × 8 = 24 combinations.
Knowing each variable’s range is essential both for evaluating a quantified statement and for later reasoning about functions.

59:34 Evaluating Quantified Claims with Counterexamples and Witnesses

For all natural numbers i, i ≥ 0 is true because zero and every larger natural number satisfy the property.
For all integers i, i ≥ 0 is false; i = −2 is a counterexample because it is an integer but does not satisfy the property.
For all integer pairs i, j, the claim i < j or i > j is false when i = j, such as i = j = 3.
Existential examples are shown with witnesses: i = 0 proves an appropriate natural-number claim, and (i, j) = (2, 3) satisfies i < j or i > j.

1:08:23 Nested Quantifiers and the Four Proof-or-Disproof Cases

Wang previews nested statements such as a universal quantifier whose property contains an existential quantifier, and vice versa.
The next topic organizes reasoning by whether the claim is universal or existential and whether the goal is to prove or disprove it.
Students are asked to interpret nested quantifiers before the class works through examples together.

1:10:19 Proof Strategies: Empty-Range Check and Existential Witness

To prove a universal statement, first check whether its range is empty; if it is, the implication is automatically true.
For a nonempty universal range, assume an arbitrary i satisfies R(i) and show that P(i) follows.
To prove an existential statement, provide a specific i that satisfies both R(i) and P(i).
The lecture ends with Lab 1 and Lab 2 reminders and a prompt to continue thinking about the size-three subsets of five numbers.

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.