First-order Logic - Introduction


While propositional logic deals with simple declarative propositions, first-order logic additionally covers predicates and quantification.

A predicate resembles a function that returns either True or False. Consider the following sentences: "Socrates is a philosopher", "Plato is a philosopher". In propositional logic these are treated as two unrelated propositions, denoted for example by p and q. In first-order logic, however, the sentences can be expressed in a more parallel manner using the predicate Phil(a), which asserts that the object represented by a is a philosopher. Thus if a represents Socrates then Phil(a) asserts the first proposition, p; if a instead represents Plato then Phil(a) asserts the second proposition, q. A key aspect of first-order logic is visible here: the string "Phil" is a syntactic entity which is given semantic meaning by declaring that Phil(a) holds exactly when a is a philosopher. An assignment of semantic meaning is called an interpretation.

First-order logic allows reasoning about properties that are shared by many objects, through the use of variables. For example, let Phil(a) assert that a is a philosopher and let Schol(a) assert that a is a scholar. Then the formula

asserts that if a is a philosopher then a is a scholar. The symbol is used to denote a conditional (if/then) statement. The hypothesis lies to the left of the arrow and the conclusion to the right. The truth of this formula depends on which object is denoted by a, and on the interpretations of "Phil" and "Schol".

Assertions of the form "for every a, if a is a philosopher then a is a scholar" require both the use of variables and the use of a quantifier. Again, let Phil(a) assert a is a philosopher and let Schol(a) assert that a is a scholar. Then the first-order sentence

asserts that no matter what a represents, if a is a philosopher then a is scholar. Here, the universal quantifier, expresses the idea that the claim in parentheses holds for all choices of a.

To show that the claim "If a is a philosopher then a is a scholar" is false, one would show there is some philosopher who is not a scholar. This counterclaim can be expressed with the existential quantifier :


  • is the negation operator: is true if and only if is false, in other words if and only if a is not a scholar.
  • is the conjunction operator: asserts that a is a philosopher and also not a scholar.

The predicates Phil(a) and Schol(a) take only one parameter each. First-order logic can also express predicates with more than one parameter. For example, "there is someone who can be fooled every time" can be expressed as:

Here Person(x) is interpreted to mean x is a person, Time(y) to mean that y is a moment of time, and Canfool(x,y) to mean that (person) x can be fooled at (time) y. For clarity, this statement asserts that there is at least one person who can be fooled at all times, which is stronger than asserting that at all times at least one person exists who can be fooled. This would be expressed as:

Asserting the latter (that there is always at least one foolable person) does not signify whether this foolable person is always the same for all moments of time.

The range of the quantifiers is the set of objects that can be used to satisfy them. (In the informal examples in this section, the range of the quantifiers was left unspecified.) In addition to specifying the meaning of predicate symbols such as Person and Time, an interpretation must specify a nonempty set, known as the domain of discourse or universe, as a range for the quantifiers. Thus a statement of the form is said to be true, under a particular interpretation, if there is some object in the domain of discourse of that interpretation that satisfies the predicate that the interpretation uses to assign meaning to the symbol Phil.

Read more about this topic:  First-order Logic

Other articles related to "introduction":

John Frame (theologian) - Selected Works
... Introduction to Presuppositional Apologetics Part 2 ... Van Til The Theologian, 1976 ISBN 0-916034-02-X Medical Ethics, 1988 ISBN 0-87552-261-0 ...
China Miéville - Bibliography - Nonfiction - Introductions To Fiction By Other Authors
... The Borribles An Introduction, 2001 ... Things That Never Happen An Introduction, 2002 ... Wizardry and Wild An Introduction, 2004 ...
Introduction To Metaphysics
... An Introduction to Metaphysics (Introduction à la Métaphysique) is a 1903 essay by Henri Bergson that explores the concept of reality ...
Introduction - Music - Songs and Tracks
... Introduction", by Chicago from The Chicago Transit Authority "Introduction", by Hood from Outside Closer "Introduction", by Kajagoogoo from White Feathers "Introduction", by Mike Oldfield from Tubular ...

Famous quotes containing the word introduction:

    We used chamber-pots a good deal.... My mother ... loved to repeat: “When did the queen reign over China?” This whimsical and harmless scatological pun was my first introduction to the wonderful world of verbal transformations, and also a first perception that a joke need not be funny to give pleasure.
    Angela Carter (1940–1992)

    My objection to Liberalism is this—that it is the introduction into the practical business of life of the highest kind—namely, politics—of philosophical ideas instead of political principles.
    Benjamin Disraeli (1804–1881)

    For the introduction of a new kind of music must be shunned as imperiling the whole state; since styles of music are never disturbed without affecting the most important political institutions.
    Plato (c. 427–347 B.C.)