Для любых конечных множеств AA, BB и CC справедливо равенство:
|A∪B∪C|=|A|+|B|+|C|−|A∩B|−|A∩C|−|B∩C|+|A∩B∩C|.|A∪B∪C|=|A|+|B|+|C|−|A∩B|−|A∩C|−|B∩C|+|A∩B∩C|.
Поясним кратко, откуда берутся слагаемые справа. Назовём двукратными элементы, входящие в пересечение ровно двух множеств, и трёхкратными — элементы, входящие в пересечение трёх множеств. Сложив мощности AA, BB и CC, мы дважды учли каждый двукратный элемент и трижды — каждый трёхкратный. Вычтя три попарных пересечения, мы «восстановили справедливость» в отношении двукратных элементов, но при этом трижды вычли трехкратные элементы, которые теперь оказались полностью неучтёнными. Поэтому надо добавить мощность тройного пересечения.
Разберем примеры решений типовых задач с этой формулой включений и исключений для случая 2 и 3 множеств (другие примеры подобных заданий вы найдете в разделе Примеры по дискретной математике: Множества и отношения).
Задача 1. Формула включений и исключений (для трех множеств). Известно, что свойством А обладает n объектов, В — m объектов, С — с объектов, АВ — р объектов, АС — g объектов, ВС — r объектов, АВС — q объектов. Сколько всего объектов?
Решение: формула включений-исключений для 3 множеств
Задача 2. Из 100 человек студентов, сдавших сессию, 48 человек сдали экономику, 42 студента – математику и 37 человек – логику. По экономике или математике сдали экзамен 76 человек, по экономике или логике также 76 человек, а по математике или логике – 66 человек. Сколько человек сдали хотя бы один экзамен, если все три предмета сдали 5 человек? Сколько человек не сдали ни одного экзамена?
Сколько человек сдали только один экзамен по логике?
Решение о сдаче экзамена
Задача 3. При обследовании читательских вкусов студентов оказалось, что 60 % студентов читают журнал А, 50 % - журнал В, 50 % - журнал С, 30 % - журналы А и В, 20 % - журналы В и С, 40 % - журналы А и С, 10 % - журналы А, В и С. Выяснить, сколько процентов студентов:
1) не читает ни одного из журналов;
2) читает в точности два журнала;
3) читает не менее двух журналов.
Решение о чтении журналов
Задача 4. На одной из кафедр университета работают 13 человек, причем каждый из них знает хотя бы один иностранный язык. Десять человек знают английский, семеро - немецкий, шестеро - французский, пятеро знают английский и немецкий, четверо - английский и французский, трое - немецкий и французский. Выяснить:
1) сколько человек знают все три языка;
2) сколько человек знают ровно два языка;
3) сколько человек знают только английский язык.
Решение о знаниях языка по формуле включений и исключений
Задача 5. Из 100 туристов, выехавших в заграничное путешествие, 10 человек не знают ни немецкого, ни французского языков, 76 человек знают немецкий и 83 – французский. Сколько туристов знают оба эти языка?
Решение по формуле включений-исключений для 2 множеств
Задача 6. В отряде из 40 ребят 30 умеют плавать; 27 умеют играть в шахматы; 5 не умеют ни плавать, ни играть в шахматы. Определить количество ребят, умеющих плавать и играть в шахматы.
|
