8 ~ Theory of Computer Science
TABLE 1.8 Truth Table of Example 1.6
P
Q
R
PvR
RvQ
(P v R) => (R v Q)
(P v Q)
a
T
T
T
T
T
T
T
T
T
T
F
T
T
T
T
T
T
F
T
T
T
T
T
T
T
F
F
T
F
F
T
F
F
T
T
T
T
T
T
T
F
T
F
F
T
T
T
T
F
F
T
T
T
T
F
T
F
F
F
F
F
T
F
T
Some formulas have the truth value T for all possible assignments of truth
values to the propositional variables. For example. P v --, P has the truth value
T irrespective of the truth value of P. Such formulas are called tautologies.
Definition 1.3 A tautology or a universally true formula is a well-fonned
formula whose truth value is T for all possible assignments of truth values to
the propositional variables.
For example. P v --, P, (P ;\ Q) ==> P. and ((P ==> Q) ;\ (Q ==> R» ==>
(P ==> R) are tautologies.
Note: When it is not clear whether a given formula is a tautology. we can
construct the truth table and verify that the truth value is T for all combinations
of truth values of the propositional variables appearing in the given formula.
EXAMPLE 1.7
Show that ex = (P ==> (Q ==> R) ==> ((P ==> Q) ==> (P--~R) is a tautology.
Solution
We give the truth values of ex in Table 1.9.
TABLE 1.9 Truth Table of Example 1.7
P Q
R Q=>R P => (Q => R) P=>Q P=>R (P => Q) => (P => R) a
T
T
T
T
T
T
T
T
T
T
T
F
F
F
T
F
F
T
T
F
T
T
T
F
T
T
T
T
F
F
T
T
F
F
T
T
F
T
T
T
T
T
T
T
T
F
T F
F
T
T
T
T
T
F
F
T
T
T
T
T
T
T
F
F
F
T
T
T
T
T
T
Defmition 1.4 A contradiction (or absurdity) is a wff whose truth value is
F for all possible assignments of truth values to the propositional variables.
For example.
and
(P ;\ Q) 1\ --, Q
are contradictions.
Note: ex is a contradiction if and only jf --, ex is a tautology.
http://engineeringbooks.net