# zbMATH — the first resource for mathematics

On the maximal minimal cube lengths in distinct DNF tautologies. (English) Zbl 1449.05018
Summary: Inspired by a recent article by A. Zaleski and D. Zeilberger [“Boolean function analogs of covering systems”, Preprint, arXiv:1801.05097], we investigate the question of determining the largest $$k$$ for which there exist Boolean formulas in disjunctive normal form (DNF) with $$n$$ variables, which are tautologies, whose conjunctions have distinct sets of variables, and such that all the conjunctions have at leastkliterals. Using a SAT solver, we answer the question for some sizes which Zaleski and Zeilberger [loc. cit.] left open. We also determine the corresponding numbers for DNFs obeying certain symmetries.
##### MSC:
 05A15 Exact enumeration problems, generating functions 68W30 Symbolic computation and algebraic computation
##### Keywords:
covering systems; SAT solving; symmetry breaking