10 !!!! Theory of Computer Science
TABLE 1.11 Logical Identities
1 1
Idempotent laws:
P v P '" P,
P ;\ P '" P
1 2
Commutative laws:
P v Q '" Q v P, p;\ Q '" Q 1\ P
1 3
Associative laws:
P v (Q v R) '" (P v Q) v R,
1 4
Distributive laws:
P 1\ (Q 1\ R) '" (P ;\ Q) 1\ R
P 1\ (P V Q) '" P
by using the distributive law (i.e. 1 4 )
by using Is
by using 1 9
by using 1 12
by using the commutative law (i.e. 1 2 )
by using the distributive law (i.e. 1 4 )
by using the DeMorgan's law (i.e. 1 6 )
by using the commutative law (i.e. 1 2 )
,by using 1]2
P v (Q 1\ R) '" (P v Q) 1\ (P v R),
P ;\ (Q v R) '" (P ;\ Q) v (P 1\ R)
----_._----_._~-~-_
.._ --------_ - -_._, ,.__._._ _ - ~ ~ - - -
Is
Absorption laws:
P v (P 1\ Q) ",p.
Is
DeMorgan's laws:
---, (P v Q) '" ---, P 1\ ---, Q,
---, (P 1\ Q) '" ---, P v ---, Q
1 7
Double negation:
P '" ---, (-, P)
1 8
P V ---, P '" T,
P 1\ ---, P '" F
19
P v T '" T,
P 1\ T '" P,
P v F '" P,
P 1\ F '" F
~~I__~ Q) 1\ (P =} ---, Q) =- ~____ ~
~~
~~
~~_._... . . _
1 11 Contra positive:
P=}Q"'---,Q=}---,P
1 12 P =} Q '" (-, P v Q)
EXAMPLE 1.9
Show that (P 1\ Q) V (P 1\ --, Q) == P.
Solution
L.H.S. = (P 1\ Q) V (P 1\ --, Q)
== P 1\ (Q V --, Q)
==PI\T
== P
= R.H.S.
EXAMPLE 1.10
Show that (P ~ Q) 1\ (R ~ Q) == (P v R) ~ Q
Solution
L.H.S. = (P ~ Q) 1\ (R ~ Q)
== (--, P v Q) 1\ (--, R v Q)
== (Q v --, P) 1\ (Q V --, R)
== Q v (--, P 1\ --, R)
== Q v (--, (P v R))
== (--, (P v R)) v Q
== (P v R) ~ Q
= R.H.S.
http://engineeringbooks.net