  Computational learning theory states that many classes of boolean formulas
are learnable in polynomial time. This paper addresses the understudied subject
of how, in practice, such formulas can be learned by deep neural networks.
Specifically, we analyze boolean formulas associated with model-sampling
benchmarks, combinatorial optimization problems, and random 3-CNFs with varying
degrees of constrainedness. Our experiments indicate that: (i) neural learning
generalizes better than pure rule-based systems and pure symbolic approach;
(ii) relatively small and shallow neural networks are very good approximators
of formulas associated with combinatorial optimization problems; (iii) smaller
formulas seem harder to learn, possibly due to the fewer positive (satisfying)
examples available; and (iv) interestingly, underconstrained 3-CNF formulas are
more challenging to learn than overconstrained ones. Such findings pave the way
for a better understanding, construction, and use of interpretable
neurosymbolic AI methods.
