Representations of Boolean Functions - NAIL031
Title: Reprezentace booleovských funkcí
Guaranteed by: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
Faculty: Faculty of Mathematics and Physics
Actual: from 2022
Semester: summer
E-Credits: 3
Hours per week, examination: summer s.:2/0, Ex [HT]
Capacity: unlimited
Min. number of students: unlimited
4EU+: no
Virtual mobility / capacity: no
State of the course: cancelled
Language: Czech
Teaching methods: full-time
Teaching methods: full-time
Additional information: http://www.cs.cas.cz/~savicky/vyuka/rbf/
Guarantor: RNDr. Petr Savický, CSc.
Class: Informatika Mgr. - Teoretická informatika
Classification: Informatics > Theoretical Computer Science
Opinion survey results   Examination dates   Schedule   Noticeboard   
Annotation -
Last update: T_KTI (20.04.2016)
The models for representation of boolean functions are discussed, namely boolean formulas in DNF and CNF, and different types of binary decision diagrams (BDD), in particular read-once decision diagrams and OBDD. The course will mainly concentrate on the proofs of comparison of the expressive power of the models and on the algorithms for the operations with the boolean functions using BDD.
Aim of the course -
Last update: RNDr. Jan Hric (07.06.2019)

TBA

Course completion requirements -
Last update: RNDr. Jan Hric (07.06.2019)

TBA

Literature -
Last update: T_KTI (18.04.2016)

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

Ch. Meinel, T. Theobald. Algorithms and Data Structures in VLSI-Design: OBDD - Foundations and Applications. Springer-Verlag, Berlin, Heidelberg, New York, 1998.

Stasys Jukna. Boolean Function Complexity: Advances and Frontiers. Springer-Verlag, 2012.

Syllabus -
Last update: T_KTI (16.05.2011)
  • Partial input, subcube, monomial, DNF, implicant, primary implicant.
  • Clause, CNF, implicate, prime implicate.
  • Dual function, monotone, self-dual and linear funciotns.
  • Boolean formulas, circuits.
  • Binary decision tree, binary decision diagrams (BDD), read-once BDD, OBDD.
  • Diagram of mutual relationships between the studied models, proofs of embeddings in it.
  • The maximum complexity of representing functions using circuits and binary decision diagrams.
  • Bounds on the complexity of functions in DNF, CNF, decision trees.
  • Bounds on the complexity of OBDD and read-once BDD.
  • Diagram of mutual relationships between the studied models, proofs of strict inclusions and incomparabilitites.
  • Operations with functions represented by OBDD.
  • The relationship between the depth and size of a decision tree and the complexity of the function expressed by both DNF and CNF.
  • Operations with functions represented using decision trees.
  • Nonuniform Turing machine, relationship to Boolean models, Karp-Lipton theorem.
  • Probabilistic non-equivalence test for read-once decision diagrams.
  • BPP is contained in P/poly, so is representable by polynomial size circuits.
  • Lower bounds for decision trees using Fourier transform of the Boolean functions.