MAT1348 D ISCRETE M ATHEMATICS FOR C OMPUTING

4. The Laws of Logical Equivalences & DNF

Example 4.1. Using a truth table, verify each of the following laws from The Table of Logical
Equivalences:
⇧ p^T⌘p (Identity Law)
⇧ p_F⌘p (Identity Law)
⇧ p_T⌘T (Domination Law)
⇧ p^F⌘F (Domination Law)
⇧ p _ ¬p ⌘ T (Negation Law)
⇧ p ^ ¬p ⌘ F (Negation Law)

Identity Laws :
P PAT PAT '→P pnT=p
¥ It
because
¥ prtepisatautology .

PVF
p '→P =P corrections
EI

PVF
T T T because
F F T tautology .

PVTPVT
PAFPAF
pVT=T
PVT
PAF
Tisa
'→T
'→F
PAF
Domination Laws :p

Fisatautology
T because

pVF←pisa
T T

F T T -
tautology .

P = F
T F T because
F F T ←
.

PMPPMP
php←Tisa
PVPPHP
php=T
Negation
PAF
'→T
'→F
PAF
-=F
Laws :p

Fisatautology
T T T because
F T T tautology .

P
T F T because
F F T ←
.

⇤ These notes are solely for the personal use of students registered in MAT1348.
1
 T HE TABLE OF L OGICAL E QUIVALENCES

1. P ! Q ⌘ ¬P _ Q Implication Law

2. P $ Q ⌘ (P ^ Q) _ (¬P ^ ¬Q)
Biconditional Laws
3. P $ Q ⌘ (P ! Q) ^ (Q ! P )

4. P _ ¬P ⌘ T
Negation Laws
5. P ^ ¬P ⌘ F

6. P _F⌘P
Identity Laws
7. P ^T⌘P

8. P _T⌘T
Domination Laws
9. P ^F⌘F

10. P _P ⌘P
Idempotent Laws
11.
FsEoistas@2waystojhinKabfneatxnYnoIEEistCabitliKefactorifawayto5WwYkhdz.p P ^P ⌘P

12. ¬¬P ⌘ P Double Negation Law

13. P _Q⌘Q_P
Commutative Laws
14. P ^Q⌘Q^P

15. (P _ Q) _ R ⌘ P _ (Q _ R)
Associative Laws
16. (P ^ Q) ^ R ⌘ P ^ (Q ^ R)

17. P _ (Q ^ R) ⌘ (P _ Q) ^ (P _ R)
Distributive Laws
18. P ^ (Q _ R) ⌘ (P ^ Q) _ (P ^ R)

19. ¬(P ^ Q) ⌘ ¬P _ ¬Q
De Morgan’s Laws
20. ¬(P _ Q) ⌘ ¬P ^ ¬Q

✓ ( pna ) =P
2.
Absorption Laws
22 .
PACPVQ ) =p
 H OW TO U SE THE L AWS IN THE TABLE OF L OGICAL E QUIVALENCES

¢
Example 4.2. Prove ((x ^ y) _ (x ^ ¬y))_ (¬x ^ y) ⌘ x _ y

)= @
NYMYDVGXAY ) ( distributive law )

=[xnT]VGx^y ) ( negation law)

( identity

NDVKMYDVGXAY
= ( × )VGxny ) law)

%¢×^y)V(xmy))VGx^y)=xvy
XVTDAKVY )
=L ( distributive law )

=
Tncxvy ) ( negation law )

identity law)
= xvy

Example 4.3. Prove that (a ^ ¬b) ^ (¬a _ b) is a contradiction Note contradiction -=F
⇒
( amb)^Gavb)=anGb^GavbD ( associative law )

=a^[Gbma)VF] ( distributive law )

=a^[Gbma)VGbnb)]
negation
( law )

=a^[7bma] C identity law )

=(
=a^Gamb) commutative law )

amajmb ( associative law )

I Fmb ( negation law )

= F ( domination law )

%(amb)^GaVb)=F so (amb)^GaVb) isacontradiction .

3
Example 4.4. Find a compound proposition that is logically equivalent to X ^Y that uses
only the logical connectives ! and ¬.

XMEMKM ) ( double negation law )

ETGXVTY ) (Demorgan 's law )

=7(X→7Y ) C
implication law )

Thus , Wefounda proposition 7(X→7Y)suchthatXM=7(X→7' D and

7(X→7' D uses only theological connectives → and 7 .

Example 4.5. Find a compound proposition that is logically equivalent to p ! (q _ r) that

uses only the logical connectives ¬ and ^.

P→(qvr)=7pv( qvr )
C
implication law )

= MGPVCQVRD ( double negation)

(Demorganslaw)

Tandn
PAGQMRD
=7[PA7(qVrD
=7[77pn7(qvrD
( double negation law )

,P→(qvr)=7[p^GqmrDand7[p^GqmrD
=7[ ( Demorgarislaw )

thus usesonlythe
logical connectives .

A collection of connectives called

logical functionally complete
*
is if
-

every compound proposition

is
logically equivalent toacompound

proposition involving only these logical connectives .

3ms { , ,→} is functionally complete .

§*
Exercisemhshowthat
•
b 4
 D ISJUNCTIVE N ORMAL F ORM

An atom is a proposition containing no logical connectives (just a propositional variable).

A literal is an atom or the negation of an atom.
A conjunctive clause is a compound proposition that contains only literals and (possibly)
the connective ^, and no atom appears more than once.
A compound proposition is said to be in disjunctive normal form (DNF) if it is a
disjunction of conjunctive clauses.
Facts about DNF.
Every compound proposition is logically equivalent to a proposition in DNF.
DNF is not unique, but all DNF of a given compound proposition X are logically
equivalent to X, hence logically equivalent to each other.

FI .
a→b = b) V Gan b) V Gamb )
Can
← one possible DNF
of a → b

a→b =
Ga)V( b) ← another possible DNF of a → b

Using a Truth Table to Obtain a DNF for a given Proposition.

• Let X be a compound proposition consisting of the propositional variables p1 , . . . , pk .
• Construct a complete truth table for X.
• For each row in which X is T, write a conjunctive clause corresponding to the truth value
of each of the atoms p1 , . . . , pk .
• The disjunction of these conjunctive clauses is a DNF for X.
Example 4.6. Use a truth table to determine a DNF for the compound proposition X, defined as
follows:
X : ¬(p $ q) _ ¬q
conjunctive clauses
TI for each row where

pqpeq7Cpaqj7q7Cp@qWnqEisTo.T
T F T F F -

T F F T T T
Pmq
F F T F T
T
7pA of
F F T F T T
Tpmq

DNF for
CPMQNGPAQNGPMQ)
:
• a # is

Thus ( pmq)VGpnq)VGpmq)
, 7(pc→q)V7q =

5
 Example 4.7. The truth table of a mystery compound proposition X consisting of propositional
variables p, q, r, s is given below.
p q r s X conjunctive clauses
for each row where
T T T T F
# is T :
T T T F F
T T F T T pnqmms
T T F F F
T F T T T Pmqnr As
T F T F F
T F F T F
T F F F F
F T T T F
F T T F F
F T F T F
F T F F F
F F T T F
F F T F F
F F F T T 7PM qmms
F F F F F
i. Determine a DNF for X.
°°
• a DNF for # is

( pnqmms )V( pmqnr ASNGPMQMMS )

ii. Is X a tautology, contradiction, or contingency? Explain.

# is a
contingency because it is not always true nor always false .

mw
exercise: Try to find a compound proposition that is logically equivalent to X that uses only the
connectives ! and ¬ (and parentheses wherever appropriate).

S TUDY G UIDE

Important terms and concepts:

⇧ The Laws from the Table of Logical Equivalences
⇧ DNF (atoms, literals, conjunctive clauses) how to find DNF from a truth table
Exercises Sup.Ex. §1 # 1, 2, 3, 7ac (using the Laws), 8
Rosen §1.3 # 7, 8, 15, and using the Laws: # 20–34
**For each of the following, find a compound proposition that uses only
the connectives ¬ and !
i. p _ q ii. p ^ q iii. p q iv. p $ q
Rosen §1.3 optional: # 47–56
6