1. Булевы функции. Существенные и фиктивные переменные.
2. Элементарные булевы функции. Формульное представление булевых функций.
3. СДНФ и СКНФ.
4. Полином Жегалкина.
5. Двойственные функции.
6. Полнота и замкнутость систем булевых функций.
7. Минимизация ДНФ.
8. Элементы теории автоматов.
9. Элементы теории кодирования.
10. Исчисление высказываний.
11. Исчисление предикатов.
Перечень контрольных вопросов по курсу
1. Определение булевой функции, табличное задание, число функций от n переменных. Элементарные функции. Существенные переменные. Равенство функций.
2. Понятие формулы, эквивалентные формулы. Основные тождества алгебры логики.
3. Двойственные функции и способы их получения. Теорема о двойственной функции.
4. Определение полной системы, примеры полных систем. Теорема о полных системах.
5. Замыкание. Свойство замыканий. Замкнутые классы. Свойства классов T0, T1.
6. Класс самодвойственных функций и его свойство.
7. Лемма о несамодвойственной функции.
8. Класс монотонных функций, его замкнутость.
9. Лемма о немонотонной функции.
10. Полином Жегалкина. Теорема о единственности полинома.
11. Линейные функции. Лемма о нелинейной функции.
12. Теорема о необходимых и достаточных условиях полноты систем булевых функций.
13. Теорема о числе функций полных систем.
14. Определение ДНФ. Понятие минимальной и кратчайшей ДНФ булевой функции. Тривиальный способ их нахождения.
15. Геометрическое представление булевых функций. Интервал, допустимый интервал, максимальный интервал. Покрытие множества единичных наборов булевой функции интервалами. Кратчайшее и минимальное покрытия. Сокращенная ДНФ.
16. Импликанта, простая импликанта, их свойства.
17. Матричное представление булевой функции в коде Грея. Визуально-матричный метод минимизации булевых функций.
18. Теорема Квайна о построении сокращенной ДНФ. Троичные векторы. Алгоритм Квайна–МакКласки.
19. Булева матрица и ее покрытия. Нахождение всех безызбыточных покрытий.
20. Теорема Блейка о построении сокращенной ДНФ булевой функции. Алгоритм Блейка.
21. Общая схема получения минимальных и кратчайших ДНФ.
22. Ортогональные конъюнкции и ортогональные ДНФ. Теорема о поглощении конъюнкции дизъюнктивной нормальной формой.
23. Теорема о сокращенной ДНФ монотонной функции.
24. Объединение и пересечение тупиковых и минимальных ДНФ.
25. Ядро ДНФ. Теорема Квайна о ядре и ее следствие.
26. Частичные булевы функции и их представления.
27. Реализация частичной функции. Импликанта и простая импликанта частичной функции. Сокращенная ДНФ.
28. Построение сокращенной ДНФ. Использование таблицы Квайна для получения кратчайших и минимальных ДНФ.
29. Визуально-матричный метод минимизации частичной функции.
30. Понятие о дискретном устройстве, комбинационном и последовательностном.
31. Анализ и синтез дискретных устройств.
32. Элементарные комбинационные устройства.
33. Синтез комбинационных устройств в базисе ДНФ.
34. Синтез комбинационных устройств в базисе НЕ И.
35. Синтез комбинационных устройств в базисе НЕ ИЛИ.
36. Определение автомата. Классификация автоматов.
37. Таблицы переходов-выходов и диаграммы переходов.
38. Триггеры.
39. Канонические уравнения и их получение из таблиц переходов-выходов.
40. Формальные языки и настроенные диаграммы.
41. Конечно-автоматные языки и их свойства.
42. Алфавитное кодирование. Однозначность кодирования.
43. Свойство префикса. Теорема.
44. Нетривиальное разложение кодов в схеме кодирования. Алгоритм проверки кодирования на однозначность.
45. Неравенство МакМилана. Теорема.
46. Теорема о существовании взаимно-однозначного кодирования, обладающего свойством префикса.
47. Понятие о кодах с минимальной избыточностью.
48. Дерево взаимно однозначного кодирования и операции на нем.
49. Насыщенное и приведенное кодовые деревья.
50. Алгоритм построения кода с минимальной избыточностью.
51. Алфавит исчисления высказываний.
52. Синтаксис исчисления высказываний.
53. Семантика исчисления высказываний.
54. Общезначимые, невыполнимые и нейтральные формулы.
55. Полная и частичная интерпретации. Модель. Дерево интерпретаций.
56. Проблема вывода. Ее сведение к анализу КНФ на невыполнимость.
57. Резольвентный метод анализа КНФ на невыполнимость. Метод Блейка.
58. Алфавит исчисления предикатов.
59. Синтаксис исчисления предикатов.
60. Семантика исчисления предикатов.
61. Проблема вывода.
62. Предваренная нормальная форма.
63. Сколемова форма.