An Analysis of DNF Maximum Entropy

This study focuses on the entropy of functions computed by monotone DNF formulas. Entropy, which is a measure of uncertainty, information, and choice, has been long studied in the field of mathematics and computer science. We will be considering spectral entropy and focus on the conjecture that for each fixed number of terms t, the maximum entropy of a function computed by a t-term DNF is achieved by a function computable by a read-once DNF. A Python program was written to first express the t-term DNF Boolean functions as multilinear polynomials and then to compute their spectral entropy. This was done for the cases t = 1, 2, 3, 4. Our results agree with the conjecture and show that the maximum entropy occurs for functions with a small number of literals.

Name thesis:degree_name

MS

Level thesis:degree_level

Immediate Access

Discipline thesis:degree_discipline

Computational Mathematics

Year dc:date.available

2014

Author dc:creator

• Hasanaj, Belinda

Contributors dc:contributor

• Karl Wimmer
• Jeffrey Jackson
• Abhay Gaur

• Boolean function
• DNF formula
• spectral entropy

Language dc:language

English

Repository record dc:identifier

https://dsc.duq.edu/etd/634

OAI identifier oai:identifier

oai:dsc.duq.edu:etd-1650