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

I l l Доказательство. Чтобы получить число элементов, не обладающих ни одним из указанных свойств, необходимо из и - множества исключить подмножество элементов, обладающих свойством р/, затем обладающих свойством р2 и т.д., т.е. 27 n(pi) элементов. Однако при этом элементы, имеющие два свойства, с к ажем v i p 2 , оказались исключёнными дважды как обладающие свойством pi, затем как обладающие свойством р^. Значит, надо возвратить все множества, элементы которых обладают двумя свойствами, т.е. прибавить 27 п{р(, pj) элементов. Но при этом элементы, обладающие тремя свойствами, скажем, pi, p j и рк , оказались включенными дважды, следовательно, надо вычесть Е п(ри pj, pij. Рассуждая далее аналогичным образом, получим алгоритм для вычисления п(pi, рг,-, р^, состоящий в попеременном отбрасывании и возвращении подмножеств. Этому и обязано название метода: метод включения и исключенш. Эту теорему можно доказать следующим образом. Пусть В - подмноясество (В^) элементов, не обладающих ни одним из свойств р,, Р2,•••, р„, яА-S\B. Следовательно, ВпЛ = 0 я S=AиВ. Тогда n(S) = п = п(В)_+ п(А), п(В) =п( P J , Р 2,..., P J ='П-П(А). Подмножество А состоит из элементов множества S, обладающих некоторыми (возможно, всеми) свойствами pj, рг,.... р„. Пусть Aj подмножество из А всех тех элементов, которые обладают свойством р/ (и может быть какими - то другими свойствами), А2 - подмножества ю А всех т е х элементов, которые обладают свойством р2 (и может быть какими - то другими свойствами) и т.д. Тогда имеем; А =А/ uA; u...uA^ следовательно, получим: п( P I , Рг,..., pJ = п- n(Ai иАз u...uA^ и по формуле (4,3) - требуемое равенство (4.7). Рассмотрим пример. Даны числа 1,2,...,100. Требуется выяснить, сколько среди них чисел, которые не делятся ни на одно из чисел 2,3,5. Положим; pi - свойство чисел делиться на 2; Р2 - свойство чисел делиться на 3; Рз - свойство чисел делиться на 5; P I Р2- будет означать, что число делится на 6; PI будет означать, что число делится на 10; РГ /'л - будет означать, что число делится на 15; Р! Р2Р3 - будет означать, что число делится на 30, Тогда легко получить, что: п( P I , Р 2. рз) = 100 - п(р,) - п(р:) ~ п(рз) + п(р,. рг) + П {ри рз) + П (р2. р^ - n(pi, Р2, Рз)~ 100 - 50 - 33 - 20 + 16 +10 + 6 - 3 = 26. Рассмотрим второй пример. При обследовании установили; 60% студентов читают журналы типа ^4,-