Proving invalidity

We have studied a method for proving the validity of a propositional argument A: we take the premises and the negation of the conclusion of A and try to obtain a contradiction.  If we can, then A is valid.  But what if we cannot derive a contradiction?  Then, two alternatives are possible:

  1. no contradiction can be derived from the premises and the denial of the conclusion
  2. a contradiction can be derived from the premises and the denial of the conclusion, but we are too dumb to derive it.
If we could rule out (2), then we would know that A is invalid, but experience teaches us never to underestimate our lack of ingenuity.  So, to make sure that an argument A is invalid, we must show that it is possible for its conclusion to be false and its premises true, that is, we must assign truth values to the constituent letters so that the premises will all be true and the conclusion false.  For example, consider
-A
A->B
-------
-B

Now, suppose -B is false; then B is true. Suppose also that A is false; then, -A is true and A->B is true.  Hence, the assignments
B : true
A: false
make the premises true and the conclusion false.  Hence, the argument is invalid.

Here's another example.
A->(BvC)
(C&D)->E
-E
-------
-A

As before, the idea here is to try and find truth assignments which make the conclusion false and the premises true.  Suppose that the conclusion is false; then A is true;  so, for the first premise to be true (BvC) must be true.  For the third premise to be true, E must be false; so, the second premise can be true only if (C&D) is false as well.  So, any assignment making A true, (BvC) true, (C&D) false, and E false will do.  Here is one such assignment:
A: true
B: true
C: false
E: false.

Here's another:
A: true
B: false
C: true
D: false
E: false.
 

Exercises
Prove that the following arguments are invalid
I.
A->B
C->D
----
A->C

II.
R->S
T-> -S
---------
RvT

III
A->(BvC)
B->(D&E)
D->(E->F)
-(A&F)
--------
A<->C

IV
FvG
F->H
G->J
--------
H&J

Answers