Контрольная работа по математике «Математическая логика и теория алгоритмов», ТУСУР

Вариант 1

1. Следующее утверждение для произвольных множеств докажите или опровергните (A ∪ B) ∩ C = A ∪ (B ∩ C). 2. Является ли тавтологией формула ((A ∨ B) & (A ∨ C) & (B ∨ D) & (C ∨ D)) ~ ((A & D) ∨ (B & C))? 3. Переведите с естественного языка на язык логики предикатов: Все девочки боятся лягушек и мышей. 4. Переведите с естественного языка на язык логики предикатов: Две прямые параллельны тогда и только тогда, когда они одновременно пересекают третью либо не пересекают её. 5. Для бинарного отношения x ρ y ⇔ «x перпендикулярна y», определенного на множестве всех прямых плоскости, выясните, какими свойствами оно обладает (рефлексивность, симметричность, антисимметричность, транзитивность) и какими не обладает. 6. Для бинарного отношения X ρ Y ⇔ «X  Y» (X и Y — множества из целых чисел) выясните, какими свойствами оно обладает (рефлексивность, симметричность, антисимметричность, транзитивность) и какими не обладает. 7. Докажите, используя математическую индукцию, для положительных целых n равенство 8. Расположите следующие 5 функций в порядке увеличения скорости роста (каждая функция есть O (следующая)):

Вариант 2

1. Проверить для произвольных множеств, что (A ∪ B) ∩ (C ∪ D) = (A ∩ C) ∪ (B ∩ C) ∪ (A ∩ D) ∪ (B ∩ D). 2. Является ли тавтологией формула (¬B ⊃ ¬A) ⊃ ((¬B ⊃ A) ⊃ B)? 3. Переведите с естественного языка на язык логики предикатов: Логарифмы всех положительных рациональных чисел иррациональны. 4. Переведите с естественного языка на язык логики предикатов: Доисторические ящеры при встречах уступали дорогу друг другу. 5. Пусть ρ и ϕ — бинарные отношения на некотором множестве. Докажите, что 6. Пусть f: x → x + 1 и g: x → 2x — отображения R в R. Найдите отображения Являются ли отображениями R в R отношения f –1 и 7. Докажите, используя математическую индукцию, равенство 8. Расположите следующие 5 функций в порядке увеличения скорости роста (каждая функция есть O (следующая)):

Вариант 3

1. Проверить для произвольных множеств, что (A ∩ B) ∪ (C ∩ D) = (A ∪ C) ∩ (B ∪ C) ∩ (A ∪ D) ∩ (B ∪ D). 2. Что можно сказать об истинностном значении высказывания p ⊃ ¬t, если формулы p ⊃ q, ¬s ⊃ ¬q и t ⊃ ¬s истинны? 3. Переведите с естественного языка на язык логики предикатов: Некоторые финансисты — мошенники, но не все. 4. Переведите с естественного языка на язык логики предикатов: Прапорщики любят порядок, и не только они. 5. Найдите композиции ρ ° ϕ и ϕ ° ρ, где ρ = {<x, y> ∈ R × R | x + y = 0}, ϕ = {<x, y> ∈ R × R | x  y < 0}, R — множество вещественных чисел. 6. Докажите, что если ρ — отношение эквивалентности на некотором множестве X, то ρ–1 — также отношение эквивалентности на X. 7. Докажите, используя математическую индукцию для чисел Фибоначчи fib(m + n) = fib(m – 1) fib(n) + fib(m) fib(n + 1). (По определению, fib(1) = fib(2) = 1, fib(n) = fib(n – 1) + fib(n – 2) для n > 2) Подсказка: индукция по n, базовые случаи n = 1 и n = 2. 8. Расположите следующие 5 функций в порядке увеличения скорости роста (каждая функция есть O (следующая))

Вариант 4

1. Следующее утверждение для произвольных множеств докажите или опровергните (A ∪ B) ∩ C = A ∪ (B ∩ C). 2. Является ли формула ((p ⊃ q) & (q ⊃ p) & (p ∨ r) & ¬r) ⊃ p тавтологией? 3. Переведите с естественного языка на язык логики предикатов: Кошки бывают только белые и серые. 4. Переведите с естественного языка на язык логики предикатов: Так как 60 делится на 2 и на 3, то 60 делится на некоторые числа, отличные от 60. 5. Для бинарного отношения x ρ y ⇔ «x + y делится нацело на 3», определенного на множестве Z целых чисел, выясните, какими свойствами оно обладает (рефлексивность, симметричность, антисимметричность, транзитивность) и какими не обладает. 6. Докажите, что отношение <a, b> ρ <c, d> ⇔ a2 + b2 = c2 + d2 есть отношение эквивалентности на множестве вещественных чисел. Найдите классы эквивалентности и изобразите их на координатной плоскости. 7. Используя математическую индукцию, докажите равенство для целого n > 0. 8. Расположите следующие 5 функций в порядке увеличения скорости роста (каждая функция есть O (следующая))

Вариант 5

1. Проверить, что A ∆ B = C ⇔ B ∆ C =A ⇔ C ∆ A = B. (Подсказка: используйте ассоциативность ∆, задача 17 из раздела «Как решать задачи. Операции с множествами».) 2. Формула (p ⊃ q) & (q ⊃ r) & ¬ (p ⊃ r) — тавтология, противоречие или не то и не другое? 3. Переведите с естественного языка на язык логики предикатов: Синус и косинус равны друг другу тогда и только тогда, когда равны тангенс и котангенс. 4. Переведите с естественного языка на язык логики предикатов: Не все решения уравнения sin 5x = 0 иррациональны. 5. Найдите отношения ρ–1 , ρ ° ρ , ρ–1 ° ρ–1 для бинарного отношения x ρ y ⇔ «x2 + y2 = 1», определенного на множестве Z целых чисел. 6. На множестве {2, 0, 4} × {2, 0, 4} задано отношение R, определяемое следующим образом: <a, b> R <c, d>, если a – b = c – d. а) Показать, что R есть отношение эквивалентности. б) Описать классы эквивалентности. 7. Используя математическую индукцию, докажите для целого n ≥ 0, что 8. Расположите следующие 5 функций в порядке увеличения скорости роста (каждая функция есть O (следующая))

Вариант 6

1. Проверить тождество для произвольных множеств: (A ∪ B) \ C = (A \ C) ∪ (B \ C). 2. Является ли тавтологией формула ((P ⊃ Q) & (R ⊃ Q) & (T ⊃ (P ∨ R)) & T) ⊃ Q? 3. Переведите с естественного языка на язык логики предикатов: Волки и люди боятся друг друга. 4. Переведите с естественного языка на язык логики предикатов: Все рыцари сражались друг с другом на поединках. 5. Пусть ρ и ϕ — антисимметричные отношения на некотором множестве. Докажите, что (ρ ∩ ϕ) –1 — антисимметричное отношение. 6. Доказать тождество для любой функции f: f 7. Числа Фибоначчи определяются следующим рекуррентным правилом: F0 = 1, F1 = 1, Fk+2 = Fk+1 + Fk для k ≥ 0. Докажите с помощью математической индукции, что для любого натурального n ≥ 0 имеем 2 8. Расположите следующие 5 функций в порядке увеличения скорости роста (каждая функция есть O (следующая))

Вариант 7

1. Определить операции ∪ и \ (каждую по отдельности) через операции ∆ и ∩. 2. Является ли тавтологией формула ((p ⊃ q) & (p ∨ r) & r) ⊃ ¬p? 3. Переведите с естественного языка на язык логики предикатов: Для любого натурального числа найдется большее его простое число. 4. Переведите с естественного языка на язык логики предикатов: Все лягушки, увидев аиста, прыгают и квакают. 5. Для бинарного отношения x ρ y ⇔ «x перпендикулярна y», определенного на множестве всех прямых плоскости, выясните, какими свойствами оно обладает (рефлексивность, симметричность, антисимметричность, транзитивность) и какими не обладает. 6. На множестве R вещественных чисел задано отношение a ρ b ⇔ a2 = b2 . Докажите, что это отношение эквивалентности, и найдите классы эквивалентности. 7. Используя математическую индукцию, докажите, что 8. Расположите следующие 5 функций в порядке увеличения скорости роста (каждая функция есть O (следующая))

Вариант 8

1. Следующее утверждение докажите или опровергните (опровергнуть можно на частном примере): A ∈ B и B ∈ C ⇒ A ∈ C. 2. Является ли тавтологией формула ((P ⊃ Q) & (R ⊃ Q) & (T ⊃ (P ∨ R)) & ¬T) ⊃ Q? 3. Переведите с естественного языка на язык логики предикатов: Зайцы не всегда глупее лис. 4. Переведите с естественного языка на язык логики предикатов: Все честные ученые уважают друг друга. 5. Для бинарного отношения x ρ y ⇔ «y = |x|», определенного на множестве вещественных чисел, выясните, какими свойствами оно обладает (рефлексивность, симметричность, антисимметричность, транзитивность) и какими не обладает. 6. Докажите, что композиция инъективных отображений есть инъективное отображение. 7. Используя математическую индукцию, докажите, что 8. Расположите следующие 5 функций в порядке увеличения скорости роста (каждая функция есть O (следующая))

Вариант 9

1. Следующее утверждение докажите или опровергните: A ∩ B ⊆ C и A ∪ B ⊆ C ⇒ A ∩ C = ∅. 2. Является ли тавтологией формула ((p ⊃ q) ∨ (r ⊃ s)) ⊃ ((p & r) ⊃ (q ∨ s))? 3. Переведите с естественного языка на язык логики предикатов: Простое число, отличное от 2, нечетно. 4. Переведите с естественного языка на язык логики предикатов: Любое число, большее 1, можно представить в виде произведения различных чисел. 5. Покажите, что равенство ρ ° ϕ = ϕ ° ρ верно не для любых бинарных отношений. 6. На множестве {1, 5, 9} × {1, 5, 9} задано отношение R, определяемое следующим образом: <a, b> R <c, d>, если a – b = c – d. а) Показать, что R есть отношение эквивалентности. б) Описать классы эквивалентности. 7. Используя математическую индукцию, докажите для целого n ≥ 0, что число 32n+3 + 2n делится на 7. 8. Расположите следующие 5 функций в порядке увеличения скорости роста (каждая функция есть O (следующая))

Вариант 10

1. Проверить для произвольных множеств, что ¬(A ∩ B ∩ C) = (A ∪ B ∪ C) \ (A ∩ B ∩ C). 2. Что можно сказать об истинностном значении высказывания p ⊃ ¬s, если p ⊃ q ≡ И, ¬s ⊃ ¬q ≡ Л? 3. Переведите с естественного языка на язык логики предикатов: Если число делится на два числа, то оно делится на их произведение. 4. Переведите с естественного языка на язык логики предикатов: Если вчера Петров прогулял два занятия, то сегодня только одно. 5. Найдите отношения ρ–1 ρ ° ρ , ρ–1 ° ρ–1 для бинарного отношения x ρ y », определенного на множестве R вещественных чисел. 6. Найдите f(A), где A = {<x, y> ∈ R × R | y = 2x + 3} для следующих отображений: а) f: <x, y> → <x, –y>; б) f: <x, y> → <y – 2, x + 2>. Изобразите на плоскости множества A и f(A). 7. Используя математическую индукцию, докажите для целого n ≥ 1, что 8. Расположите следующие 5 функций в порядке увеличения скорости роста (каждая функция есть O (следующая)):

Вариант 11

1. Проверить для произвольных множеств, что A ⊆ B ∪ C ⇔ A ∩ B ⊆ C. 2. Является ли тавтологией формула ((p & q) ⊃ r) ~ (p ⊃ (q ⊃ r))? 3. Переведите с естественного языка на язык логики предикатов: Всякое четное число, большее 2, есть сумма двух простых чисел. 4. Переведите с естественного языка на язык логики предикатов: Хотя 60 делится на 2, 3, 4, 5 и 6, но это не означает, что 60 делится на любое натуральное число. 5. Для бинарного отношения X ρ Y ⇔ «X ∩ Y = ∅» (X и Y — множества из целых чисел) выясните, какими свойствами оно обладает (рефлексивность, симметричность, антисимметричность, транзитивность) и какими не обладает. 6. Пусть f: x → x2 +1 и g: x → x3 — отображения R в R. Найдите отображения f °g и g ° f. 7. Используя математическую индукцию, докажите для целого n ≥ 1, что 8. Расположите следующие 5 функций в порядке увеличения скорости роста (каждая функция есть O (следующая)):

Вариант 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, что 8. Расположите следующие 5 функций в порядке увеличения скорости роста (каждая функция есть O (следующая)):

Вариант 13

1. Определить операции ∩ и \ (каждую по отдельности) через операции ∆ и ∪. 2. Является ли тавтологией формула ¬ (p ~ q) ~ (¬ (p ⊃ q) ∨ ¬ (q ⊃ p))? 3. Переведите с естественного языка на язык логики предикатов: Все первокурсники и второкурсники пришли на лекцию. 4. Переведите с естественного языка на язык логики предикатов: Все философы критиковали друг друга. 5. Найдите отношения ρ–1 , ρ ° ρ , ρ–1 ° ρ–1 для бинарного отношения x ρ y ⇔ «y = |x|», определенного на множестве R вещественных чисел. 6. Доказать тождество для любой функции f: f –1 7. Используя математическую индукцию, докажите для целого n ≥ 0, что число 33n+3 – 26n – 27 делится на 169. 8. Расположите следующие 5 функций в порядке увеличения скорости роста (каждая функция есть O (следующая)):

Вариант 14

1. Проверить для произвольных множеств, что (A \ B) ∪ (B \ C) = (A \ C) ∪ (C \ B). 2. Является ли тавтологией формула ((p ⊃ q) & (r ⊃ s)) ⊃ (( p ∨ r) ⊃ (q ∨ s))? 3. Переведите с естественного языка на язык логики предикатов: Два натуральных числа, делящиеся друг на друга, равны. 4. Переведите с естественного языка на язык логики предикатов: Если Ромео и Джульетта не любят друг друга, то никто никого не любит взаимно. 5. Для бинарного отношения X ρ Y ⇔ «X \ Y ≠ ∅», определенного на множестве всех подмножеств множества целых чисел, выясните, какими свойствами оно обладает (рефлексивность, симметричность, антисимметричность, транзитивность) и какими не обладает. 6. На множестве N натуральных чисел задано бинарное отношение a ρ b ⇔ «последняя цифра в десятичной записи числа a совпадает с последней цифрой числа b». Доказать, что ρ есть отношение эквивалентности. Сколько элементов в фактор-множестве N/ρ? 7. Используя математическую индукцию, докажите для целого n ≥ 1, что 8. Расположите следующие 5 функций в порядке увеличения скорости роста (каждая функция есть O (следующая)):

Вариант 15

1. Проверить для произвольных множеств, что (A \ B) ∪ (B \ C) ∪ (C \ A) = A ∪ (B ∪ C). 2. Является ли формула ((p ⊃ (q ⊃ r)) & (¬t ∨ p) & ¬q) ⊃ (t ⊃ r) тавтологией? 3. Переведите с естественного языка на язык логики предикатов: Некоторые школьники — отличники или спортсмены. 4. Переведите с естественного языка на язык логики предикатов: Некоторые прямые параллельны. 5. Найдите отношения ρ–1 , ρ ° ρ , ρ–1 ° ρ–1 для бинарного отношения x ρ y ⇔ «2x = 3y», определенного на множестве Z целых чисел. 6. На множестве σ всех отображений R в R определено отношение f ρ g ⇔ «существует c ∈ R, такое, что для всех x ∈ R имеем f(x) = g(x) + c». Докажите, что ρ — отношение эквивалентности и найдите классы эквивалентности. 7. Используя математическую индукцию, докажите для целого n ≥ 0, что делится на 8. 8. Расположите следующие 5 функций в порядке увеличения скорости роста (каждая функция есть O (следующая)):

Вариант 16

1. Следующее утверждение докажите или опровергните (опровергнуть можно на частном примере с помощью диаграммы Эйлера): если A ⊆ ¬(B ∪ C) и B ⊆ ¬(A ∪ C), то B = ∅. 2. Что можно сказать об истинностном значении высказывания p ⊃ v, если формулы (p ∨ q) ⊃ (r ∨ s) и (s ∨ r) ⊃ v истинны? 3. Переведите с естественного языка на язык логики предикатов: Сумма любого числа, отличного от нуля, с обратным к нему числом больше 2. 4. Переведите с естественного языка на язык логики предикатов: Для делимости целого числа на 8 необходима делимость на 4. 5. Для бинарного отношения x ρ y ⇔ «y делится нацело на x», определенного на множестве положительных целых чисел, выясните, какими свойствами оно обладает (рефлексивность, симметричность, антисимметричность, транзитивность) и какими не обладает. 6. На множестве {4, 10, 7} × {4, 10, 7} задано отношение R, определяемое следующим образом: <a, b> R <c, d>, если a – b = c – d. а) Показать, что R есть отношение эквивалентности. б) Описать классы эквивалентности. 7. Числа Люка удовлетворяют такому же рекуррентному отношению, как и числа Фибоначчи f(n + 2) = f(n) + f(n – 1), но с другими начальными условиями f(1) = 1, f(2) = 3 (для чисел Фибоначчи fib(1) = fib(2) = 1). Докажите, используя математическую индукцию, соотношение f(n) = fib(n – 1) + fib(n + 1) для n >1. 8. Расположите следующие 5 функций в порядке увеличения скорости роста (каждая функция есть O (следующая)):

Вариант 17

1. Следующее утверждение для произвольных множеств докажите или опровергните (A \ B) ∪ C = (A ∪ C) \ (B ∪ C). 2. Является ли тавтологией формула (p ⊃ q) ⊃ ((p & r) ⊃ (q & r))? 3. Переведите с естественного языка на язык логики предикатов: Для любого натурального числа существует большее, делящееся на n. 4. Переведите с естественного языка на язык логики предикатов: Если бы все боялись друг друга, то ни один человек не был бы счастлив. 5. Для бинарного отношения x ρ y ⇔ «x ≤ y +1», определенного на множестве Z целых чисел, выясните, какими свойствами оно обладает (рефлексивность, симметричность, антисимметричность, транзитивность) и какими не обладает. 6. Найдите f(A), где A = {<x, y> ∈ R × R | y = 2x + 3} для следующих отображений: а) f: <x, y> → <y, x>; б) f: <x, y> → <–y, –x>. Изобразите на плоскости множества A и f(A). 7. Используя математическую индукцию, докажите для целого n ≥ 1, что 8. Расположите следующие 5 функций в порядке увеличения скорости роста (каждая функция есть O (следующая)):

Вариант 18

1. Проверить тождество A ∆ (A ∆ B) = B. (Подсказка: используйте ассоциативность ∆, задача 17 из раздела «Как решать задачи. Операции с множества».) 2. Что можно сказать об истинностном значении высказывания p ⊃ (¬r ⊃ ¬q), если p ⊃ (q ⊃ r) имеет значение истина? 3. Переведите с естественного языка на язык логики предикатов: Два целых числа могут делиться друг на друга, но не быть равными. 4. Переведите с естественного языка на язык логики предикатов: Не все студенты отличники или спортсмены. 5. Для бинарного отношения x ρ y ⇔ «x × y >1», определенного на множестве R вещественных чисел, выясните, какими свойствами оно обладает (рефлексивность, симметричность, антисимметричность, транзитивность) и какими не обладает. 6. Пусть f — отображение R в R. Рассмотрим отношение a ρ b ⇔ f(a) ≤ f(b). Приведите примеры таких отображений f, для которых отношение ρ является отношением частичного порядка, и примеры таких f, что ρ не является отношением частичного порядка 7. Используя математическую индукцию, докажите для целого n ≥ 1, что 8. Расположите следующие 5 функций в порядке увеличения скорости роста (каждая функция есть O (следующая)):

Вариант 19

1. Докажите, что B = (¬A ∩ B) ∪ (¬B ∩ A) ⇒ A = ∅. (Подсказка. Доказывайте от противного: предположите, что существует x ∈ A. Рассмотрите два случая: a) x ∉ B и b) x ∈ B и придите в обоих случаях к противоречию. Это покажет, что A = ∅.) 2. Является ли тавтологией формула ((P ⊃ Q) & (Q ⊃ P) & (P ∨ R) & ¬R) ⊃ P? 3. Переведите с естественного языка на язык логики предикатов: При некоторых отрицательных x функция f(x) принимает рациональные значения. 4. Переведите с естественного языка на язык логики предикатов: Так как 60 делится на 2, 3, 4, 5 и 6, то 60 делится на любое натуральное число. 5. Найдите отношения ρ–1 , ρ ° ρ , ρ–1 ° ρ–1 для бинарного отношения x ρ y ⇔ «5x = 3y», определенного на множестве Z целых чисел. 6. Даны отображения R → R: f: x → sin x и g: x → x2 . Найдите f` ° g и g ° f. 7. Числа Фибоначчи определяются следующим рекуррентным правилом: F0 = 1, F1 = 1, Fk+2 = Fk+1 + Fk для k ≥ 0. Докажите с помощью математической индукции, что для любого натурального n ≥ 0 имеем 8. Расположите следующие 5 функций в порядке увеличения скорости роста (каждая функция есть O (следующая)):

Вариант 20

1. Следующее утверждение для произвольных множеств докажите или опровергните (¬A ∩ B) ∪ (¬B ∩ A) ⊆ B. 2. Является ли тавтологией формула ((P ⊃ Q) & (Q ⊃ P) & (P ∨ R) & R) ⊃ P? 3. Переведите с естественного языка на язык логики предикатов: Некоторые зубные врачи боятся маленьких девочек. 4. Переведите с естественного языка на язык логики предикатов: Все волки, кроме бешенных, боятся людей. 5. Найдите отношения ρ–1 , ρ ° ρ , ρ–1 ° ρ–1 для бинарного отношения x ρ y ⇔ «x и y имеют общий делитель > 1», определенного на множестве положительных целых чисел. 6. Пусть A — непустое конечное множество. Рассмотрим отношение X ρ Y на подмножествах A ⇔ «число элементов в X меньше или равно числу элементов в Y». Является ли ρ отношением частичного порядка? 7. Докажите для натурального n ≥ 7: 3n < n!. 8. Расположите следующие 5 функций в порядке увеличения скорости роста (каждая функция есть O (следующая)):