# Proof

(related to Lemma: Negation of an Implication)

### Context

• Let $x,y$ be two propositions.
• We want to show that $\neg (x\Rightarrow y)\Longleftrightarrow (x \wedge \neg y).$

### Hypothesis

• Take the negated implication $\neg(x\Rightarrow y)$.

### Implications

$$\models(x)$$ $$\models(y)$$ $$\models(x \Rightarrow y)$$ $$\models\neg(x \Rightarrow y)$$
$$1$$ $$1$$ $$1$$ $$0$$
$$0$$ $$1$$ $$1$$ $$0$$
$$1$$ $$0$$ $$0$$ $$1$$
$$0$$ $$0$$ $$1$$ $$0$$
• Based on the truth tables of the negation and conjunction, the truth table of $(x\wedge \neg y)$ is given by

$$\models(x)$$| $$\models(y)$$| $$\models(\neg y)$$| $$\models(x \wedge \neg y)$$ $$1$$| $$1$$| $$0$$| $$0$$ $$0$$| $$1$$| $$0$$| $$0$$ $$1$$| $$0$$| $$1$$| $$1$$ $$0$$| $$0$$| $$1$$| $$0$$

### Conclusion

• Since the outcomes (columns to the right) of both truth tables are equal, we have shown the equivalence $\neg (x\Rightarrow y)\Longleftrightarrow (x \wedge \neg y).$

Thank you to the contributors under CC BY-SA 4.0!

Github:

### References

#### Bibliography

1. Mendelson Elliott: "Theory and Problems of Boolean Algebra and Switching Circuits", McGraw-Hill Book Company, 1982