МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«УЛЬЯНОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»
В. А. Алексеева
ТЕОРИЯ ГРАФОВ
И МАТЕМАТИЧЕСКАЯ ЛОГИКА.
ПРАКТИКУМ
Учебное пособие
для студентов, обучающихся по направлению 231300.62
Ульяновск
УлГТУ
2014

УДК 519.17 + 510.6(075)
ББК 22.176 + 22.12я7
А47
Рецензенты:	1)	кафедра	«Телекоммуникационные
технологии и сети» УлГУ (зав. кафедрой д-р техн. наук,
профессор А. А. Смагин),
2)	зав. кафедрой «Информационная
безопасность и теория управления» УлГУ, д-р физ.-мат. наук,
профессор А. С. Андреев
Утверждено	редакционно-издательским	советом
университета в качестве учебного пособия
Алексеева, В. А.
А47	Теория графов и математическая логика. Практикум : учебное
пособие / В. А. Алексеева. - Ульяновск : УлГТУ, 2014. - 127 с.
ISBN 978-5-9795-1233-4
Содержит основные сведения по следующим разделам дискретной
математики:	теория	множеств, комбинаторика, теория	графов,
математическая логика. Представлены примеры решения задач, которые
могут быть использованы для подготовки и выполнения контрольных и
практических заданий по курсу «Теория графов и математическая логика».
Приведено много упражнений для самостоятельного выполнения.
Пособие предназначено для студентов, обучающихся по
направлению 231300.62, дневной формы обучения.
УДК 519.17 + 510.6(075)
ББК 22.176 + 22.12я7
ISBN 978-5-9795-1233-4
© Алексеева В. А., 2014
© Оформление. УлГТУ, 2014

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ	 5
ЧАСТЬ I. ТЕОРИЯ МНОЖЕСТВ	11
1.	Основные понятия теории множеств	11
2.	Основные операции над множествами и их графическое
представление	12
3.	Основные тождества алгебры множеств	16
4.	Мощность множества	17
5.	Отношения	17
6.	Задания для самостоятельного выполнения	20
ЧАСТЬ II. КОМБИНАТОРИКА	36
1.	Основные понятия комбинаторного анализа	36
1.1.	Основные правила комбинаторики	36
1.2.	Понятие выборки	39
1.3.	Размещения без повторений	40
1.4.	Перестановки без повторений	41
1.5.	Сочетания без повторений. Бином Ньютона и
биномиальные коэффициенты	42
1.6.	Разбиение множества на несколько частей.
Полиномиальные коэффициенты	43
1.7.	Размещения с повторениями	45
1.8.	Сочетания с повторениями	45
2.	Главная теорема комбинаторики (теорема о включениях и
исключениях)	46
2.1.	Теорема о включениях и исключениях	46
2.2.	Задача о смещениях	48
2.3.	«Задача о караване»	49
3

2.4.	«Решето Эратосфена»	50
2.5.	Разбиение множества на два подмножества	51
2.6.	Задачи на разбиения	52
2.7.	Формула Стирлинга	52
3.	Производящие функции	53
4.	Задания для самостоятельного выполнения	55
ЧАСТЬ III. ТЕОРИЯ ГРАФОВ	86
1.	Основные понятия теории графов	86
2.	Операции над графами	90
3.	Способы задания графов	91
4.	Задания для самостоятельного выполнения	94
ЧАСТЬ IV. МАТЕМАТИЧЕСКАЯ ЛОГИКА	111
1.	Функции алгебры логики (ФАЛ) или булевы
функции (БФ)	111
1.1.	Задание булевой функции	111
1.2.	Элементарные булевы функции. Логические операции .... 112
1.3.	Свойства логических операций	114
2.	СКНФ и СДНФ	115
3.	Полные системы	117
4.	Замкнутые системы и классы	119
5.	ДНФ и проблема минимизации БФ	121
6.	Задания для самостоятельного выполнения	123
БИБЛИОГРАФИЧЕСКИЙ СПИСОК	127
4

ВВЕДЕНИЕ
Одной из базовых дисциплин в программе подготовки
бакалавров по направлению 231300.62 «Прикладная математика»
является дисциплина «Теория графов и математическая логика»,
содержание которой определяется выпиской из федерального
государственного образовательного стандарта высшего
профессионального образования (ФГОС ВПО).
Выписка из ГОС ВПО
Код УЦ
ООП
Учебные циклы и проектируемые
результаты их освоения
Дисциплина
Б.2
Математический и
естественнонаучный циклы
Базовая часть
В результате изучения базовой
части цикла студент должен:
знать:
основные принципы перечисления
объектов; важнейшие системы чисел,
появляющиеся в комбинаторных
подсчетах; понятие производящей
функции последовательности; формулу
включения-исключения; методы реше¬
ния рекуррентных соотношений; основ¬
ные характеристики графов; специаль¬
ные цепи и циклы в графе; понятие
основного дерева в графе; методы
подсчета хроматического числа графа;
основные понятия формальной логики,
элементарной теории множеств (опера¬
ции над множествами и основные фак¬
ты, связанные с понятием мощности
множества), (булевой) логики высказы¬
ваний (включая вопросы полноты си¬
стем булевых функций), общей теории
формальных исчислений и, более
Теория гра¬
фов и матема¬
тическая ло¬
гика
5

Код УЦ
ООП
Учебные циклы и проектируемые
результаты их освоения
Дисциплина
подробно, (классического) исчисления
высказываний, а также (теоретико¬
множественной) логики предикатов и ее
взаимоотношение с (формальным)
исчислением предикатов;
уметь:
решать практические задачи, связанные
с построением конкретных ком¬
бинаторных конфигураций и с подсче¬
том их количества, строить производя¬
щие функции конкретных последова¬
тельностей и решать обратную задачу,
решать простейшие рекуррентные соот¬
ношения, находить количество решений
целочисленных линейных уравнений в
натуральных числах, строить граф по
его матрицам смежности или инциден-
ций и решать обратную задачу, строить
циклы специального вида в графе, нахо¬
дить хроматическое число и хроматиче¬
ский многочлен графа; применять мате¬
матический аппарат при решении типо¬
вых задач, а также обнаруживать приме¬
нимость аппарата математической логи¬
ки для решения задач из родственных
областей науки и ее приложений;
владеть:
аппаратом и методами теории графов и
комбинаторики для грамотной
математической постановки и анализа
конкретных задач, возникающих в про¬
фессиональной деятельности, способно¬
стью и готовностью к изучению даль¬
нейших понятий и теорий, разработан¬
ных в современной математической ло¬
гике, а также к оценке степени
6

Код УЦ
ООП
Учебные циклы и проектируемые
результаты их освоения
Дисциплина
адекватности предлагаемого аппарата к
решению прикладных задач.
Дисциплина «Теория графов и математическая логика»
включает в себя изучения ряда разделов дискретной математики.
Дискретная математика занимается изучением финитных
(конечных) свойств объектов (ограниченность, перечислимость),
которые возникают в различных разделах математики и в ее
технических приложениях. Хотя в целом границы, определяющие
дискретную математику, в значительной степени являются
условными, все же можно указать признак, позволяющий
достаточно четко разделить всю современную математику на две
составляющие. Суть этого признака заключена в самом названии
«дискретная математика», где дискретность выступает как
противоположность непрерывности, обозначающая отсутствие
понятия предельного перехода.
То, что в разделах дискретной математики рассматриваются
конечные свойства объектов, совсем не означает, что при
исследовании не встречаются бесконечные совокупности
объектов или их конфигураций, однако эти бесконечности
являются счетными. В то время как в непрерывной математике
бесконечности, как правило, континуальные.
К разделам дискретной математики обычно относят:
•	математическую логику,
•	булеву алгебру,
•	комбинаторику,
7

•	теорию конечных автоматов,
•	теорию графов,
•	теорию чисел,
•	теорию алгоритмов и еще много других разделов.
Учебное пособие состоит из четырех частей, в каждой из
которых рассматривается один из разделов дискретной
математики.
Первая часть посвящена изучению теории множеств.
Теория множеств — раздел математики, в котором изучаются
общие свойства множеств — совокупностей элементов
произвольной природы, обладающих каким-либо общим
свойством. Теория множеств стала основой многих разделов
математики — общей топологии, общей алгебры,
функционального анализа и оказала существенное влияние на
современное понимание предмета математики.
Вторая часть пособия предназначена для ознакомления с
комбинаторным анализом (комбинаторикой), изучающим
дискретные объекты, множества и отношения на них. Здесь вы
научитесь решать комбинаторные задачи, используя различные
модели комбинаторных конфигураций (сочетания, размещения,
перестановки и т. д.).
В третьей части пособия рассматривается теория графов -
раздел дискретной математики, изучающий свойства графов.
В настоящее время теория графов нашла широкое применение в
таких областях науки и техники, как химия (для описания
структур, путей сложных реакций); компьютерная химия —
сравнительно молодая область химии, основанная на применении
теории графов, информатика и программирование (граф-схема
8

алгоритма), коммуникационные и транспортные системы
(в частности, для маршрутизации данных в Интернете),
экономика, логистика, схемотехника.
Четвертый раздел - математическая логика. Она изучает
доказательства и вопросы оснований математики.
В пособии приводятся краткие сведения из
рассматриваемых разделов, примеры решения задач и задания
для самостоятельного выполнения. Задания для самостоятельного
выполнения содержат цель, требования, а также порядок
выполнения и перечень формируемых компетенций.
Кроме навыков и умений выполнение самостоятельных
работ позволит развить базовые и личностные компетенции.
Таким образом, имеется возможность оценивать результат
выполнения работ не только по критериям качества
самостоятельной работы, но	и в терминах	проявленных
личностных компетенций, таких как способность планировать
свою работу, способность самостоятельно решать стоящие
задачи, способность к самооценке. Такие	компетенции
развиваются в деятельности,	и в данном	пособии эта
деятельность представлена комплексом самостоятельных работ,
которые, как и в реальной жизни, ограничены по времени.
Временной параметр позволит оценить эффективность
деятельности по выполнению с позиции компетенций по
планированию, организации и ответственности.
Исходя из указанных	предпосылок,	предлагается
следующая схема оценки качества выполнения работ студентом:
развитие системных компетенций, развитие инструментальных
компетенций, развитие личностных компетенций. При оценке
9

развития системных компетенций оцениваются ответы на
контрольные вопросы, при оценке инструментальных
компетенций оцениваются структура, объем и содержание
выполненных работ. При оценке личностных компетенций
оцениваются время выполнения работ (способность к
планированию, организации, ответственность), качество
выполнения домашних заданий (стремление к качеству
результата, способность самостоятельно решать задачи,
самооценка).
Пособие подготовлено автором на базе собственного опыта
проведения занятий по дисциплинам «Дискретная математика» и
«Теория графов и математическая логика».
10

ЧАСТЬ I. ТЕОРИЯ МНОЖЕСТВ
1.	Основные понятия теории множеств
Множество - совокупность элементов, обладающих каким-
то одним общим свойством. (Это определение не является
строгим, оно лишь показывает особенности построения
множеств, т. е. для построения множества важно указать
свойство, которым обладают все его элементы).
Если каждому элементу множества можно присвоить номер
и этот номер не повторяется, то такое множество называется
счетным, или конечным.
Если такого номера для каждого элемента не существует, то
такое множество называется бесконечным. Бесконечное
множество часто называют континуумом (например:
совокупность точек на плоскости). Мощностью множества A
называется число его элементов (обозначается |a| или N(A)).
Запись a є A означает, что объект а есть элемент
множества A (принадлежит множеству A); в противном случае
пишут а € A. Множество, не содержащее ни одного элемента,
называется пустым и обозначается символом 0. Запись A с B
(A содержится в B) означает, что каждый элемент множества A
является элементом множества B; в этом случае множество A
называется подмножеством множества B. Множества A и B
называют равными (A = B), если A с B и B с A.
11

Множества задаются различными способами:
1.	С помощью перечисления всех его элементов, например,
{0,1,2,3,4,5,6,7,8,9}.
2.	Алгоритмическая форма (в виде последовательности или
формул): а) конечное
М={2;4;6;8} <=> М={т I 2n; n - целое; 1<=n<=4};
б) бесконечное
А={хІ Іх-1І<3}.
Пример 1. Описать перечислением элементов множество
Решение. А= {xє Z I (x -3)(x2 -1)= 0 и x > 0}.
А есть множество всех целых неотрицательных корней
уравнения (x - 3)(x2 -1)= 0. Следовательно, А = {1,3}.
2.	Основные операции над множествами и их графическое
представление
Представим основные операции над множествами в виде
таблицы (таблица 1).
Таблица 1
Основные операции над множествами
Основные операции над множествами
Диаграммы Венна
1. Включение
Множество А входит (включено) в множество
В, или А является подмножеством В. А с B .
Если всякий объект, обладающий свойством
а, также обладает свойством в, то говорят, что
свойство а включает свойство в, т. е. а с в .
©
12

Продолжение табл. 1
Основные операции над множествами
Диаграммы Венна
2. Сумма (объединение)
Сумма множеств А и В есть множество С,
включающее в себя все элементы множество А и В.
Объект входит во множество
C = А + B = А U B, если он входит во множество
А или во множество В.
C = A u B = [cilci е А или ci е B}.
т
3. Пересечение (произведение)
Пересечением множество А и В называется
новое множество С. Элементы множества С
принадлежат множеству А (обладают его
свойствами) и множеству В (обладают его
свойствами).
C = А * B = A n B = [ci l ci є А и ci є B}.
4. Вычитание (разность)
Разность множеств А и В есть множество С,
элементы которого обладают свойствами множества
А и не обладают свойствами множества В или
принадлежат множеству А и не принадлежат
множеству В.
C = А = [cilci е А и ci £ B}.
•э
5. Дополнение
Если имеется некоторое универсальное
множество (универсум) U и все рассматриваемые
множества есть его подмножества, то дополнением
А называется такое множество, элементы которого
не входят в А, но принадлежат U.
о
6. Прямое произведение А X В
Прямым произведением множеств А и В
называется множество М всех пар (а ■ b), таких, что
а е А и b е B.
Если А=В, то такое произведение называется
А2.
Аналогично можно вывести операцию прямого
произведения большего числа множеств.
13

Окончание табл. 1
Основные операции над множестами
Диаграммы Венна
А1 х А2 х...х А„
а х а2 х ...а„).
Если в частности А1 ,А1... Ап одинаковы
А п
А1 = А2 = ...Ап , то получаем А .
(Например, множество точек на плоскости
являются прямым произведением двух множеств).
Если множества конечные, мощность
произведений А х B равна мощности произведений
IА х b| = |a| ■ |b| .
Пример 2. В цехе предприятия работают 15 человек, из них
5 человек имеют дипломы наладчиков станков с ЧПУ, 10 имеют
дипломы слесарей и 6 - фрезеровщиков (III), 2 человека имеют
одновременно дипломы наладчиков станков с ЧПУ и слесарей, 3
человека имеют дипломы наладчика станков с ЧПУ и
фрезеровщика,	2 человека имеют дипломы слесаря и
фрезеровщика и 1 человек имеет все три вида дипломов. Сколько
работников цеха не имеют ни одного вида из этих трех
дипломов? Сколько работников цеха имеют ровно по два
диплома? Сколько работников цеха имеют только один из
дипломов?
Решение. Введем обозначения: А - множество человек с
дипломами наладчиков станков с ЧПУ, В - множество человек с
дипломами слесарей и С - множество человек с дипломами
фрезеровщика. Удобно представить задачу в виде следующей
диаграммы (рис. 1).
14

Мощность множества работников цеха |U | = 15. Мощность
объединения пар множеств |A u в| =5+10-2=13, |А и С| =5+6-3=8,
|в и С|=10+6-2=14.
Число работников цеха, не имеющих ни одного вида из этих
трех дипломов, определяется как IU(A u B и С)\ =
=15-5-10-6+2+3+2-1=0.
Число работников цеха, имеющих ровно по два диплома:
IA n B| +1A n С|+|B п С|-31A n B п С | =2+3+2-3=4.
Один диплом наладчика станков с ЧПУ имеют
IА|-1A n B| -1А п С|+1A n B п С| =5-2-3+1=1 работник.
Один диплом слесаря имеют
|в| -1A n B| - |B п С| +1A n B п С|=10-2-2+1=7 человек.
Один диплом фрезеровщика имеют
|СI -1А п С| - |B п С|+1A n B п С| =6-3-2+1=2 работника.
Итого, 1 диплом имеют 1+7+2= 10 человек.
15

3.	Основные тождества алгебры множеств
Независимость расположения:
A u B = B и А
А и B = B и А
Ассоциативность:
А и (B и С) = (А и B) и С
А п (в п С) = (A n B )п С
Дистрибутивность:
А и (B п С) = (А и B)п(А и С)
А п (в и С) = (A n B)и (А п С)
А и A = U
А п А = 0
А и 0 = А
A n U = А
А и А = А
А и U = U
Законы де Моргана
А и B = A n B
A n B = А и B
16

4.	Мощность множества
Теорема 1. Пусть А1, А2, ..., An - конечные множества и
IAt | = mt, тогда мощность множества А1 х А2 х...х Ап равна
произведению мощностей m1m2.mn.
Доказательство. Для п = 1 теорема очевидна. Пусть она
выполняется для некоторого п. Докажем методом
математической индукции, что она выполняется и для п+1.
Возьмем любой вектор (a1 ,a2,...,an), припишем справа an+1.
Число элементов увеличится в количество раз, равное мощности
множества Ап+1.
Теорема 2. Если для конечного множества А |А| =п, то
число всех подмножеств множества А равно 2п.
Пример 3. А = {a,b,c}. Определить число подмножеств
множества А.
Решение. Подмножества будут иметь вид: {0}, {a}, {b},{c}, {ab},
{ac}, {bc}, {abc}, т. е. всего 8 подмножеств.
5.	Отношения
п-местным отношением, или п-местным предикатом, P на
множествах А1, А2, ..., An называется любое подмножество
декартова произведения А1 х А2 х...х Ап . При п=1 отношение
называется унарным, при п=2 - бинарным. Для обозначения
бинарного отношения будем принимать знак R. Если требуется
17

указать, что (a,b)є R, т. е. между элементами a є А и b є B
существует отношение R, то пишут aRb.
Пример 4. А = {1,2,3}; B = {1,2,3,4,5,6}. Определить R.
Решение. Множество А х B содержит 18 упорядоченных пар.
Выделим на этом множестве отношение «больше»: a>b, где
a є А и b є B, тогда R = {(2,1), (3,1), (3,2)}, т. е. из 18 пар
множества А х B три пары принадлежат отношению aRb, где R
обозначает слово «больше». В этом случае справедливо равенство
aRb = {(2,1),(3,1),(3,2)}. Пусть R обозначает «меньше простого
числа». Тогда aRb = {(1,2), (1,3), (1,5), (2,3), (2,5), (3,5)}.
Бинарное отношение R между элементами a є А и b є А
называется симметричным, если при перестановке a и b
отношение сохраняется. Отношение называется асимметричным,
если оно имеет место между элементами a и b, но отсутствует
между элементами b и a. Отношение называется
несимметричным, если оно не является не симметричным, не
асимметричным, т. е. если имеет место отношение aRb, то
отношение bRa может быть, а может и не быть.
Отношение R называется транзитивным, если из aRb и bRc
следует aRс. Отношение называется интранзитивным, если из
aRb и bRc следует, что утверждение aRс является ложным.
Отношение называется нетранзитивным, если оно не является
транзитивным и не является интранзитивным, то есть если имеют
18

место отношения aRb и bRc, то утверждение aRс может быть и
истинным, и ложным.
Отношение R на множестве А называется рефлексивным,
если для всякого a є А утверждение aRа является истинным.
Отношение	называется	антирефлексивным	(или
иррефлексивным), если ни один элемент a є А не находится в
отношении R с самим собой.
Если отношение R на множестве А обладает свойствами
рефлексивности, симметричности и транзитивности, то оно
называется отношением эквивалентности.
Пример 5. Доказать, что на множестве N х N отношение Q
является	отношением	эквивалентности,	если
{(a, b), (c,d)} є Q ^ a + d = b + c.
Решение. Если отношение Q рефлексивно на множестве А,
то Vx є AxQx. В нашем случае x - пара (x,y). Тогда отношение
Q рефлексивно на множестве, если V(x,y)є Q {(x, y),(x, y)}є Q. По
условию задачи: a + d = b + c. То есть для нашего условия
рефлексивности получаем x + y = y + x. Данное равенство верно,
следовательно, Q рефлексивно.
Аналогично, если {(a, b), (c,d)} є Q, то и {(c, d ),(a,b)} є Q,
т. к. из a + d = b + c следует, c + b = d + a. Таким образом, Q
симметрично.
Если {(a,b),(c,d)}є Q, {(c,d),(e,f )}є Q, т. е. выполняются
равенства a + d = b + c и c + f = d + e, то сложив их, получаем
19

a + d + c + f = b + c + d + e ^ a + f = b + e, т. е. {(a,b), (e,f )}є Q.
Таким образом, Q транзитивно.
Если отношение R на множестве А является транзитивным и
асимметричным и не является рефлексивным, то оно называется
отношением строгого порядка. Если отношение R на множестве
А рефлексивно, антисимметрично и транзитивно, тот оно
называется отношением нестрогого порядка.
6.	Задания для самостоятельного выполнения
1.	Установить, какая из двух записей верна:
а)	{1,2}є {1,2,{1,2,3}} или {1,2} е {1,2,{1,2,3}};
б)	{1,2}є {1,2,{1,2}} или {1,2} е {1,2,{1,2}}.
2.	Задать	множество перечислением	всех	его	элементов
А= {x є	Rl x3 - 3x2 + 2x = 0}.
3.	Задать	множество перечислением	всех	его	элементов
A= j x є	R | x + — < 2 и x> 0 j.
4.	Задать	множество перечислением	всех	его	элементов
A = {x є	N ^2 - 3x - 4 < 0}.
5.	Задать	множество перечислением	всех	его	элементов
A = jx є Zl 4 < 2x < 5.
6.	Задать	множество перечислением	всех	его	элементов
A= -j x є N l log1/2 — < 2
20

7.	Задать множество перечислением всех его элементов
А = {xє Rl cos22x = 1 и 0 < x < 2п}.
8.	Изобразить	на	координатной	плоскости	множество
А = {(x, y) є R2 l x + y - 2 = 0}.
9.	Изобразить	на	координатной	плоскости	множество
А = {(x, y) є R2 l x2 - y2 > 0}.
10.	Изобразить	на	координатной	плоскости	множество
А = {(x, y) є R2 l (x2 -1)y + 2) = 0}.
11.	Изобразить	на	координатной	плоскости	множество
А = {(x, y) є R2 l y > V2x +1 и 2x + 1 > 0}.
12.	Изобразить	на	координатной	плоскости	множество
А = {(x, y) є R2 l y2 > 2x +1}.
13.	Изобразить	на	координатной	плоскости	множество
A= {(x, y) є R 2 l cos2x = cos2y}.
14.	Изобразить	на	координатной	плоскости	множество
A = <j (x, y) є R 2 l1 > — ,x ^ 0, y ^ 0
x
y
15.	Описать перечислением всех элементов множества
А и B, A n B, A \ B, B \ A,
A = {x є Rl x2 + x - 20 = 0} B = {x є Rl x2 - x +12 = 0}.
16.	Доказать, что:
а)	равенство A n B = B верно в том и только том случае,
когда B е А;
б)	равенство А и B = B верно в том и только том случае,
когда А е B.
21

17.	Пусть А = (-1,2] и B = [ 1,4). Найти множества А и B,
A n B, А \ B, B \ А и изобразить их на числовой оси.
Приняв отрезок T = [0,1] за универсальное множество, найти и
изобразить на числовой оси дополнения следующих множеств:
18.	{0,1}.
19.	(1/4,1/2).
20.	(0,1/2].
21.	{1/4} U [3/4,1).
22.	Доказать, что операция взятия дополнения обладает свой¬
ством рефлексивности (А = А), а также связана с отношением
включения е и операциями U и I следующими законами двой¬
ственности:
а)	если А е B, то А з B ;
б)	А и B = A n B и A n B = А и B .
23.	Доказать, что операции U и I связаны законами дистри¬
бутивности:
(А и B)n C= (A n C)и(в n C);
(A n B)и C= (А и C)n(B и C).
24.	Доказать равенство	А \ BI	(a U B ) =	А .
25.	Доказать равенство	А \ B =	AIB .
26.	Доказать равенство	А \ B =	A U B.
27.	Доказать равенство	AI (a \ B )=А IB.
Для заданных семейств множеств Ап,пє N, найти U Ап и I Ап ■
пє N	пє N
28.	Ап = {x є Z l -n < x	< n}.
29.	An = {3n - 2,3n -1}.
22

30.	Ап = к1,1,..., Л.
n j 2 3 n
Доказать, что следующие множества счетны:
31.	{n є Nln= 2k,k є N}.
32.	{n є Nln=k2,k є N}.
33.	{n є Nln= 2 k,k є N}.
34.	Множество А={1, 2, 5, 7, 8), B ={2,6, 9}. Найдите объеди¬
нение, пересечение и разности множеств.
35.	Множество А = {a, b, c,	d,	e), B = {p, q,	r, 5). Найдите объ¬
единение, пересечение и разности множеств.
36.	В группе 35 студентов, из них 21 знают английский, 15
знают немецкий, 8 знают и английский, и немецкий. Покажите
физический смысл объединения, пересечения, дополнения и раз¬
ности множеств.
37.	Имеются 3 множества: А = {1, 2, 3}, B = {a, d},
C = {A, B, C, D}.Найти мощность множества прямого произведе¬
ния ABC. Найти число подмножеств каждого множества и их
прямого произведения.
38.	Множество U = {1 - 100}. Множество P - все числа,
кратные 5, Q - все числа, кратные 7. Найдите пересечение мно¬
жеств, объединения, дополнения и разности множеств. Опреде¬
лите мощности всех множеств.
39.	Сколько разных слов длины, не превышающей 5, может
быть подано на вход цифрового устройства, если входной алфа¬
вит состоит из двух букв {0, 1}? Слово длины 0 - одно, длины 1 -
два (0 и 1), длины 2 - четыре, длины 3 - восемь, длины 4 - шест¬
надцать, длины 5 - тридцать два. Если к этой сумме прибавить 1,
23

получим 64. Всего на вход устройства может быть подано 26-1
разных слов. Найдите количество разных слов длины, не превы¬
шающей 7,8,9,10, п.
40.	Пусть А - множество простых чисел. Укажите номера
верных записей:
1)	1 є А; 2) 2 є А; 3) 0 є А; 4) 19 є А; 5) 23 є А.
41.	Сколько элементов в множествах:
а)	{a,b,c,aa,bc} в) {1,2,3,123,12}	д)	{11,22,11,12}
б)	{a,b,c,a,b,c} г) {111,22,2,33}	е)	{1,11,111,1}?
42.	Элементами множества S = {P,Q,R} являются:
P = {a,b,c};	Q = {1,2,3}; R = {11,12,13}.
Укажите верные записи:
а)	P є S; в) {a,b,c} є {P,Q,R};	д)	{1,2,3} є S;
б)	a є S; г) 11 gS;	е)	{P,Q} є S.
43.	Укажите элементы множеств.
1)	P = {xl x є {a,b,c}}.
2)	P = {xl x>4, x є {3,4,5,7,8}}.
3)	P = {xl x - натуральное число, x < 3}.
44.	Укажите верные равенства:
а)	{{1,2,3}} = {1,2,3};
б)	{1,2,3} = {{1,2},{3}};
в)	{0}	=	{x l x - целое неотрицательное число,
x - ненатуральное число};
г)	{1, 2, 3, 5, 7} = {х є А l х < 10, А - множество простых
чисел};
д)	{0, 2, 4, 6, 8} = {x l x < 9, x - неотрицательное четное число};
е)	{2,4} = {x l x - решение уравнения х - 6х+ 8 = 0};
ж)	{1,2} = {{1,2},{2}}.
24

45.	Укажите множества, равные множеству {2,4,6,8}:
а)	P = {x l x = 2n, n - натуральное число, n < 5};
б)	P = {x l x = 2n, n - неотрицательное целое число, n <5);
в)	P = {x l x = 2n + 2, n - неотрицательное целое число, n < 5};
г)	P = {x l x = 2(n+1), n - неотрицательное целое число, n < 3};
д)	P = {x l x = 2n + 2, n - натуральное число, n < 5};
е)	P = {x l x = 2n + 2, n - неотрицательное целое число, n<4}.
46. Дано множество вида А = {a, b, c, d}. Укажите верные за¬
писи:
2	вариант
а)	{a} е {a, b};
б)	{c} с {c};
в)	0є {a, b, c};
г)	0 е {a};
д)	A с {a, b, c, d};
е)	a, b с {a, b}.
47.	Некоторое множество имеет 62 собственных подмножест¬
ва. Найдите число элементов булеана этого множества.
48.	Дано множество P. Когда из него удалили три элемента,
получилось множество, булеан которого содержит 64 элемента.
Найдите lB(P)l.
49.	Булеан некоторого множества P содержит 256 элементов.
Найдите число собственных подмножеств множества P.
50.	Дано три множества A, B, C. Известно, что a є А. Укажите
все верные утверждения:
а)	a е B;
б)	a є А и B;
в)	a е B и C;
1 вариант
а)	a є А;
б)	d е А;
в)	0 є А;
г)	{ a, b, c, d} с A;
д)	0 е A;
е)	{a, b} е {a, b, c}.
3 вариант
а) a, b є { a, b, c};
б)	0g {a, b, c};
в)	0є{0};
г)	0 е {0};
д)	a = {a};
е)	0 = {0}.
25

г)	a є А и B и C;
д)	{a} с А;
е)	Йє B;
ж)	{a} с А и B;
з)	Йє B и C;
и)	{a} с А и B и C.
51.	Найдите элементы множества АI В, если:
1)	A={b, c, d}, B={c,d,e};
2)	A= {1, 3, 4, 5}, B={4, 7, 8};
3)	A = {1,2,3,4}, B= {2,3};
4)	A = {март, апрель, май}, B = {май, июнь}.
52.	Найдите элементы множества PIQ, если:
1)	P = {x l x< 12, x - натуральное число},
Q = {x l x > 10, x - натуральное число};
2)	P = {x l x < 12, x - натуральное число},
Q = {x l x > 10, x - натуральное число};
3)	P = {x l x - натуральное простое число},
Q = {x l x - четное натуральное число}.
53.	Найдите элементы множества A U BIC, если
1)	А= {0,1,2,3}, В = {x l x < 10, x — натуральное число},
С = {x l x > 8, x — натуральное число};
2)	A = {b, c}, B = {a, b, c}, C = {a, b, c, d};
3)	A = B = C= {b,c,d}.
54.	Укажите верные выражения:
а)	(А и B) n (А и C) = А и (B n C);
б)	(В и C)n A = A n B и A n C;
в)	A n В = В n A;
26

г)	(А и В)п (А и C) = А п (В и C);
д)	А п В и A n C = А и В n C;
е)	А п(В и C) = А и В n C.
55.	Укажите номера верных выражений:
1)	А п А п( А и В ) = А и А п В и А п В n C;
2)	(А и В)п0 = 0;
3)	0и А п В = 0 п( А и В) и 0 n C;
4)	(A n U) и В = А и В;
5)	А п 0 и В = В;
6)	А п0п В = А п В.
56.	Пусть U = {1, 2, 3, 4, 5, 6}. Укажите элементы, входящие в
множество А, если:
1) А = {3,4};	3) А = {1,2,3,4,5};
2) А = {1,2,3,4,5,6};	4) А = 0.
57.	Найдите элементы множества А, если А - множество всех
простых чисел, не превышающих 7, U= {0, 1,2, ...,9}.
58.	Найдите l A l, если U = {1, 2, 3, ..., 30}; А = {xlx < 20, x —
простое число}.
59.	Даны множества: А = {1,2,3}; В = {2,3,4}; U = {1,2,3,4,5,6}.
Найдите элементы следующих аналитически заданных множеств,
применяя к ним теорему де Моргана:
1)	А и В;
2)	А и В;
3)	А п В;
4)	А п В;
5)	А п В;
6)	А и В.
27

60.	Упростите выражения, если А е В:
1)	А и В;
2)	А и В.
У	9
3)	А п В;
4)	А п В;
5)	А и В;
6)	А и В.
61.	Найдите элементы множества А -В, если А ={3, 4, 6, 7};
В ={6, 7, 8}.
62.	Найдите элементы множества А и В, если А - В = {2, 4, 5};
В = {6, 7, 8}.
63. Дано: А= {0,1,2,3,5,6}; В= {3,4,6,7,9}; C={0, 5, 6, 7, 8};
U= {0, 1,2	9}.
Найдите элементы множеств:
1)	А-(В и C);	4)	А-(В n C);
2)	В-(A n C);	5)	C-(А п В);
3)	А-(В - C);	6)	(А и В )-(А п В).
64.	Упростите выражения:
1)	А п В n C и А п В;
2)	А п В n D и D ;
3)	А п В n C и А ;
4)	А п В n C и В;
5)	А п В n C и A n C;
6)	А п В n C n D и C .
65.	Дано: А = {1,2,3,4,5}; В = {2,3,4,5,6}; C = {2,3,6,7};
D = {2,5,6,7,8}; U = {0,1,2,.. .,9}. Найдите элементы множеств:
28

1)	А п В n C и A n C;
2)	В n C и C и A n C ;
3)	A n C и A n В n C и A n C n D.
66.	Найдите элементы множества:
A n В n C и A n C n D и A n C и A n В n C n D,
если A = {1,2,4,6,8}; В = {2,3,6}; C = {2,4,6,7}; D = {4,5,7}.
67.	Найдите элементы множества A n В n C и A n В и В,
где А = {1,3,5,7}; В = {4,5,6,7}; C = {1,2}.
68.	Упростите выражения:
1)	А п В n C и А п В n C ; 3) А п В и А п В n C и А п В ;
2)	А п В n C и А п В n C; 4) А п В n C и А п В n C и А п В .
69.	Найдите элементы множеств:
1)	А п В n C и В n C и В n C и В n C ,
2)	(А и В и C)п (А и В и C),
3)	(А п В и C)п (А п В и C),
4)	(А и В и C)п(А и В и C)п В,
если А = {1,2,4,5}; В = {1,3,6,7}; C = {2,3,6,7}.
70.	Упростите выражения, если C - универсальное множество,
D = 0.
1)	(А и B)n(C и D);	4)	A n C и В n C и A n D;
2)	А п В n C и В n C n D;	5)	АП (В U C U D) П В П C;
3) (А и В и C)n(C и D);	6) (А п В и C)п(В и D).
71.	Чему равны выражения, если принять В = C = 0 ?
1)	А и В и C и D;	4) В n C и A n D ;
2)	А п В n C n D ;	5) (А и В)n(C и D);
3)	А и В и D;	6) (А и В)п(В и C).
29

72.	Даны множества: А = {1,2,3}; В = {1,2}; C = {3,4,5};
U = {1,2,3,4,5,6}. Укажите номера пустых множеств:
1	вариант	2	вариант
1)	А п В n C ;	1) А п В n C;
2)	А п В n C;	2) А п В n C;
3)	А п В n C ;	3) А п В и В n C;
4)	А п В n C;	4) В n C и А п В	n C
3	вариант
1)	(А и В )n C ;
2)	(В и C)п (А и C);
3)	(А и В) n A n C;
4)	А п В и В n C;
5)	А п В n C ;
6)	А п В n C.
5)	А п В n C и А п В n C ; 5) (А и В)п(а и В);
6)	А и В и C.
6)	А и В и C п А.
73. Найдите элементы множества (А х В )п(В х А), если
А = {a, b}; В = {b, c}.
74. Найдите А х В и |(А х В)п(В х А), если А = { a, b, c};
В = {b, c}.
75. Найдите	элементы	множеств А	и В,	если
А х В = {(b, m), (c, m), (e, m), (b, n), (c, n), (e, n)}.
76.	Доказать равенства:
а)	A \ (A \ В) = A n В;
б)	(A \ B)\C = A\(B и C);
в)	(A \ B) n C = (A n C)\(B n C).
77.	Доказать включения:
а)	А и (В\ C) з (Аи В)\C;
б)	(А и C) \ В е (А \ В) и C.
78.	Пусть А е U, В е U. Найти множество X е U, удовле¬
творяющее уравнению (X и А) и(х и а) = В.
30

j A n X =0,
79. Доказать, что система уравнений jB п x = 0 имеет реше¬
ние тогда и только тогда, когда В с А , при этом условии реше¬
нием системы является любое множество Х такое, что
В с X с А.
80.	Пусть А = {a,b,c}, В = {l,2,3,4}, P1 с А х В, Р2 с В2.
Изобразить Р1 и Р2 графически, найти (Р1 о Р2 )-1 . Проверить с
помощью матрицы |Р2|, является ли отношение Р2 рефлексив¬
ным, симметричным, антисимметричным, транзитивным.
Р ={( a, 2), (a,3), (a, 4), (b,3), (c,1), (c,4)},
Р2 ={(1,1), (2,3), (2,2), (3,4), (1,4), (2,4), (4,2)};
а)
б)
Р ={( b, 2), (a,3), (b,1), (b,4), (c,1) ,(c,2) (c,4)},
Р, ={(1,1), (1,2), (1,4), (2,2), (2,4), (3,3), (3,2), (3,4), (4,4)}.
81.	Найдите lRl, если R определено следующим образом:
x делит у (без остатка); x є А; у є В, где А = {1, 2, 3, 4, 5};
В = {6, 7, 8, 9, 10, 11, 12}.
82.	Определите laRbl для множеств А = {1, 2, 3, 4, 5};
В = {6, 7, 8, 9, 10, 11, 12}, если R - это отношение: a є А - простое
число; b є А и В - четное или простое число.
83.	Укажите симметричные отношения:
1)	Таня — сестра Пети;
2)	прямая А перпендикулярна прямой В;
3)	город Томск расположен севернее города Новосибирска;
4)	тетрадь находится в портфеле;
5)	Зина — сестра Оли;
31

6)	25 + 10 = 15 + 20;
7)	прямая A параллельна прямой B.
84.	Укажите асимметричные отношения:
1)	я встретился со своим другом;
2)	Иван пришел в гости к своему другу Петру;
3)	дерево свалилось на дорогу;
4)	Иванов проиграл в шахматы Петрову;
5)	Андрей уважает Сергея;
6)	Останкинская башня выше Эйфелевой башни;
7)	Сидоров хорошо относится к Петрову;
8)	Петров поприветствовал Иванова.
85.	Укажите несимметричные отношения:
1)	Иван узнал Петра;
2)	лесоруб спилил дерево;
3)	столяр изготовил оконную раму;
4)	Иванов поздоровался с Орловым;
5)	олень увидел в зарослях тигра;
6)	число а не больше числа b, где a, b е {1,2,3, .. .,9};
7)	число 325 содержит столько же цифр, что и число 891.
86.	Укажите транзитивные отношения:
1)	равно;	5) меньше на 5;
2)	больше или равно;	6) быть южнее;
3)	не равно;	7) быть врагом;
4)	быть другом;	8) быть логарифмом.
87.	Укажите интранзитивные и нетранзитивные отношения:
1)	квадратный корень;	5) равно половине;
2)	старше, чем;	6) является предком;
3)	больше в три раза;	7) является матерью;
32

4)	дружит;	8) здоровается.
88.	Укажите рефлексивные отношения:
1)	Таня - сестра Зины;
2)	а < b, где а и b - натуральные числа;
3)	а Ф b, где а и b - натуральные числа;
4)	треугольник а подобен треугольнику b;
5)	площадь круга а больше площади круга b;
6)	Иван написал письмо Петру;
7)	выражения а и b имеют одно и то же значение в множестве
числовых выражений.
89.	Укажите отношения эквивалентности:
1)	быть попутчиком в одном вагоне;
2)	а + b= 100,где а, b є {1,2, ..., 100};
3)	а = b, где а, b є {1,4,8,9};
4)	прямая а перпендикулярна прямой b;
5)	треугольник а подобен треугольнику b;
6)	Сидоров живет двумя этажами выше Михайлова;
7)	а сердит на b.
8)	Иванов задал вопрос Петрову;
9)	книга а имеет такую же цену, что и книга b;
10)	Смирнов попрощался с Федоровым;
11)	Саша позвал в гости Игоря;
12)	Павлов и Васильев смотрят один и тот же фильм;
13)	высота горы а равна высоте горы b;
14)	Ухин и Орлов окончили вуз в одном и том же году;
15)	солдат Петров идет в ногу с солдатом Ивановым в одном и
том же отряде;
16)	Смирнов позвонил на работу Чичикову;
33

17)	Павлов встретил своего друга Васильева;
18) автомобиль «Москвич» едет по той же дороге, что и
автомобиль «Жигули»;
19)	автомобиль a столкнулся с автомобилем b;
20)	Иванов прочитал книгу, написанную Соколовым.
90.	Укажите отношения строгого порядка:
1)	Иванов выше Сидорова;
2)	Лена - сестра Наташи;
3)	отрезок a короче отрезка b;
4)	отрезок a длиннее отрезка b на 2 см;
5)	Васильев знает Петрова;
6)	Иванов живет этажом выше Соколова;
7)	лыжник Ухин бежит непосредственно за Ивиным;
8)	число	a непосредственно	следует	за	числом	b,
где b є {1,2, ..., 10};
9)	число a на 4 больше числа b, где a, b є {1,2,., 10};
10)	между	числами	a	и b находится точно	одно число
a, b є {1,2, ..., 10};
11)	число a равно числу b, где a, b є {1, 2, ., 10};
12)	число a следует за числом b, где a, b є {1, 2,., 10};
13)	число a больше в два раза числа b, где a,b є {1, 2, ...,20);
14)	Саша старше Димы.
91.	Укажите отношения нестрогого порядка:
1)	автомобиль a едет быстрее автомобиля b;
2)	число a не меньше числа b, где a, b є {1, 2, ., 50};
3)	натуральные числа a и b не равны числу 6;
4)	число	a без	остатка	делится	на	число	b,
где a, b є {1,2,3,4,5,6};
34

5)	a>5 и Ь>5,гдє a,b є {1,2,	,8};
6)	Петров и Иванов - друзья;
7)	угол а не больше угла в;
8)	числа a и b не являются двузначными;
9)	точка a на числовой оси находится левее точки b;
10)	самолет a летит не быстрее самолета b;
11)	расстояние между городами равно 100 км;
12)	дом a не выше дома b;
13)	отрезок a не короче отрезка b;
14)	хорошее лучше плохого.
92.	Укажите взаимно однозначные отношения:
1) «a є А на 4 больше, чем b є В», где А - множество всех
целых чисел;
2)	«a є А есть делитель b є В», где А={2, 3, 5},
В={4, 8, 9, 25, 27, 125};
3)	«пассажир a є А едет в вагоне b є В», где А - множество
пассажиров поезда; В - множество вагонов; lBl >1; в каждом
вагоне более одного пассажира;
4)	«a є А слушает лекцию в аудитории b	є	В», где	А	-
множество студентов; В - множество аудиторий;	lBl	>	1; в каждой
аудитории более одного студента;
5)	«2a Ф 3b», где a, b є {1, 2, 3};
6)	«a - b = 0», где a и b - натуральные числа;
7)	«a > b», где a є {6, 7, 9}; b є {3,4};
8)	«a + b - нечетное число», где a є {2, 3, 4, 5}; b є {6,7,8,9};
9)	скрипка a є А находится в футляре b є В, где A - множество
скрипок, В - множество футляров.
35

ЧАСТЬ II. КОМБИНАТОРИКА
Комбинаторика является разделом дискретной математики,
ориентированным на решение задач выбора и расположения
элементов некоторого множества в соответствии с заданными
правилами и ограничениями. Каждое такое правило определяет
способ построения некоторой комбинаторной конфигурации,
поэтому комбинаторика занимается изучением свойств
комбинаторных конфигураций, условиями их существования,
алгоритмами построения и оптимизацией этих алгоритмов.
1.	Основные понятия комбинаторного анализа
1.1.	Основные правила комбинаторики
Правило суммы для двух объектов: Пусть объект а можно
выбрать m способами, объект b - n способами, и существует к
общих способов выбора объектов а и b , тогда один из объектов
«а или Ь» можно выбрать (m + n - к) способами.
Пример 1. Сколькими способами из 28 костей домино
можно выбрать кость, на которой есть «2» или «5»?
Решение. Выбрать кость, содержащую «2», можно 7-ю
способами (число костей домино, содержащих «2», равно 7),
содержащую «5» - тоже 7-ю способами, но среди этих способов
есть один общий - это выбор кости «2:5». В соответствии с
правилом суммы общее число способов выбора нужной кости
можно осуществить 7 + 7 - 1 = 13 способами.
Правило суммы для трех объектов: Если объект а можно
выбрать n1 способами, объект b - n2 способами, объект с - n3
способами, и известны n12 общих способа выбора одного из
36

объектов а и b, n13 общих способа выбора одного из объектов а и
с, n23 общих способа выбора одного из объектов b и с, а также
известно n123 общих способа выбора одного из объектов а, b и с,
то число всех способов выбора одного из объектов «а или b или
с» вычисляется по формуле:
П1 + П2 + П3 - П12 - П13 - П23 + П123.
Пример 2. В ходе экзаменационной сессии 12 студентов
получили оценки «отлично»,	12	-	«хорошо»,	13	-
«удовлетворительно», 5 - «хорошо» и «отлично», 7 - «хорошо» и
«удовлетворительно», 8 - «удовлетворительно» и «отлично». У
трех студентов все виды оценок. Сколько студентов в группе,
если известно, что все они сдали сессию? Сколько отличников в
группе? Сколько в группе «чистых» троечников?
Решение. В условиях задачи n1=12, n2 =12, n3 =13, n12=5,
n23=7, n13=8, n123 =3. По формуле находим:
-	общее число студентов в группе: 12 + 13 + 12 - 5 - 7 - 8 + 3=20;
-	число отличников в группе равно
n1 - (n12 + n13) + n123 = 12 - (5 + 8) + 3 = 2;
-	число «чистых» троечников равно
n3 - (n13 + n23) + n123 = 13 - (8 + 7) + 3= 1.
Правило произведения для двух объектов: Пусть объект а
можно выбрать n способами, и после каждого такого выбора
объект b можно выбрать m способами. Тогда выбор пары «а и b»
в указанном порядке можно осуществить (n • m) способами.
Пример 3. Сколькими способами можно выбрать гласную и
согласную буквы из букв слова «студент»?
Решение. Гласную букву можно выбрать двумя способами
(в слове «студент» 2 гласные буквы «у» и «е»), согласную можно
37

выбрать пятью способами. По правилу произведения выбор
«гласной и согласной» можно осуществлять 2х5=10 способами.
Пример 4. Сколько существует двузначных четных чисел в
десятичной системе счисления?
Решение. Выбираются две цифры из множества
{0,1,2,...,8,9}. Первая цифра может быть любой, кроме нуля.
Поэтому ее можно выбрать девятью способами. Вторая цифра
может быть любой из множества {2,4,6,8,0}, ее можно выбрать
пятью способами. Следовательно, четных двузначных чисел по
правилу произведения будет n-m = 45, где п =9, m =5.
В случае произвольного числа объектов правило
произведения формулируется следующим образом:
Если объект a1 можно выбрать п1 способами, объект a2 - п2
способами, ..., объект ak - nk способами, то общее число
полученных таким образом упорядоченных наборов (a1, a2,..., ak)
можно выбрать n1-n2-... -nk способами.
Если требуется выполнить одно за другим одновременно к
действий, на одно из которых наложено ограничение, то подсчет
числа возможных комбинаций удобнее начинать с выполнения
именно этого действия.
Пример 5. В микроавтобусе 10 мест, одно из которых -
место водителя. Сколькими способами могут сесть в автобус 10
человек, если место водителя могут занять только трое из них.
Решение. Начнем с места водителя. Имеется п1 = 3 способа
занять его место. Следующее место может занять любой из
девяти оставшихся человек, т. е. п2 = 9 и т. д. По правилу
произведения получаем всего возможностей
П1*П2*П3*... "Пю = 3-9-8-7-6-5-4-3-2-1 = 3-9!
38

1.2.	Понятие выборки
Известно, что к-выборка из некоторого множества
представляет собой комбинацию из к элементов этого множества.
Выборки, в которых все элементы различны, называют
выборками без повторений, а выборки, в которые могут входить
одинаковые элементы, называются выборками с повторениями.
Выборка называется упорядоченной, если существенным
является не только состав элементов в ней, но и порядок их
расположения. Две упорядоченные k-выборки считаются
различными, если они отличаются либо составом элементов, либо
порядком их расположения. Например, упорядоченные выборки
(1,2) и (2,1) считаются различными, хотя и составлены из одних и
тех же элементов.
Выборка называется неупорядоченной,	если порядок
следования элементов в ней несущественен. Так, {1,2} и {2,1}
считаются одной и той же неупорядоченной выборкой.
Фигурными скобками будем обозначать неупорядоченные
выборки, круглыми - упорядоченные.
Пример 6. Составьте всевозможные	2-выборки из
элементов множества М={а, Ь,с}.
Решение.	(а,Ь),	(Ь,а),	(а,с),	(с,а),	(Ь,с),	(с,Ь) - это
упорядоченные 2-выборки без повторений. Их, очевидно, всего 6.
(а,а); (а,Ь); (а,с); (Ь,Ь); (Ь,а); (Ь,с); (c,c); (c,a); (с,Ь) -
упорядоченные 2-выборки с повторениями. Их всего 9.
{а,Ь},{а,с},{Ь,с}	- неупорядоченные	выборки без
повторений. Легко видеть, что их всего 3.
39

[a,b]; [a,a]; [a,c]; [b,b]; [b,c]; [c,c] - неупорядоченные
выборки с повторениями. Их всего 6.
1.3.	Размещения без повторений
Размещениями без повторений из n элементов по к
называются упорядоченные к-выборки из n элементов без
повторений. Их число обозначается А^ и вычисляется по
формуле:
і	n'
Ак = nX(n -1)X(n - 2)X...X(n - к +1 )=-—Ц-	(1)
(n - к)!
Пример 7. Сколькими способами можно составить
трехцветный полосатый флаг, если имеется материал пяти
различных цветов?
Решение. Нужно найти число 3-выборок из пяти элементов
без повторений (все цвета различны); порядок, в котором
располагаются выбранные цвета, существенен. Следовательно,
нужно найти число упорядоченных выборок, т. е. число
размещений из 5 по 3 без повторений. По формуле (1) имеем
3	5!
Ас	—Ц- = 5 X 4 X 3 = 60 (способов).
5	(5 - 3)!
Заметим, что эту задачу можно решить иначе. Для выбора
цвета первой полосы имеется пять вариантов.
После произведенного выбора цвет для второй полосы можно
выбрать четырьмя способами из четырех оставшихся. Далее
выбираем цвет для третьей полосы флага из имеющихся трех
цветов. Это можно сделать тремя способами. По правилу
произведения всего имеем 5x4x3=60 (способов)
40

Пример 8. Та же задача из предыдущего примера, но среди
полос одна обязательно должна быть красной.
Решение. Красную полосу можно расположить тремя
способами, т. к. флаг трехполосный. После выбора красной
полосы, остался материал четырех цветов, из которых нужно
выбрать два цвета. Этот выбор можно осуществить
2	4!
A4 = -,—= 4 X 3 = 12 (способами).
4	(4 - 2)!
По правилу произведения окончательно имеем
4!
3 x A; = 3 -т—^ = 36 (способов).
4	(4 - 2)!
1.4.	Перестановки без повторений
Обычно размещения без повторений из n элементов по n
называются перестановками из n элементов. Их число
обозначается Pn и вычисляется по формуле
Pn = A,n = n!	(2)
Пример 9. Сколькими способами можно поставить в ряд 5
человек для фотоснимка?
Решение. Ряд из пяти человек можно рассматривать как
упорядоченную выборку из пяти элементов по 5. По формуле (2)
имеем
P5 = A^ = 5!= 120 (способов).
41

1.5.	Сочетания без повторений. Бином Ньютона
и биномиальные коэффициенты
Сочетаниями без повторений из п элементов по к
называются неупорядоченные к-выборки из п элементов без
повторений. Их число обозначается Сп и вычисляется по
формуле
ск
Сп
п!
!	,к < п.	(3)
к!(п - к)!
Пример 10. Сколькими способами можно выбрать три
различные краски из имеющихся пяти?
Решение. Очевидно, что нужно подсчитать число 3-выборок
из 5 элементов, причем по условию задачи понятно, что среди
выбранных элементов не должно быть одинаковых и что порядок
расположения выбранных красок несущественен. Значит, нужно
найти число неупорядоченных выборок, т. е. число сочетаний без
повторений из 5 по 3. По формуле (3) имеем:
'5
3!(5 - 3)!	2!
п
п	/^к ^,kn - к
Определение.	Формула вида	(x + y)n= ^ С^хку
п '
к=0
называется биномом Ньютона.	Числа Ск	называются
биномиальными коэффициентами.
Свойства биномиальных коэффициентов, которые часто
используются при преобразованиях формул комбинаторики.
1 С к   с п-к
Сп _ Сп .
2.	Скп _ СЦ + Ch .
42

3. cn + cn+cn+... + cn = 2n.
Соотношение 2 можно переписать как сЩІ = СП + СП+1 и
для Бинома Ньютона оно означает, что коэффициент сП+l в
биноме степени n+1 получается суммированием двух соседних
коэффициентов в биноме n-й степени. На этом свойстве основана
конструкция знаменитого треугольника Паскаля.
Каждая (п+1)-я строка этого треугольника состоит из
биномиальных коэффициентов, получающихся при раскрытии
скобок в выражении (x+ y)n .
Рис. 2. Треугольник Паскаля
1.6.	Разбиение множества на несколько частей.
Полиномиальные коэффициенты
Иногда требуется переставлять предметы, часть из которых
неотличимы друг от друга. Такой вариант перестановок
называется перестановками с повторениями. Пусть имеется n1
предметов 1-го типа, n2 предметов 2-го типа, nk предметов k-го
типа и при этом n1 + n2 + ...+ nk = n.
Количество различных перестановок предметов
определится формулой
n!
P(n1 ,n2,...,nk )=	:	.
1	2 k	(n1ln.2L.nk!)
43

Пример 11. Найти количество перестановок букв в слове
«КОЛОБОК».
Решение. Слово «КОЛОБОК» состоит из семи букв,
которые можно переставить 7! способами. Однако в нем есть три
буквы «О» и две буквы «К». Поэтому меняя местами буквы «О»
или переставляя буквы «К», мы не получим новых «слов».
Так как количество перестановок трех элементов равно 3!,
а двух - 2!, то мы можем получить всего
7!
—- = 420 разных «слов» из слова «КОЛОБОК».
3!2!
Пример 12. Сколькими способами можно распределить 15
студентов по трем учебным группам по пять студентов в каждой?
Решение. У нас есть 15 объектов, которые нужно
организовать в три группы по пять. Это можно сделать
15!
Р( 5,5,5) =	= 68 796 различными способами.
(5!5!5!)
Коэффициенты
n
V
n1, n2,..., nk J
n!
n1! n2!...nk!
носят
название полиномиальных.
n1rn2	"k
Они стоят при произведениях Х1 Х2	...	xk в
разложении
(x1 +x2+ ... + xk)n =	X
степени (x1 + x2 +... + xk ) :
n
n1	n2 nk
Vn1, n2,..., nk J
V x2 ...xk
n1 +...+nk =n
44

X
0 < nt < n
Если в формуле x1 = x2 = ... = xk = 1, то получим
= kn, т.е. имеется kn способов разбить n
Vn1, n2,..., nk J
элементов на k.
1.7.	Размещения с повторениями
Размещениями с повторениями из n элементов по k
называются упорядоченные k-выборки из n элементов с
повторениями. Их число обозначается An и вычисляется по
формуле
Ak = nk, Vn,k є N.
Пример 13. Сколько различных пятиразрядных чисел
можно составить с помощью 10 цифр?
Решение. Пронумеруем разряды: 1 2 3 4 5. В первый разряд
можно поставить одну из 10 цифр. Независимо от того, какая
цифра поставлена, во второй разряд можно также поставить одну
из 10 цифр и т. д. Всего получается 105 различных чисел.
Пример 14. Сколько различных двоичных пятиразрядных
чисел можно составить?
Решение. Для двоичной системы счисления (в которой
используются только две цифры: 0 или 1) получаем 25 различных
чисел.
1.8.	Сочетания с повторениями
Сочетаниями с повторениями из n элементов по k
называются неупорядоченные k-выборки из n элементов с
45

повторениями. Их число обозначается Нп и вычисляется по
формуле
кк
Нп ~ Сп+к-1
'п + к -11 = (п + к -1)!,Чп,к€ N.
V к	J
к!(п -1)!
Пример	15.	В киоске имеются открытки	10 видов.
Сколькими способами можно купить: а) 5 открыток? б) 5 разных
открыток? в) 15 открыток с повторениями?
Решение. В случаях а) и в) нас интересуют
неупорядоченные выборки из 10 элементов с повторениями
длины 5 и 15 соответственно. Их число определяется по
формулам:
а) H150 _ с1п+5 1 _ ^10 + 5—— _	_ 2002 (способов);
10	1п+5-1	5!(10 -1)!	5!9!
л „15 nis (10 +15-1)!	24! .	_	.
в) Н1(5 _ С1П+15 1 _	_	(способов);
10	1п+15-1	15!(10 -1)!	15!9!
В случае б)	нужно подсчитать число неупорядоченных
5-выборок из	10	элементов без повторений (все	открытки
разные). Их число определяется по формуле
5	10!
б)	с10 _ —-_ 252.
10	5!5!
2.	Главная теорема комбинаторики (теорема о включениях
и исключениях)
2.1.	Теорема о включениях и исключениях
Теорема. Пусть имеется множество из N объектов
произвольной природы и пусть задано п произвольных свойств
так, что объекты могут обладать или не обладать некоторыми из
46

этих свойств. Сами свойства обозначим ах, а2, ..., an. Кроме
того, будем обозначать N( at) - количество объектов, точно
обладающих свойством а и, может быть, какими-то другими, а
N( at, а-) - число объектов, не обладающих ни свойством at, ни
свойством а -. Тогда число объектов, не обладающих ни одним
из перечисленных свойств, будет равно
N(а1, а2,.., an) = N - N(а1) - N(а2) -... - N(an) + N(а1, а2) +
+ N(а1,а3) +... + N(а1,an) + N(а2,а3) +... + N(an-1,an) -	(4)
-	N(а1,а2,а3) -... + (-1 )nN(а1, а2,а3,..,an).
Формула (4) называется формулой включений и
исключений.
Пример 16. На предприятии работают 67 человек. Из них
45 знают английский язык, 40 - немецкий, 15 - французский, 30 -
vy	vy	W	1	/-v	vy	О	1	vy	/~\
английский и немецкий, 10 - английский и французский, 9 -
немецкий и французский. 4 сотрудника знают все три языка.
Сколько человек не знают ни одного языка?
Решение. В соответствии с теоремой количество человек, не
знающих ни английского, ни немецкого, ни французского языков,
равно
N = 67 - 45 - 40 - 15 + 30 + 10 + 9 - 4 = 12.
Пример 17. В результате опроса 70 студентов выяснилось,
что 45 из них занимаются спортом, 29 — музыкой, 9 — и
спортом и музыкой. Сколько студентов из числа опрошенных не
занимаются ни спортом, ни музыкой.
Решение. Чтобы применить формулу (4), обозначим через
а1 (а 2) свойство студента, состоящее в том, что он занимается
спортом (музыкой).
47

Тогда имеем N=70, N(а1) = 45, N(а2)= 29, N(а1, а2) = 9.
Нужно найти число N(а1,а2). По формуле (4) получаем
N ($1, $2) = N — N ($1) — N ($2) + N ($1, а 2) = 70 — 45 — 29 + 9 = 5.
2.2.	Задача о смещениях
При решении задач, в которых количество объектов,
обладающих определенным набором свойств, зависит только от
количества свойств, а не от самого набора свойств, формула для
подсчета числа объектов, не обладающих ни одним из
выделенных свойств, при произвольном n имеет вид
N(n) = n!-C1(n — 1)!+C„2(n-2)!-... + (-1)"c;; = D„.	(5)
Полученное значение Dn иногда называют формулой
полного беспорядка, или субфакториалом.
Субфакториал можно представить следующим образом:
f 111	1 ^
Dn = n! 1 — - +	+... + (—1 )n — ,
n V 1! 2! 3!	n! J
где выражение в скобках стремится к e~l при неограниченном
возрастании n.
Субфакториал имеет свойства, похожие на свойства
обычного факториала, например
n!= (n — 1)[(n —1)!+( n — 2)!] - для обычного факториала,
Dn = (n —1)[Dn—1 + Dn—2 ] - для субфакториала.
Субфакториалы легко вычисляются по рекуррентной
формуле
Dn = nDn—1 +(—1) n .
48

Количество перестановок п различных предметов, при
которых ровно к предметов стоят на своих первоначальных
местах, выражается числом Опк _ Сп • Бп_к.
Пример 18. Имеется 5 различных предметов. Сколько
существует различных перестановок этих предметов, в которых
ни один предмет не находится на своем месте?
Решение. Применив формулу (5), получаем
N(5) _ 5!-С<14!+С5 3!-С531!-С50!_ 44 перестановки предметов.
2.3.	«Задача о караване»
Рассмотрим задачу, решение которой может быть получено
с использованием главной теоремы комбинаторики. По пустыне
много дней движется караван из 9 верблюдов. И верблюдам, и
погонщикам надоело видеть перед собой хвост одного и того же
верблюда. Сколько существует перестановок верблюдов таких,
при которых ни один верблюд не идет за тем, за кем шел раньше?
Выделим запрещенные пары верблюдов: (1 2), (2 3), (3 4), (4
5), (5 6), (6 7), (7 8), (8 9). Если под объектами теоремы понимать
перестановки верблюдов, а под свойствами - наличие одной из
запрещенных пар, тогда количество перестановок, не
обладающих ни одним из восьми свойств, будет равно
N(9) _ 9!-С88!+Со27!-С836!+... + С81!_ 148 329.
В общем случае при п верблюдах получаем
2-1 (п - 2)!-... + (-1)n-1 С-1 - ^ т^п-1
N (п) _ п!-С1-1(п - 1)!+с2-1 (п - 2)!-... + (-1)п-1 С-1 _ Dn+Dn_
49

2.4.	«Решето Эратосфена»
Одной из самых больших загадок математики является
расположение простых чисел в ряду всех натуральных чисел.
Древнегреческий ученый Эратосфен (он жил в III веке до новой
эры в Александрии) придумал способ, как найти все простые
числа среди натуральных чисел от 1 до N.
Сначала вычеркивают все числа, делящиеся на 2 (исключая
само число 2). Потом берут первое из оставшихся чисел (а
именно 3). Ясно, что это число простое. Вычеркивают все
идущие после него числа, делящиеся на 3. Первым оставшимся
числом будет 5. Вычеркиваем все идущие после него числа,
делящиеся на 5, и т. д. Числа, которые уцелеют после всех
вычеркиваний, и являются простыми. Так как во времена
Эратосфена писали на восковых табличках и не вычеркивали, а
выкалывали цифры, то табличка после описанного процесса
напоминала решето. Поэтому метод Эратосфена для нахождения
простых чисел получил название «решето Эратосфена».
Выпишем все числа от 1 до N. Сколько чисел из них делятся
на к нацело? Очевидно, что [N/k], где [] обозначает целую часть
числа. Тогда легко подсчитать количество чисел, которые не
делятся на конкретные числа k1, k2, ., ks. Эта задача решается по
формуле включения и исключения.
Пример 19. Сколько чисел в диапазоне от 1 до 100 не
делятся ни на 5, ни на 7?
Решение. Воспользуемся теоремой о включениях и
исключениях. Под первым свойством числа будем понимать
50

делимость на 5, под вторым - делимость на 7. Тогда количество
чисел, которые не делятся ни на 5, ни на 7, будет равно:
100 - 20 - 14 + 2 = 68.
2.5.	Разбиение множества на два подмножества
Рассмотрим простую задачу. Сколько существует вариантов
расклада пяти одинаковых рублей в два кармана? Выпишем
разные варианты расклада:
1-й	карман: 5 р.; 4 р.; 3 р.; 2 р.; 1 р.; 0 р.;
2-й	карман: 0 р.; 1 р.; 2 р.; 3 р.; 4 р.; 5 р.
Итого, существуют шесть вариантов расклада пяти рублей
по двум карманам. Если раскладываются n рублей, то число
вариантов расклада равно n + 1.
Если раскладываются предметы нескольких типов на две
кучки (ящики, корзины, множества), то такой расклад можно
выполнять независимо для каждого типа предметов.
Используя полученное решение, найдем количество
делителей любого целого числа N. Известно,	что	любое	целое
число однозначно может быть представлено	в	так	называемой
канонической форме, т. е. в виде произведения простых чисел в
_т	n	щ	n
соответствующих степенях: N= p11p22...pkk .
Задача о нахождении количества делителей любого целого
числа N сводится к раскладке этого числа на два сомножителя. В
этом случае степени простых сомножителей раскладываются так
же, как монеты в вышеприведенной задаче. Таким образом, число
делителей D некоторого числа N равно
D( N) = (n + 1)(n2 +1)( n3 + 1)...(nk +1).
51

Пример 20. Найти число делителей N = 760.
о і	і
Решение. В канонической форме 760	=	2 -5 -19 .
Следовательно, число делителей равно D(760) = (3 +1)(1 +1)(1 +1).
Для нахождения количества делителей N, кратных
некоторому числу R, можно N / R представить в канонической
форме и найти количество делителей этого числа.
Пример 21. Найти количество делителей числа 600,
кратных 15.
о	1
Решение. Находим 600/15 = 40 = 2 • 5 . Количество
делителей числа 600, кратных 15, равно D (40) = (3 +1)(1 +1) = 8.
2.6.	Задачи на разбиения
n одинаковых предметов можно разделить между k лицами
P(n, k — 1) = Ck+l—1 способами.
В частности, если каждый из k участников должен получить
не менее одного предмета, то задача решается C^—-1 способами.
2.7.	Формула Стирлинга
Для перестановок установлена очень простая формула:
Pn = n!. Применяя эту формулу при решении практических задач,
не следует забывать, что факториал — это очень быстро
растущая функция, в частности, факториал растет быстрее
экспоненты. Поэтому можно использовать известную из
математического анализа формулу Стирлинга
n!~ л/2П • nn+112 • e~n при n ^ го.
52

п
п!
г\ п+1/ 2 —п
V2п•п • е
п!
д/2л • пп+1/2 • е~п
1
1
0,992
0,922
2
2
1,919
0,960
3
6
5,837
0,979
4
24
23,510
0,980
5
120
118,037
0,983
10
3 628 800
3 598 692
0,992
Получим формулу для числа сочетаний:
к	п!	V 2П • п • Є
п	к!(п - к)!	л/2п • кк+1/2 • е“кл/2п • (п - к)п-к+1/2 • е"^
п+1/2
пп+
л/2п • кк+1/2(п - к)п-к+1/2
3.	Производящие функции
Пусть a0 ,a1,a2,... - числовая последовательность.
Ее производящей функцией (ПФ) называется функция вида
A(t) _ an + a1t + a2t2 +... _ £ antn .
n_ 0
Экспоненциальной производящей функцией	(ЭПФ)
называется функция вида
E (t) _a0+11 + 212 +... _ £ ^ t" .
1!	2!	n_ 0 n!
Если последовательность a0 ,a1,a2,... бесконечна, то ПФ и
ЭПФ степенные ряды, если в последовательности конечное число
членов, то ПФ и ЭПФ конечные многочлены.
53

Свойства производящих функций:
1.	Если A(t) и B(t) ПФ {an} и {bn}, то при любых а и p
C (t) = aA(t) + PB (t) есть ПФ последовательности
{cn } = {aan + РК }
Доказательство:
aA(t) + fiB(t) = a(a0 + a^t + a2t2 +...) + e(b + bt + b2t2 +...) =
= (ояд + /?b0) + (a + 4 )t + (a + /4b2 )t2 + •••
1			3	(			3	(			3
V	V	V
c0 c1 c2
2.	Если A(t) и B(t) ПФ {an} и {bn}, то
2
A(t) B(t) = a0b0 + (a0b1 + a1b0)t + (a0b2 + a1b1 + a2b0)t +
0b0 + Va0b1 + a1u0>1 + va0b2 + a1b1 + a2b0 -
to n
3 ■ = ZZ (ab )tn
n=0k=0
to n
+ (a0b3 + ap2 + a2^ + ab)t3 +... = Z Z(ab-k )t
n
Последовательность cn= Z akbn-k называется сверткой
k=0
последовательностей an и bn .
3. Если Ea(t) и Eb(t) ЭПФ {an} и {bn}, то при любых а и p
Ec(t)= aEa(t) + PEb(t)	есть ЭПФ от последовательности
{cn } = {aan + pbn }.
4. Если Ea(t) и Eb(t) ЭПФ {an} и {bn}, то EJt)= Ea(t)EJt) -
n
ЭПФ последовательности cn= Z akbn - k
k = 0
'n'
V k J
an =
5.	Пусть	A(t) ПФ	последовательности	{an},	тогда
A(n) (0)
n!
6.	Пусть	E(t) ЭПФ	последовательности	{an},	тогда
an = E(n) (0).
54

Пример 22. Найти ПФ и ЭПФ последовательности an = an ,
{1,a,a2,...,an }.
. 2 1 .. 1
Решение. ПФ A(t) = 1 + at + (at) + ... =	при |t| <y-,
1 — at	|a|
2
ЭПФ E(t) = 1 + — + — +... = eat
1! 2!
4.	Задания для самостоятельного выполнения
1.	Имеется 10 карточек. На каждой записана гласная буква.
Выбирают наугад карточку и к ней справа приставляют вторую,
наугад выбранную после первой. Сколько возможно таких
двухбуквенных слов?
2.	Сколько трехразрядных чисел можно образовать из цифр
3, 4, 5, 6?
3.	Сколько семизначных чисел можно образовать из
цифр 3, 7, 9?
4.	Из пятизначных десятичных чисел удалили все числа, в
которые входит хотя бы одна из цифр 0, 3, 7, 8, 9. Сколько чисел
осталось?
5.	Город А связан с городом В шестью дорогами. Сколькими
способами житель города А может посетить город В, если возврат
возможен по той же дороге, что и поездка в город В? Сколькими
способами житель города В может посетить город А, если поездка
туда и обратно осуществляется по разным дорогам?
6.	Сколько четырехзначных чисел можно составить из цифр
0,	1, 2, 3, 4, 5, если ни одна из цифр не повторяется в числе более
одного раза?
55

7.	Сколько трехзначных чисел можно составить из цифр 1, 2,
3,	4, 5, если цифра младшего разряда каждого числа является
четной, а старшего - нечетной?
8.	Сколько существует пятизначных десятичных чисел,
которые делятся на 5?
9.	Сколько существует пятиразрядных симметричных
десятичных чисел (которые одинаково читаются как справа
налево, так и слева направо, например, 39 793; 68 286)?
10.	Старший разряд двузначного числа некоторой системы
счисления может содержать одну цифру из 7, младший разряд -
одну цифру из х. Всего таких чисел существует 84. Найдите х
(десятичное число).
11.	Сколько существует трехразрядных семеричных чисел,
оканчивающихся нечетной цифрой?
12.	Сколько существует трехразрядных десятичных чисел, у
которых:
-	в старшем разряде нет ни одной из цифр 1,2,3,4,5;
-	в среднем разряде нет цифр 2,5,7;
-	в младшем разряде нет четных цифр и нет цифры 1 ?
13.	30 учащихся сдавали экзамен по физике и химии. По две
отличные оценки получили 9 человек. На «отлично» физику
сдали 12 человек, химию - 16. Сколько учащихся не получили ни
одной отличной оценки?
14.	12 туристов взяли с собой по коробке спичек, 19 туристов
-	по зажигалке. Ни спичек, ни зажигалок не взяли 6 человек.
Всего в отряде 27 человек. Сколько человек взяли с собой и
спички и зажигалки?
56

15.	Из 33 учащихся физический кружок посещают 11
человек. Из них 4 человека посещают еще и химический кружок.
Ни физический, ни химический кружок не посещают 8 человек.
Сколько человек посещают только химический кружок?
16.	Укажите номера вопросов, на которые вы ответите «да»:
1)	IAuBI = IAI + IBI. Верно ли, что AnB Ф 0?
2)	IAuBI < ІAI + |BI. Верно ли, что AnB = 0?
3)	|AuB| = IAnBI. Верно ли, что |AuB| = IAI + IBI?
4)	А = B. Верно ли, что lAnBI = B?
5)	А <zB. Верно ли, что AnB = 0?
6)	А z> B. Верно ли, что IAuBi = IAI+ IBI?
7)	А с B. Верно ли, что IAuBi = IBI?
17.	Сколько различных чисел можно образовать, переставляя
цифры 3, 4, 5, 7, 9?
18.	Известно, что операция арифметического сложения
коммутативна. Например, выражение a+b+c+d можно записать
иначе: b+c+a+d либо c+a+d+b и т. д. Сколько существует
способов записи этого выражения?
19.	Составляют буквенно-цифровой код: записывают в
некотором порядке четыре буквы а, b, c, d, затем справа
приписывают три цифры 1, 2, 3, также в некотором порядке,
например, bcda 132, abcd123, и т. д. Сколько существует таких
кодов?
20.	Буквенно-цифровой код составляют следующим образом.
Сначала записывают две буквы а и b в каком-либо порядке, затем
-	три цифры 1, 2, 3, также в определенном порядке, затем -
четыре буквы a,b,c,d в некоторой последовательности. Например:
57

ab132dbac, ba321adbc и т. д. Сколько всего существует таких
кодов?
21.	Сколько существует 6-значных чисел шестеричной
системы счисления, если каждая шестеричная цифра входит в
число точно один раз (числа, начинающиеся с нуля, не являются
шестизначными)?
22.	Сколько 10-значных чисел можно составить из
десятичных цифр, если каждая цифра входит в число один раз и
каждое число начинается с последовательности 731 и
оканчивается последовательностью 05?
23.	Известно, что п человек могут разместиться в очереди
3	628 800 способами. Найдите п.
24.	Получена шифровка вида 02, 30, 16, 04, 07, 18, 30, 17, 30,
09, 09, ..., о которой известно только, что двухразрядные
десятичные числа представляют собой номера 01, 02, ..., 33 букв
русского алфавита. Некто решил расшифровать сообщение
следующим образом. Нумерует буквы алфавита в некотором
порядке, затем вместо чисел подставляет буквы согласно
принятому соответствию. Читает запись. Если получилась
бессмыслица, буквы алфавита нумерует в другом порядке и снова
читает запись. Сколько операций перекодирования букв алфавита
потребуется выполнить в самом неблагоприятном случае? (Ответ
дать с использованием знака факториала, например, 16!).
25.	Сколько существует шестизначных десятичных чисел, в
каждом из которых три цифры 4 и три цифры 5?
26.	Сколько чисел можно образовать, переставляя цифры 1,
2,	3, 5, если в каждом числе три единицы, одна двойка, две
тройки и две пятерки?
58

27.	Сколько различных слов можно образовать путем
перестановки букв в слове «территория»?
28. В числе 3 двойки, 4 тройки, 2 четверки, 3 пятерки.
Сколько чисел можно образовать, переставляя эти цифры, если
каждое число начинается с последовательности 335 и
оканчивается тремя двойками?
29.	На полке пять книг синего цвета, две - желтого и одна -
зеленого. Сколькими способами их можно расставить на полке,
если слева всегда стоят две книги синего цвета?
30.	Сколько слов можно образовать, переставляя буквы слова
«облако», если каждое слово начинается с согласной буквы?
31.	Сколько слов можно образовать, переставляя гласные
буквы в слове «авиация» и оставляя на своих местах все
согласные буквы?
32.	Сколько возможно различных чисел при перестановке
цифр числа 4 152 486 813, если на место, занимаемое четной
цифрой, нельзя ставить нечетную?
33.	Сколько существует пятиразрядных десятичных чисел, в
каждом из которых нет цифр 0,1,2,3 и в каждом нет
повторяющихся цифр?
34.	Сколько четырехбуквенных последовательностей можно
образовать из всех гласных букв русского алфавита, если в
каждой последовательности повторяющихся букв нет?	(В
русском алфавите 10 гласных букв: а, е, ё, и, о, у, ы, э, ю, я).
35.	Сколько существует двухразрядных чисел семеричной
системы счисления, в каждом из которых нет повторяющихся
цифр?
59

36.	В тире 10 мишеней. Сколькими способами могут выбрать
себе по одной мишени три стрелка, если каждую мишень
выбирает не более чем один стрелок?
37.	Известно, что число размещений без повторений из n
элементов по т равно 210. Найдите n и т.
38.	Известно, что число размещений из n элементов по т
равно 7920. Определите числа n и т.
39.	Из 10 цифр образуют семизначные десятичные числа, в
каждом из которых нет повторяющихся цифр. Сколько
существует таких чисел, если каждое число начинается с
последовательности цифр 897?
40.	Из 10 цифр образуют семизначные десятичные числа, в
каждом из которых нет повторяющихся цифр. Сколько
существует таких чисел, если каждое число оканчивается
последовательностью цифр 789?
41.	Три ученика выбирают по одной книге из 11
предложенных. Все книги разные. Сколькими способами может
быть осуществлен выбор?
42.	Ученикам предложено несколько книг. Из них каждый
ученик выбирает себе одну книгу. Всего существуют 24 024
способа выбора. Сколько было учеников и сколько книг?
43. Известно, что существуют 900 k-разрядных чисел, не
содержащих одинаковых цифр. Определите число k. Определите
основание системы счисления, в которой заданы k-разрядные
числа.
44.	Существуют 3024 k-буквенных слов, в каждом из
которых нет повторяющихся букв. Определите число k. Сколько
было букв, из которых составились k-буквенные слова?
60

45.	Сколько двухбуквенных слов можно образовать из 10
гласных букв русского алфавита?
46.	Сколько существует трехразрядных десятичных чисел?
47.	Сколько существует пятиразрядных чисел четверичной
системы счисления?
48.	Сколько слов длины 3 можно составить из букв
множества {а, b, c, d, е, f}?
49.	Сколько слов длины 10 можно составить из двух букв
а и b?
50.	Сколько слов длины 12 можно составить из одной
буквы d?
51.	Известно, что существуют 100 m-значных чисел р-ичной
системы счисления. Найдите числа m и р.
52.	Дано множество A _ {а, б, в, г, д}. Число размещений с
повторениями из IAI по m равно N1. Число размещений с
повторениями из IAI по m+1 равно N2. Известно, что
N2 - N1 = 500. Найдите N1 и N2.
53.	Дано множество А = {а,б,в,г,д,е}. Сколько существует
размещений с повторениями из IAI по 3, если каждое размещение
(выборка) начинается с буквы в?
54.	Дано множество A = {а,б,в,г,д,е}. Сколько существует
размещений с повторениями из IAI по 3, если ни одно из
размещений не начинается с буквы д?
55.	Дано множество A =	{а,б,в,г,д,е,ж,з}. Сколько
существует размещений с повторениями из IAI по 4, если:
каждая выборка (размещение) начинается и оканчивается
буквой б?
каждая выборка начинается с а б в?
61

каждая выборка оканчивается либо буквой г, либо буквой ж?
каждая выборка начинается с гласной буквы?
ни одна выборка не начинается и не оканчивается буквой а?
56.	Сколько существует четных трехразрядных десятичных
чисел, не содержащих нечетных цифр в двух старших разрядах?
57.	Сколько существует нечетных трехразрядных
десятичных чисел, не содержащих четных цифр в двух старших
разрядах?
58.	Сколько существует восьмиразрядных двоичных чисел,
начинающихся не с нуля?
59.	Сколько существует 8-разрядных двоичных кодов,
содержащих три единицы каждый?
60.	Сколько существует 9-значных двоичных кодов, каждый
из которых содержит 6 нулей?
61.	Сколько существует 10-значных двоичных кодов,
начинающихся с нуля, если в каждом коде четыре единицы?
62. Сколько существует 8-разрядных двоичных кодов, в
каждом из которых четное число единиц?
63.	66 символов некоторого алфавита закодированы
двоичными кодами, содержащими по две единицы каждый.
Определите наименьшую длину кода.
64.	80 знаков некоторого алфавита решено закодировать
двоичными кодами, содержащими три единицы каждый. Найдите
наименьшее значение n и число нулей в коде, если n - длина кода.
65.	В шахматном городе размером mxn число кратчайших
диагональных путей, состоящих из 11 отрезков, равно 462.
Найдите m и n, если m < n, m Ф 1.
62

66.	Сколько существует кратчайших путей от А до С (рис. 3),
если каждый путь проходит через В и если n - число отрезков по
вертикали, т - число отрезков по горизонтали от А до B, k -
число отрезков по горизонтали от B до С? Принять n = т = 4,
k = 2.
Рис.3.
67.	На прямой а (рис. 4) расположено n точек, на прямой b -
т точек. Все точки прямой а соединены отрезками со всеми
точками прямой b. (Рис. 4 приведен для случая, когда n = 4, т =
3). Сколько существует точек пересечения отрезков, если ни в
одной точке больше двух отрезков не пересекаются и если n = 7,
т = 5?
Рис.4.
68.	На одной стороне равностороннего треугольника
расположено n1 точек, на второй - n2 точек и на третьей - n3
точек (рис. 5). Ни одна из этих точек не совпадает ни с одной
вершиной треугольника. Каждая из n1 точек соединена прямыми
линиями со всеми точками двух других сторон. Проведенные
63

линии внутри треугольника образуют точки пересечения, в
каждой из которых пересекается только две линии. Определите
число точек пересечения, если n1 = 4, n2 = 5, n3 = 3.
То же самое, если n1 = 5, n2 = 2, n3 = 1.
пЗ
Рис.5.
69.	Найдите х в уравнениях:
С2 = 91; С2 = 190; С3Х = 120; CJ4 = 120 .
70.	В восьмизначном числе вида k = 3 2 5 1 4 7 6 8 три цифры
заменили нулями. Получилось новое число. Если в числе k
нулями заменить другие какие-либо три цифры, получится еще
одно число. Сколько различных восьмизначных чисел можно
получить, если каждый раз нулями заменять какие-либо три
цифры?
71.	Замок сейфа управляется 12 кнопками путем
одновременного нажатия трех кнопок с номерами i, j, k,
где i, j, k = 1,2,3, ..., 12; i Ф j; i Ф k; j Ф k. Тройка этих номеров
образует кодовый ключ. Некто решил открыть сейф путем проб и
ошибок. Сколько троек ему придется проверить в самом
неблагоприятном случае?
72.	На плоскости расставлено 14 точек так, что никакие три
точки не лежат на одной прямой. Сколько прямых можно
провести, соединяя точки попарно?
64

73. Сколько существует четырехразрядных десятичных
чисел, у которых каждая следующая цифра больше предыдущей?
74. Сколько существует четырехразрядных десятичных
чисел, у которых каждая следующая цифра меньше предыдущей?
75.	На плоскости проведено п прямых так, что среди них нет
ни одной пары параллельных и никакие три линии не
пересекаются в одной точке. Каждая прямая продолжена в обе
стороны без ограничений. В результате пересечения линий
получаются различные фигуры - треугольники,
четырехугольники, пятиугольники и т. д.
Сколько получится треугольников при п = 12?
Сколько получится точек пересечения прямых при п =15?
76.	Двоичное число содержит 9 нулей и 5 единиц, причем
рядом стоящих единиц в числе нет. Сколько существует таких
чисел?
77.	На полке стоит 14 различных книг. С нее сняли 5 книг,
причем никакие две из них на полке не стояли рядом. Сколько
существует способов такого выбора книг?
п
78.	В формуле	С0„ + С1 + С2 +С3 +... + С"_ £ С‘_ 2"
i_0
укажите наибольшее число сочетаний при п = 10.
79.	При каких значениях i число сочетаний из п по i С1п в
п
формуле	c" + c1 + c" + c" +... + c" _ £ c" _ 2n	принимает
i_ 0
наибольшее значение, если п = 17.
80.	Известно, что Сm _ 165 и что п - m = 8. Найдите m и п.
81.	Известно, что Сm _ 1001; с"-1 _ 286. Найти .
65

82.	Найдите сумму вида C + C" + C" + C" + C" + C"1, если
известно, что C" + C" + C" + C" + C" + C"° + с"2 = 2048.
83.	В магазине продают четыре вида конфет. Сколькими
способами можно купить 15 конфет?
84.	Продаются тетради пяти цветов: с синей обложкой,
фиолетовой, красной, зеленой и оранжевой.
A)	Требуется купить 10 тетрадей любого цвета. Скольким
способами это можно сделать?
Б) Требуется купить 15 тетрадей. Пять из них должны быть с
фиолетовой обложкой, а обложки всех остальных тетрадей могут
быть любого цвета, кроме фиолетового. Сколькими способами
возможна такая покупка?
B)	Требуется купить 16 тетрадей, среди которых 4 тетради
должны быть с зеленой обложкой и 5 тетрадей - с оранжевой.
Цвет обложки остальных тетрадей значения не имеет. Сколькими
способами возможна покупка?
Г) Требуется купить 14 тетрадей, среди которых каждого
цвета из пяти должно быть не менее чем по две тетради. Сколько
существует вариантов покупки?
85.	20 студентов могут сдавать экзамен в любой день из
четырех. На первый день подано n1 заявок, на второй - n2, на
третий - n3, на четвертый - n4. Сколько существует различных
наборов чисел n1, n2, n3, n4?
86.	Из Томска в Кемерово можно уехать тремя видами
пассажирского транспорта:	поездом, автобусом и речным
катером. Группа туристов, насчитывающая 18 человек,
отправилась из Томска в Кемерово, причем n1 человек
воспользовались поездом, n2 - автобусом и n3 - речным катером.
66

Сколько существует различных наборов чисел n1, n2, n3
(при n1 + n2 + n3 = 18)?
87.	В железнодорожном составе 10 пассажирских вагонов. В
них необходимо разместить 6 пассажиров. Сколькими способами
это можно сделать, если в каждом вагоне имеется не менее 6
свободных мест и если пассажирам безразлично, в каком вагоне
ехать?
88.	30 конфет необходимо распределить по трем ящикам.
Сколькими способами это можно сделать при условии, что все
конфеты одинаковые?
89.	Между тремя учениками необходимо разделить 45 яблок.
Сколькими способами это можно сделать при условии, что все
яблоки одинаковые и что каждый ученик получит не менее 7
яблок?
90.	Шесть домов отдыха предлагают путевки в
неограниченном количестве. Руководством некоторого завода
решено приобрести 10 путевок. Сделать это можно многими
вариантами. Например, взять все 10 путевок в один дом отдыха
либо две путевки взять в первый дом, три - во второй, остальные
-	в пятый и т. д. Сколько всего существует вариантов выбора
домов отдыха?
91.	В 4 ящика необходимо разложить 30 предметов так,
чтобы в каждом ящике оказалось хотя бы 4 предмета. Сколько
существует способов загрузки ящиков?
92.	В четыре ящика необходимо загрузить n предметов так,
чтобы в каждом ящике оказалось не менее чем по 5 предметов.
Известно, что существует 1540 способов загрузки ящиков.
Определите n.
67

93.	Множество состоит из семи элементов. Сколькими
способами его можно разбить на два подмножества А1 и А2, если
IA1I = 3; IA2I = 4?
94.	Множество состоит из 12 элементов. Сколькими
способами его можно разбить на два подмножества А1 и А2, если
IA1I = I A2I ?
95.	Сколькими способами множество А можно разбить на два
подмножества А1 и А2, если IAI = 9?
96.	Дано разбиение: А1 _ {1, 2, 3}; А2_ {4, 5, 6, 7, 8}. Найдите
число разбиений множества А1 и А2, если
I A1I = 3; I A2I = 5
I A1I = I A2I = 4
I A1I = 2, I A2I = 6.
97.	Известно, что булеан подмножества А1 содержит 126
собственных подмножеств. Кроме	того,	известно,
что IAJ+I A2I = 14, где А1 и А2 - разбиение множества А.
-	Определите I A2I.
-	Определите число разбиений множества А при
—	I A1I = I A2I;
—	I A1I = 1; I A2I = 13.
98.	Известно, что существует 2048 способов разбиения
множества А на два подмножества.
—	Определите IAI.
—	Сколько существует разбиений множества А:
—	на два подмножества Aj и А2, если I AJI =	4?
—	на два подмножества Aj и А2, если I AJI =	6?
—	на два подмножества Aj и А2, если во всех разбие¬
ниях А1Ф0 и А2Ф0?
68

99.	Дано множество А = {a, b, c, d, e, f, k}. Сколькими
способами можно разбить его на три подмножества А1, А2 и А3,
если І А1І = 4, І А2І = 2, І А зі = 1?
100.	Дано: І А1І = 2; І А2І = 3; І АзІ = 4; І А4І = 1; A = 10. Сколько
существует способов разбиения множества А на четыре
подмножества А1, А2, А3, А4 при отсутствии каких-либо
ограничений?
101.	Множество А разбито на подмножества так, что І А1І = 1;
І А2і = 1; І А3І = 4; І А4 І = 4. Сколько существует таких разбиений
(ограничений нет)?
102.	Сколькими способами можно разбить на пять
подмножеств множество А, если І А1І = І А2і = І А3І= =І А4 І= І А5І = 1
и если нет никаких дополнительных ограничений?
103.	Требуется разложить по 4 ящикам 10 различных
предметов так, чтобы в первом и втором ящиках было по 2
предмета, а в третьем и четвертом - по 3 предмета. Сколькими
способами это можно сделать?
104.	Требуется закодировать три сообщения. Первое решено
закодировать двумя десятичными цифрами а1 и а2, второе -
цифрами а3, а4, а5, третье - а6, а7, а8. Все восемь цифр являются
различными. Сколько существует способов выбора цифр для
кодирования сообщений, если используются десятичные цифры
1, 2, ..., 8?
105.	Найти число всех беспорядков, если упорядоченное
множество содержит шесть элементов.
106.	Сколько существует пятизначных чисел, в которых по
одному разу встречаются цифры 1,2,3,4,5, если цифра 1
находится не на первом месте, цифра 2 - не на втором, цифра 3 -
69

не на третьем, цифра 4 - не на четвертом и цифра 5 - не на
пятом?
107.	Найти число беспорядков для элементов множеств
А={0|; А = {0,3}; А= {0,{0}|.
108.	Секретарь подготовил восемь конвертов для восьми
различных писем и отправил их по восьми различным адресам.
Вскоре выяснилось, что в половине конвертов оказались не те
письма. Сколькими способами могла осуществиться такая
ситуация?
109.	Для десяти различных приборов приготовили десять
табличек с названием каждого прибора. Когда таблички
прикрепили, оказалось, что названия соответствуют только
первым семи приборам, а остальные таблички оказались
перепутанными. Сколькими способами могла осуществиться
такая ситуация?
110.	Чтобы передать сообщение, 33 буквы русского алфавита
пронумеровали в последовательности 1,2,3,...,33 и вместо букв
стали передавать их номера. Однако в кодирующем устройстве
возникла неисправность, и у одной из букв код оказался другим,
но не превышающим 33. Сколькими способами это могло
произойти?
111.	Число 16! оканчивается n нулями. Найдите число n.
112.	Укажите простые делители числа а: а=35; а=231; а=170.
113.	Укажите все простые множители (с учетом их повторов)
числа а, если а = 28; а = 250; а = 539.
114.	Укажите наименьшее простое число, являющееся
делителем числа: 900; 10 011; 911 121.
70

115.	Сколько существует делителей числа: 2625; 360; 512;
375;392;23?
116.	Сколько существует способов разбиения на слагаемые
числа 5 при условии, что порядок слагаемых учитывается и что
каждая сумма начинается:
-	с единицы (например, 1 + 2 + 2)?
-	с цифры 2 (например, 2 + 3)?
-	с цифры 3?
-	с цифры 4?
-	с цифры 5?
117.	Сколько существует вариантов разбиения на слагаемые
числа 8 при условии, что учитывается порядок слагаемых и что
каждое разбиение содержит:
-	три слагаемых?
-	четыре слагаемых?
-	пять слагаемых?
-	шесть слагаемых?
118.	Сколько существует вариантов разбиения на слагаемые
числа 5, если учитывается порядок слагаемых и в каждом
разбиении содержится хотя бы одна цифра: 1? 2? 3? 4?
119.	Найдите все способы разбиения числа 6 на слагаемые
при условии, что порядок записи слагаемых не имеет значения.
Определите:
-	число разбиений, имеющих по три слагаемых;
-	число разбиений, имеющих более двух слагаемых;
-	число всех разбиений.
71

120.	То же самое, что и в упражнении 4, выполните для числа
9.	Найдите число:
-	разбиений, содержащих по три слагаемых;
-	разбиений, содержащих	по четыре слагаемых;
-	разбиений, содержащих	по пять слагаемых;
-	всех слагаемых.
121.	Сколько трехзначных чисел можно составить из цифр
1,	2, 3, 4, 5, если каждую из них можно использовать не более
одного раза?
122.	Сколько имеется пятизначных чисел, которые делятся
на 5?
123.	На одной из боковых	сторон треугольника	взято	n
точек, на другой — m точек. Каждая из вершин при основании
треугольника соединена прямыми с точками, взятыми на
противоположной стороне.
а)	Сколько точек пересечения этих прямых образуется
внутри треугольника?
б)	На сколько частей делят треугольник эти прямые?
124.	Сколько есть двузначных чисел, у которых обе цифры
четные?
125.	Пассажир оставил вещи в автоматической камере
хранения, а когда пришел получать вещи, выяснилось, что он
забыл номер. Он только помнит, что в номере были числа 23 и
37.	Чтобы открыть камеру, нужно правильно набрать
пятизначный номер. Какое наибольшее количество номеров
нужно перебрать, чтобы открыть камеру?
126. Из колоды, содержащей 52 карты, вынули 10 карт.
В скольких случаях среди этих карт окажется:
72

а)	хотя бы один туз;
б)	ровно один туз;
в)	не менее двух тузов;
г)	ровно два туза?
127.	Дано п точек, никакие три из которых не лежат на
одной прямой. Сколько прямых можно провести, соединяя точки
попарно?
128.	В соревнованиях по гимнастике две команды имели
одинаковое число участников. В итоге общая сумма баллов,
полученных всеми участниками, равна 156. Сколько было участ¬
ников, если каждый из них получил оценки только 8 или 9 бал¬
лов?
129.	В некотором царстве каждые два человека отличаются
набором зубов. Какова может быть наибольшая численность
населения царства (максимальное количество зубов у
человека - 32).
130.	В роте имеется три офицера и сорок солдат. Сколькими
способами может быть выделен наряд, состоящий из одного
офицера и трех солдат?
131.	На рояле 88 клавиш. Сколько существует
последовательностей из шести попарно различных звуков?
(В последовательности звуки идут один за другим). Сколько
существует аккордов из шести звуков? (Аккорд получается, если
любые 6 клавиш нажаты одновременно).
132.	Сколько существует чисел от 0 до 10п, в которые не
входят две подряд идущие друг за другом одинаковые цифры?
133.	Сколькими способами можно выбрать 6 карт из колоды,
содержащей 52 карты, чтобы среди них были карты всех мастей?
73

134. Какова вероятность, купив один билет, угадать в
спортлото (из 49):
а)	k номеров (k = 1,2,...,6);
б)	хотя бы k номеров?
135.	Сколькими способами можно посадить за круглый стол
n мужчин и n женщин так, чтобы никакие два лица одного пола
не сидели рядом?
136.	Сколькими способами можно разложить в два кармана
девять монет различного достоинства?
137.	Сколько различных делителей имеет число:
а)	2310;
б)	10!?
138.	У англичан принято давать детям несколько имен.
Сколькими способами можно назвать ребенка, если ему дадут не
более трех имен, а общее число имен равно 300?
139. На прямой взяты 9 точек, а на параллельной ей прямой
еще 5 точек. Сколько существует треугольников, вершинами
которых являются эти точки?
140.	Международная комиссия состоит из 9 человек.
Материалы комиссии хранятся в сейфе. Сколько замков должен
иметь сейф, сколько ключей для них нужно изготовить и как их
разделить между членами комиссии, чтобы доступ к сейфу был
возможен тогда и только тогда, когда соберутся не менее 6
членов комиссии?
141.	Пусть n и т — целые положительные числа. Доказать
n
а)	Z kC" = n • 2"-|;
k =1
74

б) I k(k - 1)Cnk = n ■ (n -1) • 2n-2;
k=2
n
в) I (2k + 1)C' = (n +1) ■ 2n.
k=0
142.	Доказать тождества:
n
n -1	n -1
а)	C2n-1 - 2-і C2n-i-1 ;
i-1
n
б)	c';1 - z c'-
i	-1
ii-1
n С -1	2
143. Доказать, что I —n-^  	, n > 1.
&	Cin-1	n + 1
144.	Найти производящие функции таких
последовательностей:
а)	an = nan ,п = 0,1,2...;
0,	п — 0,
б) an = і
а' і 2
—	,п = 1,2,...;
п!
в)	ап = п2 ,п = 0,1,2...;
IX п - 0,1,..., N,
г)	ап = і
п	[0,п > N;
д)	ап = sinan,n = 0,1,2....
145.	Найти производящую функцию последовательности
{ап} через производящую функцию последовательности {bn},
если
І0, п - 0,
а) ап = і
[bn-1 ,п =1,2
75

б)	an_ Xbi,n_ 0,1,2...;
і
в)	an _
0, п = 0,1,2к -1,
bn—k,n ^ k;
г)	an _ bn+j — bn,n_ 0,1,2...;
146.	Найти экспоненциальную производящую функцию
последовательности {an}, выраженную через производящую
функцию последовательности {bn}, если
а)	an_bn+1 ,п_ О,1,2...;
п
б)	an_ X Crnbn—r8r’n_ 0,:1,2”.
r_0
147.	Сколькими способами можно разменять 10-копеечную
монету монетами 1, 2, 3 и 5 копеек при условии, что каждая из
разменных монет присутствует в двух экземплярах?
148.	Пусть fa (t) и fb (t)	- производящие функции
последовательностей {an }и {bn} соответственно и пусть
fa (t) • fb (t) = 1 Найти {bn }и fb (t)» если an _ cm .
149.	Четыре человека сдают свои шляпы в гардероб.
В предположении, что шляпы возвращаются наугад, найти
вероятность того, что в точности k человек получат свои шляпы
назад. Рассмотреть все значения к(0 < к < 4).
150.	При обследовании читательских вкусов оказалось, что
60% студентов читают журнал А, 50%— журнал В , 50% —
журнал С, 30% — журналы А и В , 20% — журналы В и С,
40% — журналы А и С, 10% — журналы А, В и С. Сколько
процентов студентов:
а)	не читает ни одного журнала;
76

б)	читает в точности два журнала;
в)	читает не менее двух журналов.
151.	Найти число целых положительных чисел, не
превосходящих 100 и не делящихся ни на одно из чисел 3, 5 и 7.
152.	Показать, что если n = 30т, то количество целых
положительных чисел, не превосходящих n и не делящихся ни на
одно из чисел 6, 10, 15, равно 22т.
153.	В классе 35 учащихся. Из них 20 посещают
математический кружок, 11 — физический, 10 учащихся не
посещают ни один из этих кружков. Сколько учеников посещают
и математический, и физический кружок? Сколько учащихся
посещают только математический кружок?
154.	Сколькими способами можно расположить за круглым
столом n супружеских пар так, чтобы мужчины и женщины
чередовались и никакие двое супругов не сидели рядом?
155.	В букинистическом магазине лежат 6 экземпляров
романа И.С. Тургенева «Рудин», 3 экземпляра его же романа
«Дворянское гнездо» и 4 экземпляра романа «Отцы и дети».
Кроме того, есть 5 томов, содержащих романы «Рудин» и
«Дворянское гнездо», и 7 томов, содержащих романы
«Дворянское гнездо» и «Отцы и дети». Сколькими способами
можно сделать покупку, содержащую не менее чем по одному
экземпляру каждого из этих романов?
156.	Сколько существует автомобильных номеров,
содержащих 3 буквы и 5 цифр, если используется 20 букв
русского алфавита и все 10 цифр?
157.	Сколько существует 7-разрядных чисел, в первых трех
разрядах которых нет цифр 0, 8, 9?
77

158.	Время работы агрегата в течение суток задается
часами, минутами и секундами. Сколько разных временных
интервалов может быть задано для работы агрегата?
159.	Из коллектива работников кооператива в 20 человек
нужно выбрать председателя, заместителя председателя,
бухгалтера и казначея. Каким количеством способов это можно
сделать?
160.	В парламент нового независимого государства нужно
представить для рассмотрения варианты флагов (для
определенности - три горизонтальные полосы). Сколько
вариантов флагов можно представить, если каждый флаг должен
содержать три разных цвета, а количество цветов имеющегося
материала равно 12?
161.	На дискотеку пришли 12 девушек и 15 юношей.
Объявлен «белый» танец. Все девушки выбрали для танцев
юношей (и никто из них не отказался). Сколько могло
образоваться разных танцующих пар?
162.	Сколько различных слов (пусть и не имеющих смысла)
можно получить, переставляя буквы слова ДУБЛЕНКА?
163.	В заезде на ипподроме участвуют 12 рысаков.
Играющие в тотализатор заполняют карточки, в которых
указывают порядок, в котором, по их мнению, рысаки придут к
финишу. Будем считать, что к финишу одновременно не могут
прийти два и более рысака. Сколько вариантов заполнения
карточек существует?
164.	На заседании Думы 14 депутатов записались на
выступления. Сколько вариантов списков выступающих может
быть составлено, если списки отличаются только порядком?
78

165.	Подсчитайте количество расстановок в списках
выступающих для предыдущего примера, если известно, что
некоторые депутаты, например Ж, З и Я, пользуясь своим
влиянием в секретариате, уже обеспечили себе места в списках,
соответственно 3, 6 и 7.
166. У школьника 2 авторучки, 4 карандаша и 1 резинка. Он
раскладывает эти предметы на парте в ряд. Сколько вариантов
раскладки?
167.	Рыбаки поймали 5 подлещиков, 4 красноперки и 2
уклейки, посолили и вывесили на солнце сушиться. Сколько
вариантов развешивания рыбы на нитке?
168.	На узком участке трассы в линию движутся гонщики.
Из них 5 - на российских автомобилях, 6 - на американских и 3 -
на итальянских. Сколько существует разных комбинаций машин
на трассе, если нас интересует только принадлежность
автомобиля конкретной стране?
169.	Пароль состоит из двух букв, за которыми следуют 4
цифры, или из четырех букв, за которыми следуют 2 цифры.
Сколько можно составить разных паролей, если из 33-х букв
русского алфавита используются только буквы: {а, б, в, г, д, е, ж,
и,	к, л, м, н} и все 10 цифр? А сколько можно получить разных
паролей, если из множества букв исключить дополнительно
буквы а, е и л, а к десяти цифрам добавить символ *?
170.	У перевозчика через реку в лодке имеется 6 мест для
пассажиров. Подходит веселая компания из семи мужчин и
четырех женщин и просит перевезти хотя бы часть людей на
другой берег. Перевозчик ставит условие, чтобы в лодку село не
79

менее двух женщин. Сколько вариантов у перевозчика посадить в
лодку часть компании?
171.	В механической мастерской работают 12 человек, из
них 6 человек имеют дипломы слесаря, 4 - дипломы оператора
станков с ЧПУ, 7 человек - дипломы фрезеровщика, 3 человека
владеют двумя из перечисленных дипломов и 2 человека - всеми
тремя. Начальство решило уволить работников, не имеющих
дипломов хотя бы по одной из этих специальностей. Имеется ли
такая возможность?
172.	Найти количество чисел, не делящихся на 3, 5 и 7, в
диапазоне от 200 до 500.
173.	Входной алфавит абстрактного конечного автомата
содержит 5 символов, например a, b, c, d, e. Входные слова имеют
длину в 11 символов. Сколько разных слов может быть подано на
вход конечного автомата, если слова, имеющие одинаковый
состав букв и различающиеся только порядком, считать
одинаковыми? Например, слова baabce и eabcba считаются
одинаковыми.
174.	Граф-схема алгоритма микропрограммного автомата
содержит операторные и условные вершины. Операторные
вершины «начало» и «конец» являются обязательными. Сколько
существует различных граф-схем алгоритмов, содержащих 6
вершин, если нас интересует только количественный состав, а не
связи между вершинами?
175. У человека, спустившегося с гор, есть 5 баранов,
которых он хочет раздать своим 8 сыновьям. Ему нужно найти
число способов раздачи целых баранов, если:
80

а)	каждый сын может получить либо одного барана, либо
ничего;
б)	число баранов, которые получают сыновья, неограничено
(но, естественно, не превышает 5).
176.	Некоторый банк имеет 3 «свободных» миллиона и
готов раздать их 5 клиентам. Правление банка принимает
решение о выдаче ссуды, кратной 0,25 миллиона. Сколько
существует способов выдачи ссуд?
177.	Полный дешифратор имеет п входов и 2п выходов.
Сколько выходов будет иметь дешифратор на 5 входов, если
исключить все выходы, соответствующие равновесным входным
наборам из двух и четырех единиц?
178.	В некотором государстве не было двух жителей с
одинаковым набором зубов. Сколько жителей могло быть в этом
государстве, если во рту человека не может быть больше 32-х
зубов?
179.	Вычислите значения субфакториалов для
п = 11, 12, 13, 14.
180.	Имеется 7 различных предметов. В каком числе
перестановок этих предметов ровно 3 предмета находятся на
своих местах, а остальные - на чужих?
181.	Электромонтажник забыл дома схему и монтирует
12-контактный разъем наугад. В каком числе комбинаций
правильно будут припаяны ровно 4 провода, а остальные -
неверно? Если считать, что вероятность некоторого дискретного
события P может быть определена отношением числа
благоприятных комбинаций к общему числу комбинаций, тогда
можно оценить вероятность этого события. Определите эту
81

вероятность, если общее число комбинаций в данном случае
равно 12!
182.	Пусть имеется последовательность некоторых чисел a1,
a2, a3, ..., an. В каком количестве перестановок не встречается ни
одной подряд стоявшей пары?
183.	В каком количестве перестановок чисел предыдущего
примера встречается ровно 5 пар чисел, которые находились
рядом в исходной расстановке?
184.	Один из трех игроков в преферанс хочет сыграть
«мизер». Для этого ему нужно, чтобы в прикупе находилась либо
бубновая семерка, либо семерка треф, либо они вместе. Найдите
количества вариантов такого расклада. Определите вероятность
этого события.
185.	Определите количество вариантов расклада при игре в
НИМ, когда в любой кучке есть хотя бы одна (две, три) спички.
186.	Сколько разных делителей имеют числа: 1350, 1617,
8280, 10013?
187.	Сколько разных делителей, кратных 102, имеют число
62424?
188.	Четверо грибников, гуляя по лесу, собрали 12
подберезовиков, 8 белых, 11 волнушек и 15 сыроежек. При
разделе грибов решили, что каждый должен получить не менее
чем по 2 подберезовика, по 1 белому, 2 волнушки и 3 сыроежки.
Сколько вариантов раздела грибов?
189.	Имеется 8 флагов и 4 мачты. Подсчитайте количество
разных сигналов, которые можно передать.
190.	В скольких 7-разрядных числах все цифры различны?
82

191.	Сколько чисел от 1 до 900 не делится ни на 3, ни на 7,
ни на 11?
192.	На загородную прогулку выехали 92 человека.
Бутерброды с колбасой взяли 48 человек, с сыром - 38, с
ветчиной - 42, с сыром и колбасой - 28, с колбасой и ветчиной -
31,	с сыром и ветчиной - 26. 25 человек взяли с собой все три
вида бутербродов. Сколько человек взяли пирожки?
193.	Сколько разных делителей, кратных 10, имеет число
3350?
194.	Четыре числа сложили всеми возможными способами
по 2 и получили 6 сумм: 2, 4, 9, 9, 14, 16. Найдите эти числа.
195.	У мамы 3 яблока, 4 груши и 4 апельсина. Каждый день
в течение 11 дней подряд она выдает дочери по одному фрукту.
Сколькими способами она это может сделать?
196.	Найдите число способов наклейки марок достоинством
в 3, 5 и 10 копеек так, чтобы общая сумма была равна 16
копейкам.
197. Имеется 4 утки, 3 курицы и 2 гуся. Сколькими
способами можно выбрать из них несколько птиц так, чтобы
среди выбранных были и утки, и куры, и гуси?
198.	Найдите и выпишите все перестановки из букв X, Y, Z,
при которых ни одна буква не остается на своем месте. А сколько
существует перестановок из букв a, b, c, d, e, при которых ровно
одна из них на своем месте?
199.	Из колоды в 52 карты двое игроков выбирают по 4
карты каждый. Сколько существует различных вариантов
выбора? В скольких случаях один из игроков получает 4 туза, а
другой - 4 короля?
83

200.	Сколько 6-разрядных чисел содержат ровно 3
различные цифры? Сколько n-разрядных чисел содержат ровно k
различных цифр?
201.	Сколько чисел, меньших миллиона, можно записать с
помощью цифр 9, 8, 7. А с помощью цифр 9, 8, 0, если число не
может начинаться с 0?
202.	Сколькими способами можно переставить буквы слова
ЮПИТЕР так, чтобы гласные шли в алфавитном порядке?
203.	Сколькими способами можно переставить буквы слова
КАРАКУЛИ так, чтобы никакие две гласные не стояли рядом?
204.	Сколько разных делителей, кратных 21, имеет число
525?
205.	Имеется 11 тетрадей, 7 авторучек и 5 комплектов
контурных карт. Сколькими способами можно выбрать из них
несколько предметов так, чтобы среди выбранных были все
имеющиеся виды предметов?
206.	Сколько 8-разрядных чисел содержат ровно 3
различные цифры? Сколько n-разрядных чисел содержат ровно k
различных цифр?
207.	Сколькими способами можно переставить буквы слова
САЛАМАНДРА так, чтобы никакие две гласные не стояли
рядом?
208.	В компании 7 мужчин и 5 женщин. Сколько вариантов
выбора группы, в которой было бы не менее 3-х женщин?
209.	Сколько разных ожерелий можно составить из
5	изумрудов, 3 рубинов и 7 сапфиров?
210.	В скольких 7-разрядных числах все цифры различны?
84

211.	На книжной полке 15 книг. Сколько существует
способов взять с полки 7 книг, которые не стояли рядом? А 12
книг?
212.	Сколько существует способов раздачи 7 авторучек 8
ученикам без ограничения числа авторучек, передаваемых
каждому?
213.	Сколько существует перестановок из букв a, b, c, d, e, f,
при которых ровно 2 буквы остаются на месте, а остальные - на
чужих?
214.	В отчете профкома написано: в отделе 7 человек имеют
сыновей, 8 - дочерей, 4 - человека и сыновей и дочерей, 1 не
имеет детей. Число работающих в отделе не было указано.
Сколько человек работает в отделе?
215.	Сколькими способами можно переставить буквы слова
САТУРН так, чтобы гласные шли в алфавитном порядке?
216.	За круглым столом короля Артура сидят 15 рыцарей.
Сколько существует способов выбрать из них 6 таких, которые не
сидели рядом за столом?
217.	Сколько слов можно составить из трех букв а, двух
букв b и одной буквы с?
218.	Имеется 9 предметов. В скольких перестановках точно
2	предмета остаются на месте?
219.	Сколько четных делителей имеет число 1520?
220.	На карусели имеется 8 мест. Сколько существует
разных способов рассадки детей, если все места будут заняты?
221.	Сколько чисел от 1 до 1678 не делится ни на 3, ни на 5,
ни на 13?
85

ЧАСТЬ III. ТЕОРИЯ ГРАФОВ
Теория графов применяется при анализе функционирования
сложных систем, например, сетей железных и автомобильных
дорог, компьютерных и телефонных сетей и т.д. Теория графов
является эффективным аппаратом формализации задач
экономической и производственной практики, применяется в
автоматизации управления производством и сетевом
планировании.
Первой работой, в которой использовалось название «граф»
и давалось его точное определение, была работа Л. Эйлера,
которая появилась в 1736 году в трудах Петербургской академии
наук. В ней Эйлер предлагает читателю головоломку «Задача о
кёнигсбергских мостах» (рис. 6,a). Задача состоит в том, можно
ли, выйдя из одного района города, по одному разу пройти по
каждому из мостов и вернуться в исходный район? Эта задача
может быть изображена в виде графа (рис. 6,Ь).
Графом называется пара (V, E), где V - множество вершин,
E - множество инцидентных им ребер. Под степенью вершины
1.	Основные понятия теории графов
с
Рис. 6. «Задача о Кёнигсбергских мостах»
86

графа понимается число ребер, инцидентных этой вершине
(связанных с ней). Порядком графа называется число его вершин.
Две вершины графа называются смежными, если они соединены
ребром. Если вершина является концом ребра, то вершина и
ребро называются инцидентными. Вершина, степень которой
равна 1, называется висячей.
Граф называется простым, если любые две его вершины
соединены не более чем одним ребром, и каждое ребро соединяет
различные вершины. Ребра, которые соединяют одну и ту же
пару вершин, называются кратными, или параллельными. Ребро,
которое соединяет вершину саму с собой, называется петлей.
Вершина называется изолированной, если у нее нет петель и
из нее не выходит ни одного ребра.
Граф, содержащий петли или кратные ребра, называется
псевдографом. Псевдограф без петель называется мультиграфом.
Если из графа G удалить одну или несколько вершин, то
будут удалены и выходящие из них ребра. Оставшиеся вершины
и ребра образуют подграф G’ графа G.
Если в граф G добавить одну или несколько вершин и
соединить их каким-либо образом с другими вершинами графа,
то получим надграф графа G.
Граф, в котором нет ни одного ребра называется нуль-
графом.
Граф называется однородным, если степени всех его вершин
равны между собой. Число ребер однородного графа равно
K = Pl,
2
где р - степень вершины, n - число вершин.
87

Граф без петель называется полным, если каждая пара его
вершин соединена одним ребром. Число ребер полного графа
равно:
к= п(п -1)
2 .
Пример 1. Определить число ребер полного графа, число
вершин которого равно 7.
Решение. Определяем по последней формуле:
K = 7( 72 1) =21 (ребро).
Дополнением графа G называется граф G, в котором
вершин столько же, сколько и в графе G, причем любые две
несовпадающие вершины смежны в G тогда и только тогда,
когда они не смежны в G.
Пример 2. Найти дополнение для графа G1 = {У1 ,E1}.
2 і
4	5
Решение. Чтобы найти обратный граф или дополнение,
нужно дополнить данный граф до полного и удалить все ребра,
которые уже были до этого. Дополнение G будет иметь вид
2 1
88

Два графа G1 и G2 называются изоморфными, если между
множеством их вершин существует такое взаимно однозначное
соответствие, при котором в одном из графов ребрами соединены
вершины в том и только том случае, если в другом графе ребрами
соединены те же вершины. Примером изоморфных графов могут
служить графы, изображенные на рис. 7.
al	g2
Рис. 7. Изоморфные графы
Ребра графа, которые имеют направление, называются
дугами.	Граф, содержащий только	дуги,	называется
ориентированным графом, или орграфом.
Маршрутом длины n называется непустая
последовательность n ребер вида v1,e1,v2,e2,v3,e3,...,vn,en,vn+1,
где ребро ej(j = 1,2,...,n) соединяет вершины Vj и Vj+1 .
Маршрут называется цепью, если в нем нет повторяющихся
ребер. Цепь называется простой, если в ней нет повторяющихся
вершин (лишь первая и последняя вершины могут совпадать).
Замкнутая цепь называется циклом. Простая замкнутая цепь
называется простым циклом.
89

2. Операции над графами
1.	Объединение графов. Объединением двух графов
G1 = {V1 ,E1} и G2 = {V2,E2} называется граф G = G1 и G2 = {V,E},
V = V1 и V2 ;E=E1 и E 2.
Пример 3. Построить объединение графов.
Решение. Объединением этих графов будет граф:
2.	Пересечение графов. Пересечением двух графов
Gl = V ,E,}	и	G 2 = {V2 ,E2 }	называется граф
G = G1 n G2 = {V,E}, V = V1 n V2;E= E1 n E2.
Пример 4. Построить пересечение графов.
90

Решение. Пересечением этих графов будет граф:
3.	Произведение графов. Граф G = {V,E} называется
произведением G1 х G2 графов G1 и G2, причем V = V1 х V2 -
декартово произведение множеств вершин исходных графов, а
множество ребер получается следующим образом: вершины
(x1 ,x2) и (y1 ,y2) смежны в графе G тогда и только тогда, когда
или x1 = у1, а х2 и у2 смежны в G2, или x2 = у2, а х1 и у1
смежны в G1.
3.	Способы задания графов
Вместо графического представления графов при решении
разнообразных оптимизационных задач применяют различные
эквивалентные способы задания. Основным требованием
является взаимная однозначность графического изображения и
выбранного способа задания.
Чаще всего используются следующие виды задания графа:
-	матрица (таблица) инциденции (инцидентности);
-	матрица (таблица) смежности.
Рассмотрим эти виды задания.
1.	Матрица инцидентности. Нумеруются все ребра графа
(например, арабскими цифрами) и все вершины (например,
91

буквами). Строится матрица, каждой строке которой
сопоставляется вершина, а каждому столбцу - ребро. Символами
(например, единицами), отмечаются вершины, связанные
ребрами.
В случае неориентированного графа элементами матрицы
будут числа 0 и 1, т. е.
1,	вершина xt инцидентна ребру Uj,
0,	вершина xt не инцидентна ребру u j.
При построении матрицы инциденции для
ориентированного графа необходимо указать направление
перехода. Элементы rij этой матрицы равны +1, если дуга Uj
исходит из i-й вершины (начальная вершина), -1, если дуга Uj
входит в i-ю вершину (концевая вершина), 0, если дуга Uj не
инцидентна i-й вершине.
т =
ij
Пример 5. Построить матрицы инцидентности для графов.
Решение. а) Имеется обычный граф, следовательно, его
матрица инцидентности будет состоять из нулей и единиц.
Представим ее в виде таблицы: строки - вершины, столбцы -
ребра.
92

1
2
3
4
5
6
7
8
А
1
0
0
0
0
0
1
0
B
1
1
0
0
0
0
0
1
C
0
1
1
0
1
0
0
0
D
0
0
1
1
0
0
0
0
E
0
0
0
1
1
1
0
0
F
0
0
0
0
0
1
1
1
b) Имеется ориентированный граф, следовательно? его
матрица инцидентности будет иметь вид
1
2
3
4
5
6
7
A
1
0
1
0
1
0
1
B
-1
1
0
0
0
0
0
C
0
-1
-1
1
0
0
0
D
0
0
0
-1
-1
-1
0
E
0
0
0
0
0
1
-1
2.	Матрица смежности вершин. Матрица смежности
представляет собой квадратную матрицу размера п х п, где п -
число вершин графа. Ее строки и столбцы соответствуют
вершинам графа. Элементы pij матрицы смежности вершин
равны числу дуг, идущих из i-й вершины в j-ю. Если орграф не
содержит параллельных дуг, то матрица является бинарной и
состоит только из нулей и единиц. В случае неориентированного
графа матрица смежности вершин будет симметрической.
93

Пример 6. Построить матрицу смежности для графа.
Решение. Матрицу смежности для этого графа можно
представить в виде таблицы:
А
B
C
D
E
F
A
0
1
0
0
0
1
B
1
0
1
0
0
1
C
0
1
0
1
1
0
D
0
0
1
0
1
0
E
0
0
1
1
0
1
F
1
1
0
0
1
0
4.	Задания для самостоятельного выполнения
1.	Показать, что для произвольного графа G = (S, U Справед¬
ливо равенство £ P(x) = 2|U .
xeS
2.	Для графов, изображенных на рисунке, составить матрицы
смежности вершин, смежности дуг и инциденций.
94

3.	По матрице смежности вершин построить наглядные
изображения графов.
а)
(1
1
2
0
0 >
1
0
1
3
0
2
1
1
0
2
0
3
0
1
1
V 0
0
2
1
0 ,
в)
(1
0
0
1
1 "I
0
0
1
1
0
0
0
0
0
1
0
0
1
1
0
V1
0
1
1
1,
б)
г)
(0
2
1
0
0
2 л
2
0
1
1
0
0
1
1
1
0
2
1
0
1
0
0
1
1
0
0
2
1
1
2
V2
0
1
1
2
0 ,
(0
1
0
0
1
1 >
1
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
1
V1
0
0
1
1
0,
4.	На рисунке приведены графы G1 и G2. Найти G1 и G2 и
G1 х G2.
в
95

5. Найти матрицы сильных компонент и маршрутов длины
три дуги (ребра), исходящих из вершины Х1, для графов,
изображенных на рисунке.
6. Упорядочить вершины и дуги орграфов, изображенных
на рисунке, графическим и матричным способом (дуги — только
графическим способом).
7.	Доказать, что три графа, изображенных на рис. 8,
изоморфны, а графы на рис. 9 неизоморфны.
96

xe *6	X,	xs
Рис. 9.
8.	Построить граф, центр которого;
а)	состоит ровно из одной вершины;
б)	состоит ровно из трех вершин и не совпадает с
множеством всех вершин;
в)	совпадает с множеством всех вершин.
9.	Показать, что в любом графе без петель и кратных ребер,
содержащем не менее двух вершин, найдутся две вершины с
одинаковыми степенями.
10.	Определим графы Gn следующим образом.
Пусть Gn - граф, множество вершин которого совпадает с отрез¬
ком натурального ряда {l,2,...,10}, а множество ребер определя¬
ется следующим условием: несовпадающие вершины х и у смеж¬
ны тогда, когда числа х и у взаимно просты. При каких значениях
п графы Gn планарны?
97

11.	Какие из графов, изображенных на рисунке, являются
планарными?
а
б
в
12.	Определить хроматические числа графов, изображенных
на рисунке.
13.	Граф называется критическим, если удаление любой из
его вершин приводит к графу с меньшим хроматическим числом.
Показать, что Kn является критическим графом при n > 1, а Cn -
тогда и только тогда, когда n нечетно. Cn - простой цикл,
содержащий n вершин.
14.	Приведите пример графа, последовательная раскраска
вершин которого не является минимальной.
15.	Укажите номера всех пар вершин, являющихся
смежными:
а
б
в
1) 1 и 2; 3) 3 и 4; 5)1 и 7; 7) 6 и 7;
2) 1 и 5; 4) 3 и 5; 6) 2 и 7; 8) 2 и 1.
98

16. Укажите номера всех пар ребер, являющихся смежными:
1)	{1,	4}	и {2, 5}; 4)	{1,	7}	и {2, 7};
2)	{3,	4}	и {4, 5}; 5)	{2,	6}	и {5, 7};
3)	{4,	6}	и {2, 6}; 6)	{2,	6}	и {2, 5}.
17.	Укажите номера	вершин, инцидентных ребру {2, 6}.
18.	Сумма степеней всех вершин некоторого графа равна 20.
К этому графу добавили три ребра (число вершин не меняли).
Чему равна сумма степеней всех вершин нового графа? Сколько в
нем ребер?
19.	Укажите номера вопросов, на которые вы ответите «да»:
1)	существуют ли графы, в которых степень каждой
вершины равна нулю?
2)	можно ли построить граф, в котором число четных
вершин нечетно?
3)	существует ли граф, содержащий одну вершину и одно
ребро?
4)	существуют ли смежные вершины в нуль-графе?
5)	можно ли построить граф, в котором одна нечетная
вершина и три - четные?
99

20.	Для любого графа можно указать набор степеней его
вершин. Например, 0223230, где 0 - это степень первой вершины,
2 - степень второй вершины, следующая цифра 2 - степень
третьей вершины и т. д. Но если набор задан, то построить
соответствующий граф не всегда возможно. Укажите из
нижеперечисленных
номера тех наборов,
для которых
невозможно построить граф:
а) 1) 0 1 1 0 2 3 2
б) 1) 1 1 3 4 5 7 6 в)
1) 1 0 1 4 5 6 7
2) 1 1 1 0 1 3 3
2) 2 2 0 1 0 1 7
2) 1 2 3 4 1 2 3
3) 2 1 3 3 4 4 4
3) 6 9 9 4 1 3 2
3) 0 0 1 0 0 0 0
4) 0 0 1 1 0 1 5
4) 5 6 7 3 3 4 5
4) 2 2 2 1 2 2 2
5) 2 3 3 2 1 3 3
5) 2 6 7 3 3 3 0
5) 0 7 0 7 1 0 7
6) 4 2 1 0 7 3 0
6) 3 0 0 3 0 0 3
6) 2 3 5 6 7 4 2
7) 2 5 5 1 1 1 0
7) 0 0 1 1 0 1 7
7) 3 4 5 4 3 2 1
21.	Сколько ребер в однородном графе, если n = 7 и р = 6?
22.	Найдите числа пир однородного графа, если он
содержит 19 ребер.
23.	Укажите номера вопросов, на которые вы ответите «да».
Возможен ли однородный граф, в котором:
1)	пять вершин и степень каждой вершины равна 3?
2)	шесть вершин и степень каждой из них равна 4?
3)	четыре вершины и шесть ребер?
4)	пять вершин и шесть ребер?
5)	семь вершин и степень каждой вершины равна 5?
6)	шесть вершин и девять ребер?
7)	восемь вершин и степень каждой из них равна 3?
24.	В полном графе 18 вершин. Сколько в нем ребер,
инцидентных одной вершине?
100

25.	Сколько ребер имеет полный граф, если число его
вершин равно 10?
26.	Полный граф имеет 105 ребер. Найдите число его
вершин.
27.	Частичный граф полного графа, насчитывающего 12
вершин, имеет 54 ребра. Сколько ребер имеет дополнение
частичного графа?
28.	Из полного графа на 20 вершинах несколько вершин
удалили. В оставшемся подграфе стало 66 ребер. Сколько вершин
удалено? Сколько ребер удалено?
29.	Степень вершины полного графа равна 7. Из графа
удалили несколько ребер так, что степень каждой вершины
получившегося частичного графа стала равной 5. Сколько ребер
удалили? Сколько ребер осталось?
30.	Найдите степень вершины полного графа, имеющего 91
ребро.
31.	В однородном графе степень вершины равна 5. Число
ребер равно 35. Найдите число вершин.
32.	Каждую вершину полного графа G, имеющего 28 ребер,
соединили ребром с каждой вершиной полного графа G.
Получился граф, насчитывающий 55 ребер. Сколько вершин в
графе G ? Сколько ребер соединяют вершины графа G с
вершинами графа G ?
33.	Графы G1, G2 и G3 представлены в виде:
G1 = {Уь Е1}, где V = {1,2,3,4,5,6};
Е1 = {{1, 2},{1, 3},{1, 4},{2, 3},{2, 6},{3, 5},{3, 6},{5, 6}};
G2 = {V2, Е2}, где V2 = {1,2,3,4,5,6,7,8};
Е2 = {{1,4},{2,3},{3,5},{3,6},{5,6},{5,7},{5,8},{6,7},{6,8}};
101

G3 = (У3, Е3}, где V3 = {3,4,5,6,7,8,9};
Е3 = {{3,5},{3,6},{3,8},{4,6},{5,6},{5,7},{6,7},{7,8},{7,9},
(8,9}}.
1)	Найдите число вершин и число ребер графа:
-	G = G1 u G2 ;
-	G = G1	UG2 nG3;
-	G = G1	UG2 UG3;
-	G = (G1UG2) n G3;
-	G = G1nG2;
-	G = G1 n (G2 u G3).
2)	Укажите вершины графа:
-	G = G1	UG1 nG2;
-	G = G2	UG1 nG2 UG1 nG2	nG3;
-	G = G1	nG2 UG1 nG2 UG2	nG3.
34.	Укажите номера графов, являющихся изоморфными
графу, приведенному на рис. Б.
А	Б
35.	На какие вопросы вы ответите «да»:
1)	могут ли быть изоморфными графы, не содержащие
ребер?
2)	даны два полных графа с одинаковым числом вершин.
При всякой ли нумерации вершин сохраняются условия
изоморфизма этих графов?
102

3)	даны два однородных графа с одинаковым числом
вершин. Всякая ли нумерация вершин этих графов удовлетворяет
условиям изоморфизма?
4)	применимо ли понятие изоморфизма к псевдографам?
5)	может ли непустой граф быть изоморфным своему
подграфу?
6)	может ли частичный граф быть изоморфным нуль-графу
на том же числе вершин, что и частичный граф?
7) является ли изоморфизм отношением эквивалентности?
36. Укажите вершины, инцидентные ребру а.
a
b
c
d
e
f
к
l
m
n
1
1
2
1
2
2
1
3
1
2
1
1
4
1
1
1
1
1
5
1
1
1
37. Укажите номера вершин, содержащих петли.
a
b
c
d
e
f
к
l
m
n
1
1
2
1
2
2
1
3
1
2
1
1
4
1
1
1
1
1
5
1
1
1
38. Укажите номера вершин, степень которых нечетна.
a
b
c
d
e
f
к
l
m
n
1
1
2
1
2
2
1
3
1
2
1
1
4
1
1
1
1
1
5
1
1
1
103

39. Укажите номера вопросов, на которые вы ответите «да»:
1)	может ли в какой-либо колонке матрицы инцидентности
находиться только одна единица?
2)	могут ли в матрице инцидентности содержаться колонки,
в которых записано три единицы?
3)	существуют ли матрицы инцидентности, все строки
которых заполнены единицами (то есть нет ни одного нуля)?
4)	могут ли в матрице инцидентности быть колонки,
содержащие две цифры 2?
5)	существуют ли матрицы инцидентности, в каждой строке
которых содержится точно по одной единице?
6)	существуют ли матрицы инцидентности, в каждой строке
которых содержится точно по одной цифре 2?
7)	существуют ли матрицы инцидентности, содержащие
хотя бы одну колонку, в которой записана цифра 1 и цифра 2?
40. Укажите номера висячих вершин.
a
b
c
d
e
f
к
l
m
n
1
1
2
1
2
2
1
3
1
2
1
1
4
1
1
1
1
1
5
1
1
1
41.	Сколько колонок в матрице инцидентности полного
графа на десяти вершинах?
42.	В нижеприведенном списке укажите:
маршруты; циклы; замкнутые маршруты; простые цепи;
цепи; простые циклы.
104

1)	2 е3 3; 4) 3 е7 4 е8 ; 7) е4 3 е7 2 е4;
2)	1 е8 4 е8 1; 5) 3 еб 3; 8) 1 е5 3 е7 4;
3)	2 е2 3 е6 3; 6) 2 е4 3 е2 2; 9) 1 е5 3 е7 4 е8 1.
43.	В нижеприведенном списке укажите:
последовательности, не являющиеся маршрутами;
простые цепи длины 1;
цепи длины 2;
простой цикл наибольшей длины. Укажите длину этого
цикла.
1)	2	ез	3; 4) 3 е7 4 е8 ; 7) е4 3 е7 2 е4;
2)	1	е8 4 е8 1; 5) 3 е6 3; 8) 1 е5 3 е7 4;
3)	2	е2	3 е6 3; 6) 2 е4 3 е2 2; 9) 1 е5 3 е7 4 е8 1.
44.	В нижеприведенном списке укажите: маршруты; циклы;
замкнутые маршруты; простые цепи; простые циклы; цепи.
1) 3, 4, 5, 3, 6, 3;
105

2)	1, 2, 3, 4, 1;
3)	5;
4)	2, 6;
5)	3, 5, 4, 3;
6)	2, 6, 2;
7)	2, 3, 6, 2, 3, 6, 2;
8)	3, 3;
9)	3, 4, 5, 2, 3.
45.	На какие вопросы вы ответите «да»?
1)	может ли последовательность, обозначающая маршрут,
начинаться номером ребра и оканчиваться номером вершины?
2)	может ли цепь состоять из одного ребра (и двух вершин)?
3)	может ли простой граф содержать цикл, состоящий из
одного ребра?
4)	существуют ли маршруты в нуль-графе, множество
вершин которого не является синглетоном?
5)	верно ли, что если граф содержит одну вершину и не
является нуль-графом, то он содержит цикл?
6)	верно ли, что если простой граф состоит из двух вершин
и не является нуль-графом, то в нем нет циклов?
7)	могут ли в цикле повторяться вершины?
8) верно ли, что если в графе нет циклов, то в нем число
ребер равно числу вершин?
46.	Ниже дан список графов, заданных множествами их
ребер. Каждый граф содержит 6 вершин. Укажите номера графов:
трехкомпонентных; четырехкомпонентных.
1)	{{1,2}, {2,6}, {3,4}};
2)	{{1,5}, {3,5}};
106

3)	{{1,2}, {2,3}, {5,6}};
4)	{{1,6}, {2,3}, {3,4}};
5)	{{1,2}, {2,5}, {3,6}};
6)	{{2,3}, {5,6}};
7)	{{1,2}, {2,5}, {3,4}};
8)	{{1,2}, {2,3}, {4,5}}.
47.	В графе 20 вершин. Степень каждой вершины равна 1.
Сколько в графе компонент? Сколько ребер?
48.	Сколько простых цепей, соединяющих вершины 1 и 6 и
проходящих через вершину 2, содержит граф, приведенный на
рисунке?
49.	На основе графа построили подграф, удалив вершину 2.
Сколько ребер удалено? Сколько ребер в подграфе? Сколько
простых цепей соединяют вершины 1 и 6 подграфа?
50. На рисунке изображен граф на пяти вершинах.
107

Сколько в этом графе всего простых цепей, соединяющих
вершины 1 и 5?
Сколько среди них простых цепей длины 1? 2? 3? 4? 5?
Сколько простых цепей проходит через 3 вершины? через 4
вершины? через все вершины?
51.	Сколько простых цепей соединяют две смежные
вершины в полном графе на пяти вершинах?
52.	На какие вопросы вы ответите «да»:
1)	во всяком ли простом графе самая длинная простая цепь
проходит через все вершины графа?
2)	дан связный граф. Всякий ли его надграф является
связным?
3)	верно ли, что в любом полном графе любые две его
вершины соединяет одинаковое число простых цепей?
4)	существует ли связный граф, в котором любые две
вершины соединены двумя простыми цепями?
5)	может ли петля в связном графе быть элементом какой-
либо простой цепи, соединяющей две различные вершины графа?
6)	всякий ли непустой подграф полного графа является
полным?
7)	всякий ли частичный граф полного графа является
связным?
53.	На какие вопросы вы ответите «да»:
1)	верно ли, что в эйлеровой цепи каждая вершина
встречается точно один раз?
2)	верно ли, что всякая эйлерова цепь проходит через все
вершины связного графа?
108

3) существует ли эйлерова цепь (замкнутая или
разомкнутая) в связном графе, содержащем одну нечетную
вершину?
4)	верно ли, что во всяком эйлеровом графе существует
единственная последовательность ребер и вершин, образующая
эйлеров цикл?
5)	верно ли, что всякая эйлерова цепь является простой
цепью?
54.	В полном графе на п вершинах эйлеров цикл содержит
171 ребро. Найдите п.
55.	Сколько существует гамильтоновых циклов в графе при
условии, что циклы считаются различными, если они отличаются
порядком записи вершин (например, 1,2,3,4,5,1 и 1,2,3,5,4,1 -
различные циклы) либо начальной вершиной цикла (например,
1,2,3,4,5,1 и 2,3,4,5,1,2 - это различные циклы).
56.	Укажите номера плоских графов.
57.	В связном плоском графе 30 вершин и 20 граней.
Сколько в нем ребер?
58.	В связном плоском графе 20 вершин и 19 ребер. Сколько
в нем граней?
109

59.	В связном плоском графе 10 граней и 20 ребер. Сколько
в нем вершин?
60.	В связном плоском графе 18 ребер, число вершин равно
числу граней. Сколько в нем вершин?
61.	В связном плоском графе число ребер на 14 больше
числа вершин. Сколько в нем граней?
62.	В связном плоском графе число ребер на 20 больше
числа граней. Сколько в нем вершин?
63.	Найдите число компонент плоского графа, если в нем 17
вершин, а число ребер равно числу граней.
64.	Найдите хроматическое число для каждого из графов,
приведенных на рисунке.
65.	Чему равно хроматическое число дерева на 40
вершинах?
66.	Определите хроматическое число связного графа, в
котором 22 вершины и 22 ребра.
67.	Чему равно хроматическое число связного графа, в
котором 35 вершин и 35 ребер?
68.	В связном графе 6 вершин и 15 ребер (петель и кратных
ребер нет). Найдите хроматическое число.
69.	Хроматическое число простого связного графа,
содержащего 28 ребер, равно 8. Сколько в нем вершин?
110

ЧАСТЬ IV. МАТЕМАТИЧЕСКАЯ ЛОГИКА
Математическая логика - это раздел математики,
изучающий функции, которые, как и их аргументы, принимают
значения из конечного множества.
1.	Функции алгебры логики (ФАЛ) или булевы функции (БФ)
1.1.	Задание булевой функции
Функциями алгебры логики, или булевыми функциями,
называются функции f(x1,x2,...,xn), аргументы которых xi,
взятые из счетной совокупности аргументов, определены на
множестве E2 = {0,1}, i = 1,2,...,n, и такие, что f(x1,x2,...,xn )є E2 .
Для задания БФ достаточно указать, какое значение
функции соответствует каждому набору переменных, то есть
задать последний столбец таблицы, имеющей 2n строк и n +1
столбец:
Таблица 2
x1
x2
xn-1
xn
f(x1 ,x2,...,xn-1,xn)
0
0
0
0
f( 0,0 ,...,0,0)
0
0
0
1
f( 0,0 ,...,0,1)
0
0
1
0
f( 0,0 ,...,1,0)
0
0
1
1
f( 0,0 ,...,1,1)
1
1
1
1
f( 1,1	1,1)
Число различных наборов равно 2n. Обозначим через P2
систему всех БФ, через P2 (n) - систему всех БФ от n переменных.
P(n)\= 2 .
111

Векторы а, в є Vn называют соседними по i-й координате,
если их i-е координаты различны, а остальные координаты
совпадают, i = 1,2 ,...,п.
Переменная xt булевой функции f(x1 ,x2,...,xn) называется
несущественной, или фиктивной, если на любых соседних по i-й
координате векторах функция f(x1 ,x2,...,xn) принимает
одинаковые значения, i = 1,2 ,...,n. В противном случае
переменная xi булевой функции f(x1 ,x2,...,xn) называется
существенной.
Две булевы функции называются равными (f1 = f2), если
одна может быть получена из другой добавлением или изъятием
несущественных переменных.
1.2.	Элементарные булевы функции. Логические операции
Важнейшие элементарные БФ:
f1(x) = 0 - константа 0;
f2 (x)= 1- константа 1;
f3 (x)= x - тождественная функция;
f4 (x) = x - отрицание х;
f5 (x1 ,x2 )= x1 ■ x2 = x1 a x2 - конъюнкция или логическое
умножение x1 и x2 (x1 a x2 = min(x1 ,x2) - выбор минимального
значения);
f6 (x1 ,x2)=x1 v x2	(x1 или x2)	- дизъюнкция или
логическое сложение x1 и x2 (x1 v x2 = max(x1 ,x2) - выбор
максимального значения);
112

f7 (x1 ,x2 ) = x1 ^ x2 - следование или импликация x1 и x2
(из x1 следует x2);
f8 (x1 ,x2 ) = x1 ® x2 - сложение x1 и x2 по mod2 (значение 0,
если сумма четная, и 1, если нечетная);
f9(x1 ,x2 ) = x1 /x2 - функция Шеффера («не x1 или не x2 »
или «x1 и x2 не совместны»);
f10 (x1 ,x2)=x1 ~ x2 - эквивалентность (x1 эквивалентно
x2);
f11 (x1 ,x2)=x1 і x2 - стрелка Пирса («ни x1, ни x2 » или
(«не x1 и не x2 », антидизъюнкция).
Табличные задания этих функций имеют вид:
Таблица 3
x
f1(x)= 0
f2 (x)= 1
f3 (x)= x
f4 (x)= x
0
0
1
0
1
1
0
1
1
0
Таблица 4
(x1 ,x2
f5 =x1 Л x2
f6 = x1 V x2
f 7 = x1 ^ x2
f8 = x1 0 x2
00
0
0
1
0
01
0
1
1
1
10
0
1
0
1
11
1
1
1
0
Таблица 5
(x1 ,x2 )
f 9 = x1 / x2
f10 = x1 ~ x2
f11 = x1 ^ x2
00
1
1
1
01
1
0
0
10
1
0
0
11
0
1
0
113

1.3.	Свойства логических операций
1.	Коммутативность
x1 V x2 = x2 V x1	x1 Л x2 = x2 Л x1
x1 ® x2 = x2 ® x1 x1 ~ x2 = x2 ~ x1
2.	Ассоциативность
(x1 V x2) V x3 = x1 V (x 2 V x3 )= x1 V x2 V x3
(x1 Л x2) Л x3 = x1 Л (x 2 Л x3 )= x1 Л x2 Л x3
(x1 ® x2 ) Ф x5 = x1 ® (x 2 ® x5 )= x1 Ф x2 ® x5
3.	Дистрибутивность
(x1 Фx2 ) Л x3 = (x1 Л x3 )®(x2 Л x3)
(x1 V x2) Л x3 =(x1 Л x3 ) V (x2 Л x3)
(x1 Л x2) V x3 =(x1 V x3 ) Л (x 2 V x3)
4.	x = x
5.	Правила де Моргана
x1 V x2 = x1 Л x2	x1 Л x 2 = x1 V x2
6.	Законы поглощения
x V x = x	x Л x = x
x V x = 1	x Л x = 0
x V 1 = 1	x Л 1 = x
x V 0 = x	x л 0 = 0
7.	Правило вычеркивания
x1 Л x2 V x1 = x2 V x1
Пример 1. Упростить выражение x1 v x2 • (x1 • x2).
Решение. Начнем упрощение с применения закона де
Моргана:
x1 V x2 = x1 • x2
114

Используя сочетательный закон, переставим множители,
тогда получаем выражение:
x1 v x2 • (x1 • x2) = x1 • x1 • x2 • x2 .
Применим законы поглощения x a x = 0, x a x = x и
x a 0 = 0, получаем:
x1 v x2 • (x1 • x2) = x1 • x1 • x2 • x2 = 0 • x2 = 0.
Пример 2. Упростить выражение x v у • z v x v у v z.
Решение. Начнем упрощение с применения закона де
Моргана:
x v у • z v x v у v z = x v у v z v x a у a z.
Применив сочетательный закон и законы склеивания,
получим:
x v у v z v x a у a z = x v z v (у v x a у a z) = x v z v у.
2.	СКНФ и СДНФ
Функция f *(x1 ,x2,...,xn), равная f(x1 ,x2,...,xn), называется
двойственной к функции f(x1 ,x2,...,xn ). (f *)* = f .
Для формул справедлив принцип двойственности,
состоящий в том, что если формула U = C[f1 ,f2,...,fs ] реализует
функцию f(x1,x2,...,xn ), то формула U* = C[f1*,f2*,...,fs*]
называется двойственной кии реализует функцию
f * (x1, x2 ,..., xn ) .
Для формул над множеством {0, 1, x, x1 v x2, x1 a x2 }
принцип двойственности формулируется так:
для получения формулы U *, двойственной к формуле U, нужно
в формуле И выполнить взаимные замены 0 ^ 1 и a ^ v.
115

Представление вида
оо
1	.	v	n
f (x1, x2,..., xn ) =	V	V-.. • x
(G1,...,an )eVn
f (^1,..., On ) = 1
где xо = \ x>	’, называют совершенной дизъюнктивной
[ x, о = 0.
нормальной формой (СДНФ) функции f (x1 ,x2 ,...,xn), а
двойственную формулу, получаемую взаимной заменой констант
0 ^ 1 и операций л ^ V, - совершенной конъюнктивной
нормальной формой (СКНФ).
СДНФ легко строится по таблице функций, нужно
учитывать только строки, где функция равна 1.
СКНФ имеет вид
оо
f (x1, x2,..., xn ) =	Л	x11... • xnn
(^1,..„ an )є^
f ^^...an)=0
СКНФ легко строится по таблице функций, нужно
учитывать только строки, где функция равна 0.
Пример 3. Найти СДНФ и СКНФ для функции трех
переменных: f(x, y,z)=( 0,0,1,0,1,1,1,0).
Решение. Построим таблицу истинности для этой функции.
x
y
z
f(x,y,z)
0
0
0
0
0
0
1
0
0
1
0
1
0
1
1
0
1
0
0
1
1
0
1
1
1
1
0
1
1
1
1
0
116

Для построения	СДНФ выбираем	строки,	в	которых
значение функции равно 1: это 3,5,6,7 строки.
В соответствии с этим получаем выражение для функции:
f(x, y, z) = xyz V xyz V xyz V xyz .
Для построения	СКНФ выбираем	строки,	в	которых
значение функции равно 0: это 1,2,4,8 строки.
В соответствии с этим получаем выражение для функции:
f(x, y,z)= (x v y v z)(x v y v z )(x v y V z )(x V y V z).
3.	Полные системы
Система функций P(f1 ,f2,...,fs,...)	из P2	называется
(функционально) полной, если любая БФ представима формулой
над Р.
Теорема. Пусть система P(f1 ,f2,...) функций из Р2 полна и
каждая ее функция	выражается формулой над	системой
Q(q1 ,q2,...). Тогда система Q полна.
Примеры полных систем функций:
1.	Система Р2.
2. Система Р = {x,x1 • x2 ,x1 v x2}, полнота этой системы
следует из существования СДНФ для каждой БФ
3.	Система {x,x1 • x2} - ее полнота вытекает	из	примера	2	и
теоремы, так как x1 v x2 = x1 • x2.
4.	Система {x,x1 v x2} - ее полнота следует	из	примера	3	и
теоремы, так как x1 • x2 = x1 v x2
5.	Система {x1/ x2} - ее полнота следует из примера 3 и
теоремы, так как x1 / x1 = x1 v x1 = x1;
117

(x1 / x2 ) /(x1 / x2 ) = x1 v x2 = x1 ■ x2
6. Система {1, x1 • x2 ,x1 Фx2} - ее полнота следует из
примера 3 и теоремы, так как x1 = x1 Ф1.
Теорема Жегалкина. Каждая БФ однозначно представима
многочленом по mod2:
f (x1, x2,..., x„ ) =	L	® ai i\ ••• • xi •
{i1 i, }={1-2 n}	11 -,s 1	s
Так как число таких многочленов от n переменных
совпадает с числом различных БФ, то представление функции
полиномом единственно.
Это представление называется многочленом Жегалкина, или
алгебраической нормальной формой (АНФ).
Алгоритм построения полинома Жегалкина по СДНФ.
Начало. Задана СДНФ функции f(x1, ..xn).
Шаг 1. Заменяем каждый символ дизъюнкции на символ
дизъюнкции с исключением.
Шаг 2. Заменяем каждую переменную с инверсией x равно¬
сильной формулой x 0 1.
Шаг 3. Раскрываем скобки.
Шаг 4. Вычеркиваем из формулы пары одинаковых слагае¬
мых.
Конец. Получен полином Жегалкина функции f(x1,	xn).
Пример 4. Найти полином Жегалкина БФ по ее СДНФ:
f(x, у, z) = ^уz v x^z v x;y z v ^уг.
Решение. По вышеприведенному алгоритму получаем:
f(x, у, z) = ^уz v x^z v ху^ v xуz = ^z © x^z © -ку^ © xуz =
= (1 © x^z © x(1 © у )z © лгу (1 © z) © xуz = уz © xуz © xz © x^z ©
© xу © xуz © xуz = уz © xz © xу.
118

4.	Замкнутые системы и классы
Замыканием множества М называется множество всех БФ,
представимых в виде формул над М. Замыкание множества М
обозначается через [М].
Свойства замыкания:
1)	[M ]3 M ;
2)	[[M ]] = [M ];
3)	если M1 с M2 , то [M1 ]с [M2 ];
4)	[M1 u M 2 ]c[M 1 ]u[M 2 ].
Класс М называется замкнутым, если [М] = М.
В Р2 к замкнутым классам относятся:
1.	Т0 = {f є Р2: f (0,0,...,0) = 0} - класс БФ, сохраняющих
константу 0. В частности, функции {0,x,x1 • x2,x1 v x2,x1 фx2}
принадлежат T0, а функции {1, x,x1 ^ x2,1®x} не принадлежат
T).
2. T = {f є Р2: f (1,1,...,1) = 1} - класс БФ, сохраняющих
константу 1. Функции {1, x,x1 ■ x2 ,x1 v x2 ,x1	^	x2}	принадлежат
T1	а	функции {0, x, x1 ® x2} не принадлежат T1.	Класс	T1	состоит
из БФ, двойственных к функциям Т0.
3.	S = {f є Рг : f = f *}- класс самодвойственных функций.
Классу S принадлежат функции
{x, x,x1 • x2 v x2 • x3 v x1 • x3,x1 ®x2 ®x3}.
4.	M = ^.f є Р2 : если a < b, то f(a) < f(b)}	- класс
монотонных	функций.	Функции	{0,1,x,x1 ■ x2 ,x1 v x2}
монотонны. Функции {x,x1 Ф x2} не монотонны.
119

5. A = {f є P2 : f = a0 фa1 ■ x1 Ф...Фan ■ xn, ,n = 1,2,...} - класс
аффинных функций	(функций,	задаваемых аффинными
полиномами по mod 2). Очевидно,	{0,1,x, x,x1 фx2}є A,
{x1 • x2 ,x1 V x2 }ё A.
6.	L= A n T0 - класс линейных функций.
Мощности основных замкнутых классов:
1.	To (n)\= TM= 22П -1 = 2 |P2 (n)|.
2.	\S(n)\ = 22 -1.
3.	\ A(n)\= 2n+1 = 2 •\L(n)\.
Теорема Поста о полноте. Система функций P полна тогда
и только тогда, когда она не содержится ни в одном из классов
T0 , T1, S , M , A .
Пример 5. Определить, полна ли система функций f и g,
заданная таблицей:
x
y
z
f
g
0
0
0
1
0
0
0
1
0
1
0
1
0
1
0
0
1
1
1
1
1
0
0
1
0
1
0
1
1
1
1
1
0
0
0
1
1
1
1
0
Решение. Найдем канонический многочлен для g (используя
СДНФ).
xyz V xyz V xyz = yz V xyz = yz V xz =(y V x )z = (xy +1 )z = xyz + z.
120

Полученная функция не является линейной.
Так какf(0; 0; 0) = 1, аf(0; 0; 1) = 0, то функция f не является
монотонной.
Так как g(0; 0; 0) = g(1; 1; 1) = 0, то функция g не является
самодвойственной.
f(0; 0; 0) = 1, т. е. функция f не возвращает константу 0.
g(1; 1; 1) = 0, т. е. функция g не возвращает константу 1.
Получаем таблицу следующего вида:
L
M
S
T0
T1
f
-
-
-
+
g
-
-
-
+
-
В каждом столбце имеется хотя бы один «минус», значит,
система функций полна.
Система функций называется базисом, если она сама полна, но
выбрасывание из нее любой одной функции делает систему неполной.
В рассмотренном примере система является базисом.
5. ДНФ и проблема минимизации БФ
Пусть задан алфавит переменных x1 ,x2,...,xn .
Выражение K = х.
О і	О	r	О	і
- V 1 ... A X: r = X. 1
Or
xir
r
при
1	r	1
v Ф л называется элементарной конъюнкцией. Число r
называется рангом элементарной конъюнкции.
Выражение N = vK, где K.(i = 1,...,s) — элементарная
І = 1
конъюнкция ранга rt называется дизъюнктивной нормальной
формой (ДНФ).
121

Для каждой функции f(x1 ,...,xn) и f Ф 0 существует ДНФ
N такая, что f(x1 ,...,xn ) = N. В качестве такой ДНФ можно взять,
например, СДНФ для f.
Пример 6. Рассмотрим функцию f(x1 ,x2,x3), заданную
таблицей.
x1 у x2 > x3
f(x1, x2 , x3 )
000
1
001
0
010
0
011
0
100
1
101
1
110
1
111
1
Ее можно представить в виде СДНФ.
N1 = f(x1 ,x2 ,x3)=x1 • x2 • x3 v x1 • x2 • x3 v x1 • x2 • x3 V
v x1 • x2 • x3 v x1 • x2 • x3.
С другой стороны, эта функция может быть представлена
другой ДНФ
N2 = f(x1 ,x2,x3 )=x1 V І2 • Із .
Для выбора более предпочтительной реализации вводится
индекс простоты L(N), характеризующий сложность ДНФ.
Примеры индексов простоты для ДНФ:
1.	LB(N) — число букв переменных, встречающихся в
записи ДНФ N. Если взять ДНФ N1 и N2 из примера 6, то
LB(N1 )= 15 и LB(N2 )= 3, т. е. в смысле этого индекса ДНФ N2
проще, чем ДНФ N1.
122

2.	LK(N) — число элементарных конъюнкций, входящих в
N. Для ДНФ N и N2 , очевидно, LK(N1 )= 5, LK(N2 )= 2, т. е. в
смысле этого индекса ДНФ N2 проще, чем ДНФ N1.
3.	L0 (N) — число символов отрицаний, встречающихся в
записи ДНФ N. Для ДНФ N1 и N2, очевидно L0 (N1 )= 7,
L0 (N2 )= 2, т. е. в смысле этого индекса ДНФ N2 опять проще,
чем ДНФ N1.
ДНФ N, реализующая функцию f(x1 ,...,xn) и имеющая
минимальный индекс L(N), называется минимальной
относительно L (МДНФ относительно L).
Для построения МДНФ можно использовать метод полного
перебора: сначала в каком-либо порядке строят все ДНФ над
переменными x1 ,x2,...,xn , затем отбирают из этого списка те
ДНФ, которые реализуют функцию f(x1 ,...,xn), для выбранных
ДНФ вычисляют величину индекса простоты и путем
сопоставлений находят минимальную. Сформулированный
алгоритм весьма трудоемок.
6.	Задания для самостоятельного выполнения
1.	Найдите значения функций, если A = 1, C = 0:
1) f = A + ВС + АС;	3) f = А + BCD;
2) f = АС + AD;	4) f = BC + AC.
2.	Введите в устройство десятичные эквиваленты наборов,
на которых функция равна единице:
1)	f = ABC + ABC;	4) f = АВ +AC;
2)	f = BC + ABC ;	5) f = AC + BC;
3)	f = АВ + ABC;	6) f = AC + AC.
123

3.	Булева функция зависит от шести аргументов. Найдите
наборы значений аргументов, если десятичные номера их имеют
вид:
1)	16; 2) 4; 3) 22; 4) 60; 5) 55.
4.	Функция четырех аргументов принимает единичное
значение на наборах 0,1,...,12, а на остальных— нулевое. На
каких наборах функция принимает нулевое значение? (Наборы
указать в десятичной системе).
5.	Функция четырех аргументов на половине наборов
принимает нулевое значение, а на остальных — единичное.
Сколько существует наборов, на которых функция принимает
нулевое значение?
6.	В таблице соответствия семи аргументов колонка f
содержит поровну единиц и нулей. Сколько в ней нулей?
7.	Дана функция f = AB + A С + BC + AD. Упростите эту
функцию при условии, что A = 0.
8.	Найдите аналитическое выражение функции трёх
аргументов X, Y, Z, если известно, что она принимает единичное
значение только на одном наборе 6.
9.	Функцию f = A B + B C представьте в виде таблицы
истинности.
10.	В таблице соответствия пяти аргументов колонка f
содержит 19 единиц. Сколько нулей в колонке f ?
11.	В колонке f таблицы соответствия шести аргументов
содержится 64 единицы. Сколько в этой колонке нулей?
12.	Найдите СДНФ следующих функций, представив их в
аналитической форме. Все функции зависят от аргументов
A,	B, C.
124

1)	f = AB;	4) f = A BC ;
2)	f = A B + AC;	5) f = A C ;
3)	f = BC + AC;	6) f = BC + AC.
13.	Найдите минимальную форму функций:
1)	f = A C +B + AC ;
2)	f = Y + X Z + XZ;
3)	f = P + PQ;
4)	f = Q + P Q ;
5)	f = P Q+PQ+P QR ;
6)	f = (PQ + PQR )P;
7)	f = A + AB + BC;
8)	f = A + AB + BC;
9)	f = A+AB + BC;
10)	f = X + XY + XZ ;
11)	f = P + PQ + QR + RS ;
12)	f = (AB + BC + AC) AB;
13)	f = (R + S)(R + S )RST ;
14)	f = (XYZ + XYZ)(X + Y);
15)	f = (A + B + C)(a + B )BC;
16)	f = (A + B + C)ABC + PQ.
14.	Упростите выражение ABC = ABC /((c v AB)i (BC)).
15.	Упростите выражение
(ABC ^ ABC )=(c ©(AB I BC)).
16.	Упростите выражение AB ^ C = ABC / C v AB © BC.
17.	Упростите выражение ABC © ABC /(c v (AB I BC)).
18.	Является ли полной система функций, состоящая из
дизъюнкции и импликации?
19.	Доказать полноту (или неполноту) приведенной системы
булевых функций: fx = xx д x2, f2 = 0, f3 = xx ~ x2.
20.	Применяя равносильные преобразования, привести
булеву функцию f = (x ^ y )^( yz ^ xz) к минимальной ДНФ.
21.	Докажите эквивалентность формул:
1) A v B ~ A ^ B;
2)	A д B ~ A ^ B ;
125

3)	(A v B)л (A v B) ~ A;	4) (A л B)^ C ~ A ^ (B ^ C).
22.	Упростите формулы:
1)	(A ^ B )л^ ^ A)^ A v B;
2)	(A ^ B)л^
3)	(A л B) v ((A ^ B)л A);
4)	A v (A л B )v (A v C);
5)	(A л B )v (A л B )v (B л C )v(A л B л C);
6)	(A v B )л (B v C )л (C v A)^ A л B л C.
23.	Найти СДНФ и СКНФ для функций:
1)	f = (0,0,0,04,1,1,1);	4) f = (1,0,1,1,1,1,04);
2)	f = (0,1,0,1,0,1,0,1);	5) f = (1,1,0,0,0,04,1);
3)	f = (0,0,1,0,04,0,0);	6) f = (1,0,1,0444,1).
24.	Постройте многочлен Жегалкина для функций:
1)	f = (0,0,0,04,1,1,1);	4) f = (1,04,1,1,1,0,1);
2)	f = (0,1,0,1,04,04);	5) f = (1,1,0,0,0,04,1);
3)	f = (0,0,1,0,04,0,0);	6) f = (1,0,1,0,1,14,1).
25.	Приведите к многочлену Жегалкина функции:
1) xy v xz;	4) (x ^ y)(y і z);
2)	(x v y)(y v xz);	5) ((x ^ y)v z) I x;
3)	(x ^ y) I z;	6) x(x ^ z)v(x і y)..
26.	Докажите полноту систем функций:
1)	Kv,	5)	{^,0};	9) {~,л,0};
2)	{л,-};	6)	{e,v,1};	10)	{I };
3)	К -};	7)	{Ф,л,1};	11)	{і}.
4)	{v, -};	8)	{~,v,0};
126

БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1.	Гаврилов, Г.П. Задачи и упражнения по курсу дискретной ма¬
тематики / Г.П. Гаврилов, А.А. Сапоженко. - М. : Наука,
2007.
2. Гончарова, Г.А. Элементы дискретной математики: учеб. по¬
собие / Г.А. Гончарова, А. А. Мочалин. - М. : Форум: ИН-
ФРА-М, 2007.
3. Ерош, И. Л. Дискретная математика. Булева алгебра. Комби¬
национные схемы. Преобразования двоичных последователь¬
ностей : учеб. пособие / И. Л. Ерош. - СПб.: СПбГУАП, 2001.
4. Ерош, И.Л. Дискретная математика. Комбинаторика: учеб.
пособие / И. Л. Ерош. - СПб. : СПбГУАП, 2001.
5.	Иванов, Б.Н. Дискретная математика. Алгоритмы и програм¬
мы. Расширенный курс / Б.Н. Иванов. - М. : Известия, 2011.
6.	Мендельсон, Э. Введение в математическую логику / Э. Мен¬
дельсон. - М. : Наука, 2006.
7. Нефедов, В.Н. Курс дискретной математики / В.Н. Нефедов,
В.А. Осипова. - М. : Издательство МАИ, 2008.
8. Спирина, М. С. Дискретная математика : учебник / М. С. Спи¬
рина. - М. : Академия, 2009.
9. Шапорев, С.Д. Дискретная математика. Курс лекций и прак¬
тических занятий / С.Д. Шапорев. - СПб. : БХВ-Петербург,
2007.
10.Шевелев, Ю.П. Дискретная математика: учеб. пособие /
Ю.П. Шевелев. - СПб. : Издательство «Лань», 2008.
127

Учебное издание
АЛЕКСЕЕВА Венера Арифзяновна
ТЕОРИЯ ГРАФОВ И МАТЕМАТИЧЕСКАЯ ЛОГИКА.
ПРАКТИКУМ
Учебное пособие
ЭИ № 270.
Редактор Н.А. Евдокимова
ЛР №020640 от 22.10.97.
Подписано в печать 10.04.2014. Формат 60*84/16.
Усл. печ. л. 7,44. Тираж 75 экз. Заказ 488.
Ульяновский государственный технический университет
432027, г. Ульяновск, ул. Сев. Венец, 32.
ИПК «Венец» УлГТУ, 432027, г. Ульяновск, ул. Сев. Венец, 32.