Министерство науки и высшего образования Российской Федерации

Федеральное государственное бюджетное образовательное

учреждение высшего образования

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ

УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)

Кафедра автоматизированных систем управления (АСУ)


Отчет

По дисциплине «Математическая логика и теория алгоритмов»
Контрольная работа №2

Вариант 11

	Выполнил: Студент гр. _______________ / «____»_______________2023г.
	Проверил: ______________ / «____»_______________2023г.

Томск 2023

Содержание

1. Введение……………………………………………………...…………………3

2. Задача № 1……………………………………………….………………………4

3. Задача № 2……………………………………………….………………………4

4. Задача № 3…………………………………………………….…………………5

5. Задача № 4……………………………………………………….………………6

6. Задача № 5………………………………………………………….……………6

7. Задача № 6…………………………………………………………….…………7

8. Задача №7……………………………………………………………….………7

9. Задача № 8………………………………………………………….……………8

10. Заключение………………..……………………………...………………..…11

11. Список использованной литературы…………………...……...……………12

Введение

Контрольная работа №2 по дисциплине «Математическая логика и теория алгоритмов» для практического освоения задач по темам:

1) «операции с множествами»,

2) «отношения»,

3) «отображения»,

4) «эквивалентность и порядок»,

5) «логика высказываний»,

6) «язык логики предикатов»,

7) «математическая индукция»,

8) «сравнение скорости роста».

Задача №1. Проверить для произвольных множеств, что



Докажем, что заданная равносильность не выполняется в общем случае. Возьмём множества таким образом, чтобы выполнялось: . Можно представить множества кругами Эйлера:

---

B



C

A


Видим, что в этом случае выполняется , поскольку . С другой стороны, условие не выполняется, поскольку ввиду включения множества и ввиду того, что множества не пересекаются ( ).

Построим пример:



В этом случае:





Таким образом, для произвольных множеств (в общем случае) не выполняется .

Задача №2. Является ли тавтологией формула

Нам нужно проверить равносильность левой и правой частей формулы. Левая часть формулы: . Импликация ложна только в случае, когда из истины следует ложь, поэтому принимает значение “ложь” только в случае, когда принимает значение “истина”, а - значение “ложь”. Конъюнкция принимает значение “истина” только при истинности . Получаем, что принимает значение “ложь” только на одном наборе переменных:

---

.

Правая часть формулы: . Так как импликация ложна только в случае, когда из истины следует ложь, то принимает значение “ложь” только в случае, когда принимает значение “истина”, а - значение “ложь”. В свою очередь, принимает значение “ложь” только в случае истинности и ложности . Получаем, что принимает значение “ложь” тоже на одном наборе переменных: .

Видим, что обе части заданной формулы принимают значение “ложь” на одних и тех же наборах переменных (в данном случае на одном наборе). Значит, они принимают и значение “истина” на одних и тех же наборах переменных. Следовательно, эти части эквивалентны, и формула является тавтологией.

Задача №3. Переведите с естественного языка на язык логики предикатов: “Всякое чётное число, большее 2, есть сумма двух простых чисел.”

Универсум: множество натуральных чисел.

Предикаты:









Формула:



Задача №4. Переведите с естественного языка на язык логики предикатов: “Хотя 60 делится на 2, 3, 4, 5 и 6, но это не значит, что 60 делится на любое натуральное число.”

---

Вводим два универсальных множества:

множество натуральных чисел,

Предикаты:





Формула строим в смысловом отношении следующим образом: 60 делится на любое число из множества , но существует такое натуральное число, на которое число 60 не делится.



Задача №5. Для бинарного отношения ( - множества из целых чисел) выясните, какими свойствами оно обладает (рефлексивность, симметричность, антисимметричность, транзитивность) и какими не обладает.

Не для любого множества из целых чисел выполняется : для непустых множеств . Значит, отношение не является рефлексивным.

Симметричность отношения ρ: из того, что следует , т.е. из следует . Отношение симметрично.

Отношение не антисимметрично: если , то отсюда не следует, что Например, .

Отношение не транзитивно: если

---

, то отсюда не следует, что . Например, .

Таким образом, отношение является симметричным, но не является рефлексивным, антисимметричным и транзитивным.

Задача №6. Пусть - отображения .

Найдите отображения .

Композиция отображений следующим образом:



Тогда отображения :





Задача №7. Используя математическую индукцию, докажите для целого , что



Проверим выполнение для базиса индукции



Проверим справедливость индуктивного перехода: докажем, что из справедливости равенства для следует выполнение равенства для . Пусть для равенство выполняется:



Нам нужно доказать выполнение равенства для :









Индуктивный переход проверен.

Следовательно, для любого целого

---

Смотрите также файлы

• Управление стратегическими изменениями в организации.doc

• Языковой функции.docx

• Контрольная работа по дисциплине Философия Вариант 4 Работу выполнил(а) студент(ка) Агеева Т. А.doc

• Курсовая работа по дисциплине Учет и анализ (финансовый учет, управленческий учет, финансовый анализ) тема Учет материальнопроизводственных запасов и анализ использования материальных ресурсов.doc

• И (или) дад 90 мм рт ст. Этиология аг артериальная гипертензия по этиологии может быть.pptx