0.3 Discrete structures logic  (Page 9/23)

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.

Reasoning with propositions

Logical reasoning is the process of drawing conclusions from premises using rules of inference. The basic inference rule is modus ponens. It states that if both P→Q and P hold, then Q can be concluded, and it is written as

P

P →Q

-----------------

Q

Here the lines above the dotted line are premises and the line below it is the conclusion drawn from the premises.

For example if "if it rains, then the game is not played" and "it rains" are both true, then we can conclude that the game is not played.

In addition to modus ponens, one can also reason by using identities and implications.

If the left (right) hand side of an identity appearing in a proposition is replaced by the right(left) hand side of the identity, then the resulting proposition is logically equivalent to the original proposition. Thus the new proposition is deduced from the original proposition. For example in the proposition P ⋀(Q→R), (Q→R) can be replaced with (¬Q ⋁R) to conclude P ⋀(¬Q ⋁R), since (Q→R) ⇔(¬Q ⋁R)

Similarly if the left (right) hand side of an implication appearing in a proposition is replaced by the right(left) hand side of the implication, then the resulting proposition is logically implied by the original proposition. Thus the new proposition is deduced from the original proposition.

The tautologies listed as "implications" can also be considered inference rules as shown below.