Rewrite predicate formulas in propositional calculus

Question

Suppose that the universe of discourse of the atomic formula P(x,y) is the set {0,1,2,3,4,5}. Write each of the following propositions using dis-junctions, conjunctions and only one negation:

1) ∃x P(x,0)

---

2) ∀y P(1,y)

---

3) ∀y¬P(2,y)

Answer 1

HINT. Existential quantification over finite domains (say, of size $n$) is equivalent to a $n$ term disjunction over all elements. So from your example, if the universe of discourse was $\{0,1\}$, then the solution to question 1) would be $P(0,0)\lor P(1,0)$.

Similarly, universal quantification over finite domains (say, of size $n$) is equivalent to a $n$ term conjunction over all elements, so the solution to question 2) would be $P(1,0)\land P(1,1)$.

For the negation in 3) use De Morgan laws, i.e. $\neg(A\lor B)$ is equivalent to $(\neg A\land \neg B)$. This way you can convert an $n$ conjunction of negated atomic formulae to a negated $n$ disjunction.

Thanks Mauro ALLEGRANZA for pointing out an obvious typo.