This course is suitable for all undergraduate and doctoral students
who have acquired at least basic knowledge of mathematical logic,
graph theory, and complexity of algorithms. The course covers several
areas of interesting problems centerted around Boolean functions.
Although the course is mostly theoretical, it includes examples
of applications of the covered theory (e.g. in artificial intelligence
and relational databases). One of the goals of this course is to provide
the students with interesting research topics, which may be suitable
for their master thesis.
Last update: T_KTI (10.04.2001)
Tato přednáška je vhodná pro všechny studenty (nebo doktorandy),
kteří mají alespoň základní znalosti z matematické logiky, teorie
grafů a složitosti algoritmů. Přednáška pokrývá několik oblastí
zajímavých problémů soustředěných okolo Boolovských funkcí. Ačkoli je
přednáška převážně teoretická, zahrnuje i ukázky aplikací probírané
teorie (např. v oblasti umělé inteligence a relačních databází).
Jedním z cílů přednášky je poskytnout studentům zajímavá
výzkumná témata, vhodná případně i pro diplomové práce
Literature - Czech
Last update: prof. RNDr. Ondřej Čepek, Ph.D. (30.04.2015)
Y.Crama, P.L.Hammer, Boolean Functions - Theory, Algorithms, and Applications. Cambridge University Press, 2011.
Syllabus -
Last update: prof. RNDr. Ondřej Čepek, Ph.D. (30.04.2015)
1) Introduction to Boolean functions.
literals, logic operators, Boolean formulae and funkctions
normal forms (DNF, CNF) and their properties
2) Implicants, consequents, resolution (consensus) and its completeness
3) Monotone functions and their basic properties
2) Regular functions.
relative strength of variables, properties of regular functions
recognition and dualization of regular functions
3) Threshold functions.
properties, characterization, and recognition of threshold functions
4) Satisfiability of Boolean formulae
NP-completeness of SAT and 3-SAT
classes of formulae with polynomial time SAT: quadratic, Horn and q-Horn functions
5) Minimal representation of Boolean functions.
proofs of NP-completeness for some known classes
cases solvable in polynomial time: acyclic and quasi-acyclic functions
Last update: prof. RNDr. Ondřej Čepek, Ph.D. (30.04.2015)
• Úvod do Booleovských funkcí - literály, logické operátory, Booleovské formule a funkce, normální formy (DNF, CNF) a jejich vlastnosti.
• Rezoluce (konsensus) a její úplnost.
• Monotónní Booleovské funkce a jejich základní vlasnosti.
• Regulární funkce (poměrná síla proměnných, vlastnosti regulárních funkcí, rozpoznávání a dualizace regulárních funkcí)
• Prahové funkce (vlastnosti, charakterizace a rozpoznávání prahových funkcí)
• Splnitelnost Booleovských formulí (NP-úplnost SATu a 3-SATu, třídy formulí rozhodnutelné v polynomiálním čase: kvadratické, Hornovské a q-Hornovské funkce)
• Minimální reprezentace Booleovských funkcí (důkazy NP-úplnosti pro některé známé třídy, případy řešitelné v polynomiálním čase: acyklické a quasi-acyklické funkce)
