Математическая логика. Зюзьков. Томск. ТУСУР. 20 задач. Контрольные работы №№1 и 2. Вариант №7

Контрольная работа 1

Вариант 7 1. Перевести на формальный язык (обязательно указываете универсум):
«Нет действительных чисел, больших ».

 2. Перевести на формальный язык (обязательно указываете универсум):
«Если будешь хорошо учиться, поступишь в вуз, а иначе провалишься».

 3. Перевести с формального языка на человеческий:
x, y, z (Z(x) & Z(y) & Z(z) & x y & y z & z x)  x Z(x), где Z – знать тайну.

 4. Перевести на формальный язык (обязательно указываете универсум):
«Некоторые подушки мягкие».

 5. Является ли тавтологией формула
(p~q) ~ ((pq) ∩ (qp))?

 6. Докажите выполнимость (PQ)(QP).

 7. Является ли тавтологией формула ((A∩B)&(B∩C)&(C∩D)) ~
((A&C) ∩ (B&C) ∩(B&D))?

 8. Проверить, что AB=AB A=B.

 9. Проверить тождество (A\B)\C = (A\C)\(B\C).

 10. Проверить тождество AB = (AB) (AB).
Контрольная работа 2

Вариант 7 1. Для бинарного отношения xy «x2 + y2 =1», определенного на множестве R вещественных чисел, выясните, какими свойствами оно обладает (рефлексивность, симметричность, антисимметричность, транзитивность) и какими не обладает.

 2. На множестве S={2,4,6,7,10} задано отношение R, определяемое как <m,n>R тогда и только тогда, когда max(m,n) = 7;
а) Записать отношение в виде множества упорядоченных пар.
б) Является ли отношение R:
• Рефлексивным?
• Симметричным?
• Транзитивным?
• Антисимметричным?
 3. Для бинарного отношения xy «x2 = y», определенного на множестве R вещественных чисел, определите область определения, область значений и изобразите на плоскости множество всех таких точек <x,y>, что xy.

 4. Найдите композиции и , где = ={<x,y>RR|x=y2}, = {<x,y>RR|x+y =0}, R – множество вещественных чисел.

 5. Пусть f: xx2 и g: xx+1 – отображения R в R. Найдите f g и g f.

 6. На множестве TT, T={4,10,6}, задано отношение R, определяемое следующим образом: <a,b> R <c,d>, если a+d = c+b.
а) Показать, что R есть отношение эквивалентности.
б) Описать классы эквивалентности.

 7. На множестве рациональных чисел определено отношение a b «существует такое целое k, что a = 2kb». Доказать, что – отношение эквивалентности и найти классы эквивалентности.

 8. Используя математическую индукцию, докажите, что 2n > n2 для n 5.

 9. Пусть X = {1, 2, 3, 4, 5, 6} и f – инъективная функция из X в множество–степень P(X), определенная следующим образом:
f(1) = {1,2,3,4},
f(2) = {1,4},
f(3) = {2,3,4},
f(4) = ,
f(5) = {1,2,3,4,5,6},
f(6) = {1,3,6}.
Опишите множество W, отсутствие отображения на которое гарантирует нам теорема 3.16 учебного пособия.

 10. Расположите следующие 4 функции в порядке увеличения скорости роста (каждая функция есть O(следующая)), не исключено, что некоторые функции имеют одинаковую скорость:
f1(n) = n!, f2(n) = , f3(n) = en, f4(n) = . (e – основание натуральных логарифмов)