6.2 Computing Truth Functions
BOOL only has three connectives, and they are all truth functional. That means the truth value of any sentence, no matter how complex, can be computed from the truth values of the atomic sentences.
Take this sentence:
The first step is to construct the table and reference columns:
The truth function for a complex sentence is the values it has for its main connective. Luckily, you've already mastered the skill of identifying the main connective.
That means we need to compute the value of the v, which we do from the values of its inputs.
The inputs for the disjunction are ~P and Q&P. But we don't know the values of those yet. We only know the values of P and Q.
That is why you always compute truth functions from the inside out.
So we first compute the values of ~P and of Q&P.
Next, we use those inputs to compute the value for the disjunction.
Since the disjunction is the main connective, you are done. That set of values is the truth function for the sentence.
It tells you exactly when that sentence is true or false. For example, as row 2 says, if P is true and Q is false, then the complex sentence is false.
Here's what your completed table should look like, with the final truth function highlighted.
Now you should see if you can do one completely on your own. Construct a truth table for the sentence ~(Pv~Q).
To do so you should take out paper and pencil and actually build the table. When you have to answer a question like this on the exam, you won't have us walking you through it with images. You will have to produce it all yourself, so you need to practice the actual skill you are learning.
Don't read below until you've finished! If you don't practice, you won't learn the material.
So that you can check your work, here's what your table should have looked like.
So far we've only built tables for sentences with two atomic sentences, but a complex sentence could have any number of atomics.
Each time you add another atomic sentence, you double the number of rows.
Let's say we want to compute the function for (P&Q)&R. The reference columns look like this:
Since R is alphabetically last, it goes furthest to the right and alternates Ts and Fs.
Each subsequent letter doubles the number of Ts and Fs it alternates.
When you double the number of rows, you're just multiplying by 2. So the number of rows for any table is just 2n, where n is the number of atomic sentences.
Now let's compute the truth function for (P&Q)&R.
Extra practice: below are a few more practice problems.