О.Б. Лупанов - Программа экзамена по дискретной математике

Программа экзамена по математической логикеЛектор — О. Б. ЛупановII семестр, 2005 г.1. Формулы алгебры логики. Существенные и несущественные переменные. Формулы. Эквивалентность формул. Элементарные функции и их свойства. Разложение функция по переменной.

Совершенная дизъюнктивная нормальная форма (СДНФ).2. Полные системы функций. Примеры полных систем. Замкнутые классы.3. Полиномы Жегалкина. Линейные функции. Лемма о линейной функции.4. Самодвойственные функции. Лемма о несамодвойственной функции.5. Монотонные функции. Лемма о немонотонной функции.6. Теорема о полноте систем функций алгебры логики. Возможность выделить из каждой полной системыполную систему, состоящую не более чем из четырех функций.

Предполные классы.7. Функции k-значной логики. Элементарные функции. Полнота системы{0, 1, . . . , k − 1, J0 (x), J1 (x), . . . , Jk−1 (x), max(x, y), min(x, y)}.8.9.10.11.12.13.14.15.16.17.18.19.20.21.22.23.24.25.26.27.28.29.Полнота систем {max(x, y), x + 1}, {Vk (x, y)}.Алгоритм распознавания полноты конечных систем функций в Pk .Представление функций из Pk полиномами.Лемма о трех наборах. Лемма о квадрате. Теорема Яблонского. Теорема Слупецкого.Классы сохранения множеств функций и их свойства.

Теорема Кузнецова.Замкнутый класс в Pk (k > 3) без базиса. Замкнутый класс в Pk (k > 3), имеющий счетный базис.Мощность множества замкнутых классов в Pk .Графы, основные понятия. Реализация графов в трехмерном пространстве.Схемы из функциональных элементов. Простейшие методы синтеза.Контактные схемы. Простейшие методы синтеза.Метод каскадов (для контактных схем и функциональных элементов).Верхняя оценка функции Ln для схем из функциональных элементов и контактных схем.

Порядок ростафункции Ln .Детерминированные функции. Ограниченно-детерминированные функции (автоматные) функции. Способы их задания.Реализуемость автоматных функция схемами из функциональных элементов и элементов задержки (схемами с обратными связями).Исчисление высказываний. Аксиомы. Правило вывода. Тождественная истинность выводимых формул.Непротиворечивость исчисления высказываний.Предикаты. Логические операции над предикатами.Условие полноты системы предикатов на конечном множестве.Модель, формулы в модели. Свободные и связные переменные.

Значение формул в модели.Истинность формул в модели, на множестве. Тождественно истинные формулы.Правила эквивалентных преобразований формул логики предикатов. Нормальная форма.Машина Тьюринга. Вычислимые функции.Алгоритмическая неразрешимость проблемы самоприменимости.Алгоритмическая неразрешимость проблемы применимости.Последняя компиляция: 28 октября 2005 г.Обновления документа — на сайте http://dmvn.mexmat.net.Об опечатках и неточностях пишите на dmvn@mccme.ru.1.