Итоговый тест.

1. Даны множества ирезультатом операцийявляется множество: а)б)в)г)

2. Даны множества Декартовым произведениемявляется множество: а)б)в)г)

3. На множестве задано бинарное отношениекакая из пар не принадлежитR? а) ; б)в)г)

4. Если функция является сюръекцией будет ли она инъекцией а) да; б) нет; в) не обязательно.

5. Выражениеназывают: а) элементарной конъюнкцией, б)элементарной дизъюнкцией

6. Упростить а)б)в)г)

7. Квантор существования обозначают: а); б); в); г)~.

8. Значком “=>” обозначают; а) конъюнкцию; б) дизъюнкцию; в) импликацию; г) эквиваленцию.

9. Для любого действительного х выполняется неравенство . В символьной форме данное высказывание имеет вид: а)б)в)г)

10. С помощью алгоритма Евклида найти наименьший общий делитель чисел 1236 и 2232.

а) 2; б) 6; в) 4; г) 12.

Рекомендуемая литература. Основная:

1. Нефедов В.Н., Осипова В.А. Курс дискретной математики. - М.: “МАИ”, 1992.

Дополнительная

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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