- •Зачем обучать математике (мнение в. Успенского). Демократичность математики.
- •Что такое логика. Примеры ошибок в логических рассуждениях. Формальная логика Аристотеля. Переход от формальной логики к математической. Что такое математическая логика?
- •Существует ли математический мир независимо от нас или создается нами? – два мнения. Математики открывают или изобретают? Сущность математики (точка зрения н. Н. Непейводы).
- •Зачем Вам изучать формальный язык? Значение математической логики для программирования.
- •Парадоксы. Что является источником парадоксов в математике. Парадокс лжеца. Парадокс Сократа и Платона. Парадокс Альберта Саксонского. Значение парадоксов для математики.
- •Парадоксы. Что является источником парадоксов в математике. Парадокс Берри. Парадокс брадобрея. Значение парадоксов для математики.
- •Парадоксы. Что является источником парадоксов в математике. Парадокс о прямом и противоположном утверждение. Парадокс о прямоугольнике с числами. Значение парадоксов для математики.
- •Задача о двух шкатулках. Логика и реальный мир.
- •Что такое высказывание? Атомарные и сложные высказывания. Соглашение об истинностных значениях высказываний. Соглашение об истинностном значении сложного высказывания.
- •Формальный язык. Предметы и универсум. Константы и переменные. Функции. Термы. Отношения и предикаты. Элементарные формулы. Сложные формулы. Интерпретация формул.
- •Примеры нестандартной оценки истинности автореферентных (самоссылочных высказываний). Пример Клини для конъюнкции. Примеры для отрицания.
- •Логические связки: эквиваленция, импликация (обоснование таблицы истинности для импликации). Какие утверждения при переводе на формальный язык используют импликацию и эквиваленцию.
- •Логические связки: квантор общности и квантор существования. Язык первого порядка.
- •Как переводить высказывания на формальный язык.
- •Равенство. Основной закон равенства. Как представить единственность и не единственность на формальном языке.
- •Пропозициональные формулы. Таблицы истинности.
- •Тавтологии, противоречия и выполнимые формулы. Примеры тавтологий.
- •Как доказывать, что данная формула является тавтологией. Два способа.
- •Равносильные формулы. Примеры равносильностей. Способы доказательств равносильностей.
- •Теорема о равносильных преобразованиях (с доказательством).
- •Интуитивная теория множеств. Принцип абстракции и принцип объемности. Как доказывать равенство множеств?
- •Отношение включения. Пустое множество. Множество–степень. Парадокс Бертрана Рассела и его значение.
- •Операции над множествами: объединение, пересечение, относительное дополнение, симметрическая разность, абсолютное дополнение. Значение диаграмм Эйлера.
- •Основные булевы тождества для операций над множествами. Как их доказывать.
- •Упорядоченные пары и n-ки. Прямое произведение множеств. Отношения. Область определения и область значений отношения. Обратное отношение.
- •Композиция отношений. Определения рефлексивности, симметричности, транзитивности и антисимметричности. Примеры отношений.
- •Отношение эквивалентности. Примеры. Классы эквивалентности. Свойства классов эквивалентностей.
- •Разбиения множеств. Связь разбиения множества и отношения эквивалентности. Фактор–множество.
- •Частичный порядок. Линейный порядок. Примеры.
- •Определение функции. N-местные функции. Инъективность, сюръективностьь и биективность. Примеры.
- •Обратное отображение. Теорема о существовании обратного отображения (доказательство). Примеры.
- •Определение формальной теории. Выводимость. Доказуемые формулы.
- •Примеры формальных теорий. Теоремы и метатеоремы.
- •Математическая индукция. Индуктивные определения. Принцип индукции по построению объекта. Пример доказательства с математической индукцией.
- •Неформальное определение доказательства. Использование доказательства в математике. Виды доказательств.
- •Доказательство контрпримером. Доказательство от противного. Пример доказательства.
- •Понятие алгоритма и неформальная вычислимость.
- •Определение частично–рекурсивных функций. Базисные функции.
- •Операции суперпозиции, примитивной рекурсии и минимизации.
- •Примитивно–рекурсивные и частично–рекурсивные функции. Функция Аккермана.
- •Машины Тьюринга.
- •Альтернативные способы формализации понятия алгоритма и вычислимых функций. Основной результат. Тезис Чёрча.
- •Некоторые алгоритмически неразрешимые проблемы.
- •Сравнение скорости роста функций (o – большое). Сводка результатов о сравнении функций.
- •Асимптотическая временная сложность алгоритмов.
- •Что больше влияет на максимальный размер задачи, которую мы можем решить: скорость вычисления или сложность алгоритма?
- •Сложность задач.
- •Классификация задач по их сложности. Задачи полиномиальной сложности и задачи экспоненциальной сложности.
- •Задачи, не попадающие ни в класс e, ни в класс p.
-
Частичный порядок. Линейный порядок. Примеры.
Элементы многих множеств можно разместить в определенном порядке на основе некоторого, заранее оговоренного соглашения. Например, на любом подмножестве A множества целых положительных чисел можно договориться о таком расположении элементов, при котором меньшие элементы будут находиться левее больших. При этом можно сказать, что на множестве A определено отношение порядка x ρ y, где ρ есть отношение «меньше или равно».
Частичный порядок Рефлексивное, транзитивное и антисимметричное отношение на множестве X называется отношением частичного порядка на множестве X .
Линейный порядок Отношение частичного порядка ρ на множестве X, для которого любые два элемента сравнимы, т. е. для любых x, y ∈ X имеем x ρ y или y ρ x, называется отношением линейного порядка. Множество X с заданным на нем частичным (линейным) порядком называется частично (линейно) упорядоченным.
Примеры
1. Отношение x ≤ y на множестве действительных чисел есть отношение частичного порядка, причем это линейный порядок.
2. Отношение x < y на множестве действительных чисел не является отношением частичного порядка, поскольку не рефлексивно.
3. Во множестве подмножеств некоторого универсума U отношение A ⊆ B есть отношение частичного порядка, но оно не является отношением линейного порядка в общем случае.
4. Схема организации подчинения в учреждении есть отношение частичного порядка на множестве должностей.
5. Отношение на множестве слов, определенное так: «слово w связано отношением ρ со словом v, если w = v или w появляется в словаре перед словом v» является отношением линейного порядка (лексикографический порядок).
-
Определение функции. N-местные функции. Инъективность, сюръективностьь и биективность. Примеры.
Отношение f на X×Y называется функцией из X в Y и обозначается через: f: X →Y, если для каждого x∈X существует единственный элемент y∈Y такой, что из <x, y> ∈ f и <x, z> ∈ f следует y = z. Если f – функция, то вместо <x, y>∈ f пишут y = f(x) и говорят, что y – значение, соответствующее аргументу x. Множество X называется областью определения функции f, а множество Y называется областью потенциальных значений. Если A⊆X, то множество f(A) = {y | f(x) = y для некоторого x из A} называется образом множества A. Образ всего множества X называется областью значений функции f. Если B⊆Y, то множество f–1(B) = {x | f(x)∈B} называется прообразом множества B. Функция f: X →Y называется также отображением; при этом говорят, что f отображает X в Y. Если <x, y>∈ f , так что y = f(x), то говорят, что элемент x отображается в элемент y.
Поскольку функции являются бинарными отношениями, то к ним применим интуитивный принцип объемности, т. е. две функции f и g равны, если они состоят из одних и тех же элементов. Назовем f n-местной функцией из X в Y, если f: Xn→Y. Тогда пишем y = f(x1,…, xn) и говорим, что y – значение функции при значении аргументов x1,…, xn. Пусть X = {–2,–1,0,1,2}, а Y = {0,1,2,3,4,5}. Определим отношение f ⊆ X×Y как f = {<–2,5>, <–1,2>,<0,1>,<1,2>,<2,5>}. Отношение f – функция из X в Y, так как f ⊆ X×Y и каждый из элементов X присутствует в качестве первой компоненты упорядоченной пары из f ровно один раз.
Пример Пусть X = {–2,–1,0,1,2} и Y = {0,1,2,3,4,5}. Функция f: X→Y определена соотношением f(x) = x2 +1. Если A = {1,2}, то f(A) = {y|<x, y>∈ f для некоторого x из A} ={y| y=f(x) для некоторого x из A} ={2,5} является образом A при отображении f. Если B = {0,2,3,4,5} ⊆ Y, то f–1(B) = {x | f(x)∈B} = {–1, 1, –2, 2} является прообразом B, где –1 ∈ f–1(B), т.к. f(–1) = 2, 1 ∈ f–1(B), т.к. f(1) = 2, –2 ∈ f–1(B), т.к. f(–2) = 5, 2 ∈ f–1(B), т.к. f(2) = 5.
Заметим, что элементы 0, 3 и 4 не вносят никаких элементов в f–1(B), поскольку они не принадлежат области значений функции f.
Прообраз может быть пустым. Так, например, в случае W = {0,3} прообраз f–1(W) пуст, поскольку не существует такого x∈X, для которого f(x)= 0 или f(x) = 3. Область значений функции f имеет вид f(X) = {y | f(x) = y для некоторого x из X} = {1,2,5}. Элементами f(X) являются те и только те элементы области потенциальных значений Y, которые «используются» функцией f. Пусть дана функция f: X→Y. Подчеркнем еще раз три особенности нашего определения функции:
• несколько элементов из области определения X могут иметь один и тот же образ в области значений (f(c) = f (d) = f(e) = 1);
• не все элементы из Y обязаны быть образом некоторых элементов X (нет элемента x ∈ X такого, что f(x) = 4);
• для любого элемента из X, если существует образ, то он должен быть единственным (для функции недопустимо, чтобы одному элементу x ∈ X соответствовало два разных значений f(x)). Функция f: X→Y может быть классифицирована в зависимости от того, существуют ли элементы из Y, связанные данным отношением с более чем одним элементом из X, и связан ли каждый элемент из области значений f(X) с соответствующим элементом области определения X.
• Инъективность Функция (отображение) f: X→Y называется инъективной (инъективным), если для любых x1, x2∈X, y∈Y из y = f(x1) и y = f(x2) следует, что x1 = x2 (или, иначе, из <x1, y>∈f и <x2, y>∈f следует, что x1 = x2). Менее формально, функция f – инъективна, если для всех x1, x2 выполняется: x1≠x2 влечет f(x1) ≠ f(x2).
• Сюръективность Функция (отображение) f: X→Y называется сюръективной (сюръективным), если для любого элемента y∈Y существует элемент x ∈ X такой, что y = f(x).
• Биективность Функция (отображение) f называется биективной (биективным), если f одновременно инъективна и сюръективна. Если существует биективная функция (биекция) f: X→Y, то говорят, что f осуществляет взаимно-однозначное соответствие между множествами X и Y.
Примеры. Рассмотрим четыре функции, отображающие множество действительных чисел R во множество действительных чисел fi: R→R, i = 1,2,3,4:
• функция f1(x) = ex инъективна, но не сюръективна;
• функция f2(x) = x3–x сюръективна, но не инъективна;
• функция f3(x) = 2x+1 биективна;
• функция f4(x) = x не является ни инъективной, ни сюръективной.