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
- Mendelson Elliott: "Theory and Problems of Boolean Algebra and Switching Circuits", McGraw-Hill Book Company, 1982
