Математическая логика и теория алгоритмов (В. М. Зюзьков, 2015 г., 80 с.)

Контрольная работа состоит из 20 вариантов по 8 заданий в каждом.
Выбор варианта контрольной работы осуществляется по общим правилам с использованием следующей формулы:
V = (N × K) div 100,
где V — искомый номер варианта,
N — общее количество вариантов,
div — целочисленное деление,
при V = 0 выбирается максимальный вариант,
K — код варианта.

Вариант 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 (следующая)):
n! + 200n, 10000 ln n, (ln n)2, n2 + ln n, 106 n.

Вариант 2
1. Проверить для произвольных множеств, что (A ∪B) ∩ (C ∪D) = (A ∩ C) ∪ (B ∩ C) ∪ (A ∩ D) ∪ (B ∩ D).
2. Является ли тавтологией формула (¬B ⊃¬A) ⊃ ((¬B ⊃A) ⊃B)?
3. Переведите с естественного языка на язык логики предикатов: Логарифмы всех положительных рациональных чисел иррациональны.
4. Переведите с естественного языка на язык логики предикатов: Доисторические ящеры при встречах уступали дорогу друг другу.
5. Пусть ρ и ϕ — бинарные отношения на некотором множестве. Докажите, что (ρ ∪ϕ)–1 = ρ–1 ∪ ϕ–1.
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 ≥ 2.
8. Расположите следующие 5 функций в порядке увеличения скорости роста (каждая функция есть O (следующая)):
ln (n!) + 700, 0.001 × 22n, ln (ln n) + 10100 , 0.2 × 4ln n , n3/250.

Вариант 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. Найдите композиции ρ ° ϕ и ϕ ° ρ, где ρ = { ∈ R × R | x + y = 0}, ϕ = { ∈ 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. Докажите, что отношение ρ ⇔ 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, определяемое следующим образом: R , если a – b = c – d.
а) Показать, что R есть отношение эквивалентности.
б) Описать классы эквивалентности.
7. Используя математическую индукцию, докажите для целого n ≥ 0, что 8n+2 + 92n+1 делится на 8. Расположите следующие 5 функций в порядке увеличения скорости роста (каждая функция есть O (следующая)): 106 ln (ln n), 1010, n2, 4ln n /200, n3.

Вариант 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 –1(A \ B) = f –1(A) \ f –1(B).
7. Числа Фибоначчи определяются следующим рекуррентным правилом: F0 = 1, F1 = 1, Fk+2 = Fk+1 + Fk для k ≥ 0.
Докажите с помощью математической индукции, что для любого натурального n ≥ 0 имеем 2
8. Расположите следующие 5 функций в порядке увеличения скорости роста (каждая функция есть O (следующая)): 200en, 106 n2, 4ln n , n3/10, 1000000.

Вариант 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 (следующая)):
1000 n , 0.01n3, 666, 554 ln (ln n), 0.001n!.

Вариант 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, определяемое следующим образом: R , если a – b = c – d.
а) Показать, что R есть отношение эквивалентности.
б) Описать классы эквивалентности.
7. Используя математическую индукцию, докажите для целого n ≥ 0, что число 32n+3 + 2n делится на 7.
8. Расположите следующие 5 функций в порядке увеличения скорости роста (каждая функция есть O (следующая)):
ln n, n! + n, 10n ln (ln n), 23n2 + 12345, 0.12345(ln n)ln n .

Вариант 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 ⇔ «x2= y2», определенного на множестве R вещественных чисел.
6. Найдите f(A), где A = { ∈ R × R | y = 2x + 3} для следующих отображений: а) f: → ; б) f: → . Изобразите на плоскости множества A и f(A).
7. Используя математическую индукцию, докажите для целого n ≥ 1, что
8. Расположите следующие 5 функций в порядке увеличения скорости роста (каждая функция есть O (следующая)):
2lnn /106, e, 106 ln n , (ln n)2/100, 1000 2 ln n .

Вариант 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 (следующая)): 6 + n/1000, ln (ln n), (ln n)2, n2 + 1000n, 2n.

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

Вариант 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, что 5n+1 + 2 ⋅3n +1 делится на 8.
8. Расположите следующие 5 функций в порядке увеличения скорости роста (каждая функция есть O (следующая)): 2345 n , 6666, n2 + ln n, 23n2 + 1000n, 2000n ln n.

Вариант 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, определяемое следующим образом: R , если 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 (следующая)): 10n3, 1000(ln n)2, n2 + 3000ln n, 2n/123, 50 n .

Вариант 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 = { ∈ R × R | y = 2x + 3} для следующих отображений: а) f: → ; б) f: → <–y, –x>. Изобразите на плоскости множества A и f(A).
7. Используя математическую индукцию, докажите для целого n ≥ 1, что
8. Расположите следующие 5 функций в порядке увеличения скорости роста (каждая функция есть O (следующая)): en, 2 ln n + 2000, 2n, 123456, 106 n.

Вариант 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 имеем 2
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 (следующая)):