<< Chapter < Page Chapter >> Page >

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 P → Q 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.

1. T ⋁ W

2. D

C

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

~W

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

3. 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 always closed if it is Wednesday. Then C ↔ (W → ~D) Thus substituting (W → ~D) for C, we can proceed as follows.

D

W → ~D

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

~W

which is correct by modus tollens.

From this ~W combined with T V W of 1. above,

~W

T ⋁ W

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

T

which is correct by disjunctive syllogism.

Thus we can conclude that the given argument is correct.

To save space we also write this process as follows eliminating one of the ~W's:

D

W → ~D

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

~W

T ⋁ W

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

T

Proof of identities

All the identities in Section Identities can be proven to hold using truth tables as follows. In general two propositions are logically equivalent if they take the same value for each set of values of their variables. Thus to see whether or not two propositions are equivalent, we construct truth tables for them and compare to see whether or not they take the same value for each set of values of their variables.

For example consider the commutativity of ⋁:

(P ⋁Q) ⇔(Q ⋁P).

To prove that this equivalence holds, let us construct a truth table for each of the proposition (P ⋁Q) and (Q ⋁P).

A truth table for (P ⋁Q) is, by the definition of ⋁,

P Q (P ⋁Q)
F F F
F T T
T F T
T T T

A truth table for (Q ⋁P) is, by the definition of ⋁,

P Q (Q ⋁P)
F F F
F T T
T F T
T T T

As we can see from these tables (P ⋁Q) and (Q ⋁P) take the same value for the same set of value of P and Q. Thus they are (logically) equivalent.

We can also put these two tables into one as follows:

P Q (P ⋁Q) (Q ⋁P)
F F F F
F T T T
T F T T
T T T T

Using this convention for truth table we can show that the first of De Morgan's Laws also holds.

P Q ¬(P ⋁Q) ¬P ⋀¬Q
F F T T
F T F F
T F F F
T T F F

By comparing the two right columns we can see that ¬(P ⋁Q) and ¬P ⋀¬Q are equivalent.

Proof of implications

1. All the implications in Section Implications can be proven to hold by constructing truth tables and showing that they are always true.

For example consider the first implication "addition": P ⇒ (P ⋁ Q).

To prove that this implication holds, let us first construct a truth table for the proposition P ⋁ Q.

P Q (P ⋁ Q)
F F F
F T T
T F T
T T T

Then by the definition of →, we can add a column for P → (P ⋁ Q) to obtain the following truth table.

P Q (P ⋁ Q) P →(P ⋁ Q)
F F F T
F T T T
T F T T
T T T T

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Discrete structures. OpenStax CNX. Jan 23, 2008 Download for free at http://cnx.org/content/col10513/1.1
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Discrete structures' conversation and receive update notifications?

Ask