First-Order Logic

Readings

http://en.wikipedia.org/wiki/First-order_logic

Reading Questions

• 1. What is a first-order theory?

  2. What distinguishes first-order from higher-order logic?

  3. What does first-order logic cover in additional to declarative propositions? Define these other aspects of first-order logic.

  4. What logical symbols are typical in first-order logic? Are there any of these which are not strictly necessary? If so, which ones?

  5. Give at least one example of each of the following: a valid term; an invalid term; a valid formula; an invalid formula.

  6. What properties must a first-order logical system have for Gödel's incompleteness theorem to mean the system cannot be both consistent and complete?

  7. What makes a variable bound?

  8. What is a sound deductive system? What is a complete deductive system? Can you think of a system which is not sound, not complete, or both?

Lecture Notes

• First-order logic is the standard formal logic for axiomatic systems

• A first-order theory is first-order logic with a specified domain of discourse, at least one interpreted predicate letter, and proper axioms involving the interpreted predicate letter(s).

• First-order logic covers the following:

  • Simple declarative propositions: symbols making up a meaningful sentence

  • Predicates: boolean-valued functions P: X → {true, false}

  • Quantification: binding of a variable by an operator, fixing the domain of discourse

• The following logical symbols are used:

  • Quantifiers:

  • (for all), (there exists)

  • Logical connectives:

  • (conjunction / and), (disjunction / or), (implication), (biconditional), (negation / not)

  • Parentheses and brackets

  • Variables: x, y, z, etc.

  • Equality: =

  • Note that several of these are unnecessary within each group--given

    • , one of and , as well as one of and , can be dropped without changing the functionality of the language

• Additional non-logical symbols serve as predicates, functions, and constants

• The following formation rules define terms and formulae of first-order logic. Note these can be used to write a context-free formal grammar.

  • Terms:

    • Variables: any variable is a term

    • Functions: any expression of the form f(t1, ..., tn) of n arguments, in which each ti is a term and f is a function symbol, is a term

    • Only expressions obtained by a finite number of applications of the variable and function definitions is a term.

  • Formulae:

    • Predicate symbols: if P is a predicate symbol and t1, ..., tn are terms, then P(t1, ..., tn) is a formula

    • Equality: the equality of any two terms is a formula

    • Negation: the negation of any formula is a formula

    • Logical connectives: any logical connective applied to two formulae is a formula

    • Quantifiers: the quantification of a variable and a formula is another formula

    • Only expressions obtained by a finite number of applications of the above definitions are formulae

• Variables may be free or bound; bound variables are quantified, whereas free variables are not quantified

• Consistency:

  • a theory is consistent if a contradiction cannot be proven from the axioms of the theory

  • a theory is complete if, for every formula in the theory, either that formula or the negation of that formula follows from the axioms of the theory

  • Gödel's incompleteness theorem says that first-order theories containing a sufficient portion of the theory of natural numbers cannot be both consistent and complete

  • Alonzo Church and Alan Turing proved that first-order logic is undecidable if the language has at least one predicate (other than equality) which operates on two terms

• A deductive system demonstrates syntactically that one formula is a logical consequence of another formula.

  • Sound: any formula that can be derived in the system is logically valid

  • Complete: every formula which is logically valid is derivable

In-Class Activity

The matrix below represents the relationship between four people (April, Bethany, Colin, and Dave) and four fruits (apples, bananas, cherries, and durian). If a square is filled in then the person (represented as a row) eats the fruit (represented as a column). The function Exy signifies that x eats y; similarly, Eyx signifies that y is eaten by x. Translate each of the following propositions into prose, then fill out the matrix for each proposition. (Multiple ways to fill out the matrix may be possible.) Sample solutions are shown below the problems; please attempt all problems before consulting the solutions.