Propositional Logic

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.

Rules of Inference

Tautological Form

Name

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

-------
P Q
conjunction
(P Q) (R S)
P
R
-------
Q S
[(P Q) (R S) (P R)] [Q S] constructive dilemma
(P Q) (R S)
Q S
----------
P R
[(P Q) (R S) ( Q S)] [ P R] destructive dilemma


Example of Inferencing

Consider the following argument:

1. Today is Tuesday or Wednesday.

2. But it can't be Wednesday, since the doctor's office is open today, and that office is always closed on Wednesdays.

3. Therefore today must be Tuesday.

This sequence of reasoning (inferencing) can be represented as a series of application of modus ponens to the corresponding propositions as follows.

The modus ponens is an inference rule which deduces Q from tex2html_wrap_inline32 and P.

T: Today is Tuesday.

W: Today is Wednesday.

D: The doctor's office is open today.

C: The doctor's office is always closed on Wednesdays.

The above reasoning can be represented by propositions as follows.

tex2html_wrap_inline44
tex2html_wrap_inline46
------------
T

To see if this conclusion T is correct, let us first find the relationship among C, D, and W:

C can be expressed using D and W. That is, restate C first as the doctor's office is closed if it is Wednesday. Then tex2html_wrap_inline56 . Thus substituting tex2html_wrap_inline58 for C, we can proceed as follows.

tex2html_wrap_inline62
D
------------
tex2html_wrap_inline66
tex2html_wrap_inline44
------------
T


Next -- Proof of Identities

Back to Table of Contents