Контрольная работа №2 "Математическая логика и теория алгоритмов" Вариант №12 ТУСУР

Контрольная работа №2 "Математическая логика и теория алгоритмов" Вариант №12 ТУСУР

1.Определить операции и (каждую по отдельности) через операции разность \ и симметрическая разность .

2. Является ли тавтологией формула (A B) ((B C) (A C))?

3. Переведите с естественного языка на язык логики предикатов: Некоторые индейцы были храбрее белых. 4. Переведите с естественного языка на язык логики предикатов: Полицейские замешаны в преступлениях, но не все.

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

6. Пусть f: x x +1 и g: x 2x отображения R в R. Найдите отображения f g f, f f g, f g g и g f g. Являются ли отображениями R в R отношения f 1 и g 1 ?

7. Используя математическую индукцию, докажите для целого n 1, что 2 1 ( 1) . (2 1)(2 1) 2(2 1) n k k nn = kk n + = + +

8. Расположите следующие 5 функций в порядке увеличения скорости роста (каждая функция есть O (следующая)): 6 + n/1000, ln (ln n), (ln n) 2 , n2 + 1000n, 2n .