Variations on extending partially defined Boolean functions with missing bits

In this paper we consider four possible definitions for extending a partially defined Boolean function in which the input contains some missing bits. We show somewhat surprisingly that, for many general and frequently used families of function classes, three of these notions of an extension are mathematically equivalent, though such an equivalence does not hold universally, as demonstrated by several examples.

Authors

• Endre Boros
• Toshihide Ibaraki
• Kazuhisa Makino

Keywords

• Logical analysis of data
• Boolean functions
• Extensions
• Partially defined Boolean functions
• Missing bits