Proof using formal deduction, how to introduce a conclusion?

Question

Prove that $(E \land G) \lor ( G \rightarrow F )$ is formally deducible from $(E \lor F)$

where:

• "$\land$" means AND
• "$\lor$" means OR
• "$\rightarrow$" denotes an implication

This is what I have so far:

$E \lor F \vdash E \lor F$

$E \lor F , E, F, G \vdash F$

$E \lor F , E, F \vdash (G\rightarrow F)$

But I have no idea how I would get $E \land G$ since neither of them are given by the premise.

Answer 1

Law of Complements: either $G$ or not $G$.

$E\vee F \vdash (E\wedge\neg F) \vee F$

$(E\wedge\neg F)\;\wedge\; (G\vee\neg G)\;\vdash\; (E\wedge \neg F\wedge G) \;\vee\; (E\wedge \neg F\wedge \neg G)$

Now $(E\wedge \neg F\wedge G)\vdash E\wedge G$ and $(E\wedge\neg F\wedge \neg G)\vdash \neg G$ and $F\vdash G\to F$

So $(E\vee F)\;\vdash\; (E\wedge G)\;\vee\; (G\to F)$