Prove: $(p \lor q) \land (\lnot p \lor \lnot q) \Rightarrow (p \land \lnot q) \lor (\lnot p \land q)$ using natural deduction. I am trying to prove 
$$    (p \lor q) \land (\lnot p \lor \lnot q) \Rightarrow (p \land \lnot q) \lor (\lnot p \land q) $$
using Natural deduction.
But I am unable to get beyond the implication reduction and the conjuction elimination on the left.
Can someone please suggest something to finish the proof.
 A: You'd need a rule for a proof step based on an or, something like "if we can get from  $x$ to $z$, and we can get from $y$ to $z$, then we can conclude $z$ is a consequence of $x \lor y$. Also needed are rules such as: from $u$ we can derive $u \lor v$ for whatever $v$ we want.
case 1) assume $p$. Bring down next $ \lnot p \lor \lnot q$, and use some rule to arrive at $\lnot q$. Now combine the case assumption $p$ with this and get to $p \land \lnot q$, and finally use the rule about placing any other statement with this in an or to arrive at the conclusion for case 1 of $(p \land \lnot q) \lor (\lnot p \land q)$
case 2) assume $q$. This time bring down $\lnot p \lor \lnot q$ and after a few steps get again the same conclusion $(p \land \lnot q) \lor (\lnot p \land q)$ as case 1 produced.
Now looking at the two deductions of the same final $(p \land \lnot q) \lor (\lnot p \land q)$, one ("case 1") from $p$ and the other ("case 2") from $q$, you can put these two together and say you have shown that $(p \lor q) \land (\lnot p \land \lnot q)$ implies $(p \land \lnot q) \lor (\lnot p \land q).$
There are some details left out, which need to be filled in by using whatever deduction rules your version of "natural deduction" might be. But I believe the above is a general framework for the proof. Some versions use numbered lines in the proof, and refer to previous line numbers and rules used to fully justify the overall proof.
A: $\def\fitch#1#2{~~\begin{array}{|l}#1\\\hline#2\end{array}}$To prove $( (p \lor q) \land (\lnot p \lor \lnot q) )\to( (p \land \lnot q) \lor (\lnot p \land q) )$ using natural deduction, you must complete it by introducing that conditional.   Naturally this requires a conditional (sub)proof.   Thus you need to assume the antecedent aiming to derive the consequent.
$$\fitch{}{\fitch{\textsf{Assumption}}{\vdots\\\textsf{Consequent Derived}}\\\textsf{Conditional Introduction}}$$
The antecedent is a conjunction of disjunctions.   You shall need to eliminate these.   Eliminating each disjunction takes the form of a proof by cases.   You are going to be nesting these.
$$\fitch{}{\fitch{\textsf{Assumption}}{\textsf{Conjunction Elimination}\\\textsf{Conjunction Elimination}\\\fitch{\textsf{Assumption}}{\textsf{Reiteration}\\\fitch{\textsf{Assumption}}{\vdots\\\textsf{Consequent Derived}}\\\fitch{\textsf{Assumption}}{\vdots\\\textsf{Consequent Derived}}\\\textsf{Disjunction Elimination}}\\\fitch{\textsf{Assumption}}{\textsf{Reiteration}\\\fitch{\textsf{Assumption}}{\vdots\\\textsf{Consequent Derived}}\\\fitch{\textsf{Assumption}}{\vdots\\\textsf{Consequent Derived}}\\\textsf{Disjunction Elimination}}\\\textsf{Disjunction Elimination}}\\\textsf{Conditional Introduction}}$$
The consequent is a disjunction of two conjunctions.   You are going to need to introduce these in each branch of the nested proof by cases.   However, it looks clear that along the way you will encounter contradictions, but these may be exploded to derive the consequent.
$$\fitch{}{\fitch{\textsf{Assumption}}{\textsf{Conjunction Elimination}\\\textsf{Conjunction Elimination}\\\fitch{\textsf{Assumption}}{\textsf{Reiteration}\\\fitch{\textsf{Assumption}}{\textsf{Negation Elimination}\\\textsf{Explosion}}\\\fitch{\textsf{Assumption}}{\textsf{Conjunction Introduction}\\\textsf{Disjunction Introduction}}\\\textsf{Disjunction Elimination}}\\\fitch{\textsf{Assumption}}{\textsf{Reiteration}\\\fitch{\textsf{Assumption}}{\textsf{Conjunction Introduction}\\\textsf{Disjunction Introduction}}\\\fitch{\textsf{Assumption}}{\textsf{Negation Elimination}\\\textsf{Explosion}}\\\textsf{Disjunction Elimination}}\\\textsf{Disjunction Elimination}}\\\textsf{Conditional Introduction}}$$
