Page 23 - Computer science 868 Class 12
P. 23

From the above table, it is clear that both columns (a → b) ∧ (b → a) and a ↔ b have the same values (1, 0, 0, 1) for
                 the same combinations of a and b. Hence proved. This rule is also called Bi-conditional elimination.
                 Example 4: Prove using truth table a → b = b' → a'.

                 Solution:
                              a         b         a'        b'      a → b    b' → a'
                              0         0         1         1         1         1
                              0         1         1         0         1         1
                              1         0         0         1         0         0

                              1         1         0         0         1         1
                 From the above table, it is clear that both columns a → b and b' → a' have identical values (1, 1, 0, 1), for the same
                 combinations of a and b, hence they are equivalent. This rule is also called transportation (logic).
                 Example 5: From the premises a and a → b infer b

                               Or
                 Prove that (a ∧ (a → b)) → b = 1.

                 Solution:  Let us draw the truth table of a and a → b, i.e., (a ∧ (a → b)). Now inference is to be drawn on b which means
                 the expression is:

                 if (a ∧ (a → b)) then b or (a ʌ (a → b)) → b which is a tautology as seen in the truth table given below. Hence,
                 (a ∧ (a → b)) → b) = 1 is also proved.

                 The above rule is also called Modus Ponens.

                                           a        b       a → b      a ∧ (a → b)  (a ∧ (a → b)) → b
                                           0        0         1           0              1

                                           0        1         1           0              1
                                           1        0         0           0              1
                                           1        1         1           1              1

                 Example 6: If p → q and q → r are two propositions, then derive p → r
                 Solution:

                 Premises 1: p → q
                 Premises 2: q → r

                 Inference to be drawn on p → r

                 Let us draw the truth table of p → q and q → r, i.e., (p → q) ʌ (q → r)
                 To derive a conclusion on p → r, we write:

                 if p → q and q → r then p → r
                 Or

                 (p → q) ʌ (q → r) → p → r which is a tautology as derived from the truth table given below.
                 We can thus conclude p → q and q → r infers p → r

                 The above proposition is called the Chain rule or law of syllogism.




                                                                                                                        21
                                                                                                      Boolean Algebra   21
   18   19   20   21   22   23   24   25   26   27   28