-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).

  • 4
    I take it this is some exercise you have copied out of a book or assignment. Could you cite the source, please?2012-10-03
  • 0
    Welcome to this site! Since you're new here, you might not know what we expect. Many people have problems with the imperative: your question could be read as a command "Do this proof." Although this site is specifically for Q/A on matters mathematical, you'll have a better chance of getting an answer if you told us what you've tried. It's okay if you haven't tried anything, but let us know, so we can at least judge the level to which we can point our answers.2012-10-04
  • 0
    ... To aid in formatting your questions in a nicely readable LaTeX format, you can look at [this page](http://meta.math.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference).2012-10-04
  • 1
    Why the edit? $\equiv$ and $\Longleftrightarrow$ are not the same thing.2012-10-04
  • 0
    Why the close vote as not a real question ?2012-10-04
  • 0
    @Rod. For some authors it is, just as some authors make a distinction between $\Longleftrightarrow$ and $\longleftrightarrow$. Go figure. You're right, though, I should have made the reason for my choice explicit. Feel free to change it---I'm a notational agnostic.2012-10-04
  • 0
    @RickDecker - In logic class we used $\equiv$ for logic statements and $\iff$ for verbal statements. it seems that $\equiv$ should be used2012-10-04
  • 0
    In response to overwhelming demand, I've suggested the appropriate edit. If it's not accepted, it's up to Rod or Belgi to change it.2012-10-04
  • 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 for the assistance!2012-10-04