First-order logics, as well as propositional modal-like logics, that are interpreted in metric (and other distance) spaces are introduced in this paper. It investigates both their expressive power and their computational properties, including decidability and complexity of reasoning. Such logics can be used to represent and reason about spatial knowledge, which has many potential applications (for example, in geographic information systems). Another interesting application of these logics comes from the fact that distance need not be interpreted as spatial distance; it can also be viewed as a measure of the similarity of objects. Using this interpretation, these logics have potential applications in bioinformatics and in case-based reasoning.

The main technical contributions of this paper are threefold. First, a natural logic of metric spaces, MS, that is similar in flavor to modal or description logics, is introduced. Typical (modal) operators of this logic can express things like “somewhere in the circle of radius x, there is an object of a certain type,” which can, for example, describe houses that are within a certain distance of the next shop.

Second, it is proved that MS has the same expressive power as the two-variable fragment of the natural first-order logic of metric spaces. Third, it is shown that MS (and, therefore, the corresponding two-variable fragment of first-order logic) is undecidable over any class of metric spaces that contains the Euclidean plane. This is in contrast to the fact that the usual two-variable fragment of first-order logic is decidable. However, it is also shown that a number of expressive fragments of MS are indeed decidable, and enjoy the finite model property. Some complexity results (in the vicinity of nondeterministic exponential time) are also established.

To sum up, this paper provides the first in-depth analysis of the computational properties of logics intended for reasoning about distances and similarities. As such, it should be of interest to logicians, as well as to researchers in knowledge representation, case-based reasoning, geographic information systems, bioinformatics, and other areas where reasoning about distances and similarities is relevant.