Язык математики (ОТиПЛ)
1. Семантические парадоксы.
Парадокс лжеца. Парадоксы Ришара, Берри, Греллинга.
2. Начальные понятия семиотики и логики.
Алфавит, буква, слово в алфавите. Формула, переменная, форма. Область допустимых значений переменной относительно формы. Связанное и свободное вхождение переменных. Имя, денотат имени, именная форма. Высказывание, высказывательная форма.
3. Логика высказываний.
Алфавит языка логики высказываний: переменные для высказываний, логические, формулы логики высказываний.
Истинностные таблицы для отрицания, конъюнкции, дизъюнкции, импликации, эквиваленции, штриха Шеффера, стрелки Пирса. Законы логики (тавтологии), противоречия, равносильные высказывательные формы. Законы исключенного третьего, снятия двойного отрицания, контрапозиции, дистрибутивности, де Моргана, др. Применение языка логики высказываний для описания фрагментов естественных языков.
Выражение одних пропозициональных связок через другие. Полные системы связок. Булевы функции, сопряженные с формулами логики высказываний. Возможность выражения произвольной булевой функции посредством формулы. Контактные схемы, их связь с формулами логики высказываний и булевыми функциями.
4. Кванторы.
Кванторы общности и существования, соотношения между ними. Однотипность квантора общности и конъюнкции, квантора существования и дизъюнкции. Законы коммутации кванторов и импликации.
5. Числовые системы
Натуральное число и его запись (q-ичная, q=2, 3, 4, римская, др.). Целое число, его запись. Рациональное число и его запись в виде дроби, в виде тройки натуральных чисел. q-ично рациональные числа. Действительное число и его запись в виде бесконечной q-ичной дроби. Иррациональное, алгебраическое, трансцендентное число. Комплексное число, его запись. Число, сопряженное данному. Тригонометрическая форма комплексного числа, аргумент, модуль. Показательная форма комплексного числа. Формула Муавра. Теорема Безу.
Основная теорема алгебры.
6. Начальные понятия теории множеств.
Множество (совокупность), элемент множества, принадлежность элемента множеству. Способы задания множеств. Равенство множеств. Пустое множество. Подмножество, собственное подмножество. Подмножества числовой прямой: отрезки (сегменты), интервалы, полуинтервалы.
Теоретико-множественные операции объединения, пересечения, разности, симметрической разности. Универсум, дополнение множества. Выражение одних теоретико-множественных операций через другие. Объединение и пересечение элементов произвольной совокупности множеств.
Кортеж над множеством, компонента кортежа, длина кортежа. Размещение над множеством. Прямое произведение множеств, степень множества, проекция множества.
7. Отношения и порядки.
Отношение между элементами двух множеств. Область определения, множество значений отношения. Дополнение отношения. Инверсия пары, инверсия отношения. Образ, полный прообраз множества при отношении. Композиция отношений. Ассоциативность композиции. Инверсия композиции.
Бинарное отношение на множестве. Основные свойства отношений: рефлексивность, иррефлексивность, симметричность, антисимметричность, транзитивность, связанность.
Отношение эквивалентности. Разбиение множества на классы. Сопряженность разбиения множества и отношения на множестве. Единственность разбиения, сопряженного с данным отношением эквивалентности.
Отношения строгого и нестрогого порядка. Частично упорядоченное множество. Наибольший, наименьший элемент. Максимальный, минимальный элемент. Верхняя (нижняя) грань подмножества частично упорядоченного множества. Точная верхняя (нижняя) грань. Линейный порядок. Вполне упорядоченное множество.
8. Множества и их мощности.
Всюду определённое, функциональное, сюръективное, инъективное отношение между элементами двух множеств. Биекция. Равномощность (эквивалентность) множеств. Сравнение мощностей двух множеств.
n-элементное множество, конечное множество. Бесконечное множество. Счётное множество. Существование счётного подмножества у всякого бесконечного множества. Мощность объединения не более чем счётной совокупности не более чем счётных множеств. Счётность множества рациональных чисел, множества алгебраических чисел.
Несчётность множества действительных чисел. Сравнение мощностей множества и совокупности всех его подмножеств. Множества мощности континуума. Континуальность множества иррациональных чисел, множества трансцендентных чисел, множества комплексных чисел. Континуальность множества всех подмножеств натурального ряда.
9. Элементы комбинаторики.
Основные принципы комбинаторики. Установление эквивалентностей, позволяющих обосновать корректность понятий числа k-элементных подмножеств n-элементного множества, числа размещений из n по k . Числовые выражения для Cnk, Ank, Pn. Установление эквивалентностей, используемых при их получении. Перестановка с повторениями, сочетание с повторениями. Бином Ньютона. Формула включения и исключения.
Основная литература
1. П. С. Александров. Введение в теорию множеств и общую топологию. М., Наука, 1977. [С. 7-33.]
2. И. И. Ежов, А. В. Скороход, М. И. Ядренко. Элементы комбинаторики. М., Наука, 1977. [С. 5-64.]
3. Р. Курант, Г. Роббинс. Что такое математика? Элементарный очерк идей и методов. М., Просвещение, 1967. [С. 24-130.]
4. И. А. Лавров, Л. Л. Максимова. Задачи по теории множеств, математической логике и теории алгоритмов. М., Физ.-мат. литература, 1995. [С. 7-35, 50-62, 74-88.]
5. Э. Мендельсон. Введение в математическую логику. М., Наука, 1984. [С. 19-35, 60-63.]
6. А. Чёрч. Введение в математическую логику. М., ИЛ, 1960. [С. 15-63.]
7. Ю. А. Шиханович. Введение в современную математику. М., Наука, 1965. [С. 29-297.]
Дополнительная литература
1. Н. Бурбаки. Теория множеств. М., Мир, 1965. [С. 23-30.]
2. Н. Я. Виленкин. Популярная комбинаторика. М., Наука, 1975. [С. 73-117.]
3. С. К. Клини. Математическая логика. М., Мир, 1973. [С. 11-46, 93-132.]
4. Д. Кук, Г. Бейз. Компьютерная математика. М.: Наука, 1990. [С. 10-132.]
5. П. С. Новиков. Элементы математической логики. М., Наука, 1973. [С. 36-65, 123-135.]
6. Р. Столл. Множества, логика, аксиоматические теории. М., Просвещение, 1968. [С. 9-138.]
7. Р. Фор, А. Кофман, М. Дени-Папен. Современная математика. М., Мир, 1966. [С. 9-53.]
8. А. Френкель, И. Бар-Хиллел. Основания теории множеств. М., Мир, 1966. [С. 11-28.]
9. Ф. Хаусдорф. Теория множеств. М., ОНТИ, 1937. [С. 7-42.]
Программу составили Е. Ю. Ногина, В. Е. Плиско.