[SL07] Validity

§1. The full truth-table method

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 :


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?

§2. More examples

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:

  1. Which sequent is being tested for validity in this table?
  2. Is the sequent valid according to this table?

True or false?

  1. For any three formula φ, ψ, and γ, if φ ψ, and ψ γ, then φ γ.
  2. For any two formula φ and ψ, if φ ψ, then ψ φ?
  3. For any two formula φ and ψ, if φ does not entail ψ, then ψ entails φ

Use the full truth-table method to determine the validity of these sequents:

  • ((P→Q)&R), (~Q∨R) (P↔(Q↔R))
  • (((P&Q)&~S) & (~Q↔R)), ~(~R→S) ((P→Q)→(S→R))

See this page for the answers.

Confirm for yourself that the WFFs in each pair of WFFs below are logically equivalent to each other :

  • (P→Q), (~Q→~P)
  • (P↔Q), (~P↔~Q)
  • ~(PvQ), (~P&~Q)
  • ~(P&Q), (~Pv~Q)