First-Order Logic

First-order logic is a system of symbolic logic that can be attributed largely to the work of Gottlob Frege. First-order logic expands a system of propositional logic by adding the concepts of predicates and quantifiers.

Predicates

While a propositional logic system places full sentences within propositional variables, such as P or Q, a first-order logic allows you to examine the subjects and predicates within a sentence.

For example, a propositional logic may contain an entire sentence, such as “The llama is chewing” as simply ‘C’, a first-order logic would break apart the subject of the sentence, the llama and the predicate, is chewing.

Then, a constant is assigned to the subject of the sentence, such as l for ‘llama’, and a predicate symbol is assigned to the predicate, such as C⁽¹⁾ or Cx for ‘x is chewing’.

With this new symbolization, rather than simply stating ‘C’, we can state ‘Cl’ and perform operations that relate to the parts of that statement.

Predicate symbols can also have multiple places. For example, the phrase “x loves y” could be represented as ‘L⁽²⁾’ or ‘Lxy’. If we plug in the constants r for Romeo and j for Juliet, we can say “Romeo loves Juliet” simply with Lrj.

Quantifiers

In addition to predicate sentences, a first-order logic adds quantifiers. Quantifiers are used to handle statements like “every” and “some”.

The two quantifiers are the universal quantifier, ∀, and the existential quantifier, ∃.

For example, if we wanted to say that all potatoes are vegetables, we could then formally write the following:

∀x(Px → Vx)

In this example, Px is taken to mean “x is a potato” and Vx translates to “x is a vegetable”. The quantifier ∀x means “for every x”, and the parentheses are used to mark its scope. Therefore, this entire formula reads “For every x, if x is a potato, then x is a vegetable”. Less formally, we can simply translate this back to “all potatoes are vegetables”.

The existential quantifier works in a similar way. If we want to say that some potatoes (Px) that are cut (Cx), we would write it as “there exists an x such that x is a potato, and x is cut”, or formally:

∃x(Px ∧ Cx)

Note that while the universal quantifier means all, or for every, the existential quantifier means some, which, in the case of logic, means at least one.

Identity

The notion of identity is a common part of a system of first-order logic. Systems that include this notion are appropriately called “first-order logic with identity”. Identity is used to indicate when a constant or variable refers to another constant or variable — that is, when constants and variables do, or do not, represent the same object.

For example, if we want to say that Sally loves everyone, we may be tempted to symbolize the expression as follows:

∀xLsx

If s is Sally and Lxy means “x loves y”, then this reads as “For every x, Sally loves x”. This may be satisfactory, but it should be noted that, strictly speaking, this means “Sally loves everybody, including herself”. But suppose we really mean that Sally loves everybody except herself, or Sally loves everybody else. To do this, we need identity.

Identity is sometimes treated as an operator, though some insist that it is a relation. Either way, identity is symbolized with the equals symbol (=), and is used as an operator between constants and/or variables. When two constants or variables are not equal, we use the inequality symbol (≠).

Now, we can symbolize our expression as follows:

∀x(x ≠ s → Lsx)

This now reads “For every x, if x is not Sally, then Sally loves x”. This should be an accurate representation of our intended meaning, that Sally loves everybody, not including herself.