On connected Boolean functions

A Boolean function is called (co-)connected if the subgraph of the Boolean hypercube induced by its (false) true points is connected; it is called str ongly connected if it is both connected and co-connected, The concept of (c o-)geodetic Boolean functions is defined in a similar way by requiring that at least one of the shortest paths connecting two (false) true points shou ld consist only of (false) true points. This concept is further strengthene d to that of convexity where every shortest path connecting two points of t he same kind should consist of points of the same kind. This paper studies the relationships between these properties and the DNF representations of t he associated Boolean functions, (C) 1999 Elsevier Science B.V. All rights reserved.