Лекции Просолупов

Здесь ( ) — дельта-функция, которую мы обсуждали в замечании 19.5 параграфа главы .

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

§31. Задача о беспорядках

Интуитивная постановка задачи о беспорядках:

Задача 31.1 . Пусть в рамках чемпионата в городах должно пройти ровно по

одному матчу. Матчи судят судей, каждый из которых из одного из городов, все

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

Можно привести другую формулировку задачи, математическая идея которой будет той же.

Задача 31.2 . Пусть человек пришли в театр и сдали шляпы в гардероб. Когда спектакль закончился и зрители получили шляпы назад, оказалось, что каждый из получил чужую шляпу. Сколько существует вариантов такого события?

Формально задача ставится следующим образом.

Определение 31.3 . Беспорядком на множестве {1, ..., } называется перестановка, которая не сохраняет ни одного элемента: ( ) ̸= , = 1, .

61

Задача 31.4 . Найти число беспорядков на множестве {1, ..., }:

( ) = |{ | , ( ) ̸= , = 1, }|.

Решим эту задачу с помощью принципа включения-исключения.

Будем говорить, что обладает свойством , если ( ) = . Тогда = {1, ..., } — множество всех свойств, которыми может обладать перестановка. Пусть. Пусть

=( ) — число перестановок, каждая из которых обладает всеми свойствами изи не обладает свойствами из :

=( ) = |{ | , ( ) = , ; ( ) ̸= , }|.

≥( ) — число перестановок, каждая из которых обладает всеми свойствами изи, возможно, какими-то еще:

≥( ) = |{ | , ( ) = , }|.

62

Лекция 9. Мощность объединения множеств, число целочисленных решений системы неравенств

§32. Мощность объединения множеств

Приведем еще одну задачу, которая решается с помощью принципа включенияисключения, — задачу нахождения мощности объединения пересекающихся множеств.

Задача 32.1 . Пусть 1, 2, ..., — конечные множества. Пусть

∑

+| 1 ∩ 2 ∩ 3 | − · · · + (−1) +1| 1 ∩ 2 ∩ ... ∩ |. (22)

1≤ 1< 2< 3≤

∑

−| 1 ∩ 2 ∩ 3 | + · · · + (−1) | 1 ∩ 2 ∩ ... ∩ |.

1≤ 1< 2< 3≤

Перенесем все слагаемые, кроме первого, за знак равенства и получим искомое утверждение.

63

Замечание 32.3 . Часто именно формулу (22) называют принципом включенияисключения.

§33. Число целочисленных решений системы неравенств

В параграфе мы показали, что число решений уравнения 1 + 2 + · · · + = в неотрицательных целых числах находится по формуле (15):

а число решений неравенства 1 + 2 + · · ·+ ≤ в неотрицательных целых числах

— по формуле (16):

Здесь мы расширим множество систем, для которых можно будет найти число решений.

Для начала положим, что на значения переменных наложены ограничения снизу. Пусть N0, = 1, , и задана система

1 + 2 + · · · + = ,

Чтобы найти число решений этой системы, достаточно сделать замену = − . Тогда ≥ 0 и

( 1 + 1) + ( 2 + 2) + · · · + ( + ) = ,

1 + 2 + · · · + = − 1 − 2 − · · · − .

Согласно формуле (15), число целочисленных решений данной системы

Рассмотрим систему с ограничениями на переменные и сверху, и снизу. Пусть, N0, ≤ , = 1, . Требуется найти число целочисленных решений системы

64

= {( 1, 2, ..., ) | 1 + 2 + · · · = , ≤ , = 1, }.

Согласно (23)

Обозначим , = 1, , — множество решений системы (*), для которых не выполняется ограничение ≤ :

= {( 1, 2, ..., ) | 1 + 2 + · · · = ,

≤ , = 1, , + 1 ≤ }.

Таким образом, все решения системы (*), которые не удовлетворяют хотя бы одной верхней границе из (26), лежат в множестве 1 2 ... . Следовательно, число решений системы (25)-(26) равно

| ( 1 2 ... )| = | | − | 1 2 ... |.

Использовав утверждение 32.2, получим

Теперь, чтобы найти число решений системы (25)-(26), достаточно научиться находить мощность пересечения произвольного набора множеств .

Пусть {1, ..., }. Тогда

= {( 1, 2, ..., ) | 1 + 2 + · · · = ,

≤ , = 1, , + 1 ≤ , }.

Другими словами, есть множество решений системы

Тогда, согласно (23),

−

65

Подставив эти значения в формулу (**), получим число решений системы (25)-(26). Рассуждения для системы

1 + 2 + · · · + ≤ ,

аналогичны рассуждениям для системы (25)-(26) с точностью до замены величины (23) на величину (24).

Пример 33.1 . Рассмотрим систему всего с двумя переменными:

и систему без верхних ограничений на переменные:

Сравним графическое изображение области, в которой лежат решения системы ( ) (рис. 9), и области, где находятся решения системы ( ) (рис. 10). Как

Рисунок 9: Множество решений неравенства 1 + 2 ≤ с нижними ограничениями на значения переменных.

можно видеть, чтобы из области решений для системы ( ) получить область для системы ( ), нужно удалить из нее объединение областей решений систем

66

Рисунок 10: Множество решений неравенства 1 + 2 ≤ с ограничениями на значения переменных сверху и снизу.

Пример 33.2 . Пусть дана система неравенств

1 + 2 + 3 ≤ 30,

Обозначим за множество целочисленных решений исходной системы без учета верхних границ на значение переменных:

Число целочисленных решений системы (*) вычисляем по известной формуле:

67

Посчитаем мощности этих множеств.

Также рассмотрим все возможные пересечения этих множеств и посчитаем их мощности.

68

Теперь количество целочисленных решений исходной системы можно получить по формуле:

| | − | 1 2 3| = | | − (| 1| + | 2| + | 3| − | 1 ∩ 2|−

−| 1 ∩ 3| − | 2 ∩ 3| + | 1 ∩ 2 ∩ 3|) = 2925 − 560 − 969−

−969 + 56 + 56 + 165 = 704.

Рассмотрим теперь систему с ограничением на сумму переменных снизу:

1 + 2 + · · · + ≥ ,

Сделаем замену переменных = − . Тогда ограничения на значения переменных трансформируются следующим образом:

Подставим замену в неравенство для суммы переменных:

( 1 − 1) + ( 2 − 2) + · · · + ( − ) ≥ ,

1 + 2 + · · · + ≤ 1 + 2 + · · · + − .

Получили систему

которая может быть решена указанным выше для системы (25)-(26) способом. Математическая логика окончательно оформилась как самостоятельная

математическая дисциплина к 30-м годам XX века. Основная причина ее появления

— математические парадоксы, например парадокс Рассела. Сложно проводить математические рассуждения, не будучи уверенным в их непротиворечивости, а также в существовании объектов, которые они определяют. Возникла идея исследовать язык логики и математики, подойти к доказательству на основе понятий аксиом и правил вывода.

69

Лекция 10. Булевы функции и формулы.

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

Будем рассматривать булевы функции (функции алгебры логики) — функции, аргументы и значения которых принимают значения истина и ложь. Истину и ложь будем обозначать соответственно 1 и 0. Положим 2 = {0, 1}. Таким образом,

функция аргументов есть

Аргументы этих функций будем называть логическими переменными и обозначать буквами , и , возможно с индексами. Множество всех булевых функций

(функций алгебры логики) будем обозначать 2.

Пример 34.1 . Табличное задание функции :

нумеровать от 0 до 23 −1, то набор с номером оказывается представлением числа

в двоичной системе счисления. Всего различных функций от 3-х аргументов —

223

В общем случае число строк в таблице для функции от аргументов равно 2 . Число различных булевых функций от аргументов — 22 .

Пример 34.2 . Рассмотрим, как зависит функция из примера 34.1 от

переменной . Пусть ′ = ( 1, 0, 3) и ′′ = ( 1, 1, 3) — два набора с произвольными значениями 1 и 2. Тогда по таблице выше можно убедиться, что ( ′) = ( ′′):

(0, 0, 0) = (0, 1, 0), (0, 0, 1) = (0, 1, 1) и так далее. В таком случае, можно сказать, что функция не зависит существенно от переменной , или, что — несущественная переменная функции .

Замечание 34.3 . Среди 22 различных функций от переменных далеко не все зависят от аргументов существенно. В это число войдут и все функции от −1,− 2, и т. д. аргументов.

70