Вопросы к экзамену по курсу «Математическая логика и теория алгоритмов»





Скачать 66.23 Kb.
НазваниеВопросы к экзамену по курсу «Математическая логика и теория алгоритмов»
Дата публикации31.07.2013
Размер66.23 Kb.
ТипВопросы к экзамену
100-bal.ru > Математика > Вопросы к экзамену
Вопросы к экзамену по курсу «Математическая логика и теория алгоритмов».

Логика высказываний.

  1. Понятие высказывания и его структура: атомарные высказывания и составные высказывания. Логические союзы: дизъюнкция, конъюнкция, импликация, эквивалентность, отрицание. Символическая запись составных высказываний и формализация предложений естественного языка.

  2. Алфавит и слова в алфавите. Формальные языки.

  3. Алфавит языка логики высказываний. Индуктивное определение пропозициональной формулы. Понятие подформулы пропозициональной формулы. Индукция по длине построения формулы.

  4. Логическая сложность пропозициональных формул. Теорема характеризации множества пропозициональных формул.

  5. Теорема о единственности синтаксического анализа пропозициональной формулы.

  6. Оценки пропозициональных букв и индуктивное определение истинностного значения пропозициональной формулы. Множество истинностных оценок и функция истинности пропозициональной формулы. Таблица истинности пропозициональной формулы.

  7. Выполнимые и общезначимые формулы(тавтологии).

  8. Отношение семантического следования и семантической равносильности пропозициональных формул. Семантический modus ponens и семантическая теорема дедукции.

  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. Метод многозначных логик в доказательстве независимости аксиом исчисления высказываний.

Логика Предикатов.

  1. Суждения, переменные высказывания и высказывательные формулы. Ковекторы в суждения. Примеры предикатов на наборе предметных областей.

  2. Определение предиката и его множество истинности.

  3. Логические операции над предикатами: логические связки и квантификации.

  4. Теоретико-множественный смысл логических связок и кванторов.

  5. Символическая запись суждений, выраженных предложением с кванторами.

  6. Алфавит языка логики предикатов и его сигнатура: переменные, константы, функциональные и предметные символы, логические связки и кванторы.

  7. Индуктивное определение термов в логике предикатов. Примеры термов. Атомарные термы и функциональная сложность терма.

  8. Определение формул языка логики предикатов. Индуктивное построение множества формул на основе атомарных формул. Понятие логической сложности формулы.

  9. Подтермы термов и подформулы формул. Область действия кванторных приставок в формуле. Способы вхождения предметных переменных в формулы. Параметры формулы и замкнутые формулы. Примеры суждений записываемых замкнутыми формулами.

  10. Определение и примеры интерпретаций языка логики предикатов, конечные и бесконечные предметные области интерпретации.

  11. Заполнения предметных переменных в предметной области интерпретации и значения термов при заданном заполнении.

  12. Определение истинностного значения формулы в интерпретации при заданном заполнении. Примеры вычисления истинностных оценок формул в различных интерпретациях.

  13. Классификация формул по их истинностным значениям. Отношение семантического следования. Семантическое следствие множества формул.

  14. Семантические свойства истинности. Примеры логически общезначимых формул.

  15. Семантическая равносильность формул логики предикатов. Список основных равносильностей.

  16. Предваренные нормальные формы. ПНФ данной формулы и теорема о приведении к ПНФ. Алгоритм приведения к ПНФ.

  17. Построение исчисления предикатов (ИП): алфавит, язык, аксиомы и правила вывода в ИП.

  18. Выводимость из множества формул в ИП, доказуемость формулы в ИП. Теорема адекватности ИП.

  19. Теореме дедукции в Исчислении предикатов.

  20. Противоречивые и непротиворечивые множества формул в ИП. Непротиворечивость выполнимых множеств формул. Доказуемость любой формулы в противоречивой теории.

  21. Теорема Геделя о полноте в логике предикатов.

Алгоритмические модели (эффективная вычислимость).

  1. Понятие конструктивного объекта и интуитивное определение понятия «алгоритм». Слова в алфавитах как конструктивные объекты.

  2. Эвристика модели Тьюринга: неформальное описание машины Тьюринга. Входной алфавит, алфавит внутренних состояний и команды машины Тьюринга.

  3. Строгое определения машины Тьюринга и задание машины посредством тройки функций.

  4. Определение конфигурации машины Тьюринга и отношение следования на множестве конфигураций. Начальное состояние и начальная конфигурация. Определение заключительной конфигурации. Протокол вычисления на машине Тьюринга.

  5. Применимость и неприменимость машины Тьюринга к слову во входном алфавите. Словарная функция, задаваемая машиной Тьюринга. Определение вычислимой по Тьюрингу словарной функции и примеры вычислимых функций.

  6. Вычислимость функций натурального аргумента в унарной кодировке натуральных чисел. Программа для функций сложения и следования. Вычислимость копировальной машины Тьюринга.

  7. Характеристическая функция подмножества и определение разрешимого подмножества. Пример разрешимых подмножеств.

  8. Полухарактеристическая функция подмножества и определение перечислимого подмножества. Примеры перечислимых подмножеств.

  9. Теорема Поста о разрешимости перечислимого множества, если его дополнение перечислимо.

  10. Вычислимые по Тьюрингу предикаты и конструкции вычислимых функций.

  11. Нумерация машин Тьюринга и вычислимых по Тьюрингу функций. Разрешимые и перечислимые языки.

  12. Проблемы самоприменимости и остановки, теоремы об их алгоритмической неразрешимости.

  13. Тезис Черча-Тьюринга.

  14. Алгоритмическая модель вычислимости С. Клини – частично-рекурсивные функции. Основные функции. Операторы суперпозиции и схемы примитивной рекурсии.

  15. Определение и примеры примитивно-рекурсивных функций: сумма, произведение, max, min, усеченная разность, многочлены с целыми коэффициентами.

  16. Оператор минимизации и определение частично-рекурсивных функций. Пример частично-рекурсивной, но не примитивно-рекурсивной функции.

  17. Теорема о совпадении класса вычислимых по Тьюрингу функций и класса частично-рекурсивных функций.

Список литературы.

  1. А.Н. Колмогоров, А.Г. Драгалин «Введение в математическую логику», М., изд. МГУ, 1982.

  2. Э. Мендельсон «Введение в математическую логику», М., изд. «Наука», 1984.

  3. А.И. Мальцев «Алгоритмы и рекурсивные функции», М., изд. «Наука», 1965.

  4. С.Г. Гиндикин «Алгебра логики в задачах», М., изд. «Наука», 1972.

  5. Дж. Булос, Р. Джеффри «Вычислимость и логика», М., изд. «Мир», 1994.

  6. Г. Метакидес, А. Нерроу «Принципы логики и логического программирования», И., изд. «Факториал», 1998.

  7. А.С. Герасимов «Курс математической логики и теории вычислимости», С.-Пб., изд. «Лема», 2011.

  8. И. Лавров, А. Максимова «Сборник задач по теории множеств, математической логике и теории алгоритмов».

  9. Н.К. Верещагин, А. Шень «Лекции по математической логике и теории алгоритмов», часть 2 «Языки и исчисления», часть 3 «Вычислимые функции», МЦНМО, 2002.

  10. Д. Грис «Наука программирования», М., изд. «Мир», 1984(гл.1,2).

Добавить документ в свой блог или на сайт

Похожие:

Вопросы к экзамену по курсу «Математическая логика и теория алгоритмов» iconУчебно-методический комплекс по дисциплине математическая логика и теория алгоритмов
Курс математическая логика и теория алгоритмов обеспечивает приобретение знаний в соответствии с государственным образовательным...
Вопросы к экзамену по курсу «Математическая логика и теория алгоритмов» iconВопросы к государственному экзамену по информатике
Дискретная математика. Теория алгоритмов. Математическая логика. Численные методы. Теоретические основы информатики. Исследование...
Вопросы к экзамену по курсу «Математическая логика и теория алгоритмов» iconРефератов по курсу «Математическая логика и теория алгоритмов»
Темпоральные логики высказываний линейного времени и вычислительных деревьев: их синтаксис и семантика
Вопросы к экзамену по курсу «Математическая логика и теория алгоритмов» iconПрограмма дисциплины «Информатика, математическая логика и теория...
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направлений подготовки 231000....
Вопросы к экзамену по курсу «Математическая логика и теория алгоритмов» iconРабочая программа составлена в соответствии с требованиями фгос впо...
Дёгтев А. Н. Теория алгоритмов. Учебно-методический комплекс. Рабочая программа для студентов направления 010100. 62 – математика,...
Вопросы к экзамену по курсу «Математическая логика и теория алгоритмов» iconВопросы к экзамену по дисциплине “Математическая логика”
Эквивалентные преобразования формул. Применение операций склеивания и поглощения
Вопросы к экзамену по курсу «Математическая логика и теория алгоритмов» iconПрограмма вступительных испытаний по дисциплине «Математика»
Курс математическая логика и теория алгоритмов обеспечивает приобретение знаний в соответствии с государственным образовательным...
Вопросы к экзамену по курсу «Математическая логика и теория алгоритмов» iconУчебно-методический комплекс дисциплины «Математическая логика и теория алгоритмов»
Заведующий кафедрой И7 д ф м н., профессор /С. Д. Шапорев/ Составитель д ф м н., профессор /С. Д. Шапорев
Вопросы к экзамену по курсу «Математическая логика и теория алгоритмов» iconНазвание курса
Основной курс "Математическая логика и теория алгоритмов" предназначен для студентов первого курса отделения прикладной инфоматики...
Вопросы к экзамену по курсу «Математическая логика и теория алгоритмов» iconРадиофизический факультет
Фгос впо, содействует формированию мировоззрения и системного мышления. Целью преподавания дисциплины «Математическая логика и теория...
Вопросы к экзамену по курсу «Математическая логика и теория алгоритмов» iconРабочая программа по дисциплине В. В математическая логика и теория алгоритмов
Рабочая программа составлена на основе фгос впо и учебного плана мгту по направлению 090900. 62 Информационная безопасность
Вопросы к экзамену по курсу «Математическая логика и теория алгоритмов» iconРабочая программа по дисциплине В. В математическая логика и теория алгоритмов
Рабочая программа составлена на основе фгос впо и учебного плана мгту по направлению 090900. 62 Информационная безопасность
Вопросы к экзамену по курсу «Математическая логика и теория алгоритмов» iconМетодические указания к выполнению лабораторных работ 1-3 по дисциплине...
Целью работы является теоретическое изучение основных логических функций и эквивалентностей исчисления высказываний и приобретение...
Вопросы к экзамену по курсу «Математическая логика и теория алгоритмов» iconМатематическая логика и теория алгоритмов
Основными видами учебных занятий являются лекции и семинарские занятия. Аудиторные занятия составляют 54 часа в 3 семестре и 72 часа...
Вопросы к экзамену по курсу «Математическая логика и теория алгоритмов» iconРабочая программа дисциплины «Математическая логика и теория алгоритмов»
Рабочая программа предназначена для преподавания дисциплины вариативной части профессионального цикла студентам очной формы обучения...
Вопросы к экзамену по курсу «Математическая логика и теория алгоритмов» iconИндивидуальное домашнее задание по дисциплине «Дискретная математика»...
Курс математическая логика и теория алгоритмов обеспечивает приобретение знаний в соответствии с государственным образовательным...


Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
100-bal.ru
Поиск