✦ScienexySCIENCE KNOWLEDGE LIBRARY
Science reference · SCI-CS-003-043

First-Order Predicate Logic

First-Order Predicate Logic extends propositional logic by representing objects, their properties, relationships, variables, and quantified statements.

∀x (Human(x) → Mortal(x)); ∃x Student(x)

Explanation

First-Order Predicate Logic, also known as First-Order Logic (FOL), is a formal language used to represent knowledge about objects and their relationships. Unlike propositional logic, which treats complete statements as indivisible units, first-order logic describes properties of individual objects using predicates. It includes constants for specific objects, variables for objects that may vary, predicates for properties and relationships, and functions for mapping objects to other objects. Quantifiers allow statements to apply to groups of objects. The universal quantifier (∀) means that a statement applies to every object in a specified domain. The existential quantifier (∃) means that at least one object satisfies a statement. For example, ∀x (Human(x) → Mortal(x)) expresses that every human is mortal. A separate fact, Human(Socrates), can be combined with this rule to infer Mortal(Socrates). First-order logic is more expressive than propositional logic because it can represent general relationships and quantified knowledge. However, reasoning in unrestricted first-order logic is not guaranteed to terminate for every possible input, and practical systems often use restricted fragments or specialized inference procedures.

Variables

SymbolMeaning

x

A variable representing an object in a domain.

Human(x)

A predicate stating that object x is human.

∀

Universal quantifier, meaning for every object.

∃

Existential quantifier, meaning there exists at least one object.

Constant

A symbol referring to a particular object.

Function

A symbol that maps one or more objects to another object.

Example or application

Suppose the knowledge base contains ∀x (Human(x) → Mortal(x)) and Human(Socrates). By universal instantiation and modus ponens, the system can infer Mortal(Socrates).

Text

First-order logic allows AI systems to express statements about individual objects and relationships between them. Universal and existential quantifiers make it possible to represent general rules and claims about whether objects exist.

Key Points

  • First-order logic represents objects, properties, and relationships.

  • Predicates describe properties or relations involving objects.

  • Constants refer to specific objects, while variables represent objects in a domain.

  • Universal and existential quantifiers express general and existence statements.

  • First-order logic is more expressive than propositional logic.

  • Unrestricted first-order logical entailment is semi-decidable rather than generally decidable.

Applications

  • Knowledge-based AI systems

  • Automated theorem proving

  • Natural language understanding

  • Semantic knowledge representation

  • Formal specification and verification

Learning Outcomes

  • Identify constants, variables, predicates, and functions.

  • Explain the meanings of universal and existential quantifiers.

  • Translate simple statements into first-order logic.

  • Apply basic inference to derive conclusions from logical rules.

Practice Questions

  • How does first-order logic differ from propositional logic?

  • What is the difference between ∀ and ∃?

  • Represent the statement 'All birds are animals' using a predicate.

  • How can Human(Socrates) and a general mortality rule lead to a conclusion?

Related Concepts

  • Propositional Logic

  • Logical Inference and Deduction

  • Predicate

  • Quantifiers

  • Knowledge Representation

Common Mistakes

  • Confusing universal and existential quantifiers.

  • Using a predicate without specifying what its arguments represent.

  • Assuming a statement about one object automatically applies to every object.

  • Ignoring the domain over which quantified variables range.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Russell, S. and Norvig, P. Artificial Intelligence: A Modern Approach, first-order logic.
  • Enderton, H. B. A Mathematical Introduction to Logic.

Suggest a correction or source · More in Artificial Intelligence & Machine Learning