Defense Date

11-20-2014

Graduation Date

Fall 2014

Availability

Immediate Access

Submission Type

thesis

Degree Name

MS

Department

Computational Mathematics

School

McAnulty College and Graduate School of Liberal Arts

Committee Chair

Karl Wimmer

Committee Member

Jeffrey Jackson

Committee Member

Abhay Gaur

Keywords

Boolean function, DNF formula, spectral entropy

Abstract

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.

Format

PDF

Language

English

Download

Share

COinS