Введение. 
Теоретические основы принципа включений-исключений и особенности его применения в решениях задач по дискретной математике

Прежде чем приступать к изучению принципа включений и исключений, следует хорошо понимать, на чем основан этот принцип. А именно, один из основных разделов современной математики — множества.

Понятие множества является первичным, т. е. не поддается определению через другие, более простые понятия. С понятием множества мы встречаемся довольно часто: множество студентов нашего института, множество преподавателей, множество изучаемых дисциплин.

Хотя в силу первичности понятия множества нельзя дать ему строгое определение, но можно воспользоваться описательным определением, предложенным одним из создателей теории множеств — немецким математиком Георгом Кантором (1845−1918). Он сказал: «Множество есть многое, мыслимое нами как единое».

Все множества состоят из определенного конечного числа объектов, которые мы будем называть элементами множества. При этом каждый из объектов данного вида либо принадлежит, либо не принадлежит рассматриваемому множеству.

Множества, включающие только такие объекты, принадлежность или не принадлежность которых к тому или иному множеству не вызывает сомнения, называются четкими множествами. Поскольку каждый рассматриваемый объект либо принадлежит, либо не принадлежит к рассматриваемому четкому множеству, эти множества всегда имеют ясно очерченные границы. Четким множествам противопоставлены нечеткие или «лингвистические» множества, включающие такие объекты, которые могут быть отнесены к тому или иному множеству лишь с определенной степенью достоверности. Понятие нечетких множеств было впервые введено в 1965 году американским математиком Л. Заде.

Множества, которые состоят из конечного числа элементов, называются конечными множествами. К числу конечных множеств относится также и пустое множество, т. е. множество, не содержащее ни одного элемента.

Введение

понятия пустого множества связано с тем, что, определяя тем или иным способом множество, мы не можем знать заранее, содержит ли оно хотя бы один элемент. Например, множество отличников в какой-либо учебной группе.

Множества, рассматриваемые при решении практических задач, чаще всего имеет дело с конечными множествами объектов.

Не всякая задача комбинаторики решается непосредственным применением основных комбинаторных принципов — правила суммы или произведения, подсчётом числа размещений или сочетаний. В некоторых случаях приходится идти окольным путем и действовать своеобразным «методом решета», который состоит в следующем: для нахождения числа элементов интересующего нас множества мы сначала находим число элементов некоторого большего множества, а потом «просеиваем» нужные элементы, постепенно отбрасывая лишние.

Принцип включений-исключений — это важный комбинаторный приём, позволяющий подсчитывать размер каких-либо множеств, или вычислять вероятность сложных событий.