Mathematics

Minimization of representations of the logical function in Schaeffer and Pierce bases

V. V. Menshikh, V. A. Nikitenko

Voronezh Institute of the Ministry of Internal Affairs of Russia, Voronezh, Russian Federation

Abstract: The paper studies the representation of arbitrary logical functions in Schaeffer and Pierce bases. For this purpose, recurrent dependencies of the representation of disjunctive and conjunctive monomials in these bases were initially established. Then generalizations were made to the arbitrary logical formulas presented in the form of disjunctive and conjunctive normal forms. Estimates were obtained for the number of operations in logical formulas during the transition to the Schaeffer and Pierce bases.

Keywords: disjunctive monomial, conjunctive monomial, Schaeffer's basis, Pierce's basis, Boolean variable, Boolean function.

UDC: 510.63

Received: 18.07.2022

DOI: 10.14529/mmph220403