close

Вход

Забыли?

вход по аккаунту

?

Rogova Diskretnaya matematika uchebnoe posobie

код для вставкиСкачать
ФЕДЕРАЛЬНОЕ АГЕНТСТВО СВЯЗИ
Федеральное государственное бюджетное
образовательное учреждение высшего
образования
«ПОВОЛЖСКИЙ ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ
ТЕЛЕКОММУНИКАЦИЙ И ИНФОРМАТИКИ»
Кафедра высшей математики
Н.В.Рогова
ДИСКРЕТНАЯ МАТЕМАТИКА
Учебное пособие
Самара
2017
1
УДК 519.1 (075.8)
Рекомендовано к изданию методическим советом ПГУТИ,
протокол № 44, от 10.03.2017 г.
Рогова, Н. В.
Р Дискретная математика[Текст]: учебное пособие / Н. В. Рогова,.
ПГУТИ . – Самара.: ИУНЛ ПГУТИ, 2017. - 143 с.
Учебное пособие затрагивает такие разделы дискретной
математики
как:
теория
множеств,
отношения и
переключательные функции, булева алгебра, комбинаторика,
теория графов. Темы образуют единый методически
взаимосвязанный курс.
Предназначено в качестве учебного пособия для
студентов направления подготовки 09.03.02. «Информационные
системы и технологии» по дисциплине «Дискретная
математика», а также для студентов и магистрантов других
направлений подготовки и специалистов, желающих изучать
дискретную математику самостоятельно.
Каждый раздел содержит большое количество
разобранных задач и примеров.
©, Рогова Н.В., 2017
2
Оглавление
Введение .......................................................................... 5
Глава 1. Теория множеств .................................................. 6
1.1. Операции над множествами .................................... 6
1.2. Декартовое произведение...................................... 13
1.3 Инверсия и композиция графиков......................... 15
1.4 Соответствия .......................................................... 17
1.5. Счетность множеств .............................................. 20
1.6 Несчетность множества действительных чисел . 22
1.7. Отношения .............................................................. 24
Глава 2. Булева алгебра .................................................... 29
2.1. Булевы функции ..................................................... 29
2.2. Существенные и фиктивные переменные ........... 30
2.3 Булевы формулы ..................................................... 34
2.4. Булева алгебра ........................................................ 36
2.5.Совершенные нормальные формы ........................ 39
2.6 .Проблемы минимизации ....................................... 44
2.7. Принцип двойственности ...................................... 46
2.8. Карты Карно ........................................................... 50
2.9 Полином Жегалкина ............................................... 51
2.10 Полнота и замкнутость логических функций .... 56
2.11 Схемы из функциональных элементов ............... 65
Глава 3. Комбинаторика ................................................... 68
3.1. Выборки .................................................................. 68
3.2.Разложение бинома Ньютона ................................ 80
3.3.Треугольник Паскаля .............................................. 83
3.4. Полиномиальная формула..................................... 84
3.5. Формула включений и исключений ..................... 85
3.6. Задача о бескорядках ............................................. 89
3.7. Метод рекуррентных соотношений ..................... 91
3.8. Задача Фибоначчи .................................................. 93
3
Глава 4 . Теория графов .................................................... 95
4.1. Основные понятия ................................................. 95
4.2. Изоморфные графы ................................................ 99
4.3.Маршруты, цепи, циклы ....................................... 116
4.4. Метрические характеристики графа .................. 120
4.5. Планарность.......................................................... 125
4.6 Раскраска карт и графов ....................................... 130
4.7 Проблема четырех красок .................................... 132
Глоссарий ..................................................................... 135
Список литературы ..................................................... 143
4
Введение
Дискретная математика – математическая дисциплина,
которая является важным звеном для математического
образования инженеров. Дискретная математика имеет
широкий спектр приложений, прежде всего в областях,
связанных с информационными технологиями и
компьютерами. Деление математики на классическую и
дискретную в значительной мере условно, поскольку,
например, с одной стороны, происходит активная
циркуляция идей и методов между ними, а с другой –
часто возникает необходимость исследования моделей,
обладающих как дискретными, так и непрерывными
свойствами одновременно. Главной особенность дисциплины
– дискретность, т.е. отсутствие предельного перехода и
непрерывности, характерных для классической математики. В
качестве примера можно привести числовые системы:
множество натуральных чисел – дискретный объект, а
множество действительных чисел – непрерывный.
Дискретная математика, по существу, стала активно
развиваться с начала XX века, когда стали изучаться
возможности формализации математики и были получены
фундаментальные результаты в области математической
логики.
Учебное пособие состоит из четырех основных частей:
теория множеств, булева алгебра, краткого изложения основ
комбинаторики и теории графов.
Кратко изложены все основные вопросы теории
множест, булевой алгебры, комбинаторные конфигурации, к
каждой из которых приводятся разобранные примеры и задачи,
Теоретический материал по изучению теории графов содержит
основные определения и теоремы.
5
Глава 1. Теория множеств
1.1. Операции над множествами
Наиболее простая структура данных, используемых
в математике, имеет место в случае, когда между
отдельными данными присутствуют какие- либо
взаимосвязи. Совокупность таких данных представляет
собой множество. Множество принадлежит к числу
фундаментальных
неопределяемых
понятий
математики.Множество – это неопределяемое понятие.
Создатель теории множеств Георг Кантор говорил,
что множество есть многое, мыслимое нами как единое.
В отличие от других объектов, изучаемых
математикой, термин "множество" не имеет строгого
определения.Однако, множество можно пояснить следующей
фразой:
Множество – совокупность системы каких-либо
объектов, обладающих характерными для них общими
свойствами. Это не есть определение, т.к. множество и
совокупность синонимы.
Кантор: «Множество – объединение в одно общее
объектов, хорошо различаемой нашей интуицией или мыслью»
Объекты, из которых состоит множество называются его
элементами. Множество обозначается большими буквами:
Его элементы малыми буквами:
Множество считается, заданным если по отношению к
любому объекту выполняется одно из двух условий:
1)
(объект принадлежит множеству).
2)
(объект не принадлежит множеству).
Примеры множеств:
1)
– множество всех натуральных чисел 1, 2, 3,
6
2)
больших 100.
3)
.
4)
5)
6)
– множество всех натуральных чисел не
– множество всех решений уравнения
– множество всех действительных чисел вида
– множество всех действительных чисел .
– множество всех действительных корней
уравнения
.
7)
– футбольная команда «Крылья советов».
8)
– совокупность всех футбольных команд
премьер лиги.
Т.о. множество может быть элементами другого
множества.
Способы задания множеств:
1)
2)
Перечислением
или
списком
элементов
.
С помощью порождающей процедуры.
Порождающая процедура – способ получения элементов
из уже известных элементов множества или из каких либо
других объектов. (Можно задавать это также при помощи
операций над множествами).
Это множество описывается с помощью порождающей
процедуры, которая включает в себя два правила:
1.
.
2.
Если
.
3)
Описание свойств, характерных для элементов
этого множества. Пусть
– обладающие свойством , то
7
– означает, что
это множество всех
элементов , обладающих свойством .
Пример:
, т.е. множество
элементов удовлетворяющих этому неравенству.
Два множества называются равными, если они состоят
из одних и тех же элементов.
Множество называется конечным, если число его
элементов конечно. В противном случае множество называется
бесконечным.
Множество В называется подмножеством множества А,
если каждый элемент множества В принадлежит и множеству А.
не исключает того, что А совпадает с В.
Пустое множество – множество, не содержащее ни
одного элемента. Пустое множество является подмножеством
любого множества.
Различают строгое ( ) и несторогое включение ( ),
которое не исключает равенство множеств.
Пример:
Найти
все
подмножества
множества
А.
Если
в
какой-либо
задаче
рассматриваются
подмножества множества
, то это множество называется
универсальным.
Операции над множествами:
1)
Объединение или сумма
Объединением множеств А и В называется такое
множество, элементы которого принадлежат хотя бы одному из
множеств А или В и не содержат никаких других элементов.
Геометрически объединение представляется следующим
образом:
8
Объединение любого конечного или бесконечного числа
элементов множеств
– множество всех элементов,
принадлежащих хотя бы одному из элементов
:
Пример:
2)
Пересечением или произведением
Пересечением множеств А и В называется множество,
элементы которого принадлежат и множеству А и множеству В.
Геометрически
образом:
пересечение
9
выглядит
следующим
Пересечением любого конечного или бесконечного
числа элементов множеств
– множество всех элементов,
принадлежащих каждому из множеств :
Пример:
.
Законы, которым удовлетворяют операции объединения
и пересечения:
1.
Коммутативность:
2.
Ассоциативность:
3.
4.
Идемпотентность:
Дистрибутивность:
.
.
Доказательство:
Надо показать, что левая часть принадлежит правой
части, а правая часть принадлежит левой части.
А) Надо доказать, что левая часть является элементом
правой части. Если
Т.к.
был произвольным элементом, тем самым мы
доказали, что левая часть принадлежит правой части.
10
В)
3)
Разность
Разностью множеств А и В называется множество,
состоящее из элементов множества А, не принадлежащих
множеству В.
Геометрически разность выглядит следующим образом:
Пример:
4)
Дополнением
.
Разностью между универсальным и множеством А
называется дополнением.
Геометрически
образом:
дополнение
11
выглядит
следующим
Свойства:
1.
2.
3.
Доказательство:
Пусть
.
Пусть
.
5)
Симметрическая разность
Симметрической разностью множеств А и В называется
множество, которое есть сумма элементов множества А без
элементов множества В и элементов множества В без элементов
множества А.
Геометрически симметрическая разность имеет вид:
Свойства:
1.
2.
6)
Законы де Моргана.
12
1.2. Декартовое произведение
Вектором называется упорядоченный набор элементов
.
Элементы из которого состоит вектор – это его
координаты . Число координат называется длиной вектора. В
отличие от элементов множества, координаты вектора могут
совпадать, а элементы множества нет.
– вектор размерностью 5, вектор
размерностью 2 – упорядоченная пара элементов, вектор
размерностью 3 – упорядоченная тройка элементов.
Два вектора считаются равными, если их размерности
равны
и
равны
соответствующие
координаты:
.
Прямым или декартовым произведением множеств А и В
называется совокупность упорядоченных пар А и В таких, что
первый элемент берется из множества А, а второй элемент
берется из множества В.
Причем
Пример:
.
В частности если
, то обе координаты берутся из
одного и того же множества:
или
.
Свойства
декартового
произведения:
.
13
Аналогично, прямым или декартовым произведением
множеств
называется множество всех векторов
вида:
Пример: Пусть
– множество действительных чисел,
тогда можно сказать, что
это множество точек
плоскости.
Проекция вектора
Пусть дан вектор
.
Проекцией вектора
на
компонента:
.
Проекцией вектора на
размерности .
Пример:
ось называется его
называется вектор
– векторы одинаковой длины.
Для конечного множества мощностью называется
количество его элементов.
Теорема: (о мощности декартового произведения
конечных множеств)
Пусть
Тогда мощность декартового произведения конечных множеств
равна произведению их мощностей.
Доказательство: (метод математической индукции)
.
Пусть выполняется для элементов:
14
.
Приписываем к вектору справа элемент
из
,
в множестве
всего элементов
. Таких векторов мы
образуем
. Тогда
Всего можно образовать таких векторов
тогда,
перебирая
из декартового произведения
Мы доказали, что мощность равна
Следствие: мощность декартового
множеств
равна
произведению
.
произведения
мощностей
Теорема: Если каждая координата вектора может
принимать только два значения то различных векторов длины
может быть только
.
.
1.3 Инверсия и композиция графиков
График – это некоторая совокупность пар элементов.
Инверсия и композиция – операции над графиками.
– график.
– инверсия, совокупность пар
принадлежат графику
15
таких, что
Пример:
Композиция – совокупность пар таких, что
принадлежат графику
,
принадлежат графику
.
Пример:
Свойства операций над графиками:
1)
2)
.
Инверсия композиции равна композиции инверсий.
3)
Ассоциативный
16
1.4 Соответствия
Подмножество декартового произведения
называется соответствием между и .
Если вектор
, то
соответствует
при соответствии
говорят,
.
что
– называется
образом соответствия, – прообраз.
Проекция
– область определения соответствия.
– область значения соответствия.
1.
Если
, то соответствие называется
всюду определенным, в противном случае частично
определенным.
2.
Если
, то соответствие называется
сюръективным.
3.
Если
каждому
прообразу
соответствует
единственный образ, то такое соответствие называется
функциональным.
4.
Если каждому образу соответствует свой
прообраз, то такое соответствие называется инъективным.
Всюду определенное сюръективное, функциональное и
инъективное соответствие называется взаимно однозначным
соответствием (биекцией).
Пример:
1)
Стрелки из Х в У. Это соответствие всюду
определенное,
несюръективное,
нефункциональное
и
неинъективное.
17
2)
Позиция на шахматной доске представляет собой
взаимное однозначное соответствие между оставшимися
фигурами и занимаемыми ими местами.
3)
Англо-русский словарь – соответствие между
английскими и русскими словами.
Теорема: (о равномощности конечных множеств)
Пусть
и
– два конечных множества, между
элементами которых существует взаимное однозначное
соответствие, тогда мощность равна мощности .
Доказательство:
По условию теоремы имеем взаимно однозначное
соответствие. Оно всюду определено. Тогда в
найдутся два
элемента
и
такие, что им будут соответствовать
.
Предположим, что
1.
. Взаимно однозначное соответствие
всюду определено. В
найдутся
, что им будут
соответствовать один и тот же элемент
. Нарушится
функциональность.
2.
. Взаимно однозначное соответствие,
область значений совпадает со всем множеством
.
Соответствие сюръективное. В
найдутся
,
18
которым будет соответствовать одно
инъективность.
Следовательно
.
. Нарушается
Что дает эта теорема?
1)
Можно устанавливать равномощность конечных
множеств, не вычисляя этих мощностей, если устанавливать
взаимно однозначное соответствие между элементами этих
множеств.
2)
Можно установить мощность множества
,
установив взаимно однозначное соответствие с элементами,
мощность которого известна, или ее можно вычислить.
Если дано какое то конечное множество , то
–
число подмножеств данного множества.
Теорема: (о числе подмножеств конечных множеств)
Пусть
множество
,
тогда
.
Доказательство:
.
Выберем
некоторое
подмножество
. Возьмем некоторый вектор
– двоичные вектора, координаты которых состоят из нулей и
единиц.
Каждому подмножеству
поставим в соответствие
следующим образом:
Пример:
.
19
Пустому множеству будет соответствовать вектор,
вектор состоящий из нулей, а самому множеству
поставим в
соответствие вектор, состоящий из одних единиц.
Таким образом, мы установим взаимно однозначное
соответствие между множеством и вектором .
Тогда по предыдущей теореме их мощности равны:
1.5. Счетность множеств
Два
бесконечных
множества
называются
равномощными, если между их элементами устанавливается
взаимно однозначное соответствие.
Понятие мощности связано с запасом элементов в
множестве.
Если между элементами множеств существует взаимно
однозначное соответствие, то эти множества называются
эквивалентными.
.
Понятие эквивалентности применимо и к конечным и
бесконечным множествам. Два конечных множества будут
эквивалентными тогда и только тогда, когда число элементов в
них одинаково.
Конечные и бесконечные множества можно сравнивать
между собой. Конечные множества можно сравнить 2
способами:
1)
Подсчитав число элементов в каждом из них.
2)
Не подсчитывая число элементов в каждом из
них, можно установить взаимно однозначное соответствие
между ними. Но это можно сделать если в них число элементов
одинаково.
Бесконечные множества можно сравнить установив
лишь взаимно однозначное соответствие между ними.
Множество
называется счетным, если его элементы
можно занумеровать всеми натуральными числами или если оно
эквивалентно множеству натуральных чисел.
20
Счетное и конечное множество не более чем счетно.
Сходство: между конечным и счетным множеством,
заключается в том, что элементы конечного и счетного
множества можно занумеровать.
Различия: на нумерацию элементов счетного множества
уходит весь натуральный ряд, а на нумерацию конечного
множества уходит отрезок натурального ряда.
Свойства счетных множеств:
1.
Теорема: Пусть
– счетное множество. Тогда
всякое подмножество множества конечно или счетно.
Доказательство:
–
счетное
множество.
.
- элементы
множества , принадлежащие множеству . Если среди всех
индексов можно выбрать максимальное, то множество будет
конечным, в противном случае множество будет счетное, т.к.
нумерация элементов подмножества
взаимно однозначно
соответствует подмножеству натуральных чисел 1, 2, 3, …
2.
Теорема: Пусть
– счетное множество. Тогда
объединение не более чем счетного числа счетных множеств
счетно.
Доказательство:
В противном случае мы бы рассмотрели объединение
,
а
объединение
их
даст
объединение
Расположим множество элементов
21
в виде таблице:
Для нумерации элементов объединения применяем
метод диагонализации элементов.
Выписывая таким образом элементы объединения,
каждые элемент получает свой номер. Т.о. будет получено
взаимное однозначное соответствие между элементами
объединения и множеством натуральных чисел. Т.о. получаем
счетность.
3.
Теорема: Всякое бесконечное множество имеет
счетное подмножество.
Доказательство: Пусть – бесконечное множество.
– произвольный элемент множества
.
– это
можно
сделать,
т.к.
– бесконечное множество.
. Процесс этот будет продолжаться. Он не
может оборваться, т.к.
– бесконечное множество. Т.о.
образуется подмножество множества ,которое будет счетным.
4.
Теорема: (критерий бесконечности множества)
Всякое
бесконечное
множество
эквивалентно
некоторому своему собственному подмножеству. (без
доказательства)
1.6 Несчетность множества действительных чисел
Множество
несчетным.
не
являющееся
счетным
называется
Теорема Кантора. Множество действительных чисел
отрезка
не является счетным.
Доказательство: (от противного)
Пусть есть какое-то множество действительных чисел из
этого отрезка и оно счетно
22
– десятичная цифра, соответствующая
-му
десятичному знаку -того числа. Образуем десятичную дробь
, применяя диагональную процедуру Кантора.
Т.о. построили десятичную дробь
, которая не
совпадает ни с одной из дробей , т.к. от
отличается по
крайней мере одной цифрой и т.д.
Какое бы счетное множество действительных
чисел из
мы не взяли, оно не исчерпывает всего
множества действительных чисел из
.
Примеры: несчетных множеств
1)
Множество всех действительных чисел отрезка
2)
Множество всех точек плоскости и пространства.
Мощность отрезка
действительных чисел
называется мощностью континуума. ( )
Про множества, которые имеют мощность континуума,
говорят, что они континуальные. Примерами континуальных
множеств являются интервалы, полуинтервалы.
Мощность любого счетного множества обозначается
алеф нуль ( ). В анализе, как правило, множества счетные и
имеют мощность континуума. Но в дискретной математике
мощность континуума имеет более высокий порядок
бесконечности.
1)
Существуют ли множества, мощность которых
превосходит
мощность
континуума?
Да, существуют
множества, мощность которых больше мощности континуума.
2)
Существуют ли максимальные мощности? Такие
множества не существуют.
23
Теорема: Число подмножеств счетного множества имеет
мощность континуума. (без доказательства)
Даны два произвольных множества
и
. По
определению, говорят, что
тогда и только тогда
если найдется такое подмножество из множества , и это
подмножество будет эквивалентно множеству . А в множестве
такого подмножества не найдется.
Теорема: Пусть
– произвольное множество. Тогда
множество всех подмножеств этого множества больше
мощности этого множества.
.
1.7. Отношения
-местным отношением на множестве
подмножество
. Говорят, что элементы
находятся в отношении , если вектор
называется
.
Одноместным отношением будет само множество .
Элементы
находятся в отношении
, если
– двуместное отношение.
.
Примеры:
1)
выполняется данное отношение.
не выполняется данное отношение.
Бинарное отношение – график.
2)
На плоскости можно задать отношение, которое
определяется как симметрия относительно оси ох.
3)
На плоскости действительных чисел можно
задать отношение, которое определяется как «находится на
одинаковом расстоянии от начала координат».
24
Способы задания отношений
1)
Перечисление или
вступающих в данные отношения.
списком
пар
элементов,
2)
Предикатный способ – описание с помощью слов
или формул элементов множества, вступающих в данное
отношение.
3)
Матричный способ (в основном этот способ
используется для конечных множеств)
Например
–
конечное
множество. Матрица бинарного отношения на множестве
матрица -го порядка.
, в которой каждый элемент
это
, стоящий на
пересечении -й сороки и -го столбца обозначается как
Пример:
если
Отношение
называется обратным к отношению
, тогда и только тогда, когда
.
Свойства отношений
1)
Рефлексивность
Отношение
называется
рефлексивным,
. (каждый знаком сам с собой)
,
если
– отношение рефлексивно.
2)
Симметричность
Отношение
называется
симметричным,
если
.
(отношение родства)
«быть симметричным относительно оси ох»
25
3)
Антирефлексивность
Отношение
называется антирефлексивным, если
.
–
отношение
антирефлексивно.
4)
Антисимметричность
Отношение называется антисимметричным, если из
выполнения двух условий
.
отноше
ние антисимметричное.
5)
Транзитивность
Отношение
называется
транзитивным,
если
. (сын младше отца,
отец младше деда, следовательно сын младше деда.)
отношение
транзитивно.
Отношение эквивалентности
Всякое рефлексивное, симметричное и транзитивное
отношение является отношением эквивалентности.
(На множестве людей отношение эквивалентности – это
жить в одном городе)
Разбиением множества
называется совокупность
непересекающихся подмножеств множества
таких, что
каждый элемент множества
принадлежит только одному из
подмножеств.
Пример:
26
Теоремы
о
связи
разбиения
и
отношения
эквивалентности.
Теорема 1: Всякое разбиение множества
определяет
на этом множестве отношение эквивалентности
:
.
Доказательство:
.
1.
2.
.
.
3.
.
эквивалентности
Классом
элементом
множества
,
порожденным
, называется подмножество элементов
таких, которые вступают в отношение
с
элементами .
Теорема2:
Всякое
отношение
порождает разбиение множества
относительно этого отношения.
Доказательство:
1.
2.
27
эквивалентности
,
на классы эквивалентности
тогда
Отношение порядка
Всякое рефлексивное, антисимметричное и транзитивное
отношение называется отношением частичного порядка .
Пример:
1)
2)
Отношение частичного порядка на множестве
, для
которого
любые
два
элемента
сравнимы
, т.е. называется отношением
линейного порядка. Множество, в котором определено
отношение частичного (линейного) порядка называется
частично (линейно) упорядоченным множеством.
Элемент
называется наименьшим, если для
любого произвольного
. Элемент
называется наибольшим, если
.
Теорема:
(о
единственности
наименьшего
(наибольшего) элемента частично упорядоченного множества).
Если в частично упорядоченном множестве есть наибольший
(наименьший) элемент, то он единственный.
Доказательство: (от противного)
Пусть
.
Тогда
, что
противоречит нашему предположению.
Всякое
антирефлексивное,
антисимметричное
и
транзитивное отношение является отношением строго порядка.
Пример: 1.
.
2.
.
Множество
– называется полностью упорядоченным
по отношению к , если любые два его элемента сравнимы
между собой. В противном случае множество
называется
частично упорядоченным.
28
Глава 2. Булева алгебра
2.1. Булевы функции
Всякое функциональное соответствие называется
функцией.
Бинарное отношение
называется функцией если из
того, что
и
.
– область определения функции.
– область значения функции.
Биекция – сюръективная и инъективная функция.
Всюду
определенное
соответствие
называется отображением.
– отображение «на» если отображение
сюръективно.
– отображение «в».
Рассмотрим множество
Булевой функцией
.
-переменных
называется произвольная -местная функция, действующая из
в :
.
Всякая булева функция может быть задана в виде
таблице, в левой части которой все наборы аргументов
(двоичные векторы, соответствующей размерности), а в правой
вектор столбец значений функции.
Одним из способов задания функции – табличный
способ задания.
29
0
0
…
0
0
0
…
1
0
0
0…1
0
…
1
…
1
…
1…1
…
1
…
Для удобства в таблице исполнено стандартное
расположение наборов. Как запись числа в двоичной системе,
поэтому расположение наборов соответствует расположению
чисел
. В таблице
строк.
Булевы функции одной переменной:
0
1
0
0
0
1
1
0
1
1
2.2. Существенные и фиктивные переменные
Переменная
называется
фиктивной (не существенной), если справедливо равенство:
–
т.е. изменение значений переменной
не изменяет
значения функции при любых значениях остальных
переменных.
30
В противном случае переменная
называется
существенной.
В случае, когда
фиктивная переменная получается,
что
зависит от
-й переменной, т.е.
.
Функции и
называются равными, если функцию
можно получить из
удалением или добавлением фиктивных
переменных.
Преимущество удаления или ввода фиктивной
переменной. Если есть булевы функции, то можно считать, что
они зависят от одного и того же числа элементов
.
– множество булевых функций.
Пример: Найти существенные и фиктивные переменные
функции, заданной таблично.
№
1
2
3
4
5
6
7
8
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
1
1
1
1
0
1
0
1
–
1)
существенная переменная.
2)
:
31
– фиктивная переменная.
3)
–
существенная
переменная.
Теорема: (о числе разложений булевых функций
перемнных).
-
Доказательство:
При любом упорядочение значений наборов переменных
значение булевых функций определяется столбцом
.
Получим вектор длиной
, каждая координата которого
принимает только два значения. Таких векторов будет
.
С ростом числа переменных , табличное представление
булевых функций резко усложняется. Например, если
,
то строк в таблице
.
Булевы функции двух переменных
0
0
1
1
0
1
0
1
0
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
0
1
0
0
0
1
0
1
0
1
1
0
0
1
1
1
1
0
0
0
1
0
0
1
1
0
1
0
1
0
1
1
1
1
0
0
1
1
0
1
– функция тождественного нуля,
фиктивные переменные обе,
– конъюнкция,
– запрет импликации,
– функция первого элемента, фиктивная
переменная ,
32
1
1
1
0
1
1
1
1
– запрет импликации,
– функция второго элемента, фиктивная
переменная х,
– сложения по модулю 2,
– дизъюнкция,
– стрелка Пирса,
– эквивалентность,
– отрицание второй переменной,
фиктивная переменная х,
– импликация,
– отрицание первой переменной,
фиктивная переменная ,
– импликация,
– шрих Шеффера,
– функция тождественной единицы, обе
фиктивные переменные.
Т.о. из 16 функций двух переменных 6 имеют фиктивные
переменные, с ростом числа переменных доля фиктивных
переменных уменьшается и стремиться к нулю.
ПРИОРИТЕТ ОПЕРАЦИЙ
Порядок выполнения действий, если нет скобок:
.
Пример:
1)
Составить
таблицу
0
0
1
1
0
1
0
1
1
1
0
0
0
0
0
1
0
1
1
0
1
1
1
0
фиктивные переменные.
33
0
0
0
0
истинности
0
0
0
0
2)
0
0
0
0
1
1
1
0
0
1
1
0
0
1
0
1
0
1
0
1
0
1
1
0
0
0
0
0
1
0
1
1
1
1
1
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
1
0
0
1
0
0
0
1
0
1
1
1
0
1
0
1
1
1
Рассматривая данную функцию на существенные и
фиктивные переменные, получаем, что все переменные
существенные.
2.3 Булевы формулы
Наряду с табличным способом задания булевых функций
существует и другой способ задания булевых функций – с
помощью формул.
Суперпозицией функций
называется
функция
, которая получается подстановкой функций
друг в друга и переименованием переменных.
Выражение, описывающее эту суперпозицию называют
формулой.
Пусть
– какая-то конечная система логических
функций.
называется базисом, а
– базисными
функциями.
Дадим определение формулы над базисом
.
, где
– базисная функция называется
формулой. Если
– базисная функция, а
34
выражения
– базисные функции или символы
переменных, то
есть формула.
Формулы, которые встречаются в процессе построения
данной формулы называются подформулами.
Пример: Пусть
подформулы.
Всякая
формула,
выражающая
функцию
как
суперпозицию других функций задает ее способ вычисления
при условии, что можно вычислить исходную функцию. О
формуле, задающей данную функцию, говорят, что она
представляет или реализует данную булеву функцию.
Чтобы вычислить формулу булевой функции надо
вычислить все ее подформулы.
Пример:
Формула каждому набору переменных ставит в
соответствие единственное значение функции.
Задание с помощью формулы не единственно.
Формулы
и
называются эквивалентными, если они
реализуют одну и ту же функцию, т.е. на одинаковых наборах
принимают одно и то же значение.
Как установить эквивалентность формул, существует два
способа:
1)
Восстановить таблицу истинности по формуле;
2)
С помощью преобразований элементарных
функций, используя свойства основных булевых функций,
установить сходство или различие.
35
Пример:
1)
2)
3)
2.4. Булева алгебра
Функцию типа
операцией на множестве
совокупностью
называется алгеброй.
будем называть
M. Множество
, заданной
-арной
вместе с
на нем,
– основное множество.
Каждый элемент множества
представляет собой
упорядоченную совокупность элементов этого множества, т.е.
,
-тая
координата
которого
принадлежит
. По определению функции, каждой такой
совокупности ставится в соответствие
. Т.о. бинарная
операция
на
есть
функция
-переменных.
, у которой область определения
аргументов и область определения функции совпадают
при
операция будет называться унарной , а при
операция называется бинарная.
Множество
называется носителем алгебры, а
совокупность операций
- сигнатурой
алгебры.
Система
называется булевой алгеброй
логических функций, Ее носителем является множество булевых
функций , а сигнатурой являются булевы операции –
.
Пусть формула
задает
, а
задает
, тогда
постановка этих формул в дизъюнкцию
дают новую
36
формулу
, которая представляет функцию
. Т.о.
дизъюнкцию можно рассматривать как бинарную операцию на
множестве всех булевых функций
. Аналогично
конъюнкция также является бинарной операцией на множестве
всех булевых функций. Отрицание является унарной операцией.
Свойства булевых операций
1.
Коммутативность:
,
2.
Ассоциативность:
3.
умножения:
Дистрибутивность, относительно сложение и
4.
Иденпотентность:
5.
6.
Двойное отрицание:
Правило де Моргана:
7.
8.
9.
Закон противоречий:
Свойства констант:
Вычисление
булевых функций
можно решать
стандартным методом, т.е. вычисление обоих частей равенства
на всех наборах переменных. Данные формулы справедливы и
тогда, когда вместо переменной ставится некоторая формула.
При этом необходимо соблюдать правило подстановки:
- при подстановке
вместо , нужно
подставить во
все вхождения .
37
Кроме подстановки есть правило замены: Если
содержит в качестве подформулы
, то эту
можно
заменить, но не на любую формулу, а на эквивалентную ей.
Правила, вытекающие из основных свойств
1)
Если в формуле
один из элементов
равен 0, то вся конъюнкция равна нулю.
2)
Если в конъюнкции
один из
элементов равен 1, то его можно зачеркнуть.
3)
Если в дизъюнкции
один из элементов
равен 1, то вся дизъюнкция равна единице.
4)
Если в
один из элементов равен
0, то его можно зачеркнуть.
Правила упрощения
a)
Правило поглощения:
Доказательство:
b)
Правило склеивания:
Доказательство:
c)
Обобщенное склеивание:
Доказательство:
осуществляется
расщепления конъюнкций.
d)
Закон исключения третьего:
38
при
помощи
Доказательство:
e)
Доказательство: Разлагая
по
.
2.5.Совершенные нормальные формы
Пусть
о
и
1.
– параметр, который может принимать значение
Введем
.
функцию:
,
Пусть
. Пусть
.
тогда
тогда
Теорема: (о разложении булевых функций) Всякую
булеву функцию -переменных
при любом
можно представить в виде:
где дизъюнкции берутся по всевозможным наборам
значений переменных
39
Доказательство:
Проверим справедливость нашего равенства на
произвольном наборе значений переменных. Значения функций
на
наборе:
,
.
когда
(1),
совпадает
с
.
Тогда из всех конъюнкций, стоящих справа в формуле
остается только одна:
Следствие1: Разложение булевых
переменных по переменной
имеет вид
функций
-
Следствие2: Разложение булевых
переменных по всем переменным имеет вид
функций
-
Эта формула определяет формулу по которой находится
СДНФ. Дизъюнкция берется по всем наборам переменных, на
которых функция принимает значения, равные единице.
40
Теорема: (о единственности) Всякая булева функция
имеет СДНФ.
Пустую дизъюнкцию принимают равной нулю.
Алгоритм построения СДНФ
1.
Составить таблицу истинности;
2.
Конъюнкций должно быть столько, сколько
единиц в таблице истинности.
3.
Каждому единичному набору
соответствует конъюнкция всех переменных, в которой
берется с отрицанием, если
и без отрицания, если
.
Пример:
x
0
0
0
0
1
1
1
y
0
0
1
1
0
0
1
z
0
1
0
1
0
1
0
f(x,y,z)
0
0
1
1
1
0
1
1
1
1
1
–
СДНФ.
Теорема: Всякая булева функция может быть выражена
формулой, содержащий кроме символов переменных операции
конъюнкции, дизъюнкции и отрицания. (без доказательства)
41
Совершенная конъюнктивная нормальная форма
(СКНФ)
Аналогом СДНФ является СКНФ, в которой каждая
элементарная дизъюнкция содержит все переменные или их
отрицание.
.
.
.
Если функция задана таблично то ее СКНФ можно
построить по формуле:
Формула (2) называется совершенной конъюнктивной
нормальной формой.
42
Теорема: (о единственности) Любая булева функция
имеет СКНФ.
Единственная функция, которая не имеет СКНФ это
константа 1.
Алгоритм построения СКНФ
1.
Составить таблицу истинности.
2.
Дизъюнкций должно быть столько, сколько
нулей в таблице истинности.
3.
Каждому нулевому набору соответствует
дизъюнкция всех переменных, всех переменных, в которой
берется с отрицанием, если
и без отрицания, если
.
Пример:
x
0
0
0
0
1
1
1
y
0
0
1
1
0
0
1
z
0
1
0
1
0
1
0
f(x,y,z)
1
0
0
1
1
1
0
1
1
1
1
– СКНФ.
43
2.6 .Проблемы минимизации
Выражение вида
называется элементарной конъюнкцией. Число
называется
рангом элементарной конъюнкции.
Элементарная
конъюнкция
называется
полной
относительно переменных
, если каждая
переменная входит в нее не более одного раза с отрицанием или
без.
Дизъюнкция произвольного числа элементарных
конъюнкций называется дизъюнктивной нормальной формой
(ДНФ):
СДНФ – ДНФ, которая состоит из различных
правильных и полных элементарных конъюнкций.
Любую булеву функцию можно представить через ДНФ.
Приведение формулы к ДНФ осуществляется по
следующему правилу:
1.
Сначала отрицание, стоящее над формулами
спускается до переменных.
2.
Раскрываем скобки.
3.
С помощью свойств булевых операций и правил
упрощения удаляем лишние конъюнкции и переменные в
конъюнкциях.
4.
С помощью свойств булевых операций
удаляются константы.
44
Пример: Преобразовать в ДНФ
От ДНФ можно перейти к СДНФ с помощью
расщепления конъюнкций, содержащих не все переменные.
Пример: Преобразовать в СДНФ
Выражение вида
называется элементарной дизъюнкцией.
Число называется рангом элементарной дизъюнкции.
Элементарная
дизъюнкция
называется
полной
относительно переменных
, если каждая
переменная входит в нее не более одного раза с отрицанием или
без.
Конъюнкция произвольного числа элементарных
дизъюнкций называется конъюнктивной нормальной формой
(КНФ):
СКНФ – КНФ, которая состоит из
правильных и полных элементарных дизъюнкций.
45
различных
где
От ДНФ можно перейти к КНФ следующим образом:
Пусть ДНФ задана формулой
,
– элементарные конъюнкции. Представим
,
выражение
преобразуем в ДНФ
где
– элементарные конъюнкции.
Отрицание элементарных конъюнкций по правилу де
Моргана, преобразует элемент дизъюнкции и это даст ДНФ.
Пример: Записать ДНФ в КНФ
2.7. Принцип двойственности
Функция
функции
называется двойственной к
, если выполняется равенство:
Беря отрицание от обоих частей равенства и заменяя
и
на их отрицание, получим:
46
т.е. получаем:
Т.о. отношение двойственности между функциями
является симметричным.
Из
определения
двойственности
следует,
что
двойственная функция определяется однозначно. Может
оказаться, что
двойственна сама к себе, такую функцию
называют
самодвойственной.
Т.о.
, наборы переменных
противоположные.
Выше написанное равенство говорит о том, что
самодвойственная функция на противоположных наборах имеет
противоположное значение.
Пример:
Дизъюнкция
двойственная
операция
конъюнкции.
Доказательство:
1.
Конъюнкция двойственна дизъюнкции в силу
симметрии.
2.
1 двойственна к 0.
3.
Функции и самодвойственные.
Доказательство:
4.
Функция
самодвойственной.
Доказательство:
является
47
Пользуясь определением двойственности можно
доказать принцип двойственности: Если форма представляет
функцию , все знаки которой заменить на знаки двойственных
функций,
то
получим
,
которая
представляет
двойственную функцию .
В булевой алгебре принцип двойственности принимает
более конкретный вид: а именно, если в булевой функции
заменить дизъюнкцию на конъюнкцию и наоборот, 0 на 1 и
наоборот, то: получим
, представляющую
двойственную
функцию .
Если функции равны, то и двойственные функции равны.
Это позволяет с помощью указанных выше замен переходить от
равенства
к равенству
, т.е. получаются
новые эквивалентные соотношения.
Пример
таких
соотношений:
Элементарные конъюнкции, которые входят в ДНФ,
реализующие
данную
булеву
функцию,
называются
импликантами
Импликанта
называется просто,
произвольного
дизъюнктивной нормальной формы
если после отбрасывания из нее
множителя
,
она
перестает
быть
импликантой данной функции. ДНФ, реализующая данную
булеву функцию, которая состоит только из простых
импликантов, называется сокращенной.
Тупиковой
дизъюнктивной
нормальной
формой
называется ДНФ, которую нельзя упростить, путем удаления из
нее какой либо элементарной конъюнкции или удалением
какого либо множителя
.
48
Тупиковая ДНФ, обладающая наименьшим числом букв,
обозначающих переменные, называется минимальной ДНФ.
Задача построения ДНФ (минимальной) называется
проблемы минимизации.
Существуют
несколько
построения минимальной ДНФ.
эффективных
методов
Пример:
Аналогично задаче нахождения минимальной ДНФ,
ставится задача отыскания дизъюнктивной нормальной формы,
реализующую данную булеву функцию, которое содержит
наименьшее число элементарных конъюнкция. Такие ДНФ
называются кратчайшими.
49
2.8. Карты Карно
zw
00
01
11
10
1
5
9
13
2
6
10
14
3
7
11
15
4
8
12
16
xy
00
01
11
10
Представляем эту карту мысленно наклеенной на
поверхность шара, т.е. первая и четвертая строка соседние,
первый и четвертый столбец тоже соседние. Элементарным
конъюнкциям
будет
соответствовать
определенная
конфигурация из единиц.
1)
Элементарные конъюнкции в одну букву
соответствуют
конфигурации
1
в
прямоугольниках
размерностью 4*2 и 2*4.
2)
Элементарные
конъюнкции
ранга
2
соответствуют конфигурации 1 в прямоугольниках размером
1*4, 4*1, 2*2.
3)
Элементарной
конъюнкции
ранга
3
соответствуют конфигурации единиц в двух соседних клетках
2*1, 1*2.
4)
Элементарным
конъюнкциям
ранга
4
соответствуют конфигурации 1 размерности 1.
Задача нахождения минимальной ДНФ с помощью карт
Карно сводится к задаче оптимального покрытия единиц,
картами Карно размерностью 8, 4, 2 и 1.
Оптимальность покрытия состоит в том, что мы
стараемся использовать наименьшее число прямоугольников
наибольших размеров.
Нахождение минимальной КНФ сводится к покрытию
нулей картами Карно.
50
Пример:
zw
00
01
11
10
1
0
1
1
1
1
0
1
xy
00
1
1
01
1
1
11
1
1
10
1
1
1-й (1,2,3,4,13,14,15,16)
2-й (1,2,5,6,9,10,13,14)
3-й (10,11,14,15)
4-й (1,5,4,8)
Минимальная ДНФ:
Минимальная
КНФ:
2.9 Полином Жегалкина
Алгебра Жегалкина над множеством всех булевых
функций с двумя бинарными операциями
и , коротко это
записывается так
Свойства операций алгебры Жегалкина.
1.
2.
3.
4.
5.
51
6.
тогда и только тогда, когда среди переменных
имеется нечетное число единиц.
7.
, если среди слагаемых не
более одной единице.
8.
.
Доказательство:
.
.
Теорема: Любую булеву функцию можно представить в
виде полинома
который называется полиномом Жегалкина
Доказательство: Основывается на том, что любую
булеву функцию можно представить в виде СДНФ и СКНФ и на
свойствах суммы по модулю 2. Еще необходимо использовать
такое утверждение
Докажем
его:
Пример:
1.
2.
52
Для функции тождественно равной нулю, за полином
Жегалкина принимается нуль.
Теорема: (единственности) Для каждой булевой
функции существует единственный полином Жегалкина. (без
доказательства)
Число слагаемых в полиноме Жегалкина равно числу
всех подмножеств из множества -элементов.
Пустому подмножеству соответствует
. Всего число
полиномов должно быть
.
Три способа построения полинома Жегалкина
1.
Метод
неопределенных
коэффициенты
находятся из системы:
коэффициентов:
Пример:
x
0
0
0
0
1
1
1
y
0
0
1
1
0
0
1
z
0
1
0
1
0
1
0
f(x,y,z)
0
1
0
0
0
0
1
1
1
1
1
Прежде всего можно определить, что
Жегалкина для функции 3 переменных имеет вид:
53
полином
,
,
.
Полином Жегалкина для заданной функции имеет вид:
1)
Составить таблицу истинности.
2)
Выписать конъюнкции всех переменных.
Конъюнкций должно быть столько, сколько 1 в таблице
истинности.
3)
Заменить знак дизъюнкции по свойству операций
алгебры Жегалкина на сложение по модулю 2.
4)
Под
каждой
конъюнкцией
написать
соответствующий набор булевых переменных, поставить знак
инверсии над переменной, отвечающей нулевому элементу.
5)
Учесть,
что
отрицание
и
Пример:
1)
54
, таблица истинности для этой
2)
функции
x
0
0
1
1
y
0
1
0
1
f(x,y)
1
0
0
0
2.
Если
функция
задана
таблицей истинности, то полином Жегалкина находится по
формуле:
Пример: Записать полином Жегалкина для функции вида
.
x
0
0
0
0
1
1
1
y
0
0
1
1
0
0
1
z
0
1
0
1
0
1
0
f(x,y,z)
0
0
0
1
0
1
0
1
1
1
1
55
2.10 Полнота и замкнутость логических функций
Существует два способа задания функций:
1.
Табличный способ задания. Он является
универсальным, но достаточно большим.
2.
Формульный способ задания функции. Это более
компактный способ задания функции, однако формула
выражает
функцию
через
другие
функции
, поэтому для любой системы функций
возникает естественный вопрос: любая ли булева функция
может быть представлена как суперпозиция функций из ?
Теорема о том, что всякая булева функция, может быть
представлена
булевой
формулой,
как
суперпозиция
конъюнкции, дизъюнкции и отрицания. (рассмотренная выше).
Дает утвердительный ответ на этот вопрос для системы:
, т.к. данная теорема утверждает, что любая
булева функция может быть представлена булевой формулой.
Рассмотрим этот же вопрос для произвольной системы
функций .
Система функций
называется
функционально полной, если любая булева функция может быть
представлена с помощью суперпозиции этих функций:
- функционально полная система.
Теорема: Пусть даны две системы функций
56
Если система
является функционально полной
системой и любая функция этой системы
представлена суперпозицией функций системы
то система
тоже функционально полная.
Доказательство:
. Т.к.
функционально
полная система, то
В условиях теоремы сказано, что
тогда
Пример:
Примеры функционально полных систем:
1.
– функционально полная система.
Достаточно доказать, что все функции функционально полной
системы
, выражаются через функции системы
. А
фактически достаточно выразить
через
, пользуясь
правилами де Моргана.
Значит все функции системы
выражаются через все
функции системы
, тогда
сводится к
и является
функционально полной системой.
57
– функционально полная система.
2.
Выразим
через
:
Пример:
С точки зрения функциональной полноты система
является избыточной, т.к. при удалении из нее или она не
утрачивает свойство функциональной полноты, а вот
и
являются не избыточными. (т.е. формулы сильно усложняются)
3.
Система функций
– функционально
полная. Сведем
Пусть
к
:
т.е.
.
– функционально полная. Сведем
4.
к
воспользуемся формулой:
Пусть
т.е.
–
5.
система. Сведем ее к
функционально
полная
:
С понятием функциональной полноты тесно связано
понятие замыкания и замкнутого класса.
Замыканием системы логических функций
называется множество всех булевых функций, которые
получаются суперпозицией функций системы
. Замыкание
обозначается
.
58
Множество
называется замкнутым, если оно
совпадает со своим замыканием.
Класс – множество, элементами которого являются то же
множества.
Множество булевых функций
называется замкнутым
классом, если любая суперпозиция из
снова принадлежит .
Система функций называется функционально полной,
если ее замыкание совпадает с множеством всех булевых
функций:
Пример:
1.
множество булевых функций замкнуто.
2.
функций не является замкнутой.
–
–
система
этих
Свойства замыкания:
1.
2.
3.
4.
5.
Существуют
Класс
5
важнейших
замкнутых
– класс функций, сохраняющих нуль.
Теорема: Класс
Доказательство:
замкнутый класс.
59
классов:
Пример функций, принадлежащих классу
Класс
:
– класс функций, сохраняющих единицу.
Теорема: Класс
замкнутый класс.
Доказательство:
Пример функций, принадлежащих классу
:
Класс – класс самодвойственных функций.
Два булевых набора называются противоположными,
если
значение
каждой
переменной
одного
набора
противоположны соответствующему значению другого набора
переменных.
Функция называется самодвойственной, если
60
Самодвойственными являются функции
Менее
тривиальным
примером
.
является:
Из определения самодвойственной функции, следует:
Т.о. на двух наборах
и
самодвойственная функция принимает противоположные
значения. Самодвойственная функция полностью определяется
на первой половине строк таблице. Тогда число всех
самодвойственных функций переменных будет столько же,
сколько
векторов
размерности
,
т.е.
Теорема: Класс самодвойственных функций замкнут.
Доказательство: (не в самом общем случае)
Рассмотрим
Подстановка
в
самодвойственную
функцию
самодвойственной функции снова дает самодвойственную
функцию.
Класс
– класс монотонных функций.
61
На множестве векторов одинаковой размерности
определим отношение частичного порядка . Пусть даны два
вектора
. Будем
считать,
что
тогда и только тогда, когда
. Это отношение
распространено и на
множестве двоичных наборов.
на наборе
будем
обозначать
,
т.е.
полагаем,
что
.
Функция
если
для
любых
называется монотонной,
двух
векторов
из
того,
что
Проверка функции на монотонность требует анализа
таблицы истинности и это очень громоздко. Весьма полезно для
опознания монотонности следующая теорема:
Теорема: Всякая булева формула без отрицания
реализует монотонную функцию, не равную тождественно нулю
и не равную тождественно единице, и наоборот, для
найдется булева формула без
отрицания, определяющая ее.
Теорема: Класс монотонных функций является
замкнутым классом.
Доказательство: данной теоремы основывается на
использовании суперпозиции.
Пример:
Класс – класс линейных функций.
Функция
, если она представима полиномом
Жегалкина первой степени:
Теорема: Класс линейных функций замкнут.
62
Доказательство: основывается на известной теореме:
суперпозиция линейных функций есть линейная функция.
Пример:
Таблица Поста: рассмотрим основные функции в
принадлежности к замкнутым классам.
№
1
2
3
0
1
1
0
1
0
1
1
0
0
1
1
1
1
1
1
1
4
0
0
1
0
1
5
1
1
0
1
0
6
1
1
0
1
0
7
1
0
0
0
1
8
0
1
0
0
1
9
0
1
0
0
0
10
0
0
0
0
0
11
0
0
0
0
0
Система функций
называется
функционально полной в слабом смысле, если любая булева
функция представима суперпозицией 0,1 и функций системы .
– функционально полная в слабом смысле.
Пусть
произвольная
система
функций
. Для того, чтобы выяснить является ли данная
произвольная система функционально полной помогают
следующие теоремы:
Теорема: Для того, чтобы система функций
была
функционально полной в слабом смысле, необходимо и
63
достаточно, чтобы она содержала хотя бы одну немонотонную и
хотя бы одну не линейную функцию. (без доказательства).
Теорема: (основная теорема о полноте, теорема Поста)
Для того, чтобы система функций
была функционально
полной, необходимо и достаточно, чтобы она целиком не
содержалась ни в одном из пяти замкнутых классах
, т.е.
такие, что
.
(без
доказательства).
Пример: Выяснить принадлежность данной функций к
пяти замкнутым классам.
x
y
z
f(x,y,z)
0
0
0
1
0
0
1
1
0
1
0
1
0
1
1
0
1
0
0
1
1
0
1
1
1
1
0
0
1
1
1
0
.
.
.
;
;
;
;
Т.к.
, то
.
64
Функция
не принадлежит ни к одному из пяти
классов. Тогда по теореме Поста система функций
является
функционально полной.
2.11 Схемы из функциональных элементов
Рассмотрим устройство дискретного действия с
некоторым количеством входов и некоторым количеством
выходов.
Сигналы,
поступающие на входы и
снимаемые с выходов,
будем рассматривать двух
уровней,
которым
сопоставим сигналы 0 и 1.
Сигналы, которые
поступают на входы в
некоторые
дискретные
моменты
времени
, будем считать
выходящими в эти же
моменты времени (задерживание за счет срабатывания
устройства пренебрегаем).
На выходные сигналы оказываем влияние
не только входные сигналы, поступающие в данный момент
времени, но и те которые поступили раньше. Это влияние
учитывается изменением внутреннего состояния устройства.
Если же считать, что состояние устройства
фиксировано, то выходные сигналы однозначно определяются
выходными. (ДУ без памяти).
Если алфавитами входных и выходных сигналов
являются логические переменные 0 и 1, то дискретное
устройство (ранее описанное дискретное устройство называется
дискретное устройство без памяти) без памяти на выходе
реализует системы двух функций:
65
Физически дискретное устройство без памяти
представляет собой соединение некоторого числа компонентов,
которые называются логическими или функциональными
элементами.
Отвлекаясь
от
физической
природы,
функциональный элемент представляет собой объект с
некоторым
количеством
числовых
входов,
которые
перенумерованы и одним выходом.
Функция, реализующая данный
функциональный
элемент
Рассмотрим
некоторый
набор
функциональных
элементов
,
– базис,
–
базисные элементы.
Из этих базисных элементов
строят схемы. В схемы, кроме базисных
элементов, входят еще полюсы, которые
обозначаются
.
Дадим определение схемы по
индукции: совокупность полюсов есть схема, все полюсы есть
вершины схемы:
; результат присоединения к
вершинам схемы всех входов, некоторого базисного элемента (к
одной вершине может присоединяться несколько входов), есть
схема у которой вершинами являются все вершины исходной
схемы и выход присоединенного элемента.
66
В связи с
понятием системы
вводится понятие
анализа и синтеза.
Под
анализом
понимается
нахождение
булевой функции,
реализуемой данной
функциональной
схемой,
под
синтезом
–
построение
функциональной
схемы,
реализующей данную булеву функцию.
67
Глава 3. Комбинаторика
Комбинаторика произошла от латинского слова
combinutia (соединения).
Комбинаторика – дисциплина, изучающая методы
выбора и расположения элементов некоторого конечного
множества, а так же методы подсчета числа комбинаций
,которые можно составить из элементов данного множества.
Основные задачи комбинаторики:
1.
Пересчет: пересчитать все элементы данного
множества, обладающие данными свойствами.
2.
Перечисление: перечислить все элементы данного
множества, обладающие указанными свойствами.
3.
Классификация: классифицировать элементы
данного множества по определенному принципу.
4.
Оптимизация:
найти
элемент
данного
множества, на котором определена данная целевая функция, и
который доставляет ей наибольшее или наименьшее значение.
3.1. Выборки
Пусть
конечное
множество,
состоящее из элементов. Любую совокупность из элементов
множества , будем называть выборкой объемом .
Если порядок элементов в выборке существенен, то
выборка называется упорядоченной; в противном случае
неупорядоченной.
Две
– выборки, которые отличаются только
порядком следования элементов, считаются различными.
68
Если
элементы выборки
могут повторяться,
то
выборка
называется выборкой
с повторениями.
Пусть
–
выборка объема
,
состоящая
из
элементов множества
. Обозначим через
число повторений
в
выборке
. Набор
чисел
–
составляющих
комбинации , здесь
, а число
называется объемом
комбинации . может быть больше . Выборки одинакового
объема могут иметь разные составы.
Размещением с повторениями из
по
элемента,
называются упорядоченными выборками повторений объема .
Теорема: Число размещений с повторениями равно
.
Доказательство: Данная теорема доказывается методом
математической индукции. Поэтому рассматриваем случай,
когда
.
69
1)
. Показываем справедливость нашей
формулы для
– справедливо.
2)
Предположим, что наша функция справедлива
для
3)
размещение
Получаем:
. Берем какое то произвольное
.
Добавляем
к
нему
.
.
размещений можно образовывать столько, сколько
различных элементов
. Беря
-размещение и
действуя подобным образом, получим все -размещения из
элементов множества, которые будут различны, если
.
Т.к.
произвольно, то утверждение справедливо для
любого .
Пример: Для запирания сейфов применяются секретные
замки, которые открываются лишь когда набрана определенная
комбинация цифр или букв, нанесенных на диск. Пусть на диск
нанесено 12 букв, а секретная комбинация состоит из 5-ти.
Сколько неудачных попыток может быть сделано человеком,
незнающим эту комбинацию.
Речь идет об упорядоченной выборке с повторениями.
Основные правила комбинаторики
Большинство задач комбинаторики
помощи двух основных правил:
1)
Правило суммы;
2)
Правило произведения.
70
решаются
при
Правило суммы:
Если какой-либо объект
можно выбрать
способами, а объект выбрать способами, причем ни один из
способов выбора объекта
не совпадает ни с одним из
способов выбора объекта
, то выбор либо
, либо
осуществляется
способами.
Обобщение:
способов.
Пусть
– число совпадающих
– конечное множество.
– число элементов. Пусть
–конечные
множества с числами элементов
. Нетрудно
понять, что число элементов в объединении этих двух множеств
равно сумме числа элементов в
и
и без числа общих
элементов.
Этот метод справедлив для любого конечного числа
элементов.
71
Пример: В классе 35 учеников, 20 человек посещают
математический кружок, 11 – физический кружок, 10 – ничего
не посещают. Сколько учащихся посещают математический и
физический
кружки,
только
математический,
только
физический.
Решение: М – множество учащихся, посещающих
математический кружок.
Ф – ученики,
посещающие физический кружок.
. Н – ученики,
не посещающие ни один кружок.
.
–
множество всех учеников.
.
.
– те, кто ходит только в математический
кружок.
– те, кто ходит только в физический
кружок
72
Правило произведения:
Если какой либо объект можно выбрать
способами
и после каждого выбора объекта
объект
выбрать
способами, то выбор пары
(в указанном порядке)
осуществляется
способами.
Обобщение:
–
обобщенное правило
произведения.
С другой стороны: правило произведение, представляет
собой фактическую формулировку теоремы по мощности
декартова произведения конечных множеств.
Множества
и
называются множества всех
упорядоченных
пар
,
таких
что
Если
Декартовым произведением множеств
называется множество всех упорядоченных наборов, т.е.
векторов
вида
где
Если
,
то
Теорема: (теорема о мощности декартового
произведения конечных множеств) Пусть
–
конечные
множества,
.
Тогда
мощность декартового произведения равна произведению их
мощностей.
73
Пример: Сколько различных трехзначных чисел, можно
составить из цифр: 0,2,4,5,7. Каждое трехзначное число можно
рассматривать как упорядоченную тройку вида
, в
которой
первая
цифра
выбирается
из
множества
, вторая из множества
,
третья из множества
. Тогда множество
различных трехзначных цифр, это будет множество
всевозможных упорядоченных троек
Размещения без повторений.
Размещением из
по
элемента, называются такие
комбинации объема , составленные из элементов множества ,
которые отличаются друг от друга либо самими элементами,
либо порядком их следования. Т.о. размещения –
упорядоченные комбинации объема .
Утверждение:
Доказательство: Если
Рассмотрим
.
Каждое
размещение без повторений представляет
собой упорядоченную последовательность из
элементов.
Первый член этой последовательности может быть выбран
способами, второй –
, третий –
и т.д. После
того, как выбран
член,
член выборки выбирается
способом. Тогда применяя
обобщенное правило произведения:
74
Перестановка – упорядоченная комбинация из
элементов множества
. Т.е. перестановки это такие
размещения, которые отличаются друг от друга, только
порядком следования элементов. Число перестановок можно
получить из размещения без повторений при
.
Следствие:
.
Доказательство:
Пример:
1.
Группа состоит из 25 человек. Надо выбрать
старосту, зам. старосты, профорга и финорга. Сколькими
способами можно сбыло сделать этот выбор, если каждый
студент может занимать лишь один пост.
– упорядоченная выборка без
повторений.
2.
Скольким числом способов 4 человека могут
сесть на лавку.
3.
7
девушек
водят
хоровод.
Сколькими
различными способами они могут встать в круг.
Если бы девушки стояли на месте, то число способов
равнялось бы
. Но т.к. девушки кружатся, то важно
только лишь их расположение друг относительно друга, а не
относительно
окружающих
предметов.
Перестановки,
переходящие друг в друга при кружении можно считать
одинаковыми, но из каждой перестановки можно получить еще
6 новых при кружении
. Если рассматривать
перестановки из
предметов расположенных по кругу и
перестановки переходящие друг в друга, при перемещении
считать одинаковыми, то всего перестановок
.
75
Перестановки с повторениями
Имеются предметов различных типов:
– число
элементов первого типа,
– число элементов второго типа, …,
– число элементов -го типа.
– число элементов в каждой
перестановке.
Пример:
1.
Сколько перестановок можно сделать из букв
слова «лилия».
.
«л» - первого типа
.
«и» - второго типа
.
«я» - третьего типа
.
2.
Сколько можно составить семизначных чисел из
числа 1115552.
Каждое семизначное число упорядоченная комбинация
объема 7 с повторениями.
;
;
.
Число сочетаний без повторений
Сочетания без повторений из
по
элементов –
неупорядоченная комбинация объема .
Сочетания – комбинации, которые отличаются хотя бы
одним элементом. Поменять элементы местами можно
76
способами, т.о. каждому сочетанию соответствует
размещений, следовательно, размещений в
больше, чем
сочетаний, следовательно
.
Утверждение:
Доказательство: Эта формула получается из формулы
. Сначала составим все
сочетания
. В каждом
таком сочетании переставим элементы всеми возможными
способами
– все они будут различны
.
Пример:
В полуфинале первенства России по шахматам
участвуют 20 человек, а в финал выходят лишь трое. Чему равно
число различных исходов полуфинала.
Число сочетаний с повторениями
Сочетания с повторениями – неупорядоченная выборка
с повторениями.
Утверждение: Число сочетаний с повторениями равно
числу сочетаний без повторений. (без доказательства)
Пример: В кондитерском магазине продавали 3 сорта
пирожных: заварные, безе, трубочки. Сколькими способами
можно купить 7 пирожных.
.
Выборка
неупорядоченная
с
повторениями. Зашифруем каждую покупку с помощью нулей и
единиц.
(3 трубочки, 1 заварное и 3 безе):
Труб:1,1,1
Завар:0,1
Безе: 0,1,1,1
111010111
77
6 труб, 1 безе: 111111001
Каждую покупку зашифруем при помощи 7 единиц и 2
нулей. И наоборот, каждой комбинации из семи единиц и двух
нулей соответствует определенная покупка. Например,
110101111 (2 трубочки, 1 заварное, 4 безе). Мы установили
взаимное однозначное соответствие комбинации и покупки,
следовательно, число способов покупки – перестановок из 7
единиц и 2 нулей, т.е.
способов.
Замечание: Чтобы не нарушать общности считают, если
выборки пустые:
Число разбиений множества
Пусть дано
пересекающихся множеств
на
подмножеств
. Совокупность попарно не
, т.е.
, где
.
Совокупность
множеств
носит
название
– разбиения множества .
Утверждение:
Число
таких
разбиений
при
фиксированных
равно
Доказательство: Каждое из множеств
можно
рассматривать как сочетание из по без повторений. Поэтому
справедлива следующая формула.
78
Действительно, множество
сочетаний из
множество
.
можно составить числом
элементов по
. После того как
выбрано, нужно составить множество
таким числом способов можно выбрать
После того, как выбрано
из
и т.д.
выбирают следующим
числом способов:
. Теперь применим правило
произведения, получим формулу (1). Тогда из (1), расписывая,
получаем:
Примеры:
1.
Сколькими способами можно расселить 10
студентов по трем комнатам: 4-х метсной и двум трехместным.
.
2.
Сколькими способами
пригласит танцевать 4 девушек из 6-ти.
.
79
4
юношей
могут
3.2.Разложение бинома Ньютона
.
.
….
(2) – разложение степени бинома Ньютона. Ньютон
обобщил эту формулу для произвольного показателя.
Пример:
80
Свойства бинома Ньютона:
1.
В разложении
2.
Каждое слагаемое однородно относительно
-слагаемое.
и
, т.е. каждое слагаемое имеет одни и те же показатели (сумма
показателей
и
есть одно и тоже число
для каждого
слагаемого).
3.
Показатель степени уменьшается на единицу с
каждым слагаемым, а показатель
каждым слагаемым.
4.
увеличивается на единицу с
Слагаемое
является
слагаемое формулы (2). Обозначается
общим членом разложения.
5.
Биномиальные коэффициенты:
и называется
.
Свойства биномиальных коэффициентов:
1.
Равноудаленные коэффициенты в разложении (2)
равны между собой
Доказательство:
81
2.
Сумма
биномиальных
разложении (2) является
Доказательство: В (2) пусть
коэффициентов
и
в
.
3.
Сумма коэффициентов ,стоящих на четных
местах равна сумме коэффициентов, стоящих на нечетных
местах.
Доказательство:
В (2) пусть
и
.
Перенесем слагаемые с минусами влево и получим:
4.
Доказательство:
82
Сравнивая (3) и (4): (3) = (4).
Пример:
3.3.Треугольник Паскаля
Арифметический треугольник представляет собой
таблицу по краям пишутся единицы, а внутри числа, которые
есть суммы соответствующих чисел предыдущей строки.
строка преставляет собой коэффициенты
разложения
– ой степени бинома.
83
Элементами
треугольника
Паскаля
коэффициенты разложения бинома Ньютона.
являются
3.4. Полиномиальная формула
Где суммирование берется по всем решениям уравнения
в целых неотрицательных числах, а
коэффициенты
Пример:
84
;
.
3.5. Формула включений и исключений
Пусть имеется
предметов, некоторые из которых
обладают свойствами
.
При этом каждый предмет может либо обладать каким
либо из этих свойств, либо не обладать ни одним из этих
свойств.
Обозначим
– число предметов, обладающих
свойством
свойством
свойствами
– число предметов, обладающих
;
– число предметов, обладающих
;
,
но
не
обладающая
свойством
.
– число предметов, не обладающих ни
одним из свойств
.
Справедлива следующая формула:
85
(5) – формула включений и исключений.
В формуле (5) алгебраическая сумма берется по всем
комбинациям свойств
, причем знак плюс
берется, если число учитываемых свойств четно, знак минус,
если число учитываемых свойств нечетно.
Формулу (5) доказываем методом математической
индукции по числу свойств.
1.
Для одного свойства очевидно, что (5)
справедлива:
2.
Предполагаем, что (5) справедлива при
свойствах:
Формула (6) справедлива для любой совокупности
предметов, поэтому эта формула справедлива и для числа
предметов
- число предметов, обладающих свойством
. Применим (6) для
.
86
Если мы вычтем (7) из (6), получим левую часть
формулы
(5).
А
слева
получается
.
Уменьшаемое – число предметов, не обладающих свойствами
, но возможно обладающих свойством
.
Вычитаемое – число предметов, не обладающих свойствами
, но обладающих свойством
. И в
результате получается число предметов, которые наверняка не
обладают ни одним из свойств, т.е.
. Т.к.
произвольно, то формула справедлива для любого .
Пример:
1.
При
обследовании
читательских
вкусов
студентов оказалось, что 60% читают журнал А, 50% - читают
журнал В, 50% - читают журнал С. 30% читают журналы А и В,
20% – журнал В и С, 40% - А и С, 10% все три журнала.
Сколько процентов студентов не читают ни один из журналов.
2.
Сколько существует целых чисел от 0 до 999,
которые не делятся ни на 5, ни на 7.
Деление на 5
Деление на 7
,
- целая часть числа.
.
87
.
Приведем еще одну форму записи формулы включения и
исключения.
Пусть
.
Их
мощности
.
Обозначим
;
;
;…;
;…;
.
Тогда
Пример:
В отделе НИИ работают несколько человек, причем
каждый из них знает хотя бы один иностранный язык. 6 человек
знают английский, 6 – немецкий, 7 – французский, 4 –
английский и немецкий, 3 – немецкий и французский, 2 –
французский и английский, 1 – знает все три языка. Сколько
человек работают в отделе.
– множество, знающих английский язык.
– множество, знающих французский язык.
– множество, знающих немецкий язык.
88
3.6. Задача о бескорядках
Беспорядком называется такая перестановка из
элементов, при которой ни один элемент не остается на своем
месте. Число беспорядков обозначается
. Формула числа
беспорядков выводится через формулу включений и
исключений.
Обозначим
через
свойство
перестановок
заключающееся в том, что -тый элемент остался на своем месте
Тогда
– это число таких перестановок, обладающих
свойством
первый и
.
второй
– число перестановок, при которых
элемент остаются на своем месте.
- число перестановок, при которых
не остаются на своих местах.
– число всех перестановок (
).
, т.к. не важно,
какой из элементов остается на своем месте (все элементы
равноправны).
. Таких слагаемых при использовании двух свойств
, т.к.
порядок в паре не существенен. Аналогично будет и по трем
свойствам. Следовательно:
89
– число перестановок, при которых
остаются на своих местах, а остальные меняются.
элементов
– число перестановок, при которых один элемент
остался на месте. Следовательно:
, и т.д.
Это частичная сумма разложения в ряд Маклорена
функции
.
А если надо подсчитать число перестановок, при
которых ровно
– элементов остаются на своих местах, а
остальные
– элемента меняются местами:
Доказательство:
Действительно, сначала надо выбрать какие
элементов мы оставим на своих местах. Это можно сделать
.
А остальные мы можем переставить числом способов
.
Применяя правило произведения, мы можем получить нашу
формулу.
Пример:
Девушка из почтового отделения спешила и в спешке
перепутала конверты: паспорт одного положила в конверт с
адресом другого, а паспорт другого в конверт с адресом
90
первого. Пусть ей пришлось бы одновременной обрабатывать 5
писем. Подсчитаем, во скольких случаях она сделала бы полную
путаницу, т.е. так, что никто бы не получил своего паспорта.
Один адресат получил свой паспорт:
3.7. Метод рекуррентных соотношений
Метод решения задачи сведением ее к аналогичной для
меньшего числа предметов называется методом рекуррентных
соотношений.
Метод рекуррентных соотношений позволяет свести
задачу об
предметах к задаче об
предмете, потом
к задаче об
предметах и т.д. пока мы не придем к
задаче, которую мы умеем решать. Во многих случаях удается
получить из рекуррентного соотношения явную формулу для
решения комбинаторных задач.
Рекуррентное соотношение имеет порядок
если оно
позволяет
член выразить через
.
Пример:
Рекуррентному соотношению
порядка удовлетворяет
бесконечное множество число решений, т.к. первые
членов
последовательности можно задать произвольно. Но если
членов заданы произвольно, то остальные уже определяются
однозначно из рекуррентного соотношения.
Пользуясь рекуррентным соотношением, мы можем
последовательно выписывать члены последовательности до тех
91
пор, пока не найдем тот член последовательности, который
нужен для решения какой-то конкретной задачи. Но эта
процедура очень громоздкая. Поэтому желательно иметь
формулу, которая позволяла бы находить сразу нужный член
последовательности.
Некоторая
последовательность
называется
решением данного рекуррентного соотношения, если при
подстановки его в рекуррентное соотношений, оно обращает его
в верное тождество.
Пример:
– является ли решением.
.
.
.
– равенство верно.
Общим решением рекуррентного соотношения
порядка называется решение, зависящее от
произвольных
постоянных
и такое, что путем подбора этих
произвольных постоянных можно получить любое решение
данного рекуррентного соотношения.
Общего
правила
для
решения
рекуррентного
соотношения нет, но есть класс рекуррентных соотношений,
который можно решить по общему правилу. Это класс линейных
рекуррентных соотношений с постоянными коэффициентами.
Линейным рекуррентным соотношением с постоянными
коэффициентами называется соотношение вида:
где
– некоторые числа.
Будем искать решение данного уравнения в виде
. Если его подставить, то получим.
(2) –
характеристическое
рекуррентного соотношения (1).
92
уравнение
данного
Если
, то уравнение
нулевых решений не
имеет. Если характеристическое уравнение имеет своим
решением различные числа, то общее решение линейного
рекуррентного соотношения с постоянными коэффициентами
имеет вид:
Если
, т.е.
корней уравнения
совпадают, тогда часть решения (3), которое соответствует
этому кратному корню, выглядит следующим образом:
Пример: Решить рекуррентное соотношение.
.
.
.
.
.
.
.
3.8. Задача Фибоначчи
Задача Фибоначчи (1202).
Пара кроликов приносит раз в месяц приплод из двух
крольчат (самки и самца). Новорожденные крольчата через 2
месяца после рождения уже приносят приплод. Сколько
кроликов появится через год, если вначале была одна пара
кроликов.
Решение:
- это
последовательность чисел Фибоначчи:
93
Для удобства впереди последовательности добавляют 0
и 1, тогда начальные данные:
.
Характеристическое уравнение:
.
.
.
.
Общее решение.
:
.
.
94
Глава 4 . Теория графов
Теория графов (Эйлер)
«Природа говорит языком математики: буквы этого
языка – круги, треугольники и другие фигуры.» Г. Галилей.
В настоящее время теория графов находит широкое
применение
в
различных
областях
знаний:
химия,
электродинамики, экономики, лингвистики и компьютерном
языке.
р. Прегель
В 1736 году
Эйлер поставил задачу о
Кёнигсберских мостах.
Есть 7 мостов. Можно
ли выйдя из дома,
вернуться обратно пройдя по каждому из мостов только один
раз. Эйлер доказал неразрешимость этой задачи. Теорию графов
связывают с этой задачей.
В середине 19 века исследования по теории графов
возобновились. С 60-х годов 20 века теория графов бурно
развивается, т.к. она нашла приложение в новых науках: теория
игр, теория информатизации, информатика, статистика,
теоретическая физика, психология, социология, электрические
цепи и теория контактных цепей.
4.1. Основные понятия
Пусть дано множество
, соединенных некоторым
образом. Множество
назовем множеством вершин, а
элементы
назовем вершинами.
Графом
с множеством
вершин
называется семейство пар вида
95
, где
вершины графа, а элементы вида
называются
ребрами графа.
В этом определении 2 вершины, соединенных ребром
называют концевыми точками или граничными точками.
Декартово
произведение
определяет
граф
.
Можно интерпретировать граф как соответствие.
,
,
,
,
.
Ребро графа называется неориентированным, если
порядок расположения его концевых точек несущественен
, в противном случае ребро
называется ориентированным.
Граф называется ориентированным или орграфом, если
все его ребра ориентированы (ориентированное ребро часто
называется дугой).
Граф называется неориентированным, если все его ребра
неориентированным.
Граф
называется
смешанным,
если
он
и
ориентированный и неориентированный.
96
И в случае ориентированного и неориентированного
графа говорят, что ребро из
инцидентно вершинам
и ,
если это ребро их соединяет. И наоборот, вершины
и
инцидентны ребру из .
Две вершины называются смежными, если они
инцидентны одному и тому же ребру.
Два ребра называются смежными, если они имеют
концами общую вершину.
Ребро, у которого концевые вершины совпадают
называется
петлей.
Как
правило
петля
считается
неориентированной.
Или
оговаривают,
что
они
ориентированные в противоположные стороны.
Вершина не инцидентная не одному ребру называется
изолированной.
Граф, состоящий только из изолированных вершин
называется нуль-графом.
Граф, содержащий хотя бы одну изолированную
вершину называется несвязным.
Граф, у которого какие-либо две вершины соединены
несколькими ребрами называется мультиграфом.
97
Полным графом называется граф, ребрами которого
являются всевозможные пары
для двух различных
вершин из
. Т.е. граф полный если он содержит все
допустимые ребра, т.е. вершины соединены ровно одним
ребром.
Простым графом называется граф, у которого нет
петель и множество ребер.
Обозначим полный граф вида.
Для каждого ориентированного графа существует
обратный граф
, получаемый из графа
изменением ориентации каждого ребра графа. Для каждого
ориентированного графа
существует неориентированный
98
граф
. Это тот же граф, на котором не отображена
ориентация ребер.
4.2. Изоморфные графы
Существует большая свобода выбора в размещении
вершин графа и в выборе формы линий, соединяющих эти
вершины.
Графы
и
называются изоморфными, если
существует взаимно однозначное соответствие между
вершинами одного и другого графов, а так же существует
взаимно однозначное соответствие между их ребрами,
сохраняющее отношение инцидентности. Поэтому не важно
какие именно изображения данного графа используются, т.к. все
изоморфные графы обладают одними и теми же свойствами.
Способы задания графа
1.
Геометрически (вершины – точками, ребра –
соединяющими их линиями). Чаще используются на плоскости.
2.
Задание с помощью булевой матрицы.
99
Булева матрица – матрица, элементы которой нули и
единицы, т.к.
квадратную форму.
размерности
, т.е. матрица имеет
Отсутствие нулей на главной диагонали матрицы
говорит о том, что у графа петли.
3.
Сотовый способ.
100
0 – пустой квадрат, 1 – черный квадрат.
4.
Задание с помощью соответствия.
Рисуются две параллельные прямые, где отмечаются
вершины.
вершины из множества начал соединяются с
вершинами
из множества концов, когда между
вершинами есть дуга.
Некоторые частные виды графов
Псевдографом называется граф, имеющий петли, но не
имеющий параллельных ребер.
Суперграф – граф, имеющий и параллельные ребра, и
петли.
101
Двудольный граф – граф, у которого множество вершин
разбито на два не пересекающихся множества таких, что каждое
ребро имеет один конец в множестве , а другой в множестве
.
.
Полный двудольный граф – граф, у которого любые две
вершины, входящие в разные доли смежные. Обозначим полный
двудольный граф
.
Здесь
граф-
.
колесо
102
Граф Петерсона
Симметричным графом называется граф, где любые две
вершины соединены двумя противоположными дугами.
Звездный граф, определяемый вершиной , состоит из
всех ребер графа , которые имеют концевой вершиной.
103
Части и подграфы
Граф
называется частью графа
, если его
множество вершин содержится в множестве вершин
и
все ребра
являются ребрами
.
В случае когда множество вершин части
совпадает с
множеством вершин графа
, такой граф называется
сурграфом.
Нуль граф считается частью любого графа.
Частей можно изобразить столько, сколько имеется
семейств из ребер . Простейшей часть графа является ребро.
Часть графа ориентирована или неориентирована в
зависимости от того, ориентированный или неориентированный
сам граф.
Подграфом
графа
называется его
часть, вершины которой являются элементами множества
который является подмножеством
имеют своими ребрами
в
.
104
,
– а все ребра
, оба конца которых лежат
. Подграфом являются четыре
вершины, а ребра те что лежат в множестве
.
Если
Частичным
подграфом
графа
называется
подграф, ребра которого являются некоторые ребра графа
Обозначим
. Из примера
:
105
.
Если
совпадает с множеством
Степени и полустепени вершие.
Граф называется конечным, если число его ребер
конечно, в противном случае граф называется бесконечным.
При таком определении конечный граф может содержать
бесконечное множество изолированных вершин, но как правило
конечный граф имеет и конечное число изолированных вершин.
Валентностью вершины
или степенью вершины
называется число ребер, инцидентных этой вершине
.
При этом, если не оговаривать особо, петля учитывается два
раза.
Граф у которого все вершины имеют одинаковую
валентность называется правильным графом с валентностью
. (граф Петерсона)
Если у вершины степень равна нулю, то это
изолированная вершина, а вершина степени один концевая.
106
Для ориентированного графа вводятся понятия
положительной и отрицательной степени
– число
исходящих из этой вершины дуг,
эту вершину дуг.
– число входящих в
2
2
0
3
0
0
1
0
3
1
1
1
1
1
Каждая дуга имеет одну начальную и одну конечную
вершину. Поэтому в любом конечном графе сумма
положительных и отрицательных степеней равна числу дуг.
где
число дуг.
Из (1) и (2), следует что
Это так называемая лемма о рукопожатиях, т.е. число
степеней всех вершин графа равно четному числу, равному
удвоенному числу дуг.
Теорема: В конечном графе
число вершин
нечетной степени четно.
Доказательство:
Разобьем
множество
вершин
конечного графа
на два множества
и
, где
– все вершины нечетной степени, а
– все вершины четной степени.
Тогда из (3) получаем:
107
В (4) справа стоит четное число, второе слагаемое тоже
четное число, следовательно и первое слагаемое тоже должно
быть четным числом, а под знаком суммы входят нечетные
слагаемые. Чтобы в результате получилось четное число, этих
слагаемых должно быть четное число.
– минимальная степень вершины графа (в
примере
).
– максимальная степень вершины графа (в
примере
).
Если все
степень
, то такой
регулярным. Если
вершин, ребер не имеет.
отдельных ребер:
вершины графа имеют одинаковую
граф называется однородным или
, то граф состоит из изолированных
Если
, то этот граф состоит из
Если
, то граф этот циклический:
Если
, то
108
Матрица смежности
Дан граф с вершинами.
Матрицей смежности графа
квадратная матрица размерности
определены:
называется
, элементы которой
Это определение для неориентированного графа.
Для ориентированного графа определение
аналогичное:
Неориентированный граф
Замечание:
Матрица
смежности
для
неориентированного графа является симметричной, т.е.
. У неориентированного графа все параллельные
ребра будут изображаться матрицей смежности как
109
однократные, поэтому матрицу смежности нельзя использовать
для мультиграфов.
.
.
Степени матрицы смежности имеют содержательную
интерпретацию.
Пример:
.
,
.
,
соединены
парой
Следовательно,
тогда
дуг
вершина
и
и
(или
вершина
парой
ребер).
равно числу пар дуг, соединяющих
вершины
и
.
Если
цепочек из дуг (ребер).
, следовательно
110
равно числу
Матрица инцидентности
Дан граф
, где вершин и
ребер.
Матрицей инцидентности называется прямоугольная
матрица
, элементы которой определяются по формуле
, если -тая вершина инцидентна -тому ребру,
в противном случае или если ребро
петля.
Если у нас ориентированный граф:
111
есть
В каждом столбце, по две единицы, т.к. ребро имеет два
конца. Петлю и изолированную вершину нельзя восстановить
по матрице инцидентность. Поэтому матрицу инцидентности
нельзя применить для псевдографов.
В каждом столбце матрицы инцидентности для
ориентированного графа должна быть единица и минус
единица, т.к. есть начало и конец ребра.
Матрица смежности и инцидентности взаимно
дополняют друг друга и пригодны для простых графов.
Утверждение: Графы (орграфы) изоморфны тогда и
только тогда, когда их матрицы инцидентности (смежности)
получаются друг из друга перестановками строк и столбцов.
Пример: Найти матрицу смежности и матрицу
инцидентности.
112
Построение графа с заданным набором степеней
вершин
Пусть заданы неотрицательные числа
, где
. Надо построить граф
с вершинами
такой, что
. По лемме
равно четному числу, это условие необходимое, но не является
достаточным. Например, не существует графа с таким набором
степеней вершин (3,1,0,0). Ответ на поставленный вопрос дает
следующая теорема.
Теорема: (необходимое и достаточное условие
построение графа с заданным набором степеней вершин). Граф
с набором степеней вершин
(с
существует тогда и только тогда, если существует граф
вершиной) с набором степеней.
Здесь из чисел
вычитается единица, а
остальные степени остаются без изменения.
Доказательство:
Достаточность: Пусть дан граф с набором степеней (2).
113
Добавим к нему одну вершину и соединяем ее с
вершиной старших степеней набора (2).
И получаем граф с набором степеней (1).
Необходимость: Дан граф с набором степеней (1). Надо
показать, что можно получить, что существует граф с набором
степеней (2). Расположим вершину старшей степени
отдельно. Если эта вершина
соединена с
- вершинами
старших степеней, тотем самым необходимость доказана, т.к.
при удалении из графа вершины
, убираются и все ее ребра,
то каждая другая вершина тоже лишается ребра.
В противном случае будем иметь две вершины
и
такие, что
, что ребро
, а
Тогда найдется такая вершина
.
114
что
.
, а
Уберем ребро
уберем
, а добавим
, а добавим
и еще
. Мы пришли к ситуации:
соединена с
вершиной старших степеней. И тогда
убираем эту вершину и получаем граф с набором (2).
Алгоритм построения графа с заданным набором
степеней вершин
1.
Расположить степени в порядке невозрастания.
2.
Строим набор (2), т.е. отбрасываем наибольшую
степень
, а из следующих
чисел вычитаем по единице, а
остальные оставляем без изменения.
3.
Возвращаемся к пункту №1.
4.
Если на некотором шаге мы получаем набор,
реализуемым некоторым графом, то добавляем поочередно
новые вершины и стоим заданный граф.
5.
Требуемый граф не существует, если на
некотором шаге мы получаем нереализуемый набор, например,
отрицательные степени.
Пример:1)
с набором (1,1,2,2,7,5,4,3,7,2)
1.
( ,
,1,1)
2.
(6,
,1,1)
3.
4.
(3,2,1,0,0,0,1,1)
(3,
,1,0,0,0)
5.
(1,0,0,1,0,0,0)
6.
(1,1,0,0,0,0,0)
Итак:
2)(1,1,3,4,5,1,1)
1. (5
,1)
2. (3,2,0,0,0,1)
115
3. (3,
,0,0)
4. (1,0,-1,0,0) – нереализованный граф.
Связность
Любую организацию можно представить в виде графа
, где вершинами будут отдельные сотрудники или
подразделения, а ребрами – отношения между ними,
отражающие подчиненность, потоки связи, потоки информации
и т.д.
При анализе структуры организации возникает ряд
вопросов: Существует ли взаимосвязь между вершинами
и
? Сколькими звеньями связаны эти вершины? С какими
вершинами связана
одной, двумя, тремя и т.д. инстанциями.
На все эти вопросы отвечает понятие достижение
вершины.
4.3.Маршруты, цепи, циклы
Изучение достижимости связано с понятием маршрута,
которое является одним из ключевых понятий теории графов.
Граф
неориентирован.
Маршрутом называется конечная или бесконечная
последовательность
ребер
неориентированного
графа такая, что каждые два соседних ребра
общую вершину.
имеют
Как вершины, так и ребра в маршруте могут встречаться
неоднократно.
Пример:
116
Прописать маршрут из
в
.
– простые
цепи.
– маршрут.
Если в (1) нет ребер, предшествующих ребру
то
вершина
называется начальной вершиной маршрута, если в
(1) нет ребер следующих за ребром
, то вершина
называется конечной вершиной.
Любая вершина в (2), принадлежащая двум соседним
ребрам, называются внутренними или промежуточными
вершинами маршрута. Внутренними вершинами могут
оказаться как начальная, так и конечная вершины маршрута.
Нетривиальный маршрут – маршрут, состоящий хотя
бы из одного ребра.
Нуль маршрут – маршрут, где нет ни одного ребра.
Если
начальная вершина,
конечная вершина, то
маршрут
.
Длина маршрута – это число его ребер ( – длина
маршрута).
Если начальная и конечная вершины совпадают, то
маршрут называется замкнутым или циклическим.
Для любых двух вершин
и
подмаршрутом
маршрута
называется (конечным) участком
маршрута.
Если в маршруте ребра не повторяются то такой
маршрут называется цепью.
Простая цепь – маршрут, где все вершины (ребра)
различны.
Замкнутая цепь – это цикл.
117
Простой цикл – это простая замкнутая цепь.
Если граф ориентированный.
Цепь называется путем, а ориентированный цикл
называется контуром.
Связные компоненты
Пусть – неориентированный граф.
Вершины
и
графа
называются связными, если
существует маршрут вида (1), связывающий эти вершины и .
Если маршрут проходит через какую-либо вершину
более одного раза то можно удалить циклический участок и
тогда вершины и будут связаны простой цепью. Связанные
маршрутами вершины связаны и простой цепью.
Связный граф – граф, в котором любые две вершины
связаны.
Пусть – ориентированный граф.
Ориентированный граф
называется сильно связным,
если существует путь из вершины
в
и путь из
в , где
,
– произвольные вершины графа.
Ориентированный граф
называется односторонне
связанным, если для любых двух вершин
и
существует по
крайней мере путь из
в
или из
в
или оба
одновременно.
Ориентированный граф
называется слабо связным,
если для любых двух его вершин
и
существует по крайней
мере один маршрут, соединяющий их.
Ориентированный граф называется несвязным, если он
не является слабо связным.
118
Пример:
По соотношению , где
– отношение связности
записывают:
, т.е. связано .
1.
Рефлексивность
;
2.
Симметрия
;
3.
Транзитивность
.
Если отношение обладает всеми этими свойствами, то
оно называется отношением эквивалентности.
По известной теореме отношение эквивалентности
порождает разбиение, т.е. все множество вершин можно
представить
.
Это
пересечение
и
связаны между собой, но с
они не
связаны.
119
По (3) наш граф – это объединение подграфов, а каждый
из подграфов
есть связный граф:
.
Эти подграфы
называются связными компонентами,
следовательно, вытекает теорема:
Теорема: Каждый неориентированный граф распадается
в прямую сумму (4) (единственным образом) своих связных
компонент.
Говорят, что вершина
ориентированного графа
достижима из вершины , если хотя бы один путь (маршрут,
соединяющий
с ) из
в .
4.4. Метрические характеристики графа
Пусть
связный
неориентированный
граф.
Следовательно, любые две вершины соединяются маршрутом,
следовательно, простой цепью с концами и .
Длины этих цепей есть целые неотрицательные числа,
следовательно, среди них должно существовать наименьшее.
Длина кратчайшей цепи, соединяющей вершины и ,
называется расстоянием между вершинами
и
,
обозначается:
.
По определению расстояние
Очевидно, что справедливы
метрики для введенной функции
1.
2.
3.
4.
треугольника.
.
следующие
:
аксиомы
– свойство симметрии;
– неравенство
120
Пусть
– некоторая вершина графа
. Условным
радиусом
называется максимальное расстояние от
до
других вершин графа.
где
.
Радиусом графа
условных радиусов графа.
называется
минимальное
из
где
.
Вершина графа
называется центром графа,
если ее условный радиус совпадает с радиусом графа
. Очевидно, что центр графа может быть не один.
Максимальное из условных радиусов называется
диаметром
графа.
где
. Очевидно, что
.
Для ориентированного графа
, который связан,
понятие расстояние между вершинами
и , вводится как
расстояние между
и
в соотнесенном неориентированном
графе.
Центром может быть и все множество вершин графа.
Если вершины интерпретировать как населенные
пункты, а ребра – дороги между ними. То возникает вопрос как
найти центр графа.
Можно применить волновой метод (алгоритм фронта
волны). Этот волновой метод служит для определения
минимального маршрута, связывающего вершины
и , т.е.
для нахождения расстояния
.
121
Алгоритм:
1.
Пометим
вершину
,
связанного
неориентированного графа индексом 0. Вершины, смежные с
вершиной
пометим индексом 1 и отнесем их множеству
. К множеству
отнесем вершины которые еще не
помечены и смежные с вершинами из множества
. Их
пометим индексом 2.
2.
Совокупность вершин, помеченных индексом ,
обозначим
3.
.
Множество
– те вершины графа, которые
не входят в
, и смежные с некоторыми из
вершин множества
. Множество
называется фронтом
волны
уровня.
В некоторый момент вершина
4.
тоже будет
помечена и пусть она, например, попадет во фронт волны –
уровня, т.е.
. Тогда останавливаем процесс индексации.
5.
По построению можно найти вершину
,
которая принадлежит
и смежную с . Затем можно найти
вершину
и т.д.
6.
Искомое расстояние есть последовательность
ребер с вершинами
, где
,
ребро
–
ребра
графа,
т.е.
принадлежащие
, т.е. двигаться надо в сторону
убывания индекса.
Замечание1: Если в пункте 4 индексацию не
останавливать, то через некоторое количество шагов все
вершины, графа получат индекс и наибольший индекс будет
представлять собой условный радиус относительно вершины .
Замечание2: Если будем двигаться от вершины
в
сторону возрастания индекса, то можно зайти в тупик и никогда
не попасть в вершину .
122
Замечание3: Выбор последовательности вершин
, вообще говоря не однозначен. Эта
неоднозначность соответствует случаям, когда существует не
один минимальный маршрут.
Замечание4: Пусть
– орграф. В этом случае этот
метод позволит решить две задачи:
1.
Найти расстояние от вершины
до остальных
вершин графа;
2.
Найти длины кратчайших путей от каждой
вершины графа до вершины . В этом случае в пункте 3 будут
изменения:
А)
и существует дуга из
в .
В)
и
существует дуга из в
.
Пример: Найти
для неориентированного графа
.
Замечание5: Для нахождения радиуса графа надо
построить волны из каждой вершины.
123
Пример: Составить таблицу расстояний между
вершинами графа, указать условные радиусы, радиус графа,
центры и диаметр графа.
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
0
1
2
1
2
1
2
3
1
0
1
1
2
2
3
2
2
1
0
1
2
3
2
1
1
1
1
0
1
2
2
2
2
2
2
1
0
2
1
2
1
2
3
2
2
0
1
2
2
3
2
2
1
1
0
1
3
2
1
2
2
2
1
0
3
3
3
2
2
3
3
3
Центром является четвертая и третья вершины.
Диаметральная цепочка
совпадает с диаметром графа, т.е.
124
–
цепь,
длина
.
которой
4.5. Планарность
Известно, что не важно как изображать графы, т.к.
изоморфные графы несут одинаковую информацию, но бывают
ситуации, когда важно выяснить можно ли можно ли изобразить
данный граф на плоскости так, чтобы он удовлетворял
определенным требованиям (в радиоэлектронике ИМС
наносятся на изоляционную поверхность материала печатным
способом, а сама проводники не изолированы, поэтому у графа
не должно быть пересечений, чтобы не произошло замыкание;
аналогичная
задача
возникает
при
проектировании
железнодорожных путей, где нежелательны переезды). Все это
приводит к понятию плоских графов.
Плоским графом называется граф, вершинами которого
являются точки плоскости, а ребрами непрерывные
самопересекающиеся линии, соединяющие вершины так, что
никакие два ребра не имеют общих точек, кроме инцидентных
им обоим вершины.
Пример:
Любой граф
планарным.
Пример: граф
изоморфный
плоскому
называется
изоморфен графам 2) и 3), следовательно является
планарным.
125
Плоский граф, изоморфный графу называется картой
графа .
Плоский граф называется связным если связан
соответствующий планарный граф.
Утверждение1: Любой граф планарного графа
планарен.
Утверждение2: Для того, чтобы граф
был планарен
необходимо и достаточно, чтобы каждая его связная компонента
была планарной.
Возможен вопрос: а есть ли непланарные графы? Ответ
дает классическая головоломка «Задача о трех домах и трех
колодцах».
Задача: Есть три дома и три колодца.
Каждый сосед может
пользоваться любым из трех
колодцев. В один день они
поссорились
и
решили
проложить тропинки к каждому
колодцу, чтобы не встречаться.
Можно ли это сделать? 8
дорожек можно провести, а
девятую нельзя. Граф
не
является
планарным
и
справедливо следующие утверждение.
Утверждение3:
планарными.
Почти
126
все
графы
не
являются
Каждый плоский граф разбивает плоскость на области:
- конечные области,
- неограниченные области.
Справедлива следующая теорема Эйлера (1758г.)
Теорема: Для всякого связного планарного графа
справедлива
формула:
,где.
– мощность множества вершин.
– мощность множества ребер.
– мощность множества областей.
Доказательство: Пусть граф состоит из одной вершины,
т.е.
и формула (1)
справедлива. Как можно получить любой граф из графа с одной
вершиной: последовательно расширяя его от одной к двум и т.д.
Расширение может идти двумя путями:
1)
Добавлением новой вершины и образованием
нового ребра, например:
Следовательно,
увеличился на 1,
тоже
увеличился на единицу. Поэтому, значение выражения осталось
неизменным.
2)
Соединением двух смежных вершин:
127
– остальные прежние,
и
увеличился на 1.
По прежнему значение выражения слева в (1) осталось
неизменным, т.е. (1) является инвариантным, т.е. неизменным,
если расширяется граф 1) или 2) путем. А т.к. (1) справедлива
для
, то оно (1) верно.
Очевидно, что каждая область ограничена замкнутым
маршрутом.
Пусть граф
планарный, под степенью
области
(степень
) будем понимать длину замкнутого
маршрута, ограничивающего эту область в изоморфном,
данному планарному графу плоском графе.
Пример:
\
Утверждение4: Сумма всех степеней
равно удвоенному числу ребер графа, т.е.
128
, где
Утверждение5: Если
.
Утверждение6: Графы
планарными.
,
то
число
и
ребер
не являются
Доказательство:
1)
Для
от противного: пусть
планарен
по утверждению 5
,а
здесь
. Мы пришли к противоречию.
2)
Для
. Пусть он планарен, следовательно, по
утверждению 4
. Т.к. в
любые три вершины
не являются связными, то
Эйлера
имеем,
должно быть
что
, а из формулы
мощность
, а она равна 18. Мы пришли к противоречию.
– минимальные не планарные графы.
Пусть дан граф
графа
. Элементарное стягивание
образуется путем удаление ребра
переименованием вершин
и
удалением вершин
из множества вершин
и
новым символом
и
,
и
добавлением вершины в . Графически элемент стягивания –
слияние двух смежных вершин и удаление ребра между ними.
129
Говорят, что граф
стягивается к графу
, если граф
получается из
путем последовательности элементарных
стягиваний.
Пример:
Теорема Понтрягина(1927)-Куратовского(1930): Граф
планарен тогда и только тогда, когда он не содержит подграфов,
стягиваемых к
и
.
4.6 Раскраска карт и графов
Раскраской графа
называется задание цвета
вершинам графа так, чтобы никакие две вершины графа не
имели одинаковый цвет.
Раскраска графа имеет огромное практическое значение.
Характерной особенностью задачи о раскраске является
существование объектов, которые по каким либо причинам не
могут быть объединены в одну группу. Эти задачи возникли при
планировании производства, транспортирования и хранения
товаров, при составлении графиков осмотра и т.д.
Хроматическим числом
– «хи» называется
минимальное число цветов, требующихся для раскраски графов.
Такие раскраски о которых речь шла выше называются
правильными. Если требуется
цветов для правильной
раскраски, то раскраска называется правильной -раскраской.
Пример:
130
1,2,… цвета.
– циклическое, поэтому
окрашена в 3 цвет, а надо 4 цвета: 4-раскраска.
Для некоторых графов
найти несложно. Для
полного графа
, для двудольного графа
.
Очевидно,
что
граф
однохроматический
(1хроматический) тогда и только тогда, когда он нуль-граф
(пустой граф), а 2-хроматическим тогда и только тогда, когда он
двудольный и непустой.
Алгоритмы нахождения раскрасок и определение
очень сложны. До сих пор еще нет эффективных алгоритмов.
Самым простым является алгоритм последовательной
раскраски, который в ряде случаев приводит к раскраскам,
близким к
минимальным. Этот алгоритм имеет следующий
вид:
1.
Произвольной вершине графа
припишем цвет
1.
2.
Смежной с ней вершине припишем цвет 2.
3.
Если вершины
окрашены в
цветов
, где
, то новой произвольно взятой
вершине
припишем
минимальный
цвет,
не
использованный при раскраске вершин из ее окружения.
131
Для некоторых классов графов (полных,
дольных)
этот алгоритм дает минимальную раскраску. В общем случае
это не так.
Поскольку задачу правильной раскраски графов точно
решить трудно, то актуальны оценки для хроматического числа
.
– наибольшая степень вершины графа.
Оценка. Для любого графа
имеет место следующая
оценка
. В 1941 году Брукс улучшил эту
оценку: если граф
связный, то
.
4.7 Проблема четырех красок
Рассмотрим так называемые карты. Это разбиение
плоскости на связные области, т.е. при проведении в них
замкнутого самонепересекающегося контура он будет
содержать в себе только точки этой области (приблизительное
определение связной области).
– замкнутый самонепересекающийся контур.
– замкнутый самопересекающийся контур.
Можно ли раскрасить карту используя только 4 цвета? В
1890 году американец Хейвуд доказал теорему:
Теорема: Если граф планарен, то его хроматическое
число не превосходит пяти, т.е.
(теорема о пяти
красках).
В 1976 г. Аппель и Хакен доказали эту теорему, что:
Теорема: Если планарен, то
.
Но твердой уверенности в том, что эта теорема доказана
нет.
Двойственный граф. Пусть дан граф . Двойственный
граф
определим следующим образом: выберем внутри
каждой области плоский графа внутреннюю точку. Если
132
области имеют общее ребро, то проведем дугу, связывающую
выбранные внутренние точки в этих областях. Этот процесс и
определяет двойственный граф .
Раскраска графа
дает раскраску областей графа . И
все теоремы можно перефразировать на карты.
Теорема: Если области плоского графа
необходимо
раскрасить таким образом, чтобы любые смежные области
имели разные цвета, то для этого потребуется не более четырех
цветов.
Пример:
1.
В корзине 12 яблок и 10 апельсинов. Ваня
выбирает из нее яблоко или апельсин, после чего Надя берет и
яблоко и апельсин. В каком случае Надя имеет большую
свободу выбора: если Ваня взял яблоко или если он взял
апельсин.
Решение:
Пусть он взял яблоко, следовательно, 11 яблок и 10
апельсинов.
Надя может взять =110 способами.
Пусть он взял апельсин, следовательно, 12 яблок и 9
апельсинов.
.
. Следовательно, больше выбора когда он
возьмет яблоко.
2.
На полке собрание сочинений в 30 томах: a)
сколькими способами их можно переставить. Решить эту задачу
при условии, что b) том 2 стоит за томом 1; c) тома 1и 2 стоят
рядом; d) тома 1 и 2 рядом не стоят; e) тома 3 и 4 рядом не стоят.
133
Решение:
a)
b)
1 и 2 том берем за одну книгу, следовательно,
.
c)
d)
e)
134
Глоссарий
Антирефлексивность – отношение, если
.
– отношение антирефлексивно.
Антисимметричность – отношение, если из выполнения двух
условий
.
отношение антисимметричное.
Беспорядок - перестановка из элементов, при которой ни один
элемент не остается на своем месте. Число беспорядков
обозначается
.
Булева алгебра логических функций - система
,
носителем является множество булевых функций , а
сигнатурой являются булевы операции –
.
Валентность вершины
или степень вершины - число ребер,
инцидентных этой вершине
. При этом, если не
оговаривать особо, петля учитывается два раза.
Векторупорядоченный
набор
элементов
.
Граф
с множеством вершин
-
семейство пар вида
, где
вершины графа, а
элементы вида
называются ребрами графа.
Дизъюнктивная нормальная форма (ДНФ) -дизъюнкция
произвольного числа элементарных конъюнкций называется
135
Двойственная
функцияя
к
функции
, если выполняется равенство:
Замкнутая цепь – это цикл.
Импликанты - элементарные конъюнкции, которые входят в
ДНФ, реализующие данную булеву функцию
Класс эквивалентности
, порожденным элементом
подмножество элементов множества
таких, которые
вступают в отношение с элементами .
Комбинаторика – дисциплина, изучающая методы выбора и
расположения элементов некоторого конечного множества, а
так же методы подсчета числа комбинаций, которые можно
составить из элементов данного множества.
Композиция – совокупность пар таких, что
принадлежат
графику
,
принадлежат графику
.
Конечное множество - множество, если число его элементов
конечно. В противном случае множество называется
бесконечным.
Конъюнктивная нормальная форма (КНФ) - конъюнкция
произвольного числа элементарных дизъюнкций
Маршрут - конечная или бесконечная последовательность ребер
неориентированного графа
ребра
такая, что каждые два соседних
имеют общую вершину.
136
Как вершины, так и ребра в маршруте могут встречаться
неоднократно.
Матрица инцидентности - прямоугольная матрица
,
элементы которой определяются по формуле
, если тая вершина инцидентна -тому ребру,
случае или если ребро
ориентированный граф:
есть
Матрица смежности графа
размерности
в противном
петля.
Если
- квадратная матрица
, элементы которой определены:
Это определение для неориентированного графа.Если
ориентированный граф
Множество – совокупность системы каких-либо объектов,
обладающих характерными для них общими свойствами.
Монотонная функция - функция
любых
двух
векторов
, если для
из
того,
Мощность множества - количество его элементов.
Мощность континуума( ) - мощность отрезка
действительных чисел.
137
что
-местное отношение на множестве
. Говорят, что элементы
отношении , если вектор
- подмножество
находятся в
.
Одноместным отношением будет само множество .
Полином Жегалкина - булева функция, представленная в виде
полинома
Объединение множеств А и В - множество, элементы которого
принадлежат хотя бы одному из множеств А или В и не
содержат никаких других элементов.
Отношение строго порядка – отношение антирефлексивное,
антисимметричное и транзитивное.
Отношение частичного порядка
- отношение рефлексивное,
антисимметричное и транзитивное отношение.
Отношение эквивалентности - отношение рефлексивное,
симметричное и транзитивное.
Перестановка – упорядоченная комбинация из
элементов
множества . Т.е. перестановки это такие размещения, которые
отличаются друг от друга, только порядком следования
элементов.
.
Планарный граф -граф изоморфный плоскому.
Плоский граф - граф, вершинами которого являются точки
плоскости, а ребрами непрерывные самопересекающиеся линии,
соединяющие вершины так, что никакие два ребра не имеют
общих точек, кроме инцидентных им обоим вершины.
138
Подмножество множества А -множество В, если каждый
элемент множества В принадлежит и множеству А.
не исключает того, что А совпадает с В.
Полный граф - граф, ребрами которого являются всевозможные
пары
для двух различных вершин из . Т.е. граф полный
если он содержит все допустимые ребра, т.е. вершины
соединены ровно одним ребром.
Порождающая процедура – способ получения элементов
из известных элементов множества или из других
объектов.
Правило произведения – правило, если какой либо объект
можно выбрать
способами и после каждого выбора объекта
объект
выбрать
способами, то выбор пары
(в
указанном порядке) осуществляется
способами.
Обобщение:
– обобщенное правило произведения.
Правило суммы - правило в комбинаторике, если какой-либо
объект можно выбрать
способами, а объект
выбрать
способами, причем ни один из способов выбора объекта
не
совпадает ни с одним из способов выбора объекта , то выбор
либо , либо осуществляется
способами.
Обобщение:
– число совпадающих способов.
Простой граф - граф, у которого нет петель и множество ребер.
Простая цепь – маршрут, где все вершины (ребра) различны.
Простой цикл – это простая замкнутая цепь.
Прямые или декартовое произведение множеств А и В совокупность упорядоченных пар А и В таких, что первый
элемент берется из множества А, а второй элемент берется
из множества В.
139
Пустое множество – множество, не содержащее ни одного
элемента. Пустое множество является подмножеством любого
множества.
Пересечение множеств А и В - множество, элементы которого
принадлежат и множеству А и множеству В.
Псевдограф - граф, имеющий петли, но не имеющий
параллельных ребер.
Равномощные множества - два бесконечных множества, если
между их элементами устанавливается взаимно однозначное
соответствие.
Радиус графа
- минимальное из условных радиусов графа.
, где
.
Центр граф - вершина графа
, если ее условный
радиус совпадает с радиусом графа
. Очевидно, что
центр графа может быть не один.
Диаметр
графа. -максимальное из условных радиусов
называется
,где
. Очевидно, что
.
Разбиение множества
- совокупность непересекающихся
подмножеств множества
таких, что каждый элемент
множества
принадлежит только одному из подмножеств.
Размещением из
по
элемента - комбинации объема
,
составленные из элементов множества , которые отличаются
друг от друга либо самими элементами, либо порядком их
следования.
Разность множеств А и В -множество, состоящее из элементов
множества А, не принадлежащих множеству В.
140
Раскраска графа
- задание цвета вершинам графа так,
чтобы никакие две вершины графа не имели одинаковый цвет.
Самодвойственная функция -функция ,если
Симметрическая разность множеств А и В - множество, сумма
элементов множества А без элементов множества В и элементов
множества В без элементов множества А.
Совершенная дизъюктивная нормальная форма -СДНФ – ДНФ,
которая состоит из различных правильных и полных
элементарных конъюнкций.
Совершенная конзъюктивная нормальная форма -СКНФ – КНФ,
которая состоит из различных правильных и полных
элементарных дизъюнкций.
Сочетания без повторений из
по
элементов –
неупорядоченная комбинация объема
. Сочетания –
комбинации, которые отличаются хотя бы одним элементом.
Суперграф – граф, имеющий и параллельные ребра, и петли.
Теорема Кантора - множество действительных чисел
отрезка
не является счетным.
Транзитивность
отношение,
.
отношение
-
если
транзитивно.
Тупиковая дизъюнктивная нормальная форма - ДНФ, которую
нельзя упростить, путем удаления из нее какой либо
элементарной конъюнкции или удалением какого либо
множителя
.
141
Минимальная ДНФ - тупиковая ДНФ, обладающая наименьшим
числом букв, обозначающих переменные.
Функционально полная система функций - система функций
, если любая булева функция может быть
представлена с помощью суперпозиции этих функций:
Функция - бинарное отношение ,если из того, что
и
.
– область определения функции.
– область значения функции.
Хроматическое число
– «хи» - минимальное число
цветов, требующихся для раскраски графов.
Элементарная дизъюнкция - выражение вида
Число называется рангом элементарной дизъюнкции.
Элементарная конъюнкция - выражение вида
Число
называется рангом элементарной конъюнкции.
142
Список литературы
Основная литература
Алашеева, Е. А.Дискретная математика [Текст]:
конспект лекций / Е. А. Алашеева; ПГУТИ. - Самара:
ИУНЛ ПГУТИ, 2013. - 143 с.
2.
Гашков, С.Б. Дискретная математика: Учебник и
практикум для академического бакалавриата / С.Б. Гашков,
А.Б. Фролов. - Люберцы: Юрайт, 2016. - 423 c.
3.
Дмитриевский, В.Н. Дискретная математика: графы,
матроиды, алгоритмы: Учебное пособие / В.Н.
Дмитриевский. - СПб.: Лань КПТ, 2016. - 368 c.
1.
Дополнительная литература
Новиков,
Ф.А.
Дискретная
математика
для
программистов. – СПб.:Питер, 2001.
2. Шапорев, С.Д. Дискретная математика. –СПб:БХВПетербург, 2007
3. Яблонский, С.В. Введение в дискретную математику. –
М.: Высш. шк., 2002.
1.
143
Документ
Категория
Без категории
Просмотров
17
Размер файла
2 892 Кб
Теги
posobie, matematiki, uchebnoy, diskretnaya, rogova
1/--страниц
Пожаловаться на содержимое документа