0
$\begingroup$

So I have to "Use equivalences to rewrite the propositions into a logically equivalent proposition in which quantifiers only appear directly in front of predicate symbols (only one quantifier can appear directly in front of the predicate symbol". Here is the problem: $(\forall x)(P(x) \land (Q(b) \lor R(x))$. I have to solve several problems like this one, but I just don't understand where to start. I know we can't distribute a universal quantifier over disjunction, it can only distribute over injunction. So, I would assume that I can use the logical identities like the negation laws and De Morgan's Laws, is that correct? If someone could just drop some hints or point me in the right way, I would greatly appreciate it.

$\endgroup$
3
  • $\begingroup$ "injunction" ??? Maybe conjunction. $\endgroup$ Sep 8 '17 at 5:56
  • $\begingroup$ You can see here (page 3 and 5) the laws for quantifiers; but you have to take care of free variables... $\endgroup$ Sep 8 '17 at 6:00
  • $\begingroup$ In a nutshell: $\forall$ distribute over $\land$, i.e. $\forall x \ (Px \land Qx) \equiv (\forall x \ Px \land \forall x \ Qx)$ [$\forall$ can be seen as an infinite conjunction] while $\exists$ distribute over $\lor$, i.e. $\exists x \ (Px \lor Qx) \equiv (\exists x \ Px \lor \exists x \ Qx)$ [$\exists$ can be seen as an infinite disjunction]. $\endgroup$ Sep 8 '17 at 6:07
2
$\begingroup$

The baisc rules are the following.

$∀$ distribute over $∧$, i.e.

$∀x \ (Px ∧ Qx) ≡ (∀x Px ∧ ∀x Qx)$,

and $∃$ distribute over $∨$, i.e.

$∃x \ (Px ∨ Qx) ≡ (∃x Px ∨ ∃x Qx)$.

In addition, we have:

$∀x \ (Px ∨ A) ≡ (∀x Px ∨ A)$, only if $x$ is not free in $A$,

and the same restriction hold for $∃$ with $∧$.

In conclusion:

$(∀x) \ [P(x) ∧ (Q(b) ∨ R(x)] ≡ (∀x)P(x) ∧ (Q(b) ∨ (∀x)R(x))$,

because we can "safely" distribute $∀$ over $∧$ and in this case we can also distribute it over $∨$, because $x$ is not free in $Q(b)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.