Applied Logic for Computer Science Assignment 1

Department of Computer Science
CS 2209A — Applied Logic for Computer Science
Assignment 1

1. For the following proposition, give the unique readability tree and the truth table derived
from that tree. What type of statement (tautology, contradiction, satisfiable) is it? Why?
??
(p → q) → p
?
→ p
?
2. Show the following logical equivalence using the logical identities and tautologies such as the
law of the excluded middle.
??
(p ∧ q) ∨ (p ∧ s)
?
∨
?
(r ∧ q) ∨ (r ∧ s)
??
≡
?
(p ∨ r) ∧ (q ∨ s)
?
3. Convert the following proposition to Conjunctive Normal Form. Show the steps required to
get your answer.
?
(p ↔ q) → (p ∧ r)
?
4. Show the following using natural deduction.
n
(p → q)
o
`
?
(r ∨ p) → (r ∨ q)
?
5. With the clauses given by Γ show Γ ` ¬r using resolution.
Γ = n
(p ∨ ¬q ∨ ¬r),(¬p ∨ s),(q ∨ ¬r ∨ t),(¬r ∨ ¬u ∨ t),(p ∨ s ∨ ¬r ∨ t), ¬s, q, u,(¬u ∨ ¬t)
o
6. Show a bottom up derivation of Γ ` h given the definite clauses (written as head ← body) in
set Γ.
Γ =



h ← f ∧ g
g ← a ∧ c
d
e ← c
a ← d
f ← d ∧ e ∧ b
b ← e
c ← a



7. Show a top down derivation of Γ ` h given the definite clauses (written as head ← body) in
set Γ.
Γ =



h ← f ∧ g
g ← a ∧ c
d
e ← c
a ← d
f ← d ∧ e ∧ b
b ← e
c ← a



6. Show a bottom up derivation of Γ ` h given the definite clauses (written as head ← body) in
set Γ.
Γ =



h ← f ∧ g
g ← a ∧ c
d
e ← c
a ← d
f ← d ∧ e ∧ b
b ← e
c ← a



7. Show a top down derivation of Γ ` h given the definite clauses (written as head ← body) in
set Γ.
Γ =



h ← f ∧ g
g ← a ∧ c
d
e ← c
a ← d
f ← d ∧ e ∧ b
b ← e
c ← a



6. Show a bottom up derivation of Γ ` h given the definite clauses (written as head ← body) in
set Γ.
Γ =



h ← f ∧ g
g ← a ∧ c
d
e ← c
a ← d
f ← d ∧ e ∧ b
b ← e
c ← a



7. Show a top down derivation of Γ ` h given the definite clauses (written as head ← body) in
set Γ.
Γ =



h ← f ∧ g
g ← a ∧ c
d
e ← c
a ← d
f ← d ∧ e ∧ b
b ← e
c ← a


