- •Зачем обучать математике (мнение в. Успенского). Демократичность математики.
- •Что такое логика. Примеры ошибок в логических рассуждениях. Формальная логика Аристотеля. Переход от формальной логики к математической. Что такое математическая логика?
- •Существует ли математический мир независимо от нас или создается нами? – два мнения. Математики открывают или изобретают? Сущность математики (точка зрения н. Н. Непейводы).
- •Зачем Вам изучать формальный язык? Значение математической логики для программирования.
- •Парадоксы. Что является источником парадоксов в математике. Парадокс лжеца. Парадокс Сократа и Платона. Парадокс Альберта Саксонского. Значение парадоксов для математики.
- •Парадоксы. Что является источником парадоксов в математике. Парадокс Берри. Парадокс брадобрея. Значение парадоксов для математики.
- •Парадоксы. Что является источником парадоксов в математике. Парадокс о прямом и противоположном утверждение. Парадокс о прямоугольнике с числами. Значение парадоксов для математики.
- •Задача о двух шкатулках. Логика и реальный мир.
- •Что такое высказывание? Атомарные и сложные высказывания. Соглашение об истинностных значениях высказываний. Соглашение об истинностном значении сложного высказывания.
- •Формальный язык. Предметы и универсум. Константы и переменные. Функции. Термы. Отношения и предикаты. Элементарные формулы. Сложные формулы. Интерпретация формул.
- •Примеры нестандартной оценки истинности автореферентных (самоссылочных высказываний). Пример Клини для конъюнкции. Примеры для отрицания.
- •Логические связки: эквиваленция, импликация (обоснование таблицы истинности для импликации). Какие утверждения при переводе на формальный язык используют импликацию и эквиваленцию.
- •Логические связки: квантор общности и квантор существования. Язык первого порядка.
- •Как переводить высказывания на формальный язык.
- •Равенство. Основной закон равенства. Как представить единственность и не единственность на формальном языке.
- •Пропозициональные формулы. Таблицы истинности.
- •Тавтологии, противоречия и выполнимые формулы. Примеры тавтологий.
- •Как доказывать, что данная формула является тавтологией. Два способа.
- •Равносильные формулы. Примеры равносильностей. Способы доказательств равносильностей.
- •Теорема о равносильных преобразованиях (с доказательством).
- •Интуитивная теория множеств. Принцип абстракции и принцип объемности. Как доказывать равенство множеств?
- •Отношение включения. Пустое множество. Множество–степень. Парадокс Бертрана Рассела и его значение.
- •Операции над множествами: объединение, пересечение, относительное дополнение, симметрическая разность, абсолютное дополнение. Значение диаграмм Эйлера.
- •Основные булевы тождества для операций над множествами. Как их доказывать.
- •Упорядоченные пары и n-ки. Прямое произведение множеств. Отношения. Область определения и область значений отношения. Обратное отношение.
- •Композиция отношений. Определения рефлексивности, симметричности, транзитивности и антисимметричности. Примеры отношений.
- •Отношение эквивалентности. Примеры. Классы эквивалентности. Свойства классов эквивалентностей.
- •Разбиения множеств. Связь разбиения множества и отношения эквивалентности. Фактор–множество.
- •Частичный порядок. Линейный порядок. Примеры.
- •Определение функции. N-местные функции. Инъективность, сюръективностьь и биективность. Примеры.
- •Обратное отображение. Теорема о существовании обратного отображения (доказательство). Примеры.
- •Определение формальной теории. Выводимость. Доказуемые формулы.
- •Примеры формальных теорий. Теоремы и метатеоремы.
- •Математическая индукция. Индуктивные определения. Принцип индукции по построению объекта. Пример доказательства с математической индукцией.
- •Неформальное определение доказательства. Использование доказательства в математике. Виды доказательств.
- •Доказательство контрпримером. Доказательство от противного. Пример доказательства.
- •Понятие алгоритма и неформальная вычислимость.
- •Определение частично–рекурсивных функций. Базисные функции.
- •Операции суперпозиции, примитивной рекурсии и минимизации.
- •Примитивно–рекурсивные и частично–рекурсивные функции. Функция Аккермана.
- •Машины Тьюринга.
- •Альтернативные способы формализации понятия алгоритма и вычислимых функций. Основной результат. Тезис Чёрча.
- •Некоторые алгоритмически неразрешимые проблемы.
- •Сравнение скорости роста функций (o – большое). Сводка результатов о сравнении функций.
- •Асимптотическая временная сложность алгоритмов.
- •Что больше влияет на максимальный размер задачи, которую мы можем решить: скорость вычисления или сложность алгоритма?
- •Сложность задач.
- •Классификация задач по их сложности. Задачи полиномиальной сложности и задачи экспоненциальной сложности.
- •Задачи, не попадающие ни в класс e, ни в класс p.
-
Парадоксы. Что является источником парадоксов в математике. Парадокс Берри. Парадокс брадобрея. Значение парадоксов для математики.
Парадоксом называется утверждение, из истинности которого следует его ложность, а из ложности – истинность.
• Неограниченное использование естественного языка в математике приводит к парадоксам.
• Парадокс Берри (библиотекарь Оксфордского университета,1906 г.): Как известно, некоторые фразы служат определениями натуральных чисел, например: «Десять в степени десять» – число 10000000000 или «Наименьшее простое число, большее миллиона» – число 1000003. В русском языке 33 буквы, и предложений, состоящих не более чем из ста букв, конечное число (грубо говоря, не более 33 в степени 100). Натуральных же чисел же бесконечно много. Значит, среди них должны быть такие, которые нельзя назвать фразой, состоящей менее чем из ста букв. Но тогда есть и наименьшее такое число. Его можно определить как: «Наименьшее натуральное число, которое нельзя определить предложением русского языка, содержащим менее ста букв». Это предложение содержит 96 букв. Следовательно, данное определение противоречит самому себе.
• Парадокс Рассела возник в теории множеств (современный фундамент математики). Нематематическая форма этого парадокса – парадокс
брадобрея: Владелец парикмахерской в одном селе повесил следующее объявление: «Брею тех и только тех жителей села, кто не бреется сам». Спрашивается, кто бреет брадобрея?
Появление первых парадоксов ошеломило математический мир и послужило поводом, чтобы предпринять систематическое построение математической логики.
-
Парадоксы. Что является источником парадоксов в математике. Парадокс о прямом и противоположном утверждение. Парадокс о прямоугольнике с числами. Значение парадоксов для математики.
Парадоксом называется утверждение, из истинности которого следует его ложность, а из ложности – истинность.
• Неограниченное использование естественного языка в математике приводит к парадоксам.
• Прямое и противоположное утверждения. Это предложение: 1) Это предложение содержит шесть слов 2) Это предложение не содержит шесть слов. Два утверждения в рамочках являются взаимно исключающими утверждения. Значит одно из них истинно, а другое ложно. Какое именно?
• Прямоугольник с числами Запишем в прямоугольнике следующие четыре числа: 1,2,3,” наименьшее не записанное в этом прямоугольнике целое положительное число”
Теорема. Этот прямоугольник содержит записи всех целых положительных чисел.
Доказательство. От противного. Пусть прямоугольник не содержит записи всех целых положительных чисел. Тогда существует x – наименьшее не записанное в данном прямоугольнике число; но запись о x присутствует в данном прямоугольнике. Мы пришли к противоречию.
Появление первых парадоксов ошеломило математический мир и послужило поводом, чтобы предпринять систематическое построение математической логики.
-
Парадоксы. Что является источником парадоксов в математике. Парадокс о крокодиле. Парадокс о неожиданной контрольной. Парадокс Гемпеля. Значение парадоксов для математики.
Парадоксом называется утверждение, из истинности которого следует его ложность, а из ложности – истинность.
• Неограниченное использование естественного языка в математике приводит к парадоксам.
• Крокодил У одной египтянки крокодил похитил ребенка. Египтянка просила вернуть ребенка, и крокодил обещал ей это, если она правильно укажет, как поступит крокодил. Мать ребенка сказала: «Ты не возвратишь мне моего ребенка». На это крокодил ответил: «Если ты, действительно, права, то ты, как сама говоришь, не получишь назад ребенка; если же твое высказывание неверно, то, согласно нашему уговору, ты не получишь ребенка. В любом случае ребенок должен остаться у меня». «Наоборот – возразила женщина, – если мое высказывание верно, то я получу ребенка назад в силу нашего условия; если же я ошиблась, то это означает, что ты сам вернешь мне ребенка. В каждом из случаев я получу ребенка назад». Кто из них прав?
• Неожиданная контрольная Учитель говорит своим ученикам, что на следующей недели их ожидает контрольная. Однако он не сообщает им, в какой день будет проведена эта проверка. Проверка должна быть для них неожиданной. Но будет ли она неожиданной? Можно ли провести проверку в субботу? Нет, нельзя, Если до этого дня контрольной не было, то ученики будут ожидать ее именно в этот день. В субботу контрольная не будет неожиданной. Ну а как насчет пятницы? Ученики знают, что в субботу контрольная состояться не может. Поэтому если ее не было в предшествующие
дни, ученики будут ожидать ее в пятницу. В пятницу контрольная также не будет неожиданной. Аналогичное рассуждение показывает, что контрольная не будет неожиданной, если состоится в четверг, среду, вторник и понедельник. Учитель не может провести неожиданную контрольную.
• Контрольная состоялась в среду и была неожиданной для учеников.
• Парадокс К. Гемпеля
• Как действует наука? Ученые создают теории, затем подтверждают наблюдениями.
• Возьмем общее утверждение о том, что все вороны черные. Все обобщения подтверждаются их конкретными частными случаями. Поэтому, наблюдение каждой черной вороны подтверждают в какой-то степени гипотезу о том, что все вороны черного цвета.
• Если две гипотезы логически эквивалентны, то подтверждение одной гипотезы является также подтверждением другой гипотезы.
• Гипотеза «Все вороны черные» логически эквивалентна гипотезе «Все не-черные предметы являются не-воронами».
• Поэтому и зеленые рубашки, и красные маки, и голубые небеса, будучи не-черными не-воронами, подтверждают гипотезу «Все вороны черные».
• Следовательно биолог может не выходить из кабинета, чтобы получить множество подтверждающих примеров гипотезы «Все вороны черные».
Появление первых парадоксов ошеломило математический мир и послужило поводом, чтобы предпринять систематическое построение математической логики.