Lecture on Indirect Proof in Logic
Introduction
- Instructor: Mark Doors
- Course Focus: Basics of Categorical, Propositional, and Predicate Logic
- Due to technical difficulties, lecture conducted in an old-fashioned way.
Indirect Proof Overview
- Definition: A technique used in deductive proof.
- Purpose: Prove a logical argument is valid by assuming the negation of the conclusion.
- Relation to Indirect Truth Table Method: Assumes invalidity; if contradiction arises, argument is valid.
Key Concepts
Review of Deductive Proofs
- Goal: Prove logical argument for the deduction of a conclusion.
- Sequence Lines: Each line is valid, except conditional proofs.
Indirect Truth Table Method
- Assumes invalidity and deduces conclusion.
- Contradiction implies validity; no contradiction implies invalidity.
Indirect Proof Method
- Related to indirect truth table method.
- Assumes opposite of a valid conclusion.
Steps for Indirect Proof
- Assume the opposite of what you need to prove.
- Write all assumptions and deductions.
- Discover a contradiction (e.g.,
B and not B).
- Discharge the proof and conclude the opposite of the assumption.
- Apply basic rules similar to conditional proofs.
Examples of Indirect Proof
Example 1
- Problem:
A or B then C and D, if C then not D, conclusion: not A.
- Process:
- Assume
A.
- Derive contradiction
D and not D.
- Discharge and conclude
not A.
Example 2
- Problem:
S, conclusion: T or not T.
- Use indirect proof assuming
not (T or not T) leading to a contradiction.
Example 3
- Problem:
if L then not M then N and O, not N and P, conclusion: if L then M and P.
- Process:
- Use conditional and indirect proofs to derive
M and P.
Example 4 (From Homework)
- Problem:
if C and D then E, if D and E then F, conclusion: C and D then F.
- Approach: Use conditional proof instead of indirect proof.
Important Notes
- Conditional vs Indirect Proof: Choose based on the goal and structure of the problem.
- Contradiction Discovery: Doesn't have to involve the same variables as assumption.
- Discharging Proofs: Once a sequence is discharged, previous lines cannot be used.
Conclusion
- Indirect proof is a powerful technique in logic, akin to a "nuclear option".
- Useful when direct methods are not apparent.
- Encouraged to reach out if pen-and-paper method is preferred for online sessions.
Note: Apologies for the technical issues during this lecture. Feedback on the format is welcomed. Thank you for your attention.