Now it’s time to review another frequently used property in propositional logic, namely the proofs of DeMorgan’s laws of Distribution for conjunction and disjunction. The use of these laws is common in set theory and, by extension, permeates all of mathematics: from probability theory, topology, and even has a presence in electronics and programming. As usual, we will break down the proofs of these laws using the deduction techniques we have obtained so far.

DeMorgan’s Laws

DeMorgan’s laws are a set of equivalences that formalize the distribution of negations with conjunction and disjunction. Formally, they are expressed through the equivalences:

\neg(\alpha \wedge \beta) \dashv \vdash (\neg\alpha \vee \neg \beta)

\neg(\alpha \vee \beta) \dashv \vdash (\neg\alpha \wedge \neg \beta)

These proven equivalences can be obtained without the need to make a proof like we have done so far, since we can rely on the definitions that relate conjunctions with disjunctions and a bit of play with the double negation equivalence and substitutions. From the definition of conjunction, it follows that:

(A \wedge B):= \neg(\neg A \vee \neg B)

Applying a negation to both sides of this expression, we have

\neg(A \wedge B):= \neg\neg(\neg A \vee \neg B)

Then, by the double negation equivalence, we get

\neg(A \wedge B)\dashv \vdash (\neg A \vee \neg B)

Finally, replacing A=\alpha and B=\beta, we obtain DeMorgan’s first equivalence

\boxed{\neg(\alpha \wedge \beta) \dashv \vdash (\neg\alpha \vee \neg \beta)}

To obtain the second, we can continue playing with the expression we had before making the replacement by adding a negation to both sides again, obtaining

\neg\neg(A \wedge B)\dashv \vdash \neg(\neg A \vee \neg B)

And then, by double negation, we get

\neg(\neg A \vee \neg B) \dashv \vdash (A \wedge B)

If in this last expression we replace A=\neg\alpha and B=\neg\beta, we will get

\neg(\neg \neg\alpha \vee \neg \neg\beta) \dashv \vdash (\neg\alpha \wedge \neg\beta)

Which, due to the double negation equivalence, will lead to DeMorgan’s second equivalence

\boxed{\neg( \alpha \vee \beta) \dashv \vdash (\neg\alpha \wedge \neg\beta)}

In addition, in a completely analogous way, we can obtain some additional forms, which are just variations of the ones we just reviewed

\neg(\neg\alpha \wedge \beta) \dashv \vdash (\alpha \vee \neg \beta)

\neg(\neg\alpha \vee \beta) \dashv \vdash (\alpha \wedge \neg \beta)

\neg(\alpha \wedge \neg\beta) \dashv \vdash (\neg\alpha \vee \beta)

\neg(\alpha \vee \neg\beta) \dashv \vdash (\neg\alpha \wedge \beta)

Distributivity Rules Between Conjunction and Disjunction

As the name suggests, these rules allow us to distribute the sets and disjunctions within an expression. These laws are summarized in the following two equivalences:

As we have seen so far, although this is a known result, its proof is not trivial at all. Although, to complete this proof, it must be reasoned in both directions, this time I will only give the proof in one direction; the proof in the reverse direction will be left as an exercise for the reader.

∧ – Distributivity

To prove that \{(\alpha \wedge(\beta \vee\gamma))\}\vdash((\alpha \wedge \beta)\vee(\alpha \wedge \gamma)) occurs, we have the following reasoning.

With this, it is proven that \{(\alpha \wedge(\beta \vee\gamma))\}\vdash((\alpha \wedge \beta)\vee(\alpha \wedge \gamma)). Now it’s your turn to test what you’ve learned and venture to prove on your own that \{((\alpha \wedge \beta)\vee(\alpha \wedge \gamma))\}\vdash (\alpha \wedge(\beta \vee\gamma)).

∨ – Distributivity

The proof of \{(\alpha \vee(\beta \wedge\gamma))\}\vdash((\alpha \vee \beta)\wedge(\alpha \vee \gamma)) is obtained from the following reasoning:

This is half of the proof; now, the reverse proof is missing, but that is left as an exercise for the reader :3

Final Considerations

With this review of the proofs of De Morgan’s laws of distribution for conjunction and disjunction, we can conclude our study of deduction techniques in propositional logic and how they converge in the proof of classical logic laws, or at least the most important ones.

It is important to complete all the proposed proofs to reinforce knowledge of these techniques. To make it a little less complicated, it is very convenient to compare the proofs to find similarities, as it is possible that the strategy that worked in one proof will work with some variations to achieve another.

One last thing worth noting is the order I chose to develop these proofs. You should notice that each proof used the results of some of the previous proofs. I chose this order because I personally found it easier this way. A good exercise to improve your skills in these things is to ask yourself, “Can I construct these proofs in a different order following this same methodology?” I highly recommend that you try to obtain these proofs in a different order and use each proof to obtain the next ones because, even if you don’t manage to do it, the practice that arises from the attempt will give you a better understanding of the proofs and the methods used in logic.