Page 77 - Cs_withBlue_J_C11_Flipbook
P. 77

3.5 EQUIVALENCE PROPOSITIONAL LAWS
                 Two statements are said to be equivalent if they have the same truth values for all the possible combinations of their
                 variables. Thus, if the values of a and b are true in the same set of models, then they are said to be logically equivalent.

                 Some commonly used equivalence laws are given below. These laws can be proved using the truth tables:

                                                  Name                           Expression
                                                                      a.  a ∨ 0 = a
                                      1.  Properties of 0
                                                                      b.  a ∧ 0 = 0
                                                                      a.  a ∨ 1 = 1
                                      2.  Properties of 1
                                                                      b.  a ∧ 1 = a
                                      3.  Involution law              a.  (a')'  = a
                                                                      a.  a ∨ a = a
                                      4.  Idempotent law
                                                                      b.  a ∧ a = a
                                                                      a.  a ∨ a' = 1
                                      5.  Complementarity law
                                                                      b.  a ∧ a' = 0
                                                                      a.  a ∨ b = b ∨ a
                                      6.  Commutative law
                                                                      b.  a ∧ b = b ∧ a
                                                                      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.  Biconditional elimination   a.  a ↔ b = (a → b) ∧ (b → a)
                 Example 1: Prove the following using the truth table:

                    i.  a ∨ (a ∧ b) = a
                   ii.  a ∧ (a ∨ b) = a
                 Ans.
                           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 table, we see column a ∨ (a ∧ b) and 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.
                 Ans.
                          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


                                                                                                                        75
                                                           Propositional Logic, Hardware Implementation, Arithmetic Operations  75
   72   73   74   75   76   77   78   79   80   81   82