Introduction

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 the propositions under the given valuations.

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

What are valuations?

When we draw out a truth table for a given proposition, each row corresponds to each possibility of trith 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 shows a particular valuation.

A valuation is a function that maps an atomic proposition to the set ::\{\bold T, \bold F\}:: (or equivalently to the set ::\{0,1\}::).

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

In some resources, a valuation is also known as a model.

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 valuations:

::\begin{aligned} V_{1}(p) = \bold T; \space V_{1}(q) = \bold T; \\ V_{2}(p) = \bold T; \space V_{2}(q) = \bold F; \\ V_{3}(p) = \bold F; \space V_{3}(q) = \bold T; \\ V_{4}(p) = \bold F; \space V_{4}(q) = \bold F; \end{aligned}::

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 function.

So now that we have all the valuations for a compound proposition in hand, 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...

Interpretation function

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

An interpretation function takes a propositional formula and a valuation, and returns the truth value of the formula under the given valuation.

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:

::\begin{aligned} \phi^V &= V(p) \to (V(p) \vee V(q)) \\ \phi^V &= \bold T \to (\bold T \vee \bold F) \\ \phi^V &= \bold T \to \bold T \\ \phi^V &= \bold T \\ \end{aligned}::

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.

Satisfiability

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...

A proposition that has at least one true interpretation is called satisfiable.

On the same lines:

A proposition that is false in all interpretations is called unsatisfiable.

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.

As we shall see in a later chapter on propositional equivalences, the proposition ::p \wedge \neg p:: expresses one of the three laws of thought, also known as the law of contradiction.

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?

Check out more on Wikipedia on the propositional satisfiability problem.