Formal Logic: Symbolizing Arguments in Quantificational or Predicate Logic

Author: Timothy Eshing
Category: Logic and Reasoning
Word count: 1000

Editor’s note: for many readers, this essay would be more profitably read after reading Formal Logic: Symbolizing Arguments in Sentential Logic by Thomas Metcalf.

There are many varieties of formal logic of varying complexity. Here we survey one that’s somewhat more complex than sentential or propositional logic, but still fairly elementary: quantificational or predicate logic.^[1]

Rudolf Carnap’s notes on Gottlob Frege’s Begriffsschrift, the progenitor of modern quantificational logic. — Rudolf Carnap’s notes on Gottlob Frege’s *Begriffsschrift*, the progenitor of modern quantificational logic.

1. Atomic Formulas

We call symbolized sentences “formulas”. And we call some formulas “atomic” because they can’t be split into simpler formulas. We call all other formulas “molecular” or “complex”. In sentential logic, atomic formulas consist of single sentence letters.^[2]

In quantificational logic, by contrast, atomic formulas have a bit more structure. Now they consist of a subject or subjects and a predicate. Subjects are typically symbolized using lowercase letters, and predicates using uppercase letters. Three examples:

English	Sentential Logic	Quantificational Logic^[3]
“Socrates is human.”	H	H(s)
“Cate is mortal.”	M	M(c)
“Abe loves Beth.”	L	L(a,b)

Our atomic formulas now contain more structure, but they can still behave just like they did in sentential logic, because all of the sentential logical constants are retained in quantificational logic:

“It is not the case that Socrates is human” or ““Socrates is not human”.	¬H	¬H(s)
“Cate is mortal and Abe loves Beth.”	M ∧ L	M(c) ∧ L(a,b)
“Cate is mortal or Abe loves Beth.”	M ∨ L	M(c) ∨ L(a,b)
“If Socrates is human, then Cate is mortal.”	H → M	H(s) → M(c)
“Socrates is human if and only if Abe loves Beth.”	H ↔ L	H(s) ↔ L(a,b)

2. Variables and Quantifiers

Quantificational logic introduces two new kinds of symbols: variables and quantifiers.

Variables are typically symbolized with x, y, etc. Just like in algebra, variables in quantificational logic stand in for unknown or unspecified items. In algebra, variables stand in for numbers. In quantificational logic, they stand in for the subjects of our formulas.^[4] Three examples:

English^[5]	Quantified Logic
“x is human.”	H(x)
“y is mortal.”	M(y)
“x loves y.”	L(x,y)

In these examples, the variables are “free”. But formulas with free variables are not sentences in quantificational logic.^[6] Variables have to be “bound”.

To do that, in quantificational logic we add two more symbols to the roster from sentential logic: the existential and universal quantifiers:

Name	Symbol^[7]	English
Existential Quantifier	∃x	“For some x, …” or “There is/exists an x that …”.
Universal Quantifier	∀x	“For all x, …” or “Every x …”.^[8]

Quantifiers quantify over or “bind” the variables in our formulas. Eight examples:

Formula	English
∃x[H(x)]	“For some x, x is human” or “There is/exists an x that is human”.
∀y[H(y)]	“For all y, y is human” or “Every y is human”.
¬∀z[M(z)]	“It is not the case that for all z, z is mortal” or “Not every z is a mortal”.
∃z[¬M(z)]	“For some z, z is not mortal” or “There is/exists a z that is immortal”.^[9]
∃y[H(y) ∧ M(y)]	“For some y, y is human and y is mortal” or “There is/exists a y that is human and mortal” or simply “Something is a human mortal”.
∀x[H(x) → M(x)]	“For all x, if x is human, then x is mortal” or “Every human is mortal”.
∃y∀z[L(y,z)]	“For some y, for all z, y loves z” or “There is/exists a y that loves every z” or simply “Something loves everything”.
∀y∃z[L(y,z)]	“For all y, there is/exists a z that y loves” or “Every y loves some z” or simply “Everything loves something”.^[10]

Notice how we can bind both atomic (simple) and molecular (complex) formulas. Also notice how we can employ multiple quantifiers, and how their order matters.

3. Proofs

To prove things in quantificational logic, we must specify a domain containing all the individuals that can be subjects in our formulas.

Sometimes our domain includes absolutely everything there is. In that case, “Something is human”, ∃x[H(x)], is true, because humans such as you and me exist. But “Everything is human”, ∀x[H(x)], is false, because other things exist, too, like potatoes. Yet here is something seemingly true of absolutely everything: ∀x[P(x) ∨ ¬P(x)], “Everything is a potato or not a potato”!

Our domain doesn’t have to include absolutely everything though. Suppose our domain only contains three classmates: Abe, Beth, and Cate. They’re all students: S(a), S(b), and S(c). Now we can universally generalize over our domain and infer that everyone is a student: ∀x[S(x)].

We can also go in reverse by instantiating (giving an instance of) that universal generalization. If we know that everyone is a student, ∀x[S(x)], then we can infer that some specific individual in our domain, like Abe, is a student: S(a).

Suppose not all the members of our domain are the same gender, but at least one of them, Beth, is female: F(b). Now we can existentially generalize from that fact and infer that someone is female: ∃x[F(x)].

We can go in reverse here too, but we have to be careful. If we know that someone is female, ∃x[F(x)], but don’t know who that is, then we can instantiate by giving that someone a new name, one we haven’t used already, like “d”. Then we can infer that whomever “d” refers to is female: F(d). It just so happens that “d” could refer to the same person as another letter we’ve already used, like “b” for Beth.

Here’s a formal proof (whose domain includes absolutely everything) using two such inferences. It demonstrates that from “every human is mortal” and “Socrates is human” we can infer “something is mortal”:

Number	Formula	English	Rule^[11]
1.	∀x[H(x) → M(x)]	“Every human is mortal.”	Assumption
2.	H(s)	“Socrates is human.”	Assumption
3.	H(s) → M(s)	“If Socrates is human, then Socrates is mortal.”	From 1
4.	M(s)	“Socrates is mortal.”	From 2 and 3
5.	∴∃x[M(x)]	“Therefore, something is mortal.”	From 4

4. Beyond Quantificational Logic

Once we know the rules for quantificational logic, it’s not difficult to symbolize even more complex sentences and arguments. For example, we might want to quantify over predicates and not just subjects, or formalize generalizations that are probably or necessarily true or false; but those are topics for other entries.

Notes

^[1] Sentential logic is also known as “propositional” or zeroth-order logic. Quantificational (sometimes “quantified”) logic is also known as “predicate” or first-order logic.

Note: the labels “predicate” and “first-order” and even “quantified” are far more common in the literature than “quantificational”. But “quantified” isn’t quite apt, because the logic itself is not quantified. And “predicate” isn’t quite apt, because what’s distinctive about the logic is not just the subject-predicate structure of its sentences, but also the use of quantifiers ranging over subject variables. “First-order” is apt, because herein we only quantify over subjects, and not predicates (as we do in second-order logic); but that’s a more mysterious label than “quantificational”, so the latter is the preferred term in this essay.

^[2] See section 1 of Formal Logic: Symbolizing Arguments in Sentential Logic by Thomas Metcalf.

^[3] Notice how compared to English the order of subject and predicate is reversed: the predicate comes first, next comes the subject(s) to which it applies.

^[4] But not predicates. However, in second-order logic we can also quantify over predicates.

^[5] Technically, we should write “⌜x⌝ is human”, “⌜y⌝ is mortal”, etc., where the variables x and y are placed in quasi-quotes. This is because we’re not saying that the letter x itself is human, or that the letter y itself is mortal, but rather that something as yet undefined we’ll put in place of x or y (like Abe or Beth) is human or mortal. For more information, see note 6 of Formal Logic: Symbolizing Arguments in Sentential Logic by Thomas Metcalf. As in that essay, herein quasi-quotation marks are left out to avoid confusion.

^[6] To be more precise: such formulas are well-formed expressions, but they are not semantically complete, which means we cannot evaluate them for truth or falsity. “Sentence” is a technical term defined as a well-formed formula with no free variables. In quantificational logic, only sentences can have truth-values. Formulas with free variables are often called “sentence functions” (or something similar) to indicate that they are not themselves sentences, but mere building blocks of sentences: they can be turned into sentences by either (i) replacing all their free variables with one or more individual constants representing one or more definite subjects, or (ii) binding their variables with at least one quantifier as described in the main text above.

^[7] Alternative symbol for the universal quantifier: “(x)”. Sometimes people place the symbols above in parentheses too: “(∃x)” and “(∀x)”, but doing so is just for readability; it doesn’t change how the logic works.

^[8] Note: the universal quantifier does not imply that anything exists. For example, we can rightly say that “All unicorns are horned”, translating that into quantified logic as “∀x[U(x) → H(x)]”, without committing ourselves to the existence of any unicorns. So “All unicorns are horned” can be true, even when “There exists a unicorn”, “∃x[U(x)]”, is false.

^[9] Notice that this example means the same as the previous one: we can swap “¬∀x” with “∃x¬”, as well as “∀x¬” with “¬∃x”. This is because the quantifiers are duals, which means we can define one in terms of the other plus the negation operator: “∀x” is equivalent to “¬∃x¬”, and “∃x” is equivalent to “¬∀x¬”. For example, “Everything is a potato” means the same as “nothing is not a potato”, and “something is a potato” means the same as “not everything is not a potato”.

^[10] To be clear: “Everything loves something, but not necessarily the same thing”. To formalize “Everything loves one and the same thing” we’d write “∃y∀z[L(z,y)]”, that is, “There is something that everything loves”. Compare this to the previous example!

^[11] In most proof systems, we don’t just say where the line came from; we also say why, by citing a specific rule for each line. To save time and avoid confusion, in this presentation we’ve just said where each line comes from, without saying how. Line 3 follows from line 1 by universal instantiation and line 5 follows from line 4 by existential generalization. Both of these rules were discussed in the main text above. The other two rules we discussed, universal generalization and existential instantiation, are more complicated to use, so we’ve avoided them in this example. Line 4 follows from lines 2 and 3 by a different rule, called modus ponens, which works like this: from the truth of both “P” and “If P, then Q”, we can infer that “Q” is true, too; but this and other rules of inference are topics for other entries.