|
|
Математическая логика. Контрольная работа №2. Контрольная работа 2 по дисциплине Математическая логика и теория алгоритмов Студент гр з431П105 Егор Михайлович Комаров
Министерство науки и высшего образования Российской Федерации
Федеральное государственное бюджетное образовательное
учреждение высшего образования
ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ
УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)
КОНТРОЛЬНАЯ РАБОТА №2
по дисциплине «Математическая логика и теория алгоритмов»
Студент гр. з-431П10-5
Егор Михайлович Комаров
Направления подготовки
09.03.01
Вариант №2
«06» февраля 2022 г.
Руководитель:
ассистент каф. АСУ
старший преподаватель
каф. АСУ
А.В. Елецкая
«__»___________2022 г.
2022
Вариант 2
1. Проверить для произвольных множеств, что
(A∪ B) ∩ (C∪ D) = (A∩ C) ∪ (B∩ C) ∪ (A∩ D) ∪ (B∩ D).
Пусть x ϵ(A∪ B) ∩ (C∪ D). Значит x ϵ(A∪ B) и x ϵ (C∪ D). Значит x ϵAилиxϵB и xϵCили xϵD. Поэтому xϵ (A∩ C) или xϵ (B∩ C) или xϵ (A∩ D) или xϵ (B∩D). То есть xϵ(A∩ C) ∪ (B∩ C) ∪ (A∩ D) ∪ (B∩ D). Значит (A∪B)∩(C∪D)⊆(A∩C)∪(B∩C)∪(A∩D)∪(B∩D).
Пусть x ϵ(A∩ C) ∪ (B∩ C) ∪ (A∩ D) ∪ (B∩ D). . Значит xϵ (A∩ C) или xϵ (B∩ C) или xϵ (A∩ D) или xϵ (B∩D). То есть (xϵAи xϵC или xϵBи xϵC) или (xϵAи xϵD или xϵB и xϵD). Значит, ((xϵAили xϵB) и xϵC) или ((xϵA или xϵB) и xϵD). Поэтому ((xϵAили xϵB) и (xϵC или xϵD)). Следовательно, x ϵ(A∪ B) ∩ (C∪ D). Тогда (A∪B)∩(C∪D)⊆(A∪B)∩(C∪D).
Таким образом, (A∪B)∩(C∪D)⊆(A∩C)∪(B∩C)∪(A∩D)∪(B∩D) и (A∪B)∩(C∪D)⊆(A∪B)∩(C∪D).
Поэтому (A∪ B) ∩ (C∪ D) = (A∩ C) ∪ (B∩ C) ∪ (A∩ D) ∪ (B∩ D).
2. Является ли тавтологией формула (¬B ⊃ ¬A) ⊃ ((¬B ⊃ A) ⊃ B)?
(X ⊃ Y) ¬X∨Y, и ¬(X∨Y)
¬X&¬Y и ¬(¬X)
X
Тогда
(¬B ⊃ ¬A)
B∨¬A
(¬B ⊃ A)
B∨A
((B∨A) ⊃ B)
(¬ (B∨A) ∨ B)
(¬ B&¬ A) ∨ B
Воспользуемся формулой
(X&Y) ∨Z
(X∨Z )&(Y ∨Z)
(¬ B&¬ A) ∨ B
(¬ B∨ B )&(¬ A ∨ B)
Но (¬ Х∨ Х ) - истина, значит(¬ B∨ B ) - истина и
(¬ B∨ B )&(¬ A ∨ B)
¬ A ∨ B
Тогда
(B∨¬A)⊃ (¬ A ∨ B)
(B∨¬A)⊃ (B∨¬A)
¬ (B∨¬A)∨ (B∨¬A)-истина по свойству (¬ Х∨ Х ) - истина
Таким образом, формула является тавтологией.
3. Переведите с естественного языка на язык логики предикатов:
Логарифмы всех положительных рациональных чисел иррациональны.
Универсум: M = {числа}. Предикаты: Z(x) ≡ «x — рациональное», O(x) ≡ «x — иррациональное».
Формула: ∀x (Z(x) ⊃ O(log x))
4. Переведите с естественного языка на язык логики предикатов:
Доисторические ящеры при встречах уступали дорогу друг другу.
Универсум: M = { Доисторические ящеры }. Предикат: Z(x,y) ≡ «x уступает дорогу y ».
Формула: ∀x,y(Z(x,y) & Z(y,x))
5. Пусть ρ и ϕ — бинарные отношения на некотором множестве. Докажите, что (ρ ∪ ϕ)–1 = ρ–1 ∪ ϕ–1.
Доказательство
Возьмём ϵ(ρ ∪ ϕ)–1 ↔ ϵ ρ ∪ ϕ. Т.е. ϵ ρ или ϵ ϕ. Значит ϵρ‑1 или ϵϕ–1↔ϵ ρ–1 ∪ ϕ–1. Значит (ρ ∪ ϕ)–1 ⊆ ρ–1 ∪ ϕ–1.
Возьмём ϵ ρ–1 ∪ ϕ–1↔(ϵ ρ-1 или ϵ ϕ-1). Значит (ϵρ или ϵϕ)↔ϵ ρ ∪ ϕ. Значит ϵ (ρ ∪ ϕ)–1 .Следовательно ρ–1∪ϕ–1⊆(ρ∪ϕ)–1.
Т.е. (ρ ∪ ϕ)–1 ⊆ ρ–1 ∪ ϕ–1 и ρ–1∪ϕ–1⊆(ρ∪ϕ)–1. Поэтому (ρ ∪ ϕ)–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?
f ° g ° f=2x+1+1
f ° f °g=2x+2
f ° g ° g=
g ° f ° g=
Отношения f ‑1 и g –1 являются отображениями:
f ‑1 (x)=x-1
g –1 (x)=log2(x)
7. Докажите, используя математическую индукцию, равенство 
для целых n ≥ 2.
Проводим математическую индукцию по n.
Базис индукции для n = 2
Для доказательства индуктивного перехода предположим, что для n = k выполнено
 (*)
и
В соответствии с (*)
Доказательство закончено.
8. Расположите следующие 5 функций в порядке увеличения скорости роста (каждая функция есть O (следующая)):
Решение. Для этих функций правильный порядок следующий:
 |
|
|
Скачать 38.63 Kb.