◀ ▲ ▶Branches / Logic / Proof

Proof

(related to Corollary: All Boolean Functions Can Be Built Using Conjunction, Disjunction, and Negation)

• The operations conjunction "$\wedge$", the disjunction "$\vee$", and the negation "$\neg$" are the only operations used to form the conjunctive and disjunctive canonical normal forms.
• From the construction of conjunctive and disjunctive canonical normal forms, it follows that they can be constructed for any given truth table of a proposition $\phi$ based on its prime propositions $p_1,\ldots,p_n,$ which by definition represent only Boolean variables or constants.
• Since $\phi$ is an arbitrary proposition, it follows that an arbitrary Boolean function can be build using "$\wedge$", "$\vee$", and "$\neg$" as the only connectives of Boolean variables or constants.
  ∎

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
2. Hoffmann, Dirk: "Theoretische Informatik, 3. Auflage", Hanser, 2015