### Abstract

Let F_{1}, F_{2}…, F_{m} be a set of Boolean functions of the form F_{1} = ^{x E X_{1}}, where ^ denotes conjuction and each X_{1}, is a subset of a set X of n Boolean variables. We study the size of monotone Boolean networks for computing such sets of functions. We exhibit anomalous sets of conjunctions whose smallest monotone networks contain disjunctions. We show that if |F|, is sufficiently small for all i, such anomalies cannot happen. We exhibit sets of m conjuctions in n unknowns which require c_{2}ma(m, n) binary conjunctions, where α(m, n) is a very slowly growing function related to a functional inverse of Ackermann's function. This class of examples shows that an algorithm given in [12] for computing functions defined on paths in trees is optimum to within a constant factor.

Original language | English (US) |
---|---|

Pages (from-to) | 121-133 |

Number of pages | 13 |

Journal | Annals of Discrete Mathematics |

Volume | 2 |

Issue number | C |

DOIs | |

State | Published - Jan 1 1978 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Discrete Mathematics and Combinatorics