Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
4  
I take it this is some exercise you have copied out of a book or assignment. Could you cite the source, please? –  Gerry Myerson Oct 3 '12 at 23:52
    
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. –  Rick Decker Oct 4 '12 at 0:16
    
... To aid in formatting your questions in a nicely readable LaTeX format, you can look at this page. –  Rick Decker Oct 4 '12 at 0:21
1  
Why the edit? $\equiv$ and $\Longleftrightarrow$ are not the same thing. –  Rod Carvalho Oct 4 '12 at 0:28
2  
Did you want to write $\land$ on both sides (or $\lor$ on both sides) of your equivalence? –  Martin Sleziak Oct 4 '12 at 6:56
show 4 more comments

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
    
Thanks for the assistance! –  user43539 Oct 4 '12 at 14:26
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.