Глава 2. Теория булевых функций

25. Определение булевых функций и булевых векторов. Задание б.ф. с помощью таблиц истинности. Количество бф от n переменных. Фиктивные и существенные переменные. Таблица булевых функций двух переменных.

26. Задание б.ф. с помощью формул (определение формулы по индукции через элементарную формулу). Эквивалентные формулы. Подстановка и замена. Примеры эквивалентных формул.

27. Двойственность. Таблица истинности двойственной функции. Теорема о двойственной функции. Принцип двойственности. Примеры.

28. Понятие нормальной формы. Примеры. Требование на единственность и существование алгоритма построения. Теоремы о разложении. Следствия (разложение по одному элементу, по всем, двойственность).

29. Дизъюнкт и конъюнкт. ДНФ и КНФ. Основная теорема о нормальной форме. Совершенные нормальные формы и их связь с таблицей истинности.

30. Эквивалентные преобразования формул. Таблица эквивалентных формул*. Пример эквивалентного преобразования. Полином Жегалкина.

31. Импликанты. Сокращенные и минимальные дизъюнктивные формы. Минимизация методом Квайна. Пример.

32. Сокращенные и минимальные дизъюнктивные формы. Минимизация булевых функций методом Карно. Упрощение электрических схем. Примеры.

32. Функциональная декомпозиция. Простая дизъюнктивная декомпозиция. Пример. Сложные дизъюнктивные декомпозиции. Логические сети.

33. Полнота и замыкание классов функций. Лемма о представимости. Свойства замыкания (4 штуки). Замкнутый класс. Полный класс. Базис. Примеры полных классов.

34. Класс Т0 функций, сохраняющих 0 (замкнутость и мощность его). Класс Т1 функций, сохраняющих 1. Пример.

35. Класс S самодвойственных функций. Лемма о несамодвойственной функции. Пример.

36. Класс M монотонных функций. Лемма о немонотонной функции. Пример.

37. Класс L линейных функций. Теорема о нелинейной функции. Пример.

38. Теорема Поста (с доказательством). Следствие о четырех функциях в полной системе. Пример применения. Предполные классы. Теорема о предполных классах.