Дополнительная. 1. Алферова З.В. Теория алгоритмов

1. Алферова З.В. Теория алгоритмов. – М.: “Статистика”, 1973.

2. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной математике. – М.: “Наука”, 1992

3. Клини С.К. Введение в метаматематику. – М.: “ИЛ”, 1957

4. Столл Р.Р. Множества, логика, аксиоматические теории. – М.: “Просвещение”, 1968.

5. Шафаревич И.Р. Избранные главы алгебры. – М.: “Математическое образование”, 2000.

Словарь основных терминов

Автоморфизм – биективный эндоморфизм, т.е. взаимно однозначное отображение носителя алгебраической структуры на себя, сохраняющие операции сигнатуры.

Алгебраическая структура или алгебра – множество с заданными на нем операциями.

Алгоритм – точное предписание, задающее процесс решения задачи.

Биекция – взаимно однозначное отображение одного множества на другое.

Булева функция – функция, определенная на бинарных наборах заданной длины и принимающая значения из множества {0,1}.

Высказывание – языковое предложение, о котором есть смысл говорить, что оно истинно или ложно.

Гомоморфизм – отображение из одной алгебраической структуры в другую, сохраняющее операции сигнатуры.

Дизъюнктивная нормальная форма (д.н.ф.) – представление булевой функции в виде дизъюнкции элементарных конъюнкций.

Изоморфизм – взаимно однозначное соответствие между носителями алгебраических структур, сохраняющее все операции сигнатуры.

Инъекция – функция, значения которой при различных значениях аргумента различны.

Квантор общности ("x) P(x) – означает, что высказывание P(x) истинно для всех х.

Квантор существования ($х) Р(х) – означает, что существует х, для которого высказывание Р(х) истинно.

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

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

Конъюнктивная нормальная форма (к.н.ф.) – представление булевой функции в виде конъюнкции элементарных дизъюнкций.

Мономорфизм – инъективный гомоморфизм.

Мощность множества – для конечного множества это число элементов, а два бесконечных множества считаются равномощными, если между их элементами может быть установлено взаимно однозначное соответствие.

Предикат – функция, которая при подстановке вместо символов переменных конкретных значений из предметной области превращения в высказывание, т.е. принимает значение «истина» или «ложь».

Сигнатура – множество операций алгебраической структуры.

Счетное множество – множество, имеющее одинаковую мощность с множеством натуральных чисел.

Сюръекция – отображение на всё множество.

Фактор – множество - множество классов эквивалентности.

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

Частичного порядка отношение – рефлективное, антисимметричное и транзитивное бинарное отношение.

Эквивалентности отношение – рефлексивное, симметричное и транзитивное бинарное отношение. Разбивает множество на непересекающиеся подмножества, называемые классами эквивалентности.

Эндоморфизм – гомоморфное отображение носителя алгебраической структуры на себя.

Эпиморфизм – сюръективный гомоморфизм, т.е. отображение носителя одной алгебраической структуры на весь носитель другой структуры, сохраняющее операции сигнатуры.

Ответы к тестам