Математическое толкование символа O

Томский межвузовский центр дистанционного образования
Томский государственный университет систем управления и радиоэлектроники (ТУСУР)
Кафедра компьютерных систем в управлении и проектировании (КСУП)
Контрольная работа № 2
по дисциплине «Математическая логика и теория алгоритмов»
(Учебное методическое пособие «Математическая логика и теория алгоритмов» В. М. Зюзьков, Томск - 2004)

Тема: ВТОРОЕ контрольное задание

Вариант 6

Вариант 6	1. Для бинарного отношения xy  «x + y делится нацело на 3», определенного на множестве Z целых чисел, выясните, какими свойствами оно обладает (рефлексивность, симметричность, антисимметричность, транзитивность) и какими не обладает.
	2. Построить композицию следующих отношений («Быть A» означает «x является A для y».): быть родителем, быть сестрой (возможны две композиции, в зависимости от порядка отношений).
	3. Пусть  и  – бинарные отношения на некотором множестве. Докажите, что ()^–1 = ^–1 ^–1.
	4. Найдите композиции  и , где  = ={<x,y>RR|x+y=0},  = {<x,y>RR|xy>0}, R – множество вещественных чисел.
	5. Доказать тождество для любой функции f и произвольных множеств A и B: f(A)\f(B) f(A\B).
	6. Является ли отношением эквивалентности отношение: иметь одну и ту же мать.
	7. Докажите, что M ={{1},{2},{3}} – разбиение множества A={1,2,3}. Перечислите все элементы отношения эквивалентности, соответствующего разбиению M.
	8. Используя математическую индукцию, докажите, что для n  2.
	9. Пусть X = {1, 2, 3, 4, 5, 6} и f – инъективная функция из X в множество–степень P(X), определенная следующим образом: f(1) = {2,3,4}, f(2) = {1,4,2}, f(3) = {2,4}, f(4) = , f(5) = {1,2,3,4,6}, f(6) = {1,3,2}. Опишите множество W, отсутствие отображения на которое гарантирует нам теорема 3.16 учебного пособия.
	10. Расположите следующие 4 функции в порядке увеличения скорости роста (каждая функция есть O(следующая)), не исключено, что некоторые функции имеют одинаковую скорость: f1(n) = , f2(n) = , f3(n) = 2^n, f4(n) = n^2.