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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Программа экзамена по математической логикеЛектор — О. Б. Лупанов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.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов ответов (шпаргалок)