👁️‍🗨️Formal Logic I Unit 7 – Conditional and Indirect Proofs

Key Concepts and Definitions

• Conditional proof (CP) a method for proving a conditional statement by assuming the antecedent and deriving the consequent
• Indirect proof (IP) proves a statement by assuming its negation and deriving a contradiction
• Antecedent the "if" part of a conditional statement (p in "if p then q")
• Consequent the "then" part of a conditional statement (q in "if p then q")
• Contradiction a statement that is always false, often denoted as $\bot$
• Tautology a statement that is always true, often denoted as $\top$
• Modus ponens (MP) an inference rule that states if $p$ is true and $p \to q$ is true, then $q$ must be true
• Modus tollens (MT) an inference rule that states if $q$ is false and $p \to q$ is true, then $p$ must be false

Conditional Proof (CP) Basics

• CP is used to prove statements of the form $p \to q$
• Begin a CP by assuming the antecedent $p$ is true
• Aim to derive the consequent $q$ using valid inference rules and the assumption $p$
• If successful, the CP proves that $p \to q$ is true
• CP is often used when a direct proof is not apparent or straightforward
  • Example: proving $p \to (q \to r)$ by assuming $p$ and $q$, then deriving $r$
• The assumed antecedent is discharged at the end of the CP, meaning it is no longer an active assumption
• CP is a powerful tool for proving conditional statements in propositional and predicate logic

Indirect Proof (IP) Fundamentals

• IP, also known as proof by contradiction, is used to prove a statement by assuming its negation and deriving a contradiction
• Begin an IP by assuming the negation of the statement to be proved
• Use valid inference rules and the assumption to derive a contradiction (a statement that is always false)
• If successful, the IP proves that the original statement must be true
  • Example: to prove $p$, assume $\neg p$ and derive a contradiction
• IP relies on the law of excluded middle, which states that a statement is either true or false, with no other possibilities
• IP is useful when a direct proof or CP is not apparent or straightforward
• The assumed negation is discharged at the end of the IP, meaning it is no longer an active assumption
• IP is a powerful tool for proving statements in propositional and predicate logic, especially those involving negation

Rules and Strategies for CP and IP

• When using CP, focus on deriving the consequent using the assumed antecedent and valid inference rules
  • Example: if assuming $p$, look for ways to derive $q$ to prove $p \to q$
• When using IP, focus on deriving a contradiction using the assumed negation and valid inference rules
  • Example: if assuming $\neg p$, look for ways to derive both $q$ and $\neg q$ for some statement $q$
• Break down complex statements into simpler components and prove each component separately
• Use previously proven theorems and lemmas to help derive the desired conclusion
• Look for opportunities to use inference rules like modus ponens, modus tollens, and hypothetical syllogism
• Consider using proof by cases when the statement to be proved involves a disjunction
• Use proof by contraposition (proving $\neg q \to \neg p$ to prove $p \to q$) when appropriate
• Keep track of assumptions and discharged assumptions to ensure the proof is valid

Common Mistakes and How to Avoid Them

• Forgetting to discharge assumptions at the end of a CP or IP
  • Ensure all assumptions are properly discharged before concluding the proof
• Using an assumption outside its scope (e.g., using an assumption from one case in another case)
  • Keep track of the scope of each assumption and only use them within their valid scope
• Failing to prove all necessary components of a complex statement
  • Break down complex statements and ensure each component is proven
• Confusing the antecedent and consequent in a CP
  • Remember that the antecedent is assumed true, and the goal is to derive the consequent
• Deriving a contradiction in a CP instead of the consequent
  • If a contradiction is derived in a CP, the proof is not valid; the goal is to derive the consequent
• Forgetting to negate the statement to be proved in an IP
  • Always start an IP by assuming the negation of the statement to be proved
• Using invalid inference rules or fallacious reasoning
  • Ensure each step in the proof follows from valid inference rules and previously proven statements

Practice Problems and Examples

• Prove $p \to (q \to p)$ using CP
  • Assume $p$, then assume $q$, and derive $p$ (which was already assumed)
• Prove $\neg (p \land q) \to (\neg p \lor \neg q)$ using CP
  • Assume $\neg (p \land q)$, then use De Morgan's law to derive $\neg p \lor \neg q$
• Prove $p \to q$ using IP, given $\neg q \to \neg p$
  • Assume $\neg (p \to q)$, then derive a contradiction using the given statement and the definition of implication
• Prove $(p \to q) \land (q \to r) \to (p \to r)$ using CP
  • Assume $(p \to q) \land (q \to r)$, then assume $p$ and use modus ponens twice to derive $r$
• Prove $\neg (p \lor q) \to (\neg p \land \neg q)$ using IP
  • Assume $\neg (\neg (p \lor q) \to (\neg p \land \neg q))$, then derive a contradiction using De Morgan's laws and the definition of implication

Real-world Applications

• Conditional proofs are used in mathematics, computer science, and philosophy to establish the truth of conditional statements
  • Example: proving that if a number is even, then its square is also even
• Indirect proofs are used to prove statements by showing that their negation leads to a contradiction
  • Example: proving that there are infinitely many prime numbers by assuming there are only finitely many and deriving a contradiction
• CP and IP are essential for proving security properties in cryptography and computer security
  • Example: proving that a cryptographic protocol is secure against certain types of attacks
• Conditional and indirect reasoning are used in everyday decision-making and problem-solving
  • Example: "If I study hard, then I will get a good grade on the exam" (conditional reasoning)
  • Example: Proving a suspect's innocence by showing that assuming their guilt leads to a contradiction with the evidence (indirect reasoning)

Connections to Other Logic Topics

• CP and IP are closely related to the concepts of logical implication and equivalence
  • If $p \to q$ is true, then $p$ logically implies $q$
  • If $p \to q$ and $q \to p$ are both true, then $p$ and $q$ are logically equivalent
• CP and IP rely on the valid inference rules of propositional and predicate logic, such as modus ponens, modus tollens, and hypothetical syllogism
• The concepts of tautology and contradiction, which are central to IP, are also important in other areas of logic, such as Boolean algebra and model theory
• CP and IP are used in conjunction with other proof techniques, such as proof by cases, proof by contraposition, and mathematical induction
• The principles of conditional and indirect reasoning are fundamental to the study of formal logic and have applications in various fields, including mathematics, computer science, philosophy, and artificial intelligence