Predicate logic, or first-order logic, is a formal system that extends the capabilities of propositional logic. It introduces the concepts of predicates, variables, and quantifiers.

In predicate logic, the notions from the propositional logic such as truth values and logical connectives still apply but basic propositions will be replaced with proposition involving predicates and quantifiers.

Subtopics

Notations

Below is the notation used in this notes and other related notes:

  • names: , (lowercase letters a-t)
  • predicate: , (uppercase letters A-Z)
  • variables: , (lowercase letters u-z)

We also use metavariables when we talks about forms rather than a concrete sentence:

  • arbitrary well-formed formula: , (greek letters)
  • arbitrary predicate: ,
  • arbitrary names: ,
  • arbitrary variables: ,

Limitation of Propositional Logic

Consider the following argument

“All men are mortal; Socrates is a man; therefore, Socrates is mortal.”

The argument is intuitive valid.

Let’s try to symbolize this into propositional logic. We can’t find any connectives so all sentences become basic propositions:

Which is an invalid argument.

Let’s think why the original argument is valid, intuitively. That’s because it has the following structure:

All arguments with this structure is valid, but the propositional logic does not have construct to capture internal structure of each propositions here.

Names and Predicates

See also: predicates

We have seen that the internal structures of basic propositions can be important. We start with the simplest kind of basic propositions and distinguish its part, name and predicates.

Let’s consider the proposition “Socrates is a man.” We can split it into two parts:

  • name: pick an individual (i.e. “Socrates”)
  • predicates: pick up a property that things may process (i.e. “is a man”)

Names are usually symbolized by lowercase letters (last six letters in the alphabet are reserved for variables) and predicates will be symbolized by uppercase letters . So the above proposition may be symbolize as if we have the glossary .

We usually avoid using as a predicate name, since it is reserved for the identity predicate.

A predicate can be place to represent a n-ary relation. They can be denoted with superscripts attached to indicate how many platmce they are. E.g. , , though this is usually not necessary and clear from context.

Variables and Quantifiers

see also: quantifiers

First-order logic also introduced two kinds of quantifiers:

  • universal quantifier: (forall)
    • means “for all x, alpha is true”
  • existential quantifier: (there exists)
    • means “there exists an x, such that for that x, alpha is true”

Quantifiers will also introduce variables, which are often denoted by letters from to (though people tends to use first). If a variable is in the scope of a quantifier, it is said to be bound. Otherwise it is said to be free.

Semantics

In first-order logic, an interpretation is more complex than in propositional logic. Instead of simply assigning truth values to basic propositions, an interpretation consists three components:o

  • Domain (or Universe of Discourse): The set of objects that the logic talks about
  • Referents of names (refer to an object)
  • Extension of predicates (for which set of the objects are the predicates true)

Variables don’t have a fixed referent, and what they refer to can change during evaluation.

For example, we can have an interpretation of

And under this interpretation, we can say that is true but is false.

Note

You may ask why we don’t write domain as something like , this is because we want to distinguish objects from names, as multiple names can refer to the same objects and objects don’t need to have a name. Using numbers is a common convention.