Полная версия

Главная arrow Математика, химия, физика arrow Дискретная математика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

Метод включения-исключения для решения задач на множества

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

Рассмотрим классическую задачу о количестве элементов, получаемых при объединении множеств (рис. 1.2).

Пересекающиеся множества

Рис. 1.2. Пересекающиеся множества

Основная формула, по которой находят количество элементов в объединении двух множеств, вычисляется по диаграмме Эйлера— Венна, так как часть элементов принадлежат одновременно А и В и не могут учитываются дважды:

А и В = А + В-А п В (1.7)

Для трех множеств А, В и С формула пересчета выглядит следующим образом:

А u В и С| = А + |Я| + |С| -AnB-AnC-

-ВглС + АпВглС. (1.8)

Теорема 1.2. Формула включений и исключений

Если Х{, Х2, ..., Хпнекоторые множества и их мощность равна

Х], Х2,| Хп, тогда мощность объединения этих множеств равна

Х{ и12и ... и Х„ = |Х,| + Х2 + ... + Хп-- {Х{ п Х2 + Х{ п Х31 + ... + Xn_i п Хп) +

+ о Х2 о Х3 + ... + Хп_2 о Xп_| о ^Т|} + ... +

71—1

+ (-1)""‘ ЛГ, пХ2п...пХп

(1.9)

Обобщая, получаем формулу включения и исключения для 7V объектов со свойствами, которыми эти объекты могут обладать или не обладать. Пусть имеется N объектов, которые могут обладать п свойствами ?j, а2, ..., ап. Обозначим через N(ah ?j, ..., ak) число предметов, обладающих свойствами ап af, ..., ак и, быть может, какими-либо другими свойствами. Тогда число N' предметов, не обладающих ни одним из свойств а{, а2,..., ап, дается формулой

N' = N-N(a}) - N(a2) - ... - N(an) + Щах, а2) + N(ab а3) + ... +

+ N(an_і, а„) - N{ax, а2, а3) - ... - N(an_2, ап_ь ап) + ... +

+ (-)пЩаь...,ап). (1.10)

Задача 1.4

В аудитории находятся несколько программистов. Шестеро знают VISIAL BASIC, шестеро — PHP, семеро умеют программировать на JAVA. Четверо знают VISIAL BASIC и PHP, трое — VISIAL BASIC и JAVA, двое — PHP и JAVA. Один из них умеет программировать на всех языках. Сколько человек в аудитории? Сколько из них знают только VISIAL BASIC?

Решение.

По условию задачи каждый из присутствующих знает хотя бы один язык программирования.

Зададим: РVB — свойство знать VISIAL BASIC; Рр свойство знать РНР; Р} свойство знать JAVA.

Тогда количество программистов в аудитории п п = л(Рув) + п(Рр) + n(Pj) - л(РуВ & Рр) - n(Pwв & Р]) -- п(Рр & Pj) + л(РУВ &Pp&Pj> = 6 + 6 + 7- 4- 3- 2 + 1 = 11.

По формуле включений и исключений получается, что людей, знающих только VISIAL BASIC, нет:

Pр’ Pj) = n(Pb) ~ n(Pvb & Pp) ~ n(Pyв & Pj) +

+ л(РУВ &/p&/j) = 6- 4- 3 + l = 0.

1.4. Теория отображений и функций

Один из подходов, описывающий теорию отображений одного множества в другое множество, опирается на понятие декартова произведения.

Декартовым произведением двух множеств А и В является новое множество С, элементами которого являются все упорядоченные пары (а, Ь) такие, что первый элемент в паре принадлежит множеству А, второй элемент в паре принадлежит множеству В:

С = А х В = {(а, Ь) / а е А, Ь е В}.

Тогда мы говорим, что множество А отображается в множество В и элемент а отображается в элемент Ь. Обратите внимание, отображение не всегда взаимно однозначно!

Порядок в паре очень важен, в общем виде А х В ф В х А. Декартово произведение не обладает свойством коммутативности.

Задавая различные ограничения на подмножества декартова произведения, мы приходим к понятиям функции, операции, а также бинарного отношения.

Подмножество Тдекартова произведения Хх У называется функцией, если для каждого элемента х е X найдется не более одного элемента у е У (или существует единственный элементу, 3у е Y) такого, что (х, у) е F(x, у), т.е. выполняется свойство однозначности полученного результата.

Множество X называется областью определения функции F, т.е. domF, а множество ^называется областью значений функции F.

Если элементу ? domF, то говорят, что функция Fm определена на Z- Таким образом, функции могут быть как полностью определенными на множестве X, так и частично определенными. Точно так же область значений функции может не совпадать с множеством Y, а быть его подмножеством.

Если область определения функции F из X в Y совпадает с X, то пишут F:X^> Y.

Например, тождественная функция U отображает множество X само в себя, причем U: X —> X для любого х е X. А функция-константа С, полностью определенная на X, переводит все элементы множества X в один-единственный элемент се Y, С: X—> с.

В других разделах математики для функций обычно вместо записи (х, у) е F используют у = Fix).

Функция называется F: X —> Yинъективной, или инъекцией (вложением), если она отображает разные элементы Xв разные элементы множества F, т.е. для любого элемента х, принадлежащего X, и любого элемента z, принадлежащего X, неравных между собой, следует, что F(x) не равно F(z):

Ух Е X и /z е Х,х * zFix) * Fiz). (1.11)

Функция F:X^> Yназывается сюръективной, или сюръекцией Наложением), если множество ее значений есть все множество Y, т.е. для любого элемента у, принадлежащего множеству Л1, найдется элемент х из множества Xтакой, что у = Fix):

VyEY,3xEX—>y = Fix). (1.12)

Функция F: X —> Y называется биекцией или взаимно однозначным соответствием, если она одновременно является инъекцией и сюръекцией (вложением и наложением).

Любая функция F: X —> Yпредставляет собой подмножество декартова произведения множеств Хи Y. Поэтому мы можем построить подмножество обратного декартова произведения Y х X и определить обратную функцию F~l: Y—> X.

Функция F состоит из пар вида (я, Ь), где Ъ = Fia). Если функция обратима, то она состоит из пар ф, а), где а = F~). Значит, обратимая функция должна удовлетворять условию: если Fia) = b, то F~) = а.

Теорема 1.3. Теорема о существовании обратной функции

Если F— биекция, то существует обратная функция F~], для которой F~x{y) = х тогда и только тогда, когда F(x) = у.

Построим обратную функцию для F: X —> Y, у = 4х + 5. Выразим алгебраически х через у и получим обратную функцию:

х = Гу) = -Ау-$).

4

Частным случаем функции является операция О. В этом случае область значения Xи область определения ^совпадают, т.е. если задано множество М, то операция О есть подмножество декартова произведения М х М, причем для любого элемента х е М существует единственный у е М такой, что(л:, у) е 0(М):

О ^ М х М,х є М,3у є М, (х, у) е О(М). (1.13)

Задача 1.5

Построить на множестве М = {а, Ь, с, 6} операцию, сюръекцию, инъекцию и биекцию максимальной мощности.

Решение.

Операция означает, что множество X совпадает с множеством У, для получения максимальной мощности они же равны множеству М. При задании операции необходимо обеспечить свойство однозначности результата, например Т7, = {(а, Ь), (Ь, Ь), (с, б), (б, б)}.

При построение инъекции необходимо учитывать, что различным л; соответствуют различающиеся у, например Р2 = {(а, Ь), (Ь, с), (с, б), (б, а)}. Для построения сюръекции нужно использовать все элементы множества У, Р3 = {{а, а), (Ь, б), (с, с), (б, Ь)}. Обе эти функции являются как сюръекциями, так и инъекциями, следовательно, они — биекции. Мощность во всех случаях равна четырем.

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

Теорема 1.4. Принцип Дирихле

Пусть Р. Л —> Вфункция, отображающая конечное множество Л в конечное множество В. Тогда если Л >В, то по крайней мере одно значение Рвстретится более одного раза.

Если Л > кВ для некоего натурального к, то одно из значений функции Т7 повторится по крайней мере к + 1 раз.

Рассмотрим несколько примеров.

Задача 1.6

В учебной группе 15 студентов. Показать, что по крайней мере у двоих день рождения в одном и том же месяце.

Решение.

Положим, что множество А — множество студентов, а множество В — множество 12 месяцев. Рассмотрим функцию Р: А —> В, которая каждому студенту сопоставляет месяц рождения. Так как А > В, то согласно принципу Дирихле функция должна иметь повторяющиеся значения, т.е. найдутся два человека, родившиеся в одном и том же месяце.

Задача 1.7

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

Решение.

Положим, х — один из шести людей, множество А — множество оставшихся пяти человек в группе и множество В = {0, 1}.

Определим функцию Р: Д —> В следующим образом:

Г0, если а не знаком с х,

т= /

[1, если а знаком с х.

Поскольку 5 = А > 2В, то найдется три человека, которые либо знакомы с х, либо все трое его не знают.

 
<<   СОДЕРЖАНИЕ   >>