➕Logic and Formal Reasoning Unit 5 – Predicate Logic: Basics & Quantifiers

Key Concepts and Terminology

• Predicate logic extends propositional logic by introducing predicates, variables, and quantifiers
• Predicates are functions that take one or more arguments and return a truth value (true or false)
• Variables represent unspecified objects within a domain of discourse
• Constants refer to specific, named objects within a domain of discourse
• Quantifiers express the scope and quantity of variables in a predicate logic statement
  • Universal quantifier ($\forall$) asserts that a predicate holds for all values of a variable
  • Existential quantifier ($\exists$) asserts that a predicate holds for at least one value of a variable
• Domain of discourse defines the set of objects over which variables and quantifiers range
• Atomic formulas are the basic building blocks of predicate logic statements, consisting of a predicate and its arguments
• Complex formulas combine atomic formulas using logical connectives (conjunction, disjunction, implication, etc.)

Propositional vs Predicate Logic

• Propositional logic deals with simple, declarative statements (propositions) and their relationships using logical connectives
• Propositional logic cannot express statements about individual objects or their properties
• Predicate logic introduces predicates, variables, and quantifiers to express more complex statements
• Predicate logic allows for reasoning about properties of objects and relationships between them
• Propositional logic is a subset of predicate logic, as any propositional statement can be expressed in predicate logic
• Predicate logic is more expressive and powerful than propositional logic, enabling more sophisticated reasoning
• Propositional logic is decidable, while predicate logic is undecidable in the general case

Structure of Predicate Logic Statements

• Predicate logic statements consist of predicates, variables, constants, and quantifiers
• Predicates are denoted by uppercase letters (e.g., $P$, $Q$, $R$) followed by a list of arguments in parentheses
  • Example: $P(x)$ represents a unary predicate $P$ applied to a variable $x$
• Variables are typically denoted by lowercase letters (e.g., $x$, $y$, $z$)
• Constants are denoted by lowercase letters (e.g., $a$, $b$, $c$) or specific names (e.g., $john$, $mary$)
• Quantifiers are placed at the beginning of a predicate logic statement, followed by the variable they quantify
  • Example: $\forall x P(x)$ asserts that the predicate $P$ holds for all values of $x$
• Logical connectives (e.g., $\wedge$, $\vee$, $\rightarrow$, $\leftrightarrow$, $\neg$) are used to combine atomic formulas into complex formulas
• Parentheses are used to specify the order of operations and the scope of quantifiers

Variables and Constants

• Variables are symbols that represent unspecified objects within a domain of discourse
• Variables can take on any value from the domain of discourse
• Variables are typically denoted by lowercase letters (e.g., $x$, $y$, $z$)
• Constants are symbols that represent specific, named objects within a domain of discourse
• Constants have a fixed value and do not change within the context of a predicate logic statement
• Constants are denoted by lowercase letters (e.g., $a$, $b$, $c$) or specific names (e.g., $john$, $mary$)
• Variables are bound when they are quantified by a universal or existential quantifier
• Free variables are variables that are not bound by any quantifier
• Closed formulas contain no free variables, while open formulas have at least one free variable

Quantifiers: Universal and Existential

• Quantifiers express the scope and quantity of variables in a predicate logic statement
• The universal quantifier ($\forall$) asserts that a predicate holds for all values of a variable within the domain of discourse
  • Example: $\forall x P(x)$ means that the predicate $P$ is true for every $x$ in the domain
• The existential quantifier ($\exists$) asserts that a predicate holds for at least one value of a variable within the domain of discourse
  • Example: $\exists x P(x)$ means that there exists at least one $x$ in the domain for which the predicate $P$ is true
• Quantifiers can be nested to express more complex statements
  • Example: $\forall x \exists y R(x, y)$ means that for every $x$ in the domain, there exists at least one $y$ such that the relation $R$ holds between $x$ and $y$
• The order of quantifiers is important, as it affects the meaning of the statement
• Quantifiers can be negated using the negation symbol ($\neg$)
  • Example: $\neg \forall x P(x)$ is equivalent to $\exists x \neg P(x)$, and $\neg \exists x P(x)$ is equivalent to $\forall x \neg P(x)$

Translating Natural Language to Predicate Logic

• Translating natural language statements into predicate logic involves identifying predicates, variables, constants, and quantifiers
• Identify the domain of discourse and the objects being referred to in the statement
• Assign predicates to represent properties of objects or relationships between them
  • Example: "All dogs are mammals" can be translated as $\forall x (Dog(x) \rightarrow Mammal(x))$
• Use variables to represent unspecified objects and constants to represent specific objects
• Determine the appropriate quantifiers to express the scope and quantity of variables
  • Example: "Some students are athletes" can be translated as $\exists x (Student(x) \wedge Athlete(x))$
• Break down complex statements into simpler components and combine them using logical connectives
• Pay attention to the order of quantifiers and the scope of negation when translating statements
• Practice translating a variety of natural language statements to develop proficiency in predicate logic representation

Truth Tables and Validity in Predicate Logic

• Truth tables can be used to evaluate the validity of predicate logic statements, but they become impractical for statements with many variables
• To construct a truth table for a predicate logic statement, assign truth values to the predicates for each possible combination of variable values
• A predicate logic statement is valid if it is true for all possible interpretations of its predicates and variable assignments
• Validity in predicate logic is more complex than in propositional logic due to the presence of quantifiers
• A statement is satisfiable if there exists at least one interpretation and variable assignment that makes the statement true
• A statement is unsatisfiable if there is no interpretation and variable assignment that makes the statement true
• Tautologies are predicate logic statements that are true for all possible interpretations and variable assignments
• Contradictions are predicate logic statements that are false for all possible interpretations and variable assignments

Common Mistakes and How to Avoid Them

• Confusing the order of quantifiers, which can lead to unintended meanings
  • Example: $\forall x \exists y R(x, y)$ is not equivalent to $\exists y \forall x R(x, y)$
  • Carefully consider the order of quantifiers and the dependencies between variables
• Misinterpreting the scope of negation, especially when combined with quantifiers
  • Example: $\neg \forall x P(x)$ is not equivalent to $\forall x \neg P(x)$
  • Use parentheses to clearly specify the scope of negation and quantifiers
• Forgetting to specify the domain of discourse, which can lead to ambiguity or incorrect conclusions
  • Always clearly define the domain of discourse and ensure that variables and quantifiers are used consistently within that context
• Mixing up variables and constants, or using them inconsistently
  • Use distinct symbols for variables and constants, and maintain consistency throughout the predicate logic statement
• Translating natural language statements incorrectly due to ambiguity or lack of precision
  • Break down complex statements into simpler components and carefully consider the logical structure and relationships between objects
• Overlooking the limitations of predicate logic, such as its inability to express certain types of statements (e.g., "most," "few," "many")
  • Be aware of the limitations of predicate logic and use other techniques (e.g., first-order logic, modal logic) when necessary to capture more complex statements