Propositional Logic

- implications (tautologies) of propositional logic

The following implications are
some of the relationships between
propositions that can be derived from the definitions(meaning) of connectives.

below corresponds to
and it means that the implication
always holds. That is it is a tautology.

These implications are used in logical reasoning. When the right hand side of these implications is substituted for the left hand side appearing in a proposition, the resulting proposition is implied by the original proposition, that is, one can deduce the new proposition from the original one.

First the implications are listed, then examples to illustrate them are given.

- P (P Q) ----- addition
- (P Q) P ----- simplification
- [P (P Q] Q ----- modus ponens
- [(P Q) Q] P ----- modus tollens
- [ P (P Q] Q ----- disjunctive syllogism
- [(P Q) (Q R)] (P R) ----- hypothetical syllogism
- (P Q) [(Q R) (P R)]
- [(P Q) (R S)] [(P R) (Q S)]
- [(P Q) (Q R)] (P R)

1. P (P Q) ----- addition

For example, if the sun is shining, then certainly the sun is shining or it is snowing. Thus "if the sun is shining, then the sun is shining or it is snowing." "If

2. (P Q) P ----- simplification

For example, if it is freezing and (it is) snowing, then certainly it is freezing. Thus "If it is freezing and (it is) snowing, then it is freezing."

3. [P (P Q] Q ----- modus ponens

For example, if the statement "If it snows, the schools are closed" is true and it actually snows, then the schools are closed.

This implication is the basis of all reasoning. Theoretically, this is all that is necessary for reasoning. But reasoning using only this becomes very tedious.

4. [(P Q) Q] P ----- modus tollens

For example, if the statement "If it snows, the schools are closed" is true and the schools are not closed, then one can conclude that it is not snowing.

Note that this can also be looked at as the application of the contrapositive and modus ponens. That is, (P Q) is equivalent to ( Q ) ( P ). Thus if in addition Q holds, then by the modus ponens, P is concluded.

5. [ P (P Q] Q ----- disjunctive syllogism

For example, if the statement "It snows or (it) rains." is true and it does not snow, then one can conclude that it rains.

6. [(P Q) (Q R)] (P R) ----- hypothetical syllogism

For example, if the statements "If the streets are slippery, the school buses can not be operated." and "If the school buses can not be operated, the schools are closed." are true, then the statement "If the streets are slippery, the schools are closed." is also true.

7. (P Q) [(Q R) (P R)]

This is actually the hypothetical syllogism in another form. For by considering (P Q) as a proposition S, (Q R) as a proposition T, and (P R) as a proposition U in the hypothetical syllogism above, and then by applying the "exportation" from the identities, this is obtained.

8. [(P Q) (R S)] [(P R) (Q S)]

For example, if the statements "If the wind blows hard, the beach erodes." and "If it rains heavily, the streets get flooded." are true, then the statement "If the wind blows hard and it rains heavily, then the beach erodes and the streets get flooded." is also true.

9. [(P Q) (Q R)] (P R)

This just says that the logical equivalence is transitive, that is, if P and Q are equivalent, and if Q and R are also equivalent, then P and R are equivalent.

Click Yes or No , then Submit. There are two sets of questions.