Page 53 - computer science (868) class 11
P. 53

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


                                                                                                                        51
                                                           Propositional Logic, Hardware Implementation, Arithmetic Operations  51
   48   49   50   51   52   53   54   55   56   57   58