- •Зачем обучать математике (мнение в. Успенского). Демократичность математики.
- •Что такое логика. Примеры ошибок в логических рассуждениях. Формальная логика Аристотеля. Переход от формальной логики к математической. Что такое математическая логика?
- •Существует ли математический мир независимо от нас или создается нами? – два мнения. Математики открывают или изобретают? Сущность математики (точка зрения н. Н. Непейводы).
- •Зачем Вам изучать формальный язык? Значение математической логики для программирования.
- •Парадоксы. Что является источником парадоксов в математике. Парадокс лжеца. Парадокс Сократа и Платона. Парадокс Альберта Саксонского. Значение парадоксов для математики.
- •Парадоксы. Что является источником парадоксов в математике. Парадокс Берри. Парадокс брадобрея. Значение парадоксов для математики.
- •Парадоксы. Что является источником парадоксов в математике. Парадокс о прямом и противоположном утверждение. Парадокс о прямоугольнике с числами. Значение парадоксов для математики.
- •Задача о двух шкатулках. Логика и реальный мир.
- •Что такое высказывание? Атомарные и сложные высказывания. Соглашение об истинностных значениях высказываний. Соглашение об истинностном значении сложного высказывания.
- •Формальный язык. Предметы и универсум. Константы и переменные. Функции. Термы. Отношения и предикаты. Элементарные формулы. Сложные формулы. Интерпретация формул.
- •Примеры нестандартной оценки истинности автореферентных (самоссылочных высказываний). Пример Клини для конъюнкции. Примеры для отрицания.
- •Логические связки: эквиваленция, импликация (обоснование таблицы истинности для импликации). Какие утверждения при переводе на формальный язык используют импликацию и эквиваленцию.
- •Логические связки: квантор общности и квантор существования. Язык первого порядка.
- •Как переводить высказывания на формальный язык.
- •Равенство. Основной закон равенства. Как представить единственность и не единственность на формальном языке.
- •Пропозициональные формулы. Таблицы истинности.
- •Тавтологии, противоречия и выполнимые формулы. Примеры тавтологий.
- •Как доказывать, что данная формула является тавтологией. Два способа.
- •Равносильные формулы. Примеры равносильностей. Способы доказательств равносильностей.
- •Теорема о равносильных преобразованиях (с доказательством).
- •Интуитивная теория множеств. Принцип абстракции и принцип объемности. Как доказывать равенство множеств?
- •Отношение включения. Пустое множество. Множество–степень. Парадокс Бертрана Рассела и его значение.
- •Операции над множествами: объединение, пересечение, относительное дополнение, симметрическая разность, абсолютное дополнение. Значение диаграмм Эйлера.
- •Основные булевы тождества для операций над множествами. Как их доказывать.
- •Упорядоченные пары и n-ки. Прямое произведение множеств. Отношения. Область определения и область значений отношения. Обратное отношение.
- •Композиция отношений. Определения рефлексивности, симметричности, транзитивности и антисимметричности. Примеры отношений.
- •Отношение эквивалентности. Примеры. Классы эквивалентности. Свойства классов эквивалентностей.
- •Разбиения множеств. Связь разбиения множества и отношения эквивалентности. Фактор–множество.
- •Частичный порядок. Линейный порядок. Примеры.
- •Определение функции. N-местные функции. Инъективность, сюръективностьь и биективность. Примеры.
- •Обратное отображение. Теорема о существовании обратного отображения (доказательство). Примеры.
- •Определение формальной теории. Выводимость. Доказуемые формулы.
- •Примеры формальных теорий. Теоремы и метатеоремы.
- •Математическая индукция. Индуктивные определения. Принцип индукции по построению объекта. Пример доказательства с математической индукцией.
- •Неформальное определение доказательства. Использование доказательства в математике. Виды доказательств.
- •Доказательство контрпримером. Доказательство от противного. Пример доказательства.
- •Понятие алгоритма и неформальная вычислимость.
- •Определение частично–рекурсивных функций. Базисные функции.
- •Операции суперпозиции, примитивной рекурсии и минимизации.
- •Примитивно–рекурсивные и частично–рекурсивные функции. Функция Аккермана.
- •Машины Тьюринга.
- •Альтернативные способы формализации понятия алгоритма и вычислимых функций. Основной результат. Тезис Чёрча.
- •Некоторые алгоритмически неразрешимые проблемы.
- •Сравнение скорости роста функций (o – большое). Сводка результатов о сравнении функций.
- •Асимптотическая временная сложность алгоритмов.
- •Что больше влияет на максимальный размер задачи, которую мы можем решить: скорость вычисления или сложность алгоритма?
- •Сложность задач.
- •Классификация задач по их сложности. Задачи полиномиальной сложности и задачи экспоненциальной сложности.
- •Задачи, не попадающие ни в класс e, ни в класс p.
-
Задача о двух шкатулках. Логика и реальный мир.
У Порции из комедии Шекспира «Венецианский купец» было три шкатулки: из золота, серебра и свинца. В одной из шкатулок хранился портрет Порции. Поклоннику предлагалось выбрать шкатулку, и если он был достаточно удачлив (или достаточно умен), чтобы выбрать шкатулку с портретом, то получал право назвать Порцию своей невестой. На крышках шкатулок она приказала сделать надписи и пояснила поклоннику, что, что из трех высказываний, написанных на шкатулках, по крайней мере два ложны. Какую шкатулку выбрать? На золотой: портрет в этой шкатулке. портрет в этой шкатулке. На серебряной: портрет не в этой шкатулке. На свинцовой: портрет не в золотой шкатулке. Пра-пра-внучка Порции (тоже Порция) решила подвергнуть претендента на ее руку и сердце аналогичному испытанию. Порция заказала две шкатулки, серебряную и золотую, и в одну из них положила свой портрет. На крышках шкатулок красовались надписи: На золотой: Портрет не в этой шкатулке. На серебряной: Ровно одно из двух высказываний, выгравированных на крышках, истинно. Каково же было удивление поклонника, когда он открыл золотую шкатулку и не обнаружил портрета. Портрет оказался в серебряной шкатулке. Где в рассуждения претендента и в наше решение вкралась ошибка?
• Кто нам мешает взять любое число шкатулок и портретов и разложить портреты произвольным образом по шкатулкам? Дополнительно, мы можем написать произвольные надписи на шкатулках. Не зная ничего об истинности или ложности надписей, мы не можем прийти к какому-либо заключению.
• С самого начала в нашем решении предполагается, что надпись, выгравированная на серебряной шкатулке, либо истинна, либо ложна и других вариантов нет. Да, конечно, в классической логике у истинности всего два значения.
• Но математическая логика всего лишь модель логических отношений, и в данном случае надпись на серебряной шкатулке не может быть ни истинной, ни ложной, ибо в любом случае мы приходим к противоречию с реальным положением вещей (точнее, положением портрета в шкатулках).
• Не следует думать, что если бы мы использовали трехзначную логику (или еще какую-нибудь), то мы смогли бы найти портрет.
• Об отношении логики к реальному миру говорит следующая цитата из Ю. И. Манина («Доказумое и недоказуемое»):
«Предметом логики является не внешний мир, но лишь системы его осмысливания. Логика одной из таких систем – математики – в силу своей нормализованности представляет подобие жесткого трафарета, который можно накладывать на любую другую систему. Соответствие или расхождение этого трафарета с системой, однако, не служит критерием ее пригодности либо мерилом ценности».
• Альберт Эйнштейн: «Законы мышления, имеющие какое-либо отношение к реальному миру, ненадежны; а надежные математические законы не имеют отношения к реальному миру».
-
Что такое высказывание? Атомарные и сложные высказывания. Соглашение об истинностных значениях высказываний. Соглашение об истинностном значении сложного высказывания.
• Высказывание – утверждение об объектах, имеющее однозначный, точно определенный смысл.
• Это определение, конечно же, не математическое. С чисто математической точки зрения понятия высказывания и объекта являются исходными, но содержательно мы все равно должны описать, что же такое высказывание. Ведь и исходные понятия мы должны понимать.
• Атомарными, элементарными высказываниями естественно можно считать такие, которые сообщают какой-то единичный факт. Сложные высказывания образуются из простых применением двух видов операций.
• Логические связки применяются к высказываниям и в результате дают новое высказывание. Например, это «не только…, но и …», или просто конструкция сложноподчиненного предложения, как в 15.
• Кванторные конструкции применяются к совокупности однородных, отличающихся лишь значениями некоторых параметров) высказываний либо выражений и дают единое высказывание либо выражение, не зависящее от упомянутого параметра. Например, таковы «Все…», «Хотя бы один…».
Соглашения
1. Имеются исходные неопределяемые понятия истина и ложь (обозначения: 1 и 0, или И и Л, или T и F), которые являются истинностными (логическими) значениями высказываний.
2. Логическое значение сложного утверждения зависит лишь от логических значений его компонент, а не от его смысла.
Примеры высказываний: 1. 2×2 = 4; 2. 2×2 = 5; 3. sin π = 0; 4. Волга впадает в Каспийское море.; 5. Волга впадает в Балтийское море.; 6. Существует бесконечно много простых чисел–близнецов.; 7. Для всякого натурального числа найдется превосходящее его простое число.; 8. 12 января 2002 года в 11.35 на перекрестке ул. Учебной и пр. Ленина автомобилем «Тайота», принадлежащим гр. Хасбулатову, находившемуся в состоянии опьянения средней степени, был сбит гр. Иванов Иван Иванович, получивший тяжкие телесные повреждения.; 9. Не только Иванов, но и Петров прогулял сегодняшнюю лекцию.; 10. По словам Сталина, Троцкий был врагом СССР.; 11. Все волки – млекопитающие.; 12. Простых чисел бесконечно много.;
13. Геракл очистил Авгиевы конюшни.; 14. У русалок зеленые волосы.; 15. Рим расположен на реке Тибр, основан, согласно Титу Ливию, Ромулом и находится под особым покровительством Юпитера.
• Безусловно, истинные высказывания – 1, 3, 7.
• Безусловно, ложные высказывания - – 2, 5.
• Истинность высказывания иногда трудно установить – истинность высказывания 7 следует из теоремы Евклида; истинность 6 до сих пор не известна.
• Некоторые высказывания говорят не об одном факте, а о целом множестве утверждений (такие высказывания называются общими) – 11, 12.
• Истинность или ложность высказывания может иметь место в некотором «возможном мире» – 13 (традиционно считается истинным).
• Иногда высказывание относится не столько к сообщаемому факту, сколько к его оценке – 10.
• В сложном высказывании могут быть перемешены реальность, воображаемые миры и его оценка – 15.
• Высказывания могут быть достаточно сложными с точки зрения грамматики – 8.