©1992-1997 The MIT Press. Reproduction by any means strictly prohibited.

2.2 Truth Tables for Sequents

validity with TTs To determine a sequent's validity or invalidity, we construct a single TT for the whole sequent. If there is a line in the TT where all the premises are true and the con-clusion is false, then the sequent is invalid. If there is no such line, it is valid.
valid example
P Q
~P,  Q -> (P & Q)  |- ~Q
T T
 F     T     T        F
T F
 F     T     F        T
F T
 T     F     F        F
F F
 T     T     F        T
Table 2.4 This sequent is valid since there is no line on which ~P and Q -> (P & Q) are both true but ~Q is false.
invalid example
P Q R
~P -> Q,  (R & P) -> Q)  |- Q
T T T
 F T         T    F
T T F
 F T         F    T
T F T
 F T         T    F
T F F
 F T         F    T
F T T
 T T         F    T
F T F
 T T         F    T
F F T
 T F         F    T
F F F
 T F         F    T
Table 2.5 This sequent is invalid since there is at least one line where ~P -> Q and (R & P) -> Q are both true but the con-clusion is false--the fourth line.
invalidating assignment Definition. An INVALIDATING ASSIGNMENT for a sequent is an assignment of truth and falsity to its sentence letters that makes the premises true and the conclusion false.
Comment. From the TT for an invalid sequent, you can read off an invalidating assignment. Find a row of the TT where the premises are all true and the conclusion is false. The invalidating assignment is given at the left side of that row.
Example.
An invalidating assignment for the sequent in Table 2.5 assigns truth to P and falsity to Q and R.
number of lines Comment. When the sequent in question involves only two sentence letters, the TT has exactly four lines; three sentence letters requires eight lines. In general, when n sentence letters are present, the number of lines in the TT is 2n.
incompatible premises Comment. Consider this special case: If you construct a TT for the sequent P -> Q, Q -> R, P & ~R | - S you find that there is no line on which all the premises are true. Consequently, there is no line on which the conclusion is false while all the premises are true. Thus the sequent is valid.
Exercise 2.2 Use TTs to determine whether each of the following sequents is valid. For each invalid one, find an invalidating assignment. For each valid one, give a proof.
i* P & ~Q |- ~(P <-> Q)
ii* P & (Q v R) |- Q & (P v R)
iii* P & Q -> R |- P -> R
iv* P v Q -> R |- P -> R
v* P -> Q v R |- P -> R
vi* (P -> ~P) -> (~P -> P) |- P
vii* Q -> R |- (P -> Q) & (Q -> R)
viii* P v Q, P -> R, ~S -> ~Q |- ~P
ix* P -> Q, P -> R, ~(~R -> Q) |- P
x* P <-> ~Q, Q <-> ~R, R <-> ~S |- P <-> S
xi* P v Q |- (~P -> R) v (~Q -> R)
xii* P <-> (R -> P v ~Q), ~(R -> P v Q) |- ~Q
xiii* ~(R & ~P -> Q v R) |- ~(Q <-> R)
xiv* P -> (Q & R -> S), P, ~S |- ~(Q & R)
xv* ~R -> ~Q, (~P & R) -> ~Q |- ~(P <-> ~R & Q)
xvi* S -> (T <-> P), Q -> (~S <-> ~T), ~(P & R <-> T -> S)
|- R & ~Q
xvii* Q -> (P -> R & ~Q), ~Q -> ~(T v V), U & S <-> P
|- (S -> ~U) v ~T
xviii* Q v R -> U & T, ~(P <-> Q), ~(S v W) -> P
|- Q v V -> (S & U) v (T & W)
[Prev] [Next]