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