Introductory description

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.

Module aims

Outline syllabus

This is an indicative module outline only to give an indication of the sort of topics that may be covered. Actual sessions held may differ.

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.

Learning outcomes

By the end of the module, students should be able to:

• 1. Understand the notion of Boolean function and various ways of representing them
• 2. State Post's Theorem and compute Post classes generated by given functions
• 3. Recognize special classes of Boolean functions, such as quadratic, Horn, threshold, read-once, etc.
• 4. Be able to apply partially defined Boolean functions to logical analysis of data
• 5. Understand pseudo-Boolean functions in the context of pseudo-Boolean optimisation

Indicative reading list

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

Subject specific skills

This module lays a solid foundation to the study of Boolean functions. It develops in depth the notions that allow one to
investigate the structure of Boolean functions and apply them to Algebra, Analysis, Combinatorics or Computer Science. Students taking the module will learn some of the techniques required for working on a large-scale research project. These techniques are partly theoretical, and partly computational.

Transferable skills

Clear and precise thinking, and the ability to follow complex reasoning, to construct logical arguments, and to expose illogical ones. The ability to retrieve the essential details from a complex situation and thereby facilitate
problem resolution.