Page 25 - Computer science 868 Class 12
P. 25

Example 2:  Prove that ((a → b) ∧ (b → c)) → (a → c) is a tautology.
                 Solution:


                        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.

                 Solution:                                                             a      a'   a ∧ a'
                 The final column is 0 for all values of a. Hence, it is a contradiction.  0  1      0
                                                                                       1      0      0
                 Example 4: Prove that ((a → b) ∧ (b → c)) ∧ (a ∧ ∼c) is a contradiction.
                 Solution:

                         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.                       a      b    a ∨ b  ∼(a ∨ b)
                 Solution:                                                              0      0      0       1

                 The values in the final column contain both 0 and 1.                   0      1      1       0
                 Hence, it is a contingency.                                            1      0      1       0
                                                                                        1      1      1       0
                 Example 6: Prove that (a ∧ (a → b)) → ∼a is a contingency.

                 Solution:
                                           a     b   ∼a   a → b     a ∧ (a → b)  (a ∧ (a → b)) → ∼a
                                           0     0    1     1         0                1
                                           0     1    1     1         0                1
                                           1     0    0     0         0                1
                                           1     1    0     1         1                0
                 The last column has both 0 and 1 as truth values. So, it is a contingency.



                                                                                                                        23
                                                                                                      Boolean Algebra   23
   20   21   22   23   24   25   26   27   28   29   30