What is firstorder logic?
by Stephen M. Walker II, CoFounder / CEO
What is firstorder logic?
Firstorder logic (FOL), also known as firstorder predicate calculus or quantificational logic, is a system of formal logic that provides a way to formalize natural languages into a computable format. It is an extension of propositional logic, which is less expressive as it can only represent information as either true or false. In contrast, FOL allows the use of sentences that contain variables, enabling more complex representations and assertions of relationships among certain elements.
In FOL, the predicate of a sentence or statement can only refer to a single subject. Predicates in FOL assert a relationship among certain elements, and these predicates are often associated with sets. For example, in the sentence "Mary loves everyone", the predicate "loves" asserts a relationship between "Mary" and "everyone".
FOL uses quantified variables over nonlogical objects. Quantifiers always precede variables in the expressions that contain them and are written as ∀x and ∃x. If the variable refers to a predicate P(x), the quantifier precedes the predicate and is written as ∀xP(x) and ∃xP(x).
FOL is crucial for many academic and realworld disciplines as it allows problems expressed in English sentences to be represented in a formal manner, which makes it possible to formulate ideas, draw conclusions, and prove theorems. It is particularly useful in the creation of computer programs and is of interest to researchers and practitioners in the field of artificial intelligence (AI).
The syntax of FOL is comprised of symbols belonging to one of two classes: logical and nonlogical symbols. Logical symbols correspond to logical operators or connectives, while nonlogical symbols include constant symbols, variable symbols, function symbols, and predicate symbols.
What is the difference between firstorder logic and propositional logic?
Firstorder logic (FOL) and propositional logic (PL) are both formal systems used in mathematics, philosophy, linguistics, and computer science, but they differ significantly in their expressiveness and the complexity of the statements they can represent.
Expressiveness

Propositional Logic — In PL, the atomic formulas have no internal structure and are simply propositional variables that can be true or false. It deals with simple declarative propositions and does not allow for the expression of relationships between different entities or the use of variables.

FirstOrder Logic — FOL extends PL by including predicates that assert relationships among elements and quantification over individuals. It allows for the use of variables and quantifiers like "for all" ((\forall)) and "there exists" ((\exists)), which enable the expression of more complex statements about objects and their properties.
Quantification

Propositional Logic — Does not have quantifiers. Each statement is evaluated as true or false without the ability to generalize over a domain or specify properties that hold for some or all members of a domain.

FirstOrder Logic — Includes quantifiers that allow for the expression of statements about all members of a domain ((\forall x)) or about the existence of some members with certain properties ((\exists x)).
Syntax and Semantics

Propositional Logic — The syntax is simpler, with a focus on propositional connectives like "and", "or", and "not". The semantics are straightforward, with each proposition assigned a truth value.

FirstOrder Logic — The syntax is more complex, including constant symbols, function symbols, and predicate symbols, each with an associated arity. The semantics involve a domain of discourse and interpretations that assign meanings to the nonlogical symbols.
Use Cases

Propositional Logic — Often used for simple logical reasoning where the complexity of relationships and quantification is not required.

FirstOrder Logic — More suitable for formalizing natural language statements, mathematical theorems, and for use in fields like computer programming (e.g., Prolog), machine learning, and artificial intelligence, where the ability to express relationships and properties of objects is crucial.
In essence, FOL is a more expressive and powerful system than PL, capable of representing a wider range of logical statements and reasoning about the properties of objects and their relationships.
Syntax of FirstOrder Logic
The syntax of firstorder logic (FOL) is defined relative to a signature, which includes constant symbols, function symbols, predicate symbols, and variables. Each function and predicate symbol has an associated arity, indicating the number of arguments it takes. The syntax is formal and allows for the mechanical determination of wellformed expressions.
Wellformed formulas (wffs) of FOL are composed of the following types of symbols:
 Constant symbols (CONST): Represent specific objects in the domain of discourse.
 Variable symbols (VAR): Used to quantify over objects.
 Function symbols (FUNC): Represent functions over the domain, with a specific arity.
 Predicate symbols (PRED): Represent relations over the domain, with a specific arity.
 Quantifiers — Universal (∀) and existential (∃) quantifiers, used to indicate the scope of variables.
 Logical connectives — Include implication (⇒), conjunction (∧), disjunction (∨), equivalence (⇔), and negation (¬).
The syntax also includes rules for forming terms and formulas. Terms represent objects and can be variables, constants, or functions applied to terms. Formulas are constructed from atomic formulas using logical connectives and quantifiers. An atomic formula consists of a predicate symbol applied to a sequence of terms.
Semantics of FirstOrder Logic
Semantics in FOL relates the syntax to the world, providing meaning to the expressions. A model in FOL is a tuple consisting of a domain of objects and interpretations for the nonlogical symbols (constants, functions, and predicates). The domain is a nonempty set of objects, and interpretations assign each kary function symbol a kary function over the domain, each kary predicate symbol a kary relation over the domain, and each constant symbol an object in the domain.
The truth of a formula in a given model is determined with respect to a variable assignment, which is a function from variables to objects in the domain. The satisfaction relation (=) denotes that a formula is true in a model under a particular variable assignment. For example, a formula with a universal quantifier (∀xϕ(x)) is true in a model if, for every object in the domain, the formula ϕ(x) is true when x is assigned that object.
In summary, the syntax of FOL provides the rules for constructing formal expressions, while the semantics assigns meaning to these expressions by interpreting them in a model with a specific domain and interpretations for the symbols.
How can firstorder logic be used for knowledge representation and reasoning?
The basic syntactic elements of FOL include symbols, atomic sentences, complex sentences, and quantifiers. For example, consider the statement "Ravi and Ajay are brothers." In FOL, this can be represented as "Brothers(Ravi, Ajay)". FOL also allows for the use of universal quantifiers, which specify that a statement within its range is true for everything or every instance of a particular object or concept.
What are some of the advantages and disadvantages of using firstorder logic?
FOL has several advantages. It is more expressive than propositional logic, having predicate and function symbols, as well as quantifiers. It allows for the representation of partial, disjunctive, and negated information, unlike most data structures and databases. FOL is also declarative, meaning pieces of syntax correspond to facts, and it is compositional, meaning the meaning of a complex expression is derived from the meanings of its parts.
However, FOL also has its disadvantages. One of the main challenges involves addressing the computational complexity associated with conducting efficient and scalable inference. FOL is not very expressive in representing certain types of relationships between objects, such as "is taller than" or "is closer to". In many cases, it is much more efficient to use other AI methods, such as decision trees or neural networks.
What are some of the challenges in using firstorder logic for AI applications?
In AI applications, FOL is used as the basis for many automated reasoning systems that can help draw new conclusions from existing knowledge. It is used in a wide variety of applications, from planning and diagnosis to knowledge representation and reasoning. However, the integration of logic reasoning with learning and learned models remains a challenge. Despite these challenges, FOL remains a fundamental tool in AI, especially in the field of knowledge representation and reasoning.