The following lemma is sometimes very helpful in proving implications in mathematics. It uses the fact that the implication $x\Rightarrow y$ can be represented by the disjunction $\neg x\vee y$.

Lemma: Implication as a Disjunction

Any implication $x\Rightarrow y$ is equivalent to the disjunction of the negated antecedent $\neg x$ and the consequent $y$, formally $$(x\Rightarrow y)\Longleftrightarrow (\neg x \vee y).$$

Example

This lemma is a little bit surprising because, in natural language, it is not intuitive. Consider for instance the following propositions:

$x=$"Socrates is human."

$y=$"Socrates is mortal."

Then the following compound propositions are equivalent:

$x\Rightarrow y$: "If Socrates is human, then Socrates is mortal."

$\neg x \vee y$: "Socrates is not human, or Socrates is mortal."

Proofs: 1

Proofs: 1 2 3


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

Github:
bookofproofs


References

Bibliography

  1. Mendelson Elliott: "Theory and Problems of Boolean Algebra and Switching Circuits", McGraw-Hill Book Company, 1982
  2. Kohar, Richard: "Basic Discrete Mathematics, Logic, Set Theory & Probability", World Scientific, 2016