De Morgan Functions and Free De Morgan Algebras

Abstract

It is commonly known that the free Boolean algebra on n free generators is isomorphic to the Boolean algebra of Boolean functions of n variables. The free bounded distributive lattice on n free generators is isomorphic to the bounded lattice of monotone Boolean functions of n variables. In this paper, we introduce the concept of De Morgan function and prove that the free De Morgan algebra on n free generators is isomorphic to the De Morgan algebra of De Morgan functions of n variables. This is a solution of the problem suggested by B. I. Plotkin.

Keywords

• Antichain
• De Morgan function
• free De Morgan algebra
• monotone Boolean function
• disjunctive (conjunctive) normal form of De Morgan function