CS2050 L04 Deduction

Overview

The CS2050 lesson develops propositional deduction as a one-way process: an argument is valid when the implication from the conjunction of its premises to its conclusion is a tautology. It introduces core inference rules, demonstrates them in a formal proof and a 4×4 Sudoku example, explains why contradictions trigger the principle of explosion, and extends deduction to quantified statements with a formalization of the Socrates argument.

Key takeaways

A propositional argument is valid exactly when the implication from the conjunction of all its premises to its conclusion is a tautology; actual truth of the premises is a separate question.
Modus tollens, P → Q and ¬Q therefore ¬P, supports counterfactual reasoning as well as forward implication chaining.
Formal proofs need explicit, checkable steps: cite inference rules and source lines, and place the exact target conclusion on the final line.
The 4×4 Sudoku example formalizes elimination as disjunctive syllogism: from P1 ∨ P2 ∨ P3 ∨ P4 and ¬P1, ¬P2, ¬P3, derive P4.
In classical logic, accepting both P and ¬P permits deriving any Q through addition and disjunctive syllogism, which is why mathematical arguments require consistency.
Quantifier rules have important restrictions: universal generalization requires an arbitrary case, while existential instantiation introduces a fresh witness rather than an individually identified object.

Chapters

0:00 Inference as One-Way Deduction

The example “All men are mortal; Socrates is a man; therefore Socrates is mortal” illustrates an inference from premises to a conclusion.
Unlike propositional equivalences, deductions are generally one-way: the conclusion does not let you recover the original premises.
An argument is written as premises P1 through Pk, followed by a therefore sign and conclusion Q.

4:00 Argument Validity and the Tautology Test

Represent an argument with the implication (P1 ∧ ... ∧ Pk) → Q; it is valid when that implication is a tautology.
A false row in the implication’s truth table identifies a case where all premises hold but the conclusion fails.
A false premise can make an implication true in a particular valuation, but validity still requires the implication to be true across every valuation.
Validity concerns whether the reasoning follows its rules; soundness additionally requires the premises to be true.

9:00 Modus Ponens and Modus Tollens

Modus ponens has the form P → Q, P, therefore Q; a truth-table check confirms the premises cannot be true while Q is false.
Modus tollens has the form P → Q, ¬Q, therefore ¬P, as in inferring no car crash from the stated implication and the absence of its consequence.
The lecture connects modus tollens to contraposition, while treating each as a distinct step in a formal derivation.

14:48 Chaining Implications and Manipulating Disjunctions

Hypothetical syllogism combines P → Q and Q → R to conclude P → R without assuming P is true.
Disjunctive syllogism turns P ∨ Q and ¬P into Q, such as identifying Alice as the cake-bringer if either Alice or Bob promised and Bob did not.
Addition infers P ∨ Q from P, while simplification extracts either conjunct from P ∧ Q.
Conjunction combines separate premises P and Q into P ∧ Q.

20:14 Resolution and the Core Inference Toolkit

Resolution uses P ∨ Q and ¬P ∨ R to infer Q ∨ R by eliminating the complementary P and ¬P terms.
The named rules provide repeatable, mechanically checkable steps; a chain of valid steps can form a longer deduction.
In formal syntax, even an apparently interchangeable order may require an explicit law such as commutativity.

22:29 A Formal Proof from Three Premises to P

The example premises are (¬P ∨ ¬Q) → (R ∧ S), R → T, and ¬T; the goal is to derive P.
Apply modus tollens to R → T and ¬T to obtain ¬R, then use addition to form ¬R ∨ ¬S.
De Morgan’s law converts ¬R ∨ ¬S into ¬(R ∧ S); modus tollens with the first premise then yields ¬(¬P ∨ ¬Q).
De Morgan’s law and double negation simplify the resulting conjunction to P ∧ Q, and simplification leaves the required final line P.

31:08 Forward Proofs, Goal Planning, and Truth Tables

Each inference step should cite its rule and relevant earlier lines; the exact requested conclusion must appear alone on the final line.
A proof can omit irrelevant premises, and different valid sequences may reach the same conclusion.
Planning backward from a goal can help choose a route, but the written deduction proceeds through forward-valid steps.
Truth tables can verify propositional rules finitely; quantified rules need a different proof method when their domain may be infinite.

38:21 Sudoku as a Deduction Problem

A standard Sudoku requires each row, column, and highlighted square to contain the digits 1 through 9 without repeats.
The lesson simplifies the puzzle to a 4×4 grid using digits 1 through 4.
If a cell must contain one of 1, 2, 3, or 4, and its row or box rules out 1, 2, and 3, then the cell must be 4.
A conflicting set of entries can also reveal that a Sudoku configuration has no valid solution.

42:28 Proving the Sudoku Cell Must Be 4

Let P1, P2, P3, and P4 represent that the selected cell contains each respective digit; the first premise is P1 ∨ P2 ∨ P3 ∨ P4.
Use the Sudoku row, column, and 2×2 box constraints as premises ¬P1, ¬P2, and ¬P3.
Associativity groups the disjunctions into forms accepted by disjunctive syllogism, which eliminates P1, then P2, then P3.
The final deduction is P4, formally matching the quick Sudoku inference that the cell contains 4.

47:01 The Principle of Explosion

The principle of explosion states that a contradiction, P and ¬P, allows any proposition Q to be derived.
The displayed derivation uses addition to obtain ¬P ∨ Q from ¬P, then disjunctive syllogism with P to conclude Q.
Because Q is arbitrary, an inconsistent mathematical system can prove both statements such as 2 + 2 = 4 and its negation.
The lecture contrasts mathematical consistency with scientific disagreements that remain competing estimates rather than jointly accepted contradictions.

53:58 Universal Instantiation and Generalization

Universal instantiation derives P(c) from ∀x P(x) for an object c in the quantified domain.
Universal generalization moves from a case P(c) to ∀x P(x) only when c is arbitrary, not when it is a specially chosen object.
The two rules change a statement’s quantifier structure, so they are distinct syntactic inference steps.

57:53 Existential Instantiation and Generalization

Existential instantiation turns ∃x P(x) into P(c) for a fresh name c representing an existing witness.
The witness c can be used in further reasoning, such as discussing c + 1 if c represents a number.
Existential generalization derives ∃x P(x) from P(c), for example, moving from “2 is even” to “there exists an even number.”
An existential witness cannot be identified with Socrates or another known individual unless the premises justify that identification.

1:01:07 Formalizing the Socrates Deduction

Represent “All men are mortal” as ∀x(Man(x) → Mortal(x)), “Socrates is a man” as Man(Socrates), and the goal as Mortal(Socrates).
Universal instantiation specializes the first premise to Man(Socrates) → Mortal(Socrates).
Modus ponens combines that implication with Man(Socrates) to conclude Mortal(Socrates).
The proof distinguishes universal instantiation, which permits a named domain object such as Socrates, from existential instantiation, which introduces only a fresh witness.

Transcript excerpt

0:00 essentially saying >> all right let's get started uh this is CS 2050 the topic this is LO4 the topic are the rules of inference so what is uh this word mean inference or also you know like rational inquiry it's this thing that um a lot of people do uh across disciplines you know like lawyers uh math scientists as well even in sociology they perform some kind of version of this perhaps to different standards. Um but all these people have the ability to distinguish from what is considered like a a like a reasonable or

0:47 normal argument and one that is like kind of insane, right? So what where does this ability come from and what does what does this really mean for there to be an inference or deduction? Right? Consider the following sentences. Um, uh, all men are mortal. Socrates is a man. Therefore, Socrates is mortal. So, this is a deduction we could say here that exists in language. It is uh there's several observations we can make on it. First off, is it valid? Is this like a correct way to perform a deduction? Because we're working in in the context of languages, we're not

1:33 formalized this yet. We can just kind of look internally and say that sounds right. If it is true that all men are mortal and it is true that Socrates is a man, then from these two ideas, we may deduce a third idea that Socrates is oh, Socrates is mortal. Sorry. [snorts] But let's like have some more commentary on this. There's a there's a lot that's going on here. This is not necessarily the form of an equivalence as we've done with the laws of thought because we took two ideas and we're able to output a

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.