Page 22 - Computer science 868 Class 12
P. 22

a.  (a ∨ b) ∨ c = a ∨ (b ∨ c)
                                    7.  Associative law            b.  (a ∧ b) ∧ c = a ∧ (b ∧ c)

                                                                   a.  a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)
                                    8.  Distributive law
                                                                   b.  a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)
                                                                   a.  (a ∧ b)' = a' ∨ b'
                                    9.  De Morgan’s law
                                                                   b.  (a ∨ b)' = a' ∧ b'

                                   10.  Conditional elimination    a.  a → b = a' ∨ b


                                   11.  Bi-conditional elimination  a.  a ↔ b = (a → b) ∧ (b → a)

              Let us understand equivalence laws with the help of some examples.

              Example 1: Prove the following using the truth table:
              i.  a ∨ (a ∧ b) = a
              ii. a ∧ (a ∨ b) = a
              Solution: The truth table for the given propositions is as follows:


                                   a           b        (a ∧ b)     a ∨ (a ∧ b)   (a ∨ b)    a ∧ (a ∨ b)
                                   0           0           0           0            0           0
                                   0           1           0           0            1           0

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

              From the above table, we see that the fourth column a ∨ (a ∧ b) and the sixth column a ∧ (a ∨ b) have the same value
              (0, 0, 1, 1) as that of column a. Hence proved. This law is called Absorption law.
              Example 2: Prove using truth table a → b = a' ∨ b.

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

                            1         1         0         1         1
              From the table, we conclude a → b = a' ∨ b as both columns have the same value (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).
              Solution:    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





                2020  Touchpad Computer Science-XII
   17   18   19   20   21   22   23   24   25   26   27