Valuations and Interpretations

In the previous chapter, we got familiar with truth tables and learnt, with an extensive array of examples, how to construct truth tables to evaluate the truth value of a given proposition in every possible case.

Now in this chapter, we aim to formalise certain concepts, pretty much related to truth tables. In particular, we'll see what are valuations, and how are they, along with propositions, used to find the interpretation of those propositions.

Sounds confusing? Well it ain't! Let's dive right in..

When we draw out a truth table for a given proposition, each row corresponds to each possibility of truth values for the individual propositions.

For instance, when we're given a compound proposition with two variables ::p:: and ::q::, we have four possibilities, as shown in the tree diagram below:

Each of the four rows in the truth table of such a compound proposition represents each leaf in the tree diagram above.

Instead of calling them 'possiblities' over and over again, we'll now define them rigorously.

Each row in a truth table correspond to a particular valuation.

It can be thought of as an assignment of truth values to individual propositions.

A valuation could be represented as ::V(x)::. It takes a given proposition ::x:: and yields a truth value.

Simple as that!

For instance, given the compound proposition ::p \vee q::, shown below are all the four valuation functions:

The first function ::V_1:: maps the variable ::p:: to ::\bold T::, and ::q:: to ::\bold T::. The second function ::V_2:: maps the variable ::p:: to ::\bold T::, and ::q:: to ::\bold F::. And so on and so forth.

Since different valuations mean different functions, we ought to represent them differently as well. Here we've just used different subscripts to denote different functions. However, you could use whatever symbol you want for the different functions.

So now that we have all the valuations for a compound proposition in hand, with each assuming the truth values for the constituent propositions, we could use the semantics of the involved operators to compute the truth value of the compound proposition.

This is where the interpretation function comes in...

Just like valuations, the concept of interpretation functions is also extremely easy to understand. They both are just some fancy names representing rudimentary ideas.

For a valuation ::V::, propositional formula ::\phi::, the interpretation function is denoted as ::\pmb{\phi^V}::.

Let's consider a very quick example.

Let's say we have the propositional formula ::\phi = p \to (p \vee q)::, and the valuation function ::V:: such that ::V(p) = \bold T:: and ::V(q) = \bold F::. Then the interpretation function would be given as follows:

Hence, the formula ::\phi:: under ::V:: turns out to be true.

This is essentially all what needs to be understood regarding the interpretation function.

But the discussion ain't over yet. We still need to grasp a couple of ideas that can be easily defined using the concepts of valuations and interpretations.

In mathematical logic, satisfiability is a useful concept. It can help determine whether a given propositional formula can ever be true or not.

So what exactly is satisfiability. Well, it's just got to do with satisfiable propositions. And what are satisfiable propositions? Let's see...

On the same lines:

As you can see, this is an extremely basic idea. Time to apply it.

Is the proposition ::p \vee p:: satisfiable or not?

Well, it turns out that yes — it surely is satisfiable, and that is when ::p:: is ::\bold T::.

Is the proposition ::p \to q:: satisfiable? Once again, yes! In fact, there are 3 cases in which this proposition is true.

Is the proposition ::p \wedge \neg p:: satisfiable? Well, no! This is because the proposition is contradictory i.e is false in every possible interpretation.

This means that an unsatisfiable proposition is the same as saying that it's contradictory.

How can we figure out whether a proposition is satisfiable or not?

Problems of this sort where we have to show whether a proposition is satisfiable or not are collectively known as satisfiability problems, or simply SAT problems, or as Boolean satisfiability problems, or B-SAT problems.

The most straightforward way is to draw a truth table for the given proposition and see when we get a true value. As soon as it's seen, we could halt completing the truth table, by claiming that the proposition is indeed satisfiable.

But if some proposition is unsatisfiable, then we'd end up completing the truth table, without getting a truth value.

For propositions with few variables (somewhere around 20), we could solve such problems using a computer. Just feed it with the proposition and it'll check all possible cases itself. However, based on the fact that the number of possibilities of truth values grows exponentially (in the base of 2), even programatically solving such problems becomes infeasible when we have a huge amount of propositional variables to consider.

This infeasibility is of particular importance in CS. It is prat of a set of problems in CS that have no known algorithm running in polynomial time. It's believed (in fact, proven) that if one of the problems in this collection could be solved, it would be a solution to all the collection of problems.

Sounds interesting, and weird?

Much related to the concept of satisfiability is that of validity. Let's define it.

Similarly:

As with all the concepts above, validity is also very easy to understand. Do you agree?

Let's quickly see two propositions — one that is valid, and one that is invalid.

Given the proposition ::p \vee \neg p::, determine whether it is valid.

Akin to satisfiability problems, validity problems can also be solved using truth tables (as long as the involved proposition has a manageable number of constituent propositions).

Since the given proposition is ::\bold T:: in all interpretations, it is valid.

Over to the next example...

Given the proposition ::p \vee q::, determine whether it is valid.

Since this time the proposition isn't true in all interpretations i.e. it's ::\bold F:: in the last interpretation, it is invalid.

Now there's one important relationship between satisfiability and validity. Let's see whether you can determine it.