Logic for Computer Science and Artificial Intelligence

Chapter 12

Solutions to the Exercises

EXERCISE 3.1.– We can represent an interpretation as a subset of Π, with the elements of this subset being the propositional symbols that are evaluated to T in the interpretation.

There are 2^ℵo subsets of Π; hence, there is an uncountably infinite number of interpretations for PL.

A more detailed proof.

Every interpretation I can be represented by the graph of the function defining it:

There are infinitely many interpretations, take for example (l ):

Now if we assume that the set of all interpretations in PL is denumerable, then they can be enumerated (i ):

Consider the interpretation defined as follows:

This interpretation is different from every ...