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

The problems below can all be solved in two steps.

Problem 1

1. G ^ K
2. H
--------
* G ^ H

Using the premises in 1 and 2, prove that the conclusion G ^ H is true.

We see that G is part of premise 1, and H is part of premise 2, and we want to bring them together in order to prove that G ^ H is true. We can separate G out by using Simplification.

3. G          1 Simplification

We have written our new step 3 as a result of applying Simplification to premise 1.

Now that we have G separated, and knowing that H is given, we can join them by using Conjunctive Addition.

4. G ^ H      3,2 Conjunctive Addition

This line reads as follows: 4 is the new step number; G ^ H is the result of applying Conjunctive Addition to premises 3 and 2.

We have gotten to the conclusion.

1. G ^ K
2. H
*  G ^ H
--------
3. G          1 Simplification
4. G ^ H      3,2 Conjunctive Addition

Problem 2

1. R -> S
2. U
3. U -> R
---------
* S

If we look at premises 2 and 3, we can see that it is possible to apply Modus Ponens to them, in order to isolate R. We know that we are going to need R in order to obtain S from premise 1, which is our conclusion.

4. R          3,2 Modus Ponens

Now that we have R, we can apply Modus Ponens to premise 1. Here is what happens:

5. S          1,4 Modus Ponens

We have gotten to our conclusion, S. Let's review our steps.

1. R -> S
2. U
3. U -> R
*  S
---------
4. R          3,2 Modus Ponens
5. S          1,4 Modus Ponens

There is another way to solve this problem. Let's restate it.

1. R -> S
2. U
3. U -> R
---------
* S

If we look carefully at premises 3 and 1, we will realize that we can apply the Chain Rule here.

4. U -> S     3,1 Chain Rule

Now we can apply Modus Ponens to the result.

5. S          4,2 Modus Ponens

We've reached the same conclusion, with the same number of steps.

1. R -> S
2. U
3. U -> R
*  S
---------
4. U -> S     3,1 Chain Rule
5. S          4,2 Modus Ponens

Problem 3

1. ~G -> L
2. G -> K
3. ~K
----------
* L

Let's look at premises 2 and 3. We can apply Modus Tollens here.

4. ~G         2,3 Modus Tollens

Now that we have ~G, we can look at premise 1 and realize that by applying Modus Ponens we can get L.

5. L          1,4 Modus Ponens

We are done.

1. ~G -> L
2. G -> K
3. ~K
*  L
----------
4. ~G         2,3 Modus Tollens
5. L          1,4 Modus Ponens

Problem 4

1. D v E
2. ~E
--------
* D v F

We see right away that we can apply Disjunctive Inference to premises 1 and 2. D is true because E is false.

3. D          1,2 Disjunctive Inference

4. D v F      3 Disjunctive Addition

We've reached the conclusion.

1. D v E
2. ~E
*  D v F
--------
3. D          1,2 Disjunctive Inference
4. D v F      3 Disjunctive Addition

Problem 5

1. K -> L
2. K v J
3. ~L
--------
* J

Look closely at premises 1 and 3. This looks like a perfect example of Modus Tollens.

4. ~K         1,3 Modus Tollens

We have a disjunction in premise 2, and we already know that K is not true. By Disjunctive Inference, we know that J must be true.

5. J          2,4 Disjunctive Inference

We've reached the conclusion.

1. K -> L
2. K v J
3. ~L
*  J
---------
4. ~K         1,3 Modus Tollens
5. J          2,4 Disjunctive Inference

Problem 6

1. G XOR H
2. H
3. G XOR J
--------
* J

Premise 2 states that H is true. Looking at premise 1, we realize that G has to be false -- that is the property of the XOR operator, and an example of Mutual Exclusion.

4. ~G         1,2 Mutual Exclusion

Now that we have ~G, we can use Disjunctive Inference with XOR on premise 3 to prove that J is true.

5. J          3,4 Disjunctive Inference with XOR

We have gotten to the conclusion.

1. G XOR H
2. H
3. G XOR J
*  J
---------
4. ~G         1,2 Mutual Exclusion
5. J          2,4 Disjunctive Inference with XOR