2.5 English Counterexamples

counterexample

Definition. An English COUNTEREXAMPLE for an invalid argument or sequent is an argument that has the same logical form as the original, but whose premises are all obviously true and whose conclusion is obviously false.

Example.
A counterexample for P -> Q, Q |- P is

	If Los Angeles is in Canada, then Los Angeles is in North America
	Los Angeles is in North America.
	Therefore, Los Angeles is in Canada.

Comment. The relationships of Los Angeles, Canada, and North America to one another are public knowledge. The premises are both obviously true, and the conclusion is obviously false.

Comment. In con-structing a counterexample, it is not generally useful to construct the premises and the conclusion using either unspecific pronouns or personal information. For example, given the invalid sequent above, one might present

	If it is raining then there are clouds in the sky.
	There are clouds in the sky.
	Therefore, it is raining.

Although one can see in a hypothetical situation that the premises might be true at the same time as the conclusion is false, the trouble with this argument as a counterexample is that the second premise is not obviously true (you may not be in a position to see whether it is raining) and likewise the conclusion is not obviously false.

Similarly, the following is not useful:

	If my cousin is intelligent, she will pass logic.
	My cousin will pass logic.
	Therefore, my cousin is intelligent.

Since it is not general knowledge who your cousin is and whether or not she is intelligent or will pass logic, this does not provide a clear counterexample to the given sequent.

Exercise 2.5

Construct counterexamples for the invalid sequents in chapter 2.

Exercise 2.6

Give proofs, invalidating assignments, or counter- examples to establish the validity or the invalidity of the following sequents:

P -> Q, ~Q v R, R |- P

~P v Q, ~Q v R, ~R |- ~P

iii

P <-> Q, Q <-> ~R |- ~P <-> ~R

(Q -> P) -> R, ~Q v S, ~S |- ~R -> T

P & (Q -> R), Q v ~P, R v S -> T |- T v U

P <-> ~Q, R v ~Q, R <-> S |- S v P

vii

P <-> Q, Q <-> ~R, R -> P |- ~P <-> ~R

viii

P <-> Q |- (R <-> P) <-> (P <-> Q)

~R <-> ~Q, P v ~Q, P <-> S |- S v ~R

R <-> ~Q, P v ~Q, P <-> S |- S & R

(P -> Q) v (R -> S) |- (P -> S) v (R -> Q)

xii

(P -> Q) & (R -> S) |- (P -> S) & (R -> Q)

xiii

P & Q, Q -> (R -> P), R -> (~S -> ~T v ~W),
~S & T |- W

xiv

P & Q, Q -> (P -> R), R -> (~S -> ~T v ~W),
~S & T |- ~W

P v Q -> R v S, ~(T v R) -> S, (T -> P) & (R -> Q),
~S |- R

xvi

~(P v ~Q), ~P -> R v S, ~S v ~Q,
R v ~T -> W & (Y -> ~Q) |- ~(W -> Y)

xvii

P v (Q v R), S & ~T, ~(~S v T) -> ~P,
(R -> W) & ~W |- Q

xviii

P v (Q v R), S & ~T, (R -> W) & ~W |- Q

xix

(P <-> Q) <-> (~P <-> ~R) |- P -> (Q <-> R)

P <-> Q, ~(~R & P), R v S -> ~(T & Q)
|- T ->~(P v Q)

xxi

P <-> Q, R v ~P, T & Q -> ~R |- ~S & T -> ~(P v Q)

xxii

P & Q -> (R <-> S), ~P -> ~T, ~(~R v S) |- Q -> ~T

xxiii

P & Q -> R, P & ~R <-> Q v ~S,
T & (~Q & ~R -> P), (T -> S) v (T -> R) |- S & R

xxiv

R v (P -> S), T & ~W, (~T v W) -> ~R,
(S -> Q) & ~Q |- ~P

xxv

R v (P v S), T & ~W, ~(~T v W) -> ~R,
(S -> Q) & ~Q |- P

[Prev] [Next]