Syllabus
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
Annotation
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.