## Subsection4.4.2Meaning

Recall the examples from the previous slide:

1. Bear(Smokey)

2. x (Bear(x) → Animal(x))

3. x (Animal(x) → Bear(x))

4. x (Animal(x) → ∃y (MotherOf(y, x)))

5. x ((Animal(x) ∧ ¬Dead(x)) → Alive(x))

As these examples show, determining whether a sentence is true requires appeal to the meanings of the constants, functions, and predicates that it contains. (This must be so because [2] and [3] have exactly the same structure. It’s just their words that are different. Yet one is true and one is false.) An interpretation for a sentence w assigns meanings to the symbols of w. How do we specify an interpretation? How do we know that [2] is true and [3] isn’t? So far, we’ve been appealing to what we, as people, think the words that we’ve chosen for our objects and predicates “mean” in English. But we need more than that.

Our goal, when we use any logical system, is to get at truth. So what we do is to choose premises that assert things that are true. We write those premises in terms that we pick. We can pick any terms we like as long as we use them consistently to describe the situation that we want to reason with. The logical system doesn’t care what names we use. It applies its inference rules and generates new statements that it asserts to be true. But then, and here’s the key: When we read off these new statements, we do so using the same terminology that we started with. As long as we do that, we’ll get true statements that make sense to us.

Let’s return to the question of what an interpretation has to do. In Boolean logic, all it has to do is to assign a meaning to each variable. There are only two possible meanings, T and F. An interpretation of a formula then is just a single row of the formula’s truth table. That row assigns a meaning to each of the variables and then to each of the subexpressions, ending with the whole formula. Every time we wrote a truth table, what we were really doing was writing out all possible interpretations of the formula we were working with. Then we could say that:

• A Boolean formula is valid (or is a tautology) if it is true in all interpretations. In other words all rows of its truth table end in T.

• A Boolean formula is satisfiable if there exists some interpretation in which it is true. In other words, at least one row of its truth table ends in T.

• A Boolean formula is unsatisfiable (alternatively, it is a contradiction) if there exists no interpretation that makes it true. In other words, every row of its truth table ends in F.