Slide 14.1: Logic

Slide 12.15: Recursive functions (cont.)
Slide 14.2: First-order predicate calculus
Home

Logic

Logic programming is a programming style based on mathematical logic. The logic for logic programming is the first-order predicate calculus or logic:

First-order predicate calculus is a way of formally expressing logical statements, that is, statements that are either true or false.

For example, the following English statements are logical statements:

0 is a natural number.
2 is a natural number.
For all x, if x is a natural number, then so is the successor of x.
-1 is a natural number.

A translation into predicate calculus is as follows:

     natural( 0 ).
     natural( 2 ).
     For all x, natural(x) → natural( successor( x ) ).
     natural( -1 ).

Among these logical statements, the first and third statement can be viewed as axioms for the natural numbers: statements that are assumed to be true and from which all true statements about natural numbers can be proved. Indeed, the second statement can be proved from these axioms, since

     2 = successor( successor( 0 ) ) and
       natural( 0 )
     → natural( successor( 0 ) )
     → natural( successor( successor( 0 ) ) ).

The fourth statement, on the other hand, cannot be proved from the axioms and so can be assumed to be false.