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 $P$ means "All Philosophy majors at UMD are required to take a logic course.", $Q$ means "Ann is a Philosophy major at UMD." and $R$ means "Ann is required to take a logic course.". Then then the above argument is represented as $P,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 $a$ mean "Ann" and $M$ mean "is a Philosophy major at UMD", then we write $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, \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, \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(b)$, $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\ \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. $P$, 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, z$), possibly with subscripts (e.g., $x_1$, $x_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 $\forall x$, $\forall y$, $\forall z$, $\ldots$ are called universal quantifiers, and $\exists x$, $\exists y$, $\exists z$, $\ldots$ are called existential quantifiers.

If $A$ 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,

• $\forall x A(x)$ means "Everything is an $A$".
• $\exists x A(x)$ means "Something is an $A$".

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, \ldots, s, t, u$, possibly with subscripts (e.g., $a_1, a_2, \ldots$).
   2. Variables: Lower case letters from the end of the alphabet $v, w, x, y, z$, possibly with subscripts (e.g., $x_1, x_2, \ldots$).

2. Predicates: Capital letters from the beginning of the alphabet $A, B, C, \ldots, P, Q, R, \ldots, S, T, U, V$, possibly with subscripts (e.g., $P_1, P_2, \ldots$)

3. Quantifiers: Quantifier symbols followed by a variable $\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), \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 $X$ is a formula for First Order Logic, then so is $\neg X$.
3. If $X$ and $Y$ are formulas of First Order Logic, then so are
   $$(X\vee Y), (X\wedge Y), (X\rightarrow Y),\text{ and }(X\leftrightarrow Y).$$
4. If $X$ is a formula of First Order Logic, then so is a quantifier appended to $X$, i.e., $\forall x X$ and $\exists x X$ are formulas of First Order Logic.
5. Nothing else is a formula.

Example

Examples of formulas include:

1. $P(a)$,
2. $(P(a)\wedge Q(a))$,
3. $(P(x)\wedge \neg Q(b))$,
4. $\forall x P(x)$,
5. $\forall x(P(x)\rightarrow Q(x))$,
6. $\exists y (P(x)\wedge \neg Q(y))$,
7. $(Q(a)\rightarrow \forall y (P(y)\wedge\neg R(a)))$, and
8. $(\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: $\forall x A(x)$ and $\forall y A(y)$ are different formulas, but they mean the same thing.
2. Quantifiers can be applied to formulas without variables: $\forall x A(a)$ is a formula. The quantifier in this formula is said to be vacuous since $x$ does not occur in the scope of the quantifier $\forall x$. This means that $\forall x A(a)$ means the same thing as $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)$ is a formula containing a variable "$x$" that is not associated with any quantifier. We can use a pronoun to interpret the variable: "He/she/they is a $B$".
4. Make sure to use parentheses when applying a quantifier to a complex formula: $\exists x A(x) \wedge B(x)$ and $\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 $A$ and she/he/they is a $B$". The second formula means "There is something that is both an $A$ and a $B$".

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:

• $a$ means "Ann"
• $M$ is the predicate "is a Philosophy major at UMD"
• $L$ 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)\rightarrow L(a))$

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

3. All Philosophy majors at UMD are required to take a logic course.
   Translation: $\forall x (M(x) \rightarrow L(x))$
   Notes: The logical form of "All $A$s are $B$s" is a universal quantifier applied to a conditional: $\forall x (A(x)\rightarrow B(x))$. A common mistake is to translate "All $A$s are $B$s" as $\forall x (A(x)\wedge B(x))$. This has a different meaning. The sentence $\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: $\exists x (M(x) \wedge L(x))$ Notes: The logical form of "Some $A$s are $B$s" is an existential quantifier applied to a conjunction: $\exists x (A(x)\wedge B(x))$. A common mistake is to translate "Some $A$s are $B$s" as $\exists x (A(x)\rightarrow B(x))$. This has a different meaning. The sentence $\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: $\neg \exists x (M(x) \wedge L(x))$
   Notes: There is an equivalent way to translate this sentence: $\forall x (M(x) \rightarrow \neg L(x))$.

6. Not all Philosophy majors at UMD are required to take a logic course.
   Translation: $\neg \forall x (M(x) \rightarrow L(x))$
   Notes: There is an equivalent way to translate this sentence: $\exists x (M(x) \wedge \neg L(x))$.

The following table summarizes the translation of sentence with quantifiers. Let $A$ and $B$ be predicates:

Statement	Translation
All $A$ are $B$	$\forall x(A(x)\rightarrow B(x))$
Every $A$ is $B$	$\forall x(A(x)\rightarrow B(x))$
Some $A$ is $B$	$\exists x(A(x)\wedge B(x))$
No $A$ is $B$	$\neg \exists x(A(x)\wedge B(x))$ or $\forall x(A(x)\rightarrow\neg B(x))$
Some $A$ is not $B$	$\exists x(A(x)\wedge\neg B(x))$
Every $A$ is not $B$	$\forall x(A(x)\rightarrow\neg B(x))$
Not every $A$ is $B$	$\neg \forall x(A(x)\rightarrow B(x))$ or $\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 $B$ be the predicate "is a bird" and $F$ the predicate "flies". Then the translation is:
   $\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 $M$ be the predicate "is a UMD student" and $V$ the predicate "must be vaccinated". Then the translation is:
   $\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 $P$ be the predicate "is a Philosophy student" and $L$ the predicate "enjoys logic". Then the translation is:
   $\forall x(P(x)\rightarrow L(x))$
   

Practice Questions

I. Fix the following translation key:

• $L$: "is a logician"
• $M$: "is a mathematician"

Using this translation key, translate the following sentences.

1. All logicians are mathematicians.

2. Some logicians are mathematicians.

3. No logician is a mathematician.

4. Some logicians are not mathematicians.

5. Every logician is not a mathematician.

6. Not every logician is a mathematician.

II. Fix the following translation key:

• $A$: "is an administrator"
• $P$: "is a professor"
• $U$: "is underpaid"
• $O$: "is overworked"
• $G$: "is a graduate student"

Using this translation key, translate the following sentences.

1. Professors are underpaid and overworked.

2. Some professor is a graduate student.

3. Some professors are overworked and underpaid, and all graduate students are.

4. If professors are overworked, then graduate students are underpaid.

5. Some graduate students and some professors are underpaid, but no administrator is.

6. If some professor is overworked, then all professors are.