Proof
(related to Lemma: Implication as a Disjunction)
Context
- Let x,y be two propositions.
- We want to show that (x\Rightarrow y)\Longleftrightarrow (\neg x \vee y).
Hypothesis
- We are given the implication x\Rightarrow y.
Implications
\models(x) |
\models(y) |
\models(x \Rightarrow y) |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
- Based on the truth tables of the negation and disjunction, the truth table of (\neg x\vee y) is given by
\models(x)| \models(y)| \models(\neg x) | \models(\neg x \vee y)
1| 1| 0| 1
0| 1| 1| 1
1| 0| 0| 0
0| 0| 1| 1
Conclusion
- Since the outcomes (columns to the right) of both truth tables are equal, we have shown the equivalence (x\Rightarrow y)\Longleftrightarrow (\neg x \vee 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