Foundations of Computer Science
1. Given the wff W = ∃x p(x) → ∀x p(x). Find all possible interpretations of W over the domain D = {a, b}.
Also give the truth value of W over each of the interpretations.
2. Find a model for each of the following wffs.
a. ∃x (p(x) → q(x)) ^ ∀x ¬ p(x)
b. ∃x ∀y p(x, y) ^ ∃x ∀y ¬ p(x, y)
c. ∃x p(x) ^ ∃x q(x) → ∃x (p(x) ^ q(x))
3. Find a countermodel for each of the following wffs.
a. ∃x p(x) ^ ∃x q(x) → ∃x (p(x) ^ q(x))
b. ∃x ∃y p(x, y) → ∃x ∀y p(x, y)
c. ∀x p(x, x) → ∃x ∀y p(x, y)
4. Given the wff W = ∀x ∀y (p(x) → p(y)). Find all possible interpretations of W over the domain D = {a,
b}. Also give the truth value of W over each of the interpretations.
SAMPLE ASSIGNMENT
