|
Булевы функции
Булева функция
Существенная переменная
Теорема о числе булевых функций, существенно зависящих от n переменных
Формула над заданным множеством булевых функций
Функция, реализуемая формулой
Эквивалентные формулы
Теорема о разложении функций по переменным
Совершенная дизъюнктивная нормальная форма
Совершенная конъюнктивная нормальная форма
Двойственная функция. Принцип двойственности
Замкнутое, полное множества булевых функций
Теорема о полноте двух систем
Полином Жегалкина
Теорема Жегалкина
Основные замкнутые классы булевых функций
Теорема Поста
Лемма о несамодвойственной функции
Лемма о нелинейной функции
Лемма о немонотонной функции
Предполный класс
Теорема о предполных классах булевых функций
Минимальная ДНФ
Кратчайшая ДНФ
Импликанта
Интервал ранга r
Сокращенная ДНФ
Теорема о сокращенной ДНФ монотонной функции
Метод Нельсона построения сокращенной ДНФ
Метод Квайна построения сокращенной ДНФ
Метод Блейка построения сокращенной ДНФ
Тупиковая ДНФ
Теорема Журавлева (критерий поглощения)
Ядровая элементарная конъюнкция
Ядро сокращенной ДНФ
ДНФ Квайна
Схема из функциональных элементов
Система функций, реализуемая схемой из функциональных элементов
Сложность схемы из функциональных элементов
Функция Шеннона
Верхняя оценка функции Шеннона для СФЭ
Лемма о нижней оценке
Теорема о нижней оценке функции Шеннона для СФЭ
Асимптотика функции Шеннона для СФЭ
Автоматные функции, конечные автоматы
Детерминированные функции
Информационное дерево
Ограниченно-детерминированная функция
Множество состояний ограниченно-детерминированной функции
Диаграмма Мура
Канонические уравнения ограниченно-детерминированной функции
Конечный автомат Мили
Автоматная функция
Схема из автоматных элементов
Теорема о несуществовании конечных полных систем автоматных функций
Элемент единичной задержки
Теорема о реализации автоматных функций схемами из автоматных элементов
Остальное знать к экзамену:
Эквивалентность конечных автоматов
Конечный автомат Мура
Теорема об эквивалентности автоматов Мили и Мура
Конечный детерминированный инициальный автомат без выходов
Язык, распознаваемый конечным автоматом
Теорема о существовании языков, не распознаваемых конечными автоматами
Регулярный язык
Недетерминированный конечный автомат без выходов
Теорема детерминизации
Теорема синтеза автоматов
Теорема анализа автоматов
|