The complexity of Boolean functions in the Reed–Muller polynomials class

Abstract

This paper considers the problem of transforametion of Boolean functions into canonical polarized polynomials (Reed–Muller polynomials). Two Shannon functions are introduced to estimate the complexity of Boolean functions in the polynomials class under consideration. We propose three Boolean functions of n variables whose complexity (in terms of the number of terms) coincides with value. We investigate the properties of functions and propose their schematic realization on elements AND, XOR, and NAND.