WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

Математическая логика и алгоритмы (2014)

Программа экзамена

Логика предикатов

1. Сигнатура 1-го порядка. Термы, атомарные формулы, формулы. Вхождение

буквы в слово. Свободные и связанные вхождения переменных в формулы.

Замкнутые термы и формулы.

2. Интерпертация сигнатуры (в другой терминологии - модель; структура).

Нормальная интерпретация сигнатуры с равенством. Расширенная сигнатура.

Оцененные термы и формулы. Значения оцененных термов и формул в интерпретации. Общезначимость и выполнимость замкнутых формул.

3. Гомоморфизм и изоморфизм интерпретаций. "Сохранение" значений:

оцененных термов при гомоморфизме, оцененных формул без равенства при сюръективном гомоморфизме, оцененных формул с равенством при изоморфизме.

4. Композиция гомоморфизмов. Изоморфность интерпретаций.

5. Определимые (выразимые) в данной интерпретации предикаты и отношения; их инвариантность при автоморфизмах.

6. Элементарная теория интерпретации. Элементарная эквивалентность.

Элементарная эквивалентность изоморфных структур.

7. Теории 1-го порядка. Модель теории. Выполнимые теории. Сильно категоричные теории. Теорема о сильной категоричности элементарной теории конечной структуры в конечной сигнатуре (с равенством).

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

9. Исчисление предикатов 1-го порядка в данной сигнатуре без равенства. Схемы аксиом и правила вывода. Доказательство (вывод) из множества гипотез.

Выводимость. Теоремы исчисления предикатов и теорий 1-го порядка.

10. (Мета)теорема о дедукции для исчисления предикатов. Связь между выводимостью в конечной теории и выводимостью в исчислении предикатов.

11. Производные и допустимые правила в исчислении предикатов. Допустимость производных правил.

12. Примеры допустимых правил и теорем исчисления предикатов: правила Бернайса, монотонности для кванторов, контрапозиции, силлогизма; снятие двойного отрицания, переименование связанной переменной, взаимодействие кванторов с отрицанием.

13. Условие истинности для формулы с несколькими кванторами общности.

Универсальное замыкание формулы. Эквивалентность различных его вариантов.

14. Определение общезначимости для формулы с параметрами. Равносильные (эквивалентные) формулы. Равносильность как отношение эквивалентности на формулах.

15. Общезначимость пропозициональных аксиом исчисления предикатов.

16. Лемма о сложной подстановке для термов.

17. Лемма о сложной подстановке для формул.

18. Общезначимость кванторных аксиом исчисления предикатов. Теорема корректности для исчисления предикатов.

19. Логическое (семантическое) следование. Теорема корректности для теорий первого порядка. Противоречивые теории. Непротиворечивость выполнимых теорий.

20. Полные теории. Свойства полных теорий.

21. Лемма Линденбаума о расширении непротиворечивой теории до полной.

22. Лемма о свежей константе.

23. Теории Хенкина. Расширение непротиворечивой теории до непротиворечивой теории Хенкина.

24. Теорема о выполнимости непротиворечивой теории без равенства в счетной сигнатуре.

25. Теорема Гёделя о полноте для исчисления предикатов без равенства.

30. Теорема Гёделя о полноте для теорий без равенства: совпадение семантического и синтаксического следования. Теорема Лёвенгейма - Сколема для теорий без равенства в счетной сигнатуре.

31. Исчисление предикатов с равенством.

32. Нормальные интерпретации. Нормальная выполнимость и общезнаичмость.

Нормальная общезначимость аксиом равенства. Нормальное логическое следование. Теорема корректности для теорий 1-го порядка с равенством.

Непротиворечивость нормально выполнимых теорий.

33. Лемма о «нормализации» модели аксиом равенства.

34. Теорема о нормальной выполнимости непротиворечивой теории с равенством в счетной сигнатуре.

35. Теорема Гёделя о полноте для исчисления предикатов с равенством. Теорема Гёделя о полноте для теорий с равенством: совпадение нормального семантического и синтаксического следования. Теорема Лёвенгейма - Сколема для теорий с равенством.

36. Теорема Гёделя - Мальцева о компактности для теорий с равенством. Признак существования бесконечной модели.

37. Счетно категоричные теории. Признак полноты Вота. Примеры счетно категоричных теорий: теория неограниченных плотных линейных порядков; теория бесконечных множеств в сигнатуре равенства.

Формальная арифметика и вычислимость 38. Сигнатура арифметики. Арифметика Робинсона, арифметика Пеано; их непротиворечивость. Истинная арифметика.

39. Существование нестандартных моделей арифметики.

40. Нумералы. Некоторые теоремы о нумералах в арифметике Робинсона.

41. Примитивно рекурсивные и общерекурсивные функции. Примеры примитивно рекурсивных функций.



42. Примитивно рекурсивные предикаты. Ограниченные кванторы и ограниченные -операторы. Построение примитивно рекурсивных функций с помощью ограниченных сумм, ограниченных произведений, «разбором случаев».

43. Представимость числовой функции в арифметической теории (определение). Представимость базисных примитивно рекурсивных функций.

44. Сохранение представимости при подстановке представимых функций в представимую.

45. Сохранение представимости при применении (определенного) -оператора.

46. Примитивно рекурсивная нумерация пар натуральных чисел.

Восстановление пары по ее номеру.

47. Бета-функция Гёделя и ее свойства. Теорема о свойствах бета-функции в арифметике Робинсона.

48. Сохранение представимости при применении оператора примитивной рекурсии. Представимость общерекурсивных функций.

49. Примитивно рекурсивная нумерация кортежей натуральных чисел.

Функции длины (lh), соединения (), проектирования ([x]y ), начального 50. Машины Тьюринга. Определение вычислимой частичной функции Nk N.

Кодирование конфигураций машины натуральными числами.

51. Примитивно рекурсивная функция G(x,n), вычисляющая код конфигурации, полученной из конфигурации с кодом х за время n (для данной машины Тьюринга).

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

53. Частичная рекурсивность числовых функций, вычислимых по Тьюрингу.

54. Разрешимые множества. Сохранение разрешимости при булевых операциях.

55. Перечислимые множества (эквивалентные определения). Сохранение перечислимости при объединении и пересечении.

56. Теорема Поста (критерий разрешимости множества).

57. Сохранение перечислимости для образов и прообразов относительно вычислимых функций. Сохранение разрешимости для прообразов относительно вычислимых всюду определенных функций.

58. Кодирование машин Тьюринга. Теорема об универсальной машине Тьюринга (без док.). Теорема об универсальной вычислимой функции.

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

60. Арифметические множества. Арифметичность перечислимых множеств натуральных чисел.

61. Разрешимые и перечислимые множества слов. Теорема Поста для множеств слов.

62. Перечислимость множества теорем рекурсивно аксиоматизируемой теории первого порядка (в конечной сигнатуре).

63. Разрешимые теории первого порядка. Разрешимость полной рекурсивно аксиоматизируемой теории (в конечной сигнатуре).

64. Неперечислимость истинной арифметики. 1-я теорема Гёделя о неполноте.

65. Гёделевская нумерация арифметических формул. Теорема Клини Фефермана о неподвижной точке.

66. Существенная неразрешимость арифметики (теорема Тарского - Мостовского Робинсона). Теорема Чёрча о неразрешимости исчисления предикатов.

67. Теорема Тарского "о невыразимости истины". Неарифметичность истинной 68. Формальная доказуемость в арифметической теории. Формальная непротиворечивость. 2-я теорема Гёделя о неполноте.

ЛИТЕРАТУРА

1. Н.К. Верещагин, А.Х. Шень. Лекции по математической логике и теории алгоритмов. Часть 2: Языки и иcчисления. M., МЦНМО, 2000. http://www.mccme.ru 2. В.А. Успенский, Н.К. Верещагин, В.Е. Плиско. Вводный курс математической логики. Издательство МГУ. М., 1991 и 1997. Физматлит, 2002.

3. Справочная книга по математической логике под ред. Дж. Барвайса. Ч. 1.

Теория моделей. М., Наука, 1982.

4. Э. Мендельсон. Введение в математическую логику. М.,1984. 5. А.Н.Колмогоров, А.Г.Драгалин. Математическая логика. Серия "Классический университетский учебник", 2005.

6. В.Н. Крупский, В. Е. Плиско. Математическая логика и теория алгоритмов, Академия, 2013.

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

8. Дж. Шенфилд. Математическая логика. М., Наука, 1975.

9. С.К. Клини. Математическая логика. М., Мир, 1973.

10. С.К. Клини. Введение в метаматематику. М., ИЛ, 1957.





Похожие работы:

«ВЕСТНИК УДМУРТСКОГО УНИВЕРСИТЕТА 51 ФИЗИКА. ХИМИЯ 2012. Вып. 4 Неорганическая и аналитическая химия УДК 623.459: 504.054: 661.718 В.Г. Петров АНАЛИЗ ПРИМЕНЕНИЯ ТЕХНОЛОГИИ ВЫСОКОТЕМПЕРАТУРНОГО СЖИГАНИЯ ПРИ УНИЧТОЖЕНИИ ХИМИЧЕСКОГО ОРУЖИЯ В США Рассмотрено использование в США метода высокотемпературного сжигания отравляющих веществ при реализации Международной конвенции по химическому оружию. Показана высокая эффективность применения метода для уничтожения разных типов химических боеприпасов....»

«КАРДИОЛОГИЯ 2005 СПЕЦИАЛИЗИРОВАННАЯ ВЫСТАВКА И НАУЧНЫЙ ФОРУМ РОССИЙСКИЙ НАУЧНЫЙ ФОРУМ КАРДИОЛОГИЯ 2005 25 - 28 января МОСКВА Центр международной торговли ОРГАНИЗАТОРЫ ЗАО МЕДИ Экспо СОВМЕСТНО С Министерством здравоохранения и социального развития РФ Российской академией медицинских наук НИИ кардиологии им. проф. А.Л. Мясникова РКНПК МЗ РФ Государственным научно-исследовательским центром профилактической медицины МЗ РФ Национальным научно-пракСПЕЦИАЛИЗИРОВАННАЯ ВЫСТАВКА тическим обществом скорой...»

«УЧРЕЖДЕНИЕ РОССИЙСКОЙ АКАДЕМИИ НАУК ИНСТИТУТ НЕФТЕГАЗОВОЙ ГЕОЛОГИИ И ГЕОФИЗИКИ ИМ. А.А. ТРОФИМУКА СИБИРСКОГО ОТДЕЛЕНИЯ РАН УТВЕРЖДАЮ академик М.И. Эпов _ 23 декабря 2011 г. ОТЧЕТ о деятельности Учреждения Российской академии наук Института нефтегазовой геологии и геофизики им. А.А. Трофимука Сибирского отделения РАН в 2011 году Новосибирск 2011 ВАЖНЕЙШИЕ НАУЧНЫЕ ДОСТИЖЕНИЯ ОГЛАВЛЕНИЕ ОБЩИЕ СВЕДЕНИЯ Основные направления научной деятельности Структура Института Структура программ и проектов...»

«РАЗРАБОТАНА УТВЕРЖДЕНА Кафедрой аналитической Ученым советом и физической химии Химического факультета Протокол № 4 от 27.02.2014 Протокол № 8 от 13.03.2014 ПРОГРАММА ВСТУПИТЕЛЬНОГО ЭКЗАМЕНА для поступающих на обучение по программам подготовки научнопедагогических кадров в аспирантуре в 2014 году Направление подготовки 04.00.00 Химия Профиль подготовки 02.00.02 Аналитическая химия Астрахань – 2014 г. ПОЯСНИТЕЛЬНАЯ ЗАПИСКА В данной программе представлены вопросы для поступающих на обучение по...»

«ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ САРАТОВСКАЯ ГОСУДАРСТВЕННАЯ ЮРИДИЧЕСКАЯ АКАДЕМИЯ УТВЕРЖДАЮ Первый проректор, проректор по учебной работе _С.Н. Туманов 22 _июня_2012 г. УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС ПО ДИСЦИПЛИНЕ ТЕОРИЯ ГОСУДАРСТВА И ПРАВА по направлению подготовки (специальности) 031003 Судебная экспертиза квалификация (степень) специалист Саратов – Учебно-методический комплекс дисциплины обсужден на заседании кафедры теории...»

«  Тезисы  конференции  Энергия из биомассы: котельные и ТЭЦ на  биотопливе, производство пеллет,  брикетов, биогаза в России   19 июня 2014 г.  в рамках  II Российского Международного Энергетического Форума      есто проведения: CанктПетербруг, Ленэкспо, 6 павильон  М         Организаторы:   ИАА ИНФОБИО, журнал Международная биоэнергетика, ООО ЭФИнтернэшнл, НП  Биоэнергетический Союз    Информационные спонсоры: Биотопливный портал Woodpellets.com, выставочная компания MVK, ...»

«Приложение 1: Рабочая программа обязательной дисциплины История и философия науки ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ПЯТИГОРСКИЙ ГОСУДАРСТВЕННЫЙ ЛИНГВИСТИЧЕСКИЙ УНИВЕРСИТЕТ Утверждаю Проректор по научной работе и развитию интеллектуального потенциала университета профессор З.А. Заврумов _2012 г. Аспирантура по специальности 10.02.20 Сравнительно-историческое, типологическое и сопоставительное языкознание отрасль науки: 10.00.00...»

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

«Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования РОССИЙСКАЯ АКАДЕМИЯ НАРОДНОГО ХОЗЯЙСТВА И ГОСУДАРСТВЕННОЙ СЛУЖБЫ при ПРЕЗИДЕНТЕ РОССИЙСКОЙ ФЕДЕРАЦИИ ВФ РАНХиГС г. Воронеж Факультет (институт) Международно-правовой Специальность 032301.65 Регионоведение Специализация Западная Европа Кафедра Региональных и международных отношений РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ ПРОЦЕСС ФОРМИРОВАНИЯ ВНЕШНЕЙ ПОЛИТИКИ И ДИПЛОМАТИЯ (наименование дисциплины)...»

«Пояснительная записка Настоящая рабочая программа по географии разработана как нормативно-правовой документ для организации учебного процесса в Муниципальном казенном общеобразовательном учреждении Толпинская средняя общеобразовательная школа. Содержательный статус программы – базовая. Она определяет минимальный объем содержания курса география для основной школы и предназначена для реализации требований ФГОС второго поколения к условиям и результату образования обучающихся основной школы по...»

«П 151-2.5.13 - 2010 ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение высшего профессионального образования ПЕНЗЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ (ПГУ) МЕДИЦИНСКИЙ ИНСТИТУТ КАФЕДРА ТЕРАПИЯ ПОЛОЖЕНИЕ О СТРУКТУРНОМ ПОДРАЗДЕЛЕНИИ П 151-2.5.13 - 2010 ПОЛОЖЕНИЕ О КАФЕДРЕ ТЕРАПИИ 1 Пе нз а – 2 01 0 П 151-2.5.13 - 2010 ПЕНЗЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПОЛОЖЕНИЕ О ПОДРАЗДЕЛЕНИИ П 151-2.5.13- ПОЛОЖЕНИЕ О КАФЕДРЕ ТЕРАПИИ Дата введения 2010-11- 1 Основное назначение...»

«МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Саратовский государственный аграрный университет имени Н.И. Вавилова РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ (МОДУЛЯ) Дисциплина ИНОСТРАННЫЙ ЯЗЫК (АНГЛИЙСКИЙ) Направление подготовки 111100.68 Зоотехния Технология производства продуктов Магистерская программа животноводства Квалификация (степень) Магистр выпускника Нормативный срок 2 года обучения...»

«Учреждение Российской академии наук Уральское отделение РАН ОТЧЕТ о научной и научно-организационной деятельности Учреждения Российской академии наук Института горного дела Уральского отделения РАН за 2009 год УТВЕРЖДЕН ОДОБРЕН Объединенным ученым Ученым советом Советом УрО РАН Института горного дела по наукам о Земле 25 декабря 2009 г. _2010 г. Протокол № 13 Протокол №_ Председатель Совета Директор института, Академик проф., д.т.н. _В.А.Коротеев С.В.Корнилков Ученый секретарь института,...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ ХАБАРОВСКОГО КРАЯ КРАЕВОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ НАЧАЛЬНОГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ПРОФЕССИОНАЛЬНОЕ УЧИЛИЩЕ № 6 РАБОЧАЯ ПРОГРАММА УЧЕБНОЙ ДИСЦИПЛИНЫ ОП 02. МАТЕРИАЛОВЕДЕНИЕ 2011 г 1 Рабочая программа учебной дисциплины разработана на основе Федерального государственного образовательного стандарта (далее – ФГОС) по профессии начального профессионального образования (далее НПО) 270802.08 Мастер сухого строительства...»

«РЕГЛАМЕНТ ЧЕМПИОНАТА ЕВРОПЫ ПО ФУТБОЛУ СРЕДИ ДЕВУШЕК ВОЗРАСТНОЙ КАТЕГОРИИ ДО 17 ЛЕТ 2013/14 СОДЕРЖАНИЕ Преамбула I Общие положения Статья 1 Сфера применения Применение существительных женского и мужского рода Кубок мира по футболу среди девушек возрастной категории до 17 лет под эгидой ФИФА II Условия участия – Допуск – Обязанности и обязательства Статья 2 Условия участия Критерии допуска Процедура допуска Обязанности и обязательства ассоциаций III Кубок – Медали – Приз за честную игру Статья 3...»

«Программа кандидатского экзамена по специальности 10.02.04 Германские языки Место кандидатского экзамена по специальности Германские языки в структуре образовательной программы Дисциплина Английский язык (ОД.А.02) является неотъемлемым компонентом блока обязательных дисциплин (ОД.А.00). Основные знания, полученные в ходе освоения дисциплины, имеют целью подготовить аспиранта (соискателя) к сдаче кандидатского экзамена по английскому языку (КЭ.А.02), входящего в блок исследовательской...»

«АКАДЕМИЯ УПРАВЛЕНИЯ ПРИ ПРЕЗИДЕНТЕ РЕСПУБЛИКИ БЕЛАРУСЬ ИНСТИТУТ УПРАВЛЕНЧЕСКИХ КАДРОВ УТВЕРЖДАЮ Проректор по учебной работе – директор Института управленческих кадров И. И. Ганчеренок.. 2013 Регистрационный № /р. ФОРМЫ И МЕТОДЫ ИДЕОЛОГИЧЕСКОЙ РАБОТЫ В ТРУДОВЫХ КОЛЛЕКТИВАХ Учебная программа для специальности: 1-26 01 03 Государственное управление и экономика первой ступени высшего образования Факультет управления Кафедра философских наук и идеологической работы Курс (курсы) Семестр (семестры)...»

«ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ САРАТОВСКАЯ ГОСУДАРСТВЕННАЯ ЮРИДИЧЕСКАЯ АКАДЕМИЯ УТВЕРЖДАЮ Первый проректор, проректор по учебной работе _С.Н. Туманов __2012 г. УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС ДИСЦИПЛИНЫ Экологическое право по специальности 030201.65 Политология Составители: доцент, к.ю.н. Сорокина Ю.В., доцент, к.ю.н. Абанина Е.Н. Саратов Учебно-методический комплекс дисциплины обсужден на заседании кафедры земельного и...»

«ПРОГРАММА ВСТУПИТЕЛЬНЫХ ИСПЫТАНИЙ ДЛЯ ПОСТУПАЮЩИХ В МАГИСТРАТУРУ. Математический анализ. 1. Производные и дифференциалы функций одной и нескольких переменных. Основные теоремы о непрерывных и дифференцируемых функциях. Формула Тейлора. 2. Интегралы: определенный, двойной, тройной, криволинейные, поверхностные. (Определения, свойства, формулы для вычисления). 3. Числовые и функциональные ряды. Признаки сходимости. Равномерная сходимость функциональных рядов. Ряд и интеграл Фурье. 4. Основные...»

«Приложение 7Б: Рабочая программа дисциплины по выбору Региональная экономика ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ПЯТИГОРСКИЙ ГОСУДАРСТВЕННЫЙ ЛИНГВИСТИЧЕСКИЙ УНИВЕРСИТЕТ Утверждаю Проректор по научной работе и развитию интеллектуального потенциала университета профессор З.А. Заврумов _2012 г. Аспирантура по специальности 08.00.05 Экономика и управление народным хозяйством отрасль науки: 08.00.00 Экономические науки Кафедра...»






 
2014 www.av.disus.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Программы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.