Вопросы к экзамену

Все темы данного раздела:

Образцы экзаменационных билетов
  Билет № 1 1. Дедуктивный характер математики. Предмет математической логики, ее роль в вопросах обоснования математики. 2. Формальные теории (как строится формальн

АКСИОМАТИЧЕСКИЕ ТЕОРИИ
  Рассматривается аксиоматический метод построения математических теорий. Обсуждаются свойства непротиворечивости и полноты аксиоматических теорий.   Греки п

Понятие аксиоматической теории
  На уроке геометрии. Учитель: «Для чего мы изучаем аксиомы?» Ученик: «Чтобы их не доказывать».   Аксиоматический метод не является достижением

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

Интерпретации и модели аксиоматической теории
Формулируя аксиомы в примерах предыдущего пункта, нами не учитывалась природа элементов тех множеств, которые там встречаются, а также природа других первоначальных понятий этих аксиоматических тео

Свойства аксиоматических теорий
Первый вопрос, который возникает, когда рассматривается та или иная аксиоматическая теория, - это вопрос о непротиворечивости, и полноте аксиоматической теории. Непротиворечивость является

Упражнения
5.1. Докажите непротиворечивость аксиоматической теории порядка – теории с одним бинарным отношением a, удовлетворяющим аксиомам транзитивности и антисимметричности. 5.2. Докажите н

Формулировка аксиоматической теории
В этом параграфе вводится понятия формулировки теории и независимости системы аксиом. Как уже говорилось, неформальная теория T включает в себя некоторый список

Упражнения
1. Докажите независимость множества аксиом {B1, B2, B3} теории эквивалентности (пример 3.2). 2. Проверьте на независимость системы аксиом а

Интуитивное понятие алгоритма
Человек ежедневно встречается с множеством задач, возникающих в различных областях деятельности общества, например: a) подготовиться к уроку по математике; b) приготовить раствор

Упражнения
1.1. Составьте алгоритм сложения столбиком двух натуральных чисел. 1.2. Опишите правила перехода улицы для случаев: а) перекресток регулируемый; б) перекресток нерегулиру

Свойства алгоритмов
Рассмотренные примеры показывают, что выполнение алгоритма разбивается на последовательность законченных действий-шагов. Каждое действие должно быть закончено исполнителем прежде, чем он приступит

Уточнение понятия алгоритма
«То, что вообще может быть сказано, может быть сказано ясно, а о чем невозможно говорить - о том следует молчать». Людвиг Витгенштейн (Эпиграф, предпосланный изложению языка про

Упражнения
3.2. Составьте алгоритмы, вычисляющие функции: а) б)

Нумерация программ для МНР
Определение 4.1. Множество X называют счетным, если можно установить взаимно однозначное отображение

Нумерация вычислимых функций
Определение 5.1. Пусть f – n-местная функция, вычислимая по программе P с геделевым номером m = g(P). Число m будем называть индексом функции f

Универсальные программы
В этом разделе мы докажем несколько неожиданный результат, состоящий в том, что существуют универсальные программы, то есть программы, которые в некотором смысле реализуют все другие программы. Это

Алгоритмически неразрешимые проблемы
Основным стимулом, приведшим к выработке понятия алгоритма и созданию теории алгоритмов, явилась потребность доказательства неразрешимости многих проблем, возникших в различных областях математики.

S-m-n-теорема
В этом разделе мы докажем теорему, принадлежащую к числу основных результатов теории алгоритмов. Суть теоремы в следующем. Допустим, что f(х, у) - вычислимая функция. Для каждого фикс

Упражнения
8.1. Докажите, что не существует алгоритма, определяющего по тексту программы, будет ли эта программа вычислять некоторую конкретную вычислимую функцию. 8.2. 2. Покажите, что не существует