Sur l'efficacité des systèmes de formes normales de fonctions Booléennes

Dans cet article, nous comparons différentes représentations des fonctions Booléennes à l'aide de systèmes de formes normales. Nous étendons les travaux de [3] sur l'étude asymptotique de l'efficacité des représentations produites par des systèmes de formes normales (Normal Form Systems–NFSs). Nous identifions certaines propriétés, comme l'associativité, la linéarité, la quasi-linéarité et la symétrie, qui nous permettent de comparer l'efficacité des NFSs correspondantes. Nous illustrons ces résultats en comparant des NFSs usuelles telles que la DNF, CNF, les représentations polynomiales, ainsi que la forme normale médiane (MNF) et celle dite de Sheffer (SNF). Nous obtenons en particulier que les NFSs générés par un seul connecteur sont polynomialement aussi efficace que ceux générés par plusieurs. La MNF, quand à elle, est aussi efficace que n'importe quel autre système.