1_2 СРСП_Множества. Дискретная математика

• Название: Дискретная математика
• Дата: 06.04.2023
• Размер: 0.61 Mb.
• Имя файла: 1_2 СРСП_Множества.doc
• Тип: Документы; #1041502
• страница: 1 из 3

Дискретная математика

Предлагаемый курс дискретной математики знакомит ссовременными средствами моделирования – универсальными моделями и методами формализованного описания. В процессе моделирования этот класс методов занимает одно из ключевых мест. Отметим два важных обстоятельства, касающихся моделирования как процесса.

Процесс моделирования заключается в уточнении исследуемой ситуации, процесса при использовании каких-либо средств фиксации имеющихся и выявленных знаний в виде модели как результата такой формализации.

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

• 
  Универсальные средства формализованного представления;
  
• 
  Способы корректной переработки информации, представленной на этих языках;
  
• 
  Возможности и условия перехода с одного языка описания явлений на другой с сохранением содержательной ценности моделей.
  

Задачей курса и является и освоение основных моделей и методов формализованного представления: теоретико-множественных, логических, графических. Теория множеств, логика, теория графов являются фундаментом дискретной математики. Теоретико-множественные, логические и графические представления, относящиеся к этим разделам дискретной математики.


1 СРСП






















2 СРСП

Диаграмма Венна

Диаграмма Венна – геометрические представления множеств. Построение диаграммы заключается в изображении большого прямоугольника, представляющего универсальное множество U, а внутри его – кругов представляющих множества. Фигуры должны пересекаться в наиболее общем случае требуемом в задаче и должны быть соответствующим образом обозначены. Точки, лежащие внутри различных областей диаграммы могут рассматриваться как элементы соответствующих множеств. Имея построенную диаграмму. Можно заштриховать определенные области для обозначения вновь образованных множеств.

Пример 1.

Представить множество А (В С) диаграммой Венна.

Начнем с общей диаграммы, показанной на рис.

Заштрихуем В диагональными линиями в одном направлении, а С в другом. Площадь с двойной штриховкой представляет собой их пересечение, т.е. множество В С. Выделим это множество жирной линией. На новой копии диаграммы заштрихуем эту область В С линиями одного направления, а А – другого. Вся заштрихованная .
Упражнения

1. В примере 2 проиллюстрировано свойство дистрибутив­ности слева операции пересечения относительно операции объединения и. Подтвердить справедливость свойства дист­рибутивности справа пересечения относительно объедине­ния , а также слева и справа и относительно п, т.е.:

а) (А В) С=(А С) (В С)- справа относитель­но ;

б) А (В С)=(А В) (А В) -слева относительно ;

в) (А В) C=( А С) (В С)- справа относитель­но .

2. 
   Построить диаграммы Венна, иллюстрирующие мно­жества а) - л) из упражнения 7 в § 1.2.
   
3. 
   Построить диаграммы Венна, иллюстрирующие мно­жества а) - з) из упражнения 8 в § 1.2. Отметить точками внутри соответствующих областей диаграмм элементы ис­ходных множеств U, А, В, С.
   
4. 
   Пусть ЛД С с: U. Проиллюстрировать на примере кон­кретных множеств и с помощью диаграмм Венна справед­ливость следующих соотношений:
   

а) А (В С) = (А В) С; д) А (А В) = А;
6) A (B C) = (А В) С; е )А (А В)=А;_
в) А В = А В;ж) (А В) (A В )=- А;

г)А В=А В;з)А (А В)=А В.

Доказательства

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

Ниже в примерах 1-5 проиллюстрированы наиболее час­то используемые в теории множеств приемы доказательств:

• 
  доказательство равенства - соотношений типа Х= Y;
  
• 
  доказательство единственности существования;
  
• 
  доказательство от противного.
  

В примерах 1, 2 доказательства соотношений типа X= Y, где Xи Y - множества, основаны на использовании определений I и II равенства двух множеств.

В соответствии с определением I для равенства двух мно­жеств требуется совпадение их элементов. Поэтому сначала доказывается, что для произвольного элемента а из того, что а Х, следует, что a Y, затем доказывается, что если а X, то а Y. Таким образом, элементы множествами Гсовпада-ют и, следовательно, по определению I, Х= Y.

В соответствии с определением UX= Y, если х у и Y X. Поэтому для доказательства равенства двух множеств тре­буется показать справедливость включений х у и Y X.

В примере 3 для доказательства единственности суще­ствования теоретико-множественного объекта Xиспользо­ван основной математический подход, в соответствии с ко­торым сначала предполагается, что существуют два таких объекта X' и X", а затем доказывается, что они совпадают: Х'=Х", т.е. Х'=Х"=Х.

На последовательности примеров 1-4 показано, как мож­но выводить сравнительно сложные утверждения путем пос­ледовательности доказательств простых утверждений.

Пример 5 иллюстрирует косвенный метод доказательства - доказательство от противного. Для доказательства ис­тинности некоторого утверждения Qпри исходных услови­ях Р предполагается, что Qпри этих условиях ложно; далее показывается, что в таком случае имеют место противоре­чия. Следовательно, принятое предположение ложно, т.е. утверждение Q- истинно *.

Пример 1. Доказать справедливость соотношения

А (В С)=(А В) (А В)

(свойство дистрибутивности слева объединения относительно пересечения .

• 
  Такое доказательство может быть выполнено с помощью диаграмм Венна. Здесь для этих целей используем один из примеров доказательства равенства двух множеств.
  

В соответствии с определением 1 равенства множеств равны, т.е. Х=У, если их элементы совпадают. Это означает, что Х=У, если их элементы совпадают. Это означает, что Х=У, если из того, что a Х, следует a У, и из того, что а X, то а Y.

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

1. 
   a А (В С).
   

Из определения операции объединения следует, что элемент а принадлежит хотя бы одному из них. Таким образом, a А или a (В С), при этом возможны следующие случаи:

1.1. а принадлежит множеству А и а не принадлежит пересечению множеств

В С ;

a А и a (В С).

Последлежит множеству А и а не принадлежит пересечению множеств В или С, или им обоим, т.е.;

1. 
   a А, а В, а С;
   
2. 
   a А, а В, а С;
   
3. 
   a А, а В, а С;
   
1. 
   а А и а ( В С), т.е. а А, а В, а С.
   
2. 
   а А и а ( ВС), т.е. а А, а В, а С.
   

Рассмотрим каждый из этих случаев.

1. 
   Так как а А, то а принадлежит объединению множества А с любым множеством, в том числе а (А В) и а (А С).
   
2. 
   Так как а В, а С, то а (А В) и а (А С), следовательно,
   

а (А В) (А С).

3. 
   Так как а А , то этого достаточно, чтобы а (А В) и а (А С), следовательно, а (А В) (А С).
   

Таким образом, а любом из рассмотренных случаев из того, что а А (В С), следует что а (А В) (А С).

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

2. 
   а А ( В С). Элемент а не принадлежит объединению двух множеств, если он не принадлежит ни одному из них. Тогда а А и . а ( В С), т.е. возможны следующие случаи:
   

2.1. а А, а В, а С;

2.2. а А, а В, а С;

2.3. а А, а В, а С;

Рассмотрим каждый из этих случаев:

1. 
   Так как а А, а В, то а (А В), следовательно,
   

а (А В) (А С).

2. 
   Так как а А, а С, то а (А С), то этого достаточно, чтобы а (А С), следовательно а (А В) (А С).
   
3. 
   Так как а А, а В, то этого достаточно, чтобы а (А В) и следовательно, а (А В) (А С).
   

Как видим, в любом из этих случаев из того, что а А (В С), следует что а (А В) (А С).
Пример 2. Доказать справедливость соотношения

(А В) С=(А С) (А С). (свойства дистрибутивности справа пересечения относи­тельно объединения ).

• 
  Множества X = Y, если X Yи Y X. Поэтому пока­жем сначала, что (А и В) С (А С) (В С), т.е. любой произвольный элемент а из множества, заданного левой ча­стью соотношения, принадлежит и множеству, заданному правой частью соотношения.
  

Пусть а (А В) С. Тогда а (А В)и а С =>

=> (а А или а В) и (а С)=>

=>(а А и а С) или (а Виа С) =>

=>а (А С)или а (В С) =>

=>а (А С) (В С)
Таким образом, (А В) С (А С) (В С).
Покажем теперь, что (А С) (В С) (А В) С . т.е. любой элемент а из множества, заданного правой частью ис­ходного соотношения, принадлежит и множеству, заданно­му левой частью исходного соотношения.

Пусть a (A С) (B С). Тогда а (А С) или а (В С) =>

=>(а Аиа С) или (а Ви а е С)=>

=>(а А или а В) и а С=>

=>а (А В) а С=> а (А В) С

Следовательно, (А С) (В С) а (А В) С

Таким образом, (А В) С = (А С) (В С) что и требовалось доказать.

Пример 3*. Доказать, что относительно данного универ­сального множества Uдополнение любого множества А , если А U, единственно.

• 
  Для доказательства единственности дополнения А множества ,4 с Uпредположим, что существуют два множе­ства В и С в U, каждое из которых удовлетворяет требовани­ям дополнения множества А, т.е. их пересечение с А пусто, а объединение с А дает U:
  

а)В А = Ø;6)С А = Ø;

b)BuA = U;t)C A = U.

Очевидно, что B=B U.Cучетом условия г) В=В (С А).

Тогда по доказанному выше (см. пример 2, § 1.3)

В=(В С) (В А), но с учетом условия

а) В = (В С) А = В С, т.е. В = В С. Поэтому

а В=> а В и а С=> В (В С)=>. В В и В С.
Очевидно, что B B, отсюда следует, что B C.

В то же время (с учетом условий в), б), а также в соответ­ствии с доказанным выше примером 2 § 1.3):

С = С U = С (В А) = (С В) и (С А) (С В) (С В) Ø = С В.

Поэтому

а С => а С и а В =>С (С В) => С С и С В.

Отсюда следует, что С В.

Таким образом, откуда 5 = С. Следователь­но, В = С = А и Л - единственно, что и требовалось В С и С В, откуда В=С. Следовательно, В=С=А и А – единственно, что и требовалось дока­зать.