Page 79 - Cs_withBlue_J_C11_Flipbook
P. 79

Example 1: Prove that a ∨ a' is a tautology.
                 Ans. The final column is 1 for all values of a. Hence, it is a tautology.

                                                             a      a'    a ∨ a'
                                                             0      1      1
                                                             1      0      1

                 Example 2: Prove that ((a → b) ∧ (b → c)) → (a → c) is a tautology.
                 Ans.
                        a    b    c    (a → b)   (b → c)   (a → c)    (a → b) ∧ (b → c)  ((a → b) ∧ (b → c)) → (a → c)
                        0    0    0       1         1         1             1                       1
                        0    0    1       1         1         1             1                       1
                        0    1    0       1         0         1             0                       1
                        0    1    1       1         1         1             1                       1
                        1    0    0       0         1         0             0                       1
                        1    0    1       0         1         1             0                       1
                        1    1    0       1         0         0             0                       1
                        1    1    1       1         1         1             1                       1
                 The final column results in 1. So, it is a tautology.
                 Example 3: Prove that a ∧ a' is a contradiction.
                 Ans. The final column is 0 for all values of a. Hence, it is a contradiction.
                                                             a      a'    a ∧ a'
                                                             0      1      0
                                                             1      0      0
                 Example 4: Prove that ((a → b) ∧ (b → c)) ∧ (a ∧ ∼c) is a contradiction.
                 Ans.    a    b      c    (a → b)   (b → c)   a ∧ ~c  (a → b) ∧ (b → c)  ((a → b) ∧ (b → c)) ∧ (a ∧ ∼c)

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

                 The final column results in 0. So, it is a contradiction.
                 Example 5: Prove that ∼(a ∨ b) is a contingency.
                 Ans. The values in the final column contain both 0 and 1.
                 Hence, it is a contingency.

                                                        a       b    a ∨ b  ∼(a ∨ b)

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





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