🤔Mathematical Logic Unit 3 – Formal Proofs in Propositional Logic

Key Concepts and Definitions

• Propositional logic deals with statements that can be either true or false, represented by symbols like $p$, $q$, and $r$
• Logical connectives combine propositions to form more complex statements
  • Connectives include conjunction ($\land$), disjunction ($\lor$), negation ($\lnot$), implication ($\rightarrow$), and biconditional ($\leftrightarrow$)
• Truth tables display all possible truth value combinations for a given statement or set of statements
• Tautology refers to a statement that is always true regardless of the truth values of its component propositions
• Contradiction describes a statement that is always false for all possible truth value assignments
• Logical equivalence means two statements have the same truth value for all possible truth value assignments to their component propositions
• Validity of an argument indicates that if the premises are true, the conclusion must also be true
• Soundness of an argument requires both validity and true premises

Logical Connectives and Truth Tables

• Conjunction ($\land$) represents "and" and is true only when both propositions are true
• Disjunction ($\lor$) represents "or" and is true when at least one of the propositions is true
  • Inclusive disjunction allows for both propositions to be true
  • Exclusive disjunction (XOR) requires exactly one proposition to be true
• Negation ($\lnot$) represents "not" and flips the truth value of a proposition
• Implication ($\rightarrow$) represents "if...then" and is false only when the antecedent (left side) is true and the consequent (right side) is false
• Biconditional ($\leftrightarrow$) represents "if and only if" and is true when both propositions have the same truth value
• Truth tables exhaustively list all possible combinations of truth values for a given set of propositions
  • The number of rows in a truth table is $2^n$, where $n$ is the number of distinct propositions
• Constructing truth tables helps determine the overall truth value of a complex statement and identify tautologies, contradictions, and logical equivalences

Rules of Inference

• Modus ponens states that if $p \rightarrow q$ is true and $p$ is true, then $q$ must be true
• Modus tollens asserts that if $p \rightarrow q$ is true and $q$ is false, then $p$ must be false
• Hypothetical syllogism allows the conclusion $p \rightarrow r$ to be drawn from the premises $p \rightarrow q$ and $q \rightarrow r$
• Disjunctive syllogism concludes $q$ from the premises $p \lor q$ and $\lnot p$
• Conjunction introduction infers $p \land q$ from the individual statements $p$ and $q$
• Conjunction elimination (simplification) allows concluding $p$ from the premise $p \land q$
• Disjunction introduction (addition) infers $p \lor q$ from the statement $p$
• Disjunction elimination (proof by cases) proves a conclusion by considering all possible cases in a disjunction

Proof Techniques and Strategies

• Direct proof assumes the premises are true and uses logical steps to reach the conclusion
• Proof by contradiction (reductio ad absurdum) assumes the negation of the desired conclusion and derives a contradiction, thus proving the original conclusion
• Proof by contraposition proves the equivalent contrapositive statement $\lnot q \rightarrow \lnot p$ instead of $p \rightarrow q$
• Proof by cases (exhaustive proof) considers all possible cases and proves the conclusion holds for each case
• Proof by induction demonstrates a statement holds for a base case and an arbitrary case $k$, then shows it holds for the next case $k+1$
  • Induction is useful for proving statements involving natural numbers or recursively defined structures
• Proof by example provides a counterexample to disprove a universal statement
• Proof by construction explicitly demonstrates the existence of an object satisfying given conditions

Common Proof Structures

• Conditional proof (direct proof of an implication) assumes the antecedent and proves the consequent
• Biconditional proof requires proving both implications $p \rightarrow q$ and $q \rightarrow p$
• Proof by equivalence demonstrates a chain of logical equivalences to transform the premise into the conclusion
• Proof by contradiction (indirect proof) assumes the negation of the conclusion and derives a contradiction with the premises or known facts
• Proof by contraposition starts with the contrapositive of the implication and proceeds with a direct proof
• Proof by cases typically involves a disjunction in the premises, proving the conclusion for each case separately
• Existential proof demonstrates the existence of an object satisfying a given property, often by providing an explicit example or using proof by contradiction
• Universal proof shows a property holds for all elements in a given set, often using a general element and direct proof or proof by contradiction

Examples and Practice Problems

• Prove that the statement $((p \rightarrow q) \land (q \rightarrow r)) \rightarrow (p \rightarrow r)$ is a tautology using a truth table
• Prove the validity of the argument: $p \rightarrow q$, $q \rightarrow r$, $p$, therefore $r$ using rules of inference
• Prove that if $n$ is an odd integer, then $n^2$ is also odd using a direct proof
• Prove that if $n$ is an integer and $n^2$ is even, then $n$ is even using proof by contraposition
• Prove that there exist irrational numbers $a$ and $b$ such that $a^b$ is rational using proof by contradiction
• Prove that the square root of 2 is irrational using proof by contradiction
• Prove that if a graph has a Hamiltonian cycle, then it has a Hamiltonian path using proof by cases (considering the removal of an edge from the cycle)
• Prove that the set of real numbers is uncountable using Cantor's diagonalization argument (proof by contradiction)

Applications in Mathematics and Computer Science

• Propositional logic forms the foundation for more advanced logical systems, such as first-order logic and higher-order logic
• Automated theorem proving uses propositional logic to verify the correctness of mathematical proofs and software systems
• Boolean algebra, based on propositional logic, is essential in the design of digital circuits and computer architectures
• Propositional satisfiability (SAT) is a fundamental problem in computer science with applications in artificial intelligence, hardware verification, and constraint satisfaction
• Propositional logic is used in the specification and verification of software systems, ensuring the correctness of programs
• In artificial intelligence, propositional logic is employed in knowledge representation, reasoning, and planning systems
• Propositional logic is a building block for more expressive logics used in databases, such as relational algebra and SQL
• In set theory, propositional logic is used to define and reason about complex set operations and relations

Common Pitfalls and How to Avoid Them

• Confusing implication ($\rightarrow$) with biconditional ($\leftrightarrow$) or assuming the converse of an implication is always true
  • Remember that $p \rightarrow q$ is not equivalent to $q \rightarrow p$ unless explicitly stated as a biconditional
• Misinterpreting the scope of negation ($\lnot$) or incorrectly applying De Morgan's laws
  • Use parentheses to clarify the scope of negation and carefully distribute negation over conjunctions and disjunctions
• Incorrectly assuming that a statement and its contrapositive are always equivalent
  • While $p \rightarrow q$ is logically equivalent to $\lnot q \rightarrow \lnot p$, this does not hold for other logical connectives
• Failing to consider all possible cases in a proof by cases or overlooking a crucial case
  • Ensure that the cases are exhaustive and mutually exclusive, covering all possibilities
• Misapplying rules of inference or using invalid argument forms
  • Double-check the premises and conclusions to ensure they match the valid forms of the rules of inference
• Confusing the use of existential and universal quantifiers in more advanced logical systems
  • Remember that existential quantification ($\exists$) asserts the existence of at least one object satisfying a property, while universal quantification ($\forall$) asserts that all objects satisfy a property
• Misinterpreting the meaning of logical connectives in natural language or confusing their colloquial usage with their precise logical definitions
  • Be aware of the differences between the logical meanings of connectives and their everyday usage, and rely on the formal definitions when constructing proofs