2. Булевы функции. Табличное задание булевых функций. Существенные и фиктивные переменные. Представление булевых функций формулами. Разложение булевой функции по переменной. Совершенная дизъюнктивная нормальная форма. Совершенная конъюнктивная нормальная форма.

3. Полиномы Жегалкина. Единственность полинома Жегалкина. Методы построения полинома Жегалкина. Преобразование Мебиуса. Явная формула для коэффициентов полинома Жегалкина. Быстрое преобразование Мебиуса. Преобразование Мебиуса обратно само себе.

4. Замкнутые классы булевых функций. Классы функций, сохраняющих константы. Самодвойственные, линейные, монотонные функции. Оценки числа монотонных функций с использованием теоремы Дилуорса.

5. Леммы о несамодвойственной, немонотонной, нелинейной функциях. Теорема о полноте системы булевых функций. Возможность выделить из любой полной системы булевых функций полную подсистему не более чем из четырех функций.

6. k-значные функции. Элементарные k-значные функции. Первая и вторая канонические формы для k-значных функций. Представление k-значных функций полиномами. Полнота системы из одной функции Вебба. Алгоритм распознавания полноты системы.

7. Схемы из функциональных элементов. Простейшие методы реализации булевых функций схемами из функциональных элементов. Совместная реализация всех конъюнкций. Метод Шеннона.

8. Детерминированные функции. Ограниченно-детерминированные (автоматные функции). Диаграммы Мура. Канонические таблицы. Двоичные канонические таблицы. Канонические уравнения. Реализация автоматных функций схемами из функциональных элементов с задержками.

9. Алфавитное кодидование. Коды с однозначным декодированием. Префиксные, суффиксные коды. Неравенство Макмиллана. Существование префиксного кода с параметрами, удовлетворяющими неравенству Макмиллана.

10. Оптимальные коды. Существование оптимальных кодов. Свойства оптимальных префиксных кодов. Алгоритм построения оптимального кода (Алгоритм Хаффмана).

11. Коды, обнаруживающие и исправляющие ошибки типа замены. Кодовое расстояние. Линейные коды. Порождающая матрица. Дуальный код. Проверочная матрица. Построение проверочной матрицы с помощью порождающей и наоборот. Синдром линейного кода. Кодовое расстояние линейного кода. Связь кодового расстояния линейного кода со свойствами столбцов его проверочной матрицы. Код Хэмминга. Кодирование и декодирование с использованием кода Хэмминга.