LOGIC MAIN PAGE

LOGICAL OPERATORS

Sample sentences
AND operator
IF/THEN operator
NOT operator
OR operator
XOR operator

RULES OF LOGIC

Chain Rule
Contrapositive
DeMorgan's Law
Disjunctive Inference
Disjunctive Infer. (XOR)
Double Negation
Modus Ponens
Modus Tollens
Mutual Exclusion
Simplification

VALIDITY PROOFS

2-step
3-step
4-step
5-step or more

Validity Proof Problems (5 steps or more)

The problems below can be solved in five or more steps.

Problem 1

1. ~X -> ~Y
2. Y ^ Z
----------
* X ^ Z

Looking at premise 2, we realize that we can apply Simplification. Here is what happens:

3. Y          2 Simplification
4. Z          2 Simplification

The conclusion has Z and X, and we have Z already. How about getting X out of premise 1? If we look carefully at the consequent of the condition in premise 1, and then at step 3, we realize that we can use Modus Tollens here.

5. ~(~X)      1,3 Modus Tollens

This looks very much like Double Negation. We apply it here.

6. X          5 Double Negation

We finally got X, but the conclusion requires X and Z together. We can join them using Conjunctive Addition.

7. X ^ Z      6,4 Conjunctive Addition

We are done.

1. ~X -> ~Y
2. Y ^ Z
*  X ^ Z
-------
3. Y          2 Simplification
4. Z          2 Simplification
5. ~(~X)      1,3 Modus Tollens
6. X          5 Double Negation
7. X ^ Z      6,4 Conjunctive Addition

Problem 2

1. (W ^ N) -> M
2. ~(~N v M)
----------
* ~W

Premise 2 looks rather complicated, so we can apply DeMorgan's Law here to simplify it.

3. N ^ ~M     2 DeMorgan's Law

Now we can use Simplification to separate out both conjuncts from the result.

4. N          3 Simplification
5. ~M         3 Simplification

In step 5, we have the opposite of the consequent in premise 1. We can apply Modus Tollens to it.

6. ~(W ^ N)   1,5 Modus Tollens

Again, this is a good candidate for DeMorgan's Law.

7. ~W v ~N    6 DeMorgan's Law

In step 4, we proved that N is true, so we can use Disjunctive Inference as our last step:

8. ~W         7,4 Disjunctive Inference

We are done.

1. (W ^ N) -> M
2. ~(~N v M)
*  ~W
----------
3. N ^ ~M     2 DeMorgan's Law
4. N          3 Simplification
5. ~M         3 Simplification
6. ~(W ^ N)   1,5 Modus Tollens
7. ~W v ~N    6 DeMorgan's Law
8. ~W         7,4 Disjunctive Inference