1. Дизъюнктивные нормальные формы (ДНФ). Допустимые и минимальные конъюнкции. Тупиковая, минимальная и сокращ.нная ДНФ. Геометрическая интерпретация.

2. Оценки сложности ДНФ (функции L_D(n) и L'_D(n)).

3. Замкнутая ДНФ. Методы получения сокращенной ДНФ. Градиентный алгоритм.

4. Критерий вхождения минимальной конъюнкции в ДНФ S T.

5. Окрестность ранга r. Отсутствие критерия ранга r вхождения минимальной конъюнкции в ДНФ S M.

6. Контактные схемы. Простейшие методы синтеза. Контактное дерево. Свойство разделительности.

7. Реализации всех конъюнкций контактной схемой со сложностью 2ⁿ(1+o(1)). Свойство ослабленной разделительности.

8. Асимптотически наилучший метод синтеза контактных схем.

9. Нижняя оценка функции L_k(n). Асимптотика функции L_k(n).

10. Метод каскадов (для контактных схем).

11. Доказательство минимальности контактной схемы для линейной функции.

12. Нижняя оценка вида Cn^3/2 для сложности реализации линейной функции контактными π-схемами.

13. Нижняя оценка вида n² для сложности реализации линейной функции контактными π-схемами.

14. Доказательство минимальности контактного дерева в классе разделительных схем.

15. Самокорректирующиеся контактные схемы. Корректирование одного замыкания (размыкания).

16. Надежные контактные схемы из ненадежных контактов.

17. Эквивалентные преобразования формул над базисом {& ,Ъ ,Ш , x, 0, 1}.

18. Эквивалентные преобразования контактных схем. Система правил Г_n. Производные правила (для цепочек). Полнота системы Г_n для схем над переменными x₁,...,x_n.

19. Отсутствие полной конечной системы правил преобразований контактных схем.

20. Тесты. Таблицы неисправностей. Тривиальные оценки длины теста. Длина минимального теста для почти всех таблиц.

21. Градиентный алгоритм построения тестов. Оценка длины.

22. Диагностический тест. Доказательство соотношения D(n)=2ⁿ.