10 - Logic

Summary

We have described a universe that is richly populated with individuals, sets, tuples, relations, functions, and sequences. We can extend our univetse indefinitely by using operators to build up ever more complex structures. But we need something more.

We need a way to classify the profusion of structures we can create. We need to divide the wheat from the chaff, the sheep from the goats, the bogus from the bona fide. We will make an essentially binary distinction between the answer we are looking for — the objects we wish to model — and everything else. Our tool for distinguishing the two is called logic. The concept of a purely binary classification may seem crude, but with logic we can express distinctions that are exceedingly fine.

Basic predicates

The textual unit of logic is the predicate. There are just a few kinds of basic predicates. All the others are built up from these.

The simplest predicates are true and false. We say true and false are the two logical constants or truth values. In fact, every predicate has one value or the other, true or false. There are many rules for simplifying predicates or otherwise inferring whether any predicate, no matter how complicated, is true or false.

The next basic predicate is equals, =. The predicate e₁ = e₂ is true when the two expressions e₁ and e₂ have the same value, and is false otherwise.