Formal Logic/Predicate Logic/The Predicate Language

From Wikibooks, open books for an open world
< Formal Logic‎ | Predicate Logic
Jump to: navigation, search
← Goals ↑ Predicate Logic Formal Syntax →



The Predicate Language[edit]

This page informally describes our predicate language which we name \mathcal{L_P}\,\!. A more formal description will be given in subsequent pages.

Language components[edit]

Use of \mathcal{L_P}\,\! occurs in the context of a domain of objects. Ascribing a property to everything is interpreted as ascribing it just to everything in the domain.

Terms[edit]

Variables will be lower case letters n through z. Variables serve roughly as placeholders or perhaps pronouns, particularly in general statements about all or some objects. A variable could serve as the 'it' in 'For any number, if it is even then it is not odd'.

Operation letters of zero or more places will consist of lower case letters a through m. Since the same letters are used for operation letters of any number of places, some disambiguation will be necessary. For now, just let the context decide the number of places. Note, though, that variables always have zero places.

Terms can be one of the following.

  • A variable.
  • A zero-place operation letter.
  • An n-place operation letter (n being 1 or greater) followed by a parenthesised list of n terms. Examples include
f(c)\,\!
g(x, y)\,\!

Names are terms in which no variables occur. Names name. In particular, they name objects in the domain. Variables, and so terms containing variables (i.e., terms that are not names), do not name.

For the remainder of this page, assume the following translations.

c\ :\ \ \mbox{Cain}\,\!
f(x)\ :\ \ \mbox{the father of}\ x\,\!
g(x, y)\ :\ \ \mbox{the greater of}\ x\ \mbox{and}\ y\,\!

With the right set of characters in the domain, biblical tradition has

c\,\!
f(c)\,\!

naming Cain and Adam respectively. The term

g(x, y)\,\!

doesn't name anything. However, if we abuse \mathcal{L_P}\,\! a bit by permitting numerals to serve as zero place operation letters, then the terms

g(7, 3)\,\!
g(3, 3)\,\!

name 7 and 3 respectively (assuming that 7 and 3 are in the domain).

Primitive formulae[edit]

Predicate letters of zero or more places will consist of capital letters A through Z. The same letters will be used for predicate letters of any number of places, so, as with operation letters, we will need to disambiguate. Again as with operation letters, we will let context decide the number of places for now. Notice that zero-place predicate letters are sentence letters we are familiar with from sentential logic.

Primitive formulae can be one of the following.

  • A zero-place predicate letter (that is, a sentence letter).
  • An n-place predicate letter (n being 1 or greater) followed by a parenthesised list of n terms. Examples include
\mathrm{P}\,\!
\mathrm{F}(f(c))\,\!
\mathrm{G}(g(x, y), u, v)\,\!

If \mathrm{P}\,\! translates 'Snow is white', then it is true. However, it is false if it translates 'Snow is blue'.

Suppose we add

\mathrm{F}(x)\ :\ \ x\ \mbox{is bald}\,\!
b\ :\ \ \mbox{Yul Brenner}\,\!
k\ :\ \ \mbox{Don King}\,\!

to the translations above. Then

\mathrm{F}(f(c))\,\!

is true or false according with whether Adam was bald. We say that \mathrm{F}\,\! is true of all bald things and false of all non-bald things. Thus the first of

\mathrm{F}(b)\,\!
\mathrm{F}(k)\,\!

is true while the second is false. For confirmation of these truth evaluations, see pictures accompanying the Wikipedia articles on Yul Brenner and Don King. (Note. The picture of Don King has been removed from the Wikipedia article. However, he rather famously is not bald.)

Now add

\mathrm{G}(x, y, z)\ :\ \ x\ \mbox{is between}\ y\ \mbox{and}\ z\,\!

to the translations above. Then

\mathrm{G}(g(x, y), u, v)\,\!

is neither true nor false because, as above,

g(x, y)\,\!

does not name anything. For that matter, neither do the variables u\,\! or v\,\!. But if we again abuse \mathcal{L_P}\,\! a bit by permitting numerals to serve as zero place operation letters, then the first of

\mathrm{G}(g(3, 3), 1, 4)\,\!
\mathrm{G}(g(7, 3), 1, 4)\,\!

is true while the second is false.

Sentential connectives[edit]

The predicate language \mathcal{L_P}\,\! will use sentential connectives just as they were used in the sentential language \mathcal{L_S}\,\!. These were:

\lnot,\ \land,\ \lor,\ \rightarrow,\ \mathrm{and}\ \leftrightarrow\,\!

Using the translations already set above (together with letting numerals be zero-place operation letters),

\mathrm{F}(f(d)) \lor \mathrm{G}(g(7, 3), 1, 4)\,\!

is true while

\mathrm{F}(f(d)) \land \mathrm{G}(g(7, 3), 1, 4)\,\!

is false.

Quantifiers[edit]

Quantifiers are special symbols that allow us to construct general sentences which are about all thing or about some (at least one) things.

\mbox{Universal quantifier:}\ \forall\,\!

  • \forall x\,\! translates to English as 'for all x'.
  • \forall x\ \mathrm{F}(x)\,\! is called a universal generalization.
  • \forall x\ \mathrm{F}(x)\,\! is true if \mathrm{F}(x),\! is true of all objects in the domain. Roughly speaking, it is true if
\mathrm{F}(a_1) \land \mathrm{F}(a_2) \land ... \land \mathrm{F}(a_n)\,\!
where each (a_i)\,\! names an object in the domain and all objects in the domain are named. This is only a rough characterization, however. First, we do not require that all objects in the domain have a name in the predicate languange. Second, we allow there to be infinitely many objects in the domain but do not allow infinitely long sentences.
  • Some authors use (x)\,\! instead of \forall x\,\!. This notation is semi-obsolete and is becoming ever less frequent.

\mbox{Existential quantifier:}\ \exists\,\!

  • \exists x\,\! translates to English as 'there exists an x' or, perhaps a bit more clearly, 'there exists at least one x'.
  • \exists x\ \mathrm{F}(x)\,\! is called an existential generalization.
  • \exists x\ \mathrm{F}(x)\,\! is true of at least one object in the domain. Roughly speaking, it is true if
\mathrm{F}(a_1) \lor \mathrm{F}(a_2) \lor ... \lor \mathrm{F}(a_n)\,\!
where each (a_i)\,\! names an object in the domain and all objects in the domain are named. This is only a rough characterization, however. First, we do not require that all objects in the domain have a name in the predicate languange. Second, we allow there to be infinitely many objects in the domain but do not allow infinitely long sentences.

Translation[edit]

Using the translation scheme

\mathrm{F}(x)\ :\ \ x\ \mbox{is a number}\,\!
\mathrm{G}(x)\ :\ \ x\ \mbox{is prime}\,\!

we translate as follows.

All numbers are prime.
\forall x(Fx \rightarrow Gx)\,\!
Some numbers are prime.
\exists x(Fx \land Gx)\,\!
No numbers are prime.    (two equivalent alternatives are given)
\forall x(Fx \rightarrow \lnot Gx)\,\!
\lnot \exists x(Fx \land Gx)\,\!
Some numbers are not prime.
\exists x(Fx \land \lnot Gx)\,\!


Now using the translation scheme

\mathrm{P}(x)\ :\ \ x\ \mbox{is a person}\,\!
\mathrm{L}(x, y)\ :\ \ x\ \mbox{loves}\ y\,\!
g\ :\ \ \mbox{George}\,\!
m\ :\ \ \mbox{Martha}\,\!

we can translate as follows.

George loves Martha.
\mathrm{L}(g, m)\,\!
Martha loves George.
\mathrm{L}(m, g)\,\!
George and Martha love each other.
\mathrm{L}(g, m) \land \mathrm{L}(m, g)\,\!


We can further translate as follows.

Everybody loves everybody.    (the second alternative assumes only persons in the domain)
\forall x (\mathrm{P}(x) \rightarrow \forall y (\mathrm{P}(y) \rightarrow \mathrm{L}(x, y)))\,\!
\forall x \forall y \mathrm{L}(x, y)\,\!
Somebody loves somebody.    (the second alternative assumes only persons in the domain)
\exists x (\mathrm{P}(x) \land \exists y (\mathrm{P}(y) \land \mathrm{L}(x, y)))\,\!
\exists x \exists y \mathrm{L}(x, y)\,\!
Everybody loves somebody (or other).    (the second alternative assumes only persons in the domain)
\forall x (\mathrm{P}(x) \rightarrow \exists y (\mathrm{P}(y) \land \mathrm{L}(x, y)))\,\!
\forall x \exists y \mathrm{L}(x, y)\,\!
Somebody is loved by everybody.    (the second alternative assumes only persons in the domain)
\exists y \forall x (\mathrm{P}(y) \land (\mathrm{P}(x) \rightarrow \mathrm{L}(x, y)))\,\!
\exists y \forall x \mathrm{L}(x, y)\,\!
Everybody is loved by somebody (or other).    (the second alternative assumes only persons in the domain)
\forall x \exists y (\mathrm{P}(x) \rightarrow \mathrm{P}(y) \land \mathrm{L}(y, x))\,\!
\forall x \exists y \mathrm{L}(y, x)\,\!
Somebody loves everybody.    (the second alternative assumes only persons in the domain)
\exists y \forall x (\mathrm{P}(y) \land (\mathrm{P}(x) \rightarrow \mathrm{L}(y, x)))\,\!
\exists y \forall x \mathrm{L}(y, x)\,\!