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 rev n.gif):


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


Consider the interpretation image defined as follows:

This interpretation is different from every ...

Get Logic for Computer Science and Artificial Intelligence now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.