Page 76 - ComputerScience_Class_11
P. 76
Let's break each of them down:
Tautology Contradiction Contingency
A compound proposition A compound proposition A compound proposition
is called a tautology if is called a contradiction if is called a contingency if
and only if it is true for all and only if it is false for all and only if it is neither a
possible truth values of its possible truth values of its tautology nor a contradiction.
propositional variables. The propositional variables. The The proposition contains both
proposition is evaluated as proposition evaluates as 0 0 (false) and 1 (true) in its
1 or true in the last column or false in its last column of last column of the truth
of the truth table. the truth table. table.
Example 1: Prove that a ∨ a' is a tautology.
Answer: 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.
Answer: 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. Hence, it is a tautology.
Example 3: Prove that a ∧ a' is a contradiction.
Answer: 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.
Answer: a b c (a → b) (b → c) ~c a ∧ ~c (a → b) ∧ (b → c) ((a → b) ∧ (b → c)) ∧ (a ∧ ∼c)
0 0 0 1 1 1 0 1 0
0 0 1 1 1 0 0 1 0
0 1 0 1 0 1 0 0 0
0 1 1 1 1 0 0 1 0
1 0 0 0 1 1 1 0 0
1 0 1 0 1 0 0 0 0
1 1 0 1 0 1 1 0 0
1 1 1 1 1 0 0 1 0
The final column results in 0. Hence, it is a contradiction.
74 Touchpad Computer Science (Ver. 3.0)-XI
