Module: Sentential logic
Quote of the page
Good reasons must, of force, give place to better.
- William Shakespeare
Popular pages
In this tutorial we study how to make use of full truth-table method to check the validity of a sequent in SL. Consider this valid sequent:
P, (P→Q) ⊧ Q
To prove that it is valid, we draw a table where the top row contains all the different sentence letters in the argument, followed by the premises, and then the conclusion. Then, using the same method as in drawing complex truth-tables, we list all the possible assignments of truth-values to the sentence letters on the left. In our particular example, since there are only two sentence letters, there should be 4 assignments :
| P | Q | P | ( | P | → | Q | ) | Q | ||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| T | T | |||||||||||||
| T | F | |||||||||||||
| F | T | |||||||||||||
| F | F |
The next step is to draw the truth-table for all the premises and also the conclusion:
In the completed truth-table, the first two cells in each row give us the assignment of truth-values, and the next three cells tell us the truth-values of the premises and the conclusion under each of the assignment. If an argument is valid, then every assignment where the premises are all true is also an assignment where the conclusion is true. It so happens that there is only one assignment (the first row) where both premises are true. We can see from the last cell of the row that the conclusion is also true under such an assignment. So this argument has been shown to be valid.
In general, to determine validity, go through every row of the truth-table to find a row where ALL the premises are true AND the conclusion is false. Can you find such a row? If not, the argument is valid. If there is one or more rows, then the argument is not valid.
Note that in the table above the conclusion is false in the second and the forth row. Why don't they show that the argument is invalid?
Remember that “(P→Q), ~P, therefore ~Q” is invalid. Look at the truth-table, and determine which line is supposed to show that?
To show that a sequent is invalid, we find one or more assignment where all the premises are true and the conclusion is false. Such an assignment is known as an invalidating assignment (a counterexample) for the sequent.
Let's look at a slightly more complex sequent and draw the truth-table:
(~P∨Q), ~(Q→P) ⊧ (Q↔~P)
Again we draw a truth-table for the premises and the conclusion :
To help us calculate the truth-values of the WFFs under each assignment, we use the full truth-table method to write down the truth-values of the sentence letters first, and then work out the truth-values of the whole WFFs step by step. The truth-values of the complete WFFs under each assignment is written beneath the main operator of the WFFs. As you can see, the critical one to check is the third assignment. Since there is no assignment where the premises are true and the conclusion is false, the sequent is valid.
Examine this table and answer the questions:
True or false?
Use the full truth-table method to determine the validity of these sequents:
See this page for the answers.
Confirm for yourself that the WFFs in each pair of WFFs below are logically equivalent to each other :
One thing you might notice about the full truth-table method is that it can help us determine the validity of any sequent in SL. A program can be written that, given any finite sequent in SL as input, after a finite number of processing steps, produces an output "Yes" if the sequent is valid, or an output "No" if it is not. Of course, the computer would need to have a lot of memory if the sequent is a long one, but in principle it can be done. This is roughly what logicians mean when they say that validity in SL is decidable. Intuitively, it is a matter of whether there is an algorithm or computer program that can come up with a proof of either the validity or the invalidity of a sequent.
What is interesting and perhaps surprising is that decidability no longer obtains when we are dealing with some more powerful systems of logic. One of the most important discoveries in modern logic is that mathematics is undecidable. In particular, Gödel's first incompleteness theorem says that any consistent systems of mathematics would have to include statements that can neither be proved or disproved. In other words, it is impossible for there to be a computer program that can tell whether these statements are true.