Файл: Контрольная работа по дисциплине Математическая логика и теория алгоритмов.docx
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 26.10.2023
Просмотров: 282
Скачиваний: 15
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РФФедеральное государственное бюджетное образовательное учреждение высшего образованияТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТСИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)КОНТРОЛЬНАЯ РАБОТАпо дисциплине «Математическая логика и теория алгоритмов»Студент гр. з-442П12-5М.Ю.СлесареваНаправления подготовки 09.03.03«20» марта 2023 г. Руководитель: Ассистент каф. АСУСт. преподаватель каф. АСУ____________ А.В. Елецкая «____» ____________2023 г. 2023Вариант 18 1. Проверить тождество A Δ (A Δ B) = BРешение. Используя основные тождества алгебры множеств, преобразуем левую и правую часть к одному множеству. Начнем с левой части. A Δ (A Δ B) = (по определению Δ) (A \ (A Δ B)) ((A Δ B) \ A) = = (A ¬ (A Δ B)) ((A Δ B) ¬A) = (по определению Δ) (A ¬ ((A ¬B) (B ¬A))) (((A ¬B) (B ¬A)) ¬A). Преобразуем отдельно множества (A ¬ ((A ¬B) (B ¬A))) и (((A ¬B) (B ¬A)) ¬A). a) (A ¬((A ¬B) (B ¬A))) = (закон де Моргана) (A (¬ (A ¬B) ¬ (B ¬A))) = ( по закону де Моргана) (A ((¬A ¬ ¬B) (¬B ¬ ¬A))) = = (A ((¬A B) (¬B A))) = A (¬A B) (¬B A) = (дважды применяя закон ассоциативности) A (¬B A) (¬A B) = A (A ¬B) (¬A B) = (по закону поглощения) A (¬A B) = (по закону дистрибутивности) (A ¬A) (A B) = (так как подчёркнутое множество пустое) A B. b) Аналогично преобразуя множество ((A ¬B) (B ¬A)) ¬A, получаем((A ¬B) (B ¬A)) ¬A = (A ¬B ¬A) (B ¬A ¬A) = = (A ¬A ¬B) (B ¬ A) = ( ¬B) (B ¬ A) = (B ¬ A) = = B ¬ AТаким образом, левая часть преобразована к множеству (A B) (B ¬ A) =(B A) (B ¬ A) = B (A ¬ A)= B U= B. Следовательно, тождество доказано.
2. Что можно сказать об истинностном значении высказывания p (¬r ¬q), если p (q r) имеет значение истина?Решение. Так как ¬r ¬ q = ¬ ¬r ¬ q = r ¬ q = ¬ q r = q r, тоp (¬r ¬q) = p (q r) = И.3. Переведите с естественного языка на язык логики предикатов: Два целых числа могут делиться друг на друга, но не быть равными.Решение. Универсум: Z = целые числа. Предикаты: x/y «x делится на y», xy «m не равно n». Формула: x, y((x /y) (x y)).4. Переведите с естественного языка на язык логики предикатов: Не все студенты отличники или спортсмены.Решение. Универсум: M = {люди}. Предикаты: C(x) «x студент» O(x) «x отличник», S(x) «x спортсмен». Формула: x(С(x) & O(x) & S(x)).5. Для бинарного отношения x ρ y ⇔ «x × y> 1», определенного на множестве R вещественных чисел, выясните, какими свойствами оно обладает (рефлексивность, симметричность, антисимметричность, транзитивность) и какими не обладает.Решение. Отношение ρ не обладает рефлексивностью, так как, например, при x = 0 получим 0 ×0 = 0 <1. Отношение ρ обладает симметричностью, так как для любых вещественных x, y из того, что x × y> 1 следует, что y ×x> 1 (по свойству симметричности умножения вещественных чисел). Отношение ρ не является транзитивным, так как, например, при при x = 1, y = 4, z= 0,5 получим 1 ×4 = 4 > 1 и 4 ×0,5 = 2 > 1, но 1 ×0,5 = 0,5 < 1. Таким образом, отношение ρ является симметричным и не является рефлексивным и транзитивным.6. Пусть f отображение R в R. Рассмотрим отношение a ρ b ⇔ f(a) ≤ f(b). Приведите примеры таких отображений f, для которых отношение ρ является отношением частичного порядка, и примеры таких f, что ρ не является отношением частичного порядка.Решение. При f(x) = x отношение ρ не симметрично, например, 1 ≤ 2, но 2 ≤ 1 не выполнено. Отношение является антисимметричным, поскольку
x ≤ y и y ≤ x влекут x = y. Отношение ρ, очевидно, является транзитивным, ибо если x ≤ y и y ≤ z, то x ≤ z. Таким образом, при f(x) = x отношение ρ является отношением частичного порядка.При f(x) = 1 отношение ρ не является антисимметричным, поскольку, например, f(2)≤ f(3) и f(3) ≤ f(2) не влечёт 2 = 3. Таким образом, при f(x) = 1 отношение ρ не является отношением частичного порядка.7. Используя математическую индукцию, докажите для целого n ≥ 1, что .Решение. при n = 1, , .Для доказательства индуктивного перехода предположим, что для n = k выполнено . Имеем для n = k + 1: . Что и требовалось доказать.8. Расположите следующие 5 функций в порядке увеличения скорости роста (каждая функция есть O (следующая)): , , , , .Решение. Так как любая экспонента растёт быстрее любой степенной функции, а любая степенная функция растёт быстрее любого логарифма, то наибольшую скорость роста имеют функции и , причём, очевидно, что . Далее, очевидно, , т.е. и , т.е. .Таким образом, , , ,
2. Что можно сказать об истинностном значении высказывания p (¬r ¬q), если p (q r) имеет значение истина?Решение. Так как ¬r ¬ q = ¬ ¬r ¬ q = r ¬ q = ¬ q r = q r, тоp (¬r ¬q) = p (q r) = И.3. Переведите с естественного языка на язык логики предикатов: Два целых числа могут делиться друг на друга, но не быть равными.Решение. Универсум: Z = целые числа. Предикаты: x/y «x делится на y», xy «m не равно n». Формула: x, y((x /y) (x y)).4. Переведите с естественного языка на язык логики предикатов: Не все студенты отличники или спортсмены.Решение. Универсум: M = {люди}. Предикаты: C(x) «x студент» O(x) «x отличник», S(x) «x спортсмен». Формула: x(С(x) & O(x) & S(x)).5. Для бинарного отношения x ρ y ⇔ «x × y> 1», определенного на множестве R вещественных чисел, выясните, какими свойствами оно обладает (рефлексивность, симметричность, антисимметричность, транзитивность) и какими не обладает.Решение. Отношение ρ не обладает рефлексивностью, так как, например, при x = 0 получим 0 ×0 = 0 <1. Отношение ρ обладает симметричностью, так как для любых вещественных x, y из того, что x × y> 1 следует, что y ×x> 1 (по свойству симметричности умножения вещественных чисел). Отношение ρ не является транзитивным, так как, например, при при x = 1, y = 4, z= 0,5 получим 1 ×4 = 4 > 1 и 4 ×0,5 = 2 > 1, но 1 ×0,5 = 0,5 < 1. Таким образом, отношение ρ является симметричным и не является рефлексивным и транзитивным.6. Пусть f отображение R в R. Рассмотрим отношение a ρ b ⇔ f(a) ≤ f(b). Приведите примеры таких отображений f, для которых отношение ρ является отношением частичного порядка, и примеры таких f, что ρ не является отношением частичного порядка.Решение. При f(x) = x отношение ρ не симметрично, например, 1 ≤ 2, но 2 ≤ 1 не выполнено. Отношение является антисимметричным, поскольку
x ≤ y и y ≤ x влекут x = y. Отношение ρ, очевидно, является транзитивным, ибо если x ≤ y и y ≤ z, то x ≤ z. Таким образом, при f(x) = x отношение ρ является отношением частичного порядка.При f(x) = 1 отношение ρ не является антисимметричным, поскольку, например, f(2)≤ f(3) и f(3) ≤ f(2) не влечёт 2 = 3. Таким образом, при f(x) = 1 отношение ρ не является отношением частичного порядка.7. Используя математическую индукцию, докажите для целого n ≥ 1, что .Решение. при n = 1, , .Для доказательства индуктивного перехода предположим, что для n = k выполнено . Имеем для n = k + 1: . Что и требовалось доказать.8. Расположите следующие 5 функций в порядке увеличения скорости роста (каждая функция есть O (следующая)): , , , , .Решение. Так как любая экспонента растёт быстрее любой степенной функции, а любая степенная функция растёт быстрее любого логарифма, то наибольшую скорость роста имеют функции и , причём, очевидно, что . Далее, очевидно, , т.е. и , т.е. .Таким образом, , , ,
.