Representation of Boolean Functions

Czech version

The course is organized by Department of Theoretical Computer Science and Mathematical Logic of the Faculty of Mathematics and Physics, Charles University in Prague.

Annotation

The models for representation of Boolean functions are discussed, namely Boolean circuits and formulas, DNF, CNF, decision trees and different types of binary decision diagrams. Some of the models may be used as a data structure for algorithms, which perform operations on the Boolean functions. We will be mainly interested in the proofs of some of the known results, which compare the expressive power of the models.

Synopsis

Bibliography

I. Wegener. Branching Programs and Binary Decision Diagrams - Theory and Applications. SIAM Monographs on Discrete Mathematics and Applications, 2000.