Lesson 5

Zero-order logic (also known as propositional logic) studies statements composed of variables and logical connectives. As we mentioned, any tautology can be derived from eleven axiomatic schemes using the modus ponens rule.

First-order logic (predicate calculus) extends zero-order logic by adding quantifiers over variables. Gödel's completeness theorem states that a first-order logic formula is universally valid if and only if it is derivable. (Above we did not define either universal validity or derivability.)

It is easy to see that the language of first-order logic is richer than the language of zero-order logic, but still not all predicates can be expressed (for example, it will not be possible to express the reachability predicate in a graph: \(P_{G}(x,y)=1\) if and only if there is a path from \(x\) to \(y\) in \(G\)).

Second-order logic extends first-order logic by allowing quantifiers not only over variables but also over predicates and functional symbols.