Formal Logic II Unit 3 ReviewFirst-Order Logic: Rules and Proofs

What's This All About?

• First-order logic (FOL) is a powerful formal system for representing and reasoning about complex statements and arguments
• Extends propositional logic by introducing predicates, quantifiers, and variables to express more intricate logical relationships
• Allows for the representation of objects, their properties, and the relationships between them
• Provides a foundation for many areas of computer science, including artificial intelligence, databases, and software verification
• Mastering FOL is essential for understanding advanced topics in logic and its applications across various domains
  • Enables precise formulation and analysis of arguments in mathematics, philosophy, and other fields
  • Serves as a basis for the development of automated theorem provers and proof assistants

Key Concepts and Definitions

• Predicates: Symbols representing properties or relations, taking one or more arguments (e.g., $P(x)$, $Q(x, y)$)
• Variables: Symbols representing arbitrary objects within the domain of discourse (e.g., $x$, $y$, $z$)
• Quantifiers: Symbols specifying the scope and quantity of variables in a formula
  • Universal quantifier ($\forall$): Asserts that a property holds for all objects in the domain
  • Existential quantifier ($\exists$): Asserts that a property holds for at least one object in the domain
• Terms: Expressions referring to objects, which can be variables or functions applied to terms (e.g., $x$, $f(x)$, $g(x, y)$)
• Formulas: Expressions representing logical statements, built using predicates, variables, quantifiers, and logical connectives
• Interpretation: An assignment of meaning to the symbols in a first-order language, specifying the domain of discourse and the truth values of predicates
• Validity: A formula is valid if it is true under every possible interpretation
• Satisfiability: A formula is satisfiable if there exists an interpretation that makes it true

First-Order Logic Basics

• FOL formulas are constructed using predicates, variables, quantifiers, and logical connectives ($\wedge$, $\vee$, $\rightarrow$, $\leftrightarrow$, $\neg$)
• The order of precedence for logical connectives is: $\neg$, $\wedge$, $\vee$, $\rightarrow$, $\leftrightarrow$
• Quantifiers have higher precedence than logical connectives and bind to the smallest possible scope
• Free variables are not bound by any quantifier, while bound variables are within the scope of a quantifier
• Formulas without free variables are called sentences and have a fixed truth value under a given interpretation
• The domain of discourse is the set of objects over which the variables range and the predicates are defined
  • Can be any non-empty set, such as natural numbers, real numbers, or a set of specific objects
• Interpreting a formula involves assigning truth values to its predicates based on the objects in the domain of discourse

Rules of Inference

• Modus Ponens (MP): If $\phi$ and $\phi \rightarrow \psi$ are true, then $\psi$ is true
• Modus Tollens (MT): If $\phi \rightarrow \psi$ is true and $\psi$ is false, then $\phi$ is false
• Hypothetical Syllogism (HS): If $\phi \rightarrow \psi$ and $\psi \rightarrow \chi$ are true, then $\phi \rightarrow \chi$ is true
• Universal Instantiation (UI): If $\forall x \phi(x)$ is true, then $\phi(t)$ is true for any term $t$
• Existential Generalization (EG): If $\phi(t)$ is true for some term $t$, then $\exists x \phi(x)$ is true
• Universal Generalization (UG): If $\phi(x)$ is true for an arbitrary $x$, then $\forall x \phi(x)$ is true
• Existential Instantiation (EI): If $\exists x \phi(x)$ is true, then $\phi(c)$ is true for a new constant $c$
  • The constant $c$ must not appear in any other assumption or the conclusion

Proof Techniques and Strategies

• Direct proof: Assume the premises and use rules of inference to derive the conclusion
• Proof by contradiction: Assume the negation of the conclusion and show that it leads to a contradiction with the premises or known facts
• Proof by cases: Divide the problem into exhaustive and mutually exclusive cases and prove the conclusion for each case separately
• Existential elimination: When dealing with existential statements, introduce a new constant to represent the object asserted to exist and reason about its properties
• Universal introduction: To prove a universal statement, assume an arbitrary object and show that the property holds for that object, then generalize the result
• Proof by induction: For statements involving natural numbers, prove the base case and the inductive step to show that the statement holds for all natural numbers
  • Base case: Show that the statement holds for the smallest value (usually 0 or 1)
  • Inductive step: Assume the statement holds for an arbitrary $n$ and prove that it holds for $n+1$
• Proof by analogy: Use similar reasoning patterns or techniques from one problem to solve another related problem

Common Mistakes and How to Avoid Them

• Confusing the order of quantifiers: Pay attention to the order of quantifiers and their scope, as changing the order can drastically alter the meaning of a formula
• Misinterpreting the meaning of connectives: Understand the precise meaning of each logical connective and use them correctly in formulas and proofs
• Forgetting to consider all cases: When using proof by cases, ensure that all possible cases are covered and that they are mutually exclusive and exhaustive
• Misusing rules of inference: Apply rules of inference correctly and only when their premises are satisfied
  • For example, do not apply Universal Instantiation to a formula that does not have a universal quantifier
• Introducing inconsistent assumptions: Avoid introducing assumptions that contradict each other or the given premises, as this can lead to invalid proofs
• Confusing implication with equivalence: Remember that implication ($\rightarrow$) and equivalence ($\leftrightarrow$) have different meanings and cannot be used interchangeably
• Mishandling free and bound variables: Keep track of which variables are free and which are bound by quantifiers, and ensure that variable names are used consistently throughout the proof

Real-World Applications

• Database queries: FOL is used to express complex queries in relational databases, allowing for the retrieval of specific data based on logical conditions
• Artificial intelligence: FOL serves as a foundation for knowledge representation and reasoning in AI systems, enabling them to make inferences and draw conclusions from available information
• Software verification: FOL is employed to specify and verify the correctness of software systems, ensuring that they meet their intended specifications and are free from logical errors
• Natural language processing: FOL can be used to represent the logical structure of natural language statements, facilitating tasks such as information extraction, question answering, and text entailment
• Automated theorem proving: FOL is the basis for many automated theorem provers, which use logical inference rules to prove mathematical theorems and verify the correctness of proofs
• Formal verification of hardware: FOL is used to specify and verify the behavior of digital circuits and hardware components, ensuring their reliability and correctness
• Philosophical reasoning: FOL provides a rigorous framework for analyzing and evaluating philosophical arguments, helping to clarify concepts and expose logical fallacies

Practice Problems and Solutions

1. Translate the following English sentence into a first-order logic formula: "Every student in this class has studied either mathematics or physics."

   • Solution: Let $S(x)$ represent "x is a student in this class," $M(x)$ represent "x has studied mathematics," and $P(x)$ represent "x has studied physics." The FOL formula is:

     $\forall x (S(x) \rightarrow (M(x) \vee P(x)))$

2. Prove the following argument is valid using rules of inference: "If all mammals are warm-blooded and all dogs are mammals, then all dogs are warm-blooded."

   • Solution:
     1. $\forall x (M(x) \rightarrow W(x))$ (Premise: All mammals are warm-blooded)
     2. $\forall x (D(x) \rightarrow M(x))$ (Premise: All dogs are mammals)
     3. $D(a)$ (Assumption: a is a dog)
     4. $D(a) \rightarrow M(a)$ (Universal Instantiation from 2)
     5. $M(a)$ (Modus Ponens from 3 and 4)
     6. $M(a) \rightarrow W(a)$ (Universal Instantiation from 1)
     7. $W(a)$ (Modus Ponens from 5 and 6)
     8. $D(a) \rightarrow W(a)$ (Implication Introduction from 3-7)
     9. $\forall x (D(x) \rightarrow W(x))$ (Universal Generalization from 8)

3. Determine the satisfiability of the following formula: $(\exists x P(x)) \wedge (\forall x \neg P(x))$

   • Solution: The formula is unsatisfiable. The first conjunct asserts that there exists an object $x$ for which $P(x)$ is true, while the second conjunct asserts that for all objects $x$, $P(x)$ is false. These statements are contradictory and cannot be simultaneously true under any interpretation.

4. Prove the following theorem using the proof technique of your choice: "If a number is even, then its square is also even."

   • Solution (Proof by Contradiction):
     1. Assume the negation of the conclusion: There exists an even number $n$ such that $n^2$ is odd.
     2. If $n$ is even, then $n = 2k$ for some integer $k$.
     3. $n^2 = (2k)^2 = 4k^2 = 2(2k^2)$
     4. This means $n^2$ is even, as it is a multiple of 2.
     5. This contradicts our assumption that $n^2$ is odd.
     6. Therefore, the original statement must be true: If a number is even, then its square is also even.