Languages of First-Order Logic: An Overview
ch. |
Lexicon |
Syntax |
Semantics |
Deductive System |
1,2 | Some collection of predicates and individual constants which
will vary from one first-order language to the next. Examples from the
blocks language include: predicates: Tet(x), Larger(x,y), . . . individual constants: a, b, c, . . . note: the predicates and constants listed above will be different for different first-order languages. Those above are for the blocks language. The constants and predicates for the language of set theory, the language of arithmetic, and other languages that we might develop for various purposes, will be different. Some languages contain function symbols in addition to predicates and constants. These also can vary between languages. The rest of the lexicon consists of expressions that will be part of every first-order language, regardless of what its subject matter is. one logical predicate: = |
The result of putting n individual constants in the argument
places of an n-ary predicate is an atomic sentence. Slightly more formally: if F is a predicate of arity n, and c_{1}, ..., c_{n} are individual constants, then F(c_{1}, ..., c_{n}) is an atomic sentence. |
A language is about a collection of objects, called the universe.
(In a Tarski's World world, the universe is the set of all the blocks in
that world.) Each individual constant refers to one element of the
universe. Each 1-ary predicate expresses a property that objects in the
universe either have or lack; each n-ary predicate for n > 1 expresses
an n-ary relation that may hold between n objects in the universe. An atomic sentence is true if and only if the object(s) referred to by the n constant(s) have the property or relation expressed by the predicate. a = b is true iff the constants 'a' and 'b' both denote the same object |
=Intro: for any name n,
we can write, at any point in a deduction, the sentence n
= n, regardless of what earlier sentences the proof contains
=Elim: If our proof contains a sentence containing a name n, say S(n), and also an identity sentence n = m with n on the left, we can write down a new sentence which is the result of removing one or more occurrences of n from S and replacing it with m. (Note that it is permissible to replace some but not all occurrences of n with m.) |
3-6 | one-place logical connective:
¬
(it's a little odd to call this one a connective, since it applies to a single sentence to form a compound sentence. Call it an operator if you'd like . . .) two-place logical connectives: ∨, ∧ Note: these three connectives are sometimes known as Boolean connectives, after George Boole, who developed "boolean logic." |
if S is a sentence, then so is
its negation,
¬S
if S_{1} and S_{2} are sentences, then so are their disjunction (S_{1} ∨ S_{2}) and their conjunction (S_{1} ∧ S_{2}) |
¬S
is false if S is true, and true if S
is false
(S_{1} ∨ S_{2})_{ } is true if S_{1} or S_{2} or both are true; it is false if S_{1} and S_{2} are both false (S_{1} ∧ S_{2}) is true if S_{1} and S_{2} are both true; otherwise it is false |
¬Intro,
¬Elim ∨Intro, ∨Elim ∧Intro, ∧Elim |
7,8 | two-place logical connectives: →,↔ | if S_{1} and S_{2} are sentences, then so are the conditional (S_{1} → S_{2}) and biconditional (S_{1} ↔ S_{2}) | If S1 is true and S2 is false, then
(S_{1}
→
S_{2}) is false; otherwise it is true (S_{1} ↔ S_{2}) is true iff S_{1} and S_{2} have the same truth value |
→Intro,
→Elim ↔Intro, ↔Elim |
9-14 | variables: x,
y, . . . quantifiers: ∀, ∃ |
An atomic formula is like an atomic sentence, except
that the argument places may be filled by either constants or variables. Negations, disjunctions, conjunctions, and conditionals built up from formulas are also formulas. If P(x) is a formula containing one or more free occurrences of x, then the universal ∀x P(x) and the existential ∃x P(x) are also formulas. |
An n-place predicate is satisfied by a
sequence of n objects iff the result of placing names of the n
objects, in order, in the n argument places of the predicate would be
a true sentence. More generally, a formula with n free variables is satisfied by a sequence of n objects iff the result of replacing the variables by names of the objects, in order, yields a true sentence. A universal sentence ∀x P(x) is true iff the formula P(x) is satisfied by every object in the universe. An existential sentence ∃x P(x) is true iff the formula P(x) is satisfied by at least one object in the universe. |
∀Intro,
∀Elim ∃Intro, ∃Elim |