| << Chapter < Page | Chapter >> Page > |
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
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.
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 |
Notification Switch
Would you like to follow the 'Discrete structures' conversation and receive update notifications?
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|