Page 24 - Computer science 868 Class 12
P. 24

p      q       r    p → q  q → r    (p → q) ∧ (q → r)  p → r  (p → q) ∧ (q → r) → p → r
                          0      0      0       1      1             1            1               1
                          0      0      1       1      1             1            1               1
                          0      1      0       1      0             0            1               1
                          0      1      1       1      1             1            1               1
                          1      0      0       0      1             0            0               1
                          1      0      1       0      1             0            1               1
                          1      1      0       1      0             0            0               1
                          1      1      1       1      1             1            1               1

                  1.8 TAUTOLOGY, CONTRADICTION AND CONTINGENCY


                   Tautology                        Contradiction                       Contingency
                 A compound  proposition  is         A compound  proposition  is        A  compound proposition  is
                 called a tautology if and only if, it   called  a contradiction  if  and   called  contingency  if  and  only
                 is true for all possible truth values   only if it is false for all possible   if it is neither a tautology nor a
                 of its propositional  variables.    truth values of its propositional   contradiction.  The proposition
                 The proposition evaluates 1 or      variables.  The    proposition     contains  both  0  (false)  and  1
                 true in  its  final  column  of  the   evaluates 0 or false in  the final   (true) in the final column of the
                 truth table.                        column of the truth table.         truth table.



                     Valid                           Unsatisfiable                       Satisfiable

                  A  compound  proposition  is       A  compound  proposition  is       A  compound  proposition  is
                  called valid if and only if it is true   called unsatisfiable if and only if it   called  satisfiable  if  and  only  if
                  for all  possible  truth values  of   is false for all possible truth values   it is true  for some  values of its
                  its  propositional variables.  The   of its propositional variables. The   proposition variables. It contains
                  proposition  evaluates 1 or true   proposition  evaluates  0  or false   either  only  1  (all  true)  or  both
                  in  its  final  column  of  the truth   in  the final  column  of  the truth   0 (false) and 1 (true) in the final
                  table.                             table.                             column of the truth table.

              We can thus conclude that:

              •  All tautologies are valid and all valid propositions are tautology.
              •  All tautologies are satisfiable but all satisfiable propositions are not valid.
              •  All contingencies are satisfiable but all satisfiable propositions are not contingency.
              •  All contradictions are unsatisfiable and all unsatisfiable propositions are contradictions.
              Example 1: Prove that a ∨ a' is a tautology.

              Solution:
              The final column is 1 for all values of a.                                a           a'        a ∨ a'
                                                                                        0           1           1
              Hence, it is a tautology.
                                                                                        1           0           1







                2222  Touchpad Computer Science-XII
   19   20   21   22   23   24   25   26   27   28   29