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

