2.2 Syntax of FOL: predicates, quantifiers, variables, and connectives
4 min read•august 15, 2024
First-order logic (FOL) builds on propositional logic by adding predicates, quantifiers, and variables. This powerful system lets us express complex relationships and make precise statements about objects and their properties.
FOL's syntax includes predicates to describe properties, quantifiers to specify scope, and variables to represent objects. We'll explore how these elements combine with connectives to form well-formed formulas, both atomic and complex, in FOL.
Syntax of First-Order Logic
Predicates, Variables, and Constants
Top images from around the web for Predicates, Variables, and Constants
.svg.png&w=828&q=75)
File:Argument terminology used in logic (en).svg - Wikipedia View original
Is this image relevant?
Chapter 8 The Entity Relationship Data Model – Database Design – 2nd Edition View original
Is this image relevant?
Árbol de sintaxis abstracta - Wikipedia, la enciclopedia libre View original
Is this image relevant?
File:Argument terminology used in logic (en).svg - Wikipedia View original
Is this image relevant?
Chapter 8 The Entity Relationship Data Model – Database Design – 2nd Edition View original
Is this image relevant?
1 of 3
Top images from around the web for Predicates, Variables, and Constants
File:Argument terminology used in logic (en).svg - Wikipedia View original
Is this image relevant?
Chapter 8 The Entity Relationship Data Model – Database Design – 2nd Edition View original
Is this image relevant?
Árbol de sintaxis abstracta - Wikipedia, la enciclopedia libre View original
Is this image relevant?
File:Argument terminology used in logic (en).svg - Wikipedia View original
Is this image relevant?
Chapter 8 The Entity Relationship Data Model – Database Design – 2nd Edition View original
Is this image relevant?
1 of 3
- Predicates are symbols that represent relations or properties of objects, denoted by uppercase letters (P, Q, R)
- Predicates can have different arities, which refer to the number of arguments they take (unary, binary, ternary predicates)
- Unary predicates take one argument (IsRed(x))
- Binary predicates take two arguments (Loves(x, y))
- Predicates can have different arities, which refer to the number of arguments they take (unary, binary, ternary predicates)
- Variables are symbols that represent objects in the domain of discourse, denoted by lowercase letters (x, y, z)
- Constants are symbols that represent specific objects in the domain of discourse, denoted by lowercase letters (a, b, c)
- Constants refer to a particular object (JohnDoe, Earth, 42)
Quantifiers and Connectives
- Quantifiers are symbols that specify the quantity or scope of objects that a applies to
- () states that a predicate holds for all objects in the domain (∀x Human(x) - "For all x, x is human")
- (∃) states that a predicate holds for at least one object in the domain (∃x Loves(x, icecream) - "There exists an x such that x loves ice cream")
- Connectives are logical symbols that join or modify propositions
- (¬) reverses the truth value of a proposition (¬P(x) - "It is not the case that P(x)")
- (∧) states that both propositions must be true ((P(x) ∧ Q(y)) - "P(x) and Q(y)")
- (∨) states that at least one proposition must be true ((P(x) ∨ Q(y)) - "P(x) or Q(y)")
- (→) states that if the first proposition is true, then the second must also be true ((P(x) → Q(y)) - "If P(x), then Q(y)")
- (↔) states that both propositions must have the same truth value ((P(x) ↔ Q(y)) - "P(x) if and only if Q(y)")
Constructing Well-Formed Formulas
Atomic Formulas
- Atomic formulas are the simplest well-formed formulas (WFFs) in FOL
- Consist of a predicate followed by the appropriate number of terms (variables or constants) enclosed in parentheses
- Unary predicate example: IsRed(apple)
- Binary predicate example: Loves(John, Mary)
- Consist of a predicate followed by the appropriate number of terms (variables or constants) enclosed in parentheses
- Atomic formulas cannot be broken down into simpler formulas
- They are the basic building blocks used to construct more complex formulas
Complex Formulas
- Complex formulas are formed by combining atomic formulas or other complex formulas using connectives and quantifiers
- Negation (¬) is applied to a single formula (¬IsHappy(John))
- Binary connectives (∧, ∨, →, ↔) join two formulas ((IsRed(apple) ∧ IsSweet(apple)))
- Quantifiers (∀, ∃) are applied to a variable and a formula (∀x Human(x), ∃y Loves(John, y))
- Parentheses are used to specify the scope and order of operations in complex formulas
- Example: (IsStudent(x) ∧ IsEnrolled(x, Math101)) → CanAttend(x, MathLecture)
- Complex formulas can be broken down into simpler components
- Example: ∀x (IsHuman(x) → Mortal(x)) can be broken into the atomic formulas IsHuman(x) and Mortal(x), connected by the implication (→) and quantified by the universal (∀)
Atomic vs Complex Formulas
Differences between Atomic and Complex Formulas
- Atomic formulas have a single predicate and no connectives or quantifiers
- Example: IsStudent(John)
- Complex formulas involve the use of connectives and/or quantifiers to join or modify formulas
- Example: IsStudent(John) ∧ ¬IsGraduated(John)
- Atomic formulas are the basic units of FOL, while complex formulas are constructed from atomic formulas and other complex formulas
- Atomic formulas: Loves(John, Mary), IsRed(apple)
- Complex formulas: ∀x (IsHuman(x) → Mortal(x)), Loves(John, Mary) ∨ Loves(John, Susan)
Breaking Down Complex Formulas
- Complex formulas can be analyzed by identifying their components
- Atomic formulas within the complex formula
- Connectives and quantifiers used to join or modify the atomic formulas
- Example: ∃x (IsStudent(x) ∧ ¬IsGraduated(x))
- Atomic formulas: IsStudent(x), IsGraduated(x)
- Connectives: Conjunction (∧), Negation (¬)
- Quantifier: Existential quantifier (∃)
Validity of First-Order Logic Formulas
Rules of Formation
- The rules of formation specify how to construct valid WFFs in FOL using the defined syntax
- Atomic formula rule: An atomic formula is a valid WFF if it consists of a predicate followed by the appropriate number of terms (variables or constants) enclosed in parentheses
- Example: IsRed(apple), Loves(John, Mary)
- Negation rule: If φ is a valid WFF, then ¬φ is also a valid WFF
- Example: If IsHappy(John) is a WFF, then ¬IsHappy(John) is also a WFF
- Binary connective rule: If φ and ψ are valid WFFs, then (φ ∧ ψ), (φ ∨ ψ), (φ → ψ), and (φ ↔ ψ) are also valid WFFs
- Example: If IsStudent(x) and IsEnrolled(x, Math101) are WFFs, then (IsStudent(x) ∧ IsEnrolled(x, Math101)) is also a WFF
- Quantifier rule: If φ is a valid WFF and x is a variable, then ∀x φ and ∃x φ are also valid WFFs
- Example: If Loves(x, icecream) is a WFF, then ∀x Loves(x, icecream) and ∃x Loves(x, icecream) are also WFFs
Determining the Validity of Formulas
- To determine the validity of a formula, check if it can be constructed using the rules of formation
- Start with atomic formulas and apply the appropriate rules for connectives and quantifiers
- Example: ∀x (IsHuman(x) → Mortal(x))
- IsHuman(x) and Mortal(x) are valid atomic formulas (atomic formula rule)
- (IsHuman(x) → Mortal(x)) is a valid WFF (binary connective rule)
- ∀x (IsHuman(x) → Mortal(x)) is a valid WFF (quantifier rule)
- Example: ∀x ∃y Loves(x, y)
- Loves(x, y) is a valid atomic formula (atomic formula rule)
- ∃y Loves(x, y) is a valid WFF (quantifier rule)
- ∀x ∃y Loves(x, y) is a valid WFF (quantifier rule)
Key Terms to Review (20)
∀: The symbol ∀ represents universal quantification in first-order logic, indicating that a statement applies to all members of a specified domain. This concept is fundamental in constructing logical expressions that assert a property or relation holds for every element within a particular set, connecting deeply with the structure of predicates and the rules governing quantifiers.
∃ (Existential Quantifier): The existential quantifier, denoted by ∃, is a symbol used in formal logic to express that there exists at least one element in a given domain that satisfies a specified property. It plays a crucial role in making statements about the existence of objects and is foundational in various logical expressions involving predicates, variables, and connectives.
Arity: Arity refers to the number of arguments or operands that a function or predicate takes. In the context of formal logic, especially first-order logic, it is crucial for defining predicates, which can have different arities depending on how many elements they relate to. Understanding arity helps clarify how predicates function within logical statements, influencing the application of quantifiers and the overall structure of logical expressions.
Bound Variable: A bound variable is a variable that is quantified within a logical expression, meaning its value is restricted to a specific range determined by a quantifier, such as 'for all' or 'there exists.' This concept is crucial in understanding how variables interact with predicates and quantifiers, as it helps define the scope in which the variable operates and ensures that its interpretation is clear within formal logic.
Conjunction: In logic, a conjunction is a compound statement formed by combining two or more propositions using the logical connective 'and,' symbolized as '$$\land$$'. A conjunction is true only when all its component propositions are true, highlighting the importance of this operation in understanding logical relationships and structures.
Disjunction: Disjunction is a logical operation that connects two statements with an 'or,' indicating that at least one of the statements must be true for the overall expression to be true. This concept is crucial in understanding how different logical constructs interact, especially in terms of creating more complex expressions and evaluating truth values.
Entailment: Entailment refers to a fundamental relationship between statements where one statement logically follows from another. If a set of premises entails a conclusion, then if the premises are true, the conclusion must also be true. This concept connects closely with the structure of logical expressions, especially as they relate to predicates, quantifiers, and connectives, as well as how we understand truth in terms of validity and logical consequence.
Equivalence: Equivalence refers to the relationship between two propositions or logical expressions that yield the same truth value in every possible scenario. This means that when both expressions are evaluated, they will either both be true or both be false, demonstrating a fundamental logical connection. Equivalence is crucial in transforming and manipulating logical statements, as it allows for simplification and the establishment of logical identities across different contexts.
Existential Quantifier: The existential quantifier is a symbol used in first-order logic to express that there exists at least one element in a domain that satisfies a given property or predicate. It is denoted by the symbol $$\exists$$ and is crucial for formulating statements about the existence of certain objects within logical frameworks, linking it to free and bound variables, logical deductions, and the overall structure of logical expressions.
Formulas of FOL: Formulas of First-Order Logic (FOL) are structured expressions that represent logical statements, built using predicates, quantifiers, variables, and connectives. These formulas enable the expression of relationships and properties in a formalized manner, allowing for rigorous reasoning within a logical framework. The ability to combine these elements creates more complex statements that can convey intricate ideas about the domain of discourse.
Free variable: A free variable is a variable in a logical expression that is not bound by a quantifier and can take on any value within its domain. Free variables are crucial in understanding the scope of quantifiers, as they represent placeholders for objects in the universe of discourse that have not been specified by any particular binding. They help to distinguish between parts of statements that are general versus those that are specific, allowing for a clearer interpretation of logical formulas.
Implication: Implication is a logical relationship between two propositions where the truth of one proposition (the antecedent) guarantees the truth of another proposition (the consequent). This concept is essential in understanding how statements relate to one another, especially in terms of cause and effect, as well as reasoning processes.
N-ary predicate: An n-ary predicate is a logical function that takes 'n' arguments or inputs and returns a truth value. This concept is fundamental in formal logic, as it allows for the expression of complex relationships among multiple entities, connecting to the broader framework of predicates, quantifiers, variables, and connectives in first-order logic.
Negation: Negation is a fundamental logical operation that transforms a proposition into its opposite truth value. It plays a critical role in understanding and manipulating logical statements, allowing us to express denial or contradiction of a proposition, thus impacting the interpretation of logical expressions and arguments.
Nullary Predicate: A nullary predicate is a type of predicate that takes no arguments and simply evaluates to a truth value, either true or false. It is unique in that it does not rely on any individual constants or variables to convey meaning, often representing a specific property or fact that is universally applicable. This makes nullary predicates distinct within the broader framework of predicates, which typically require one or more arguments to function.
Predicate: A predicate is a fundamental component in first-order logic that expresses a property or relation among objects. It allows us to make statements about subjects by asserting something about them, often represented as a function that takes one or more arguments. Predicates form the backbone of logical expressions, enabling the use of quantifiers to specify the scope of their applicability.
Predicate Symbol: A predicate symbol is a fundamental component of first-order logic that represents a property or relation that can be attributed to objects in a domain. It connects the logical structure of statements to their meanings by allowing for the expression of assertions about specific objects, using quantifiers and variables to create more complex logical expressions.
Quantifier: A quantifier is a symbol or phrase in logic that specifies the quantity of subjects to which a predicate applies. It plays a crucial role in expressing statements that involve varying amounts of elements, enabling us to make generalizations or assertions about sets or individual objects. Quantifiers help bridge the relationship between predicates and variables, forming the basis for constructing complex logical statements.
Universal Quantifier: The universal quantifier is a logical operator used in first-order logic that expresses that a given property or statement holds for all elements in a specified domain. It is often denoted by the symbol $$ orall$$ and indicates that the statement following it is true for every instance of the variable in its scope, linking closely to concepts like free and bound variables, as well as interpretations and truth assignments.
Well-formed formula: A well-formed formula (WFF) is a syntactically correct expression in formal logic that adheres to the rules of a particular logical language, ensuring that it can be evaluated for truth or falsity within a given interpretation. The structure of a WFF allows it to convey meaningful statements about objects, properties, and relationships, using components like predicates, quantifiers, and logical connectives. This syntactic correctness is crucial for establishing interpretations and truth assignments in logical systems.