Множества. Комбинаторика. Отношения (стр. 5 )

3) Crn Ckn = Crn 2n–r (тождество Коши);

4) Ckn+m = Csn Ck–sm, k £ n, m; n, m ³ 1;

5) Cn2n = (Csn)2;

6) Ckn Ckn = Cmn Cn –kn -m, n > 1, k £ n, m £ k;

Указание к 1). Продифференцировать равенство (1)

(1+x)n =Ckn xk

1.2.4. Размещения с повторениями

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

Пример: Пусть дано множество B={a, b, c}. Выпишем все размещения из трех по два с повторениями: {a, b}, {b, a}, {a, c}, {c, a}, {b, c}, {c, b}, {a, a}, {b, b}, {c, c}.

Число всех размещений с повторениями из n пo r будем обозначать Urn. По определению U0n =1.

ТЕОРЕМА. Urn = nr.

Доказательство проведем методом полной математической индукции по переменной r. Очевидно, что U1n = n. Предположим, что для r = k справедливо равенство Ukn = nk. Пусть r = к+1. С помощью правила умножения можно доказать равенство

Urn = n Ur-1n (1)

Отсюда Uk+1n = n Ukn = n×nk = nk+1.

Доказательство 2: По правилу произведения начинаем выбирать элементы. Первый элемент можно выбрать n способами, второй – тоже n способами, так как элементы могут повторяться, и т. д., т. е. для выбора любого элемента существует ровно n способов, а так как их ровно r, то мы и получаем nr. ■

ТЕОРЕМА. Число всех подмножеств конечного множества М из n элементов равно 2n.

Доказательство. Выберем подмножество. Если элемент принадлежит подмножеству, то кодируем эту ситуацию символом 1, а если не принадлежит, то символом 0. Элементы исходного множества пронумеруем. Тогда каждому подмножеству ставится во взаимнооднозначное соответствие размещение с повторениями из двух элементов

О и 1 по n. Таких размещений 2n, поэтому и подмножеств 2n . ■

С другой стороны, таких подмножеств Crn и, тем самым, формула (3) из предыдущего параграфа доказана вторым способом.

Упражнение

1) Сколько существует различных функций из Х в У, если card Х = m, card У = n? Ответ: nm.

1.2.5. Сочетания с повторениями

Неупорядоченная выборка, в которой элементы могут повторяться, называется сочетанием с повторениями. Число всех сочетаний с повторениями из n по r будем обозначать Crn (n).

ТЕОРЕМА.

Crn (n) = Cr-1n (n) + Crn-1 (n). (1).

Доказательство аналогично выводу формулы Паскаля. ■

ТЕОРЕМА.

Crn (n) = Crn+r–1. (2).

Доказательство. Проведем индукцию по n. База индукции есть: Cr1 (n)=1, Cr1–r–1 = 1. Пусть формула верна для n = к. Положим n= к–1. Докажем с помощью индукции по r равенство Crk+1 (n) = Crk+r. При r = 1 имеем C1k+1 (n) = k+1, Crk+1+ r–1 = C1k+1 = 1, т. е. база индукции есть. Пусть формула верна при r = s, т. е. Csk+1 (n) = Csk+ s. Тогда при r = s +1 по формуле (1) и гипотезе индукции Cs+1k+1 (n) = Csk+1(n) + Cs+1k (n) =Csk+ s + Cs+1k+ s = Cs+1k+ s+1 = Cs+1(k+1) + (s+1) – 1. ■

1.2.6. Принцип включения и исключения

ТЕОРЕМА. Пусть имеется N объектов и свойства a1,...,an. Обозначим через j(ai1...ai k) число объектов, обладающих свойствами ai1,...,ai k; через j( ai1...ai sùai s+1.... ùai k) – число объектов, обладающих свойствами ai1,...,ai k, но не обладающих свойствами ai s+1.... ai k. Тогда число объектов, не обладающих не одним из свойств j(ùa1... ùan) определяется по формуле включения и исключения:

j(ùa1 ùa2 ... ùan) = N – j(a1) – j(an) + j(a1a2) + j(a1a3) +...+ j(an-1 an) – j(a1a2a3) – j(a1a2a4) –...– j(an-2an-1an) + ... +(–1)n j(a1 ...... an) (1)

Доказательство. Проведем индукцию по числу свойств. При n = l имеем:

j(ùa1) = N – j(a1) (2).

Пусть:

j(ùa1 ùa2 ... ùan-1) = N – j(a1) –...– j(an-1) + j(a1a2) + j(a1a3) +...+ j(an-1an) – ... – (–1)n-1 j(a1 ...... an-1) (3)

Применим формулу (1) к свойству an:

j(ùa1 ùa2 ... ùan) = j(ùa1 ùa2 ... ùan-1) – j(ùa1 ùa2 ... an) (4).

Рассмотрим множество тех объектов, которые обладают свойством an. Среди них не обладают свойствами a1 a2 ... an-1, элементы, число которых вычисляется следующим образом:

j(ùa1 ùa2 ... ùan-1 an) = j(an) – j(a1an) –...– j(an-1 an) + j(a1a2an) + j(a1a3an) +...+ j(an-2an-1an) + ... +(–1)n j(a1 .... an) (5).

Подставив в формулу (4) выражение для j(ùa1 ùa2 ... ùan-1) из (3) и для j(ùa1 ùa2 ... ùan-1 an) из (5), получим (1). <

3адача о беспорядках. Сколько существует перестановок i1.......1n чисел 1,2,...,n таких, что ik ¹ k для всех k=1,2,...,n?

Решение. Общее число перестановок N=n! Число перестановок, в которых 1 стоит на своем месте (n-1)!, число 2 стоит на своем месте (n-1)! Число перестановок, в которых элементы i и j стоят на своих местах (n-2)! Отсюда по формуле включений и исключений получаем ответ на заданный вопрос:

N(0) = n! – n(n-1)! + C2n(n-2)! – C3n(n-3)! +...+ (–1)k×1 = n!(1-1+1/2!-1/3!+...+(–1)r×1/r! +...+(–1)n/n!) » n!/e.

Задача о встречах. Сколько существует перестановок i1.......1n, в которых аi = i точно в r местах?

Решение. N(r)= n!/r!(1-1+1/2!–...+(–1)n-r × 1/(n-r)!), так как N(r) = (n-r)! –n(n-r-1)! + C2n-r (n-r-2)! – …

Упражнения

1)  Докажите, что n! = nn – C1n(n-1)n + C2n(n-2)n –…

2)  Найдите количество чисел, не делящихся на 3, 7, 11 в первой тысяче натурального ряда.

3)  Найдите сумму всех целых чисел от 1 до 1000, которые не делятся на 5 и на 7.

Глава 2. Булевы функции. Замкнутые классы и полнота

2.1. Булевы функции

2.1.1. Алгебра высказываний

Высказывание – предложение, о котором можно сказать, истинно оно или ложно. При этом оно не может быть одновременно истинным и ложным.

Пример:

1)  “Сейчас идет дождь”. Это предложение является высказыванием.

2)  “Снег – зеленый”. Это тоже высказывание.

3)  “Стой!” Это предложение не является высказыванием.

Существуют, так называемые, “логические парадоксы”. Например, про предложение “Я лгу” нельзя сказать истинно оно или ложно. Если оно истинно, то я лгу, а раз я лгу, значит, в данный момент говорю правду. Противоречие.

Отрицанием высказывания А называется такое высказывание, которое истинно тогда и только тогда, когда А ложно. Обозначается оно через ØА или. Читается “не А”. Операция отрицания унарная.

Операции, которые будут рассматриваться далее бинарные.

Конъюнкцией двух высказываний А и B называется такое третье составное высказывание, которое истинно тогда и только тогда, когда А и B истинны одновременно. Для конъюнкции применяются обозначения A&B, A^B, AB (логическое умножение). Запись читается “А и В”.

Дизъюнкцией двух высказываний А и B называется такое третье составное высказывание, которое истинно тогда и только тогда, когда одно из высказываний А и B истинно или оба высказывания истинны одновременно. Обозначение: АÚВ (логическая сумма). Читается “А или В”.

Импликацией двух высказываний А и B называется такое третье составное высказывание, которое ложно тогда и только тогда, когда А истинно, а В ложно. Обозначение А®B. Читается “из А следует В”. Здесь А называют посылкой, а В – следствием.

Эквиваленцией двух высказываний А и B называется такое третье составное высказывание, которое истинно тогда и только тогда, когда высказывания А и В одновременно истинны или ложны. Обозначение АÛВ. Читается “А тогда и только тогда, когда В”, “для А необходимо и достаточно В”.

Действия над высказываниями можно описать с помощью таблиц истинности. В них буква “И” соответствует значению “истина”, а буква “Л” значению “ложь”.

А	В	А&В	АÚ В	АÞ В	АÛ В
Л	Л	Л	Л	И	И
Л	И	Л	И	И	Л
И	Л	Л	И	Л	Л
И	И	И	И	И	И

Заметим, что двуместная операция дизъюнкции соответствует союзу “или”. Но в обычной речи союз “или” употребляется, по крайней мере, в двух различных смыслах: неальтернативное неисключающее “или” и альтернативное исключающее “или”. В нашем случае дизъюнкция соответствует высказыванию первого типа.

2.1.2. Функции алгебры логики

Функция у = f(x1,…,xn) называется n–местной булевой функцией, если каждая переменная принимает только два значения 0 или 1 и функция принимает значения в этом же множестве {0;1}. Булевой функцию называют в честь ирландского математика Джорджа Буля (1815 – 1864), работавшего в университете города Корк, отца писательницы Этель Лилиан Войнич. С именем Буля связана революция в логике, она приобрела письменность, появился новый тип алгебры. Другие имена, связанные с этой теорией: Аристотель, Раймундо Луллий (исп. философ, монах–отшельник 12–13 вв), Б. Спиноза, Н. Винер. Булевые функции называют также функциями алгебры логики или, более полно, алгебры двузначной логики.

Булеву функцию можно задать таблицей:

x1	x2	…..	xn-1	xn	f(x1,…,xn)
0	0	….	0	0	f(0,…,0)
0	0	….	0	1	f(0,…,1)
…	…	….	….	…
1	1	….	1	1	f(1,…,1)

Всюду в дальнейшем наборы значений переменных x1,…,xn булевой функции будем располагать в стандартном порядке, при котором набор a = <a1,…,an> представляет собой двоичную запись числа в n разрядах своего номера (нумерация начинается с нуля), т. е.