Как называется отношение между индивидами

Аппарат теории множеств как называется отношение между индивидами в настоящее время широко применяется для формализованного описания сложных систем и решения различных задач обработки данных, разработки математического обеспечения современных ЭВМ. Теория множеств используется также в читаемых для специальности АСУ курсах 'Теория вероятностей', 'Основы дискретной математики' и других. В методических указаниях, кроме вычислительных задач, содержатся также примеры, способствующие выработке навыков перехода от содержательных представлений и наоборот.

Приведенный ниже текст получен путем автоматического извлечения из оригинального PDF-документа и предназначен для предварительного просмотра.
Изображения (картинки, формулы, графики) отсутствуют.

ПЕРМСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ Кафедра автоматизированных систем обработки информации и управления ТЕОРИЯ МНОЖЕСТВ Методические указания по курсу ''Основы дискретной математики'' для студентов специальности 220200 Пермь 1998 -1- Теория множеств Аппарат теории множеств в настоящее время широко применяется для формализованного описания сложных систем и решения различных задач обработки данных, разработки математического обеспечения современных ЭВМ. Теория множеств используется также в читаемых для специальности АСУ курсах ''Теория вероятностей'', ''Основы дискретной математики'' и других. В методических указаниях, кроме вычислительных задач, содержатся также примеры, способствующие выработке навыков перехода от содержательных представлений и наоборот. Наряду с новыми задачами без дополнительных ссылок использованы задачи из литературы. СПИСОК ЛИТЕРАТУРЫ Основная 1. Шиханович Ю.А. Введение в современную математику. – М.: Наука, 1965.–376 с. 2. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергия, 1980. – 342 с. 3. Шрейдер Ю.А. Равенство. Сходство. Порядок. – М.: Наука, 1972. – 254 с. 4. Столл Р. Множества. Логика. Аксиоматические теории. – М.: Просвещение, 1968. – 231 с. 5. Коршунов Ю.Н. Математические основы кибернетики. – М.: Энергия, 1972. - 376 с. 6. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической ло- гике и теории алгоритмов. – 1975. – 240 с. Дополнительная 1. Александров П.С. Введение в общую теорию множеств и функций. – М.; Л.: Гостехиздат, 1948. – 411 с. 2. Бурбаки Н. Теория множеств. – М.: Мир, 1965. – 366 с. 3. Куратовский К., Мостовский А. Теория множеств. – М.: Мир, 1970. – 416 с. 4. Френкель А., Бар-Хиллел И. Основания теории множеств. – М.: Мир, 1966. - 555 с. -2- Теория множеств СВОЙСТВА МНОЖЕСТВ. ОПЕРАЦИИ НАД МНОЖЕСТВАМИ Понятие ''множества'' относится к числу фундаментальных неопределяемых понятий. Основоположник теории множеств Г.Кантор ввел множество как объединение в одно целое объектов, хорошо различимых нашей интуицией или мыслью. Объекты множества называются элементами множества. Запись х ∈ А читается ''элемент х принадлежит А'' или ''х есть элемент мно – жества А''; х ∉ А - ''х не принадлежит множеству А'', здесь ∈ - знак отношения принадлежности (соответственно ∉- не принадлежности). Множество может задаваться: а) перечислением его элементов А = {х1, х 2,..., х n }, где х i - элемент множества А, (i = 1, n ) индивидами ; б) с помощью описания свойства объектов, по которому они объединяются в одно множество А = { х | С (х) }, где С(х) – характеристическое свойство, которому удовлетворяют элементы этого мно – жества. Два множества считаются равными, если они состоят из одних и тех же элементов. Запись А ⊆ В читается ''А включено в В'' или ''А есть подмножество В'' и означает, что каждый элемент множества А является элементом множества В, здесь ⊆ – знак отношения включения. Запись А ⊂ В читается ''А строго включено в В'' и означает, что А ⊆ В и А ≠ В, где ⊂ - знак отношения строгого включения. Отношение включения обладает следующими свойствами: 1) рефлексивностью – А ⊆ А ; 2) транзитивностью – если А ⊆ В и В ⊆ С, то А ⊆ С ; 3) интуитивным принципом объемности – если А ⊆ В и В ⊆ А, то А = В. Множество, не содержащее элементов, называется пустым и обозначается Ш. Если все рассматриваемые в ходе какого-либо рассуждения множества являются подмножествами некоторого другого множества, то это множество называется универсальным множеством и обозначается U. Новые множества могут задаваться с помощью операций над множествами: объединение А U В = { х | х ∈ А или х ∈ В } ; пересечение А I В = { х | х ∈ А и х ∈ В }; разность А \ B ={ х | х ∈ А и х ∉ В }; симметрическая разность А ∆ В = { х | ( х ∈ А и х ∉ В) или (х ∉ А и х ∈ В ) }, т.е. А ∆ В = (А \ В) U (В \ А). Дополнением множества А будем называть множество А= { х| х∉ А } или А = U \ А. Следовательно, А \ В можно представит как А I В. -3- Теория множеств Для графической иллюстрации отношений между множествами и операций над ними часто используют так называемые диаграммы Эйлера-Венна. Основные законы алгебры множеств: коммутативный А U В = В U А, А I В = В I А; ассоциативный А U ( В U С ) = ( А U В) U С, А I ( В I С ) = ( А I В) I С; дистрибутивный А U ( В I С ) = ( А U В) I ( А U С ), А I ( В U С ) = ( А I В) U ( А I С ); поглощения А U ( А I В) = А, А I ( А U В) = А; де Моргана АU В = АI В, АI В = АU В; идемпотентности А U А = А, А I А = А; А U U =U, А I U =U; А U Ш = А, А I Ш = Ш; исключенного третьего противоречия А U А = U, А I А = Ш; Ш = U, U = Ш; инволюции А = А. Решение уравнений алгебры множеств (с одним неизвестным) вида F1 (Х) = F2 (Х), где Х – неизвестное множество: 1. Представим уравнение в виде F1 (X) ∆ F2 (X) =Ш. 2. Используя законы алгебры множеств, преобразуем уравнение к виду (С I Х ) U ( D I X ) = Ш, где C и D – некоторые множества не содержащие множество Х или его дополнение. 3. Для искомого множества выполняется соотношение D ⊆ Х ⊆ С. Примем стандартные обозначения: N – множество натуральных чисел, Z – множество целых чисел, Q – множество рациональных чисел, R – множество действительных чисел. 1. Что можно сказать о справедливости данных выражений: -4- Теория множеств 1.1. А ∈ Ш? – несправедливо, поскольку пустое множество Ш по определению есть множество, не содержащее никаких элементов. 1.2. {1,2} = {1,2,1}. 1.3. {∆} = { ∇ }. 1.4. А ⊆ Ш. 1.5. А ⊆ {Ш }. 1.6. А ∈ {Ш }. 1.7. {2,3} ∈ { {1,2,3},{1,3}1,2 }. 2. Доказать: 2.1. Ш ≠ {0}. Д о к а з а т е л ь с т в о: множество слева от неравенства – пустое, т.е. не содержа- щее элементов; множество справа содержит элемент 0 (т.е. является одноэлементным множеством). 3. Даны произвольные множества А, В, С : 3.1. В ⊂ А, С ⊂ В. Чему равно А I В I С? А U В U С? А \ С? С \ А? Ре ш е н и е : из свойства транзитивности отношения включения и заданных отношений В ⊂ А, С ⊂ В следует, что С ⊂ А, отсюда ( А I В) I С = С, А U В U С = А, А \ С ≠ Ш, С \ А = Ш. 4. Существуют ли такие непустые множества А, В, С, что 4.1. А I В ≠ Ш, А I С = Ш, ( А I В) \ С = Ш. Р е ш е н и е : из ( А I В) \ С = Ш следует, что А I В ⊆ С. Поскольку по первому условию А I В ≠ Ш, то, значит, существует так элемент х ∈ А, что х ∈ В и х ∈ С. Следовательно, А I С ≠ Ш, что противоречит второму условию ( А I С = Ш ), а значит, множеств А, В, С, удовлетворяющих сразу всем трем условиям не существует. 5. Изобразить на диаграмме Эйлера-Венна множества: 5.1. (А \ В) ∆ (А \ D). Р е ш е н и е : изобразим общий случай расположения множеств А, В и D диаграмме Эйлера-Венна (рис.1); 2) заштрихуем на диаграмме множество Е = А \ В (рис.2); Рис.1 Рис.2 3) штриховкой с другим наклоном отобразим на диаграмме множество F = A \ D (рис.3); -5- Теория множеств Рис.3 Рис.4 4) множество Е ∆ F будет состоять из подмножеств, заштрихованных только в одном (любом) направлении (рис.4). 6. Записать аналитически множество, представленное на диаграмме Эйлера-Венна (рис.5). Рис.5 6.1. Запишем множество, изображенное на рис.5: 1) обозначим заштрихованные части как новые множества E и F; 2) искомое множество G = E U F ; 3) выразим множество Е через множества А, В и С ( Е = ( А I В) \ С) ; 4) выразим F через А, В, С ( F = ( В I С ) \ А) ; 5) G = E U F = [ ( A I B) \ C ] U [( B I C ) \ A ]. Используя законы алгебры множеств, можно упростить это выражение: G = [ ( A I B) I C ] U [ (B I C I A ] = ( A I B I C ) U ( A I B I C ) = = B I [ ( А I С ) U ( А I С ) ] = В I ( А Δ С). Конечное выражение можно было, разумеется, получить и сразу из исходной диаграммы рис.5. 7. Доказать равенство множеств, используя принцип объемности: 7.1. А U В = В U А. Д о к а з а т е л ь с т в о: пусть х ∈ А U В, тогда х ∈ А или х ∈ В, значит, х ∈ В U А. Следовательно, А U В ⊆ В U А. Аналогично, из факта х ∈ В U А следует х ∈ А U В, т.е. В U А ⊆ А U В. 7.7. А I (В \ А) = Ш. -6- Теория множеств 8. Доказать равенство множеств, преобразуя множества к одинаковому виду помощью основных законов алгебры множеств. 8.1. A \ (A \ B) = A I B. Д о к а з а т е л ь с т в о : преобразуем левую часть к виду правой части равенства. Для этого выразим разность через операции пересечения и дополнения, тогда A \ (A \ B) = A I (A I B). По закону де Моргана A I ( A I B) = A I ( A U B ). Применяя закон двойного отрицания, преобразуем A I ( A U B ) = A I (A U B). Применяя дистрибутивный закон операции пересечения относительно объедине – ния, получим A I ( A U B) = ( A I A ) U ( A I B). По закону противоречия A I A = Ш, следовательно ( A I A ) U ( A I B) = Ш U ( A I B ). Используя закон, утверждающий, что объединение любого множества с пустым дает само множество, получим Ш U ( A I B) = A I B, т.е. левая часть выражения равна правой, A I B = A I B, что требовалось доказать. 8.7. ( A I B) U ( A I B) = ( A U B) I ( A U B). 9. Доказать равенство множеств, преобразуя множества к одинаковому виду с помощью основных законов алгебры множеств: 9.1. ( А Δ В) \ С = ( А Δ В) U С. Д о к а з а т е л ь с т в о : преобразуем левую часть к виду правой ________ ____________________ _____________________ ( А Δ В) \ С = [ ( А I В) U ( А I В) ] \ С = [ ( А I В ) U ( А I В) ] I С = ⎡ ⎤ = ⎢( А I В ) U ( А I В ) ⎥ U С = [ А I В I А I В ] U С = ⎡( А U В ) I ( А U В ) ⎤ U С = ⎣ ⎦ ⎢ ⎣ ⎥ ⎦ = [ ( А U В) I ( А U В ) ] U С = [ А I ( А U B]U = [ B I ( A U B)] U C = = [( A I A) U ( A I B)] U [( B I A) U ( B I B)] U C = = [( A I B) U ( B I A)] U C = [( A \ B) U ( B \ A)] U C = ( A Δ B) U C. 9.14. A Δ ( B Δ C ) = ( A Δ B) Δ C (ассоциативный закон симметрической разности множеств). 10. Решить уравнение относительно Х: 10.1. X U A = B. Р е ш е н и е : представим уравнение F1 (X) = F2 (X) в виде F1 (X) ∆ F2 (X) = Ш, ______ т.е. ( X U A) Δ B = Ш. Используя законы алгебры множеств, преобразуем выражение к виду (C I X ) U ( D I X ) = Ш, где C = F3 (A,B), D = F4 (A,B): ( X U A) Δ B = Ш, (( X U A) \ B) U ( B \ ( X U A)) = Ш, ( X I A I B) U ( B I ( X U A)) = Ш, ( X I A I B ) U ( B I X ) U ( A I B) = Ш. -7- Теория множеств Получили выражение, которое не сводится прямо к виду (C I X ) U ( D I X ) = Ш (''мешает'' выражение ( A I B) ). Поэтому, воспользовавшись законом исключенного третьего ( А U А = U ), пересечем скобку ( A I B) с универсумом ( X U X ) (что не нару- шает равенства): ( X I A I B) U ( B I X ) U [( A I B) I ( X U X )] = Ш. Преобразуем, применяя дистрибутивный закон: ( X I A I B) U ( B I X ) U ( A I B I X ) U ( A I B I X ) = Ш, [ X I ( B U ( A I B))] U [ X I (( A I B) U ( A I B ))] = Ш. _ Запишем решение в виде ( A I B) U ( A I B) ⊆ X ⊆ B или A Δ B ⊆ X ⊆ B. Дальнейший содержательный анализ позволяет допустить три варианта: 1) В = Х = Ш (тривиальный вариант), а следовательно, и А = Ш, так как по условию А Δ В ⊆ Х. Тогда решение будет Ш ⊆ Х ⊆ U ; 2) А = В = Ш, тогда А ∆ В = Ш и решение будет Ш ⊆ Х ⊆ В ; 3) В ⊆ А, В I Х = Ш (так как Х ⊆ В ) и тогда А ∆ В ≠ Ш, поскольку иначе (если В I Х = Ш и А I Х = Ш ) А ∆ В ⊄ Х. В этом случае допускаемое расположение непустых множеств изображено на рис.11, где A – I и II, B – I, X – III. II III I Рис.11 11. Решить уравнение относительно Х: 11.1. ( Х U А) \ ( Х I В ) = U. Решение: 1. [ ( X U A) \ ( X I B) ] Δ U = Ш 2. [ (([ X U A) \ ( X I B)) \ U ] U [ U \ (( X U A) \ ( X I B)) ] = Ш, [ (( X U A) \ ( X I B)) I Ш ] U [ U I (( X U A) I ( X I B)) ] = Ш, ( X U A) I ( X U B) = Ш, ( X U A) U ( X U B) = Ш, ( X I A) U ( X I B) = Ш, X I ( A U B) = Ш. Получили уравнение, в котором отсутствует выражение типа (С I Х ). Применя- -8- Теория множеств ем следующий прием: уравнение не изменится, если левую часть его объединить с пустым множеством типа ( Х I Ш ). Поэтому перепишем уравнение в виде [ X I ( A U B)] U ( X I Ш ) = Ш. Запишем решение в виде AU B ⊆ X ⊆U. 12. Найти все подмножества множеств: 12.1. {x | 2 ≤ x ≤ 4; x ∈ N }. Р е ш е н и е : {x | 2 ≤ x ≤ 4; x ∈ N } = {2,3,4}. Тогда все подмножества будут Ш, {2}, {3}, {4}, {2,3}, {2,4}, {3,4}, {2,3,4}, n т.е. количество их рвано 2, где n – количество элементов исходного множества. 15. Доказать, что для произвольных множеств А, В, и С справедливы утверждения: 15.1. Если A ⊆ B и С ⊆ В, то А U С ⊆ В. Д о к а з а т е л ь с т в о : предположим обратное, что А U С ⊄ В. Возьмем такой элемент х, что х ∈ А U С и х ∉ В. Поскольку х ∈ А U С, то х ∈ А или х ∈ С. Но A ⊆ B, а С ⊆ В, следовательно, в любом случае х ∈ В, что противоречит предположению, значит, А U С ⊆ В. 16. Разрешить относительно Х системы: ⎧ А I Х = Ш, 16.1. ⎨ ⎩ В I Х = Ш. Р е ш е н и е : решаем автономно каждое уравнение: ⎧( A I X ) U ( X I Ш) = Ш, ⎪ ⎨ ⎪(B I X ) U ( X I Ш) = Ш. ⎩ Запишем ответы уравнений: Ш ⊆ X ⊆ A, B ⊆ C ⊆ U. Ответ, удовлетворяющий всей системе, запишется следующим образом: Ш U B ⊆ X ⊆ X ⊆ A I U или B ⊆ X ⊆ A. ГРАФИКИ, СООТВЕТСТВИЯ, ОТНОШЕНИЯ. Упорядоченная последовательность элементов вида < x1, x2, …, xn > называется кортежем, а сами элементы – компонентами кортежа. Кортеж, состоящий из двух компонентов < x1, x2 >, называется парой, < x1, x2, x3 > – тройкой, < x1, x2, …, xn > – n-кой. Графиком называется множество пар. Пара < c, d > называется инверсией пары < a, в >, если с = в и d = a. График P -1 называется инверсией графика Р, если его элементы являются инверсией соответствующих пар графика Р. Если Р = {< a, в >, < c, d >}, то P –1 = {< в, а >, < d, c >}. Композицией графиков P и Q называется такой график -9- Теория множеств R = P o Q, что < x, y > ∈ R тогда и только тогда, когда есть такой элемент z, что < x, z > ∈ P, < z, y > ∈ Q. Диагональный график – график вида ∆ м = {< x, x >, < y, y >, …} для всех x, y, … ∈ М. График называется функциональным, если он не содержит пар с одинаковыми первыми и различными вторыми компонентами. График называется инъективным, если он не содержит пар с одинаковыми вторыми и различными первыми компонентами. Декартовым произведением множеств А и В называется множество А × В = {< a, в >| а ∈ А, в ∈ В }. Декартово произведение множеств А1, …, Аn А1 × А2 × …× Аn = { < a1, a2, …,an >| a1 ∈ А1, a2 ∈ А2, …, an ∈ Аn}. Соответствием называется упорядоченная тройка множеств < P, X,Y > такая, что P ⊆ X × Y, где множество Х называется областью отправления, множество Y – областью прибытия. Свойства соответствий. 1. Соответствие называется функциональным (функцией), если его график функционален. 2. Соответствие называется инъективным, если его график инъективен. 3. Соответствие называется всюду определенным, если проекция его графика на первую ось совпадает с областью отправления. 4. Соответствие называется сюръективным, если проекция его графика на вторую ось совпадает с областью прибытия. 5. Соответствие называется биективным (взаимно-однозначным), если оно функционально, инъективно, всюду определено и сюръективно. Отношением называется пара вида φ = < Ф, М > такая, что ϕ ⊆ М 2, где Ф – график, а М – то множество, между элементами которого существует данное отношение ϕ. Отношение называется полным, если Ф = М2. Отношение называется отношением равенства, если Ф = ∆М. Отношение называется отношением неравенства, если Ф = М2 \ ∆М. Если < x, y > ∈ Ф из ϕ, то отношение между элементами записывается x ϕ y. Операции над отношениями. Пусть ϕ = < Ф, М >, r = < R, M >, то ϕIr = < ФIR, M >, ϕ U r = <Ф U R,M >, ϕ =< M 2 \ Ф, М >, ϕ \ r =< Ф \ R, M >, ϕ −1 =< Ф −1, М >, ϕ o r =< Ф o R, M >. Основные свойства отношений. 1. Рефлексивность. Для всех х справедливо х ϕ х, или ∆М ⊆ Ф.

© 2005-2017 ФГАУ ГНИИ ИТТ "Информика"

Главная | Каталог | Избранное | Порталы | Библиотеки ВУЗов | Отзывы | Новости | | Рекламодателям | Контакты | Карта сайта


Источник: http://window.edu.ru/catalog/pdf2txt/660/47660/23618



Рекомендуем посмотреть ещё:


Закрыть ... [X]

Опухла верхняя губа у ребенка - причины, что делать? Отношение объемов двух цилиндров

Как называется отношение между индивидами Как называется отношение между индивидами Как называется отношение между индивидами Как называется отношение между индивидами Как называется отношение между индивидами Как называется отношение между индивидами Как называется отношение между индивидами Как называется отношение между индивидами