CS2050 L02 Laws of Thought
Watch on YouTube →
Overview
Abrahim Ladha shows how propositional logic turns uncertain claims into deductions, solving a knights-and-knaves puzzle with variables, implications, and truth tables. He then defines logical equivalence by identical truth tables and develops laws of thought, including De Morgan’s laws, absorption, implication rules, and biconditional identities, finishing with a formal proof that (P ∧ Q) → (P ∨ Q) is a tautology.
Key takeaways
- In a knights-and-knaves puzzle, encode both what a person says and whether they tell the truth: A’s claim that B is a knight yields P → Q when A is truthful and ¬P → ¬Q when A lies.
- Truth tables provide a mechanical way to solve finite constraint problems: with P meaning A is a knight and Q meaning B is a knight, the lecture’s two claims leave only P = false, Q = false.
- Logical equivalence is defined by identical truth-table columns, which justifies rewrites such as P → Q ≡ ¬P ∨ Q even when the English phrasing looks different.
- Truth tables grow exponentially: n propositional variables require 2ⁿ rows, motivating reusable laws such as De Morgan’s, distributivity, and absorption.
- A biconditional P ↔ Q requires both implications, while its negation is exclusive or: exactly one of P and Q is true.
- A formal equivalence proof should show each intermediate formula and name the single law used at each step, as in the derivation that (P ∧ Q) → (P ∨ Q) is a tautology.
Chapters
- Homework 1 has four problems, is due Friday, and can be submitted handwritten or with the LaTeX template.
- Canvas hosts homework files, GradeScope handles submissions, and a syllabus quiz allows unlimited retakes.
- The lecture applies propositional logic to deduction rather than treating logic as abstract symbol manipulation.
- Knights always tell the truth and knaves always lie, with every person belonging to exactly one type.
- Person A claims that B is a knight; person B claims that A and B are opposite types.
- The task is to identify both people’s types without assuming either spoken claim is true.
- Let P mean A is a knight and Q mean B is a knight; ¬P and ¬Q then mean they are knaves.
- A’s spoken claim is Q, but the claim’s truth depends on whether A is a knight.
- Ladha emphasizes that a proof should make deductions objective and mechanistic, not rely on a guess that happens to fit.
- A’s truthfulness yields P → Q, while A’s lying yields ¬P → ¬Q; together these conditions encode the relationship between A’s type and claim.
- B’s claim that they are opposites is represented by (P ∧ ¬Q) ∨ (¬P ∧ Q).
- B’s type is tied to the truth of that claim using a biconditional: B is a knight exactly when the opposite-types statement is true.
- Two variables P and Q produce four assignments: TT, TF, FT, and FF.
- Ladha evaluates A’s and B’s constraints row by row, then conjoins them to retain only assignments where both constraints hold.
- The surviving assignment is P = false and Q = false, so both A and B are knaves.
- A’s false claim that B is a knight fits B being a knave; B’s false claim that they are opposites fits both being knaves.
- A truth table with no true rows indicates that the constraints have no solution; multiple true rows indicate multiple solutions.
- Ladha connects the puzzle approach to Robert Smullyan’s collection of logic problems, where formal reasoning extracts answers from sparse information.
- With n propositional variables, a full truth table has 2ⁿ rows; three variables already require eight rows.
- Ladha compares propositional laws to arithmetic rules such as a(b + c) = ab + ac, which apply without knowing particular values.
- He argues that intuition alone can mislead, citing the often-confusing case where P → Q is true whenever P is false.
- Two propositions are defined as equivalent when their truth tables have identical values in every row.
- The conditional-disjunctive equivalence is P → Q ≡ ¬P ∨ Q, verified by comparing their truth-table columns.
- The example “if you study, then you pass” has the same truth conditions as “you do not study or you pass.”
- Identity laws include P ∧ T ≡ P and P ∨ F ≡ P; domination includes P ∨ T ≡ T and P ∧ F ≡ F.
- Idempotence gives P ∧ P ≡ P and P ∨ P ≡ P, while double negation gives ¬¬P ≡ P.
- Commutativity allows swapping P and Q, and associativity allows regrouping expressions such as (P ∧ Q) ∧ R.
- The distributive identities are P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R) and P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R).
- Ladha uses shirt-and-pants choices to illustrate how one shirt paired with either of two pants corresponds to a disjunction of outfits.
- De Morgan’s laws state ¬(P ∧ Q) ≡ ¬P ∨ ¬Q and ¬(P ∨ Q) ≡ ¬P ∧ ¬Q; Augustus De Morgan is credited with their symbolic formulation.
- Absorption gives P ∨ (P ∧ Q) ≡ P and P ∧ (P ∨ Q) ≡ P.
- For the first identity, if P is true the whole expression is true; if P is false, the conjunction is false and the whole expression remains false.
- Ladha notes that absorption can also be derived from other Boolean laws, including distributivity.
- The conditional-disjunctive equivalence rewrites P → Q as ¬P ∨ Q, and contraposition gives P → Q ≡ ¬Q → ¬P.
- Combining consequences with the same premise gives (P → Q) ∧ (P → R) ≡ P → (Q ∧ R).
- If P → R and Q → R, then (P ∨ Q) → R: either premise is sufficient to reach the shared conclusion.
- Ladha distinguishes allowed proof rules from useful derived identities, emphasizing that a formal proof applies one specified law at a time.
- P ↔ Q is equivalent to (P → Q) ∧ (Q → P), and also says P and Q are either both true or both false.
- The negation of P ↔ Q holds exactly when one proposition is true and the other false, represented by (P ∧ ¬Q) ∨ (¬P ∧ Q), or exclusive or.
- P ∨ ¬P is the law of excluded middle, while P ∧ ¬P is a contradiction; Ladha also distinguishes equivalence between formulas from the biconditional proposition inside a formula.
- Ladha proves that (P ∧ Q) → (P ∨ Q) is always true by rewriting the implication with conditional-disjunctive equivalence.
- The derivation applies De Morgan’s law, associativity, and commutativity to group ¬P with P and ¬Q with Q.
- Each negation-disjunction pair becomes a tautology by excluded middle, and domination reduces the final expression to true.
Transcript excerpt
0:01 Test tank. Test tank. All right, let's get started. This is CS2050 uh lecture uh O2. Um so I'm going to start recording the lectures mostly because I have a YouTube playlist. It's kind of old. Uh I was supposed to record the first lecture. A computer, you know, it doesn't work. So we're going to start recording from this lecture. So if you're following along on YouTube or whatever, you're going to miss the first lecture. But you know, we're all here in person, so it doesn't really matter. Um, logistics homework one has been released already. It's due Friday, so that's like two days from now. Today's already Wednesday. There's just four problems. There's also a latex template. If you want to do it, you can handr write it. That's no problem. Um, submissions are on grade scope, but the files themselves are released on Canvas. Um, I'm also going to release a syllabus quiz today. It's like unlimited retakes. It's just to make sure you know how the quizzes
0:49 work. It's pretty easy, right? Just like what is the syllabus? That's the first question on the quiz or something like this, right? Um, let's see. Logistics. TAs are still deciding their office hours. Um they're still adding and dropping their own classes. So they can't promise uh anything specific for this week except Friday from 10 to 2 p.m. in the office hours room. There will be they promise to hold office hours during that time. Um once their schedules are fixed next week, then there'll be like a Google calendar. You can see the the specific TAs have specific hours or something. But effectively, if you just go to the TA office hour room, which is on the second floor, it's got the name 2050 on it.
This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.
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, Abrahim Ladha.