👁️‍🗨️Formal Logic I Unit 6 – Natural Deduction in Propositional Logic

Key Concepts and Terminology

• Propositional logic deals with the logical relationships between propositions or statements that can be either true or false
• Propositions are declarative sentences that have a truth value (true or false) and are often represented by lowercase letters ($p$, $q$, $r$)
• Logical connectives join propositions to form compound statements and include symbols such as $\wedge$ (and), $\vee$ (or), $\rightarrow$ (if...then), $\leftrightarrow$ (if and only if), and $\neg$ (not)
• Truth tables display all possible combinations of truth values for a given set of propositions and help determine the validity of arguments
• Tautologies are formulas that are always true regardless of the truth values of their constituent propositions ($(p \vee \neg p)$)
• Contradictions are formulas that are always false regardless of the truth values of their constituent propositions ($p \wedge \neg p$)
• Logical equivalence occurs when two formulas have the same truth value for all possible combinations of truth values for their constituent propositions

Logical Connectives and Their Rules

• Conjunction ($\wedge$) represents "and" and is true only when both propositions are true ($p \wedge q$)
  • Commutative property allows the order of conjuncts to be swapped without affecting the truth value ($p \wedge q \equiv q \wedge p$)
  • Associative property allows the grouping of conjuncts to be changed without affecting the truth value ($(p \wedge q) \wedge r \equiv p \wedge (q \wedge r)$)
• Disjunction ($\vee$) represents "or" and is true when at least one of the propositions is true ($p \vee q$)
  • Inclusive disjunction allows for both propositions to be true
  • Exclusive disjunction (XOR) is true only when exactly one proposition is true
• Conditional ($\rightarrow$) represents "if...then" and is false only when the antecedent (left side) is true and the consequent (right side) is false ($p \rightarrow q$)
• Biconditional ($\leftrightarrow$) represents "if and only if" and is true when both propositions have the same truth value ($p \leftrightarrow q$)
• Negation ($\neg$) represents "not" and flips the truth value of a proposition ($\neg p$)
  • Double negation elimination states that two negations cancel each other out ($\neg \neg p \equiv p$)

Natural Deduction: Introduction and Elimination Rules

• Natural deduction is a proof system that uses introduction and elimination rules for each logical connective to construct valid arguments
• Conjunction introduction ($\wedge$I) allows the inference of a conjunction if both conjuncts have been proven separately
  • $\frac{p \quad q}{p \wedge q}$ ($\wedge$I)
• Conjunction elimination ($\wedge$E) allows the inference of either conjunct from a proven conjunction
  • $\frac{p \wedge q}{p}$ ($\wedge$E)
  • $\frac{p \wedge q}{q}$ ($\wedge$E)
• Disjunction introduction ($\vee$I) allows the inference of a disjunction if either disjunct has been proven
  • $\frac{p}{p \vee q}$ ($\vee$I)
  • $\frac{q}{p \vee q}$ ($\vee$I)
• Disjunction elimination ($\vee$E) allows the inference of a formula if it can be derived from each disjunct separately
  • $\frac{p \vee q \quad p \rightarrow r \quad q \rightarrow r}{r}$ ($\vee$E)
• Conditional introduction ($\rightarrow$I) allows the inference of a conditional if the consequent can be derived assuming the antecedent
  • $\frac{[p]^* \quad \vdots \quad q}{p \rightarrow q}$ ($\rightarrow$I)
• Conditional elimination or Modus Ponens ($\rightarrow$E) allows the inference of the consequent if the antecedent and the conditional have been proven
  • $\frac{p \quad p \rightarrow q}{q}$ ($\rightarrow$E)
• Biconditional introduction ($\leftrightarrow$I) allows the inference of a biconditional if both conditionals have been proven
  • $\frac{p \rightarrow q \quad q \rightarrow p}{p \leftrightarrow q}$ ($\leftrightarrow$I)
• Biconditional elimination ($\leftrightarrow$E) allows the inference of either conditional from a proven biconditional
  • $\frac{p \leftrightarrow q}{p \rightarrow q}$ ($\leftrightarrow$E)
  • $\frac{p \leftrightarrow q}{q \rightarrow p}$ ($\leftrightarrow$E)

Constructing Valid Arguments

• Begin by identifying the premises (given information) and the conclusion (the statement to be proven)
• Break down the conclusion into smaller, more manageable parts using the introduction and elimination rules
• Work backwards from the conclusion, applying the appropriate rules to introduce or eliminate connectives
• Use subproofs (temporary assumptions) when necessary to derive intermediate steps
  • Discharge assumptions when they are no longer needed using the appropriate introduction rules
• Ensure that each step in the proof is justified by a valid rule or a previously proven statement
• Double-check that the premises are sufficient to derive the conclusion and that no logical fallacies have been committed

Proof Strategies and Techniques

• Conditional proof (CP) is a technique used to prove a conditional statement by assuming the antecedent and deriving the consequent within a subproof
  • Discharge the assumption using the conditional introduction rule ($\rightarrow$I)
• Proof by contradiction (RAA, reductio ad absurdum) is a technique that assumes the negation of the desired conclusion and derives a contradiction, thereby proving the original conclusion
  • Assumes $\neg p$ and derives a contradiction ($q \wedge \neg q$)
  • Concludes $p$ by the principle of explosion (from a contradiction, anything follows)
• Proof by cases (PC) is a technique that breaks down a disjunction into its constituent cases and proves the desired conclusion for each case separately
  • Applies the disjunction elimination rule ($\vee$E) to conclude the desired result
• Indirect proof is a technique that proves a statement by showing that its negation leads to a contradiction or an absurdity
• Proof by equivalence is a technique that proves a biconditional by proving both conditionals separately
  • Uses the biconditional introduction rule ($\leftrightarrow$I) to conclude the biconditional

Common Mistakes and How to Avoid Them

• Affirming the consequent fallacy occurs when concluding the antecedent from the consequent and the conditional ($q, p \rightarrow q \therefore p$)
  • Avoid by recognizing that the conditional only guarantees the consequent if the antecedent is true, not vice versa
• Denying the antecedent fallacy occurs when concluding the negation of the consequent from the negation of the antecedent and the conditional ($\neg p, p \rightarrow q \therefore \neg q$)
  • Avoid by recognizing that the conditional does not specify what happens when the antecedent is false
• Begging the question (circular reasoning) occurs when the premise assumes the truth of the conclusion, making the argument circular
  • Avoid by ensuring that the premises are independent of the conclusion and do not rely on its truth
• Equivocation fallacy occurs when a term or phrase is used with multiple meanings within an argument, leading to an erroneous conclusion
  • Avoid by ensuring that terms are used consistently throughout the argument
• Undischarged assumptions occur when a subproof is not properly closed, and the assumption is not discharged using the appropriate introduction rule
  • Avoid by carefully tracking assumptions and ensuring they are discharged when no longer needed

Practice Problems and Examples

• Prove the validity of the argument: $p \rightarrow q, q \rightarrow r \therefore p \rightarrow r$
  1. $p \rightarrow q$ (premise)
  2. $q \rightarrow r$ (premise)
  3. $[p]^*$ (assumption)
  4. $q$ (Modus Ponens, 1, 3)
  5. $r$ (Modus Ponens, 2, 4)
  6. $p \rightarrow r$ (Conditional Introduction, 3-5)
• Prove the validity of the argument: $p \vee q, \neg p \therefore q$
  1. $p \vee q$ (premise)
  2. $\neg p$ (premise)
  3. $[p]^*$ (assumption)
  4. $\bot$ (contradiction, 2, 3)
  5. $q$ (explosion principle, 4)
  6. $[q]^{**}$ (assumption)
  7. $q$ (reiteration, 6)
  8. $q$ (disjunction elimination, 1, 3-5, 6-7)
• Prove the equivalence of $p \rightarrow (q \rightarrow r)$ and $(p \wedge q) \rightarrow r$
  • Prove $p \rightarrow (q \rightarrow r) \therefore (p \wedge q) \rightarrow r$
    1. $p \rightarrow (q \rightarrow r)$ (premise)
    2. $[p \wedge q]^*$ (assumption)
    3. $p$ (conjunction elimination, 2)
    4. $q \rightarrow r$ (Modus Ponens, 1, 3)
    5. $q$ (conjunction elimination, 2)
    6. $r$ (Modus Ponens, 4, 5)
    7. $(p \wedge q) \rightarrow r$ (conditional introduction, 2-6)
  • Prove $(p \wedge q) \rightarrow r \therefore p \rightarrow (q \rightarrow r)$
    1. $(p \wedge q) \rightarrow r$ (premise)
    2. $[p]^*$ (assumption)
    3. $[q]^{**}$ (assumption)
    4. $p \wedge q$ (conjunction introduction, 2, 3)
    5. $r$ (Modus Ponens, 1, 4)
    6. $q \rightarrow r$ (conditional introduction, 3-5)
    7. $p \rightarrow (q \rightarrow r)$ (conditional introduction, 2-6)
  • Conclude $p \rightarrow (q \rightarrow r) \leftrightarrow (p \wedge q) \rightarrow r$ (biconditional introduction, steps from both subproofs)

Applications in Real-world Reasoning

• Propositional logic can be used to analyze and evaluate arguments in various fields, such as philosophy, law, and computer science
• In philosophy, propositional logic helps clarify and assess the validity of philosophical arguments and theories
  • Example: Analyzing the logical structure of ethical dilemmas or thought experiments
• In law, propositional logic is used to evaluate the consistency and coherence of legal arguments and to identify logical fallacies
  • Example: Assessing the validity of a legal defense or the consistency of a contract
• In computer science, propositional logic forms the basis for Boolean algebra and digital circuit design
  • Example: Optimizing logical expressions in programming or designing efficient digital circuits
• Propositional logic can be applied to decision-making processes by breaking down complex decisions into simpler, more manageable components
  • Example: Evaluating the pros and cons of different options in a decision tree
• In artificial intelligence and expert systems, propositional logic is used to represent and reason about knowledge and rules
  • Example: Developing rule-based systems for medical diagnosis or financial analysis