Формализованное описание системы как множества с отношением

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

Приведенный ниже текст получен путем автоматического извлечения из оригинального 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]

Выкройка для Анабель Видео на Запорожском портале Мастер класс по пальчиковым красками

Формализованное описание системы как множества с отношением Формализованное описание системы как множества с отношением Формализованное описание системы как множества с отношением Формализованное описание системы как множества с отношением Формализованное описание системы как множества с отношением Формализованное описание системы как множества с отношением Формализованное описание системы как множества с отношением Формализованное описание системы как множества с отношением Формализованное описание системы как множества с отношением