Ì Exam ple 8.4.11: Prove that ( )( ) ( , ) ( )( ) ( , )
∨ ℑ
→ ℑ ℑ
y
y
x
y
P x y
P x y is
logically valid.
Solu tion
1.
( ) ( ) ( , )
∨ ℑ
x
y P x y
P
2.
( ) ( , )
ℑ y P a y
US, (1)
3.
P a y
( , )
ES, (2)
4.
( ) ( , )
ℑ y P a y
(3), EG
5.
( ) ( ) ( , )
ℑ ℑ
x
y P x y
(4), EG
Ì Exam ple 8.4.12: Show that ¬ P a b
( , ) follows logically from
( )( )( ( , )
( , ))
∨ ∨
→
x
y P x y
W x y and ¬ W a b
( , ).
Solu tion
1.
( ) ( ) ( ( , )
( , ))
∨ ∨
→
x
y
P x y
W x y
P
2.
( ) ( ( , )
( , ))
∨
→
x
P x b
W x b
(1), US
3.
P a b
W a b
( , )
( , )
→
(2), US
4.
¬
∨
P a b W a b
( , )
( , )
P Q
P Q
→ ⇔ ¬ ∨
5.
¬ W a b
( , )
P
6.
¬ P a b
( , )
T
P P Q Q
, ( ),
,
5 ¬
∨ ⇒
8.5 NORMAL FORMS
Let us show how to find the formula given the Truth Table.
P
Q
R
f (P, Q, R)
T
T
T
T












4 Truth val ues are
“True”
T
T
F
F
T
F
T
T
T
F
F
T
F
T
T
F
F
T
F
F
F
F
T
T
F
F
F
F
Prop o si tions and Pred i cates
289