Глава 2. Математическая логика

Математика

Содержание

Глава 1. Элементы теории множеств.

1.1. Множества

1.2. Отношения

1.3. Отображения. Функции

Глава 2. Математическая логика.

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

2.2. Логика предикатов

2.3. Решение логических задач с помощью булевых функций

Глава 3. Комбинаторика.

3.1. Общие правила комбинаторики

3.2. Перестановки

3.3. Размещения

3.4. Сочетания

Раздел 4. Элементы теории вероятностей.

4.1. Основные понятия

4.2. Определение вероятности события

4.3. Теорема сложения вероятностей

4.4. Теорема умножения вероятностей

Глава 5. Элементы теории графов.

5.1. Основные понятия теории графов.

5.2. Задача определения кратчайшего пути.

5.3. Задача о кратчайшем расстоянии между двумя пунктами.

5.4. Построение коммуникационной сети минимальной длины.

5.5. Задача определения максимального потока.

Глава 1. Элементы теории множеств

Множества

Теория множеств как математическая дисциплина создана немецким математиком Г.Кантором (1845-1918).

Множество – одно из основных (фундаментальных) понятий математики, а потому строгого определения не имеет. Описательно термин «множество» объясняется как собрание, совокупность, набор некоторых объектов произвольной природы, объединенных по каким-то общим для них признакам. Объекты, из которых состоит множество, называют его элементами.

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

Исходя из примеров, можно определить свойства множества:

1) элементы множества должны быть строго определены;

2) каждый элемент должен учитываться только один раз;

3) порядок расположения элементов внутри множества не имеет значения.

Пример: Множество студентов какой-либо группы университета.

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

Множества обозначают заглавными буквами латинского алфавита: A, B, C, D ...; элементы – строчными: a, b, c, ...

Символическая запись означает принадлежность элемента a множеству А. Запись означает, что элемент а не принадлежит множеству А.

Пример: Пусть А – множество четных чисел. Тогда , а .

Если число элементов множества конечно, то множество называют конечным, иначе – бесконечным. Считается, что примеры множеств, взятых из материального мира, конечны. Числовые множества – бесконечны.

Пример: Множество рыб в океане велико, но конечно. Множество действительных чисел – бесконечно.

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

Существуют разные способы задания множеств. Конечное множество можно задать перечислением его элементов.

Пример: С= -- множество цифр десятичной системы счисления.

Также задать множество можно с помощью характеристического признака.

Пример: -- множество четных чисел.

Два множества равны, когда они состоят из одних и тех же элементов.

Пример: Множества и равны.

Пример: Множества и равны.

Множество А называют подмножеством множества В, если каждый элемент множества А является одновременно элементом множества В. В этом случае пишут (читается: «А включается или содержится в В»). Любое множество содержит в качестве подмножества. Очевидно, ( записывают ); А и называют несобственными подмножествами множества А. Все остальные подмножества называют собственными, т.е. кроме его элементов в множестве должен содержаться еще хотя бы один элемент.

Пример: Пусть , тогда .

Основные свойства включения: если ;

если -- равные множества.

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

Пример: R – множество действительных чисел – универсальное множество, если в процессе изучения рассматриваются множества натуральных, целых и рациональных чисел

Существуют следующие операции над множествами:

1) объединение: -- элементы нового множества лежат хотя бы в одном из множеств А или В;

2) пересечение: -- элементы нового множества лежат в обоих множествах А; В;

3) разность: -- элементы нового множества – это элементы множества А, не содержащиеся в В;

4) дополнение множества А в множестве U ( ): .

Пример: .

Тогда .

Введенные операции обладают следующими свойствами:

(коммутативность).

(ассоциативность).

(дистрибутивность)

(идемпотентность).

(поглощение).

Задачи.

1. Используя диаграмму Венна, доказать законы 3 и 5.

2. Используя законы множеств, доказать равенства:

a) .

b) .

c) .

3. Заданы множества . Верным для них будет утверждение...

Варианты ответов:

a) «Множества А и В равны».

b) «Множество B есть подмножество множества A».

c) «Множество А есть подмножество множества В».

d) «Множества А и В не содержат одинаковых элементов».

4. Заданы произвольные множества А, В и С. Расположить указанные ниже четыре множества так, чтобы каждое из них было подмножеством следующего за ним:

a)

b)

c)

d) .

5. Даны множества . Установить соответствия между следующими множествами и их элементами:

6. Принято обозначать:

N – множество натуральных чисел;

Q – множество рациональных чисел;

Z – множество целых чисел;

R – множество действительных чисел.

Тогда верным утверждением будет...

Варианты ответов:

7. С помощью диаграмм Венна исследовать вопрос о справедливости каждого из следующих рассуждений:

а) если А, В, и С – такие подмножества множества U, что

;

b) если А, В, и С – такие подмножества множества U, что и , то .

Отношения.

Между элементами множеств можно установить отношения в виде их произведения. Декартовым произведением множеств А и В называют множество AxB всех упорядоченных пар элементов (а;b), где , т.е. . Элементы a и b при этом называют компонентами (координатами) пары.

Пример: . Тогда

.

Декартово произведение АxА называется декартовым квадратом множества А.

В целях наглядного представления декартовых произведений удобно использовать язык геометрии. Для этого множества X,Y представляются осями координат. Элементы -- соответственно абсциссами и ординатами. Само произведение -- точками плоскости XOY. Любое непустое подмножество такого произведения называется бинарным отношением. Ему можно придать прикладное значение. Например, значения множества X – названия предметов, изучаемых в университете, а элементы множества Y – группы студентов. Тогда отношению XxY можно придать смысл множества изучаемых студентами предметов.

По аналогии с декартовым произведением двух множеств X,Y можно построить декартово произведение XxYxZ трех и более множеств. Пример может быть следующий: по курсу x студент y выбрал билет z.

Бинарные отношения обладают следующими свойствами:

-- рефлексивность – отношение Р, при котором элемент отображается сам на себя, т.е. для любого x из Х выполняется xРx. Например, «x похож на x».

-- антирефлексивность – отношение, противоположное рефлексивности, т.е. xРx не выполняется ни для одного x из X. Например, «скорость компьютера x больше компьютера x». Данное отношение – скорость одного компьютера больше другого – обладает свойством антирефлексивности, т.к. скорость одного и того же компьютера не может превышать саму себя.

-- симметричность – отношение, при котором xРy влечет yРx. Например, отношение «x похож на y» обладает свойством симметричности, т.к. верно, что и «y похож на x». Отношение же «компьютер x быстрее y» не симметрично, т.к. «компьютер y быстрее x» уже не выполняется.

-- асимметричность – отношение, обратное симметричности, т.е. одно из двух соотношений xPy или yPx не выполняется. Отношение «компьютер x быстрее y» асимметрично.

-- антисимметричность – отношение, при котором xPy и yPx выполняются тогда и только тогда, когда x=y. Отношение « » выполняется только тогда, когда x=y.

-- транзитивность – отношение, при котором, из xPy и yPz следует xPz. Например, из того, что «студент В пришел позже студента А» и «студент С пришел позже студента В» следует, что «студент С пришел позже студента А».

Отношение Р называют отношением эквивалентности, если оно одновременно рефлексивно, транзитивно и симметрично.

Пример. Р – отношение равенства треугольников – отношение эквивалентности.

Отношение называют частичного (нестрогого) порядка, если оно одновременно рефлексивно, антисимметрично и транзитивно.

Пример. - рефлексивность

выполняются одновременно, когда - антисимметричность

Если , то - транзитивность.

Следовательно, отношение « » есть отношение частного порядка.

Отношение Р называют отношением строгого порядка, если оно антирефлексивно, антисимметрично и транзитивно.

Пример.Отношение «<» на множестве чисел являются отношениями строгого порядка.

Задачи.

1. Заданы множества , тогда декартовым произведением этих множеств является множество...

Варианты ответов:

2. Выяснить, являются ли следующие отношения отношениями эквивалентности:

а) равенство в произвольной системе множеств;

b) отношение параллельности прямых;

с) отношение «проживания в одном доме» жителей города;

d) ;

e) .

3. Привести примеры отношений:

а) рефлексивного и симметричного, но не транзитивного в некотором множестве;

б) рефлексивного и транзитивного, но не симметричного;

в) симметричного и транзитивного, но не рефлексивного.

Отображение. Функция.

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

Пример. Пусть множество А – перечень размеров обуви от 35 до 45, В – множество студентов МГУКи. Тогда между А и В можно установить соответствие, при котором для каждого элемента А выбирается один, ни одного или совокупность(подмножество) элементов.

На основе понятия соответствия между множествами вводится понятие отображения множеств. При этом различают отображение множества «в» множество и отображение множества «на» множество.

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

Пример. Поставим в соответствие каждому слову некоторого словаря его заглавную букву. Такое соответствие определяет отображение множества слов словаря в множество букв алфавита.

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

Пример.Поставим в соответствие каждому трехзначному числу цифру его десятков. Такое соответствие определяет отображение множества трехзначных чисел на множество В= .

Отображения множеств обычно обозначают буквами f, g, h,…

и пишут .

Если при отображении f элементу соответствует элемент , то элемент b называют образом элемента а, элемент а называют прообразомэлемента b и пишут.

.

Отображение f называют обратимым, если из условия вытекает , т.е. разным прообразам соответствуют разные образы. В этом случае каждый образ y имеет единственный прообраз x и можно определить отображение , называемое обратным к отображению f. Обратное отображение устанавливает взаимно однозначное соответствие между множествами А и , т.е. такое соответствие, при котором каждому элементу множества А соответствует единственный элемент множества и каждому элементу множества соответствует единственный элемент множества А. Взаимно однозначное отображение называют также биекцией.

Отображение f называют функционалом, если множество В является множеством действительных чисел (B=R).

Пример.А – множество участков дорог на трассе. В – значения допустимой скорости.

Отображение f называют оператором. Если множества А и В – любой природы.

Пример.Каждому взрослому человеку соответствует свой ИНН.

Если же и множество А – числовое, то отображение f называют функцией. В частности, если , то говорят о функции одной переменной x. Множество принято обозначать и называть областью значений функции.

Пример.Элементарные функции являются числовыми функциями: .

Если (n-мерное пространство), то говорят о функции n переменных . В этом случае .

Задачи.

1. Изобразить отношение. Указать, является ли данное отношение функцией.

а) ;

б) ;

в) ;

г) ;

д) .

2. Привести примеры функционала и оператора.

Глава 2. Математическая логика

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

Рассмотрим случай, когда элементами множества являются высказывания.

Высказывание есть любое повествовательное предложение, о котором можно сказать истинно оно или ложно. Высказывание является основным понятием математической логики. Широкое применение , кроме самой математики, раздел «Математическая логика» получил при анализе и синтезе логических схем входа и выхода данных в компьютерах и других цифровых устройствах.

Пример: «2x2=4» – истинное высказывание,

« Все студенты МГУКи владеют двумя языками» -- ложное высказывание,

« Да здравствует субботник» -- не высказывание.

Обозначают высказывания прописными буквами латинского алфавита x, y,z; истинностные значения – цифрами 0 (ложно) и 1(истинно).

Функции, аргументы и значения которых могут принимать только значения 0 и 1 называют булевыми функциями.

Операциями над высказываниями являются:

1) отрицание -- такое высказывание, которое истинно, когда x – ложно и наоборот.

-- отрицание (не x)

x

2) дизъюнкция (логическое сложение) – такое третье высказывание,

которое ложно в единственном случае: когда x и y оба ложны; в остальных случаях оно истинно.

-- дизъюнкция ( x или y)

x	y

3) конъюнкция (логическое умножение) – такое третье высказывание, которое истинно лишь в одном случае, когда x и y оба истинны, в остальных случаях – ложно.

-- конъюнкция (x и y)

x	y

4) импликация (логическое следствие) – такое третье высказывание, которое ложно в единственном случае, когда x—истинно, а y – ложно. В остальных случаях -- истинно.

-- импликация ( если x, то y)

x	y

5) эквиваленция (логическое равенство) – такое третье высказывание, которое истинно, когда x и y принимают одинаковые истинностные значения, в остальных случаях – ложно.

-- эквиваленция (тогда и только тогда)

x	y

Операции над высказываниями называют сентенциональными связями. С их помощью из элементарных высказываний можно получать сложные булевы функции (формулы). Порядок выполнения операций указывается скобками. Для упрощения записи принят ряд соглашений:

n для отрицания скобки опускаются ;

n имеет приоритет перед ;

n имеет приоритет .

Любая булева функция определяется своей таблицей истинности.

Пример: определим таблицу истинности булевой функции .

x	y

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

Пример: -- формула для исключения импликаций

Для установления равносильности формул, нужно составить таблицу истинности для левой и правой частей. Если истинностные значения совпадают, то формулы равносильны.

x	y

В алгебре высказываний имеют место следующие основные равносильности:

Замечание: заменив в формулах множества на высказывания, , получим, что законы алгебры множеств перейдут в законы алгебры высказываний; т.е. две алгебры отличаются лишь по форме входящих в них элементов. Алгебраически они неразличимы (изоморфны).

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

т.и.(т.л) – тавтологии – 1(0)

Любая тавтология выражает собой некоторый логический закон.

Пример: -- закон отделения

x	y

Число булевых функций от n переменных равно .

Пример: если n=1, то ;

Если n=2, то . Все они указаны в таблице:

У некоторых из этих функций есть специальные названия.

-- тождественный нуль.

-- конъюнкция. Часто знак не пишут ( )

-- сложение по модулю 2.

-- дизъюнкция.

-- стрелка Пирса.

-- эквивалентность.

-- импликация.

-- штрих Шеффера.

-- тождественная единица.

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

Задачи.

1. Предположим, что высказываниям x, y, z и t соответствуют значения 1, 0, 0 и 1. Найти истинностные значения каждого из следующих высказываний:

a) ;

b) ;

c) ;

d) .

2. Пусть значение высказывания

a) истинно;

b) ложно.

Что можно сказать о значениях высказываний и ?

3. С помощью таблицы истинности доказать формулы:

а) -- исключение импликации;

b) -- исключение эквивалентности: .

4. С помощью таблицы истинности доказать законы:

a) -- закон силлогизма;

b) -- закон отделения;

c) -- закон контрапозиции.

2.2. Логика предикатов.

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

Пример: P(x)= «x – простое число» -- одноместный предикат, P(2)= «2 – простое число» -- истинное высказывание(1), P(4)= «4 – простое число» -- ложное высказывание(0).

Q(x,y)= « » -- двухместный предикат, Q(1,2)= «1>2; » -- ложное высказывание(0), Q(2,1)= «2>1; 2,1 » -- истинное высказывание(1).

Замена части предикатных неизвестных обращает его в предикат меньшей местности. Замена вех переменных – в высказывание. Высказывание при этом является 0-местным предикатом.

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

По аналогии с высказываниями, к предикатам применяются операции отрицания, дизъюнкции, конъюнкции, импликации и эквивалентности. Указанные операции обращают предикат в предикат.

Есть возможность обратить предикат в высказывание с помощью так называемых кванторов общности и существования:

(для всех x) – квантор общности;

(существует такое значение x) – квантор существования.

Пример: P(x)= «x – простое число» -- одноместный предикат,

P(x) – истинное высказывание,

P(x) – ложное высказывание.

Если все предикатные переменные связаны кванторами, то предикат обращается в высказывание, если часть, то в предикат меньшей местности. Операция приписывания к предикату квантора называется навешиванием квантора. Переменная, к которой относится квантор, называется связанной, без квантора – свободной.

Пример: P(x,y,z)= « » -- трехместный предикат,

-- двухместный предикат,

-- одноместный предикат,

-- истинное высказывание.

Задачи.

1. Определить, чему равны значения предиката Р(x)= «x – четное число» при x=23 и x=48.
2. Применить кванторы общности и существования к предикату примера 1 и найти значения полученных высказываний.
3. Навесить квантор общности на все переменные предиката P(x,y)= «x делится на y без остатка» и определить значение высказывания.
4. Навесить квантор существования на все переменные предиката P(x,y)= «x делится на y без остатка» и определить значение высказывания.

2.3. Решение логических задач с помощью булевых функций.

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

Пример: Сергей, Анна, Юрий и Ольга заняли на математической олимпиаде четыре первых места. На вопрос о распределении мест, одноклассники ответили следующее: 1) Анна – первая, Ольга – вторая; 2) Анна – вторая, Сергей – третий; 3) Юрий – второй, Сергей – четвертый. В каждом из ответов только одно утверждение истинно. Определим, как распределились места.

Пусть -- простые высказывания, где X – первая буква имени участника. Y – номер занятого места. Тогда высказывания можно записать: 1) ; 2) ; 3) .

Так как все дизъюнкции истинны, то истинной будет и конъюнкция этих дизъюнкций, т.е.

( )( )( )=1;

=1;

=0, т.к. Анна не может занимать два места;

=0, т.к. Ольга и Анна не могут обе быть на втором месте.

Тогда равенство примет вид: =1;

=1;

=1.

Следовательно, Анна заняла первое место, Сергей – второе, Юрий – третье, тогда Ольга – четвертое.

Задачи.

1. Записать символически следующие сложные предложения:

а) идет дождь или кто-то не выключил душ;

b) если вечером будет дождь, то Олег или останется дома, или должен будет взять такси;

c) если я устал или голоден, я не могу заниматься;

d) хлеба уцелеют тогда и только тогда, когда будут вырыты ирригационные канавы; если хлеба не уцелеют, то фермеры обанкротятся и оставят фермы.

2. Пусть даны высказывания: c= «сегодня ясно», r= «сегодня идет дождь», s= «сегодня идет снег», y= «вчера было пасмурно». Перевести на обычный язык следующие сложные высказывания:

a) ;

b) ;

c) .

3. Исследовать справедливость следующих рассуждений.

(а) Я пойду домой или останусь в университете и сдам долги. Я не пойду домой. Следовательно, я останусь и сдам.

(b) Заработная плата возрастет только, если будет инфляция. Если будет инфляция, то увеличится стоимость жизни. Заработная плата возрастет. Следовательно, увеличится стоимость жизни.

(с) Преподаватель или переутомился, или болен. Если он переутомился, то он раздражается. Он не раздражается. Следовательно, он болен.

(d) Если я пойду завтра на первое занятие, то должен буду встать рано, а если я пойду вечером на танцы, то лягу спать поздно. Если я лягу спать поздно, а встану рано, то я буду вынужден довольствоваться пятью часами сна. Я просто не в состоянии обойтись пятью часами сна. Следовательно, я должен или пропустить завтра первое занятие, или не ходить на танцы.

(e) Объем фонда музея возрастет только, если в него будут поступления из личных коллекций граждан. Если будут поступления, то увеличится число выставок. Объем фонда возрастет. Следовательно, увеличится число выставок.

(f) Встретились скульптор Белов, скрипач Чернов и художник Рыжов. «Замечательно, что один из нас имеет белые, один черные и один рыжие волосы, но ни у одного нет волос того цвета, на который указывает его фамилия», -- заметил черноволосый. «Ты прав», -- сказал Белов. Определить, какой цвет волос у художника.

Глава 3. Комбинаторика.

Часто приходится составлять из конечного числа элементов различные комбинации и производить подсчет числа всех возможных комбинаций, составленных по некоторому правилу. Например: -- сколькими способами можно расположить людей в очереди?; -- сколькими способами возможно распределение мест на чемпионате среди десяти команд?; -- сколько существует вариантов составления расписания?; и т.д. Такие задачи получили название комбинаторных, а раздел математики, занимающийся их решением, называется комбинаторикой. В комбинаторике имеют дело только с конечными множествами.

3.1.Общие правила комбинаторики.

Рассмотрим правило суммы.

Если некоторый элемент из одного множества можно выбрать n способами, а из другого -- m способами, то существует m+n способов выбора данного объекта из двух множеств.

Пример: Есть возможность добраться из пункта А в пункт В либо самолетом (три рейса в день), либо поездом (два рейса в день). Сколько существует вариантов отправления человека из пункта А в пункт В?

3+2=5 – вариантов. Это и есть правило суммы для непересекающихся множеств.

Если множества пересекаются, то число способов выбора объекта будет m+n-k, где k – элементы, лежащие одновременно в двух множествах.

Пример: Из двух магазинов нужно выбрать один товар. В первом магазине 5 видов подходящего товара, во втором – 10, причем среди 5-ти и 10-ти видов 3 одинаковых. Сколько существует способов выбора подходящего товара?

5+10-3=12 – способов.

Правило умножения.

Пример: Нужно добраться из пункта А в пункт С через пункт В. Из пункта А в пункт В ведут три дороги; из пункта В в пункт С – четыре. Найти все варианты маршрутов следования А–В--С.

3 4=12 вариантов.

В общем виде: если требуется поэтапно выполнить какое-либо действие, причем, первый этап можно осуществить способами, второй -- способами, и т.д., k-й -- способами, то это действие можно осуществить способами. В этом заключается правило произведения.

Известно, что наименьшей расчетной единицей памяти ЭВМ является байт, состоящий из восьми бит – ячеек, в каждую из которых может быть помещены 1 или 0. Набор единиц и нулей может быть различным и в каждом отдельном случае составляет комбинацию. Для нахождения всех возможных комбинаций используется правило умножения. В первой ячейке возможны два варианта – 1 или 0. Каждому из вариантов первой ячейки соответствуют два варианта второй ячейки, т.е. . Продолжая далее, можно посчитать количество всех возможных комбинаций заполнения ячеек единицами и нулями: .

3.2.Перестановки.

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

Перестановки можно образовывать из элементов любого конечного множества.

Множество из одного элемента можно упорядочить одним-единственным образом. Множество из двух элементов А и Б – двумя способами: АБ и БА.

Множество из трех элементов: А, Б, В – шестью способами: АБВ, АВБ, БАВ, БВА, ВАБ, ВБА.

Установленный в конечном множестве порядок элементов называют перестановкой.

Число перестановок из n элементов обозначают через . Мы нашли, что

Вычислять удобно последовательно, пользуясь рекуррентной формулой:

. (1)

Докажем ее. Пусть требуется упорядочить множество из n элементов. Какой-то из этих элементов придется поставить на последнее, n-е место. Этот элемент можно выбрать n различными способами. Если он уже выбран, то останется n-1 элемент. Ими придется занять первые n-1 мест. Это можно сделать способами ( по смыслу ). Всего получается способов упорядочить множество из n элементов, т.е. .

По формуле (1) последовательно получаем:

Например, 7 гостей можно рассадить по 7 местам за столом 5040 способами.

Из формулы (1) вытекает, что (число перестановок из n элементов) равно произведению первых n натуральных чисел:

. (2)

Для произведения первых n натуральных чисел принято специальное обозначение: n! (читается «n-факториал»). Пользуясь этим обозначением, формулу (2) можно записать в виде

n! (3)

Для дальнейшего удобно считать, что пустое множество можно упорядочить только одним способом, т.е. . Тогда формулой (1) можно пользоваться и при n=1:

.

Пример: Сколькими способами можно составить список из 9 студентов?

=362880.

Формула (3) применима для подсчета числа перестановок элементов множеств, т.е. когда элементы совокупности различные. Если же некоторые объекты в перестановках повторяются, то применяется формула для числа перестановок с повторениями.

Число перестановок элементов из такой совокупности будет меньше, чем из множества, где число элементов то же.

Пример: все перестановки для набора чисел (5,1,5): 515, 551, 155; все перестановки для набора чисел (5,1,2): 512, 521, 125, 152, 215, 251. В первом и втором наборах по три элемента, но там, где элементы повторяются, число перестановок меньше. Следовательно, число перестановок зависит от количества повторяющихся элементов.

В общем виде задача формулируется так: имеется n элементов, которые разбиты на k различных групп с одинаковыми элементами в первой группе, одинаковыми элементами во второй группе и одинаковыми элементами в последней, k-й группе. Сколько различных перестановок из n элементов, разбитых на k групп можно составить?

Теорема. Число различных перестановок с повторениями определяется по формуле:

. (4)

Пример: разобьем набор чисел предыдущего примера (5,1,5) на группы: =2 – количество 5-ок и =1 – количество 1-ниц. Тогда по формуле (4): =3.

Задачи.

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

2. Сколькими способами можно составить список из 9 студентов?

3. В пассажирском поезде 14 вагонов. Сколькими способами можно распределить по вагонам 14 проводников, если за каждым вагоном закрепляется один проводник?

4. Найти значение выражения:

а) 8! +9!; б) ; в) .

5.Сократить дробь:

а) ; б) ; в) .

6. Из цифр 0,1,2,3 составлены всевозможные четырехзначные числа так, что в каждом числе нет одинаковых цифр. Сколько получилось чисел?

7. Из цифр 1,2,3,4,5 составлены всевозможные пятизначные числа без повторения цифр. Выясните, сколько среди этих пятизначных чисел таких, которые:

а) начинаются цифрой 3;

б) не начинаются с цифры 5;

в) начинаются с 54;

г) не начинаются с 543.

8. Определить, сколько различных слов можно составить из слова «литература».

3.3.Размещения.

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

Пример. Дано множество .

Подмножества -- это различные упорядоченные множества.

Каждое упорядоченное подмножество из m элементов множества из n элементов называется размещением из n элементов по m элементов -- («A из n по m»).

Теорема. Число размещений элементов множества определяется по формуле: .

Для доказательства данной формулы воспользуемся следующими рассуждениями: на первое место упорядоченного множества из m элементов можно поставить один из n элементов (таких вариантов n), на второе – один из (n-1) элементов (таких вариантов (n-1)). Итого n(n-1), т.к. каждому из n соответствует один из (n-1). Продолжая далее, на m место можно поставить один из (n-m+1). Получаем: .

Пример: Сколько различных размещений по 3 элемента из элементов множества можно составить?

.

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

Теорема. Число размещений из n элементов множества по m с повторениями равно .

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

Пример:Сколькими способами можно распределить 3 различных предмета между 5 лицами?

=125.

Задачи.

1. Доказать, что .

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

3. В группе 15 студентов. Они обменялись друг с другом фотокарточками. Сколько всего было роздано фотокарточек?

4. Найти n, если .

5. Какая часть из семизначных телефонных номеров состоит из семи различных цифр?

6. В однокруговом турнире по футболу участвуют 8 команд. Сколько существует вариантов призовой тройки?

7. Студенты первого курса изучают 15 предметов. Сколькими способами можно составить расписание на среду, если известно, что в этот день должно быть 6 пар?

8. Сколько различных слов из 3 букв можно составить из 33 букв алфавита?

9. Сколько существует вариантов назначения 5 исполнителей на выполнение 5 видов работ?

3.4. Сочетания.

Пример: Рассмотрим все подмножества множества . Их восемь:

-- пустое множество;

-- три множества по одному элементу в каждом;

-- три множества по два элемента в каждом;

-- одно множество из трех элементов.

Число подмножеств по m элементов в каждом, содержащихся в множестве из n элементов, обозначается . В комбинаторике конечные множества называются сочетаниями. Поэтому называют «числом сочетаний из n по m».

Из примера видно, что и

.

Если число элементов множества большое, то процесс выписки всех подмножеств сложен. В этом случае число подмножеств определяется по формуле P(A)= . Выведем ее.

Перенумеровав все элементы множества А из примера, поставим в соответствие каждому подмножеству комбинацию 0 и 1, где присутствие элемента означает 1, отсутствие – 0. Т.е. -- 0,0,0;

-- 1,0,0;

-- 0,1,0 и т.д.

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

Чтобы вывести формулу для , докажем сначала, что .

Рассмотрим случай при m=2 и n=3. =3 – число множеств по две буквы в каждом. Каждое из них можно упорядочить способами, что дает упорядоченных множеств. Действительно, .

Общее доказательство аналогично. Чтобы образовать упорядоченное множество, содержащее m элементов из данных n, надо:

-- выделить какие-либо m из этих n элементов, что можно сделать способами;

-- упорядочить выделенные m элементы, что можно сделать способами.

Всего получим способов (упорядоченных множеств), т.е.