ДМ


МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)Кафедра автоматизированных систем управления (АСУ)
УТВЕРЖДАЮ
Зав. кафедрой АСУ
профессор д-р техн. наук
_______________А.М. Кориков
«_____»______________1999 г.
ДИСКРЕТНАЯ МАТЕМАТИКАМетодическое пособие по дисциплине
«Дискретная математика»
для студентов специальностей 071900
«Информационные системы в экономике» и 22040
«Программное обеспечение вычислительной техники
и автоматизированных систем»
Конспект лекций, часть 1
Разработчик
канд. техн. наук, доцент
_____________ Е.Н. Сафьянова
1999
Методическое пособие рассмотрено и рекомендовано к изданию методическим семинаром кафедры автоматизированных систем управления ТУСУР 17 мая 1999 г.
Зав. кафедрой АСУ
проф. д-р техн. наук А.М.Кориков
© Е.Н. Сафьянова, 1999 г.
© ТУСУР, каф. АСУ, 1999 г.
СОДЕРЖАНИЕ TOC \o "1-3" ВВЕДЕНИЕ PAGEREF _Toc460599550 \h 5
1 ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ МНОЖЕСТВ PAGEREF _Toc460599551 \h 6
1.1 Основные определения PAGEREF _Toc460599552 \h 6
1.2 Операции над множествами PAGEREF _Toc460599553 \h 7
1.3 Отношения на множествах PAGEREF _Toc460599554 \h 11
1.4 Экстремальные элементы множеств PAGEREF _Toc460599555 \h 14
1.5 Отображения множеств PAGEREF _Toc460599556 \h 14
1.6 Задачи и упражнения PAGEREF _Toc460599557 \h 16
2 ОСНОВЫ ТЕОРИИ ГРАФОВ PAGEREF _Toc460599558 \h 18
2.1 Основные определения PAGEREF _Toc460599559 \h 19
2.1.1 Общие понятия PAGEREF _Toc460599560 \h 19
2.1.2 Ориентированные и неориентированные графы PAGEREF _Toc460599561 \h 20
2.1.3 Цепи, циклы, пути и контуры графов PAGEREF _Toc460599562 \h 21
2.1.4 Конечный и бесконечный графы PAGEREF _Toc460599563 \h 22
2.1.5 Частичные графы, подграфы, частичные подграфы PAGEREF _Toc460599564 \h 22
2.1.6 Связность в графах PAGEREF _Toc460599565 \h 24
2.1.7 Изоморфизм. Плоские графы PAGEREF _Toc460599566 \h 25
2.2 Отношения на множествах и графы PAGEREF _Toc460599567 \h 26
2.3 Матрицы смежности и инциденций графа PAGEREF _Toc460599568 \h 29
2.4 Операции над графами PAGEREF _Toc460599569 \h 30
2.5 Степени графов PAGEREF _Toc460599570 \h 36
2.5.1 Степени неориентированных графов PAGEREF _Toc460599571 \h 36
2.5.2 Степени ориентированных графов PAGEREF _Toc460599572 \h 37
2.6 Характеристики расстояний в графах PAGEREF _Toc460599573 \h 38
2.7 Определение путей и кратчайших путей в графах PAGEREF _Toc460599575 \h 40
2.7.1 Алгоритм определения пути в графе PAGEREF _Toc460599576 \h 40
2.7.2 Алгоритм определения кратчайших путей в графе PAGEREF _Toc460599577 \h 41
2.8 Обход графа PAGEREF _Toc460599578 \h 45
2.8.1 Эйлеровы цепи, циклы, пути, контуры PAGEREF _Toc460599579 \h 45
2.8.2 Гамильтоновы цепи, циклы, пути, контуры PAGEREF _Toc460599580 \h 49
2.9 Характеристики графов PAGEREF _Toc460599581 \h 50
2.10 Задачи и упражнения PAGEREF _Toc460599582 \h 51
3. ОСНОВЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ PAGEREF _Toc460599583 \h 523.1 Алгебра высказываний PAGEREF _Toc460599584 \h 52
3.2 Булевы функции PAGEREF _Toc460599585 \h 56
3.3 Совершенные дизъюнктивная и конъюнктивная нормальные формы PAGEREF _Toc460599586 \h 58
3.4 Полнота системы булевых функций PAGEREF _Toc460599587 \h 60
3.5 Минимизация дизъюнктивных нормальных форм PAGEREF _Toc460599589 \h 65
3.5.1 Основные определения PAGEREF _Toc460599590 \h 65
3.5.2 Этапы минимизации ДНФ PAGEREF _Toc460599591 \h 66
3.5.3 Минимизация ДНФ методом Квайна PAGEREF _Toc460599592 \h 69
3.6 Автоматные описания PAGEREF _Toc460599593 \h 72
3.7 Синтез комбинационных схем PAGEREF _Toc460599594 \h 76
3.8 Логика предикатов PAGEREF _Toc460599595 \h 79
3.8.1 Предикаты и операции квантирования PAGEREF _Toc460599596 \h 79
3.8.2 Равносильные формулы логики предикатов PAGEREF _Toc460599597 \h 81
3.9 Задачи и упражнения PAGEREF _Toc460599598 \h 83
Список литературы PAGEREF _Toc460599599 \h 84
ВВЕДЕНИЕДля создания и эксплуатации сложных автоматизированных систем обработки информации и их компонент в области экономики, математи-ческого и программного обеспечения вычислительной техники, сетей передачи данных и многих других сферах деятельности человека необходимо знание дискретной математики.
Дискретная математика – часть математики, которая зародилась в глубокой древности. Как говорит само название, главной ее особенностью является дискретность, т.е. антипод непрерывности. В ней отсутствует понятие предельного перехода, присущее классической, «непрерывной» математике. Дискретная математика занимается изучением дискретных структур, которые возникают как внутри математики, так и в ее приложениях.
Цель дисциплины «Дискретная математика» знакомство с основными разделами зтой науки: теорией множеств, математической логикой, теорией графов, теорией алгоритмов, комбинаторным анализом как аппаратом для построения моделей дискретных систем.
Дискретная математика является обязательной дисциплиной цикла «Математические и общие естественнонаучные дисциплины». Знания и навыки, полученные при ее изучении, используются в дисциплинах: «Информатика», «Программирование», «Структуры и алгоритмы обработки данных в ЭВМ», «Базы данных» и т.д.
Настоящее пособие представляет собой курс лекций, читаемый в Томском государственном университете систем управления и радиоэлектроники студентам специальностей «Программное обеспечение вычислительной техники и автоматизированных систем» и «Информационные системы в экономике».
Пособие рассчитано на изучение в течение двух семестров и в соответствии с этим разбито на две части.
В первой части излагаются основы теории множеств, теории графов, элементы алгебры высказываний, теории булевых функций и логики предикатов.
Вторая часть посвящена изложению основ построения формальных теорий, знакомству с основными разделами теории алгоритмов: аппаратом рекурсивных функций, машинами Тьюринга, нормальными алгоритмами Маркова. Завершает вторую часть раздел, дающий представление о задачах и основных построениях комбинаторного анализа.
В конце каждого раздела приведены задачи и упражнения, которые необходимо выполнить для закрепления теоретического материала.
1 ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ МНОЖЕСТВ1.1 Основные определенияПонятие множества является фундаментальным неопределяемым понятием. Интуитивно под множеством понимают совокупность вполне определенных различаемых объектов, рассматриваемых как единое целое.
Природа объектов может быть самой различной. Так, можно говорить о множестве стульев в комнате, людей, живущих в Томске, студентов в группе, о множестве натуральных чисел, букв в алфавите, состояний системы и т.п. Но нельзя, например, говорить о множестве капель в стакане воды, так как невозможно четко и ясно указать каждую отдельную каплю, капли неразличимы между собой.
Отдельные объекты, из которых состоит множество, называют его элементами.
Для обозначения конкретных множеств принято использовать прописные буквы A, S, X, ... . Для обозначения элементов множества используют строчные буквы a, s, x, ... . Множество X, элементами которого являются x1, x2, x3 , обозначают X = {x1, x2, x3}. Это один способ задания множества перечисление всех его элементов. Он удобен при рассмотрении конечных множеств, содержащих небольшое число элементов. Второй способ задания множества описательный состоит в том, что указывается характерное свойство, которым обладают все элементы множества. Так, если M множество студентов группы, то множество X отличников этой группы записывается в виде
X = {x M / x - отличник группы},
что читается следующим образом: множество X состоит из элементов x множества M таких, что x является отличником группы. Множество простых чисел записывается как X = {x / x - простое}. Для указания того, что элемент x принадлежит множеству X, используется запись x X. Запись x X означает, что элемент x не принадлежит множеству X.
Множество называется конечным, если оно содержит конечное число элементов, и бесконечным, если число его элементов бесконечно. Множество, не содержащее ни одного элемента, называется пустым. Пустое множество обозначается , например:
X ={x C / x2 - x + 1 = 0} = ,
где С - множество целых чисел. Пустое множество условно относится к конечным множествам.
Два множества X и Y равны в том и только в том случае, когда они состоят из одних и тех же элементов, т.е. X = Y, если x X, то x Y и если y Y, то y X.
Множество X является подмножеством множества Y, если любой элемент множества X принадлежит множеству Y. Этот факт записывается как X Y.
Последовательность из n элементов множества называется n-строчкой или кортежем. В n-строчке каждый элемент занимает определенное место, тогда как во множестве порядок расположения элементов роли не играет.
Для сокращения записи в теории множеств используются некоторые логические символы. Это кванторы общности и существования , а также символы следствия (импликации) и логической эквивалентности . Смысл этих обозначений следующий:
- «любой», «каждый», «для всех»;
- «существует», «найдется», «хотя бы один»;
- «влечет», «имеет следствием»;
- «тогда и только тогда», «необходимо и достаточно».
Использование логических символов, например, для определения подмножества, которое может быть сформулировано в виде: для любого x утверждение «x принадлежит X» влечет за собой утверждение «x принадлежит Y», приводит к записи:
x [x X x Y].
Запись X Y и Y X X = Y означает: для того, чтобы X было равно Y необходимо и достаточно, чтобы X Y и Y X.
1.2 Операции над множествамиНад множествами можно производить действия, которые во многом напоминают действия сложения и умножения в элементарной алгебре. Для графической иллюстрации операций над множествами будем использовать так называемые диаграммы Эйлера, в которых произвольному множеству X ставится в соответствие множество точек на плоскости внутри некоторой замкнутой кривой.
Объединением (суммой) множеств X и Y называют множество, состоящее из всех тех и только тех элементов, которые принадлежат хотя бы одному из множеств X, Y (рис.1.1).
Объединение двух множеств символически записывают как X Y или Y X. Объединение множеств Xi (i = 1, 2, ... N) есть множество элементов, каждый из которых принадлежит хотя бы одному из множеств Xi. Соответствующее обозначение: .

Рис. 1.1 – Объединение множеств
Пересечением множеств X и Y называют множество, состоящее из всех тех и только тех элементов, которые принадлежат как множеству X, так и множеству Y (рис.1.2).
Пересечение множеств обозначается через X Y. Множества X и Y называют непересекающимися, если они не имеют общих элементов, т.е. если
X Y = .

Рис. 1.2 – Пересечение множеств
Пересечением множеств X i (i = 1, 2, ... N) называется множество элементов, принадлежащих всем X i. Оно обозначается как .
Разностью множеств X и Y называют множество, состоящее из всех тех элементов, которые принадлежат X и не принадлежат Y (рис.1.3). Разность множеств обозначается через X \ Y.
Рис. 1.3 – Разность множеств
Пример 1. Пусть X – множество отличников в группе, Y – множество студентов, проживающих в общежитии. Тогда X Y – множество студентов, которые или учатся на «отлично», или проживают в общежитии, X Y – множество отличников, проживающих в общежитии, X \ Y множество отличников, живущих вне общежития.
Дополнительным к множеству X по отношению к множеству W, если X W, называется множество, состоящее из элементов W, не принадлежащих множеству X. Символически дополнительное множество обозначается как ZW(X) (рис.1.4).
Рис. 1.4 – Дополнительное множество
Универсальным множеством называется множество I, для которого справедливо соотношение: X I = X, означающее, что множество I содержит все элементы множества X, так что любое множество X полностью содержится во множестве I. Так, для примера 1 универсальным множеством можно считать множество студентов в группе.
Универсальное множество удобно изображать графически в виде множества точек прямоугольника. Отдельные области внутри этого прямоугольника будут представлять различные подмножества универсального множества.
Множество X, определяемое из соотношенияX = I \ X, называют дополнением множества X (до универсального множества I). На рис 1.5. множествоX представляет собой не заштрихованную область.
Рис. 1.5 – Универсальное множество
и его дополнение
Очевидно выполнение соотношений X X = , X X = I, из которых следует, что не толькоX является дополнением X, но и X, в свою очередь, есть дополнение X. Но дополнение X есть X. Таким образом,
С помощью операции дополнения можно в удобном виде представить разность множеств. X \ Y = X Y.
Множество упорядоченных пар (x, y), образованных элементами множеств X и Y, называется декартовым, или прямым, произведением множеств X и Y и обозначается X Y. Таким образом, элементами декартова произведения являются двухэлементные строчки вида (x, y).
-177800028194000Геометрической иллюстрацией декартова произведения может служить рис.1.6, на котором множества X и Y изображены отрезками вещественной оси, а произведение X Y заштрихованным прямоугольником. Из рис.1.6 следует, что декартово произведение не обладает переместительным свойством. X Y Y X.
.
Рис. 1.6 – Декартово произведение
множеств
Пример 2. Пусть X = {x1 , x2 , x3 , x4} и Y = {y1 , y2 , y3}. Тогда декартово произведение X Y можно представить табл.1.1.
Таблица 1.1 – Пример декартова произведения
2844804572000 Y X y1 у2 Y3
x1 (x1 , y1) (x1 , y2) (x1 , y3)
x2 (x2 , y1) (x2 , y2) (x2 , y3)
x3 (x3 , y1) (x3 , y2) (x3 , y3)
x4 (x4 , y1) (x4 , y2) (x4 , y3)
Декартовым произведением множеств X1, X2, ... Xn называют множество, обозначаемое X1 X2 ... Xn и состоящее из всех тех и только тех n-строчек, первая компонента которых принадлежит X1, вторая X2 и т.д.
Разбиением множества X называется такое множество множеств {X1, X2, ... Xn}, которое удовлетворяет следующим условиям:
1) Xi X, i = 1, ... , n;
2) Xi , i = 1, ... , n;
3) Xi Xj = , при i j;
4)
Так, например, курсы данного факультета являются разбиением множества студентов факультета, а группы данного курса разбиением множества студентов курса.
Нетрудно показать, что введенные операции над множествами обладают следующими свойствами:
а) X Y = Y X,
X Y = Y X; (коммутативность)
б) (X Y) Z = X (Y Z),
(X Y) Z = X (Y Z); (ассоциативность)
в) X X = X,
X X = X; (идемпотентность)
г) X (Y Z) = (X Y) (X Z),
X (Y Z) = (X Y) (X Z). (дистрибутивность)
1.3 Отношения на множествахДля приложения теории множеств к решению практических задач часто приходится рассматривать множества, между элементами которых определены те или иные отношения. Так, например, во множестве офицеров данного полка для некоторых пар элементов (a, b) справедливо утверждение «Офицер a служит в одной роте с офицером b», для других пар справедливо утверждение «Офицер a старше по званию офицера b», для третьих - утверждение «Офицер a имеет то же звание, что и офицер b». Каждое из этих утверждений задает некоторое отношение между офицерами a и b (совместной службы, старшинства, равенства званий). Примерами отношений могут служить неполные предложения предикаты:
... меньше, чем ..., ... делится на ...,
... включено в ..., ... конгруэнтно ... .
В приведенных примерах речь шла об отношениях между элементами одного и того же множества. Можно говорить и об отношениях (точнее, соответствиях) между элементами различных множеств - например, утверждение «Офицер a служит в роте b» задает соответствие между множеством офицеров и множеством рот.
Для определения понятия соответствия используем представление о множестве упорядоченных пар элементов, троек, n-строчек, т.е. кортежей.
Бинарным соответствием (отношением) называется всякое подмножество множества X Y. В этом случае говорят, что между множествами X и Y установлено бинарное соответствие. Этот факт символически записывается в виде:
x R y , x X , y Y,
где R - символ отношения, указывающий конкретное подмножество множества X Y.
Тернарным соответствием (отношением) называется подмножество множества упорядоченных троек, являющихся элементами декартова произведения X Y Z.
n - арное соответствие (отношение) определяется как подмножество множества n-строчек, являющихся элементами декартова произведения
X1 X2 ... Xn.
Отметим, что в теории графов в основном рассматриваются бинарные соответствия, поэтому ограничимся рассмотрением соответствий только этого типа.
Если множества X и Y в бинарном соответствии совпадают, то говорят об отношении между элементами множества X. Рассмотрим основные свойства отношений.
Отношение R на множестве X называется рефлексивным, если для любого элемента x X справедливо x R x или, иначе, (x, x) R.
Если условие рефлексивности не выполняется ни для одного элемента x X, то отношение R называется антирефлексивным.
Отношение R между элементами множества X называется симметрическим, если для любых элементов x, y X справедливо соотношение
x R y y R x или (x, y) R (y, x) R.
Отношение R между элементами множества X называется антисимметрическим, если для любых элементов x, y X справедливо утверждение (x, y) R (y, x) R. Антисимметрическое отношение является одновременно и антирефлексивным.
Отношение R между элементами множества X называется тождественным, если для любых элементов x, y X справедливо утверждение: x R y и y R x x = y или (x, y) R и (y, x) R x = y. Антисимметрическое отношение является пересечением тождественного и антирефлексивного отношений.
Отношение R между элементами множества X называется транзитивным, если для любых элементов x, y, z X справедливо
x R y, y R z x R z или (x, y) R и (y, z) R (x, z) R.
Примерами транзитивных отношений являются отношения параллельности, равенства, «больше». Отношения перпендикулярности, неравенства представляют собой нетранзитивные отношения.
Отношение R между элементами множества X обладает свойством полноты, если для любой пары (x, y) элементов из X всегда выполняется одно из двух соотношений: x R y или y R x.
Для каждого отношения R можно определить обратное отношение R-1. Краткая запись этого определения выглядит следующим образом:
R R-1, y R-1 x x R y.
Например, для отношения «x является делителем y» обратным является «y кратно x», для отношения «x больше y» обратно «y меньше x».
Нулевым называется отношение, которое не выполняется ни для одной пары элементов множества. Универсальным называется отношение, которое выполняется для любой пары элементов множества.
Дополнительным к R отношением R называется такое отношение, что (x1, x2) R (x1, x2) R.
Рассмотрим теперь основные виды отношений.
Отношение R X X между элементами множества X, обладающее свойствами рефлексивности (x R x x X), симметричности (x1 R x2 x2 R x1 x1, x2 X) и транзитивности (x1 R x2 и x2 R x3 x1 R x3 x1, x2, x3 X), называется отношением эквивалентности и обозначается x1 x2. Примерами отношения эквивалентности являются равенство векторов в евклидовом пространстве, равенство фигур в евклидовой геометрии. Любое отношение эквивалентности, заданное на множестве, разбивает это множество на непересекающиеся подмножества. Так, например, отношение «проживание в одном городе» на множестве жителей страны разбивает это множество на непересекающиеся подмножества, количество которых равно числу городов в стране. Эти подмножества называются классами эквивалентности. Справедливо и обратное утверждение: каждое разбиение множества на непересекающиеся подмножества определяет некоторое отношение эквивалентности.
Отношением квазипорядка на множестве X называется отношение R X X, обладающее свойствами рефлексивности и транзитивности. Например, отношение «x1 x2» на множестве вещественных чисел есть отношение квазипорядка. Поэтому данное отношение часто обозначается символом .
Отношение квазипорядка, обладающее также свойством тождественности, называется отношением порядка. Оно должно, таким образом, удовлетворять аксиомам отношения «x x»: x1 x2 и x2 x3 x1 x3, x1 x2 и x2 x1 x1 = x2.
Отношение, обладающее свойствами транзитивности и антисимметричности, называется отношением строгого порядка. Это отношение часто обозначают символом >. Оно должно удовлетворять следующим аксиомам: x1 > x2 и x2 > x3 x1 > x3, x1 > x2 x2 > x1 – невозможно.
Отношением полного порядка называется отношение порядка, не удовлетворяющее требованию рефлексивности ни на одном из элементов множества. Оно обладает, следовательно, свойствами транзитивности, антисимметричности и полноты.
Наглядное представление о перечисленных типах отношений и их свойствах дает табл. 1.2.
Кроме того, все рассмотренные отношения и их свойства хорошо иллюстрируются на графах, что мы и покажем несколько позднее.
Таблица 1.2. – Виды отношений и их свойства
Отношения
Свойства Эквивалентность Квазипорядок Порядок Строгий порядок Полный порядок Нерефлексивный полный порядок
1.Рефлексивность * * * * 2.Антирефлексив-ность * *
3.Симметричность * 4.Антисимметрич-ность * *
5.Тождественность * * 6.Транзитивность * * * * * *
7.Полнота * *
1.4 Экстремальные элементы множествВ соответствии с отношением порядка говорят, что при x1 x2 элемент x1 предшествует элементу x2 или x2 следует за x1.
Пусть имеется подмножество X X, где X упорядоченное множество, т.е. множество, для элементов которого определено отношение порядка. Тогда мажорантой множества X называется элемент xmax X, следующий за всеми элементами множества X, xmax x (xmax X). При этом мажоранта может и не принадлежать множеству X. Если же xmax X, то xmax называется наибольшим элементом, или максимумом множества X.
Минорантой множества X называется элемент xmin X, предшествующий всем элементам множества X. Если элемент xmin X, то он называется наименьшим элементом, или минимумом множества X.
1.5 Отображения множествПусть X и Y - два непустых множества. Закон G, согласно которому любому элементу x X ставится в соответствие элемент y Y, называется однозначным отображением X в Y, или функцией, определенной на X и принимающей значения на Y.
Используются следующие формы записи:
G: X Y или y = G(x), x X, y Y.
В случае однозначного отображения элемент y = G(x) называется образом элемента x.
Возможна ситуация, когда каждому x X отображение G ставит в соответствие некоторое подмножество G(x) Y. Тогда образом элемента x будет подмножество G(x), а отображение G, будет называться многозначным отображением. Отображение является, таким образом, всюду определенным соответствием, т.е. частным случаем соответствия и определяется тройкой множеств (X, Y, G).
Интересным является случай, когда множества X и Y совпадают. При этом отображение G: X X представляет собой отображение множества X самого в себя и определяется парой (X, G), где G X X. Подробным изучением таких отображений занимается теория графов. Коснемся лишь нескольких операций над ними.
Пусть G и H – отображения множества X в X. Композицией этих отображений назовем отображение GH, которое определяется следующим образом: GH(x) = G(H(x)).
В частном случае при H = G получим отображения G2(x) = G(G(x)), G3(x) = G(G2(x)) и т.д.
Для произвольного S 2: GS(x) = G(GS-1(x)).
Введем для общности рассуждений соотношение G0(x) = x. Тогда можно записать: G0(x) = G(G-1(x)) = GG-1(x) = x.
Это означает, что G-1(x) представляет собой обратное отображение. Тогда G-2(x) = G-1(G-1(x)) и т.д.
Пусть, например, X - множество людей. Для каждого человека x X обозначим через G(x) множество его детей. Тогда G2(x) - множество внуков x, G3(x) - множество правнуков x, G-1(x) - множество родителей x и т.д. Изображая людей точками и рисуя стрелки, идущие из x в G(x), получим родословное, или генеалогическое дерево (рис. 1.7.)

Рис. 1.7 – Генеалогическое дерево
1.6 Задачи и упражненияДаны множества X = {1, 2, 3, 4, 5}, Y = {2, 4, 6, 7}, найдите X Y, X Y, X \ Y, Y \ X.
Пусть X множество отличников в группе, Y множество студентов группы, проживающих в общежитии. Найдите множества: X Y, X Y, X \ Y, Y \ X.
Что представляет собой пересечение множества всех прямоугольников с множеством всех ромбов?
Пусть I = {x1, x2, x3} универсальное множество, а X = {x1, x2}, Y = {x2, x3}, Z = {x3} его подмножества. Определите перечислением множества: X X, Z Z, X Y, Y X, X Y Y X, X Y Y X.
Проиллюстрируйте графически тождества
X (Y Z) = (X Y) (X Z),
X (Y Z) = (X Y) (X Z).
Пусть R множество вещественных чисел, X = {x R / 0 x 1}, Y = {y R / 0 y 2}. Что представляют собой множества X Y, X Y, X \ Y?
Начертите фигуры, изображающие множества A = {(x, y) R2 / x2 + y2 1}, B = {(x, y) R2 / x2 + (y-1)2 1}, где R2 вещественная плоскость. Какие фигуры изображают множества A B, A B, R2 \ A?
Пусть X, Y, Z подмножества множества R2, равные: X = {(x, y) R2 / x 0}, Y = {(x, y) R2 / y 0}, Z = {(x, y) R2 / x + y 1}. Представьте геометрически множества
Пусть X = {-1, -2, -3, 1, 2, 3, 0} и Y множество всех натуральных чисел. Каждому числу x X ставится в соответствие его квадрат. Выпишите все пары, принадлежащие этому соответствию.
Пусть X = {«атом», «стол», «море», «мера»}, Y = {а, м, о, р, е}. Составьте декартово произведение X Y. Отметьте в нем пары, связанные соответствием «в слово x входит буква y».
Пусть V множество положительных целых чисел от 1 до 20, на котором задано отношение R: «число x делится на число y», причем x V, y V. Выпишите все пары из V, находящиеся в отношении R.
Дано множество B = {1, 3, 5, 7, 9}. Элементы этого множества связаны отношением S: «число x на 2 больше числа y». Запишите множество пар, принадлежащих этому отношению.
Определите свойства следующих отношений:
а) «прямая x пересекает прямую y» (на множестве прямых);
б) «число x больше числа y на 2» (на множестве натуральных чисел);
в) «число x делится на число y без остатка» (на множестве натуральных чисел);
г) «x сестра y» (на множестве людей).
На множестве X = {x / x N, x < 12} задано отношение R: «x и y имеют один и тот же остаток при делении на 5» (x X, y X). Покажите, что R отношение эквивалентности. Запишите все классы эквивалентности, на которые разбивается множество данным отношением.
Рассмотрите на множестве людей следующие отношения, укажите среди них отношения эквивалентности:
а) «x похож на y»;
б) «x и y живут в одном доме»;
в) «x и y друзья»;
г) «x живет этажом выше, чем y».
Отношение S на множестве X = {1, 2, 3} состоит из пар: (1, 2), (1, 1), (2, 2), (2, 1), (3, 1), (3, 3). Является ли S отношением эквивалентности на множестве X?
Какие из нижеперечисленных отношений являются отношениями квазипорядка, порядка, строгого порядка?
а) «отрезок x длиннее отрезка y»;
б) «отрезок x короче отрезка y в 2 раза» на множестве отрезков;
в) «x старше по возрасту, чем y»;
г) «x является сестрой y»;
д) «x живет в одном доме с y»;
е) «x друг y» на множестве людей;
ж) «число x не меньше числа y» на множестве R;
з) «окружность x лежит внутри окружности y» на множестве окружностей плоскости.
Докажите тождества: A (B \ A) = , A \ (B C) = (A \ B) \ C.
Решите систему уравнений
7416804826000 A \ X = B,
A X = C,
где A, B, C - заданные множества и B A C.
Докажите, что A = B (A \ B) (B \ A) = .
Докажите, что если отношения R1 и R2 рефлексивны, то рефлексивны и отношения R1 R2, R1 R2.
Докажите, что если отношения R1 и R2 симметричны, то симметричны и отношения R1 R2, R1 R2.
Докажите, что два множества равны тогда и только тогда, когда результаты их пересечения и объединения совпадают.
Известно, что из 100 студентов живописью увлекается 28, спортом 42, музыкой 30, живописью и спортом 10, живописью и музыкой 8, спортом и музыкой 5, живописью, спортом и музыкой 3. Определите количество студентов:
а) увлекающихся только спортом;
б) ничем не увлекающихся.
2 ОСНОВЫ ТЕОРИИ ГРАФОВНа практике часто бывает полезно изобразить некоторую ситуацию в виде рисунков, составленных из точек (вершин), представляющих основ-ные ситуации, и линий (ребер), соединяющих определенные пары этих вершин и представляющих связи между ними. Таким способом удобно представлять структуру системы (вершины – блоки, ребра – связи между блоками). Удобны графы при исследовании систем методом пространства состояний. В этом случае вершины – состояния системы, процесса, ребра – действия, которые могут изменить состояние. При решении оптимиза-ционных задач вершинами могут быть предполагаемые решения, ребрами – правила для их нахождения.
Такие рисунки известны под общим названием графов. Графы встре-чаются в разных областях под разными названиями: “структуры” в гражд-анском строительстве, “сети” в электротехнике, “социограммы” в социо-логии и экономике, “молекулярные структуры” в химии, и т. д.
Начало теории графов как математической дисциплины было поло-жено Эйлером в знаменитом рассуждении о Кенигсбергских мостах. Од-нако эта статья, написанная в1736 г, была единственной в течение почти ста лет. Интерес к этой науке возродился около середины ХIХ в. в связи с развитием естественных наук (исследования электрических сетей, моделей кристаллов и структур молекул), формальной логики (бинарные отноше-ния можно изучать в форме графов). Кроме того, оказалось, что многие математические головоломки могут быть сформулированы в тер-минах теории графов. Это приводило к пониманию того, что многие зада-чи такого рода содержат некоторое математическое ядро, важность кото-рого выходит за рамки конкретного вопроса. Наиболее знаменитая из них – проблема четырех красок (сформулирована Де Морганом в 1850г.).
Последние 35 – 40 лет ознаменовали новый период интенсивных разработок в теории графов. Появились новые области приложения: теория игр и программирование, теория передачи сообщения, электрических сетей и контактных цепей, биология, психология.
2.1 Основные определения2.1.1 Общие понятияГраф G задается множеством точек (вершин) X={x1,..xn} и множеством линий (ребер) A={a1,..,a m}, соединяющих между собой все или часть этих точек. Таким образом, граф G полностью задается парой (X,A).
Другое, чаще употребляемое описание графа, состоит в задании множества вершин X и соответствия G, которое показывает, как между собой связаны вершины. То есть граф задается следующим образом.
2296160744220x6
x2
x3
x4
x1
x0
x5
Рис. 2.1 – Пример задания графа
00x6
x2
x3
x4
x1
x0
x5
Рис. 2.1 – Пример задания графа
Пусть дано множество X, состоящее из элементов (назовем их вершинами графа) и закон G, позволяющий установить соответствие между каждым элементом x множества X и некоторыми его подмножествами G(x) тогда граф полностью определяется множеством X и соответствием G, то есть граф обозначается парой (X,G). Удобно использовать обозначение G(x) по аналогии с функцией.
Пример (рис.2.1). Множество вершин X = {x0, x1, x2, x3, x4, x5} и соответствия между вершинами
G(x0) = {x1, x2},
G(x2) = {x0, x1, x5},
G(x3) = {x4},
G(x4) = {x1, x3},
G(x5) = {x2},
G(x6) = .
Ребра графа – линии, соединяющие вершины, указывают на соответствие между вершинами в графе.
Запись g(xi, xj) говорит, что ребро g инцидентно вершинам xi, xj и вершины xi, xj инцидентны ребру g. Две вершины xi, xj называются смежными, если они определяют ребро графа. Два ребра графа называются смежными, если их концы имеют общую вершину.
Вершина, не инцидентная никакому ребру графа, называется изолированной. Если граф состоит из изолированных вершин, его называют ноль-графом.
2.1.2 Ориентированные и неориентированные графы10160675640xj
xi
Рис. 2.2 – Дуга ориентированного графа
00xj
xi
Рис. 2.2 – Дуга ориентированного графа
Ребро графа называется неориентированным, если порядок расположения его концов (направление стрелок) в графе не принимается во внимание. Ребро графа называется ориентированным, если этот порядок существенен.
В этом случае говорят, что для ребра g(xi, xj) xi – начальная, а xj – конечная вершины ребра. Ориентированное ребро называют также дугой графа (рис.2.2).
Граф называется неориентированным, если каждое ребро его не ориентированно, и ориентированным, если каждое ребро его ориентированно. Если граф содержит как ориентированные, так и неориентированные ребра, он называется смешанным.
Для каждого графа G(x) существует обратный граф.G-1(x), полученный изменением ориентации каждого из ребер графа G(x) на противоположную.
Полным неориентированным графом называется граф U(x), ребрами которого являются всевозможные пары g(xi, xj,) для двух возможных xi, xj X, ij (рис.2.3).
1079557150x3
x2
x1
x4
Рис. 2.3 – Полный неориентированный и полный ориентированный графы
x3
x1
x2
00x3
x2
x1
x4
Рис. 2.3 – Полный неориентированный и полный ориентированный графы
x3
x1
x2
Полным ориентированным графом U0(x) называется граф, у которого любые две вершины соединены хотя бы в одном направлении.
1079565405g(xi, xi)
xi
Рис. 2.4 - Петля
00g(xi, xi)
xi
Рис. 2.4 - Петля
Петлей называется ребро g(xi , xi), у которого начальная и конечная вершины совпадают (рис.2.4) Петля обычно считается неориентированной.
Мультиграфом называется граф, в котором пара вершин соединяется несколькими различными ребрами или дугами (рис.2.5).
10795100965xj
xi
xj
xi
Рис. 2.5 – Неориентированный и ориентированный мультиграфы
00xj
xi
xj
xi
Рис. 2.5 – Неориентированный и ориентированный мультиграфы
Дополнением графа G(x) является такой граф Gk(x), ребра которого совместно с графом G(x) образуют полный U(x) граф.
2.1.3 Цепи, циклы, пути и контуры графовДля неориентированных графов справедливы следующие понятия.
Цепь – конечная или бесконечная последовательность ребер
S = (…,g1, g2,…), в которой у каждого ребра gk одна из вершин является вершиной ребра gk-1, а другая – вершиной ребра gk+1. При этом одно и то же ребро или вершина может встречаться несколько раз (рис.2.6):
10160104140g6
g2
g5
g3
g1
g4
g0
x4
x3
x1
x2
x5
x0
Рис. 2.6 – Пример цепи
00g6
g2
g5
g3
g1
g4
g0
x4
x3
x1
x2
x5
x0
Рис. 2.6 – Пример цепи
{g0, g1, g2, g3, g4, g5, g2, g6} = {(x0, x1), (x1, x2), (x2, x3), (x3, x1), (x1, x4), (x4, x3), (x3, x2), (x2, x5)}.
Цепь называется простой, если все ребра в ней различны, и составной или сложной – в противном случае. Величины (вершины)в простой цепи могут повторяться. Цепь называется элементарной, если в ней ни одна из вершин не повторяется.
Циклом называется конечная цепь, начинающаяся на некоторой вершине xi и оканчивающаяся на той же вершине.
Простые, составные или сложные, элементарные циклы – по аналогии с цепями.
Для ориентированных графов введены следующие дополнительные понятия.
Путем в графе G(x) называется такая последовательность дуг
(g1, g2 ,…), что конец каждой предыдущей дуги является началом следующей. Существуют простые, составные (сложные), элементарные пути.
Контур графа – это конечный путь, у которого начальная вершина совпадает с конечной. Существуют простые, составные (сложные), элементарные контуры.
Длина пути есть число дуг L(s) в последовательности дуг пути s. В случае бесконечного пути L(s) = .
1016071120xj
xi
Рис. 2.7 – Симметрический граф
00xj
xi
Рис. 2.7 – Симметрический граф
Граф называется симметрическим, если xi, xj из того, что xi G(xj) xj G(xi), то есть две смежные вершины xi, xj всегда соединены противоположно ориентированными дугами (рис.2.7).
Граф называется антисимметрическим, если xi, xj; xi G(xj) xj G(xi), то есть каждая пара смежных вершин соединена только в одном направлении.
2.1.4 Конечный и бесконечный графыГраф называется конечным, если число его вершин конечно.Граф G(X) называется G – конечным, если для каждой его вершины
x X множество G(x) конечно, и бесконечным, если число вершин бесконечно. Если обозначить |X| число элементов множества X, то
граф G(X) конечен, если |X| ,
граф G(X) G – конечен, если |G(x)| x X,
граф G(X) G-1- конечен, если |G-1(x)| x X.
Граф G(X) называется локально конечным, если он одновременно G - и G-1 - конечен. Очевидно, что всякий конечный граф локально конечен.
2.1.5 Частичные графы, подграфы, частичные подграфы284480467360x2
x3
x1
x4
x0
x2
x3
x1
x4
x0
Рис. 2.8 – Граф G(X) и частичный для него граф H(X)
00x2
x3
x1
x4
x0
x2
x3
x1
x4
x0
Рис. 2.8 – Граф G(X) и частичный для него граф H(X)
Граф H(x) называется частичным для графа G(X), если все ребра H(X) являются ребрами G(X) и множество вершин графа H(X) совпадает с множеством вершин графа G(X), то есть H(x) G(x) x X (рис.2.8).
Частичный граф содержит часть ребер (дуг). Он также может быть ориентированным или неориентированным в зависимости от исходного.
Отметим, что ноль-граф графа G(X) считается частичным графом каждого графа. Все частичные графы H(X) для G(X) можно получить, выбирая в качестве ребер H(X) всевозможные подмножества множества ребер графа G(X).
-81280477520x2
x3
x1
x0
Рис. 2.9 – Подграф GA(A) графа G(X)
00x2
x3
x1
x0
Рис. 2.9 – Подграф GA(A) графа G(X)
Подграфом GA(A) графа G(X), где A X, называется граф, вершинами которого являются элементы множества A X, а ребрами – все ребра из G, оба конца которых лежат в A (рис.2.9).
Таким образом, подграф содержит часть вершин вместе с ребрами, соединяющими эти вершины. Иначе, GA(A) – подграф графа G(X), если A X и GA(x) = G(x) A. Если A = X, то GA(A) = G(X). Для единственной вершины A={a} подграф GA(a) состоит из петель в а. Подграфом GA(A) графа G(X) будет ноль-граф, если A X есть подмножество изолированных вершин графа G(X). Подграф будет ориентированным или неориентированным в зависимости от графа.
Частичным подграфом HA(A), A X графа G(X) называется подграф (рис.2.10), ребрами которого являются некоторые ребра из G(X), оба конца которых лежат в A. Иначе, HA(A) – частичный подграф графа G(X), если A X и HA(x) G(x) A xX.
-81280500380x2
x3
x1
x0
Рис. 2.10 – Частичный подграф HA(A) графа G(X)
x2
x3
x4
x0
Рис. 2.11 – Дополнительный частичный граф H(A) графа G(X)
00x2
x3
x1
x0
Рис. 2.10 – Частичный подграф HA(A) графа G(X)
x2
x3
x4
x0
Рис. 2.11 – Дополнительный частичный граф H(A) графа G(X)
Дополнительным частичным графом H(A) графа G(X) является единственный граф, состоящий из ребер графа G(X), не принадлежащих некоторому частичному подграфу HA(A) графа G(X) (рис.2.11).
Звездным графом, определяемым вершиной х, называется граф, состоящий из всех ребер G(X), имеющих х концевой вершиной. Петли в х могут как включаться, так и не включаться в звездный граф.
2.1.6 Связность в графахРассмотрим вопрос о связности в графах. Пусть G(X) – неориентированный граф. Две вершины хi, хj называется связными, если существует цепь S с концами хi и хj. Если S проходит через некоторую вершину xk более одного раза, то можно удалить цикл в вершине xk из цепи S. Отсюда следует, что вершины, связанные цепью, связаны элементарной цепью.
Неориентированный граф называется связным, если любая пара его вершин связана. Отношение связности для вершин графа есть отношение эквивалентности (xi xj, xj xk, xi xk).
1016071755x4
x5
x3
x1
x2
Рис. 2.12 – Граф с двумя компонентами связности
00x4
x5
x3
x1
x2
Рис. 2.12 – Граф с двумя компонентами связности
Компонентой связности неориентированного графа G(X) называется подграф HA(A) графа G(X) с множеством вершин A X и множеством ребер в G(X), инцидентных только вершинам из A, причем ни одна вершина из xi A не смежна с вершинами из множества X \ A (рис.2.12).
Ориентированный граф называется сильно связным, если для любой пары вершин найдется путь, соединяющий их.
Компонентой сильной связности ориентированного графа G(X) называется подграф HA(A) графа G(X) (подчиняющийся определению сильно связного графа) с множеством вершин AX и множеством дуг, имеющих начало и конец в A, причем ни одна из вершин xi A и xj X \ A не смежны между собой (рис.2.13).
-8128071120x1
x6
x7
x5
x4
x3
x2
Рис. 2.13 – Ориентированный граф с двумя компонентами сильной связности
00x1
x6
x7
x5
x4
x3
x2
Рис. 2.13 – Ориентированный граф с двумя компонентами сильной связности
Очевидно, что ориентированный граф G(X) сильно связан тогда и только тогда, когда он имеет одну компоненту связности.
На практике широко используются такие виды графов, как деревья и прадеревья.
-172720464820x4
x3
x9
x7
x8
x2
x6
x5
x0
x1
Рис. 2.14 – Дерево
00x4
x3
x9
x7
x8
x2
x6
x5
x0
x1
Рис. 2.14 – Дерево
Деревом называется конечный связный неориентированный граф, состоящий по крайней мере из двух вершин и не содержащий циклов. Такой граф не имеет петель и кратных ребер (рис.2.14).
Ветвями дерева называются ребра графа, входящие в дерево. Хордами дерева называются ребра, входящие в граф, дополнительный к данному дереву.
Лагранжевым деревом называется дерево, все ветви которого имеют общую вершину.
Лесом называется несвязный граф, каждая компонента связности которого является деревом.
284480647700Рис. 2.15 – Прадерево
00Рис. 2.15 – Прадерево
Прадеревом называется ориентированный граф G(X) с корнем x1  X, если в каждую вершину xi x1 (xi X) заходит ровно одна дуга, в вершину x1 не заходит ни одна дуга, граф G(x) не содержит контуров (рис.2.15).
2.1.7 Изоморфизм. Плоские графы101600632460x3
x2
x1
x3
x1
x2
G1(X1)
G2(X2)
00x3
x2
x1
x3
x1
x2
G1(X1)
G2(X2)
В изображении графа имеется относительно большая свобода в размещении вершин и в выборе формы соединяющих их ребер. Поэтому один и тот же граф может быть представлен (на плоскости) по-разному (рис. 2.16).
193040-25400x4
x5
x1
x2
x3
x5
x3
x1
x4
x2
G1(X1)
G2(X2)
Рис. 2.16 – Примеры изоморфных графов
00x4
x5
x1
x2
x3
x5
x3
x1
x4
x2
G1(X1)
G2(X2)
Рис. 2.16 – Примеры изоморфных графов
Графы G1(X1), G2(X2) называются изоморфными, если между множествами их вершин существует взаимно однозначное соответствие, такое, что вершины соединены ребрами в одном из графов в том и только том случае, когда соответствующие им вершины соединены в другом графе. Если ребра графов ориентированы, то их направление в изоморфных графах также должно соответствовать друг другу.
-81280471805Рис. 2.17 – Примеры плоского (а) и неплоского (б) графов
x2
x4
x1
x2
x3
x4
x1
x2
x3
x1
x3
x6
x5
x4
а)
б)
00Рис. 2.17 – Примеры плоского (а) и неплоского (б) графов
x2
x4
x1
x2
x3
x4
x1
x2
x3
x1
x3
x6
x5
x4
а)
б)
Граф G(X) называется плоским, если он может быть изображен на плоскости так, что все пересечения его ребер являются вершинами графа G(X) (рис.2.17).
2.2 Отношения на множествах и графыКаждый ориентированный граф G(X) определяет некоторое отношение на множестве X своих вершин. Это отношение может быть записано как xiG xj. Оно означает, что в графе есть дуга, идущая от xi к xj .
Отношению со свойством рефлексивности (x R x) должна соответствовать на графе петля в вершине. Если это отношение соблюдается во всех вершинах x X, то соответствующий граф G(X) должен иметь петлю в каждой своей вершине. В случае антирефлексивного отношения на множестве X, соответствующий граф ни в одной из вершин не имеет петли.
Симметрическому отношению на множестве X соответствует граф с неориентированными ребрами и наоборот граф с неориентированными ребрами определяет некоторое симметрическое отношение. В случае антисимметрического отношения на графе невозможно присутствие двух дуг (xi, xj), (xj, xi) на графе, то есть существование неориентированного ребра. Кроме того, на этих графах нет петель, то есть соответствующее антисимметрическое отношение антирефлексивно.
Отношение, обладающее свойством тождественности, соответствует графу с антисимметричным отношением на множестве вершин (ориентированному графу) и добавлением петли в каждой вершине. Этот граф не должен иметь контуров.
1016022860xk
xi
xj
Рис. 2.18 – Свойство транзитивности на графе
00xk
xi
xj
Рис. 2.18 – Свойство транзитивности на графе
Граф, соответствующий транзитивному отношению (рис.2.18), обладает следующими свойствами: для любой пары ориентированных ребер (дуг) графа (xi, xj),(xj, xk) имеется замыкающая дуга (xi, xk). Можно сказать, что в графе, который соответствует транзитивному отношению, для каждого пути S(xi, xk) имеется дуга (xi, xk) (рис.2.19).
-1668780153670x1
x2
x3
x4
x1
x2
x3
x4
Рис. 2.19 – Примеры транзитивного (а) и нетранзитивного (б) графов
а)
б)
00x1
x2
x3
x4
x1
x2
x3
x4
Рис. 2.19 – Примеры транзитивного (а) и нетранзитивного (б) графов
а)
б)

Отношение, обладающее свойством полноты, определено на множестве вершин полного ориентированного графа.
Нулевое отношение определено на множестве вершин ноль-графа.
Универсальное отношение определено на множестве вершин полного неориентированного графа с петлями.
Дополнительное к R отношениеR определено на множестве вершин дополнительного Gk(X)графа к графу G(X).
284480797560x4
x1
x2
x3
x10
x5
x7
x6
x8
x9
Рис. 2.20 – Граф, соответствующий отношению эквивалентности
00x4
x1
x2
x3
x10
x5
x7
x6
x8
x9
Рис. 2.20 – Граф, соответствующий отношению эквивалентности
Графы, соответствующие отношению эквивалентности, представляют собой совокупность компонент связности (для каждого класса эквивалентности своя компонента) несвязного графа. Каждая компонента несвязного графа должна быть полным неориентированным графом с петлями (рис. 2.20).
-1727202148840x2
x1
x3
x5
x4
x2
x1
x3
x5
x4
x8
x9
x3
x5
x4
Рис. 2.21 – Примеры графов, на которых определено отношение квазипорядка
а)
б)
в)
00x2
x1
x3
x5
x4
x2
x1
x3
x5
x4
x8
x9
x3
x5
x4
Рис. 2.21 – Примеры графов, на которых определено отношение квазипорядка
а)
б)
в)
При рассмотрении отношения квазипорядка соответствующий граф должен иметь петли в каждой вершине и может иметь неориентированные и ориентированные ребра. В отличие от предыдущего случая здесь не соблюдается свойство симметричности (рис. 2.21, а, б, в).
Граф, на множестве вершин которого определено отношение эквивалентности, одновременно является графом, на множестве вершин которого определено отношение квазипорядка.
Граф, на множестве вершин которого определено отношение порядка, является также графом, на множестве вершин которого определено отношение квазипорядка. Этот граф:
имеет петли во всех вершинах;
для каждого пути S(xi, xk) должен иметь замыкающую дугу (xi, xk);
не должен иметь контуров и все ребра должны быть ориентированы (рис. 2.21, в).
Граф, на множестве вершин которого определено отношение строгого порядка, получается удалением всех петель в графе, на множестве вершин которого определено отношение порядка.
Отношение полного порядка соответствует каждой компоненте связности графа, на множестве вершин которого определено отношение порядка.
Если на графе G(X) определено одно из отношений эквивалентности, квазипорядка, порядка, строгого порядка, полного порядка, нулевое, универсальное, дополнительное, то данное отношение сохраняется и на графе G-1(X).
2.3 Матрицы смежности и инциденций графаЕсли в графе G(X) через aij обозначить число дуг, идущих из xi в xj, то матрица || aij || с n строками и n столбцами называется матрицей смежности вершин графа. Здесь aij – элемент, стоящий на пересечении i-й строки и j-го столбца, ai – i-я вектор-строка, aj – j-й вектор-столбец.
-8128028575x1
x3
x2
x4
x5
Рис. 2.22 – Пример графа для определения матрицы смежности A
00x1
x3
x2
x4
x5
Рис. 2.22 – Пример графа для определения матрицы смежности A
x1 x2 x3 x4 x5
6172201778000 x1 0 1 0 0 1
x2 0 0 0 0 1
А = x3 0 1 0 1 0
x4 0 0 0 0 1
x5 0 0 0 0 1
Наличие нулевого элемента на главной диагонали означает отсутствие петли в соответствующей вершине.
Матрица AT соответствует графу G-1(X).Матрица А является симметрической тогда и только тогда, когда граф G(X) – симметрический. Матрица А антисимметрична тогда и только тогда, когда граф G(X) – антисимметрический. Матрица А полна тогда и только тогда, когда граф G(X) – полный (aij + aji 1).
Матрицей смежности ребер графа называется такая матрица
В = || bij || (i = 1, …, m; j = 1, …, m, где m – число ребер графа), что
55880022860001, если ребра gi и gj имеют общий конец,
bij =
0 в противном случае.
Пусть g1 ,…, gm – дуги, а x1 ,…, xn – вершины ориентированного графа G(X). Матрица S = || sij || (i = 1, …, n – номер вершины графа, j = 1, …, m – номер дуги графа), такая что
558800737870005588006985001, если gj исходит из xi,
sij = -1, если gj заходит в xi,
0, если gj не инцидентна xi
называется матрицей инциденций для дуг графа.
Матрица R = || rij || размером n m, где
1, если xi (i = 1, …, n) инцидентна gj (j = 1, …, m),
rij =
0 в противном случае
284480170180g2
g3
g1
g4
g5
g6
x1
x5
x4
x2
x3
x6
Рис. 2.23 – Пример графа для определения матриц инциденций S и R
00g2
g3
g1
g4
g5
g6
x1
x5
x4
x2
x3
x6
Рис. 2.23 – Пример графа для определения матриц инциденций S и R
называется матрицей инциденций для ребер графа (рис. 2.23).
375920138938000 0 1 0 1 0 0 0 1 0 1 0 0 1 0 1 0 0 0 1 0 1 0 0 0 S = -1 -1 0 0 0 0 , R = 1 1 0 0 0 0 .
0 0 -1 -1 1 1 0 0 1 1 1 1 0 0 0 0 -1 0 0 0 0 0 1 0 0 0 0 0 0 -1 0 0 0 0 0 1 2.4 Операции над графами
Сумма графов
Пусть даны два графа G1(X) и G2(X) на одном и том же множестве вершин. Тогда суммой G(X), графовG1(X) и G2(X) является граф, состоящий из ребер, принадлежащих G1(X), либо G2(X). Таким образом, если
(xi', xj') G1(X)и (xi'', xj'') G2(X), то (xi', xj') G(X) и (xi'', xj'') G(X)
(xi', xj', xi'', xj'') X.
Символически сумму двух графов обозначают следующим образом:
G(X) = G1(X) G2(X). Аналогично определяется сумма n графов Gi(X)
(i =1, …, n): n
G(X) = Gi(X)
i =1
-172085830580Рис. 2.24 – Примеры операции суммирования графов
G(X)=G1(X)G2(X)
x3
x5
x2
x1
x3
x4
x5
x2
x1
x3
x4
x5
x2
x1
x3
x4
1)
G1(X)
G2(X)
G(X)=G1(X)G2(X)
x1
x2
x5
x4
x3
x1
x2
x5
x4
x3
x1
x2
x5
x4
x2
x1
x3
x4
x5
x2
x1
x3
x4
а)
G1(X)
G2(X)
G(X)=G1(X)G2(X)
б)
G1(X)
G2(X)
00Рис. 2.24 – Примеры операции суммирования графов
G(X)=G1(X)G2(X)
x3
x5
x2
x1
x3
x4
x5
x2
x1
x3
x4
x5
x2
x1
x3
x4
1)
G1(X)
G2(X)
G(X)=G1(X)G2(X)
x1
x2
x5
x4
x3
x1
x2
x5
x4
x3
x1
x2
x5
x4
x2
x1
x3
x4
x5
x2
x1
x3
x4
а)
G1(X)
G2(X)
G(X)=G1(X)G2(X)
б)
G1(X)
G2(X)
как граф, состоящий из ребер, принадлежащих хотя бы одному из графов Gi(X) (рис. 2.24, а, б).
Операция суммирования графов обладает переместительным свойством, то есть G1(X) G2(X) = G2(X) G1(X).
Пример 1.
Рассмотрим случай, когда операция суммы графов применяется к графам, определенным на различных множествах вершин. Тогда суммой G(X) будет графn
G(X) = G1(X1) G2(X2) … Gn(Xn) = Gi(Xi),
i=1
для которого справедливо: Х = Х1 Х2 … Хn и
n
G(xj) = G1(xj) G2(xj) … Gn(xj) = Gi(xj), xj X (рис. 2.25).
193040307340x1
G2(X2)
G1(X1)
x2
x3
x1
x2
x1
x2
x3
Рис. 2.25 – Суммирование графов с различными множествами вершин
G1(X1)G2(X2)
00x1
G2(X2)
G1(X1)
x2
x3
x1
x2
x1
x2
x3
Рис. 2.25 – Суммирование графов с различными множествами вершин
G1(X1)G2(X2)
i=1
Пример 2.
Пересечение графов
Пусть даны два графа G1(X) и G2(X) на одном и том же множестве вершин. Тогда пересечением графов G1(X) и G2(X) называется граф G(X), состоящий из ребер, принадлежащих и G1(X) и G2(X), то есть если
(xi, xj) G1(X) и (xi, xj) G2(X), то (xi, xj) G(X).
Обозначение пересечения двух графов: G(X) = G1(X) G2(X).
Аналогично пересечение n графов Gi(X) (i = 1, …, n) обозначается как
n
Gi(X) = Gi(X) и определяет граф G(X), состоящий из ребер, принадле-
i=1
жащих одновременно всем графам Gi(X).
Для графов, используемых в примере 1 (рис. 2.24), имеем:
а) G1(X) G2(X) = (ноль - граф);
б) пересечение графов G1(X) и G2(X) изображено на рис. 2.26.
Для графов, определенных на различных множествах вершин операция пересечения определяется следующим образом:
n
G(X) = G1(X1) G2(X2) … Gn(Xn) = Gi(Xi),
n i=1
где Х = Х1 Х2 … Хn = Xi
i=1 n
и G(xj) = G1(xj) G2(xj) … Gn(xj) = Gi(xj),
xj X.i=1
193040154940x1
x2
x5
x4
x3
Рис. 2.26 – Пересечение графов примера 1, б
x1
x2
Рис. 2.27 – Пересечение графов примера 2
00x1
x2
x5
x4
x3
Рис. 2.26 – Пересечение графов примера 1, б
x1
x2
Рис. 2.27 – Пересечение графов примера 2
Пересечение графов G1(X1) и G2(X2) примера 2 изображено на рис. 2.27.
Композиция графов
Композицией (произведением) двух графов G1(X) и G2(X) с одним и тем же множеством вершин Х является граф, у которого множество вершин, смежных с вершиной xi, состоит из всех вершин, достижимых из xi цепью длины два, первое ребро которой принадлежит G2(X), а второе – G1(X) (рис. 2.28). Здесь (xi, xj) G2(X), (xj, xk) G1(X), (xi, xk) G1(G2(X)).
-812801620520x4
x5
x1
x2
x4
x3
x1
x2
x5
x3
G1(X)
G2(X)
Рис. 2.29 – Пример композиции графов
x3
G1(G2(X))
x3
x1
x2
x5
x4
00x4
x5
x1
x2
x4
x3
x1
x2
x5
x3
G1(X)
G2(X)
Рис. 2.29 – Пример композиции графов
x3
G1(G2(X))
x3
x1
x2
x5
x4
1016066040xi
xj
xj
xk
xi
xk
Рис. 2.28 – Иллюстрация операции композиции
00xi
xj
xj
xk
xi
xk
Рис. 2.28 – Иллюстрация операции композиции
Композиция графов обозначается как G(X) = G1(G2(X)) (на рис. 2.29 изображен пример композиции).
Пример 3.
Композицию графов, изображенных на рис. 2.29, иллюстрирует табл.2.1.
Таблица 2.1 – Соответствие между вершинами графов (рис. 2.29)
10160508000 Соответст-
вие
Вер-
шина (xi, xj) G1(X) (xi, xj) G2(X) (xi, xj) G1(G2(X)) (xi, xj) G2(G1(X))
x1 (x1, x4) (x1, x5)
x2 (x2, x5) (x2,x3)
x3 (x3, x2) (x3, x4) (x3, x3)
x4 (x4, x3) (x4,x4)
x5 (x5, x3) (x5, x2)
-812807620x3
G2(G1(X))
x3
x1
x2
x5
x4
Рис.2.30 – Композиция G2(G1(X))
00x3
G2(G1(X))
x3
x1
x2
x5
x4
Рис.2.30 – Композиция G2(G1(X))
На основе таблицы можно построить G1(G2(X)) и G2(G1(X))
(рис. 2.30).
Транзитивное замыкание
графов
Пусть имеется нетранзитивный ориентированный граф G(X). Его можно сделать транзитивным, добавляя дуги с целью получения замыкающей дуги (xi, xk) для каждой пары его последовательных дуг (xi, xj) и (xj, xk). В этом случае говорят, что транзитивный граф Gтр(X) получен из нетранзитивного G(X) при помощи транзитивного замыкания графа (аналогично транзитивному замыканию отображений)
Gтр(X) = {x} G(x) G2(x) G3(x), …, xX.
-81280158115x1
x2
x3
а)
x1
x2
x3
x4
G(X)
x1
x2
x3
x4
Gтр(X)
G(X)
x1
x2
x3
Gтр(X)
б)
Рис. 2.31 – Примеры транзитивного замыкания графов
00x1
x2
x3
а)
x1
x2
x3
x4
G(X)
x1
x2
x3
x4
Gтр(X)
G(X)
x1
x2
x3
Gтр(X)
б)
Рис. 2.31 – Примеры транзитивного замыкания графов
Пример 4.
Декартово произведение
Декартовым произведением двух графов G1(X1) и G2(X2) называется граф G(X) = G1(X1) G2(X2), определенный следующим образом:
а) множество вершин Х является декартовым произведением множеств Х1 и Х2: Х = Х1 Х2 = {(xi1, xj2) / xi1 X1, xj2X2};
б) множество вершин, смежных с вершиной (хi1, хj2) декартова произведения двух графов, определяется как G(xi1, xj2) = G1(xi1) G2(xj2), т.е. как декартово произведение множеств вершин графа G1(X1), смежных с хi1 и графа G2(X2), смежных с xj2. Пример приведен на рис. 2.32.
-81280223520G1(X1) x1
G2(X2) x1
G1(X1) G2(X2)
(x01, x02)
(x01, x12)
(x11, x02)
(x11, x12)
(x21, x02)
(x21, x12)
x11
x01
x21
x02
x12
Рис. 2.32 – Декартово произведение графов
00G1(X1) x1
G2(X2) x1
G1(X1) G2(X2)
(x01, x02)
(x01, x12)
(x11, x02)
(x11, x12)
(x21, x02)
(x21, x12)
x11
x01
x21
x02
x12
Рис. 2.32 – Декартово произведение графов
Пример 5.
Для примера 5G(x01,x02)={(x11,x12), (x21,x12)},
G1(x01)={x11, x21},G(x01, x12)={(x11, x02), (x21, x02)},
G1(x11)= x01, G2(x02)=x12,G(x11, x02)=(x01, x12),
G1(x21)= x01, G2(x12)=x02,G(x11, x12)=(x01, x02),
G(x21, x02)=(x01, x12),
G(x21, x12)=(x01, x02).
Пусть даны n графов G1(x1), G2 (x2), ..., Gn (xn). Тогда граф
G(x)= G1(x1) G2(x2) ... Gn(xn) называется декартовым произве-
дением указанных графов, если
а) x = x1 x2 ... xn = {( x1 , x2 , ..., xn) / x1 X1, x2 X2, ... , xn Xn};
б) G(x1 , x2 , ... , xn) = G1(x1) G2(x2) ... Gn(xn) – декартово произведение подмножеств вершин графов Gi(xi) (i = 1, ..., n), смежных с вершинами x1, x2, ... , xn.
Декартова сумма графов
Декартовой суммой графов G1(x1) и G2(x2) G(x) = G1(x1) + G2(x2) называется граф, определенный следующим образом:
а) множество вершин X является декартовым произведением X1 и X2, т.е. X = X1 X2 = {(xi1, xj2) / xi1 X1, xj2 X2};
б) множество вершин, смежных с вершиной (xi1, xj2) определяется как
G(xi1, xj2) = [G1(xi1) {xj2}] [{xi1} G2(xj2)] ( операция декартова произведения).
Для примера 5
G(x01, x02) = {G1(x01) {x02}} {{x01} G2(x02)} =
2204720-83820G(X) = G1(X1) + G2(X2)
(x01, x02)
(x01, x12)
(x11, x02)
(x11, x12)
(x21, x02)
(x21, x12)
Рис. 2.33 – Декартова сумма графов
00G(X) = G1(X1) + G2(X2)
(x01, x02)
(x01, x12)
(x11, x02)
(x11, x12)
(x21, x02)
(x21, x12)
Рис. 2.33 – Декартова сумма графов
= {(x11, x02), (x21, x02)} {(x01, x12)},
G(x01, x12) = {G1(x01) {x12}} {{x01} G2(x12)}=
= {(x11, x12),(x21, x12)} {(x01, x02)},
G(x11,x02) = {(x01, x02)} {(x11, x12)}, G(x11, x12) = {(x01, x12)} {(x11, x02)},
G(x21,x02) = {(x01, x02)} {(x21, x12)}, G(x21, x12) = {(x01, x12)} {(x21, x02)}.
Соответствующий граф изображен на рис. 2.33.
Граф G(X) называется декартовой суммой n графов
G(X) = G1(X1) + G2(X2) + ... + Gn(Xn), если
а) X = X1 X2 ... Xn;
б) G(x1, x2, ... , xn) = [G1(x1) {x2} ... {xn}] [{x1} G2(x2) ... {xn}] ... [{x1} {x2} ... Gn(xn)].
2.5 Степени графов2.5.1 Степени неориентированных графовПусть G(X) – неориентированный граф. Степенью m(x) графа G(X) в вершине x называется число ребер, инцидентных вершине x. Если все числа m(x) для x X конечны, то граф называется локально конечным. Петли можно считать одинарным или двойным ребром в зависимости от конкретной задачи.
Обозначим m(xi, xj) = m(xj, xi) – число ребер, соединяющих вершины xi и xj. Если в графе G(X) нет кратных ребер, то m(xi, xj) = 0 или m(xi, xj)=1.
Очевидно, что m(xi) = .
Поскольку каждое ребро учитывается в двух вершинах xi и xj, то общее число ребер m графа G(X)
(1)
Это выражение справедливо и для графов с петлями, если петлю считать двойным ребром.
Так как – четное число, то можно сделать вывод о том, что в конечном графе число вершин с нечетной степенью четно.
Это следует из того, что если из суммы вычесть все слагаемые, соответствующие вершинам с четной степенью, она останется четной.
Граф, степени всех вершин в котором равны, называется однородным, т.е. m(xi) = mn xi X.
Конечные однородные графы могут быть представлены в виде правильных многогранников (Платоновых тел): тетраэдра, куба, октаэдра, додекаэдра, икосаэдра и т.д. Примеры бесконечных однородных графов изображены на рис. 2.34.
1016045720Рис. 2.34 – Бесконечные однородные графы
00Рис. 2.34 – Бесконечные однородные графы
Из (1) следует, что в однородном графе степени mn число ребер равно , где n – число вершин.
2.5.2 Степени ориентированных графовВ ориентированном графе существуют такие понятия, как полустепени исхода и захода.
Полустепенью исхода m(x) называется число дуг, выходящих из вершины x. Полустепень захода m(x) – число дуг, входящих в вершину x. Петли считают по одному разу в каждой из полустепеней.
Аналогом кратности неориентированных ребер m(xi, xj) в ориентированном графе являются две кратности: m(xi, xj) – число дуг, направленных от xi к xj, и m(xi, xj) – число дуг, направленных от xj к xi.
Таким образом, m(xi, xj) = m(xj, xi).
Число дуг, выходящих из вершины xi, определится суммой ,
а число дуг, входящих в вершину xi, равно .
Отсюда общее число дуг графа
.
Если все полустепени m(x) и m(x) равны для всех x X, то ориентированный граф G(X) называется однородным графом степени mn.
Для такого графа m = mn n, где n – число вершин графа G(X). Примеры однородных ориентированных графов приведены на рис.2.35.
101600101600x1
x2
x3
x0
Рис. 2.35 – Конечный и бесконечный однородные ориентированные графы
00x1
x2
x3
x0
Рис. 2.35 – Конечный и бесконечный однородные ориентированные графы
2.6 Характеристики расстояний в графахПусть G(X) – конечный или бесконечный ориентированный граф. Отклонением d(xi, xj) его вершины xi от вершины xj называется длина кратчайшего пути из xi в xj: d(xi, xj) = {l[Sk(xi, xj)]}.
Отклонение d(xi, xj) удовлетворяет следующим аксиомам метрического пространства:
1) d(xi, xj) 0;
2) d(xi, xj) = 0 xi = xj;
3) d(xi, xj) + d(xj, xk) d(xi, xk) – неравенство треугольника
и не удовлетворяет четвертой аксиоме, а именно:
4) d(xi, xj) d(xj, xi) так как граф ориентирован.
Необходимо отметить, что если xj G(xi), то d(xi, xj) = ∞.
Отклоненностью вершины xi называется наибольшее из отклонений d(xi, xj) по всем xj:
d(xi) = {d(xi, xj)} = {{l[Sk(xi, xj)]}}.
В качестве примера рассмотрим схему первой (1870 г.) сети связи для почтовых голубей. Граф, представляющий ее, изображен на рис. 2.36, а матрица отклонений и вектор отклоненностей – в табл. 2.2 и табл.2.3 соответственно.
1930400-292100Париж
Гренобль
Ницца
Марсель
Лион
Бордо
Рис. 2.36 – Схема первой сети связи для почтовых голубей
00Париж
Гренобль
Ницца
Марсель
Лион
Бордо
Рис. 2.36 – Схема первой сети связи для почтовых голубей
Таблица 2.2 – Матрица отклонений d(xi , xj)
Города П Б Л Г М Н
Париж 0 2 1 1 2 2
Бордо 1 0 2 2 3 3
Лион 2 1 0 1 1 2
Гренобль 0 1
Марсель 3 2 1 2 0 1
Ницца 0
Таблица 2.3 – Вектор отклоненностей d(xi)
Города П Б Л Г М Н
d(xi) 2 3 2 3
Для неориентированного графа, соответствующего графу, изображенному на рис. 2.36, можно найти аналогичные характеристики, но без учета ориентации дуг. При этом матрица d(xi, xj) оказывается симметричной.
В связном неориентированном графе понятиям отклонения и отклоненности соответствуют понятия: расстояние и удаленность.
Пусть G(X) – связный неориентированный граф. В соответствии с определением связности для вершин xi и xj графа существует элементарная цепь S(xi, xj) с концами xi и xj, причем l(S) 0.
Расстоянием d(xi, xj) между вершинами xi и xj называется длина цепи S(xi, xj) наименьшей длины
d(xi, xj) = {l[Sk(xi, xj)]}.
Удаленность вершины xi графа G(X) есть число
d(xi)={d(xi , xj)}= {{l[Sk(xi, xj)]}}.
Центром графа называется вершина, в которой достигается наименьшая из отклоненностей (удаленностей), если таковая является конечным числом (Париж, Лион).
В графе может быть несколько центров, а может не быть ни одного.
Периферийной вершиной графа называется вершина с наибольшей отклоненностью или удаленностью (Гренобль, Ницца).
Радиусом (G) ориентированного графа называется отклоненность его центра.
(G) = = .
В примере (рис.2.36) (G) = 2 (d(Париж) = d(Лион) = 2). Если в графе нет центров, то полагают, что (G) = ∞. В неориентированном графе (G) – удаленность центра.
Диаметром неориентированного графа называется удаленность периферийной вершины.
2.7 Определение путей и кратчайших путей
в графах2.7.1 Алгоритм определения пути в графеРешение целого ряда практических задач, описываемых в терминах графов, зависит от существования некоторой цепи, соединяющей данную вершину с какой-либо другой. Например, в качестве вершин графа можно рассматривать исходные позиции или состояния некоторой головоломки или игры, а ребра будут указывать возможные ходы из одной позиции в другую. Ребро будет неориентированным или ориентированным в зависимости от того, обратим переход или нет.
Граф G(X) с двумя отмеченными вершинами xi, xj называется (xi, xj)-плоским, если граф G(X) = G(X) (xi, xj), полученный добавлением к G(X) ребра (xi, xj), является плоским.
Рассмотрим алгоритм определения пути, ведущего из вершины xi в xj плоского графа. Если xi не является вершиной никакого простого цикла, то при определении алгоритма пути из xi в xj в графе G(X) всегда выбирается самый левый или самый правый коридор (ребро) (рис. 2.37).
Аналогичный алгоритм определения пути в прадереве предполагает следующие действия. Из корня идти по какой-либо ветви насколько возможно далеко, затем возвратиться на какой-нибудь перекресток и отправиться по новому направлению (еще не пройденному) и т.д. Искомый путь из xi в xj будет состоять из всех тех ребер, которые в процессе поиска были пройдены по одному разу.
При определении пути в произвольном графе, не являющемся прадеревом, приходим к предыдущему случаю следующим образом. Если, пройдя по некоторому ребру g, попадаем на уже пройденный ранее перекресток x, то ребро g «отсекается» от одной из своих концевых точек. После отсечения ребра, пройденные хотя бы один раз, образуют прадерево.
-172720-83820xi
x8
x3
x7
x5
x6
x11
x12
x14
x15
x13
x16
x19
xj
x17
x18
x20
xi
x9
x10
xi
x1
x2
x4
Рис. 2.37 – Определение пути в графе
путь при выборе левого коридора;
путь при выборе правого коридора.
00xi
x8
x3
x7
x5
x6
x11
x12
x14
x15
x13
x16
x19
xj
x17
x18
x20
xi
x9
x10
xi
x1
x2
x4
Рис. 2.37 – Определение пути в графе
путь при выборе левого коридора;
путь при выборе правого коридора.
При определении пути в графе с помощью алгоритма Тарри необходимо в данном алгоритме пользоваться правилом:
не проходить дважды по одному ребру в одном и том же направлении;
находясь в вершине x, не выбирать того ребра, которое привело в данную вершину в первый раз (если есть возможность другого выбора).
2.7.2 Алгоритм определения кратчайших путей в графеЭта задача имеет большое значение в практических применениях. К ней сводятся многие задачи выбора наиболее экономичного (с точки зрения расстояния или стоимости) маршрута на имеющейся карте дорог, наиболее экономичного способа перевода динамической системы из одного состояния в другое и т.д. Существует много математических способов решения, но часто методы, основанные на теории графов, наименее трудоемки.
Рассмотрим задачу о кратчайшем пути. Пусть дан G(X), дугам которого приписаны веса (расстояния, стоимости), задаваемые матрицей . Задача о кратчайшем пути состоит в нахождении кратчайшего пути от заданной начальной вершины s X до заданной конечной вершины t X при условии, что такой путь существует. В общем случае возможно Сij 0, Сij 0, Сij = 0. Единственное ограничение состоит в том, чтобы в графе G(X) не было циклов с отрицательным суммарным весом.
Приведем очень простой и эффективный алгоритм Дейкстры решения этой задачи для случая Сij 0 i, j. Алгоритм основан на приписывании вершинам временных пометок, причем пометка вершины дает верхнюю границу длины пути от s к этой вершине. Величины этих пометок постепенно уменьшаются с помощью некоторой итерационной процедуры, и на каждом шаге итерации точно одна из временных пометок становится постоянной. Это означает, что пометка уже не является верхней границей, а дает точную длину кратчайшего пути от s к рассматриваемой вершине.
Опишем этот алгоритм.
Пусть l(xi) – пометка вершины xi. Алгоритм Дейкстры состоит из следующих этапов.
Присвоение начальных значений
Шаг 1. Положить l(s) = 0 и считать эту пометку постоянной. Положить l(xi) = xi s и считать эти пометки временными. Положить p = s.
Обновление пометок
Шаг 2. Для всех xi G(P), пометки которых являются временными, изменить пометки в соответствии с выражением
l(xi) = min [l(xi), l(p) + c(p, xi)] (2)
Превращение пометки в постоянную
Шаг 3. Среди всех вершин с временными пометками найти такую xi*, для которой l(xi*) = min[l(xi)]. Считать пометку вершины xi* постоянной и положить p = xi*.
Шаг 4, а (выполняется в случае, если требуется найти лишь путь от S к t). Если p = t, то l(p) является длиной кратчайшего пути. Останов. Если p t, перейти к шагу 2.
Шаг 4,б (Выполняется в случае, если требуется найти путь от S ко всем остальным вершинам). Если все вершины отмечены как постоянные, то эти отметки дают длины кратчайших путей. Останов. Если некоторые пометки являются временными, перейти к шагу 2.
Проиллюстрируем работу алгоритма на примере графа, изображенного на рис.2.38, матрица весов которого дана в табл.2.4. Здесь каждое ребро рассматривается как пара противоположно ориентированных дуг равного веса. Требуется найти все кратчайшие пути от x1 ко всем остальным вершинам. Постоянные пометки будем обозначать знаком +.
Шаг 1. l(x1) = 0+, l(xi) = xi x1, p = x1.
Первая итерация.
Шаг 2. G(p) = G(x1) = {x2, x7, x8, x9}.Все эти вершины имеют временные пометки.
58356540640x3
x2
x1
x5
x8
x9
x7
x6
x4
Рис.2.38 - Пример графа к алгоритму Дейкстры
00x3
x2
x1
x5
x8
x9
x7
x6
x4
Рис.2.38 - Пример графа к алгоритму Дейкстры
Таблица 2.4 – Матрица смежности с весами для графа на рис. 2.38
x1 x2 x3 x4 x5 x6 x7 x8 x9
x1 10 3 6 12
x2 10 18 2 13
x3 18 25 20 7
x4 25 5 16 4 x5 5 10 x6 20 10 14 15 9
x7 2 4 14 24
x8 6 23 15 5
x9 12 13 9 24 5 Уточняем пометки в соответствии с формулой (2).
l(x2) = min(, 0+ +10) = 10, аналогично l(x7) = 3, l(x8) = 6, l(x9) = 12.
1885315-14414500Шаг 3. min(10, 3, 6,12,) = 3,
x2x7x8x9x3, x4, x5, x6
соответственно x7 получает постоянную пометку l(x7) = 3+, p = x7.
10160492760x1
x2
x9
x8
x7
x3
x6
x5
x4
Рис. 2.39 – Пометки в начале второй итерации
0+
3+




6
12
10
00x1
x2
x9
x8
x7
x3
x6
x5
x4
Рис. 2.39 – Пометки в начале второй итерации
0+
3+




6
12
10
Шаг 4. Не все вершины имеют постоянные пометки, поэтому переходим к шагу 2. Значения пометок вершин графа приведены на рис. 2.39. Обведены вершины с постоянными пометками.
Вторая итерация.
Шаг 2. G(p) = G(x7) = {x2, x4, x6, x9}.Пометки всех этих вершин временные. Из (2) получим l(x2) = 5, l(x4) =7, l(x6) = 17, l(x9) = 12.
1917700-3810000Шаг 3. min(5,7,17,6,12,) = 5,
x2x4x6x8x9x3, x5
соответственно x2 получает постоянную пометку. l(x2) = 5+, p = x2.
10160287020x1
x8
x2
x7
x9
x5
x6
x3
x4
Рис. 2.40 – Пометки в начале третьей итерации
0+
3+

17
7

6
12
5+
00x1
x8
x2
x7
x9
x5
x6
x3
x4
Рис. 2.40 – Пометки в начале третьей итерации
0+
3+

17
7

6
12
5+
Шаг 4. Перейти к шагу 2. Значения пометок приведены на рис. 2.40.
Третья итерация.
Шаг 2. G(p) = G(x2) = {x1, x3, x7, x9}. Только вершины x3 и x9 имеют временные пометки. Из (2) получаем: l(x3) = min(, 5+ +18) = 23, аналогично l(x9) = 12.
Шаг 3. min(23,7,17,6,12,) = 6,
x3x4x6x8x9x5
соответственно x8 получает постоянную пометку l(x8) = 6+, p = x8.
193040291465x1
x8
x2
x7
x9
x5
x6
x3
x4
Рис. 2.41 – Пометки в начале четвертой итерации
0+
3+

17
7
12
6+
12
5+
00x1
x8
x2
x7
x9
x5
x6
x3
x4
Рис. 2.41 – Пометки в начале четвертой итерации
0+
3+

17
7
12
6+
12
5+
Шаг 4. Перейти к шагу 2 (рис. 2.41).
Продолжая итерационный процесс, получим в итоге постоянные пометки для всех вершин графа (рис.2.42) и кратчайшие пути от вершины x1 ко всем остальным вершинам. Эти пути выделены на рис. 2.42 жирными линиями.
Для нахождения кратчайшего пути между вершиной x2 и начальной вершиной x1, последовательно используем соотношение
l(xi) + C(xi, xi) = l(xi). Полагая i = 2 находим вершину x2, непосредственно предшествующей x2 в кратчайшем пути от x1 к x2:
467360864235x5
12+
17+
7+
x1
x8
6+
x9
11+
23+
5+
0+
x7
3+
x3
x2
x6
x4
Рис.2.42 – Пометки и кратчайшие пути в графе
00x5
12+
17+
7+
x1
x8
6+
x9
11+
23+
5+
0+
x7
3+
x3
x2
x6
x4
Рис.2.42 – Пометки и кратчайшие пути в графе
l(x2) + C(x2, x2) = l(x2) = 5. Этому соотношению удовлетворяет вершина x7. Следовательно, x2 = x7. Полагая i = 7 и применяя соотношение еще раз, получим x7 = x1. Поэтому кратчайший путь состоит из вершин x1, x7, x2. Аналогичным образом находим все кратчайшие пути от x1 к остальным вершинам.
2.8 Обход графаВ теории графов есть понятие обход графа. Это маршрут, содержащий все ребра или вершины графа и обладающий определенными свойствами. Наиболее известными обходами графа являются эйлеровы и гамильтоновы цепи и циклы.
2.8.1 Эйлеровы цепи, циклы, пути, контурыЭти понятия возникли в статье Эйлера в 1736 г., в которой он рассуждает о Кенигсбергских мостах. Известно, что Кенигсберг (ныне Калининград) расположен на берегах реки Преголи и островах на ней. Все части города соединены мостами. На рис. 2.43,а приведен план расположения семи мостов в Кенигсберге. Задача состоит в том, чтобы пройти каждый мост по одному разу и вернуться в исходную точку C.
Так как существенны только переходы через мосты, то план города можно свести к изображению графа, в котором ребра соответствуют мостам, а вершины – различным разделенным частям города (рис. 2.43,б).
Поскольку в конце обхода нужно вернуться в исходную часть города, и на каждом мосту нужно побывать по одному разу, этот маршрут является простым циклом, содержащим все ребра графа. В дальнейшем такие 731520464820A
C
B
D
g
e
f
b
a
c
d
а)
C
a
b
B
g
D
f
d
c
A e
б)
Рис. 2.43 – Схема Кенигсбергских мостов и соответствующий граф
00A
C
B
D
g
e
f
b
a
c
d
а)
C
a
b
B
g
D
f
d
c
A e
б)
Рис. 2.43 – Схема Кенигсбергских мостов и соответствующий граф
циклы стали называть эйлеровыми, а графы, имеющие эйлеров цикл, – эйлеровыми графами.
Эйлеров цикл можно считать следом пера, вычерчивающего этот граф, не отрываясь от бумаги. Таким образом, эйлеровы графы – это графы, которые можно изобразить одним росчерком пера, причем процесс такого изображения начинается и заканчивается в одной и той же точке.
Обнаружив, что в данном графе не существует циклических обходов, проходящих по всем ребрам по одному разу, Эйлер обратился к общей задаче: при каких условиях в графе можно найти такой цикл? Ответ на этот вопрос дает следующая теорема.
Теорема 1 (Эйлера). Конечный связный неориентированный мультиграф является эйлеровым графом тогда и только тогда, когда в нем отсутствуют вершины нечетной степени.
Доказательство. Каждый раз, когда эйлеров цикл проходит через какую-либо вершину, он должен войти в нее по одному ребру, а выйти по другому. Поэтому условие отсутствия вершин нечетной степени в эйлеровом графе является необходимым.
Для доказательства достаточности предположим, что все вершины графа имеют четные степени. Начнем цепь P в произвольной вершине xi графа G (рис. 2.44,а), и будем продолжать ее, насколько возможно, все время через новые ребра. Так как в каждой вершине число ребер четно, этот процесс может закончиться только в xi. Если цикл P содержит не все ребра графа G, то удалим из G часть, соответствующую циклу P.
Графы P и G имеют четные степени всех вершин. То же должно быть справедливо и для оставшегося графа .
Так как граф G связен, в цикле P должна найтись вершина xj , инцидентная также ребрам . Из xj можно построить новую цепь P, содержащую только ребра из . И снова такая цепь может закончиться только при возвращении в xj . Но тогда из P и P можно составить новый цикл
P1= P(xi , xj) P P(xj, xi),
403352033274000который возвращается в xi и содержит больше ребер, чем P. Если P1 не является эйлеровым циклом, то построение повторяется. По окончании построения получим эйлеров цикл.
Процесс построения эйлерова цикла иллюстрирует рис. 2. 44, б. Объединяя,10160223520xi
xj
P

x1
x2
x3
x7
x8
x4
x5
x6
Рис. 2.44 – Иллюстрация доказательства теоремы Эйлера (а) и
пример построения Эйлерова цикла (б)
а)
б)
00xi
xj
P

x1
x2
x3
x7
x8
x4
x5
x6
Рис. 2.44 – Иллюстрация доказательства теоремы Эйлера (а) и
пример построения Эйлерова цикла (б)
а)
б)
например, циклы {x1, x2, x3, x4, x5, x6, x1} и {x3, x7, x8, x3, x5, x1, x3}, получим эйлеров цикл { x1, x2, x3, x7, x8, x3, x5, x1, x3, x4, x5, x6, x1}.
Как граф с эйлеровым циклом можно рассмотреть схему обхода выставки по различным коридорам, которую посетители должны пройти согласно указателям так, чтобы увидеть каждый экспонат по одному разу.
Эйлеровой цепью называется цепь, включающая все ребра данного конечного неориентированного графа G(X), но имеющая различные начало хi и конец хj. Чтобы в графе существовала эйлерова цепь, он должен быть связным и все вершины, кроме хi и хj должным иметь четные степени. Степени вершин хi и хj должны быть нечетными, что естественно, так как из хi мы лишний раз выходим, а в хj мы лишний раз входим. Эти условия являются достаточными для существования эйлеровой цепи.
Важен также следующий вопрос: каково наименьшее количество не пересекающихся по ребрам цепей, покрывающих конечный связный граф G(X) (покрыть – значит включить все ребра графа в цепь)? На этот вопрос отвечает теорема 2.
Теорема 2. В конечном связном неориентированном графе G(X) с k вершинами нечетной степени минимальное число непересекающихся по ребрам цепей, покрывающих G(X) равно k/2.
4033520165862000Доказательство. Пусть G(X) не является эйлеровым графом и k – число его вершин нечетной степени. Ранее было доказано, что k четно. Каждая вершина нечетной степени должна быть концом хотя бы одной из покрывающих граф цепей. Следовательно, число таких цепей не меньше, чем k/2. Но можно показать, что и не больше. Соединим попарно вершины нечетной степени k/2 ребрами. Тогда степень каждой вершины увеличиться на единицу и станет четной. Получится эйлеров граф, в котором существует эйлеров цикл. Теперь будем постепенно выбрасывать присоединенные ребра. При выбрасывании первого ребра эйлеров цикл превратится в эйлерову цепь, а при выбрасывании каждого последующего ребра одна из возникших к этому моменту цепей разобьется на две части. Таким образом, общее число этих цепей равно k/2.
В качестве примера рассмотрим граф на рис.2.45. В нем 10160106680x2
x3
x4
x5
x6
x1
Рис. 2.45 – Пример построения покрывающих цепей
00x2
x3
x4
x5
x6
x1
Рис. 2.45 – Пример построения покрывающих цепей
x1, x2, x3, x5 – вершины нечетной степени. Добавим два ребра: (x2, x5), (x1, x3) (штриховые линии). Получим эйлеров граф с эйлеровым циклом {x1, x2, x3, x4, x5, x2, x5, x6, x1, x3, x1}. Убрав (x3, x1), получим эйлерову цепь. Убрав (x2, x5), получим 2 покрывающих цепи: {x1, x2, x3, x4, x5, x2} и {x5, x6, x1, x3}.
Из теоремы 2 следует, что если в связном неориентированном мультиграфе имеются две вершины нечетной степени хi и хj, то существует эйлерова цепь, начинающаяся в хi и кончающаяся в хj.
Если связный мультиграф G(X) имеет четыре вершины нечетной степени, то его можно нарисовать двумя росчерками. Если количество нечетных степеней равно k, то граф можно нарисовать k/2 росчерками.
Рассмотрим теперь случай конечного ориентированного графа. Чтобы в конечном ориентированном графе существовал эйлеров цикл (контур), необходимо и достаточно, чтобы полустепени исхода и захода вершин этого графа по входящим и исходящим дугам были равны:
m(xi) = m(xj), xi X.
Доказательство то же, что и для неориентированного графа.
Так как любому неориентированному графу соответствует ориентированный, в котором каждое ребро заменено двумя дугами, инцидентными тем же вершинам и идущими в противоположном направлении, то отсюда следует, что в конечном связном графе всегда можно построить ориентированный цикл, проходящий через каждое ребро по одному разу в каждом из двух направлений. Такой цикл называется способом обхода всех ребер графа. Он используется во многих прикладных задачах, связанных с графами.
2.8.2 Гамильтоновы цепи, циклы, пути, контурыГамильтоновой цепью в неориентированном графе называется цепь, проходящая через каждую его вершину один и только один раз.
Гамильтоновым циклом в неориентированном графе называется цикл, проходящий через каждую вершину один и только один раз за исключением начальной вершины, которая совпадает с конечной.
Гамильтоновым путем в ориентированном графе называется путь S(x1, …, xn), проходящий через все вершины графа, притом только по одному разу.
Гамильтоновым контуром называется контур М(х0, x1,…, xn, x0) в ориентированном графе G(X), если он проходит через все вершины графа, притом только по одному разу.
Существует следующая распространенная интерпретация задачи о гамильтоновых циклах. Обед накрыт на круглом столе. Среди гостей некоторые являются друзьями. При каких условиях можно рассадить всех так, чтобы по обе стороны от каждого из присутствующих сидели его друзья?
В применении графов к играм вершины соответствуют различным позициям. Существование гамильтонова цикла равносильно существованию циклической последовательности ходов, содержащей каждую позицию по одному разу. Примером является известная задача о шахматном коне: можно ли, начиная с произвольного поля на доске, ходить конем в такой последовательности, чтобы пройти каждое из шестидесяти четырех полей и вернуться в исходное?
К гамильтоновым циклам относится также известная задача о бродячем торговце (задача о коммивояжере). Район, который должен посетить коммивояжер, содержит определенное количество городов. Расстояния между ними известны, и нужно найти кратчайшую дорогу, проходящую через все пункты и возвращающуюся в исходный. Эта задача имеет ряд приложений в экономике и исследовании операций.
Сформулирован целый ряд достаточных условий существования гамильтоновых цепей, циклов, путей и контуров. Приведем некоторые из них без доказательства.
1. Теорема Кёнига. В полном конечном графе всегда существует гамильтонов путь.
2. Если в графе G(X) с n вершинами для любой пары вершин хi и хj справедливо неравенство
m(xi) + m(xj) n – 1,
где m(xi), m(xj) – степени вершин хi и хj, то граф G(X) имеет гамильтонову цепь.
Несмотря на сходство в определении эйлерова и гамильтонового циклов, соответствующие теории для этих понятий имеют мало общего. Критерий существования для эйлеровых циклов был установлен просто, для гамильтоновых циклов никакого общего правила неизвестно. Более того, иногда даже для конкретных графов бывает трудно решить, можно ли найти такой цикл. В принципе, поскольку речь идет о конечном числе вершин, задачу можно решить перебором, однако эффективного алгоритма неизвестно. Имеются некоторые частные схемы для отдельных случаев. Один довольно большой пример определения кратчайшей воздушной линии, соединяющей все столицы штатов в США, просчитали Данциг, Джонсон, и Фалкерсон.
2.9 Характеристики графовРешение многих технических задач методами теории графов сводится к определению тех или иных характеристик графов, поэтому полезно знакомство со следующими характеристиками.
Цикломатическое число. Пусть G(X) – неориентированный граф, имеющий n вершин, m ребер и r компонент связности. Цикломатическим числом графа G называется число (G) = m – n + r.
Это число имеет интересный физический смысл: оно равно наибольшему числу независимых циклов в графе. При расчете электрических цепей цикломатическим числом можно пользоваться для определения числа независимых контуров.
Хроматическое число. Пусть p – натуральное число. Граф G(X) называется р-хроматическим, если его вершины можно раскрасить различными цветами так, чтобы никакие две смежные вершины не были раскрашены одинаково. Наименьшее число р, при котором граф является р-хроматическим, называется хроматическим числом графа и обозначается (G). Если (G) = 2, то граф называется бихроматическим. Необходимым и достаточным условием того, чтобы граф был бихроматическим, является отсутствие в нем циклов нечетной длины.
Хроматическое число играет важную роль при решении задачи наиболее экономичного использования ячеек памяти при программировании. Однако его определение, за исключением (G) = 2, представляет собой довольно трудную задачу, требующую применения ЭВМ.
Множество внутренней устойчивости. Множество S X графа G(X) называется внутренне устойчивым, если никакие две вершины из S не являются смежными, то есть для любого х S имеет место
G(x) S = .
Множество внутренней устойчивости, содержащее наибольшее число элементов, называется наибольшим внутренне устойчивым множеством, а число элементов этого множества называется числом внутренней устойчивости графа G. Наибольшее внутренне устойчивое множество играет важную роль в теории связи.
Множество внешней устойчивости. Множество T X графа G(X) называется внешне устойчивым, если любая вершина, не принадлежащая T, соединена дугами с вершинами из T, то есть для любого x T имеет место G(x) T .
Множество внешней устойчивости, содержащее наименьшее число элементов, называется наименьшим внешне устойчивым множеством, а число элементов этого множества называется числом внешней устойчивости графа G(X).
2.10 Задачи и упражнения229616048260Рис. 2.46 – К задаче 1
00Рис. 2.46 – К задаче 1
Покажите, что два графа на рис.2.46 изоморфны.
«Три дома и три колодца». Три поссорившихся соседа имеют три общих колодца. Можно ли провести непересекающиеся дорожки от каждого дома к каждому колодцу?
Найдите число частичных графов конечного графа с m ребрами.
Каково число ребер в полном неориентированном графе с n вершинами?
Пусть U – множество положительных целых чисел, на котором задано отношение «a есть делитель b». Постройте граф этого отношения для множества целых чисел от 1 до 20.
174752086360А
Д
Г
Б
В
Е
Рис. 2.47 – К задаче 6
00А
Д
Г
Б
В
Е
Рис. 2.47 – К задаче 6
На рис.2.47 задан граф отношения «быть сестрой» на множестве студентов-родственников нашего факультета. Постройте по рис.2.47 граф отношения «быть братом».
Постройте графы отношений для задач №№ 11 – 17 главы 1.
Постройте матрицы смежности и инциденций для правильных многогранников: тетраэдра, куба, октаэдра. Найдите для каждого из них число внутренней устойчивости, число внешней устойчивости, центр, периферийные вершины, радиус, диаметр.
Для графа, изображенного на рис.2.48 найдите:
257048039370Рис. 2.48 – К задаче 9
x6
x1
x2
x3
x4
x5
g10
g1
g2
g8
g4
g9
g3
g5
g7
g6
00Рис. 2.48 – К задаче 9
x6
x1
x2
x3
x4
x5
g10
g1
g2
g8
g4
g9
g3
g5
g7
g6
а) матрицу смежности (вершин);
б) матрицу инциденций;
в) наибольшее внутренне устойчивое множество;
г) наименьшее внешне устойчивое множество;
д) матрицу отклонений;
ж) центр и радиус графа.
Постройте графы, для которых радиус r равен 2, 3, и такие графы, для которых диаметр d равен 2, 3.
Определите, какие из графов трех правильных многогранников имеют эйлеровы циклы. В тех случаях, когда эйлерова цикла нет, определите, сколько требуется цепей, чтобы покрыть все ребра.
Какие из графов правильных многогранников имеют гамильтоновы цепи и циклы?
3. ОСНОВЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ3.1 Алгебра высказыванийИзучение математической логики мы начнём с изучения алгебры высказываний, на которой базируются другие логические исчисления (логика предикатов, вероятностная логика и т. д.). Алгебра высказываний представляет и самостоятельный интерес, как основа для построения моделей, описывающих некоторые дискретные устройства.
Под высказыванием понимается повествовательное предложение, о котором имеет смысл говорить, что оно истинно или ложно, но не то и другое вместе.
Примеры. 1. Волга впадает в Каспийское море.
2. Два больше трёх.
3. Я лгу.
Примеры 1, 2 являются высказываниями (1 – истинно, 2 – ложно). 3 – не высказывание (если предположить, что оно истинно, то в силу его смысла оно одновременно ложно и, наоборот, из ложности этого предложения вытекает его истинность).
В алгебре высказываний не рассматривают внутреннюю структуру высказываний, а ограничиваются рассмотрением их свойства представлять истину или ложь. Поэтому на высказывание можно смотреть, как на величину, которая может принимать только одно из двух значений «истина» или «ложь».
Высказывания будем обозначать буквами A, B, C,..., а их значения, то есть истину или ложь, соответственно цифрами 1 или 0.
В обычной речи сложные предложения образуются из простых с помощью связок: «и», «или», «если…, то» и др.
Примеры.1. Светит солнце, и идёт дождь.
2. Шесть делится на два или шесть делится на три.
3. Если контакт замкнут, то лампа горит.
Связки можно рассматривать как операции над высказываниями. В обычной речи не всегда удаётся однозначно определить истинность или ложность сложного высказывания по истинности или ложности его составных частей. В алгебре высказываний вводят операции, аналогичные связкам обычной речи, причём истинность или ложность сложного высказывания полностью определяется истинностью или ложностью его составляющих.
Пусть даны два произвольных высказывания А и В.
Выражение А ۸ В (читается: «А и В») означает высказывание, истинное только в том случае, когда А и В истинны. Такое высказывание называют конъюнкцией высказываний А и В. Символом ۸ обозначают операцию конъюнкции. Эта операция соответствует союзу «и» в обычной речи. Однако в повседневной речи не принято соединять союзом «и» два высказывания, далекие по содержанию. В алгебре же высказываний операция конъюнкции может быть применена к любым двум высказываниям. Так, например, для высказываний «пять больше трех» и «трава зеленая» их конъюнкция «пять больше трех и трава зеленая» является истинным высказыванием.
Выражение А ٧ В (читается: «А или В») означает высказывание, истинное, если хотя бы одно из высказываний А или В является истинным. Такое высказывание называют дизъюнкцией высказываний А и В. Символ ٧ обозначает операцию дизъюнкции. Эта операция соответствует союзу или обычной речи, применяемому в неисключающем смысле.
Дело в том, что в повседневной речи союз «или» может иметь два смысловых значения: неисключающее и исключающее. В первом случае подразумевается, что из двух высказываний, по крайней мере, одно истинно, а может быть и оба истинны. Примером является высказывание «В жаркую погоды пьют воду или едят мороженое». Во втором случае полагают, что из двух высказываний истинным является только одно («Сегодня мы поедем на экскурсию или пойдем на пляж»). Конъюнкция высказываний соответствует первому случаю.
Выражение А В (читается: «если А, то В» или «А влечет В») означает высказывание, которое ложно тогда и только тогда, когда А истинно, а В ложно. Такое высказывание называют импликацией высказываний А и В. Высказывание А называется условием или посылкой, высказывание В – заключением или следствием импликации. Символ обозначает операцию импликации. В обычной речи операции импликации соответствует связка если ..., то. Отличие состоит в том, что связка предполагает смысловую зависимость соединяемых высказываний, а для операции смысловая связь несущественна. Так, например, высказывания «если 22 = 5, то трава синяя» и «если два больше трех, то восемь делится на четыре» являются истинными, так как у первого из них ложная посылка, а у второго – истинное следствие. Импликация «если 22 = 4, то 5<2» ложна, поскольку ее условие истинно, а заключение ложно.
Выражение А В (читается: «А эквивалентно В», «для того, чтобы А, необходимо и достаточно, чтобы В», «А тогда и только тогда, когда В», «А равносильно В») означает высказывание, которое истинно тогда и только тогда А и В оба истинны или оба ложны. Такое высказывание называют эквивалентностью высказываний А и В. Символ означает операцию эквивалентности. В обычной речи этой операции соответствует связка тогда и только тогда, когда. Примером эквивалентности может служить высказывание «Треугольник АВС равнобедренный тогда и только тогда, когда угол при вершине В равен углу при вершине С».
ВыражениеА (читается: «не А») означает высказывание, которое истинно, когда А ложно и ложно, когда А истинно. Такое высказывание называют отрицанием высказывания А. Символ над буквой обозначает операцию отрицания. В обычной речи этой операции соответствует частица не. Например, для истинного высказывания «восемь делится на четыре» отрицанием является ложное высказывание «неверно, что восемь делится на четыре» или «восемь не делится на четыре».
Если А, В, С – произвольные высказывания, которые рассматриваются как величины, принимающие одно из двух значений 1 или 0, то, применяя к ним операции конъюнкции, дизъюнкции, импликации, эквивалентности и отрицания, можно получить новые сложные высказывания, например:
18884901016000((А ٧ В) ٨С) A B.(3)
В обычной речи не всегда удается однозначно определить истинность или ложность сложного высказывания по истинности или ложности его составных частей. В алгебре высказываний значение сложного высказывания полностью определяется значениями его составляющих. Предположим, что А – ложное высказывание, В – истинное, С – ложное. Тогда высказывание (3) является ложным в силу определения логических операций.
Наряду с высказываниями, принимающими определенные и постоянные значения 1, 0 и называемыми определенными высказываниями, в алгебре высказываний рассматривают переменные высказывания, которые не имеют определённого значения. Если X, Y, Z – переменные высказывания, то, применяя к ним операции конъюнкции, дизъюнкции, импликации, эквивалентности и отрицания, можно получить формулы алгебры высказываний. При задании значений переменных высказываний формула принимает определенное значение. Таким образом, каждая формула определяет некоторую функцию, переменными которой являются переменные высказывания. Переменные и функции принимают только два значения: истина или ложь, поэтому функции можно описать конечной таблицей, которую называют истинностной таблицей или таблицей истинности данной формулы.
Приведём истинностную таблицу формул X ٨ Y, X ٧ Y, X Y,
X Y,X (табл.3.1).
Таблица 3.1 – Истинностная таблица для операций над высказываниями
X Y X ٨ Y X ٧ Y X Y X Y X
0 0 0 0 1 1 1
0 1 0 1 1 0 1
1 0 0 1 0 0 0
1 1 1 1 1 1 0
Возможен случай, когда две формулы имеют одну и ту же истинностную таблицу. Такие формулы называют равносильными. При этом количество и состав переменных в формулах не обязательно должны совпадать. Так, например, равносильными являются формулыY ٧Z и
1016000381000((X ٧ Y) ٨Z) (X Y) (табл. 3.2).
Запись формул можно упростить, опуская некоторые скобки и считая, что если их нет, то выполнять операции нужно в следующем порядке:
отрицание;
конъюнкция;
дизъюнкция;
импликация;
эквивалентность.
Например, формулу X ٨ Y ٧ Z следует понимать как (X ٨ Y) ٧ Z.
Таблица 3.2 – Истинностная таблица для равносильных формул
36010853238500X Y Z Y ٧ Z ((X ٧ Y) ٨Z) (X Y)
0 0 0 1 1
0 0 1 1 1
0 1 0 0 0
0 1 1 1 1
1 0 0 1 1
1 0 1 1 1
1 1 0 0 0
1 1 1 1 1
Если все значения формулы в истинностной таблице равны 1, то формула называется тождественно истинной или тавтологией. Тавтологии называют также законами логики. В обычном языке рассуждение имеет импликативную форму «если то-то и то-то, то то-то и то-то». При этом заботятся не об истинности или ложности посылок и заключений, а о правильности рассуждений. Рассуждения должны быть правильными, то есть соответствующие им импликации должны быть тождественно истинными. С этой точки зрения задачей логики можно считать исследование тавтологий. Тавтологичность формулы можно всегда обнаружить с помощью таблиц истинности.
3.2 Булевы функцииФункция f (x1, x2,..., xn), принимающая два значения: 0 и 1 и зависящая от переменных, каждая из которых может принимать значения 0 и 1, называется булевой или переключательной. Из определения следует, что область определения булевой функции – совокупность всевозможных n-мерных наборов из нулей и единиц, а для её задания достаточно указать, какие значения функции соответствуют каждому из наборов (табл. 3.3).
Таблица 3.3 – Задание булевой функции
x1 x2 ... xn-1 xn f (x1, x2,...,xn-1, xn)
0 0 ... 0 0 f (0, 0,...,0, 0)
0 0 ... 0 1 f (0, 0,...,0, 1)
... ... ... ... ... .................………
1 1 ... 1 0 f (1, 1,...,1, 0)
1 1 ... 1 1 f (1, 1,...1, 1)
Порядок расположения наборов, принятый в таблице, называется стандартным или естественным. При таком порядке каждому набору
= (1,...,n), где i есть 0 или 1, ставится в соответствие число
N = 1 2n-1 + ... + n-1 2 + n .
Наборам (0, 0,...,0, 0), (0, 0,...,0, 1),..., (1, 1,...,1, 1) соответствуют числа 0, 1,..., 2n-1. Естественным порядком будет расположение наборов в порядке возрастания соответствующих им чисел. Десятичное число, соответствующее входному набору, является его номером. Поэтому очевидно, что количество k входных наборов для булевой функции n переменных равно k=2n. Количество же различных функций n переменных можно определить из следующих соображений. Каждая функция задается набором своих k значений (для k входных наборов), которому также можно поставить в соответствие k-разрядное двоичное число. Располагая теперь в таблице функции в порядке возрастания соответствующих им чисел, мы получим все возможные различные функции. Количество таких функций будет равно .
Рассмотрим другие способы задания булевых функций. Сначала познакомимся с функциями одной и двух переменных, которые часто употребляются в математической логике и кибернетике, их можно считать «элементарными» функциями (табл. 3.4, 3.5).
Таблица 3.4 – Булевы функции одной переменной
x g1(x) g2(x) g3(x) g4(x) g1(x), g4(x) – константы 0 и 1,
0 0 0 1 1 g2(x) = x,
1 0 1 0 1 g3(x) = x (отрицание x).
Таблица 3.5 – Булевы функции двух переменных
x1 x2 f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15 f16
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
Следует отметить, что к функциям двух переменных относятся и такие, которые в действительности зависят от одной переменной или не зависят ни от одной.
Функции f1, f16 – константы 0 и 1. Они не зависят существенно ни от одной переменной.
Функции f4 = х1, f11 =х2, f6 = х2, f13 =х1 зависят существенно только от одной переменной.
f2 = х1 ٨ х2 – конъюнкция или логическое умножение (знак «٨» можно заменять на «∙», либо опускать).
f8 = х1 ٧ х2 – дизъюнкция или логическое сложение.
f10 – эквивалентность, х1 х2.
f7 = х1 х2 или х1 + х2 (mod 2) – сложение по модулю два.
f12, f14 – импликация, х2 х1 и х1 х2.
f15 – штрих Шеффера, х1 | х2.
f9 – стрелка Пирса, х1 х2 (другое название – функция Вебба).
31280101905000f3, f5 – функции запрета х1 и х2 соответственно. f3 = х1 х2 ,
2101852222500f5 = х2 х1 .
Исходя из элементарных функций можно строить формулы, т.е. рассматривать функции от функций например, (x1 x2)х2) х3 .
Некоторые свойства элементарных функций
Функции конъюнкция, дизъюнкция, сумма по модулю 2 обладают свойством ассоциативности, что позволяет опускать скобки и использовать следующие обозначения:
n n
٨ xi = x1 x2 ... xn ,٧ xi = x1 ٧ x2 ٧...٧ xn ,
i=1i=1
1098550508000234950508000х1х2 =х1 ٧х2, х1 ٧ х2 =х1х2 – закон де Моргана,
– закон двойного отрицания.
х х = х, х ٧ х = х, хх = 0, х ٧х = 1,
х 0 = 0, х 1 = х, х ٧ 0 = х, х ٧ 1 = 1.
Свойства можно проверить по таблице булевых функций (табл. 3.5).
3.3 Совершенные дизъюнктивная и конъюнктивная нормальные формыРассмотрим возможность представления произвольной булевой функции в виде формулы из элементарных функций. Так, теоремы 1 и 2 доказывают возможность такого представления в виде формулы, содержащей только функции дизъюнкции, конъюнкции и отрицания.
Теорема 1. Произвольную булеву функцию f (x1,x2...,xn) можно представить в виде
=(1,...,1)
f (x1,x2...,xn) = ٧ f (1,2...,n) х11 х22 ... хnn , (4)
=(0,...,0)
где i {0, 1}, xi0 =xi, xi1 = хi , = (1,...,n) и дизъюнкция берётся по всем n-мерным наборам из нулей и единиц.
Доказательство. Покажем, что левая и правая части соотношения (4) совпадают. Произвольный набор = (1, 2,..., n), где каждое i {0,1}, подставим в соотношение (4). В левой части получим f (1,2,..,n), а в правой части
=(1,...,1)
٧ f(1,2,...,n) 1122...nn = f(1,2,...,n) 1122...nn =
=(0,...,0)
39420804064000= f (1,2,...,n) .
Равенства в правой части вытекают из свойств конъюнкции, дизъюнкции и из того, что х = 1 x = .
Если f (x1, x2,...,xn) ≢ 0, то соотношение (4) можно переписать в форме
f (x1, x2...,xn) = ٧ х11 х22хnn (5)
по всем
f ()=1
Эта форма называется совершенной дизъюнктивной нормальной формой (совершенной ДНФ) функции f (x1,x2,...,xn).
Построение совершенной ДНФ из табличного задания функции производится следующим образом. Для каждого набора = (1,...,n) такого, что f (1,...,n) = 1, составляется выражение х11хnn и затем все такие конъюнкции соединяются знаком дизъюнкции. Например, для функции сложения по модулю два совершенная ДНФ имеет вид
х1 х2 =х1х2 ٧ х1x2 .
Теорема 2. Произвольную булеву функцию f (x1,x2,...,xn) можно представить в виде
=(1,...,1)
f (x1,x2,...,xn) = ٨ (f (1,2...,n) ٧ х11 ٧ х21 ٧...٧ хnn) , (6)
=(0,...,0)
где i = {0,1}, xi0 = xi, xi1 = хi, = (1,...,n) и конъюнкция берётся по всем n-мерным наборам из нулей и единиц.
Доказательство. Из свойства булевой функции (закон двойного отрицания) имеем f (x1,...,xn) = (x1,...,xn).
Для функцииf (x1,...,xn) по теореме 1 существует представление в виде
=(1,...,1)
f (x1,x2,...,xn) = ٧ f (1,2,...,n) х11х22...хnn , тогда
=(0,...,0)
10991854064000 = (1,...,1)
f (x1,x2,...,xn) = ٧ f (1,2,...,n) х11х22...хnn =
=(0,...,0)

=(1,...,1)
16598901651000 = ٨ (f (1,2,...,n) ٧ x11 ٧ x22 ٧...٧ xnn), что следует из закона
=(0,...,0)
де Моргана.17595853238500 Заметим также, что xii = xii. Следовательно,
=(1,...,1)
39751003302000f (x1,х2,...,xn) = ٨ (f (1,2,...,n) ٧ х11 ٧ х22 ٧...٧ хnn)
=(0,...,0)
Если f (x1,x2,...,xn) ≢ 1, то соотношение (6) можно переписать в форме
f(x1,x2,...,xn) = ٨ (х11 ٧ х22 ٧...٧ хnn ).(7)
по всем ,
f()=0
Эта форма называется совершенной конъюнктивной нормальной формой (совершенной КНФ) функции f (x1,x2,...,xn).
Построим совершенную КНФ функции х1 х2 (табл. 3.5):
х1 х2 = (х1 ٧ х2) (х1 ٧ х2).
Вывод. Булеву функцию любого числа переменных можно построить из функций одной или двух переменных. Средством такого построения является суперпозиция булевых функций, то есть подстановка одних булевых функций вместо переменных в другие булевы функции.
3.4 Полнота системы булевых функцийСистема булевых функций {f1 (x11,...,x1p1),...,fs (xs1,...,xsps),...} называется полной, если для любой булевой функции f (x1,...,xn) можно построить равную её функцию, представляющую собой результат суперпозиции функций {f1,...,fs,...} и x1,...,xn .
Примеры полных систем булевых функций.
338518529210000x1x2, x1 ٧ x2,x1. Полнота следует из того, что для каждой функции можно построить совершенные ДНФ и КНФ.
x1x2,x1. Полнота следует из п.1 и равенства х1 ٧ х2 = х1х2 .
3502025-1524000x1 ٧ x2 , x1. Полнота следует из п.1 и равенства х1х2 =х1 ٧х2 .
х1х2, х1 х2, 1. Полна, так какх1 = х1 1, а система x1x2,x1 является полной (п.2).
Теорема 3. Любую булеву функцию f (x1,...,xn) можно представить в виде полинома
f (x1,x2,...,xn) = a0 a1x1 a2x2 ... a2n-1x1…xn,
где ai {0,1}, i = 0, 1,...,2n-1.
Доказательство. Система функций х1х2, х1 х2, 1, 0 полна. Пользуясь правилами
A A = 0, A ∙ A = A, A 0 = A,
A ∙ 0 = 0, A ∙ 1 = A, A ∙ B = B ∙ A,
A B = B A, (A B) ∙ C = A ∙ C B ∙ C,
398335517018000которые легко проверить, получим представление функции в виде полинома по модулю 2.
Легко показать, что представление функции в виде полинома по модулю два является единственным.
Как обнаружить полноту или неполноту булевых функций? Для решения этого вопроса познакомимся с пятью классами булевых функций.
Класс функций, сохраняющих ноль
Функция f (x1,...,xn) называется сохраняющей ноль, если она на наборе из нулей принимает значение 0, т.е. f (0,...,0) = 0.
Так, функции x1x2 , x1 ٧ x2, х, 0 – сохраняют ноль, функции x1 х2,х, 1 – не сохраняют.
Лемма 1. Из функций, сохраняющих ноль, суперпозицией можно получить только функции, сохраняющие ноль.
Доказательство. Поскольку функции, равные переменным, сохраняют ноль, достаточно показать, что функция
Φ (х1,...,хn) = f (f1 (x1,...,xn),..., fm (x1,...,xn))
сохраняет ноль, если функции f, f1,...,fm сохраняют ноль. Последнее следует из
39833555588000f (f1 (0,...,0),... fm (0,...,0)) = f (0,...,0) = 0.
Следствие. Полная система булевых функций должна содержать хотя бы одну функцию, не сохраняющую ноль.
Класс функций, сохраняющих единицу
Функция f (x1,...,xn) называется сохраняющей единицу, если она на наборе из единиц принимает значение 1, то есть f (1,..,1) = 1.
Так, функции x1x2 , x1 ٧ x2, х, 1 – сохраняют единицу, функции
x1 х2,х, 0 – не сохраняют.
Лемма 2. Из функций, сохраняющих единицу, суперпозицией можно получить только функции, сохраняющие единицу.
Доказательство очевидно.
Следствие. Полная система булевых функций должна содержать хотя бы одну функцию, не сохраняющую единицу.
Класс самодвойственных функций
Функция f (x1, ... ,xn) называется самодвойственной, если
f (x1, ... ,xn) =f (x1,…,xn). Например, x ,x – самодвойственные функции, x1x2, x1 ٧ x2 - несамодвойственные.
Лемма 3. Из самодвойственных функций путём суперпозиции можно получить только самодвойственные функции.
Доказательство. Пусть f (y1, ... ,ym), f1 (x1, ... ,xn),...,fm (x1, ... ,xn) самодвойственные функции. Надо показать, что
Φ (x1,...,xn) = f (f1 (x1,...,xn),..., fm (x1,...,xn)) самодвойственная.
Из цепочки равенств
Φ (x1,…,xn) =f (f1 (x1,…,xn),…,fm (x1,…,xn)) =
f (f1 (x1,…,xn),…,fm (x1,…,xn)) = f (f1(x1,…,xn),…,fm (x1,…,xn)) =398335521082000
= Φ (x1,...,xn) следует, что Φ (x1,...,xn) – самодвойственна.
Следствие. Полная система функций должна содержать хотя бы одну несамодвойственную функцию.
Лемма 4. Из несамодвойственной функции подстановкой x иx можно получить константу.
Доказательство. Функция f (x1, ... ,xn) несамодвойственная, поэтому найдется набор = (1,...,n) такой, что f (1,..., n) = f (1,...,n). По набору = (1,...,n) определяются вспомогательные функции
i (x) (i = 1,2...,n),
7080258064500 x, если i = 0,
i (x) =
x, если i = 1.
Функция i (x) обладает свойством i(0) = i, i(1) = i .
Рассмотрим функцию (x) = f (1(x), ... , n(x)). Она получена из функции f (x1, ... ,xn) подстановкой x иx. Функция (x) – константа, так как398399049530000 (0) = f (1(0),...,n(0)) = f (1,...,n) = f (1,...,n) =
= f (1(1),..., n(1)) = (1).
Класс монотонных функций
Набор = (1,...,n) предшествует набору = (1,...,n), если i i (i=1,2,...,n). Этот факт обозначаем как ≼ . Наборы, которые находятся в отношении ≼, называются сравнимыми.
Функция f (x1,...,xn) называется монотонной, если для любой пары наборов = (1,...,n) и = (1,...,n) таких, что ≼ , f () f().
Например, функции x1x2, x1 ٧ x2, x – монотонные, аx немонотонная.
Лемма 5. Из монотонных функций с помощью суперпозиции можно получить только монотонные функции.
Доказательство. Пусть функции f (y1,...,ym), f1 (x1,...,xn),...,fm (x1,...,xn) монотонные. Надо показать, что
Φ(x1,...,xn) = f (f1 (x1,...,xn),...,fm (x1,...,xn)) монотонная функция.
Пусть ≼ , тогда fi () fi () (i=1,...,m). Отсюда
37426903683000 Φ() = f (f1 (),...,fm ()) f (f1 (),...,fm ()) = Φ().
Следствие. Полная система функций должна содержать хотя бы одну немонотонную функцию.
Лемма 6. Из немонотонной функции путём подстановки констант 0, 1 и функции x можно получитьx.
Доказательство. Пусть дана немонотонная функция f (x1,...,xn), т.е. для неё существуют наборы = (1,...,n) и = (1,...,n) такие, что
≼, а f () > f (). Рассмотрим функцию (x), которая получается из функции f (x1,...,xn) подстановкой констант 0, 1 и функции x. Подстановку определим следующим образом: вместо xi будем подставлять i, если i = i, и x, если ii. Рассмотрим функцию (x).
(0) = f (1,..., n) > f (1,..., n) = (1).
39751001778000Следовательно, (x) =x.
Класс линейных функций
Функция f (x1,...,xn) называется линейной, если полином этой функции имеет вид
f (x1,...,xn) = a0 a1 x1 ...an xn , где ai {0,1} (i=0,1,...,n).
Например: x,x – линейны, x1x2 нелинейна.
Лемма 7. Из линейных функций суперпозицией можно получить только линейные функции.
Доказательство очевидно.
Следствие. Полная система функций должна содержать хотя бы одну нелинейную функцию.
Лемма 8. Из нелинейной функции f (x1,...,xn), констант 0, 1 и функций x,x, y суперпозицией можно получить конъюнкцию двух переменных xy.
Доказательство. Так как функция f (x1,...,xn) нелинейна, её полином по модулю 2 содержит хотя бы один член с конъюнкцией двух переменных xi и xj. Члены полинома, представляющего функцию f (x1,...,xn) можно перегруппировать следующим образом:
f (x1,...,xn) = xi xj f1 (x1,...,xi-1 ,xi+1,...,xj-1, xj+1,..., xn)
xi f2 (x1,...,xi-1, xi+1,...,xj-1, xj+1,..., xn)
xj f3 (x1,...,xi-1, xi+1,...,xj-1, xj+1,..., xn)
f4 (x1,..., xi-1 ,xi+1,..., xj-1 , xj+1,..., xn),
где функция f1(x1,..., xi-1 ,xi+1,..., xj-1 , xj+1,..., xn) ≢ 0, т.е. существует набор (1,..., i-1, i+1 ,..., j-1, j+1,..., n) такой, что
f (1,..., i-1, i+1 ,..., j-1, j+1,..., n) = 1.
Подставляя этот набор в f (x1,...,xn), получим функцию (xi, xj):
(xi, xj) = f (1,..., i-1, xi, i+1 ,..., j-1, xj, j+1,..., n) = xixj xi xj ,
где
= f2 (1,..., i-1, i+1,..., j-1, j+1,..., n),
= f3 (1,..., i-1, i+1,..., j-1, j+1,..., n),
= f4 (1,..., i-1, i+1,..., j-1, j+1,..., n).
Рассмотрим функцию F (x, y) = (x , y ) = xy .
Она получена суперпозицией (xi, xj), x, y и x (x = x 1).
Если = 0, то F (x, y) = xy,
39744654889500а если = 1, тоF (x, y) = xy.
Критерий полноты системы булевых функций дает теорема 4 (приведем ее без доказательства).
Теорема 4 (о полноте). Для того чтобы система булевых функций {f1 (x11,..., x1p1),..., fs (xs1,..., xsps),…} была полна, необходимо и достаточно, чтобы она содержала функцию, не сохраняющую 0; функцию, не сохраняющую 1; несамодвойственную функцию; немонотонную функцию; нелинейную функцию.
Теперь мы можем составить таблицу, отражающую принадлежность каждой из функций двух переменных к рассмотренным классам функций
(табл. 3.6).

Таблица 3.6 – Свойства функций двух переменных
Обозначение функции Наименование
функции Свойства функции
Сохраняющая 0 Сохраняющая 1 Самодвойственность Монотонность Линейность
f1 = 0 Нулевая функция + - - + +
f2 = x1 x2 Конъюнкция + + - + -
101603175000f3 = x1 x2 Запрет x1 f4 = x1 Повторение x1 101603175000f5 = x2 x1 Запрет x2 f6 = x2 Повторение x2 f7 = x1 x2 Сложение по |2| f8 = x1 ٧ x2 Дизъюнкция f9 = x1 x2 Стрелка Пирса f10 = x1 x2 Эквивалентность f11 =x2 Отрицание x2 f12 = x2 x1 Импликация x2 в x1 f13 =x1 Отрицание x1 f14 = x1 x2 Импликация x1 в x2 f15 = x1 | x2 Штрих Шеффера f16 = 1 Единичная функция Эта таблица весьма полезна при выявлении полных систем булевых функций. В ней заполнены только две первых строки. Оставшуюся часть таблицы заполните самостоятельно.3.5 Минимизация дизъюнктивных нормальных форм3.5.1 Основные определенияТеорема о полноте даёт ответ на вопрос, из какой системы функций можно получить в виде суперпозиции любую функцию. Но в практических задачах нужна не столько возможность, сколько правила, пользуясь которыми можно получить представление, оптимальное в некотором смысле. Каждое представление функции в виде суперпозиции можно охарактеризовать некоторым числом, которое называется сложностью данного представления (например, число применений операции суперпозиции) и зависит от конкретной задачи. Тогда можно поставить задачу об отыскании представления булевой функции наименьшей сложности. В принципе, такую задачу всегда можно решить последовательным перебором различных суперпозиций функций системы. Рассмотрим теперь суперпозиции над системой функций, содержащей лишь конъюнкцию, дизъюнкцию и отрицание. Именно для этих суперпозиций методы минимизации разработаны достаточно хорошо. Чтобы дать точную формулировку задачи, приведем некоторые определения.
Элементарной конъюнкцией Ui называется выражение
Ui = , где все (j = 1,…,r) – различны, а r – ранг конъюнкции. Единица считается конъюнкцией нулевого ранга.
Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция N = U1 ٧ U2 ٧…٧ Uk элементарных конъюнкций U1, U2,..., Uk . Совершенная ДНФ – частный случай ДНФ.
Минимальной ДНФ функции f (x1,...,xn) называется ДНФ
N = U1 ٧ U2 ٧…٧ Uk, представляющая функцию f (x1,...,xn) и содержащая наименьшее количество букв по сравнению с другими ДНФ, то есть число букв в N равно min, где ri - ранг конъюнкции Ui, а минимизация проводится по всем ДНФ функции f (x1,...,xn).
Тогда задача об отыскании представления булевой функции наименьшей сложности формулируется так: для всякой функции найти представление в виде минимальной ДНФ.
Прежде чем описать метод решения задачи дадим ещё несколько определений.
Импликантом функции f (x1,...,xn) называется элементарная конъюнкция Ui = ..., если выполнено соотношение Ui f (x1,...,xn) 1. Это означает, что если на некотором наборе импликант Ui обращается в единицу, то функция f(x1,...,xn) на этом наборе тоже обращается в единицу. Любая элементарная конъюнкция произвольной совершенной ДНФ является импликантом данной функции.
Простым импликантом функции f (x1,...,xn) называется импликант функции f (x1,...,xn) , если элементарная конъюнкция, получающаяся из него удалением любой буквы, не является импликантом функции.
Сокращенной ДНФ функции f (x1,...,xn) называется дизъюнкция всех простых импликантов функции f (x1,...,xn).
Теорема 5 (без доказательства). Сокращённая ДНФ представляет функцию f (x1,...,xn).
Теорема 6 (без доказательства). Минимальная ДНФ функции
f (x1,...,xn) получается из ее сокращённой ДНФ удалением некоторых элементарных конъюнкций.
3.5.2 Этапы минимизации ДНФВ силу теоремы 6 получение минимальной ДНФ можно разбить на два этапа.
Нахождение сокращенной ДНФ.
Нахождение тупиковых ДНФ (таких, из которых нельзя удалить ни
одного простого импликанта) путём удаления подмножества элементарных конъюнкций из сокращённой ДНФ. Выбор минимальной из полученных тупиковых ДНФ.
Рассмотрим первый этап получения минимальной ДНФ. Метод получения сокращённой ДНФ функции f(x1,...,xn) из ее совершенной ДНФ состоит в последовательном применении двух равносильных преобразований:
1) операции полного склеивания, которая состоит в замене выражения Ax ٧ Ax на A, так как
Ax ٧ Ax A (x ٧x) A∙1 A;
2) операции неполного склеивания, которая состоит в замене
Ax ٧ Ax на Ax ٧ Ax ٧ A, так как
Ax ٧ Ax ٧ A A (x ٧x) ٧ AA ٧ A = A ;
3) операции поглощения, которая состоит в замене
AB ٧ A на A, так как AB ٧ A A (B ٧ 1) A.
Здесь A и B – произвольные элементарные конъюнкции.
Теорема 7 (без доказательства). Сокращённую ДНФ функции
f (x1,...,xn) можно получить из ее совершенной ДНФ, применяя все возможные операции неполного склеивания, а затем операции поглощения.
Пример 1. Построить сокращённую ДНФ функции f (x1, x2) = x1 x2. Имеем
f (x1, x2) =x1x2 ٧x1x2 ٧ x1x2 =x1x2 ٧x1x2 ٧x1 ٧ x1x2 =
x1x2 ٧x1x2 ٧x1 ٧ x1x2 ٧ x2 =x1 ٧ x2 .
Теперь перейдем ко второму этапу получения минимальной ДНФ.
Пусть дана сокращённая ДНФ функции f (x1,...,xn): N = U1 ٧ U2 ٧…٧ Uk . Простой импликант называется ядерным (входящим в ядро функции
f (x1,...,xn) ), если
k
Ui ٧ Uj 1.
j = 1
i j
Эта запись означает, что простой импликант Ui является ядерным импликантом функции f (x1,...,xn), если существует набор = (1,...,n), на котором импликант Ui обращается в 1, а все остальные импликанты сокращённой ДНФ в ноль.
Пример 2. Найти ядерные импликанты функции f (x1,x2,x3,x4), заданной своей сокращённой ДНФ
x2x4 ٧ x1x4 ٧ x1x2 ٧ x2x3x4 ٧x1x3x4 ٧ x1x2x3.
Простой импликант x2x4 является ядерным, так как на наборе (0,0,0,0)x2x4 = 1, а дизъюнкция оставшихся импликантов
x1x4 ٧ x1x2 ٧ x2x3x4 ٧x1x3x4 ٧x1x2x3 = 0.
Простой импликант x1x4 неядерный, так как он равен единице
на наборах {1,0,0,0}, {1,0,1,0}, {1,1,0,0}, {1,1,1,0}, но на этих же наборах
x2x4 ٧ x1x2 ٧ x2x3x4 ٧x1x3x4 ٧x1x2x3 = 1,
следовательно
x1x4 x2x4 ٧ x1x2 ٧ x2x3x4 ٧x1x3x4 ٧x1x2x3 1.
Простой импликант x1x2 ядерный, так как на наборе {1,1,0,1}
x1x2 = 1, а x2x4 ٧ x1x4 ٧ x2x3x4 ٧x1x3x4 ٧x1x2x3 = 0.
Простой импликант x2x3x4 неядерный, так как на наборах {0,1,1,1}, {1,1,1,1}
x2x4 ٧ x1x4 ٧ x 1x2 ٧x1x3x4 ٧x1x2x3 = 1.
Простой импликантx1x3x4 неядерный, так как на наборах {0,0,1,1}, {0,1,1,1}
x2x4 ٧ x1x4 ٧ x1x2 ٧ x2x3x4 ٧x1x2x3 = 1;
Простой импликантx1x2x3 неядерный, так как на наборах {0,0,1,0}, {0,0,1,1}
x2x4 ٧ x1x4 ٧ x1x2 ٧ x2x3x4 ٧x1x3x4 = 1.
Теорема 8 (без доказательства). Простой импликант Ui входит во все тупиковые ДНФ тогда и только тогда, когда Ui входит в ядро функции
f (x1,...,xn), то есть тогда и только тогда, когда он является ядерным.
Следствие. Пусть ядро f (x1,...,xn) состоит из импликантов
Uℓ1, ... ,Uℓm, тогда импликант Uℓ , для которого выполнено соотношение
m
Uℓ ٧ Uℓj ≡ 1
j = 1
( импликант Uℓ обращается в единицу на тех же наборах, что и дизъюнкция ядерных импликантов), не входит ни в одну из тупиковых ДНФ функции f (x1,...,xn).
Возвращаясь к примеру 2, отметим, что импликант x1x4 удовлетворяет следствию из теоремы 8: x1x4 x2x4 ٧ x1x2 1 и поэтому не входит ни в одну тупиковую форму.
Импликант x2x3x4, для которого
x2x3x4 x2x4 ٧ x1x2 1, не удовлетворяет следствию.
Импликантx1x3x4, для которого
x1x3x4 x2x4 ٧ x1x2 1, не удовлетворяет следствию.
Импликантx1x2x3, для которого
x1x2x3 x2x4 ٧ x1x2 1, не удовлетворяет следствию.
Таким образом, последовательность действий при выполнении второго этапа состоит в следующем:
для каждого простого импликанта сокращённой ДНФ проверить,
входит он в ядро или нет. Отметить неядерные импликанты;
проверить для отмеченных импликантов выполнение следствия
из теоремы 8. Простые импликанты, для которых выполнено следствие, удалить из сокращённой ДНФ;
проверить возможность удаления оставшихся отмеченных конъ-
юнкций. Из полученных тупиковых ДНФ выбрать минимальную ДНФ.
Рассмотрим эту последовательность действий на примере 2:
1) нашли ядро функции f (x1, x2, x3, x4), состоящее из простых импликантов x2x4 и x1x2. Отметим курсивом в сокращённой ДНФ неядерные импликанты:
x2x4 ٧ x1x4 ٧ x1x2 ٧ x2x3x4 ٧x1x3x4 ٧x1x2x3;
2) среди помеченных импликантов нашли удовлетворяющий следствию из теоремы 8. Это импликант x1x4. Удалим его из сокращённой ДНФ:
x2x4 ٧ x1x2 ٧ x2x3x4 ٧x1x3x4 ٧x1x2x3;
3) для получения тупиковых ДНФ удаляем подмножества отмеченных импликантов. Можно удалить следующие подмножества:
{ x2x3x4,x1x3x4,x1x2x3 }I, { x2x3x4,x1x3x4 }II, { x2x3x4,x1x2x3 }III,
{x1x3x4,x1x2x3 }IV, { x2x3x4 }V, {x1x3x4 }VI, {x1x2x3 }VI I.
При каждом удалении нужно проверять, представляет ли оставшаяся ДНФ функцию f (x1, x2, x3, x4).
Если удалить подмножество I, то получим ДНФ, не представляющую функцию f (x1, x2, x3, x4), так как на наборе {0,1,1,1} функция
f (x1, x2, x3, x4), = 1, а x2x4 ٧ x1x2=0.
Если удалить подмножество II, то получим ДНФ, не представляющую функцию f (x1, x2, x3, x4), так как на наборе {0,1,1,1} функция
f (x1, x2, x3, x4), = 1, а x2x4 ٧ x1x2 ٧x1x2x3 = 0.
Если удалить подмножество III, получим минимальную ДНФ функции f (x1, x2, x3, x4):
x2x4 ٧ x1x2 ٧x1x3x4 - минимальная ДНФ.
3.5.3 Минимизация ДНФ методом КвайнаСуществуют и другие методы, позволяющие независимо от исходной формы представления функции найти все ее тупиковые формы и выбрать из них минимальную. Одним из них является метод Квайна. В соответствии с этим методом отыскание минимальной ДНФ проводится в несколько этапов.
Первый этап. Функция, заданная в виде логической формулы произвольной формы, представляется в совершенной ДНФ. При этом:
1) последовательным применением эквивалентных преобразований логическая функция приводится к ДНФ, то есть к форме, не содержащей знаков отрицания над функциями, более сложными, чем один из аргументов;
2) каждый член ДНФ, представляющий собой конъюнкцию менее n членов (n - количество аргументов функции), развертывается в дизъюнкцию нескольких элементарных конъюнкций умножением на выражение вида (x1 ٧x1)(x2 ٧x2)..., тождественно равное единице;
3) приводятся, если возможно, подобные члены.
Второй этап. Отыскиваются все простые импликанты данной функции. Для этого выписываются все элементарные конъюнкции, входящие в СДНФ. Каждая из пар этих конъюнкций исследуется на возможность склеивания. Члены, участвовавшие хотя бы в одном склеивании, отмечаются, но не исключаются из дальнейших сравнений.
В результате выявляются группы конъюнкций, содержащие по
(n - 1) члену. С этой группой конъюнкций проводится та же процедура, после которой получим группы конъюнкций, содержащие по (n - 2) членов и так далее, пока не останется ни одного члена, допускающего склеивания с каким либо другим членом.
Добавление к исходной ДНФ любого количества «склеенных» членов не изменяет вида функции. Последующее исключение всех членов, отмеченных в процессе склеивания, тоже не изменяет функцию, так как они поглощаются склеенными членами. Все неотмеченные в процессе преобразований члены представляют собой простые импликанты, а их дизъюнкция эквивалентна исходной функции.
Третий этап. Дизъюнкция всех простых импликантов может оказаться избыточной формой представления функции. Поэтому исследуется возможность удаления некоторых из них. Для этого составляется импликантная таблица, строки которой обозначаются выявленными на втором этапе простыми импликантами, а столбцы – элементарными конъюнкциями, входящими в совершенную ДНФ.
Любая клетка этой таблицы отмечается, если простой импликант, записанный в соответствующей строке, является составной частью элементарной конъюнкции, записанной в соответствующем столбце. Иначе говоря, данный простой импликант покрывает нашу функцию на наборе, соответствующем элементарной конъюнкции, записанной в столбце.
В каждом столбце при этом может оказаться несколько отмеченных клеток. Задача упрощения ДНФ сводится к вычеркиванию из таблицы максимального количества строк таким образом, чтобы заданная функция на всех наборах, обращающих ее в единицу, оказалась покрытой хотя бы одним простым импликантом.
Эту задачу можно выполнить в следующей последовательности:
1) выявляются столбцы, содержащие только одну помеченную клетку. Простые импликанты, соответствующие этим клеткам, записываются в окончательное выражение для ДНФ как обязательные члены. После этого в таблице вычеркиваются строки, соответствующие обязательным простым ипликантам и столбцы, содержащие отмеченные клетки в вычеркнутых строках. Вычеркивание столбцов возможно потому, что соответствующие им элементарные конъюнкции уже покрыты обязательными простыми импликантами и поэтому их можно исключить из дальнейшего рассмотрения;
2) если после этого в таблице окажутся такие пары столбцов, что всем отмеченным клеткам второго столбца соответствуют в тех же строках отмеченные клетки первого столбца, а возможно, и некоторые другие отмеченные клетки, то первый столбец вычеркивается. Это возможно потому, что какую бы совокупность простых импликантов, покрывающую элементарную конъюнкцию, которая соответствует второму столбцу мы ни подобрали, этой совокупностью автоматически будет покрываться и конъюнкция, соответствующая первому столбцу;
3) строки, не содержащие после выполнения п.п. 1) и 2) ни одной отмеченной клетки, также вычеркиваются. Это возможно потому, что все конъюнкции, которые могут быть покрыты данным простым импликантом, уже покрыты другими простыми импликантами, которые должны войти в окончательное выражение для ДНФ;
4) в сокращенной таблице выявляется пара строк, содержащая хотя бы по одной отмеченной клетке в каждом столбце. Простые импликанты, соответствующие этим строкам, добавляются к ДНФ;
5). Если оказывается несколько вариантов выполнения п. 4) , то все они сравниваются и выбирается простейший вариант.
Пример. Минимизировать функцию f (x1, x2, x3, x4) = x1x2x4 ٧ x2x3x4 ٧x1x2x3 ٧x1x2x4 . В результате развертывания элементарных конъюнкций получим:

45720988695003556038163500 x1x2x3x4,
x1x2x3x4,
x1x2x3x4,
x1x2x3x4,
x1x2x3x4,
x1x2x3x4,
x1x2x3x4,
x1x2x3x4. После
приведения
подобных
слагаемых: 1) x1x2x3x4,
2) x1x2x3x4,
3)x1x2x3x4,
4)x1x2x3x4,
5)x1x2x3x4,
6)x1x2x3x4.
После склеивания
получим: 1) x1x2x4 (1,2),
2) x2x3x4 (1,3),
3)x1xЗx4 (3,4),
4)x1x2x3 (4,5),
5)x1x2x4 (5,6).
Импликантная таблица представлена в таблице 3.7.
Таблица 3.7 - Импликантная таблица
x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4
-374651079500x1x2x46046470165100051320701651000 X X x2x3x4 X X x1xЗx4 X X x1x2x3 X X x1x2x4 X X
Вычеркивая строки и столбцы, соответствующие обязательным импликантам x1x2x4 иx1x2x4, получим упрощенную импликантную таблицу (табл. 3.8).
Таблица 3.8 - Упрощенная импликантная таблица
x1x2x3x4 x1x2x3x4
x2x3x4 X x1xЗx4 X X
x1x2x3 X
Из упрощенной таблицы видно, что простой импликант x1xЗx4 по-крывает обе оставшиеся конъюнкции. Теперь можно окончательно записать минимальную ДНФ для функции f (x1, x2, x3, x4):
f (x1, x2, x3, x4) = x1x2x4 ٧x1x2x4 ٧ x1xЗx4.
Для уменьшения количества проверок на возможность склеивания целесообразно все элементарные конъюнкции, содержащие одинаковое число букв, сгруппировать по признаку одинакового количества инвертированных (или не инвертированных) букв. Тогда проверять можно только элементы двух соседних групп. Метод Квайна с таким усовершенствованием называется методом Квайна-Мак-Класки.
3.6 Автоматные описания14605546100x2
xq
yp
y2
y1
x1
Рис. 3.1 – Модель черного ящика
00x2
xq
yp
y2
y1
x1
Рис. 3.1 – Модель черного ящика
При разработке системы управления некоторым объектом необходимым этапом является формализация функционирования будущего устройства. Рассмотрим три вида описаний, относящихся к типу автоматных.
Будем представлять будущее устройство в виде «черного ящика» (рис. 3.1), у которого есть входы x1, x2,...,xq и выходы y1, y2, ...,yp и «что-то внутри». Внутреннее содержание «черного ящика» нам не известно, но его функционирование мы можем описывать с помощью внутренних состояний будущего устройства. Точное число входов и выходов системы управления известно, так как каждый вход ее есть выход некоторого датчика, установленного на объекте управления или на пульте управления (в этом случае датчиком является человек-оператор), а каждый выход ее есть вход некоторого исполнительного механизма на объекте управления или индикатора сигнализации на пульте.
Разработчику известно смысловое значение всех входов xi и выходов yj. Часто на практике xi и yj принимают двоичные значения, например, xi - «включено», «выключено»; yj - «включить», «выключить». Сигнал по входу или по выходу может быть и недвоичным, но дискретным. Например, датчик температуры показывает три уровня: 1) ниже - 5oC; 2) от -5oС до +5oС; 3) выше +5oС. В этом случае вместо одного входа x от датчика температуры введем два: xi׳ и xi״. При этом возможны четыре комбинации двоичных значений на этих входах: 00, 01, 10, 11. Три из них можно сопоставить трем сигналам от датчика температуры.
Будем обозначать через Xi набор значений входных сигналов и Yj набор значений выходных сигналов. Если, например, устройство имеет три входа и в некоторый момент времени x1 = 1, x2 = 0, x3 = 0, то двоичный номер этого набора есть 100. Таким образом, этому набору соответствует вход X4.
Составим теперь таблицу, в левой части которой перечислены все входные наборы, а в правой соответствующие им выходные наборы. Если устройство управления имеет q входов и p выходов, то таблица будет содержать 2q строк, а в правой ее части будут перечислены выходы из 2p возможных. Заметим, что заполнить такую таблицу можно только тогда, когда каждый набор Xi однозначно определяет набор Yj. Если это так, то говорят, что система управления представляет собой комбинационную схему (автомат без памяти). Сама таблица называется автоматной таблицей и дает автоматное описание системы управления.
Приведем пример составления автоматной таблицы. Пусть необходимо спроектировать следующую систему управления. Кондиционер малой мощности должен включаться, если температура воздуха в помещении достигнет +10oС и выключаться, когда температура достигнет +22oС. После этого должен включиться мощный кондиционер. Если же температура достигнет +30oС, необходимо включить оба кондиционера. Наконец если температура достигнет значения +35oС, необходимо выдать аварийный сигнал.
Исходя из условий задачи, можно считать, что проектируемое устройство имеет один вход, принимающий пять значений:
1) to < 10oC;
+10oC to < +22oC;
+22oC to < +30oC;
+30oC to < +35;
to 35oC.
Для перехода к двоичным входным сигналам введем три входа: x1, x2, x3. На них можно реализовать 8 различных двоичных комбинаций. Выберем любые пять из них (например, 000, 001, 010, 011, 100) и закодируем ими упомянутые показания датчика температуры.
Выходами устройства управления являются три двоичных сигнала: y1, y2, y3. Значение y1 = 1 соответствует включению кондиционера малой мощности, y1 = 0 отключению этого кондиционера, y2 = 1 включению кондиционера большой мощности, y2 = 0 его отключению, y3 = 1 соответствует включению сигнала аварии, y3 = 0 отсутствию этого сигнала. Теперь можно составить автоматную таблицу (табл. 3.9). Эта таблица имеет две особенности: 1) в правой части не заполнены три последние строки; 2) для набора X4 не определен однозначно выходной набор.
Таблица 3.9 - Автоматная таблица
Входы Выходы
x1 x2 x3 y1 y2 y3
0 0 0 0 0 0
0 0 1 1 0 0
0 1 0 0 1 0
0 1 1 1 1 0
1 0 0 ? ? 1
1 0 1 1 1 0 1 1 1
Действительно, входные наборы 101, 100, 111 не соответствуют никакому сигналу от датчика температуры и никогда не появляются на входе системы управления. Такие наборы входов называются неиспользуемыми (о том, как заполнять таблицу в этом случае, скажем позднее). Кроме того, из задания неясно, что делать с кондиционерами, если температура стала аварийной (входной набор 100): оставить включенными (соответствующий выходной набор 111), отключить (выходной набор 001), либо оставить включенным один из них (выходные наборы 101, 011). После уточнения этого вопроса (с заказчиком) неоднозначность должна быть устранена.
Возможна ситуация, когда разработчику не удается составить таблицу так, чтобы каждому входному набору в ней соответствовал единственный выходной набор. В этом случае мы имеем дело с автоматом с памятью. Так, для нашего примера на вопрос разработчика о том, что нужно выдавать при входном наборе 100, заказчик может ответить, что это зависит от состояния исполнительных механизмов в момент возникновения аварийной ситуации. Если кондиционеры были включены, то следует оставить их включенными, а если они не были включены, то включать их не следует. При таком ответе неоднозначность в таблице устранить не удастся. Есть два способа выхода из положения:
1) увеличить число входов системы управления, дополнив их сигналами датчиков, регистрирующих состояние каждого кондиционера;
2) в системе управления организовать память, в которой будут фиксироваться действия, которые она формировала в прошлом. Формально это означает введение множества внутренних состояний системы. Обозначим это множество Z = {z0, z1,...,zk}. Среди элементов множества Z выделим начальное состояние объекта z0. В каждой конкретной задаче начальное состояние связывается с некоторым фиксированным состоянием объекта.
-78740670560010
001
011
000
010
011
000
001
000
100
001
100
010
100
011
100
000
001
010
011
Z1
Z0
Z3
Z2
Рис. 3.2 – Граф переходов
00010
001
011
000
010
011
000
001
000
100
001
100
010
100
011
100
000
001
010
011
Z1
Z0
Z3
Z2
Рис. 3.2 – Граф переходов
В нашем примере с кондиционерами множество внутренних состояний Z = {z0, z1, z2, z3}. Начальное состояние z0 соответствует ситуации, когда оба кондиционера выключены, z1 включенному кондиционеру малой мощности и выключенному кондиционеру большой мощности, z2 включенному кондиционеру большой мощности и выключенному кондиционеру малой мощности, z3 состояние, когда оба кондиционера включены.
Построим граф переходов рассматриваемого ав-томата с памятью. Вершинами графа являются состояния z0, z1, z2, z3, дуги соответствуют переходам из одного состояния в другое. Каждая дуга помечается входным набором, при котором осуществляется соответствующий переход (рис. 3.2). Петлям графа соответствуют два набора, что следует из условий задачи и уточнений заказчика.
Информацию о смене состояний можно представить в виде так называемой таблицы переходов (для нашего примера это табл. 3.10). На пересечении строк и столбцов этой таблицы стоят внутренние состояния, в которые переходит система при данной комбинации внутреннего состояния и входного набора.
Таблица 3.10 – Таблица переходов
Состояния Входы
000 001 010 011 100
Z0 Z0 Z1 Z2 Z3 Z0
Z1 Z0 Z1 Z2 Z3 Z1
Z2 Z0 Z1 Z2 Z3 Z2
Z3 Z0 Z1 Z2 Z3 Z3
Таблица переходов еще не содержит полной информации о работе системы управления: необходимо указать, как формируются выходные наборы, подаваемые системой управления на объект. Для этого таблицу или граф переходов нужно дополнить таблицей выходов. В случае нашего примера она имеет вид табл. 3.11.
Таблица 3.11 – Таблица выходов
Состояния Входы
000 001 010 011 100
Z0 000 100 010 110 001
Z1 000 100 010 110 101
Z2 000 100 010 110 011
Z3 000 100 010 110 111
В отличие от таблицы переходов, на пересечении строк и столбцов таблицы выходов указаны выходные наборы, формируемые системой управления.
Таблицы переходов и выходов называются автоматными таблицами. Задание таких таблиц является одной из форм автоматного описания системы управления.
Если на дугах графа переходов выписать еще и выходные наборы, соответствующие входному набору и внутреннему состоянию, из которого эта дуга выходит, то мы получим полное задание системы управления. Такой граф называется автоматным графом и дает еще одно автоматное описание, эквивалентное табличному. Однако каждая из этих форм автоматного описания имеет свои преимущества. Таблицы дают возможность осуществить формальный переход к структуре системы управления. С другой стороны, автоматный граф позволяет судить о том, полно ли сформулированы условия функционирования системы управления и нет ли противоречий в формулировке задания. Неполнота задания проявляется в наличии в графе вершин, из которых при некоторых входных наборах не указаны дуги переходов. Противоречивость может выявляться либо в наличии двух одинаково помеченных дуг, ведущих из одной вершины в разные, либо в том, что одной и той же дуге и входному набору сопоставляется более одного выходного набора.
3.7 Синтез комбинационных схемС помощью аппарата булевых функций можно получить наиболее компактное автоматное описание системы управления. Кроме того, этот аппарат может быть эффективно использован при переходе от автоматного описания к структурной реализации системы управления. Приведем одну из методик синтеза комбинационной схемы с одним выходом, основанную на исходном представлении в виде совокупности таблиц истинности булевых функций. Для полноты изложения перечислим все этапы проектирования, хотя некоторые из них уже были рассмотрены ранее.
Первый этап. 1. По заданному в техническом задании алгоритму выделяем независимые аргументы (входы) и выписываем все их комбинации (входные наборы). При большом количестве входов следует попытаться объединить их или реализовать устройство по частям.
2. Отмечаем запрещенные наборы, т.е. комбинации входных сигналов, которые не могут возникнуть.
3. Выписываем все значения выхода для каждого незапрещенного набора. При этом нужно проверить, зависит ли это значение только от комбинации входов, или еще и от последовательности их появления в каждой комбинации. В первом случае получим таблицу истинности. Во втором случае делаем вывод о том, что заданный алгоритм нельзя реализовать с помощью комбинационного устройства.
4.Доопределяем таблицу на запрещенных наборах, пользуясь информацией, имеющейся в алгоритме, либо руководствуясь следующим (не всегда наилучшим) соображением: если в таблице больше единичных значений выхода, чем нулевых, она доопределяется единичными значениями и наоборот.
5. Записываем аналитическое выражение выхода как булевой функции входов в совершенной ДНФ, если единичных значений выхода в таблице меньше, и в совершенной КНФ - в противном случае.
Второй этап. 6. Упрощаем полученное выражение. Для этой цели можно либо использовать известные методы минимизации булевых функций, дающее минимально возможное в некотором смысле выражение, либо применить систему эквивалентных преобразований. Дополним уже знакомые нам эквивалентные преобразования следующими соотношениями:
(x1 ٧ x2) (x2 ٧ x3) (x3 ٧x1) = (x1 ٧ x2) (x3 ٧x1),
x1x2 ٧ x2x3 ٧ x3x1 = x1x2 ٧ x3x1,
(x1, x2,...,xn) = x1 (1, x2,...,xn) ٧x1 (0, x2,...,xn),
(x1, x2,...,xn) = (x1 ٧ (0, x2,...,xn)) (x1 ٧ (1, x2,...,xn)),
x1 (x1 , x2,...,xn) = x1 (1, x2,...,xn),
x1 ٧ (x1, x2,...,xn) = x1 ٧ (0, x2,...,xn),
x1 (x1, x2,...,xn) = x1 (0, x2,...,xn),
x1 ٧ (x1, x2,...,xn) = x1 ٧ (1, x2,...,xn).
Эффект применения эквивалентных преобразований зависит от последовательности их применения. Наиболее важными являются склеивание xi ٧xi = 1 и поглощение xi ٧ xixj = xi. К сожалению, нельзя указать такой порядок применения эквивалентных преобразований, который обеспечивал бы наиболее простую форму записи булевой функции.
Третий этап. 7. Пользуясь таблицами, имеющимися в литературе, преобразуем полученные на втором этапе выражения в такие, логические операции которых соответствуют выбранному функционально полному набору элементов. При этом следует иметь в виду, что в новом базисе минимальность выражения не гарантируется.
8. Выбираем обозначение для каждой логической операции, реализуемой элементами данного набора. Существуют стандартные изображения базисных функций как некоторых блоков, техническая реализация которых может быть основана на использовании различных физических явлений: магнитных, явлений в полупроводниках и т.д. Примеры таких символических обозначений представлены в таблице 3.12.
Таблица 3.12 – Логические элементы и их обозначения
Элемент
Дизъюнкция
x1 ٧ x2 Конъюнкция
x1 ∙ x2 Отрицание
x Импликация
x1 x2 Эквивалентность
x1 ~ x2 Сложение по mod 2
x1 x2
409575223520x1
x2
x1
x2
x
x1
x2
x1
x2
x1
x2
1

1
1
=
M2
00x1
x2
x1
x2
x
x1
x2
x1
x2
x1
x2
1

1
1
=
M2
Обозначение542544027178000


1274445603885009. По аналитическому выражению строим логическую схему. При этом необходимо соблюдать очередность, раскрывая выражение «изнутри наружу». Полученная в результате логическая схема может оказаться избыточной. Например, пусть имеем минимальное выражение булевой функции y = (x1 ٧ x2) x3 ٧ (x1 ٧ x2) x4. Переходя к логической схеме, получим шесть элементов, причем два из них реализуют функцию x1 ٧ x2. Поэтому нужно постараться упростить логическую схему, находя общие части выражения и объединяя их в схеме. Для нашего примера окончательно получим схему, изображенную на рис. 3.3.
Четвертый этап. 10. От логической схемы выражения, описывающего работу системы управления, можно непосредственно перейти к принципиальной схеме устройства, так как каждому условному изображению функции на логической схеме соответствует физический элемент, реализующий данную операцию и имеющий несколько вариантов принципиальной схемы в зависимости от элементной базы. Соединения между элементами задаются связями на логической схеме.
74168071755x1
x2
x3
y
x4
1
&
1
&
1
Рис. 3.3 – Логическая схема
00x1
x2
x3
y
x4
1
&
1
&
1
Рис. 3.3 – Логическая схема
3.8 Логика предикатов3.8.1 Предикаты и операции квантированияРазвитием уже знакомой нам алгебры высказываний является логика предикатов, Это тоже логическая система или определенный язык описания знаний. В логике предикатов наряду с высказываниями рассматриваются некоторые высказывательные функции, называемые предикатами.
Рассмотрим вначале некоторые примеры:
1) «x простое число». Это выражение не является высказыванием, пока мы не заменим переменную x на какое-либо определенное число. При x = 1 получим истинное высказывание, при x = 6 ложное. Таким образом, выражение «x простое число» есть некоторая функция P (x), зависящая от переменной x. Область определения P (x) множество чисел, область значений P (x) высказывания;
2) «x больше y». Это выражение можно рассматривать как функцию Q (x, y), зависящую от переменных x и y. Она становится высказыванием после того, как x и y заменим их значениями.
В общем случае под предикатом от n переменных понимается выражение P(x1, x2,.., xn), которое становится высказыванием после подстановки вместо переменных x1, x2,.., xn их значений из множеств
M1, M2,..., Mn соответственно. Элементы этих множеств называются предметами, а переменные x1, x2,.., xn предметными переменными. Множество M1 M2 … Mn (декартово произведение) упорядоченных наборов длины n называется полем предиката P (x1, x2,.., xn). Если число предметных переменных равно нулю, то предикат есть высказывание.
Будем обозначать:
x, y, z,.., x1, x2, x3,... (малые буквы конца латинского алфавита) предметные переменные;
a, b, c,.., a1, a2, a3,... (малые буквы начала латинского алфавита) предметы из множеств M1, M2,.., Mn;
A (x, x), B, F (x, y), P (x1, x2,.., xn) предикаты. Символы 0,1 ,как и прежде, обозначают истину и ложь.
К предикатам можно применять операции алгебры высказываний (конъюнкцию, дизъюнкцию, импликацию, эквивалентность, отрицание) и получать новые предикаты. Это действительно так: заменяя предметные переменные в предикатах их значениями из некоторого множества предметов, мы получим высказывания истинные или ложные, а применяя к ним операции логики высказываний, получим новые высказывания.
Пусть, например, «х = у» предикат A (х, у), а «х < у» предикат В (х, у). Тогда
A (x, y) ٧ B (x, y)
новый предикат, полученный применением операции дизъюнкции.
Помимо операций алгебры высказываний в логике предикатов есть две специфические операции, связанные с природой предикатов.
Пусть дан предикат P (x), зависящий от одной переменной и определенный на поле М.
Выражение x P (x) («для всякого х, Р (х)») означает высказывание, истинное только в том случае, когда предикат Р (х) истинен для всех предметов из поля М. Здесь символ квантор общности.
Выражение x P (x) («существует х, что Р (х)») означает высказывание, истинное только в том случае, когда предикат Р (х) истинен хотя бы для одного предмета из поля М; символ квантор существования.
Эти две операции называются операциями квантирования. Рассмотрим примеры применения операций квантирования. Пусть даны предикаты над по лем натуральных чисел:
1) x2 = xx, тогда x (x2 = xx) истинное высказывание;
2) x + 2 = 7, тогда x (x + 2 = 7) ложное;
x (x + 2 = 7) истинное;
3) x + 2 = x, тогда x (x + 2 = x) ложное.
Операции квантирования легко обобщаются на случай, когда предикат зависит от n переменных. Пусть G (x1, x2,.., xn) предикат от переменных x1, x2,.., xn над полем М = M1 M2 .. Mn. Подставим вместо переменных x1,.., xi-1, xi+1,.., xn предметы a1,.., ai-1, ai+1,.., an из множеств M1,.., Mi-1, Mi+1,.., Mn. Получим предикат G (a1,.., ai-1, ai+1,.., an), зависящий только от одной переменной xi. Следовательно, выражение
xi G (a1,.., ai-1, xi, ai+1,.., an)
есть высказывание. Отсюда выражение
xi G(x1,.., xi-1, xi, xi+1,.., xn)
есть предикат от n-1 переменной. Он не зависит от xi. Значение его для данного набора (a1,.., ai-1, ai+1,.., an) равно истине, если предикат G (a1,.., ai-1, xi, ai+1,.., an) истинен для всякого предмета xi из поля М.
Аналогичные рассуждения можно провести для квантора . С помощью операций конъюнкции, дизъюнкции, импликации, эквивалентности, отрицания, а также операций квантирования можно получать более сложные предикаты. При этом предметные переменные, по отношению к которым применялись операции квантирования, называются связанными а остальные свободными.
Например, в предикате
x (A (x, y) ٧ z B (z, v))
переменные x, z- связанные, y, v- свободные.
Мы рассмотрели предикаты, значения которых (истина или ложь) известны для каждого набора значений свободных предметных переменных. Такие предикаты называются определенными предикатами. Но существуют еще так называемые переменные предикаты, для которых значения не определены. Будем обозначать переменные предикаты большими буквами латинского алфавита:
X, Y,.., X1, X2,.., W(x1, x2,.., xn), V(x1, x2,.., xn), …
Переменный предикат от нуля переменных есть переменное высказывание. Применяя к переменным предикатам операции ٧ , ٨ , , ‾, ~, , , получим формулы логики предикатов. Так, выражение
x W (x, y) ٧ x U (z)
– пример формулы логики предикатов.
3.8.2 Равносильные формулы логики предикатовРассматривая формулы логики предикатов над полем М можно говорить о формулах, равносильных над данным полем, то есть о таких формулах, которые принимают одно и то же значение при замене всех свободных предметных переменных предметами и всех переменных предикатов определенными.
Пример. Рассмотрим формулы x W (x) и x W (x) над полями
М1 = {a} и М2 = {a, b}.
Пусть x W (x) и x W (x) даны над полем М1, Значениями переменного предиката W (x) могут быть два определенных предиката A(x) и B(x) (табл. 3.13). Составим истинностную таблицу формул (табл. 3.14).
Таким образом, формулы x W (x) и x W (x) равносильны над полем M1.
Таблица 3.13 – Предикаты над М1 Таблица 3.14 – Равносильность над М1
x A (x) B (x) W (x) x W (x) x W (x)
a 0 1 A (x) 0 0
B (x) 1 1
Пусть теперь формулы x W (x) и x W (x) даны над полем М2. В качестве значений переменного предиката W (x) нужно взять определенные предикаты над полем М2. Таких предикатов существует четыре (табл.3.15). Составив истинностную таблицу формул x W (x) и x W (x) (табл.3.16), убеждаемся в их неравносильности над полем М2.
Таблица 3.15- Предикаты над М2 Таблица 3.1- Неравносильность над М2
x I1 (x) I2 (x) I3 (x) I4 (x) W (x) x W (x) x W (x)
I1 (x) 0 0
a 0 0 1 1 I2 (x) 0 1
I3 (x) 0 1
b 0 1 0 1 I4 (x) 1 1
Формулы логики предикатов называются равносильными, если они равносильны над любым полем.
Примеры равносильных формул:
5003801524000x W (x) и x W (x);читается: «высказывание не верно, что для любого х А(х) истинно» эквивалентно высказыванию «найдется х, для которого А(х) ложно»
x W (x) и x W (x);
x W (x) и x W (x);
x W (x) и x W (x).
2421255106680000-571510668000038176206096000020891507677150078422545593000Докажем равносильность первой пары формул. Пусть М – произвольное поле, а A (x) – некоторый определенный предикат над ним. Подставим вместо переменного предиката W (x) определенный предикат A (x). Пусть высказывание x A (x) истинное, тогда высказывание x A(x) ложно. Следовательно, существует предмет a из поля M, что A (a) ложно, тогда A (a) – истинно. Значит, высказывание x A (x) истинно. Аналогичными рассуждениями получим, что из предположения ложности высказывания x A (x) следует ложность высказывания x A (x).
Среди всех формул логики предикатов можно выделить формулы, истинные над любым полем, их называют тождественно-истинными. Например, формула x W(x) x W(x) является тождественно-истинной.
В общем случае выяснить вопрос, является ли данная формула тождественно-истинной, сложно, так как приходится использовать понятие бесконечности.
3.9 Задачи и упражненияДано высказывание А: «Существуют четные простые числа». Определите, истинно оно или ложно. Укажите среди следующих высказываний отрицание высказывания А: а) «Существуют нечетные простые числа»; б) «Неверно, что существуют четные простые числа»; в) «Любое простое число нечетно».
Для высказывания А: «Любые два треугольника подобны» сформулируйте отрицание и двойное отрицание. Какие из этих трех высказываний истинны?
197167546101000Даны высказывания «Я купил велосипед» (А); «Я путешествовал по России» (В) и «Я участвовал в соревнованиях по велосипеду» (С). Сформулируйте высказывания, соответствующие формулам: А ٨ В, А ٨ В ٨ С, А ٨С, А ٨ В, В ٨С.
Даны высказывания «Четырехугольник MNPQ – параллелограмм» (А) и «Диагонали четырехугольника MNPQ в точке пересечения делятся пополам» (В). Сформулируйте высказывания, соответствующие формулам А В, В А, А, В, А В, В А.
Составьте таблицы истинности для следующих формул: X (Y ٧ Z), (X Y) ٧ (X Z).
Покажите, что формулы X ٨Y Y ٨ X, X ٧YY ٧X, ((X Y) ٨ X) Y являются тавтологиями.
56515047498000Докажите равносильность формул: а) X ٨ (Y ٧ Z) и (X ٨ Y) ٧ (X ٨ Z); б) X ٧ (Y ٨ Z) и (X ٧ Y) ٨ (X ٧ Z); в) X ٧ Y иX ٨Y; г) X ٨ Y иX ٧Y; д) X (Y Z) и (X ٨ Y) Z; е) (X Y) ٨ (X Z) и X (Y ٨ Z).
Постройте совершенные ДНФ и КНФ функций: x1 x2, x1 x2, x1 x2, x1 x2.
Запишите в совершенных ДНФ и КНФ булеву функцию f1 (x1, x2, x3), принимающую значение 1 на наборах с номерами 0, 3, 7. Определите, к каким классам функций относится эта функция.
Проверьте справедливость равенств: x =x 1, x1 x2 = x1 ٧ x2.
Составьте таблицу свойств булевых функций двух переменных. Из таблицы выпишите все полные системы булевых функций.
Проверьте линейность булевой функции f2 (x1, x2, x3), принимающей значение 1 на наборах с номерами 0, 1, 5, 6.
Синтезируйте логические схемы булевых функций из задач № 9, 12 в базисах: а) { ٧, }; б) { ٨, }.
Найдите минимальную ДНФ функции f (x1, x2, x3, x4), принимающей значение 1 на наборах с номерами 0, 1, 2, 5, 6. 7, 8, 12, 13.
Приведите примеры: а) монотонной функции, которая одновременно была бы линейной; б) самодвойственной функции, которая одновременно была бы линейной; в) линейной и монотонной функций.
Покажите, что функции Шеффера и Вебба не являются ни линейными, ни монотонными, ни самодвойственными.
Докажите полноту системы булевых функций, состоящей из дизъюнкции, константы 0 и эквивалентности.
Путешественник попал к людоедам. Они разрешают ему произнести какое-нибудь высказывание и ставят условие, что если его высказывание будет истинным, то его сварят, а если ложным, то зажарят. Какое высказывание следует произнести путешественнику, чтобы избежать гибели?
Список литературыКориков А.М., Сафьянова Е.Н. Основы системного анализа и теории систем: Учебное пособие. – Томск: изд-во Том. ун-та, 1989. – 207 с.
Оре О. Теория графов. – М.: Наука, 1980. – 352 с.
Основы кибернетики. Математические основы кибернетики / Под. ред. К.А. Пупкова. – М.: Высш. школа, 1974. – 416 с.
Горбатов В.А. Основы дискретной математики. – М.: Высш. школа, 1986. – 312 с.
Кристофидес Н. Теория графов. Алгоритмический подход. – М.: Мир, 1978. – 432 с.
Кузин Л.Т. Основы кибернетики.: В 2 т. Т.2. Основы кибернетических моделей. – М.: Энергия, 1979. – 584 с.
Шевелев Ю.П. Высшая математика 5. Дискретная математика. Ч.1: Теория множеств. Булева алгебра (для автоматизированной технологии обучения): Учебное пособие. – Томск: Том. гос. ун-т систем управления и радиоэлектроники, 1998. – 114 с.

Приложенные файлы

  • docx 8884712
    Размер файла: 1 MB Загрузок: 0

Добавить комментарий