Математическая логика

1. Для бинарного отношения xρy ⇔ «x×y >1», определенного на множестве R вещественных чисел,выясните, какими свойствами оно обладает (реф-
лексивность, симметричность, антисимметричность, транзитивность) и какими не обладает.
2. Построить композицию следующих отношений («Быть A» означает «x является A для y».): быть соседом, быть другом
(возможны две композиции, в зависимости от порядка отношений).
3. Покажите, что равенство ρ ° ϕ = ϕ ° ρ верно не для любых бинарных отношений. Найдите контр пример.
4. Найдите композиции ρ°ϕ и ϕ°ρ, где ϕ =
={∈R×R|x=y2}, ρ = {∈R×R|x×y>0}, R –множество вещественных чисел.
5. Даны отображения R→R: f: x→sin x и g: x→x2. Найдите f`° g и g ° f.
6. Является ли отношением эквивалентности отношение: иметь одну и ту же сестру.
7. Докажите, что M ={{1,7},{2,4,5,6},{3}} – разбиение множества A = {1,2,3,4,5,6,7}. Перечислите все элементы отношения эквивалентности, соответствующего разбиению M.
8. Найдите ошибку в доказательстве того, что все лошади имеют одну и ту же масть (см. задачу в разделе «4.2 Математическая индукция» учебного пособия).
9. Пусть X = {1, 2, 3, 4, 5, 6} и f – инъективная функция из X в множество–степень P(X), определенная следующим образом:
f(1) = {1,2,3,4,6},
f(2) = {1,2,4,6},
f(3) = {2,3,4,5,6},
f(4) = {4,6},
f(5) = {1,2,3,4,5,6},
f(6) = {1,3,6}.
Опишите множество W, отсутствие отображения на которое гарантирует нам теорема 3.16 учебного пособия.
10. Расположите следующие 4 функции в порядкеувеличения скорости роста (каждая функция есть O(следующая)), не исключено, что некоторые функции имеют одинаковую скорость: f1(n) = 2ln n , f2(n) = ln n , f3(n) = ln n, f4(n) =
=ln (ln n).