Formal Logic I Unit 4 Review: Logical Equivalence & Implication

Key Concepts

• Propositional logic deals with statements that can be either true or false
• Logical operators connect propositions to form compound statements
• Truth tables visually represent all possible truth value combinations for a given logical expression
• Logical equivalence means two statements have the same truth value for all possible combinations of their component propositions
• Tautologies are statements that are always true regardless of the truth values of their component propositions
• Contradictions are statements that are always false regardless of the truth values of their component propositions
• Logical implication $(P \rightarrow Q)$ means if $P$ is true, then $Q$ must also be true
  • Converse $(Q \rightarrow P)$, inverse $(\neg P \rightarrow \neg Q)$, and contrapositive $(\neg Q \rightarrow \neg P)$ are related implications

Logical Operators

• Negation $(\neg)$ flips the truth value of a proposition
  • $\neg P$ is read as "not $P$"
• Conjunction $(\land)$ connects two propositions with "and"
  • $P \land Q$ is true only when both $P$ and $Q$ are true
• Disjunction $(\lor)$ connects two propositions with "or"
  • $P \lor Q$ is true when at least one of $P$ or $Q$ is true
• Conditional $(\rightarrow)$ represents an if-then statement
  • $P \rightarrow Q$ is read as "if $P$, then $Q$"
• Biconditional $(\leftrightarrow)$ represents an if and only if statement
  • $P \leftrightarrow Q$ is true when $P$ and $Q$ have the same truth value
• Order of operations: parentheses, negation, conjunction, disjunction, conditional, biconditional

Truth Tables

• List all possible combinations of truth values for the component propositions
• For each row, evaluate the truth value of the overall compound proposition
• Number of rows in a truth table is $2^n$ where $n$ is the number of unique propositions
• Can be used to determine logical equivalence by comparing columns
  • If two expressions have identical output columns, they are logically equivalent
• Tautologies have a column of all T's
• Contradictions have a column of all F's

Logical Equivalence

• Two statements are logically equivalent if they have the same truth value for all possible interpretations
• Denoted with the symbol $\equiv$
• Examples of logically equivalent statements:
  • Commutative laws: $P \land Q \equiv Q \land P$, $P \lor Q \equiv Q \lor P$
  • Associative laws: $(P \land Q) \land R \equiv P \land (Q \land R)$, $(P \lor Q) \lor R \equiv P \lor (Q \lor R)$
  • Distributive laws: $P \land (Q \lor R) \equiv (P \land Q) \lor (P \land R)$, $P \lor (Q \land R) \equiv (P \lor Q) \land (P \lor R)$
  • De Morgan's laws: $\neg (P \land Q) \equiv \neg P \lor \neg Q$, $\neg (P \lor Q) \equiv \neg P \land \neg Q$
• Can be proven using truth tables or logical proofs

Logical Implication

• Statement of the form "if $P$, then $Q$" denoted $P \rightarrow Q$
• $P$ is the antecedent (hypothesis) and $Q$ is the consequent (conclusion)
• Only false when $P$ is true and $Q$ is false
  • If the hypothesis is false, implication is vacuously true
• Converse: $Q \rightarrow P$, reverses order of $P$ and $Q$
• Inverse: $\neg P \rightarrow \neg Q$, negates both $P$ and $Q$
• Contrapositive: $\neg Q \rightarrow \neg P$, both negates and reverses order of $P$ and $Q$
  • Logically equivalent to the original implication
• Implications can form chains: $(P \rightarrow Q) \land (Q \rightarrow R) \rightarrow (P \rightarrow R)$

Proof Techniques

• Direct proof: Assume the antecedent is true and use logical steps to show the consequent must be true
• Proof by contrapositive: Prove the logically equivalent contrapositive statement instead
  • Useful when the contrapositive is easier to prove directly
• Proof by contradiction: Assume the negation of what you want to prove and show it leads to a contradiction
  • Contradiction means the assumption must have been false
• Proof by cases: Break the proof into distinct cases and prove each case separately
• Proof by counterexample: To disprove a statement, provide a single counterexample where the statement doesn't hold

Common Fallacies

• Affirming the consequent: Incorrectly concluding $P$ is true because $Q$ is true in $P \rightarrow Q$
  • Example: "If it rains, the grass is wet. The grass is wet, therefore it rained." (Grass could be wet for other reasons)
• Denying the antecedent: Incorrectly concluding $\neg Q$ is true because $\neg P$ is true in $P \rightarrow Q$
  • Example: "If I study, I will pass the test. I didn't study, therefore I won't pass." (Might pass without studying)
• Begging the question (circular reasoning): Assuming the truth of the conclusion within the premise
  • Example: "God exists because the Bible says so, and the Bible is true because it is the word of God."
• False dilemma (false dichotomy): Presenting limited options as if they're the only possibilities when more exist
  • Example: "You're either with us or against us." (Ignores neutral or alternative positions)
• Slippery slope: Asserting a relatively small first step will inevitably lead to a chain of related events culminating in a significant impact
  • Example: "If we allow same-sex marriage, next people will want to marry their pets."

Practical Applications

• Digital circuit design uses logical expressions to define output based on input signals
• Computer programming uses logical operators and control structures like if-then statements
• Artificial intelligence and expert systems rely on logical inference to draw conclusions from available information
• Debugging software or hardware issues often involves systematic troubleshooting using logical elimination of potential causes
• Philosophical arguments and proofs use formal logic to establish validity of claims
• Legal arguments in court cases rely on logical reasoning to build a compelling case from evidence
• Scientific research uses logical deduction to formulate hypotheses and logical induction to generalize from data
• Constructing valid arguments or deconstructing others' arguments in debates or persuasive writing