Skip to main content

First Order Logic

Consider the following argument:

All Philosophy majors at UMD are required to take a logic course. Ann is a Philosophy major at UMD. So, Ann is required to take a logic course.

This argument is valid. The conclusion ("Ann is required to take a logic course") follows from the two premises. However, the logical form of this argument cannot be captured using formulas in propositional logic: From the point of view of propositional logic, since there are no Boolean connectives in the statements making up the argument, each premise and the conclusion would be represented by a different atomic proposition. For example, suppose that PP means "All Philosophy majors at UMD are required to take a logic course.", QQ means "Ann is a Philosophy major at UMD." and RR means "Ann is required to take a logic course.". Then then the above argument is represented as P,Q⇒RP,Q\Rightarrow R. But, of course, this is not a valid argument in propositional logic. There are two main problem with using atomic propositions to represent the statements in this argument:

  1. The second premise and the conclusion are represented by different atomic propositions; however both of these statement are about the same single individual ("Ann").
  2. The logical form of the first premise involve the quantifier "All".

In the remainder of this section, we introduce First Order Logic that can address these issues. First Order Logic is also known as Predicate Logic, Quantified Logic. For simplicity, in this section we only present a fragment of First Order Logic, known as Monadic Predicate Logic.

Objects and Predicates#

In First Order Logic, atomic statements are decomposed into two parts. The first part is the noun-like part representing the subject of a sentence. The second part is the verb-like part called the predicate, which may be a verb or several words. For example, in the sentence:

Ann is a Philosophy major at UMD.

the subject is "Ann" and the predicate is "is a Philosophy major at UMD". We will use capital letters to represent predicates and lower case letters to represent subjects. Let aa mean "Ann" and MM mean "is a Philosophy major at UMD", then we write M(a)M(a) for the statement "Ann is a Philosophy major at UMD".

Atomic Propositions of First Order Logic

Capital letters from the beginning and middle of the alphabet (A,B,…,P,Q,R,…,U,V,WA, B, \ldots, P, Q, R, \ldots, U, V, W) will be used as predicates. Lower case letters from the beginning and middle of the alphabet (a,b,…,s,t,ua, b, \ldots, s, t, u) will be used as subjects and will be called constants. An atomic proposition in first order logic is a predicate followed by a constant in parentheses. For example, A(a)A(a), A(b)A(b), B(a)B(a), …\ldots are examples of atomic propositions.

Notation

Two comments about our notation:

  1. You might wonder why we write the subject after the predicate in our formalism. While there are some logical systems that have formulas in which the subject occurs before the predicate, for example, aΒ isΒ aΒ Ma\ \mathsf{is\ a}\ M, we follow the convention used by many Logicians and use prefix notation, writing the predicate symbol then the subject in parentheses.
  2. We are using the same symbols, e.g. PP, both as a predicate in first order logic and as an atomic proposition in propositional logic. We trust that no confusion will arise since it will always be clear whether we are discussing propositional or first order logic.

Quantifiers#

Returning to the symbolization of the above argument, we need a way to represent the quantifier "All" in the first premise. We can paraphrase the statement "All Philosophy majors at UMD are required to take a logic course" as

For any thing, if that thing is a Philosophy major at UMD, then that thing is required to take a logic course.

It is important that the symbol that we use to represent the thing that is a Philosophy major at UMD is the same symbol used to represent the thing that is required to take a logic course. A first order variable will be represented by a lowercase letter from the end of the alphabet (w,v,x,y,zw, v, x, y, z), possibly with subscripts (e.g., x1x_1, x2x_2, …\ldots). We use first order variables to define quantifiers. In this course, we study two types of quantifiers.

Quantifiers

A quantifier is a symbol βˆ€\forall (for all) or βˆƒ\exists (exists) followed by a variable. Quantifiers βˆ€x\forall x, βˆ€y\forall y, βˆ€z\forall z, …\ldots are called universal quantifiers, and βˆƒx\exists x, βˆƒy\exists y, βˆƒz\exists z, …\ldots are called existential quantifiers.

If AA is a predicate, then we can create a quantified formula by writing a quantifier followed by the predicate where the variable from the quantifier is the subject of the predicate. For instace,

  • βˆ€xA(x)\forall x A(x) means "Everything is an AA".
  • βˆƒxA(x)\exists x A(x) means "Something is an AA".

Formulas of First Order Logic#

The building blocks of formulas of first order logic include:

  1. Terms: There are two types of terms:

    1. Constants: Lower case letters from the beginning of the alphabet a,b,c,…,s,t,ua, b, c, \ldots, s, t, u, possibly with subscripts (e.g., a1,a2,…a_1, a_2, \ldots).
    2. Variables: Lower case letters from the end of the alphabet v,w,x,y,zv, w, x, y, z, possibly with subscripts (e.g., x1,x2,…x_1, x_2, \ldots).
  2. Predicates: Capital letters from the beginning of the alphabet A,B,C,…,P,Q,R,…,S,T,U,VA, B, C, \ldots, P, Q, R, \ldots, S, T, U, V, possibly with subscripts (e.g., P1,P2,…P_1, P_2, \ldots)

  3. Quantifiers: Quantifier symbols followed by a variable βˆ€x,βˆ€y,…,βˆƒx,βˆƒy,…\forall x, \forall y, \ldots, \exists x, \exists y, \ldots

  4. Boolean Connectives: The Boolean connectives from Propositional Logic: Β¬,∧,∨,β†’\neg, \wedge, \vee, \rightarrow, and ↔\leftrightarrow.

  5. Parentheses: Parentheses "))" and "((" are used to make formulas readable.

Putting everything together, formulas of First Order Logic are constructed as follows:

Rules to Construct First Order Formulas
  1. An atomic proposition of First Order Logic is a predicate applied to a term. For example,
    A(a),A(b),…A(x),A(y),…A(a), A(b), \ldots A(x), A(y), \ldots
    are atomic proposition of First Order Logic. Each atomic propositions of First Order Logic is a formula of First Order Logic.
  2. If XX is a formula for First Order Logic, then so is Β¬X\neg X.
  3. If XX and YY are formulas of First Order Logic, then so are
    (X∨Y),(X∧Y),(Xβ†’Y),Β andΒ (X↔Y).(X\vee Y), (X\wedge Y), (X\rightarrow Y),\text{ and }(X\leftrightarrow Y).
  4. If XX is a formula of First Order Logic, then so is a quantifier appended to XX, i.e., βˆ€xX\forall x X and βˆƒxX\exists x X are formulas of First Order Logic.
  5. Nothing else is a formula.
Example

Examples of formulas include:

  1. P(a)P(a),
  2. (P(a)∧Q(a))(P(a)\wedge Q(a)),
  3. (P(x)∧¬Q(b))(P(x)\wedge \neg Q(b)),
  4. βˆ€xP(x)\forall x P(x),
  5. βˆ€x(P(x)β†’Q(x))\forall x(P(x)\rightarrow Q(x)),
  6. βˆƒy(P(x)∧¬Q(y))\exists y (P(x)\wedge \neg Q(y)),
  7. (Q(a)β†’βˆ€y(P(y)∧¬R(a)))(Q(a)\rightarrow \forall y (P(y)\wedge\neg R(a))), and
  8. (Β¬βˆ€xΒ¬P(x)β†’βˆƒxP(x))(\neg \forall x \neg P(x)\rightarrow \exists x P(x)).

Formulas of First Order Logic are more complex than formula of Propositional Logic. It can be challenging to keep straight all the different components of a formula of First Order Logic. The following notes are important to keep in mind when using formulas of First Order Logic.

  1. The choice of variables in a quantified sentence does not matter: βˆ€xA(x)\forall x A(x) and βˆ€yA(y)\forall y A(y) are different formulas, but they mean the same thing.
  2. Quantifiers can be applied to formulas without variables: βˆ€xA(a)\forall x A(a) is a formula. The quantifier in this formula is said to be vacuous since xx does not occur in the scope of the quantifier βˆ€x\forall x. This means that βˆ€xA(a)\forall x A(a) means the same thing as A(a)A(a).
  3. A formula that has a variable that is not bound to any quantifier is said to have a free variable. For example, B(x)B(x) is a formula containing a variable "xx" that is not associated with any quantifier. We can use a pronoun to interpret the variable: "He/she/they is a BB".
  4. Make sure to use parentheses when applying a quantifier to a complex formula: βˆƒxA(x)∧B(x)\exists x A(x) \wedge B(x) and βˆƒx(A(x)∧B(x))\exists x(A(x)\wedge B(x)) are different formulas that do not mean the same thing. The first formula means "There is something that is an AA and she/he/they is a BB". The second formula means "There is something that is both an AA and a BB".

Translations#

Recall the steps to translate English sentences into formulas of propositional logic. The same steps apply when translating into first order logic. Fix the following translation key:

  • aa means "Ann"
  • MM is the predicate "is a Philosophy major at UMD"
  • LL is the predicate "is required to take a logic course"

Using this translation key, we translate the following sentences:

  1. If Ann is a Philosophy major at UMD, then Ann is required to take a logic course.
    Translation: (M(a)β†’L(a))(M(a)\rightarrow L(a))

  2. Ann is a Philosophy major at UMD and is required to take a logic course.
    Translation: (M(a)∧L(a))(M(a)\wedge L(a))

  3. All Philosophy majors at UMD are required to take a logic course.
    Translation: βˆ€x(M(x)β†’L(x))\forall x (M(x) \rightarrow L(x))
    Notes: The logical form of "All AAs are BBs" is a universal quantifier applied to a conditional: βˆ€x(A(x)β†’B(x))\forall x (A(x)\rightarrow B(x)). A common mistake is to translate "All AAs are BBs" as βˆ€x(A(x)∧B(x))\forall x (A(x)\wedge B(x)). This has a different meaning. The sentence βˆ€x(M(x)∧L(x))\forall x (M(x)\wedge L(x)) means "Every thing is a Philosophy major at UMD and is required to take a logic course" which is not equivalent to the above setence.

  4. Some Philosophy majors at UMD are required to take a logic course.
    Translation: βˆƒx(M(x)∧L(x))\exists x (M(x) \wedge L(x)) Notes: The logical form of "Some AAs are BBs" is an existential quantifier applied to a conjunction: βˆƒx(A(x)∧B(x))\exists x (A(x)\wedge B(x)). A common mistake is to translate "Some AAs are BBs" as βˆƒx(A(x)β†’B(x))\exists x (A(x)\rightarrow B(x)). This has a different meaning. The sentence βˆƒx(M(x)β†’L(x))\exists x (M(x)\rightarrow L(x)) means "There is something that either is not a Philosophy major at UMD or is required to take a logic course" which is not equivalent to the above setence.

  5. No Philosophy majors at UMD are required to take a logic course.
    Translation: Β¬βˆƒx(M(x)∧L(x))\neg \exists x (M(x) \wedge L(x))
    Notes: There is an equivalent way to translate this sentence: βˆ€x(M(x)β†’Β¬L(x))\forall x (M(x) \rightarrow \neg L(x)).

  6. Not all Philosophy majors at UMD are required to take a logic course.
    Translation: Β¬βˆ€x(M(x)β†’L(x))\neg \forall x (M(x) \rightarrow L(x))
    Notes: There is an equivalent way to translate this sentence: βˆƒx(M(x)∧¬L(x))\exists x (M(x) \wedge \neg L(x)).

The following table summarizes the translation of sentence with quantifiers. Let AA and BB be predicates:

StatementTranslation
All AA are BBβˆ€x(A(x)β†’B(x))\forall x(A(x)\rightarrow B(x))
Every AA is BBβˆ€x(A(x)β†’B(x))\forall x(A(x)\rightarrow B(x))
Some AA is BBβˆƒx(A(x)∧B(x))\exists x(A(x)\wedge B(x))
No AA is BBΒ¬βˆƒx(A(x)∧B(x))\neg \exists x(A(x)\wedge B(x)) or βˆ€x(A(x)β†’Β¬B(x))\forall x(A(x)\rightarrow\neg B(x))
Some AA is not BBβˆƒx(A(x)∧¬B(x))\exists x(A(x)\wedge\neg B(x))
Every AA is not BBβˆ€x(A(x)β†’Β¬B(x))\forall x(A(x)\rightarrow\neg B(x))
Not every AA is BBΒ¬βˆ€x(A(x)β†’B(x))\neg \forall x(A(x)\rightarrow B(x)) or βˆƒx(A(x)∧¬B(x))\exists x(A(x)\wedge\neg B(x))

One thing to keep in mind when translating English sentences into first order logic is that, typically, universal claims are expressed without using the quantifier "all". For instance, consider the following three sentences:

  1. Birds fly.
  2. UMD students must by vaccinated.
  3. Philosophy students enjoy logic.

Each of these sentences can be paraphrased using the quantifier "all":

  1. All birds fly.
  2. All UMD students must by vaccinated.
  3. All philosophy students enjoy logic.

These statements are translated as follows:

  1. Birds fly.
    For all things, if that thing is a bird, then that thing flies.
    Let BB be the predicate "is a bird" and FF the predicate "flies". Then the translation is:
    βˆ€x(B(x)β†’F(x))\forall x (B(x)\rightarrow F(x))
  2. UMD students must by vaccinated.
    For all things, if that thing is a UMD student, then that thing must be vaccinated.
    Let MM be the predicate "is a UMD student" and VV the predicate "must be vaccinated". Then the translation is:
    βˆ€x(M(x)β†’V(x))\forall x(M(x)\rightarrow V(x))
  3. Philosophy students enjoy logic.
    For all things, if that thing is a Philosophy student, then that thing enjoys logic.
    Let PP be the predicate "is a Philosophy student" and LL the predicate "enjoys logic". Then the translation is:
    βˆ€x(P(x)β†’L(x))\forall x(P(x)\rightarrow L(x))

Practice Questions#

I. Fix the following translation key:

  • LL: "is a logician"
  • MM: "is a mathematician"

Using this translation key, translate the following sentences.

  1. All logicians are mathematicians.
  1. Some logicians are mathematicians.
  1. No logician is a mathematician.
  1. Some logicians are not mathematicians.
  1. Every logician is not a mathematician.
  1. Not every logician is a mathematician.

II. Fix the following translation key:

  • AA: "is an administrator"
  • PP: "is a professor"
  • UU: "is underpaid"
  • OO: "is overworked"
  • GG: "is a graduate student"

Using this translation key, translate the following sentences.

  1. Professors are underpaid and overworked.
  1. Some professor is a graduate student.
  1. Some professors are overworked and underpaid, and all graduate students are.
  1. If professors are overworked, then graduate students are underpaid.
  1. Some graduate students and some professors are underpaid, but no administrator is.
  1. If some professor is overworked, then all professors are.