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 (4 steps)

The problems below can be solved in four steps.

Problem 1

1. ~A -> D
2. C -> ~B
3. A -> B
----------
* ~D -> ~C

At first nothing seems to work, but if we look carefully at premise 1 and apply Contrapositive to it, we'll get something resembling the answer. Let's try it.

4. ~D -> A    1 Contrapositive

Immediately after this we can connect premises 4 and 3 using the Chain Rule.

5. ~D -> B    4,3 Chain Rule

We're getting closer, but we're not there yet. We still need to somehow connect ~D with ~C. We've just proved ~D -> B, and premise 2 connects C and B. Let's explore that. If we apply Contrapositive here, we then might connect premise 5 with the result.

6. B -> ~C    2 Contrapositive

It's working! Now all we need is to use the Chain Rule on premises 5 and 6.

7. ~D -> ~C   5,6 Chain Rule

We've solved the problem.

1. ~A -> D
2. C -> ~B
3. A -> B
* ~D -> ~C
----------
4. ~D -> A    1 Contrapositive
5. ~D -> B    4,3 Chain Rule
6. B -> ~C    2 Contrapositive
7. ~D -> ~C   5,6 Chain Rule

Problem 2

1. W ^ X
2. ~X v Y
---------
* Y ^ W

The first thing we can do immediately is apply Simplification to premise 1.

3. W          1 Simplification
4. X          1 Simplification

Looking at premise 2, we realize that its first part is false since we have just proven X. Therefore, by Disjunctive Inference, we conclude that Y is true.

5. Y          2,4 Disjunctive Inference

We know that W is true (step 3), and we have just found out that Y is true as well. We can connect them by Conjunctive Addition.

6. Y ^ W      5,3 Conjunctive Addition

And that's our conclusion.

1. W ^ X
2. ~X v Y
*  Y ^ W
---------
3. W          1 Simplification
4. X          1 Simplification
5. Y          2,4 Disjunctive Inference
6. Y ^ W      5,3 Conjunctive Addition