2.3Диаграммы Венна. Формула включений-исключений.
Удобный способ наглядного изображения формул алгебры множеств и исчисления высказываний доставляют так называемые диаграммы Венна. Множества будем представлять себе как внутренности областей на плоскости, ограниченных замкнутыми контурами (например, окружностями). Рассмотрим, например, три множества А, В и С.
На первом рисунке выделено множество А. Если обозначить предикат хÎА за р, предикат уÎB за q и предикат zÎC за r, то первому рисунку соответствует область истинности предиката р.
На третьем рисунке отмечена область ВÈС и соответствует оно истинному значению дизъюнкции qÚr. На четвёртом рисунке закрашена область АÇВÇС и соответствует оно значению Т конъюнкции pÙqÙr.
Упражнение 4.
a) Каким множествам и истинным значениям каких предикатов соответствуют закрашенные области на втором и пятом рисунках?
b) Нарисуйте диаграммы Венна для множеств В\А, АDВ, AсÇBÇC.
c) Нарисуйте диаграммы Венна соответствующего истинному значению для предиката pÙØqÙrÚpÙqÙØrÚØpÙqÙr.
Е
сли
мы имеем конечные множества А и В, то
можно выразить число элементов АÈВ
через числа элементов в А, в В, и в АÇВ.
Обозначим число элементов в А через
½А½.
Если мы рассмотри сумму ½А½+½В½,
то увидим, что мы посчитали зелёные и
оранжевые элементы по одному разу, а
жёлтые – дважды (см. рис. 6). В объединение
же ½АÈВ½
все эти элементы входят по одному разу.
Поэтому имеет место формула
включения-исключения для двух множеств:
½А½+½В½=½АÈВ½+½АÇВ½.
Упражнение 5.
Каждый ученик класса изучает английский или испанский. Английский изучают 25 человек, а испанский – 27. 18 человек изучают оба языка. Сколько человек учится в классе?
В Тбилиси 85% жителей говорят по-грузински, а 75% - по-русски. Сколько %% жителей говорят на обоих языках?
50% учеников играют в баскетбол, 40% - в теннис, 10% - в обе игры. Какая часть класса не играет ни в баскетбол, ни в теннис?
Упражнение 6.
Выведите формулу включения-исключения для трёх множеств: ½АÈВÈС½= В правой части должны участвовать величины ½А½,½В½,½С½, ½АÇВ½,½АÇС½,½СÇВ½ и ½АÇВÇС½.
*Попробуйте выдвинуть гипотезу о том, как будет выглядеть эта формула для n множеств. Для доказательства своей гипотезы естественно воспользоваться методом математической индукции.
В международной конференции участвовало 95 человек из трёх стран – Германии, России и США. Из них 60 могли говорить по-русски, 48 –по-английски, 32 - по-немецки, 21 – по-русски и по-английски, 19- по-английски и по-немецки, 15- по-немецки и по-русски. Сколько участников конференции владеют только одним из этих языков? Сколько участников конференции владеют тремя языками?
*Из 100 человек каждый владеет, по крайней мере, одним языком, никто не владеет ровно двумя языками, но некоторые владеют тремя. Известно, что 85 человек знают английский, 80 – испанский, 75 – немецкий. Сколько человек знают 3 языка?
В деревне 60 семей держат коров, столько же семей держат овец, и 70 семей держат свиней. При этом 20 семей держат коров и свиней, 14 – коров и овец и 28 – овец и свиней. При этом в деревне живёт 136 семей, и каждая семья держит либо коров, либо свиней, либо овец. Сколько семей в деревне держит всех трёх животных? Сколько ровно двух? Сколько только одно животное?