Декартово произведение множеств

 

Пусть A₁, A_2, …, A_n  - некоторые множества. Их декартовым произведением называют множество, состоящее из кортежей вида <α₁, α_{2, …}α_n>,

где α₁ A₁; α₂ A₂; … α_n A_n. Декартово произведение обозначается так:

A₁хA₂х …хA_n.

Произведение  

сокращенно обозначается как Aⁿ и называется декартовой n – й степенью множества A.

Пример 5. Пусть А = {1, 2, 3}, B = {x, y}. Выписать все элементы декартова произведения AxB и BxA.

Решение.                      

                        

Допускается запись

  

 

 

Работу составила преподаватель                     Т.С. Пронина

 

 

Практическое занятие № 11

1 Наименование работы: Диаграммы Эйлера-Венна.

2 Цель работы: Научиться строить диаграммы Эйлера-Венна и решать задачи с применением диаграмм Эйлера-Венна.

Формирование ОК 2- 5; овладение знаниями и умениями, необходимыми для освоения ПК 1.2. (спец. 09.02.03.), ПК 1.2, 2.4. (спец. 09.02.04.).

3 Подготовка к занятию: Повторите тему: Диаграммы Эйлера-Венна.

4 Литература:

4.1 Конспект лекций по учебной дисциплине «Элементы математической логики», 2016

4.2 Приложение к ПЗ №11.

5 Перечень необходимого оборудования и материалов:

5.1 Бланк для отчета.

5.2 Канцелярские принадлежности.

6 Задание на занятие:

Основная часть

6.1 Каждый из 63 студентов первого курса, изучающих информатику в университете, может посещать и дополнительные лекции. Если 16 из них слушают еще курс бухгалтерии, 37 – курс коммерческой деятельности, и 5 изучают обе эти дисциплины, то сколько студентов вообще не посещают упомянутых дополнительных занятий?

6.2 Студенты первого курса, изучающие информатику в университете, могут посещать и дополнительные дисциплины. В этом году 25 из них предпочли изучать бухгалтерию, 27 выбрали бизнес, а 12 решили заниматься туризмом. Кроме того, было 20 студентов, слушающих курс бухгалтерии и бизнеса, 5 изучали бухгалтерию и туризм, а трое – туризм и бизнес. Известно, что никто из студентов не отважился посещать сразу 3 дополнительных курса. Сколько студентов посещали по крайней мере 1 дополнительный курс? Сколько из них были увлечены только туризмом?

6.3 Постройте диаграммы Эйлера-Венна по следующим операциям:

а)(AÈB)\A

б) (AÇB) \B

в) (A\B) Ç (AÇB)

 

г) (A\B) Ç A

д)

е)

Вариативная часть

6.4 Воспользовавшись диаграммами Эйлера-Венна, определите, какие из следующих высказываний логически истинны:

а)

б)

в)

6.5 Постройте диаграммы Эйлера-Венна по следующим операциям:

а) ((AÈB) Ç (AÈC)) \ (BÈC)

б) (AÈB)\(C\A)

в) AÇ(B\C)

7 Порядок выполнения работы:

Выполните практическую работу в соответствии с заданиями (основная часть 6.1 – 6.3) и сдайте зачет. В случае получения зачета, выполните вариативную часть (6.4-6.5).

8 Содержание отчета:

Решения задач в соответствии с заданием.

9 Контрольные вопросы:

1 Для чего могут использоваться диаграммы Эйлера-Венна?

2 Опишите краткий алгоритм решения задач на доказательство с помощью диаграмм Эйлера-Венна.

3 Как с помощью диаграмм Эйлера-Венна изобразить логические операции конъюнкцию, дизъюнкцию, отрицание, сумму по модулю два, эквиваленцию, штрих Шеффера, импликацию, стрелку Пирса?

4 Изобразите с помощью диаграмм Эйлера-Венна основные операции над множествами: АÈВ, АÇВ, А\В, В\А, АDВ.

 

      

       Приложение к практическому занятию по ЭМЛ № 11

Диаграммы Эйлера-Венна – удобный инструмент, позволяющий изображать множества и иллюстрировать операции над ними.

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

Диаграммы Эйлера-Венна также могут использоваться для решения задач, связанных с пересеченными множествами.

При этом для двухпеременных пересеченных множеств используется формула:

|АÈВ| = |А| +|В| - |АÇВ|,

где |А|  - число элементов множества А;

   |В| - число элементов множества В;

   |АÇВ| - число элементов, входящих одновременно и в множество А, и в множество В.

Для трехпеременных пересеченных множеств используется формула:

|АÈВÈС|= |А|+ |В|+ |С| - |АÇВ| - |АÇС| - |ВÇС| + |АÇВÇС|.

 

Пример 1. Предположим, что из 100 опрошенных студентов 50 изучают химию, 53 – математику, 42 – физику, 15 – химию и физику, 20 занимаются физикой и математикой, 25 – математикой и химией и 5 студентов изучают все 3 предмета.

а) Сколько студентов изучают хотя бы один из 3 перечисленных предметов?

б) Сколько студентов не изучают ни один из 3 перечисленных предметов?

в) Сколько студентов изучают только математику?

г) Сколько студентов изучают физику или химию, но не изучают математику?

д) Сколько студентов не изучают ни математику, ни химию?

Поскольку 5 человек изучают все 3 предмета, а 15 человек – химию и физику, остаются 10 человек, изучающих химию и физику, но не изучающих математику. Аналогично, 25-5=20 человек занимаются математикой и химией, но не физикой, и 20-5=15 человек изучают математику и физику, но не изучают химию. Данную ситуацию изображает диаграмма Венна, приведенная на рис.1.

                                                   рис.1

Поскольку 50 студентов изучают химию, и 35 из них уже учтены, то оставшиеся 15 изучают только химию. Аналогично, 53 студента занимаются математикой, и 40 из них уже учтены, поэтому 13 человек изучают только математику. Наконец, 42 студента изучают физику, и 30 из них уже учтены, поэтому 12 человек изучают только физику.

а) Суммируя количество людей, принадлежащих семи непересекающимся подмножествам, получаем 90 тех, кто изучает хотя бы один из трех предметов.

б) Поскольку 90 из 100 студентов изучают хотя бы один предмет, то 100-90=10 человек не изучают ни один из этих 3 предметов.

в) Из диаграммы Венна следует, что 13 человек изучают только математику.

г) 37 студентов занимаются химией или физикой, но не изучают математику.

д) Из диаграммы Венна, изображенной на рис.2, следует, что 75 человек изучают математику или физику. Поэтому 100-75= 25 студентов не изучают ни математику, ни физику. 

                                                    рис.2

 

Пример 2. Изобразим с помощью диаграмм Эйлера-Венна множество

(А\В)È(В\А).

Это множество является объединением двух разностей, называется симметрической разностью и обозначается АDВ, т.е. (А\В)È(В\А)= АDВ (рис.3).

 рис.3

 

Пример 3. Докажите, пользуясь диаграммой Эйлера-Венна, что высказывание - логически истинно.

Решение. Этому высказыванию соответствует множество , отвечающая ему диаграмма изображена на рис.4.

рис.4

 

Множество А заштриховано вертикальными линиями, а множество  горизонтальными. Вся заштрихованная область является их объединением и совпадает с множеством U, так что составное высказывание логически истинно.

 

Пример 4. Докажите, пользуясь диаграммой Эйлера-Венна, что XÚ(YÙZ) эквивалентно (XÚY)Ù(XÚZ).

Решение. Множество истинности высказывания XÚ(YÙZ) совпадает со всей заштрихованной областью на диаграмме слева, а множество истинности высказывания (XÚY)Ù(XÚZ) совпадает с дважды заштрихованной областью на диаграмме справа (рис.5).

 

                                                        рис.5

 

 

Работу составила преподаватель                       Т.С. Пронина.    

                                   Практическое занятие №12

1 Наименование работы: Решение задач теории множеств на доказательство.

2 Цель работы: Научиться решать задачи на доказательство с применением диаграмм Эйлера-Венна, формул алгебры множеств и алгебры логики.

Формирование ОК 2- 5, 9; овладение знаниями и умениями, необходимыми для освоения ПК 1.2. (спец. 09.02.03.), ПК 2.4. (спец. 09.02.04.).

3 Подготовка к занятию: Повторите темы: Основные понятия теории множеств. Законы алгебры логики.

4 Литература:

4.1 Конспект лекций по учебной дисциплине «Элементы математической логики», 2016

4.2 Приложение к ПЗ №12.

5 Перечень необходимого оборудования и материалов:

5.1 Бланк для отчета.

5.2 Канцелярские принадлежности.

6 Задание на занятие:

Основная часть

6.1 Докажите тождество:

ÈВ = ÈВ

 

6.2 Докажите с помощью диаграмм Эйлера-Венна следующие выражения:

а) А È (В\С) É (АÈВ)\С

б) (АÈС)\В Ì (А\В) ÈС

 

6.3 Определите с помощью диаграмм Эйлера-Венна тождественную истинность (ложность) логических операций.

а)

б)

 

6.4 Докажите, что, если АÌВ; В ÌА, то А=В.

 

6.5 Заданы множества А= {x: x²  -1£ 0} и В= {x: |x|< 1}. Определите АÇВ; АÈВ; А/В, В/А. Графически представьте эти множества.

 

Вариативная часть

6.6 Докажите равенства:

а) (А\В)ÇС = (АÇС)\(ВÇС)

б) (А\В) \С = А\ (ВÈС)

 

6.7 Пусть А= {xÎN: 2< x £6}, B={xÎN: 1< x<4}, C= {xÎN: x²-4=0}

Из каких элементов состоят множества:

а) ВÈС;

б) АÇВÇС;

в) АÈВÈС;

г) В´С;

д) С´В?

 

6.8 Пусть AÌU, BÌU. Найдите множество, удовлетворяющее уравнению = B.

7 Порядок выполнения работы:

Выполните практическую работу в соответствии с заданием (основная часть 6.1 – 6.5) и сдайте зачет. В случае получения зачета, выполните вариативную часть (6.6 – 6.8).

8 Содержание отчета:

Решения задач в соответствии с заданием.

9 Контрольные вопросы:

1 Определите, каким операциям над множествами соответствуют следующие логические операции: отрицание, конъюнкция, дизъюнкция, импликация?

2 Как используются диаграммы Эйлера-Венна в решении задач на доказательство?

3 Перечислите законы алгебры множеств для пересечения, объединения, разности множеств и проведите аналогию с законами алгебры логики.

 

Приложение к практическому занятию по ЭМЛ № 12

Законы алгебры множеств

Законы объединения и пересечения:

1. АÈА = А

2. АÇА = А

3. АÈВ = ВÈА

4. АÇВ = ВÇА

5. АÈ(ВÈС) = (АÈВ) ÈС

6. АÇ(ВÇС) = (АÇВ) ÇС

7. АÇ(ВÈС) = (АÇВ) È (АÇС)

8. АÈ(ВÇС) = (АÈВ) Ç (АÈС)

9. AÈU= U

10. AÇÆ = Æ

11. AÇU= A

12. AÈÆ = A

 

Законы для дополнений

1. = A

2.AÈ = U

3.AÇ = Æ

 

4.

5.

6. = Æ

Законы для разностей множеств:

1. А\В=

2. U\A=

3. A\U= Æ

4. A\Æ= A

5. Æ\A= Æ     

6. A\A= Æ

7.((A\B)\C)= A\(BÈC)

8.A\(B\C)= (A\B) È(AÇC)

9.AÈ(B\C)= (AÈB)\(C\A)

10. AÇ(B\C)= (AÇB)\(AÇC)

 

Пример 1. Доказать, что .

Пусть xÎ . По определению операции дополнения это означает, что xÏAÈB, но xÎU. Следовательно, xÏA и одновременно xÏВ. Таким образом, xÎ  и xÎ . Из определения операции пересечения получаем, что xÎ Ç . Поэтому, учитывая произвольность элемента xÎ , имеем Ì .

Пусть теперь xÎ Ç . Это значит, что xÎ  и xÎ . Таким образом, xÏA и xÏВ. Поэтому xÏAÈB. Следовательно, xÎU\(AÈB)= . Поскольку х - произвольный элемент из , то окончательно получаем Ì .

Приходим к выводу, что = .

Пример 2. Доказать с помощью диаграмм Эйлера – Венна, что А\В = .

На рисунке 1 (а) изображена диаграмма А\В. На рисунке 1 (б) штриховкой вправо изображено множество А, штриховкой влево – множество `В, а двойной штриховкой .

 

          

            А\В                                                                 

 

                                         

       рис.1 (а)                                                  рис.1 (б)         

При сравнении рис. 1 (а) и 1 (б) видно, что разность А\В, показанная на

рис. 1(а) штриховкой влево, равна пересечению , изображеному на рис. 1(б), двойной штриховкой.

Пример 3. Доказать с помощью диаграмм Эйлера – Венна, что  =

Построение  поэтапно показано на рисунке 2 (а) и 2 (б).

               

           АÈВ                                                        

                        

          рис.2 (а)                                                       рис.2 (б)

 

Построение  поэтапно показано на рисунке 3.

3 (а) - ;

3 (б) - ;

3 (в) -

 

                                                                                                      

                            

         рис.3 (а)                                                              рис.3 (б)

 

                   

          

рис.3 (в)

Из анализа видно, что  =

 

Пример 4. Доказать равенство: А\(А\В)= АÇВ

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

В нашем случае А\В= АÇ . Преобразуем левую часть

А\(А\В)= А\(АÇ )= АÇ()= АÇ() = = = АÇВ.

Докажем это же равенство с помощью диаграмм Эйлера-Венна (рис.4 и рис.5).

 

         

                 рис.4                                                              рис.5