C H A P T E R

1 The Foundations:
Logic and Proofs

1.1

1.2 n
n n(n + )/

1.3

1.4

1.5

1.6

1.7

1.8

Introduction
 Propositions

EXAMPLE 1

+ =
+ =

▲
EXAMPLE 2

x+ =
x+y =z

b.c.e. b.c.e. ▲
 p, q, r, s, . . . .

DEFINITION 1 p p ¬p p

p
¬p p p ¬p
p

EXAMPLE 3

▲
EXAMPLE 4
▲
 p
p
¬p p

p ¬p

DEFINITION 2 p q p q p∧q
p q p∧q p q

p∧q
p q
p
q

EXAMPLE 5 p q p
q

p∧q

▲
DEFINITION 3 p q p q p∨q
p q p∨q p q

p∨q

p q p∧q p q p∨q
EXAMPLE 6 p q p q

p q p∨q

▲
p q
p q p q
p q p q
 p→q
p q p⊕q p q p→q

DEFINITION 4 p q p q p⊕q
p q

Conditional Statements

DEFINITION 5 p q p→q p
q p→q p q
p→q p
q

p→q p→q q
p
p→q
p→q p q p
q

p→q

p q p q
p q p q
p q q p
q p q p
q p q p
p q q p
q ¬p
 p
q p→q

p→q
p q q ¬p

p q p q p
q p q p
q p q
q q p p→q
q p p→q
p q
q ¬p p
q q ¬p ¬p q
q ¬p p q
q ¬p p→q

EXAMPLE 7 p q
p→q

p
q p→q

▲
 + =

+ =

+ =

p S p
S
S p S p

EXAMPLE 8 x

+ = x := x +

x= :=
x := x + x+ x

+ = x := x +
+ =

▲
x

CONVERSE, CONTRAPOSITIVE, AND INVERSE

p→q
q→p
p→q p→q ¬q → ¬p
¬p → ¬q p→q
p→q
p→q
¬q → ¬p p→q
p→q
¬p ¬q p q
q→p ¬p → ¬q p→q
p q p q
 EXAMPLE 9

q p
p→q

▲
BICONDITIONALS

DEFINITION 6 p q p↔q p
q p↔q q

p↔q p↔q
p→q q→p

→ ← p↔q
p q
p q
p q
p↔q
p↔q (p → q) ∧ (q → p)

p↔q
p q p↔q
EXAMPLE 10 p q
p↔q

p q

p q

▲
IMPLICIT USE OF BICONDITIONALS

p→q p↔q

Truth Tables of Compound Propositions

EXAMPLE 11

(p ∨ ¬q) → (p ∧ q).

p q

p q
¬q p ∨ ¬q
p∧q (p ∨ ¬q) → (p ∧ q)
▲

(p ∨ ¬ q) → (p ∧ q)
p q ¬q p ∨ ¬q p∧q (p ∨ ¬q) → (p ∧ q)
 Precedence of Logical Operators

(p ∨ q) ∧ (¬r)
p∨q ¬r
¬p ∧ q
¬p q (¬p) ∧ q p q ¬(p ∧ q)
¬

∧ p∧q∨r (p ∧ q) ∨ r p ∧ (q ∨ r)
∨

→
↔ → ↔
∧ ∨
p∨q →r (p ∨ q) → r

¬ ∧ ∨ → ↔

Logic and Bit Operations

∧ ∨ ⊕

∨, ∧ ⊕
 x∨y x∧y x⊕y

DEFINITION 7

EXAMPLE 12

▲
∨, ∧ ⊕

EXAMPLE 13

▲
Exercises

+x =

n ≥

+ =
+ =
x+ = + =
 p q

· · = ¬p p∨q
¬p ∧ q q→p
¬q → ¬p ¬p → ¬q
p↔q ¬q ∨ (¬p ∧ q)
p q
p:
q:
p q

p q r
p:
q:
r:

p→q ¬q ↔ r
q → ¬r p∨q ∨r
(p → ¬r) ∨ (q → ¬r)
(p ∧ q) ∨ (¬q ∧ r)
p q
p:
q:
p q

p q
p:
q:

¬p p∨q p→q
p∧q p↔q ¬p → ¬q
¬p ∧ ¬q ¬p ∨ (p ∧ q)
p q
p q r
p:
q:
¬q p∧q ¬p ∨ q r:
p → ¬q ¬q → p ¬p → ¬q p q r
p ↔ ¬q ¬p ∧ (p ∨ ¬q)
 ++

p q r
p:
q:
r:
p q r

−
p q

+ = + =
+ = + =
+ =
> > p q

+ = + =
+ = + =
+ = + =
+ =

+ =
+ =
+ =
+ = + =
 p q q ∨ p ∨ ¬s ∨ ¬r ∨ ¬t ∨ u
p ∧ r ∧ t) ↔ q ∧ t)

(q → ¬p) ∨ (¬p → ¬q)

(p ∨ ¬t) ∧ (p ∨ ¬s)
(p → r) ∨ (¬s → ¬t) ∨ (¬u → )
p ∧ r ∧ s) ∨ (q ∧ t) ∨ (r ∧ ¬t)

p ∧ ¬p p ∨ ¬p
(p ∨ ¬q) → q (p ∨ q) → (p ∧ q)
(p → q) ↔ (¬q → ¬p)
(p → q) → (q → p)

p p → ¬p p ↔ ¬p
q p ⊕ (p ∨ q) (p ∧ q) → (p ∨ q)
(q → ¬p) ↔ (p ↔ q)
(p ↔ q) ⊕ (p ↔ ¬q)

(p ∨ q) → (p ⊕ q) (p ⊕ q) → (p ∧ q)
(p ∨ q) ⊕ (p ∧ q) (p ↔ q) ⊕ (¬p ↔ q)
(p ↔ q) ⊕ (¬p ↔ ¬r)
(p ⊕ q) → (p ⊕ ¬q)

p
q p⊕p p ⊕ ¬p
p ⊕ ¬q ¬p ⊕ ¬q
(p ⊕ q) ∨ (p ⊕ ¬q) (p ⊕ q) ∧ (p ⊕ ¬q)

p → ¬q ¬p ↔ q
(p → q) ∨ (¬p → q) (p → q) ∧ (¬p → q)
(p ↔ q) ∨ (¬p ↔ q)
(¬p ↔ ¬q) ↔ (p ↔ q)

(p ∨ q) ∨ r (p ∨ q) ∧ r
(p ∧ q) ∨ r (p ∧ q) ∧ r
(p ∨ q) ∧ ¬r (p ∧ q) ∨ ¬r

p → (¬q ∨ r)
¬p → (q → r)
(p → q) ∨ (¬p → r)
(p → q) ∧ (¬p → r)
(p ↔ q) ∨ (¬q ↔ r)
(¬p ↔ ¬q) ↔ (q ↔ r)
p → ¬p ((p → q) → r) → s
(p ∨ ¬r) ∧ (q ∨ ¬s) (p ↔ q) ↔ (r ↔ s)
 (p ∨ ¬q) ∧
(q ∨ ¬r) ∧ (r ∨ ¬p) p q r

(p ∨ q ∨ r) ∧
(¬p ∨ ¬q ∨ ¬r) p q r

x
x=

x+ = x := x +
x+ = ) x+ = x := x +
( x+ = ) ( x+ = ) x := x +
(x + = ) (x + = ) x := x +
x< x := x +

,
, ∗
, ∗ n
, n

∧( ∨ )
( ∧ )∨ n n
( ⊕ )⊕
( ∨ )∧( ∨ )

Introduction

Translating English Sentences

EXAMPLE 1

a c f

a → (c ∨ ¬f ).

▲
EXAMPLE 2

q r s

(r ∧ ¬s) → ¬q.

System Specifications

EXAMPLE 3

p
q ¬p
 q → ¬p

▲
EXAMPLE 4

p q

p ∨ q ¬p p→q
p ¬p p∨q p
q p→q p q
p q

▲
p q

EXAMPLE 5

p q ¬q

▲
q

Boolean Searches

EXAMPLE 6
 ▲
Logic Puzzles

EXAMPLE 7

A B A B A B B

p q A B
¬p ¬q A B
A p A
B q A B
B B A B
(p ∧ ¬q) ∨ (¬p ∧ q) A
B A p

A A B
q q B
B B A B
A B A B
▲
EXAMPLE 8

s d

s∨d

d s
s d
d
s∨d
s
d d s∨d
s
s

▲
Logic Circuits

p , p , . . . , pn
s , s , . . . , sn
 ¬ ∨ ∧

v g g

∧¬
∧¬ ∨¬
¬

p ¬p
p q p∨q
p q
p∧q

EXAMPLE 9

p ¬q q p ∧ ¬q
p ∧ ¬q ¬r
(p ∧ ¬q) ∨ ¬r

▲
r

EXAMPLE 10 (p ∨ ¬r) ∧ (¬p ∨ (q ∨ ¬r))

p q r

p ∨ ¬r ¬p ∨
(q ∨ ¬r) p ∨ ¬r
¬r r p ¬r
¬p ∨ (q ∨ ¬r) ¬r
q ¬r q ∨ ¬r
¬p ∨ (q ∨ ¬r) p q ∨ ¬r
p ∨ ¬r ¬p ∨
(q ∨ ¬r)
▲
 ∨¬

¬ ∨¬ ∧ ¬ ∨ ∨¬
¬

¬ ∨ ∨¬
∨¬
¬

p ∨ ¬r ∧ ¬p ∨ q ∨ ¬r

Exercises

g
g
r r
e h
a h

p q
m e
p

g
m r
b

p q
d r
s

e
a
b p
r

u
b b
 A B A B

A B
A B A

A B B
A B
A B

A B C

∗
A C B A C

A B
C B
A B C

A B A
C
A B A
C B
A B
C
A B
C A
A B
C
∗
(p ∧ ¬r) ∨ (¬q ∧ r) p q r

((¬p ∨ ¬r) ∧ ¬q) ∨ (¬p ∧ (q ∨ r)) p

q r
 Introduction

p∧q

DEFINITION 1

EXAMPLE 1
p ∨ ¬p p ∧ ¬p p ∨ ¬p
p ∧ ¬p

▲
Logical Equivalences

DEFINITION 2 p q p↔q
p≡q p q

≡ p≡q
p↔q ⇔
≡

p q

p ¬p p ∨ ¬p p ∧ ¬p
 ¬(p ∧ q) ≡ ¬p ∨ ¬q
¬(p ∨ q) ≡ ¬p ∧ ¬q

¬(p ∨ q) ¬p ∧ ¬q

EXAMPLE 2 ¬(p ∨ q) ¬p ∧ ¬q

¬(p ∨ q) ¬p ∧ ¬q
p q ¬(p ∨ q) ↔ (¬p ∧ ¬q)

▲
¬(p ∨ q) ¬p ∧ ¬q
p q p∨q ¬(p ∨ q) ¬p ¬q ¬p ∧ ¬q

EXAMPLE 3 p→q ¬p ∨ q

¬p ∨ q p→q

▲
¬p ∨ q
p→q
p q ¬p ¬p ∨ q p→q

p q r

p
q r

n n
 p ∨ (q ∧ r) (p ∨ q) ∧ (p ∨ r)

p q r q ∧r p ∨ (q ∧ r) p∨q p∨r (p ∨ q) ∧ (p ∨ r)

EXAMPLE 4 p ∨ (q ∧ r) (p ∨ q) ∧ (p ∨ r)

p ∨ (q ∧ r) (p ∨ q) ∧ (p ∨ r)

▲
p∧ ≡p
p∨ ≡p

p∨ ≡
p∧ ≡

p∨p ≡p
p∧p ≡p

¬(¬p) ≡ p

p∨q ≡ q ∨p
p∧q ≡ q ∧p

(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)

p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)

¬(p ∧ q) ≡ ¬p ∨ ¬q
¬(p ∨ q) ≡ ¬p ∧ ¬q

p ∨ (p ∧ q) ≡ p
p ∧ (p ∨ q) ≡ p

p ∨ ¬p ≡
p ∧ ¬p ≡
 p → q ≡ ¬p ∨ q
p ↔ q ≡ (p → q) ∧ (q → p)
p → q ≡ ¬q → ¬p
p ↔ q ≡ ¬p ↔ ¬q
p ∨ q ≡ ¬p → q
p ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q)
p ∧ q ≡ ¬(p → ¬q)
¬(p ↔ q) ≡ p ↔ ¬q
¬(p → q) ≡ p ∧ ¬q
(p → q) ∧ (p → r) ≡ p → (q ∧ r)
(p → r) ∧ (q → r) ≡ (p ∨ q) → r
(p → q) ∨ (p → r) ≡ p → (q ∨ r)
(p → r) ∨ (q → r) ≡ (p ∧ q) → r

p∨q ∨r
p q
p∨q r q r
p q ∨r p∧q∧r
p ∨ p ∨ · · · ∨ pn p ∧ p ∧ · · · ∧ pn
p , p , . . . , pn

¬(p ∨ p ∨ · · · ∨ pn ) ≡ (¬p ∧ ¬p ∧ · · · ∧ ¬pn )

¬(p ∧ p ∧ · · · ∧ pn ) ≡ (¬p ∨ ¬p ∨ · · · ∨ ¬pn ).

n n
j= pj p ∨ p ∨ · · · ∨ pn j= pj
p ∧ p ∧ · · · ∧ pn
n n n n
¬ j= pj ≡ j= ¬pj ¬ j= pj ≡ j= ¬pj

Using De Morgan’s Laws

¬(p ∨ q) ≡ ¬p ∧ ¬q
¬(p ∧ q) ≡
¬p ∨ ¬q
EXAMPLE 5

p q
p∧q
¬(p ∧ q) ¬p ∨ ¬q

r s
r ∨s
¬(r ∨ s) ¬r ∧ ¬s

▲
Constructing New Logical Equivalences

p q q r p r

EXAMPLE 6 ¬(p → q) p ∧ ¬q
 ¬(p → q)
p ∧ ¬q

¬(p → q) ≡ ¬(¬p ∨ q)
≡ ¬(¬p) ∧ ¬q
≡ p ∧ ¬q

▲
EXAMPLE 7 ¬(p ∨ (¬p ∧ q)) ¬p ∧ ¬q

¬(p ∨ (¬p ∧ q))

¬p ∧ ¬q

¬(p ∨ (¬p ∧ q)) ≡ ¬p ∧ ¬(¬p ∧ q)

≡ ¬p ∧ [¬(¬p) ∨ ¬q]
≡ ¬p ∧ (p ∨ ¬q)
≡ (¬p ∧ p) ∨ (¬p ∧ ¬q)
≡ ∨ (¬p ∧ ¬q) ¬p ∧ p ≡
≡ (¬p ∧ ¬q) ∨
≡ ¬p ∧ ¬q

¬(p ∨ (¬p ∧ q)) ¬p ∧ ¬q

▲
EXAMPLE 8 (p ∧ q) → (p ∨ q)

(p ∧ q) → (p ∨ q) ≡ ¬(p ∧ q) ∨ (p ∨ q)
≡ (¬p ∨ ¬q) ∨ (p ∨ q)
≡ (¬p ∨ p) ∨ (¬q ∨ q)

≡ ∨

≡
▲

Propositional Satisfiability
EXAMPLE 9 (p ∨ ¬q) ∧ (q ∨ ¬r) ∧
(r ∨ ¬p) (p ∨ q ∨ r) ∧ (¬p ∨ ¬q ∨ ¬r) (p ∨ ¬q) ∧ (q ∨ ¬r) ∧ (r ∨ ¬p) ∧
(p ∨ q ∨ r) ∧ (¬p ∨ ¬q ∨ ¬r)

(p ∨ ¬q) ∧ (q ∨ ¬r) ∧ (r ∨ ¬p) p q r

p q r
(p ∨ q ∨ r) ∧ (¬p ∨ ¬q ∨ ¬r) p q r
(p ∨ q ∨ r) ∧ (¬p ∨ ¬q ∨ ¬r)
p q r
(p ∨ ¬q) ∧ (q ∨ ¬r) ∧ (r ∨ ¬p) ∧ (p ∨ q ∨ r) ∧ (¬p ∨ ¬q ∨ ¬r)
(p ∨ ¬q) ∧ (q ∨ ¬r) ∧ (r ∨ ¬p) (p ∨ q ∨ r) ∧ (¬p ∨ ¬q ∨ ¬r)

p q r (p ∨ ¬q) ∧ (q ∨ ¬r) ∧ (r ∨ ¬p) ∧

(p ∨ q ∨ r) ∧ (¬p ∨ ¬q ∨ ¬r)

▲
 2 9 4
5 1
4
4 2
6 7
5
7 3 5
1 9
6

Applications of Satisfiability

SUDOKU × ×

, ,...,

× ×
n ×n n n ×n
n n×n
 p(i, j, n)
n i j × × =
i j n
p( , , ) p( , j, )
j = , ,...,

p(i, j, n) i j n

p(i, j, n) i
j n

p(i, j, n)
i= n= j =

p(i, j, n)
j = n= i=

p( r + i, s + j, n)
r= s= n= i= j =

n n i j n=n p(i, j, n) →
¬p(i, j, n )

i n j= p(i, j, n)
i n
n n= j= p(i, j, n).
n= j= p(i, j, n)
i= n= j= p(i, j, n)
×

p(i, j, n)
 Solving Satisfiability Problems

= , ,

Exercises

(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
p∧ ≡p p∨ ≡p
p∧ ≡ p∨ ≡ p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
p∨p ≡p p∧p ≡p
¬(¬p) p ¬(p ∧ q) ≡ ¬p ∨ ¬q

p∨q ≡q ∨p p∧q ≡q ∧p

(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
 (p → q) ∧ (q → r) → (p → r)

(p ∨ q) ∧ (¬p ∨ r) → (q ∨ r)
(p → q) → r p → (q → r)

(p ∧ q) → r (p → r) ∧ (q → r)

(p → q) → (r → s) (p → r) →
(q → s)

(p ∧ q) → p p → (p ∨ q) ∨ ∧ ¬
¬p → (p → q) (p ∧ q) → (p → q) ∨ ∧ ∧ ∨
¬(p → q) → p ¬(p → q) → ¬q s s∗

p ∨ ¬q p ∧ (q ∨ (r ∧ ))
[¬p ∧ (p ∨ q)] → q (p ∧ ¬q) ∨ (q ∧ )
[(p → q) ∧ (q → r)] → (p → r)
[p ∧ (p → q)] → q
[(p ∨ q) ∧ (p → r) ∧ (q → r)] → r p ∧ ¬q ∧ ¬r (p ∧ q ∧ r) ∨ s
(p ∨ ) ∧ (q ∨ )
s∗ = s s
(s ∗ )∗ = s s

p ∨ (p ∧ q) ≡ p p ∧ (p ∨ q) ≡ p
(¬p ∧ (p → q)) → ¬q
∗∗
(¬q ∧ (p → q)) → ¬p
∧, ∨ ¬

p q r p q
r

p↔q (p ∧ q) ∨ (¬p ∧ ¬q) p, q r p, q

r
¬(p ↔ q) p ↔ ¬q

p→q ¬q → ¬p
¬p ↔ q p ↔ ¬q
¬(p ⊕ q) p↔q n
¬(p ↔ q) ¬p ↔ q

(p → q) ∧ (p → r) p → (q ∧ r)

(p → r) ∧ (q → r) (p ∨ q) → r

(p → q) ∨ (p → r) p → (q ∨ r)

(p → r) ∨ (q → r) (p ∧ q) → r

¬p → (q → r) q → (p ∨ r)
¬ ∧ ∨
p↔q (p → q) ∧ (q → p)

p↔q ¬p ↔ ¬q
∗ ¬ ∧

p∨q
¬(¬p ∧ ¬q
∗ ¬ ∨ p ∨ ¬q ¬p ∨ q q ∨ r
q ∨ ¬r ¬q ∨ ¬r
p q r
p p ∨ ¬q ∨ s ¬p ∨
q p q ¬r ∨ s ¬p ∨ ¬r ∨ ¬s ¬p ∨ q ∨ ¬s q ∨ r ∨ ¬s
p q q ∨ ¬r ∨ ¬s ¬p ∨ ¬q ∨ ¬s p ∨ r ∨ s p ∨ r ∨¬s
p q
p|q p↓q p q r s
| ↓

p|q ¬(p ∧ q)

p↓q ¬(p ∨ q) (p ∨ ¬q) ∧ (¬p ∨ q) ∧ (¬p ∨ ¬q)

{↓} (p → q) ∧ (p → ¬q) ∧ (¬p → q) ∧ (¬p → ¬q)
(p ↔ q) ∧ (¬p ↔ q)
p↓p ¬p
(p ↓ q) ↓ (p ↓ q)
p∨q (p ∨ q ∨ ¬r) ∧ (p ∨ ¬q ∨ ¬s) ∧ (p ∨ ¬r ∨ ¬s) ∧
(¬p ∨ ¬q ∨ ¬s) ∧ (p ∨ q ∨ ¬s)
{↓} (¬p ∨ ¬q ∨ r) ∧ (¬p ∨ q ∨ ¬s) ∧ (p ∨ ¬q ∨
¬s) ∧ (¬p ∨ ¬r ∨ ¬s) ∧ (p ∨ q ∨ ¬r) ∧ (p ∨
∗ ¬r ∨ ¬s)
p→q ↓ (p ∨ q ∨ r) ∧ (p ∨ ¬q ∨ ¬s) ∧ (q ∨ ¬r ∨ s) ∧
{|} (¬p ∨ r ∨ s) ∧ (¬p ∨ q ∨ ¬s) ∧ (p ∨ ¬q ∨ ¬r) ∧
(¬p ∨ ¬q ∨ s) ∧ (¬p ∨ ¬r ∨ ¬s)
p|q q|p ×
p | (q | r) (p | q) | r
|
∗
p ×
q
p q r
p q q r
p r ×
∗

× ×

Introduction