2.4 Indirect TTs

indirect TT	Comment. A TT is a systematic search for invalidating assignments. A shorter way of doing this is the indirect truth table (ITT).
	In an ITT, one attempts to build invalidating assignments. When the sequent is valid, it is impossible to build an invalidating assignment (as in the first example below).
	In cases of invalid arguments, an invalidating assignment can be discovered (as in the second example below). Sometimes one must examine more than one assignment (as in the third example below).
easy valid case	Example. Consider the sequent P -> Q, ~R -> ~Q \|- ~R -> ~P
	There is only way for the conclusion (~R -> ~P) to be false: ~R must be true and ~P false. That is, R must be false and P must be true, as shown below. P -> Q, ~R -> ~Q \|- ~R -> ~P T TF TF F FT
	Having established these truth assignments, we now see if there is any way of making the premises all true that is compatible with this assignment. In other words, we need a value of Q to complete the following: P -> Q, ~R -> ~Q \|- ~R -> ~P T T TF T TF F FT
	The assignment indicated requires Q to be true, in order for the first premise to be true, but also requires ~Q to be true (hence Q to be false), in order for the second premise to be true. This is the only way to make both premises true and the conclusion false, and it is impossible to achieve.
	Thus, there are no invalidating assignments, and the argument is valid.
easy invalid case	Example. The sequent below has a conditional conclusion. Thus, if the conclusion is to be false, its antecedent must be true and its consequent false. P & ~Q, Q -> R \|- P -> R T T TF F T F T F F
	The invalidating assignment assigns T to P and F to Q and R.
harder case	Example. In the sequent below there are three ways to make the conclusion false. Here is one of them: ~P -> Q, ~P -> ~Q \|- P & Q F F T
	On this assignment, the second premise is false. Thus, we have failed to find an invalidating assign- ment. So we try a different way of making P&Q false: ~P -> Q, ~P -> ~Q \|- P & Q FT FT T F F
	Here, both premises are true, since they both have false antecedents. Thus, an invalidating assignment assigns T to P and F to Q.
Exercise 2.4	(a) Use ITTs to determine whether the sequents given in exercise 2.2 are valid or invalid.
	(b) Use ITTs to determine whether the following sequents are valid. For each invalid one, give an invalidating assignment. For each valid one, construct a proof.
i*	P -> Q, Q \|- P
ii*	P v Q, P \|- Q
iii*	P -> Q, ~Q -> R \|- P -> R
iv*	P v ~Q, ~Q & R \|- P & R
v*	P <-> Q v R, ~Q \|- ~P
vi*	P -> Q, (R -> S) -> ~P \|- Q v R
vii*	P -> Q v R, Q -> S & T, ~S \|- ~P
viii*	P & ~Q -> R, P <-> ~R \|- (Q & R) v P
ix*	P -> Q & ~R, ~P v Q <-> S \|- S -> ~P v T
x*	~(P <-> Q), P -> R, Q -> S \|- ~R v S
xi*	S -> Q, ~S -> Q v T, T -> P \|- P -> Q v R
xii*	~Q -> S, S -> Q v ~T, ~T -> P \|- Q -> P v R
xiii*	P -> (~Q -> ~R & ~S), ~(R <-> S), ~Q \|- ~P
xiv*	P v Q, ~(R -> P) \|- Q <-> (~T -> ~R v S)
xv*	P & S -> R, R v T, T -> Q & P, ~Q v U \|- P -> S v U
xvi*	~(P <-> Q), P -> R, Q -> S \|- ~R v S
xvii*	~(P -> ~Q & R), ~R <-> ~P \|- P & Q
xviii*	(P -> Q) & (~Q -> P & R) -> (S v T -> ~Q) \|- Q -> ~(~S -> T)
xix*	\|- (P v ~Q -> ~P & ~Q) <-> ~P
xx*	Q <-> ~Q \|- P <-> ~P

[Prev] [Next]