Рассмотрим пример

В группу артистов входят певцы, танцоры и музыканты.

При этом из них:

1) 9 человек певцы, 12  танцоры и 7  музыканты;

2) 8 человек одновременно певцы и танцоры, 5 человек

певцы и музыканты, 6 являются танцоры и музыканты;

3) 4 человека одновременно певцы, танцоры и музыканты.

Тогда по формуле включений-исключений общее число людей в группе равно: 9 + 12 + 7  8  5  6 + 4 = 13.

Замечание. Справедливость формулы бинома Ньютона может быть установлена с помощью несложных комбинаторных рассуждений.

Выпишем очевидные соотношения (1  x)^r = (1x) . . . (1x) = а₀ x⁰ + . . . + а_r x^r. Очевидно, что значение коэффициента а_i определяется количеством разных произведений, в которых из i скобок в произведение включается x, а из остальных ri скобок в произведение входит 1. Поэтому а_i = . Следовательно,

(1  x)^r =  x+... + (1)ⁱ xⁱ +...+(1)^r x^r.

Упражнение

Сколько существует различных слов в английском языке которые состоят из 7 символов и либо начинаются с WH, либо содержат средний символ R, либо заканчиваются на ING.

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

1.  A  B  =  A  +  B  - AB;

2.  A \ B  =  A  - AB;

3. A  (B  C) = (A  B)  (A  C);

4. A  (B \ C) = (A  B) \ (A  (B  C))

3. Отношения

3.1. Определение и примеры отношений

Пусть заданы множества А и B. Бинарным отношением на этих множествах (или отношением) называется всякое подмножество множества А  B. Тo есть отношение на А и B  это произвольное множество пар элементов, первая компонента которых принадлежит А, а вторая - множеству B.

Содержательно всякое отношение состоит из таких пар элементов, между которыми существует определенная смысловая связь. Например, пусть А  это множество людей, а B  множество наименований специальностей. Тогда множество всех таких пар, в которых первая компонента задает конкретного человека, а вторая  специальность, которой такой человек владеет, образует отношение на А B. Для обозначения отношений в дальнейшем будут использоваться строчные символы греческого алфавита:

Если (a, b) , то в этом случае говорят, что элементы a и b находятся между собой в отношении .

Для записи факта, что элементы a и b находятся между собой в отношении , используется также запись a  b.

Одним из свойств бинарных отношений на произвольных множествах А и B является возможность взаимно однозначного соответствия между такими отношениями и бинарными предикатами, переменные которых принимают значения из множеств А и B соответственно.

Такое соответствие предикатов и отношений определяется следующими соотношениями.

1. Пусть   А B. Ему соответствует такой предикат P(x, y), для которого переменные x и y принимают значения на множествах A и B, что P(x, y) является истинным для тех и только тех наборов значений переменных x и y, которые входят в отношение .

2. Пусть P(x, y)  некоторый предикат, переменные которого принимают значения из множеств A и B соответственно. Этому предикату можно сопоставить отношение   А  B, состоящее из тех и только тех элементов множества А B, на которых предикат P является истинным.

Понятие отношения обобщает понятие отображения.

Если  некоторое отображение, то ему можно поставить в соответствие отношение . Такое отношение  принято называть графиком отображения f.

Если отношение  образует график некоторого отображения, то для него справедливо следующее свойство. Для каждого элемента x A в отношении  содержится ровно одна пара, первая компонента которой равна x.

Отношения, для которых не выполнено последнее свойство, не являются графиками отображений. В этом случае имеет место один из случаев:

1. для некоторого a A в  нет пары с первой компонентой, равной a;

2. для некоторого a A в  содержится не менее двух разных пар, первая компонента которых равна a.