pith. sign in

arxiv: 1902.03431 · v1 · pith:LKCSMQXDnew · submitted 2019-02-09 · 🧮 math.CO · cs.LO

On the maximal minimal cube lengths in distinct DNF tautologies

classification 🧮 math.CO cs.LO
keywords answeranthonyarticlebooleancertainconjunctionscorrespondingcube
0
0 comments X
read the original abstract

Inspired by a recent article by Anthony Zaleski and Doron Zeilberger, we investigate the question of determining the largest k for which there exists boolean formulas in disjunctive normal form (DNF) with n variables, none of whose conjunctions are `parallel', and such that all of them have at least k literals. Using a SAT solver, we answer some of the questions they left open. We also determine the corresponding numbers for DNFs obeying certain symmetries.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.