Page 78 - Cs_withBlue_J_C11_Flipbook
P. 78

From the table, we conclude a → b = a' ∨ b, as both columns have the same values (1, 1, 0, 1) for the same combinations of
              a and b. This law is called Conditional elimination.
              Example 3: Prove using truth table a ↔ b = (a → b) ∧ (b → a).

              Ans.
                        a       b     a ↔  b   a → b    b → a   (a → b) ∧ (b → a)
                       0        0       1        1       1             1
                       0        1       0        1       0             0
                       1        0       0        0       1             0
                       1        1       1        1       1             1

              Both columns (a → b) ∧ (b → a) and a ↔ b have same values (1, 0, 0, 1) for the same combinations of a and b. Hence
              proved. This rule is also called Biconditional elimination.

              Example 4: Prove using truth table a → b = b' → a'.
              Ans.      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
              Columns a → b and b' → a' have identical values (1, 1, 0, 1), hence they are equivalent. This rule is also called
              transportation (logic).
              Example 5: Prove that (a ∧ (a → b)) → b = 1.

              Ans.
                       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

              Here, (a ∧ (a → b)) → b has value (1, 1, 1, 1) for all combinations of a and b. Hence, we conclude (a ∧ (a → b)) → b = 1.
              The above rule is also called Modus Ponens.

                  3.6 TAUTOLOGY, CONTRADICTION AND CONTINGENCY

                           Tautology                          Contradiction                       Contingency

                   A  compound  proposition            A  compound  proposition            A  compound  proposition
                   is  called  a tautology  if         is called  a  contradiction  if     is  called  a contingency if
                   and only if it is true for all      and only if it is false for all     and  only  if it is neither a
                   possible truth values of its        possible  truth  values  of  its    tautology nor a contradiction.
                   propositional variables. The        propositional variables. The        The proposition contains both
                   proposition is evaluated as         proposition  evaluates as  0        0  (false)  and  1  (true)  in  its
                   1 or true in the last column        or false in its last column of      last column  of the truth
                   of the truth table.                 the truth table.                    table.







                7676  Touchpad Computer Science-XI
   73   74   75   76   77   78   79   80   81   82   83