Основы логики для бизнес-информатиков. Отображения и отношения
Покупка
Основная коллекция
Издательство:
Новосибирский государственный технический университет
Автор:
Яхъяева Гульнара Эркиновна
Год издания: 2025
Кол-во страниц: 67
Дополнительно
Вид издания:
Учебное пособие
Уровень образования:
ВО - Бакалавриат
ISBN: 978-5-7782-5332-2
Артикул: 875020.01.99
Учебное пособие составлено на основе курса лекций, который читается автором для студентов II курса факультета бизнеса Новосибирского государственного технического университета. В работе систематически изложены основы теории отображений, теории бинарных отношений и теории графов. В конце каждой главы приводится набор заданий, выполнение которых направлено на закрепление теоретического материала.
Учебное пособие предназначено для студентов, обучающихся по направлению 38.03.05 «Бизнес-информатика».
Тематика:
ББК:
УДК:
- 33: Экономика. Экономические науки
- 510: Фундаментальные и общие проблемы математики. Основания математики, математ. логика
ОКСО:
- ВО - Бакалавриат
- 38.03.05: Бизнес-информатика
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
Министерство науки и высшего образования Российской Федерации НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ Г. Э. ЯХЪЯЕВА ОСНОВЫ ЛОГИКИ ДЛЯ БИЗНЕС-ИНФОРМАТИКОВ ОТОБРАЖЕНИЯ И ОТНОШЕНИЯ Утверждено Редакционно-издательским советом университета в качестве учебного пособия НОВОСИБИРСК 2025
УДК 510.6(075.8)
Я919
Рецензенты:
д-р физ.-мат. наук,
зав. каф. общей информатики ФИТ НГУ Д. Е. Пальчунов
канд. экон. наук, доцент И. В. Асланова
Работа подготовлена на кафедре экономической информатики
Яхъяева Г. Э.
Я919
Основы логики для бизнес-информатиков. Отображения
и отношения : учебное пособие / Г. Э. Яхъяева. – Новосибирск :
Изд-во НГТУ, 2025. – 67 с.
ISBN 978-5-7782-5332-2
Учебное пособие составлено на основе курса лекций, который читается автором для студентов II курса факультета бизнеса Новосибирского государственного технического университета. В работе систематически изложены основы теории отображений, теории бинарных отношений и теории графов. В конце каждой главы приводится набор заданий, выполнение которых направлено на закрепление теоретического материала.
Учебное пособие предназначено для студентов, обучающихся по
направлению 38.03.05 «Бизнес-информатика».
УДК 510.6(075.8)
ISBN 978-5-7782-5332-2
© Яхъяева Г. Э., 2025
© Новосибирский государственный
технический университет, 2025
Г л а в а 1 ОТОБРАЖЕНИЯ 1.1. ПРЯМОЕ ПРОИЗВЕДЕНИЕ МНОЖЕСТВ Пусть нам даны два объекта 𝑎 и 𝑏 (𝑎്𝑏). Двухэлементное множество ሼ𝑎, 𝑏ሽ принято также называть неупорядоченной парой. В самом деле, независимо, в каком порядке – ሼ𝑎, 𝑏ሽ или ሼ𝑏, 𝑎ሽ – будут записаны элементы, они будут образовывать одно и то же множество. Что же тогда является упорядоченной парой? Определение 1. Множества вида ൛𝑎, ሼ𝑎, 𝑏ሽൟ называются упорядоченными парами (обозначается ሺ𝑎, 𝑏ሻ). Элемент 𝑎 называется первой координатой пары ሺ𝑎, 𝑏ሻ, элемент 𝑏 – второй координатой пары ሺ𝑎, 𝑏ሻ. Следующие утверждения показывают правомерность такого определения упорядоченной пары. Утверждение 1. Для любых элементов 𝑎 и 𝑏 если 𝑎്𝑏, то ሺ𝑎, 𝑏ሻ് ሺ𝑏, 𝑎ሻ. Доказательство. Для того чтобы доказать неравенство двух множеств, достаточно найти хотя бы один элемент, который принадлежит одному множеству и не принадлежит другому. В качестве такого элемента можно выбрать элемент 𝑎, так как из определения непосредственно вытекает, что 𝑎∈ሺ𝑎, 𝑏ሻ и 𝑎∉ሺ𝑏, 𝑎ሻ. Утверждение 2. Для любых элементов 𝑎, 𝑏, 𝑐, 𝑑 имеет место равенство ሺ𝑎, 𝑏ሻൌሺ𝑐, 𝑑ሻ тогда и только тогда, когда 𝑎ൌ𝑐 и 𝑏ൌ𝑑.
Доказательство. Пусть ሺ𝑎, 𝑏ሻൌሺ𝑐, 𝑑ሻ, т. е. ൛𝑎, ሼ𝑎, 𝑏ሽൟൌ൛𝑐, ሼ𝑐, 𝑑ሽൟ. Мы имеем два варианта равенства элементов: 1ሻ 𝑎ൌ𝑐, ሼ𝑎, 𝑏ሽൌሼ𝑐, 𝑑ሽ; 2ሻ 𝑎ൌሼ𝑐, 𝑑ሽ, ሼ𝑎, 𝑏ሽൌ𝑐. В первом случае из равенства 𝑎ൌ𝑐 вытекает равенство 𝑏ൌ𝑑. Во втором случае если 𝑎ൌሼ𝑐, 𝑑ሽ, то ൛ሼ𝑐, 𝑑ሽ, 𝑑ൟൌ𝑐, а этого быть не может (например, никакой трактор не может быть деталью собственного двигателя). Таким образом, справедлив только первый случай. Пусть теперь 𝑎ൌ𝑐 и 𝑏ൌ𝑑. Докажем равенство соответствующих упорядоченных пар. Из равенства элементов следует равенство множеств ሼ𝑎, 𝑏ሽൌሼ𝑐, 𝑑ሽ. Тогда мы получим равенство множеств ൛𝑎, ሼ𝑎, 𝑏ሽൟൌ ൛𝑐, ሼ𝑐, 𝑑ሽൟ. Определение 2. Прямым (декартовым) произведение множеств 𝐴 и 𝐵 называется множество всевозможных упорядоченных пар, первые координаты которых принадлежат множеству 𝐴, а вторые – множеству 𝐵, т. е. 𝐴ൈ𝐵ൌሼሺ𝑎, 𝑏ሻ|𝑎∈𝐴, 𝑏∈𝐵ሽ. Например, пусть 𝐴ൌሼ1, 3, 4ሽ и 𝐵ൌሼ1, 2, 3ሽ. Тогда 𝐴ൈ𝐵ൌሼሺ1, 1ሻ; ሺ1, 2ሻ; ሺ1, 3ሻ; ሺ3, 1ሻ; ሺ3, 2ሻ; ሺ3, 3ሻ; ሺ4, 1ሻ; ሺ4, 2ሻ; ሺ4, 3ሻሽ. Если элементы множества 𝐴 изобразить точками на оси OX, а элементы множества 𝐵 – на оси OY декартовой системы координат, то множество 𝐴ൈ𝐵 будет образовано соответствующими точками плоскости (рис. 1). Рис. 1. Декартово произведение множеств
Рассмотрим теперь множество 𝐵ൈ𝐴: 𝐵ൈ𝐴ൌሼሺ1, 1ሻ; ሺ1, 3ሻ; ሺ1, 4ሻ; ሺ2, 1ሻ; ሺ2, 3ሻ; ሺ2, 4ሻ; ሺ3, 1ሻ; ሺ3, 3ሻ; ሺ3, 4ሻሽ. Легко заметить, что в данном случае 𝐴ൈ𝐵 ്𝐵ൈ𝐴. Так, например, элемент ሺ4, 1ሻ принадлежит множеству 𝐴ൈ𝐵 и не принадлежит множеству 𝐵ൈ𝐴. Таким образом, прямое произведение множеств не является коммутативной операцией. Результатом прямого произведения двух множеств будет множество элементов, отличных от исходных, поэтому свойство идемпотентности также выполняться не будет, т. е. 𝐴ൈ𝐴 ്𝐴. Однако операция прямого произведения дистрибутивна относительно объединения, пересечения и разности множеств: Утверждение 3. Для любых множеств 𝐴, 𝐵, 𝐶 имеет место 1) A ൈሺB ∪CሻൌሺA ൈBሻ∪ሺA ൈCሻ; 2) 𝐴ൈሺ𝐵∩𝐶ሻൌሺ𝐴ൈ𝐵ሻ∩ሺ𝐴ൈ𝐶ሻ; 3) 𝐴ൈሺ𝐵\𝐶ሻൌሺ𝐴ൈ𝐵ሻ\ሺ𝐴ൈ𝐶ሻ. Доказательство. Докажем только первое свойство, оставляя доказательство двух других читателю. Пусть элемент 𝑥 принадлежит множеству 𝐴ൈሺ𝐵∪𝐶ሻ, тогда 𝑥 представляет собой упорядоченную пару ሺ𝑥ଵ, 𝑥ଶሻ такую, что 𝑥ଵ∈𝐴 и 𝑥ଶ∈𝐵∪𝐶. Из того, что 𝑥ଶ∈𝐵∪𝐶, следует, что 𝑥ଶ∈𝐵 или 𝑥ଶ∈𝐶. Из того, что 𝑥ଵ∈𝐴 и 𝑥ଶ∈𝐵, следует 𝑥ൌሺ𝑥ଵ, 𝑥ଶሻ∈𝐴ൈ𝐵. Аналогично получим, что 𝑥∈𝐴ൈ𝐶. Следовательно, 𝑥∈ሺ𝐴ൈ𝐵ሻ∪ሺ𝐴ൈ𝐶ሻ. Пусть теперь 𝑥∈ሺ𝐴ൈ𝐵ሻ∪ሺ𝐴ൈ𝐶ሻ. По определению объединения имеем 𝑥ൌሺ𝑥ଵ, 𝑥ଶሻ∈𝐴ൈ𝐵 или 𝑥ൌሺ𝑥ଵ, 𝑥ଶሻ∈𝐴ൈ𝐶. Из этого вытекает, что, с одной стороны, 𝑥ଵ∈𝐴, а с другой стороны – 𝑥ଶ∈𝐵 или 𝑥ଶ∈𝐶. Тогда по определению объединения получим 𝑥ଶ∈𝐵∪𝐶 и, следовательно, 𝑥∈𝐴ൈሺ𝐵∪𝐶ሻ. Определение 3. Пара ൫ሺ… ሺ𝑎ଵ, 𝑎ଶሻ, … , 𝑎ିଵሻ, 𝑎൯ называется кортежем длины n (или упорядоченной n-кой) и обозначается ሺ𝑎ଵ, 𝑎ଶ, … , 𝑎ିଵ, 𝑎ሻ. Элемент 𝑎ሺ𝑖ൌ1, … , 𝑛ሻ называется i-й координатой кортежа ሺ𝑎ଵ, 𝑎ଶ, … , 𝑎ିଵ, 𝑎ሻ. Определение 4. Прямым произведением множеств 𝐴ଵ, 𝐴ଶ, … , 𝐴 называется множество всевозможных кортежей длины n, i-я координата которых принадлежит множеству 𝐴ሺ𝑖ൌ1, … , 𝑛ሻ, т. е. 𝐴ଵൈ𝐴ଶൈ… ൈ𝐴ൌሼሺ𝑎ଵ, 𝑎ଶ, … , 𝑎ሻ | 𝑎∈𝐴, 𝑖ൌ1, … , 𝑛ሽ.
1.2. СООТВЕТСТВИЯ МЕЖДУ МНОЖЕСТВАМИ Пусть нам дано прямое произведение 𝐴ൈ 𝐵 множеств 𝐴 и 𝐵. Множество 𝐶⊆𝐴ൈ𝐵 называется соответствием между множествами 𝐴 и 𝐵. Например, пусть 𝐴ൌ ሼ𝑎, 𝑏, 𝑐, 𝑑, 𝑒ሽ и 𝐵ൌ ሼ1,2, 3, 4, 5ሽ. Тогда одним из примеров соответствия между множествами 𝐴 и 𝐵 является следующее множество упорядоченных пар: 𝐹ൌ ሼሺ𝑎, 1ሻ; ሺ𝑏, 1ሻ; ሺ𝑐, 2ሻ; ሺ𝑐, 3ሻ; ሺ𝑑, 4ሻሽ. Элементам множества 𝐴 ставятся в соответствие элементы множества 𝐵 (рис. 2). Рис. 2. Соответствие между множествами Множество 𝐶ൌ𝐴ൈ 𝐵 называется полным соответствием, т. е. каждому элементу из множества 𝐴 соответствует каждый элемент множества 𝐵. Пустое множество ∅ можно рассматривать как пустое соответствие, так как ∅∈𝐴ൈ𝐵. Множество всех элементов множества 𝐴, которым поставлены в соответствие элементы множества 𝐵, называется областью определения соответствия 𝐹 (обозначается 𝐷𝑜𝑚ሺ𝐹ሻ), т. е. 𝐷𝑜𝑚ሺ𝐹ሻൌሼ 𝑥∈𝐴 | ∃ 𝑦: ሺ𝑥, 𝑦ሻ∈ 𝐹 ሽ. Множество всех элементов множества 𝐵, которые поставлены в соответствие элементам множества 𝐴, называется областью значений соответствия 𝐹 (обозначается 𝐼𝑚ሺ𝐹ሻ), т. е. 𝐼𝑚ሺ𝐹ሻൌሼ𝑦∈𝐵 | ∃ 𝑥: ሺ𝑥, 𝑦ሻ∈𝐹ሽ. Определение 5. Соответствие 𝐹⊆𝐴ൈ𝐵 называется функцией (или отображением), если для любого 𝑥∈𝐴 и для любых 𝑦, 𝑧∈ 𝐵 из того, что ሺ𝑥, 𝑦ሻ∈𝐹 и ሺ𝑥, 𝑧ሻ∈𝐹, следует, что 𝑦ൌ𝑧.
Таким образом, соответствие 𝐹 называется функциональным, если каждому элементу 𝑥 из множества 𝐴 ставится в соответствие ровно один элемент из 𝐵 (рис. 3). Очевидно, что если соответствие 𝐹⊆𝐴ൈ𝐵 является отображением, то выполняются условия 𝐷𝑜𝑚ሺ𝐹ሻൌ𝐴 и 𝐼𝑚ሺ𝐹ሻ⊂𝐵. Рис. 3. Отображение Далее для обозначения отображений будем использовать прописные латинские буквы и функциональную запись: вместо 𝐹⊆𝐴ൈ𝐵 будем записывать 𝑓: 𝐴→𝐵 и вместо ሺ𝑥, 𝑦ሻ∈𝐹 будем записывать 𝑓ሺ𝑥ሻൌ𝑦. Примером отображения может служить любая числовая функция (например, 𝑦ൌ√𝑥ଶ ఱ ), где 𝐴 совпадает с областью допустимых значений данной функции. Если 𝐷𝑜𝑚ሺ𝑓ሻൌ𝐴 и 𝐼𝑚ሺ𝑓ሻൌ𝐵, то говорят, что 𝑓 отображает 𝐴 на 𝐵 (обозначается 𝑓: 𝐴 на → 𝐵). Отображение «на» называют также сюръективным отображением. Два отображения 𝑓 и 𝑔, определенные на одном и том же прямом произведении 𝐴ൈ𝐵, называются равными, если они равны как множества, т. е. пара ሺ𝑥, 𝑦ሻ∈𝐴ൈ𝐵 принадлежит 𝑓 тогда и только тогда, когда она принадлежит 𝑔. Например, отображения 𝑓ሺ𝑥ሻൌሺ𝑥1ሻሺ𝑥െ1ሻ и 𝑔ሺ𝑥ሻൌ𝑥ଶെ1 равны. Заметим, что если 𝑓ൌ𝑔, то 𝐷𝑜𝑚ሺ𝑓ሻൌ𝐷𝑜𝑚ሺ𝑔ሻ и 𝐼𝑚ሺ𝑓ሻൌ𝐼𝑚ሺ𝑔ሻ. Однако обратное утверждение не всегда справедливо. Например, отображения 𝑓ሺ𝑥ሻൌ𝑥ଶ и 𝑔ሺ𝑥ሻൌ𝑥ସ имеют равные области определения и области значения, но все же не являются равными, так как имеют только один общий элемент – пару ሺ0, 0ሻ.