Дискретная математика. Краткий курс. Учебное пособие. Александр Анатольевич Казанский

утверждение Р истинно для всех n. Иногда принцип математической индукции записывают в более удобном для использования виде

      1) P (1) истинно.

      2) P (n + 1) истинно, если истинно P (k) для всех 1 ≤ k < n.

      Тогда Р истинно для каждого положительного целого.

      1.11. Представление множеств формулами

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

      Для универсального множества U всегда можно построить его разбиение, из множеств которого легко получать требуемые совокупности. Наиболее конструктивным разбиением для этих целей является система множеств, порождаемая фундаментальными произведениями. Из 1.7 следует, что для любых n множеств можно построить разбиение S универсального множества U на 2n подмножеств, называемых фундаментальными произведениями.

      Определение

      Любое множество или совокупность множеств разбиения S можно представит как объединение пересечений, каждое из которых является фундаментальным произведением. Обратно, каждое непустое выражение из объединения фундаментальных произведений задает некоторое множество или совокупность множеств разбиения и такое задание однозначно определяет это множество.

      Если рассматривать операцию объединения как сложение, а операцию пересечения как умножение, то подобные выражения часто называют многочленами. Эти многочлены можно преобразовывать, используя алгебраические методы. Многочлен, образованный из фундаментальных произведений, единственным образом задает любое подмножество разбиения. Будем называть такой многочлен каноническим. Осуществляя эквивалентные преобразования выражения для многочлена в каноническом виде, при котором сохраняется множество, которое он определяет, можно получать более простые выражения для аналитического задания данного множества. Если многочлен для заданного множества не допускает дальнейшего упрощения, то такой многочлен называется минимальным.

      Рассмотрим пример использования многочленов.

      Пример 1.6

      Предположим, что в некотором университете проведена выборочная проверка посещаемости занятий девяти студентов по трем предметам: математике, информатике и английскому языку. Обозначим через А множество