-1
$\begingroup$

Show that

$\forall x(C \land D) \equiv (\forall x\ C) \lor D$

where $C$ may have free occurrences of $x$, but $D$ does not have a free occurrence of $x$.

Prove this using only propositional logic inference rules and the quantifier introduction and elimination rules (don't use any of the logical identities).

  • 2
    Did you want to write $\land$ on both sides (or $\lor$ on both sides) of your equivalence?2012-10-04

1 Answers 1

1

It is evidently enough to show that (i) from the assumption $\forall x(\varphi(x) \land D)$ you can derive $(\forall x\varphi(x) \land D)$ and (ii) from the assumption $(\forall x\varphi(x) \land D)$ you can derive $\forall x(\varphi(x) \land D)$ (where $D$ doesn't contain $x$ free).

For (i): suppose $\forall x(\varphi(x) \land D)$; instantiate to get $(\varphi(a) \land D)$; use $\land$-elimination to derive $\varphi(a)$ and $D$ separately; use quantifier introduction on the first of those (why is that legitimate)?; and then use $\land$-introduction to get the desired conclusion.

You can now do (ii) similarly.

  • 0
    Thanks $f$or the assistance!2012-10-04