3 Examples of well-formed formulas

Instead of giving the lengthy definition of well-formed formulas, we will simply look at some examples from arithmetic together with their ordinary interpretation. Our domain here is the set of natural numberNatural number can mean either a positive integer ( 1, 2, 3, 4,. or a non-negative integer ( 0, 1, 2, 3, 4,. Natural numbers have two main purposes: they can be used for counting ("there are 3 apples on the table"), or they can be used for ordering ("thiss:

(i.e.: forAll x, thereExists y suchThat y isGreaterThan x )

For every number x there exists a bigger number y. That's true.

(i.e.: thereExists y suchThat forAll x, y isGreaterThan x )

There exists a number y which is bigger than every number x. That's not true.

(i.e.: forAll x, ( thereExists y suchThat 6*y=x) implies (thereExists y suchThat 3*y=x) )

If a number x is divisible by 6, then it is also divisible by 3. True.

(i.e.: thereExists x suchThat (not ThereExists y suchThat y < x ) )

There exists a number x such that there doesn't exist a smaller number y. True (take x=0).

Now one would have to write down 15 logical axioms and 2 inference rules to completely specify the first-order calculus. How can one be sure that those axioms and rules are enough? This is the subject of Gödel's completeness theoremModel theory Godel's completeness theorem is a fundamental theorem in mathematical logic proved by Kurt Godel in 1929. It states, in its most familiar form, that in first-order predicate calculus every universally valid formula can be proved. The word "pr: if you start out with some subject matter axioms and you look at a certain statement, then it is possible to prove that statement using only the subject matter axioms, the 15 logical axioms and the two inference rules if and only if the statement is true in every domain in which the subject matter axioms are true. (See also Leon HenkinLeon Henkin is a logician, currently Emeritus Professor at Berkeley. He is principally known for the "Henkin Completeness Proof": his version of the proof of the semantic completeness of standard systems of first-order logic. Henkin's result was not novel)

4 An important type of well formed formulas: clauses

A term is defined as follows:

1. A variableIn computer science and mathematics, a variable is a symbol denoting a quantity or symbolic representation. In mathematics, a variable often represents an unknown quantity; in computer science, it represents a place where a quantity can be stored. Variabl is a term.
2. An object constant is a term.
3. If , ..., are terms and is a function constant of arityIn mathematics, the arity of a function or an operator is the number of arguments or operands it takes, A function or operator can thus be described as unary binary ternary etc. Terms such as 7-ary or n ary are also used. Sometimes, it is useful to consid , then is a term.

A atom (or atomic formula) is a well-formed formula of the form , where is a predicate constant of arity and are terms.

A literal is either an atom or the negationNegation in its most basic sense, changes the truth value of a statement to its opposite. It is an operation needed chiefly in logic, mathematics, and grammar. Logic and mathematics In logic, logical negation is a unary logical operator that reverses the of an atom.

A clause is a well-formed formula of the form

,

where are literals and are variables in them. Alternatively, a clause can be thought of as the set of literals

.

A unit clause is simply a clause with only one literal.

5 Grammar

The "vocabulary" is composed of

1. Predicate letters which are capital letters of the alphabet.
2. Lowercase letters which are designated to be constant terms.
3. Lowercase letters which are designated to be variable terms.
4. Function letters (optional: not necessary for a purely logical pred.calc.)
5. Symbols denoting logical operators: ¬, , , →, ↔.
6. Symbols denoting quantifiers: ∀, ∃.
7. Left and right parenthesis.

The set of well-formed formulae (wffs) is recursively defined by the following rules:

1. Basis: Atomic formulae, defined as in the previous section about "clauses".
   If an atomic formula contains variable terms, then the formula is an open sentence, and each time the variable appears in the sentence, it is called a "free instance" of that variable.
2. Inductive Clause I: If φ is a wff, then ¬ φ is a wff.
3. Inductive Clause II: If φ and ψ are wffs, then (φ ∧ ψ), (φ ∨ ψ), (φ → ψ), (φ ↔ ψ) are wffs.
4. Inductive Clause III: If φ is a wff containing a free instance of variable x, then and are wffs. (Then any instance of x is said to be bound — not free — in and .)
5. Closure Clause: Nothing else is a wff.

Grammar pays no attention to the truth-value of a wff. A wff may be valid, invalid, provable, decided, undecided, necessary, or contingent; grammar is not concerned with semantics, but only with syntax. Likewise, terms have no truth-value. If function letters are chosen to be included in the vocabulary, then a function applied to its arguments does not (implicitly) return a truth-value, but it does have a constant term as its return-value (especially if all the function's arguments are themselves constant terms). If a function is replaced by its return-value during evaluation, then the truth-value of the well-formed formula remains unchanged, but all well-formed formulae have truth-values.

6 Calculus

Predicate calculus is an extension of propositional calculus. If propositional calculus is defined with eleven axioms and one inference rule ( modus ponens), not counting some auxiliary laws for the logical equivalence operator, then predicate calculus can be defined by appending four additional axioms and one additional inference rule.

6.1 Axiomatic Extension

The following four logical axioms characterize a predicate calculus:

• PRED-1:
• PRED-2:
• PRED-3:
• PRED-4:

These are actually axiom schemata, because the predicate letters W and Z in them can be replaced by any other predicate letters, without altering the validity of these formulae.

6.2 Inference rule

The inference rule called Generalization is characteristic of predicate calculus. It can be stated as

where Z(x) is supposed to stand for an already-proven theorem of predicate calculus. The predicate letter Z can be replaced by any other predicate letter.

Notice that Generalization is analogous to the Necessitation Rule of modal logic, which is

.

7 Case study: first-order Peano axioms

The Peano axioms for the natural numbers are sometimes formulated as second-order statements (the induction axiom talks about all "properties" or all "sets of numbers"), but this is not necessary if one is willing to allow infinitely many first-order axioms. A first-order version of the Peano axioms follows.

We are using the object constants 0 and 1, the function constants + and *, and the predicate constant =. Here are the axioms:

1. • i.e.: forAll x, not (0 = x + 1)
   • i.e.: no number has 0 as its successor
2. • i.e.: forAll x, forAll y, not(x=y) implies not(x + 1 = y + 1)
   • i.e.: if x ≠ y, then x+1 ≠ y+1
3. • i.e.: forAll x, x + 0 = x
4. • i.e.: forAll x, forAll y, x + (y + 1) = (x + y) + 1
   • i.e.: for all x and y, x + (y + 1) = (x + y) + 1
5. • i.e.: forAll x, x * 0 = 0
6. • i.e.: forAll x, forAll y, x * (y + 1) = x * y + x
   • i.e.: for all x and y, x * (y + 1) = x * y + x
7. This is an axiom scheme consisting of infinitely many axioms. If P(x) is any formula involving the constants 0, 1, +, *, = and a single free variable x, then the following formula is an axiom:
   • i.e.: ( P(0) and (forAll x, ( P(x) implies P(x + 1) ) ) ) implies (forAll x, P(x) )
   • i.e.: if something is true for 0, and from its being true for x it follows that it is also true for x + 1, then it is true for all x (induction)

Axioms 1, 2 and 7 are the traditional Peano axioms while axioms 3-6 serve to define addition and multiplication. If one omits the function constant * and axioms 5 and 6 and allows in scheme 7 only formulas without *, then one gets the very interesting Presburger arithmetic.

8 References

• Introduction to mathematical logic
• Metamath: a project to construct mathematics using an axiomatic system based on propositional calculus, predicate calculus, and set theory

<Hide>