Logic for Computer Science and Artificial Intelligence

Chapter 9

Problem Specification in Logical Languages

9.1. Equality

Equality is an extremely important¹ predicate (relation), in particular, in mathematics, that has a meaning in every universe of discourse, which is not the case for other predicates (for example, if P(x, y) has the intended meaning “x loves y”, it would have no meaning if the universe of discourse was, say, ).

It seems natural to want to treat it using logics that we have already studied.

Imagine we have to prove the validity (or non-validity) of the equivalence:

If propositional logic (PL) is used, using the names mentioned, we get , which is obviously a non-valid formula, but our experience with = tells us that formula (*) is valid, and we want to classify it as such.

FOL would also fail (without any additional axioms) to capture the characteristics of equality.

Equality has particular properties that we must make explicit.

There are formulas such as:

that are valid when R is replaced by x = y or by any other predicate Q(x, y).

But the validity of the formula

depends on the semantics of =.

9.1.1. When is it used? ...