Formal Logic Arguments Rules and Proof Sequences

Foundations of Logic: Propositions and Arguments

• Propositions / Statements: In formal logic, declarative statements that express a truth value (either true or false) are called propositions or statements.

• Definition of an Argument: An argument is defined as a structured sequence of statements.

• Structure of an Argument:

  • An argument consists of a conjunction of initial statements called hypotheses: $p_1, p_2, \dots, p_n$.

  • The hypotheses collectively imply a final statement $q$, which is called the conclusion.

  • Symbolic Representation of an Argument: $(p_1 \land p_2 \land \dots \land p_n) \implies q$

• Core Rule of Logical Evaluation:

  • Analysis must focus strictly and exclusively on the relationship between the given hypotheses and the conclusion.

  • No external information, unstated real-world assumptions, or prior domain knowledge may be introduced.

• Verbal to Symbolic Translation Example:

  • Hypothesis 1 ($p_1$): "George Washington was the first president."

  • Hypothesis 2 ($p_2$): "If George Washington was the first president, then John Adams was the first vice president."

  • Conclusion ($q$): "John Adams was the first vice president."

  • Symbolic Mapping:

  • Let $a$ = "George Washington was the first president."

  • Let $b$ = "John Adams was the first vice president."

  • $p_1 = a$

  • $p_2 = a \implies b$

  • $q = b$

  • Complete Symbolic Representation: $((a) \land (a \implies b)) \implies b$

Truth Tables and Valid Arguments

• Truth Table Size Formulas:

  • The number of rows required in a truth table depends on the number of distinct propositional variables (letters) $n$:

  • $2$ variables ($a, b$) $\rightarrow 2^2 = 4 rows.\n - 3$variables ($a, b, c) $\rightarrow 2^3 = 8 rows.

  • $4$ variables ($a, b, c, d$) $\rightarrow 2^4 = 16 rows.\n - 5$variables ($a, b, c, d, e) $\rightarrow 2^5 = 32 rows.

• Definition of a Valid Argument:

  • An argument is valid if and only if its symbolic expression $(p_1 \land p_2 \land \dots \land p_n) \implies q$ evaluates to True under every possible truth evaluation (i.e., every row of its truth table is True).

• Tautology:

  • A logical expression that is always True in every possible scenario is called a tautology.

  • An argument is logically valid if and only if the conditional statement representing the argument is a tautology.

Formal Proof Sequences and Derivation Tools

• Proof Sequence Definition:

  • A proof sequence is a sequence of well-formed formulae (wffs) starting with given hypotheses and applying rules of formal logic step-by-step until reaching the conclusion.

  • The initial lines of a proof sequence consist of the given hypotheses, which are always assumed to be True.

  • Subsequent lines are derived by manipulating prior lines using formal derivation tools.

  • Reaching the exact conclusion on the final line demonstrates that the given argument is valid.

• Two Main Categories of Derivation Tools:

  1. Equivalence Rules

  2. Inference Rules

Equivalence Rules

• Properties of Equivalence Rules:

  • Equivalence rules state that two well-formed formulae have identical truth values across all scenarios.

  • Equivalence rules are bidirectional (they work in both directions: Column 1 $\leftrightarrow$ Column 2).

  • Any formula pattern matching Column 1 can be rewritten into Column 2, and any pattern matching Column 2 can be rewritten into Column 1.

• List of Equivalence Rules:

  • Commutative Rules:

  • $p \lor q \iff q \lor p$

  • $p \land q \iff q \land p$

  • Associative Rules:

  • $(p \lor q) \lor r \iff p \lor (q \lor r)$

  • $(p \land q) \land r \iff p \land (q \land r)$

  • De Morgan's Laws:

  • $\neg(p \lor q) \iff \neg p \land \neg q$

  • $\neg(p \land q) \iff \neg p \lor \neg q$

  • Implication Rule:

  • $p \implies q \iff \neg p \lor q$

  • Double Negation Rule:

  • $p \iff \neg(\neg p)$

  • Equivalence Rule (Biconditional):

  • $p \iff q \iff (p \implies q) \land (q \implies p)$

Inference Rules

• Properties of Inference Rules:

  • Inference rules allow introducing a new well-formed formula as a line in a proof sequence based on matching patterns from prior lines.

  • Inference rules are unidirectional (they work strictly from Column 1 to derive Column 2; they CANNOT be applied in reverse).

• Fundamental Inference Rules:

  • Modus Ponens (MP):

  • Pattern: Given $p \implies q$ is True, and $p$ is True, derive $q$ is True.

  • Truth Table Rationale: The implication statement $p \implies q$ is False ONLY when $p$ is True and $q$ is False. If $p$ is False, the implication $p \implies q$ holds True vacuously regardless of $q$. Therefore, when $p \implies q$ is True and $p$ is True, $q$ MUST be True.

  • Modus Tollens (MT):

  • Pattern: Given $p \implies q$ is True, and $\neg q$ is True (meaning $q$ is False), derive $\neg p$ is True (meaning $p$ is False).

  • Truth Table Rationale: If $q$ is False and $p \implies q$ is True, $p$ cannot be True (otherwise the implication would be False). Thus, $p$ must be False ($\neg p$).

  • Conjunction Rule:

  • Pattern: Given $p$ is True and $q$ is True, derive $p \land q$ is True.

  • Simplification Rule:

  • Pattern: Given $p \land q$ is True, derive $p$ is True (or derive $q$ is True).

  • Addition Rule:

  • Pattern: Given $p$ is True, derive $p \lor q$ is True (where $q$ can be any formula).

Simplification and Logical Translation Examples

• Algebraic Simplification Example:

  • Expression to simplify: $\neg a \lor \neg b \lor c$

  • Step 1: Group $\neg a \lor \neg b$ and apply De Morgan's Law: $\neg(a \land b) \lor c$

  • Step 2: Recognize pattern matching the Implication Rule ($\neg p \lor q \iff p \implies q$), setting $p = (a \land b)$ and $q = c$

  • Simplified Form: $(a \land b) \implies c$

• Verbal Logic Applications:

  • Verbal Modus Ponens Example:

  • Premise 1 ($p \implies q$): "If it is bright and sunny today, then I will wear my sunglasses."

  • Premise 2 ($p$): "It is bright and sunny today."

  • Conclusion ($q$ via MP): "Therefore, I will wear my sunglasses."

  • Verbal Modus Tollens Example:

  • Premise 1 ($p \implies q$): "If it is bright and sunny today, then I will wear my sunglasses."

  • Premise 2 ($\neg q$): "I will not wear my sunglasses."

  • Conclusion ($\neg p$ via MT): "It is not bright and sunny today" (which expands via De Morgan's to "It is not bright or it is not sunny today").

• Strict Rule Matching Criterion:

  • Rule patterns must match exact structural positions.

  • Given $a \implies (b \lor c)$ and $a$, Modus Ponens yields $b \lor c$. Modus Ponens does NOT yield $a \implies b$. To extract $b$ directly using Simplification after MP, the consequence must be a conjunction $b \land c$, as in $a \implies (b \land c)$.

Deduction Techniques: The Reduction Method

• Purpose: Applied when the conclusion of an argument is itself an implication statement of the form $r \implies q$.

• Original Argument Form: $(p_1 \land p_2 \land \dots \land p_n) \implies (r \implies q)$

• Reduction Procedure:

  1. Pull the antecedent ($r$) of the conditional conclusion over to the hypothesis side.

  2. Gain $r$ as an additional hypothesis.

  3. Set the remaining consequent ($q$) as the new single target conclusion to reach.

• Transformed Argument Form: $(p_1 \land p_2 \land \dots \land p_n \land r) \implies q$

Additional Inference Rules

• Hypothetical Syllogism (HS):

  • Pattern: Given $p \implies q$ and $q \implies r$, derive $p \implies r$.

  • Derivation via Reduction: Assuming hypotheses $p \implies q$, $q \implies r$, and pulling extra hypothesis $p$: applying MP on $p$ and $p \implies q$ yields $q$; applying MP on $q$ and $q \implies r$ yields $r$.

• Disjunctive Syllogism (DS):

  • Pattern: Given $p \lor q$ and $\neg p$, derive $q$

• Contraposition Rule:

  • Pattern: $p \implies q \iff \neg q \implies \neg p$

• Self-Reference (Idempotent Rule):

  • Pattern: $p \lor p \iff p$ and $p \land p \iff p$

• Exportation Rule:

  • Pattern: $(p \land q) \implies r \iff p \implies (q \implies r)$

• Inconsistency Rule:

  • Pattern: If both $p$ and $\neg p$ are established within the same proof sequence, derive any desired statement $q$.

• Distributive Rules:

  • $p \land (q \lor r) \iff (p \land q) \lor (p \land r)$

  • $p \lor (q \land r) \iff (p \lor q) \land (p \lor r)$

Step-by-Step Proof Sequence Examples

• Proof Sequence Guidelines:

  • Every line must be numbered consecutively.

  • Every derived line must explicitly list the line numbers and rule name used for justification.

  • Proof sequence length does not determine correctness; validity relies strictly on correct rule applications.

• Proof Sequence Example 1:

  • Goal: Prove $d$ from hypotheses.

  • Line 1: $a$ (Hypothesis)

  • Line 2: $a \implies c$ (Hypothesis)

  • Line 3: $(a \land b) \implies \neg(d \lor c)$ (Hypothesis)

  • Line 4: $a$ (Hypothesis)

  • Line 5: $c$ (Lines 2, 4 via Modus Ponens)

  • Line 6: $a \land b$ (Joined via Conjunction Rule)

  • Line 7: $\neg(d \lor c)$ (Lines 3, 6 via Modus Ponens)

  • Line 8: $\neg(c \lor d)$ (Line 7 via Commutative Rule)

  • Line 9: $c \implies d$ (Line 8 via Implication Rule transformation)

  • Subsequent Steps: Apply Modus Ponens with Line 5 ($c$) and Line 9 ($c \implies d$) to arrive at destination $d$

• Proof Sequence Example 2 (Deriving $\neg a$ via Self-Reference):

  • Scenario: Intermediate steps derive $\neg c \implies \dots$ and $a \implies \neg a$

  • Step 1: Establish implication $a \implies \neg a$

  • Step 2: Apply Implication Rule ($p \implies q \iff \neg p \lor q$) to line $a \implies \neg a$, yielding $\neg a \lor \neg a$

  • Step 3: Apply Self-Reference Rule ($p \lor p \iff p$) to $\neg a \lor \neg a$, yielding final destination $\neg a$

  • Proof complete.