MA3K6 Boolean Functions
Lecturer: Vadim Lozin
Term(s): Term 1
Status for Mathematics students: List A
Commitment: 30 lectures
Assessment: 85% 3 hour examination, 15% coursework
Formal registration prerequisites:
Assumed knowledge:
Useful background:
Content: Boolean functions, named after an English mathematician George Boole, are {0,1}-valued functions of {0,1}-valued variables. They are the most fundamental objects studied in pure and applied mathematics. This module is a comprehensive introduction to the theory of Boolean functions with an emphasis on structural and combinatorial properties. We will also discuss connections of Boolean functions with other combinatorial structures, such as graphs, hypergraphs, set systems, matroids, as well as applications of Boolean functions in data analysis and optimisation.
Aims: The module will include a brief introduction to the basic concepts of Boolean functions, and it will then be structured around the following topics:
1. Foundations:
- Representations of Boolean functions: Boolean expressions, binary decision diagrams, decision trees, geometric interpretation
- Normal forms, prime implicants
- Duality theory
- Functional completeness, Post’s Theorem
2. Classes of Boolean functions:
- Quadratic functions
- Horn functions
- Threshold functions
- Read-once functions
3. Generalizations and applications:
- Partially defined Boolean functions and logical analysis of data
- Pseudo-Boolean functions and pseudo-Boolean optimisation
Learning outcomes: At the end of the module, students will be able to:
- Understand the notion of Boolean function and various ways of representing them
- State Post's Theorem and compute Post classes generated by given functions
- Recognize special classes of Boolean functions, such as quadratic, Horn, threshold, read-once, etc
- Be able to apply partially defined Boolean functions to logical analysis of data
- Understand pseudo-Boolean functions in the context of pseudo-Boolean optimisation
Books:
Crama, Yves; Hammer, Peter L., Boolean Functions. Theory, Algorithms and applications. Encyclopaedia of Mathematics and its Applications, 142. Cambridge University Press, Cambridge, 2011. xxii+687 pp. ISBN: 978-0-521-84751-3