2 - Formal Proof in First Order Logic

Summary

Cambridge LCF proofs are conducted in PPλ, a logic of domain theory. Leaving aside domains — discussed in later chapters — PPλ is a typical natural deduction formulation of first order logic. This chapter introduces formal proof, first order logic, natural deduction, and sequent calculi. The discussion of semantics is brief and informal; the emphasis is how to construct formal proofs. See a logic textbook for a proper account of model theory.

If you seriously intend to construct proofs, memorizing the inference rules is not enough. You must learn the individual characteristics and usage of each rule. Many sample proofs are given; study every line. Work the exercises.

Fundamentals of formal logic

A formal logic or calculus is a game for producing symbolic objects according to given rules. Sometimes the motivation of the rules is vague; with the lambda calculus there ensued a protracted enquiry into the meaning of lambda expressions. But usually the rules are devised with respect to a well-understood meaning or semantics. Too many of us perform plausible derivations using notations that have no precise meaning. Most mathematical theories are interpreted in set theory: each term corresponds to a set; each rule corresponds to a fact about sets. Set theory is taken to be the foundation of everything else. Its axioms are justified by informal but widely accepted intuitions that sets exist, the union of two sets is a set, and so forth.