и по идее эту формулу надо аккуратно доказывать.
Я могу, конечно это сделать, и наверное я сейчас это проделаю всё-таки.
Просто для того, чтобы не оставалось у слушателей какого-то впечатления,
будто бы я что-то недоговариваю, будто здесь это как-то очень трудно.
Но смотрите, если при первом прослушивании этого курса вам покажется слишком занудным
и трудным доказательство этой теоремы- оно в принципе несложное, но немножко такое
требующее все-таки аккуратного восприятия, то вы не пугайтесь, это не страшно.
На самом деле суть-то интуитивно совершенно понятна.
И этой сути вполне достаточно для того, чтобы решать конкретные задачи.
После того, как я произнесу занудную речь с доказательством, ну я уж постараюсь его
там расцветить всеми возможными способами, но оно все-таки будет немножко занудное,
вот после того как я воспроизведу доказательство этой формулы,
я приведу обязательно пару примеров задач, которые с помощью этой формулы очень
красиво решаются, прокомментирую их, и я думаю, что это будет как раз то, что нам
нужно в рамках этой лекции, когда мы действительно как следует с вами осознаем
вот этот вот замечательный принцип, как работает формула включений-исключений.
Итак давайте сейчас перейдем все-таки к аккуратному доказательству, которое,
повторяю, при первом прослушивании можно чуть-чуть пропустить,
но можно и не пропускать, можно вникнуть.
А после доказательства обсудим примеры.
Так, ну давайте все-таки докажем эту теорему,
докажем формулу включений-исключений.
Тут есть один тонкий момент, который связан с тем, что
доказательство будет идти с помощью то что называется метода математической индукции.
Значит, конечно, если этот метод сам по себе
рассказывать в подробностях, это займет еще одну лекцию как минимум.
Но с одной стороны я надеюсь на то, что большинство слушателей так или иначе как
минимум слышало, что такой метод существует.
С другой стороны, я уже сказал, что в общем,
если вы это доказательство в курсе не осознаете- это не смертельно совершенно,
потому что я его привожу исключительно для полноты картины, чтобы слушателям не
показалось, что я их обманываю и давлю исключительно на интуицию.
Ну а в-третьих, идея-то очень простая.
Давайте я сейчас буду рассказывать, в чем состоит метод,
и идеологически я думаю что вы поймете на самом деле, как это устроено,
и действительно поверите в то, что этот принцип должен работать.
Итак, смотрите, давайте сперва докажем утверждения
для случая n маленькое, то есть количество свойств, равного единице.
Давайте во-первых рассмотрим ситуацию,
когда у нас есть только одно свойство, которое нас интересует.
Ну скажем, знание английского языка.
Понятно, что в этом случае все данные,
которыми мы располагаем- это лишь количество объектов в нашем множестве,
и это, конечно, количество объектов среди них,
которые обладают свойством альфа один у нас, n маленькое равняется единице,
никаких других свойств кроме альфа один нету, поэтому вот все наши данные.
N большое- это общее количество свойств.
N большое от альфа один это- извините, не свойств, а объектов,
конечно- это количество объектов, которые обладают ровно вот этим одним свойством.
И интересует нас по-прежнему количество объектов,
которые этим свойством не обладают.
N от альфа один штрих- это и есть та величина, которую мы изучаем в теореме.
Ну, здесь вроде совершенно понятно, что если мы хотим найти количество людей,
которые не знают английский среди всех людей, и при этом знаем, сколько из них
владеют английским языком, то действительно надо взять просто количество
всех людей, вычесть из них количество тех, кто владеет английским языком,
и мы получим товарищей, которые английского не знают.
То есть, это абсолютно очевидная штука.
С другой стороны,
вот эта абсолютно очевидная штука- это и есть частный случай формулировки теоремы.
Ну, когда n маленькое равняется единице,
никаких других вычитаемых и тем более добавляемых нету.
То есть, та формула, которая заявлена в утверждении теоремы,
она как раз вот к этому и сводится.
Упрощается до такого вот замечательного вида.
Иными словами, при n маленькое равном единице утверждение теоремы, вот оно,
является очевидным фактом, не требующим какого-то специального доказательства.
То есть мы знаем, что для n маленького равного единице это верно.
Ну, давайте даже так,
я прямо вот напишу: мы знаем,
что при n маленькое равном единице верно
следующее: верно следующее
какие бы N большое объектов мы
ни взяли (нас природа этих объектов не интересует) даже вот так:
сколько бы объектов мы ни взяли, каково бы ни было число N большое,
это значок "для любого" каково бы ни было N большое,
и каковы бы ни были сами вот эти вот объекты N а1 и так далее аN большое,
и наконец, каково бы ни было одно-единственное свойство альфа один,
вот простите за занудство, но я напишу в такой степени подробности,
вот какими бы ни были все вот эти вот данные, теорема верна.
Формула включений-исключений верна.
Мы ее только что доказали.
Ну давайте, не верна, чтоб здесь "верно" и здесь "верно" как-то нехорошо,
ну напишем "справедлива".
Для красоты.
Имеет место формула включений-исключений.
Не важно, сколько этих объектов, кто они там, это люди,
это какие-нибудь, я не знаю, бракованные-небракованные детали,
это какие-нибудь машины там, что хотите.
Каково бы ни было свойство, но если только оно одно- формула включений-исключений
верна, вот это мы доказали.
Дмитрий Ильинскийпреподаватель
Андрей Райгородскийпрофессор, доктор физико-математических наук
