Упражнения на графы. Лекции по ДИСМАТ _ Часть 1-теори множеств. Лекции Дискретная математика

• Название: Лекции Дискретная математика
• Анкор: Упражнения на графы
• Дата: 15.06.2021
• Размер: 1.02 Mb.
• Имя файла: Лекции по ДИСМАТ _ Часть 1-теори множеств.doc
• Тип: Лекции; #217395
• страница: 2 из 4

I. элемент множества, соответствующего левой части заданного равенства, является также элементом множества, соответствующего правой его части.

II. элемент множества, соответствующего правой части равенства, является элементом и множества, соответствующего его левой части.

Пример: A (B C) = (A B) (A C)

I. Пусть x A (B C) => /тогда, по определению операции объединения/ => x хотя бы одному из двух множеств A и В С =>

а). Если х А => x A B и x A C => x (A B) (A C).

b). Если же х В С => x B и х С => x B A и x C A => /по определению операции пересечения/ => x (B A) (C A).

В любом случае, как видно, из x A (B C) => x (A B) (A C). Это означает, что А (B C) (A B) (A C).
II. Пусть x (A B) (A C) => /по определению операции пересечения/ => x A B и x A C => x A или x B и, в то же время, x A или x C => (одновременно в обеих случаях)

Либо а). x A , либо b). x A

а). Если х А => x A D, где D - множество и в частности D=B C => x A (B C).

b). Если же х А, то (одновременно) х B и x C => x B C => x (B C) E, где Е - множество, в том числе Е=А . Таким образом, если х (А В) (А С) => х А (В С).

Как видно, в любом случае (x A или x A) при x (A B) (A C) имеем х А (В С), тем самым показано, что (А В) (А С) А (В С).

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

Подобным образом доказываются все равенства и тождества со множествами.
8. Решение уравнения со множествами

Кроме тождеств, которые верны при любых значениях входящих в нее множеств U алгебра множеств рассматривает уравнения, которые содержат фиксированные подмножества (А₁, А₂, А₃, .... или А, В, С, ...) и подлежащие определению неизвестные подмножества Х₁, Х₂, Х₃ ... .

В простейшем случае в уравнение входит одно подмножество X. При этом требуется во первых найти условия, при которых уравнение имеет решение и во вторых - найти все такие решение, когда эти условия будут выполняться, то есть определить Х. Решение уравнения с одним неизвестным подмножеством Х основывается на последовательном выполнении следующих тождественных преобразований:

1. 
   Равенство преобразовывается в дизъюнктивную сумму его левой и правой частей, которая приравнивается затем .
   
2. 
   Полученное уравнение преобразуется к виду (М Х) (N ) R= ,
   

где R,M, N – некоторые множества (или выражения, определяемые через заданные постоянные множества) не содержащие Х .

(Любое уравнение с одним неизвестным и правой частью = приводится к такому виду).

3. 
   Объединение множеств = тогда и только тогда, когда любое из множеств, входящих в объединение = . Потому полученное уравнение распадается на систему уравнений типа:
   

R= ,

М Х= ,

N = .

4. 
   Эта система уравнений имеет смысл тогда и только тогда, когда R= , Х и Х N.
   

Следовательно, условием существования решения будет R= , и N .

Из этих соотношений устанавливаются ограничения на заданные постоянные множества в уравнении, выполнение которых необходимо для существования решения.

Решением же уравнения будет множество Х , удовлетворяющее соотношению N X .