Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Федеральное агентство по образованию
Государственное образовательное учреждение
высшего профессионального образования
Санкт-Петербургский государственный технологический институт (технический университет)
Кафедра менеджмента высоких технологий
В.И. Халимон, А.Ю. Рогов, О.В. Проститенко
Дискретная математика
(Операции на графах, булева алгебра)
Учебное пособие
Санкт-Петербург
2009
УДК 519.45
Дискретная математика: учебное пособие В.И. Халимон, А.Ю. Рогов, О.В. Проститенко - СПб.: СПбГТИ(ТУ), 2009.- 48 с.
Учебное пособие посвящено изучению разделов: «Теория графов», «Булевая алгебра» и «Представление функций алгебры логики в виде схем из функциональных элементов» входящих в стандартную программу учебной дисциплины «Дискретная математика». Понятия и методы этих теорий широко используются в различных разделах учебных дисциплин.
В пособии даются базовые понятия из теории графов, булевой алгебры, приводится обзор различных задач и методов их решения, и рассматриваются практические примеры.
Учебное пособие составлено в соответствии с учебной программой дисциплины «Дискретная математика». В учебное пособие включены задания для контрольных работ и примеры их решения.
Учебное пособие предназначено для студентов второго курса, обучающихся по специальностям 22.07.01 "Менеджмент высоких технологий" и 23.01.00 "Информатика и вычислительная техника", а также для слушателей факультета переподготовки кадров по новым направлениям науки и техники.
Рис. 29, табл. 5, формул 7, библиогр. 10 назв.
Рецензенты:
1 В.Г. Харазов, д-р техн. наук, профессор по кафедре АПХП СПбГТИ(ТУ)
Утверждено на заседании учебно-методической комиссии факультета Информатики и Управления 22.12.2008.
Рекомендовано к изданию РИСо СПбГТИ(ТУ)
ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ……………………………………………………………………………………….... 4
1 КОНТРОЛЬНАЯ РАБОТА №1…………………………………………………………………. 5
2 КОНТРОЛЬНАЯ РАБОТА №2…………………………………………………………………. 31
3 КОНТРОЛЬНАЯ РАБОТА №3….……………………………………………………………… 42
4 ЛИТЕРАТУРА…………………………………………………………………………………... 47
ВВЕДЕНИЕ
Целью дисциплины «Дискретная математика» является изучение и освоение методов дискретной математики, и формирование практических навыков разработки и анализа алгоритмов над объектами дискретной математики.
Настоящее пособие представляет собой руководство к выполнению лабораторно-практических работ по дискретной математике.
Пособие позволяет выдавать индивидуальное задание каждому учащемуся. Все задания имеют одинаковую степень сложности.
Весь материал разбит на главы, в которых дается набор работ по соответствующей теме. Каждая работа начинается с задания, которое одинаково для любого из вариантов. В конце работы приводится образец ее выполнения.
Студент самостоятельно выбирает вариант контрольной работы в соответствии с начальной буквой фамилии или получает вариант от преподавателя в индивидуальном порядке.
|
Буква |
А |
Б |
В |
Г |
Д |
Е Ё |
Ж |
З |
И Й |
К |
Л |
М |
Н |
О |
П |
|
№ варианта |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
|
Буква |
Р |
С |
Т |
У |
Ф |
Х |
Ц Ю |
Ч |
Ш Щ |
Э Я |
|
№ варианта |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
Изучение основ теории графов, базовых понятий и определений; ознакомление с задачами, возникающими в теории графов и методами их решения.
ОСНОВНЫЕ ПОЛОЖЕНИЯ
ГРАФОВЫЕ МОДЕЛИ, МЕТОДЫ ПРЕДСТАВЛЕНИЯ ГРАФОВ
Граф G представляет собой двойку вида: G = ( X , U ), где X — множество вершин графа; U — множество ребер графа.
Множество вершин обычно представляет собой множество элементов системы, а множество ребер — связи между элементами системы или отношения элементов. Пусть множество X имеет размерность N, а множество U — размерность Q. Понятие графа опирается на понятие инцидентности. Если некоторому элементу из множества U сопоставлен элемент из множества X, то говорят, что некоторое ребро u инцидентно вершине x. Данное сопоставление может быть единственным, т.е. данному ребру u может быть сопоставлена вершина x только один раз, и множественным, т.е. данному ребру вершина сопоставляется несколько раз. В зависимости от того, сколько вершин сопоставлено ребру и сколько раз производится сопоставление, графы делятся на обычные графы, мультиграфы, гиперграфы и мультигиперграфы.
При изучении взаимосвязей между объектами исследуемая система представляется в виде графа. Для построения графа системы достаточно знать состав элементов и связи между ними. Топологический анализ проходит в несколько этапов:
анализ элементов;
анализ путей и контуров в системе;
анализ связанности структуры;
определение обобщенных структурных характеристик системы;
оценка быстродействия;
проверка достижимости элементов;
анализ надежности;
определение степени централизации элементов.
Графы можно задавать: матрицей смежности, матрицей инциденций, списком дуг, списком окрестностей вершин графа. Пусть дан граф G = (X , U), где X — множество вершин графа, а U — множество связей в графе, и пусть P — число вершин графа, Q — число связей в графе. Рассмотрим базовые представления графов наследующем примере (P=13, Q=16):
Рисунок 1. Пример графа
Матрицей смежности графа называется матрица V, имеющая размерность P*P, каждый элемент которой определяется следующим образом:
1 , если между i-ой вершиной и j-ой
V(i,j) = вершиной есть дуга ; (1)
0 , в противном случае.
Если на главной диагонали этой матрицы стоит единица, то это соответствует наличию петли в графе. Для графа представленного на рис. 1 представление имеет вид (см. рис. 2)
Рисунок 2. Матрица смежности графа
Данное представление является очень удобным и широко используемым на практике. Однако, в случае, когда Q < P*P это представление является не экономичным, поскольку требует много памяти для хранения нулей.
Матрицей инциденций графа называется матрица W, имеющая размерность P*Q, каждый элемент которой определяется следующим образом:
-1, если i-ая вершина — начало j-ой дуги;
W(i,j) = 1, если i-ая вершина — конец j-ой дуги; (2)
0, в остальных случаях.
В неориентированном графе каждое ребро представляется как две противоположно направленные дуги. Для графа представленного на рис.1 представление имеет вид (см. рис.3):
Рисунок 3. Матрица инциденций графа
Это представление также является не экономичным, поскольку требует много памяти для хранения нулей. Задание графа списком дуг включает массивы IU и OU. Оба массива имеют размерность Q для ориентированного графа и 2Q для неориентированного графа. Массив IU хранит номера вершин, являющихся началом дуг, а массив OU — концы дуг. Для I-ых элементов массивов IU и OU, т.е. для I-ой дуги, справедливо:
IU[i] — начало дуги,
OU[i] — конец дуги.
В неориентированном графе каждое ребро представляется как две противоположно направленные дуги. Для графа представленного на рис.1 представление имеет вид (см. рис.4):
Рисунок 4. Список дуг графа
Задание графа окрестностью вершин включает массивы FO и KAO. Массив FO имеет размерность Q для ориентированного графа и 2Q для неориентированного графа. В нем хранятся номера вершин, являющихся выходами (входами) дуг. Массив KAO имеет размерность P+1. В нем хранятся номера элементов массива FO, с которых начинается новая окрестность. I-ый элемент KAO хранит номер элемента массива FO, с которого начинается окрестность I-ой вершины графа. В неориентированном графе каждое ребро представляется как две противоположно направленные дуги. Для графа представленного на рис. 1 представление имеет вид (см. рис. 5):
Рисунок 5. Список по выходным дугам
АНАЛИЗ СТРУКТУР СЛОЖНЫХ СИСТЕМ ГРАФОВЫМИ МЕТОДАМИ
Анализ структур сложных систем графовыми методами рассматривается по следующим пунктам:
выявление ошибок в структуре системы;
анализ связей структуры;
анализ быстродействия системы;
анализ надежности системы.
Выявление ошибок в структуре системы
При проектировании сложных систем в проектах могут появляться различные ошибки структурного характера.
Существуют наиболее общие грубые ошибки, свойственные практически всем системам. Наиболее типичные из них следующие:
Рассмотрим эти типичные ошибки. Появление несвязанных элементов является одной из грубых ошибок синтеза системы потому, что элементы включаются в систему для того, чтобы они несли какую-то функцию в ней, взаимодействовали с другими элементами путем передачи потоков энергии, вещества, информации. Если элемент существует в системе сам по себе, не оказывая влияния на другие элементы системы или на внешнюю среду, то для чего такой элемент включается в систему? Выявление несвязанных элементов графовым методом состоит в поиске в графе системы изолированных вершин. Например, для графа, представленного на рис. 1, вершина с номером 13 является изолированной. Вершина с номером 12 хотя и связана, но она связана только сама с собой, что тоже можно рассматривать как ошибку в структуре.
Рисунок 6. Изолированные вершины
Входами системы будем называть элементы, которые получают из внешней среды вещество, энергию, информацию или воспринимают какое-то воздействие. Выходами системы будем называть элементы, которые отдают во внешнюю среду вещество, энергию, информацию или оказывают на нее какое-то воздействие. Несоответствие числа входов системы обычно свидетельствует о том, что в ней имеются какие-то внутренние источники веществ, энергии, информации. Эти источники оказывают определенное воздействие на другие элементы системы и могут вносить различные помехи в работу системы. Несоответствие числа выходов системы обычно свидетельствует о том, что в ней имеются элементы, через которые происходит утечка вещества, энергии, информации. Появление дополнительных выходов может привести к каким-то побочным эффектам в работе системы при взаимодействии ее с внешней средой.
Выявление входов и выходов системы графовым методом состоит в поиске в графе системы антитупиковых и тупиковых вершин соответственно. Например, для графа, представленного на рис. 6, входной вершиной будет только вершина с номером 1 (см. рис. 7), а выходными — 5 и 11 (см. рис. 8).
Рисунок 7. Входная вершина
Рисунок 8. Выходные вершины
Анализ связей структуры (достижимость)
Отсутствие достижимости выходов системы из входов системы обычно свидетельствует о том, что в ней нарушается прохождение потоков вещества, энергии, информации от входов к выходам. Система обычно должна преобразовывать входные воздействия в выходные. Воздействия в системе проходят от входов через элементы системы к ее выходам. Если сигнал не может пройти от определенного входа к выходу системы, а должен проходить, то проектировщик должен найти ошибку. Причиной такой ошибки может быть, например, неправильное соединение элементов. Эта задача в терминах теории графов формулируется как задача проверки достижимости одного множества вершин графа из другого множества вершин, при условии, что эти множества не пересекаются. Например, для графа, представленного на рисунке 8, выходная вершина 11 достижима из входной вершины 1. Вершина 8 достижима из входа 1 и недостижима из вершины 11.
Анализ быстродействия системы
Быстродействие элементов, составляющих систему, определяется по их техническим характеристикам. Определить быстродействие больших систем довольно сложно, поскольку их быстродействие зависит не только от быстродействия элементов, но и от способа соединения элементов, характера связей. Если в систему входят быстродействующие элементы, то это еще не означает, что быстродействие системы в целом будет хорошее. Необходимо проанализировать характер связей между элементами и порядок прохождения сигналов через систему. Этот анализ можно выполнить на графе структурной схемы системы. Известно, что чем короче цепь, по которой сигнал проходит от одного элемента системы к другому, тем меньше времени тратится на передачу данного сигнала и тем выше быстродействие системы. Длину проходимой цепи можно оценивать числом устройств системы, числом связей. Если ввести в граф некоторые технические характеристики самих элементов системы такие, как время прохождения сигнала через элемент, скорость прохождения сигнала, задержка сигнала в элементе, инерционность элемента, то можно провести более точный анализ быстродействия системы.
Таким образом, во многих задачах анализа сложных систем, связанных с повышением быстродействия системы возникает потребность нахождения путей минимальной или максимальной длины. При этом возможны различные постановки задачи: найти кратчайшую (максимальную) цепь между двумя вершинами, найти все кратчайшие цепи между двумя вершинами, найти дерево кратчайших цепей с корнем в заданной вершине и т.д. По числу приложений задача о кратчайшей цепи занимает первое место среди других задач теории графов. Прежде чем перейти к рассмотрению этой задачи необходимо ввести понятие расстояния на графе, т. е. определить метрику графа.
Пусть задан граф G = ( X , U ) и на графе определена функция расстояния d( xi , xj ) между двумя вершинами xi, xj таким образом, что длина цепи между двумя вершинами равна числу дуг, входящих в эту цепь. При таком определении каждой дуге сопоставляется единица условной длины. Под условной единицей можно понимать устройство в системе управления, единицу оборудования в технологической схеме и т. д. Задача нахождения кратчайшего пути формулируется как задача нахождения такого маршрута между вершинами xi и xj, что d(xi,xj)=min. Эта задача связана с нахождением такого пути в системе между двумя заданными элементами, при котором сигнал проходит наименьшее число устройств. Например, для графа системы, представленного на рис. 10, кратчайшим невзвешенным путем будет путь: 1, 2, 8, 11. По этому пути сигналу нужно пройти наименьшее число устройств от входа 1 до выхода 11.
Другой важной задачей является нахождение дерева кратчайших цепей с корнем в заданной вершине. В этой задаче находятся кратчайшие пути из заданной вершины до всех остальных вершин графа. По этим путям сигнал из данной точки системы распространяется быстрее, чем по другим путям. Далее можно определить максимальное и минимальное значение этих путей и, таким образом, оценить скорость передачи сигналов от данного элемента системы.
При решении задач, связанных с повышением быстродействия систем результаты исследования удобно представить некоторыми обобщенными характеристиками графа, которыми являются радиус и диаметр графа. Прежде чем дать определение этим характеристикам необходимо ввести понятие эксцентриситета вершины. Эксцентриситетом вершины называется длина максимального из наикратчайших путей от этой вершины до других вершин графа, т. е.:
e(x) = max (d( x , xi )) , i=1, ... , n, (3)
где e(x) — эксцентриситет вершины x;
d( x, xi ) — расстояние от заданной вершины x
до другой вершины xi графа;
n — число вершин графа.
Разные вершины в графе имеют разный эксцентриситет, поэтому интересно знать верхнее и нижнее значение эксцентриситетов вершин.
Радиусом графа называется минимальный из эксцентриситетов его вершин, т. е.:
R(G) = min ( e(xi) ) , i=1, ... , n, (4)
где R(G) — радиус графа G;
e(xi) — эксцентриситет xi вершины графа;
n — число вершин графа.
Радиус графа дает нижнюю оценку скорости прохождения сигнала в системе. Однако, если R(G)=0, то это означает, что граф содержит вершины-тупики, из которых сигналы не поступают.
Диаметром графа называется максимальный из эксцентриситетов его вершин, т. е.:
D(G) = max ( e(xi) ) , i=1, ... , n , (5)
где D(G) — диаметр графа G;
e(xi) — эксцентриситет xi вершины графа;
n — число вершин графа.
Диаметр графа дает верхнюю оценку скорости прохождения сигнала в системе, т. е. сигнал от произвольной точки системы пройдет меньшее либо равное диаметру число устройств.
С эксцентриситетами вершин связана еще одна графовая задача — задача нахождения вершин графа, эксцентриситет которых равен радиусу или диаметру графа. Такие вершины называются центральными. Центром графа G = (X, U) называется такое подмножество вершин X' из X, что для всех вершин x входящих в X' их эксцентриситет равен радиусу графа, т.е. e(x) = R(G). Если R(G)=0, то это множество вершин-тупиков, т. е. стоков информации, иначе это множество точек системы, от которых сигнал до самой удаленной точки распространяется быстрее, чем от других точек системы. Эти точки лежат как бы в центре системы.
Периферией графа G = (X , U) называется такое подмножество вершин X' из X, что для всех вершин x входящих в X' их эксцентриситет равен диаметру графа, т.е. e(x) =D(G). Это подмножество критических точек системы, от которых сигнал до самой удаленной точки распространяется дольше всего, хотя до некоторых ближних точек сигнал может доходить достаточно быстро (например, смежная точка). Поэтому при повышении быстродействия системы анализ нужно начинать с этих точек.
Рисунок 9. Параметры быстродействия
При данном выше определении расстояния имеется один недостаток. Дело в том, что на практике сигнал через разные устройства распространяется не с одинаковой скоростью. Поэтому естественнее было бы ввести расстояние другим образом. Пусть дан граф G = ( X, U ). Каждой дуге u (вершине x) графа G сопоставим вещественное неотрицательное число w(u)>0 (w(x) > 0), которое называется весом дуги (вершины). Если каждая дуга графа является некоторым устройством в системе, то число w может иметь значение скорости или времени прохождения сигнала через данное устройство. Таким образом, в граф системы включаются технические характеристики элементов системы. Данные выше определения будут сформулированы следующим образом. Длиной маршрута, проходящего через заданные дуги, называется сумма весов дуг, входящих в этот маршрут. Функция расстояния d( x, y ) между двумя вершинами x и y определяется аналогично, как длина цепи c началом в x и концом в y. Задача нахождения кратчайшего пути формулируется как задача нахождения такого маршрута между вершинами x и y, что d(x,y)=min.
Аналогичные определения получаются и для обобщенных характеристик: радиуса, диаметра, центра и периферии. Например, для графа системы, представленного на рис. 10, кратчайший взвешенный путь из входа 1 в выход 11 проходит через вершины: 1, 6, 10, 11:
Кратчайший путь от вершины 1 до вершины 11:
Невзвешенный путь: 3 Взвешенный путь: 25,00
Рисунок 10. Поиск кратчайшего пути
Анализ надежности структуры
Надежность систем рассматривают в трех направлениях:
надежность элементов системы;
надежность структуры системы;
исследование условий функционирования системы.
В теории графов рассматриваются вопросы, связанные со структурной надежностью. Представляя структурную схему системы в виде графа необходимо располагать методикой, позволяющей выделить и определить некоторые структурные параметры и дать им количественную оценку. В качестве параметров, определяющих качество структурной схемы при представлении ее графом, можно рекомендовать следующее:
связанность графа;
ранг элемента;
множество точек сочленения;
независимое подмножество;
полное подмножество (клика).
Связанный граф — это граф, у которого любая пара вершин взаимодостижима. Достижимость некоторой вершины x графа из вершины y означает, что из вершины y существует маршрут в вершину x. Граф связан тогда и только тогда, когда любая пара вершин соединяется маршрутом. Этот параметр должен выявить в структуре наличие обрывов, отсутствие необходимых связей, «узкие» места в системе, слабосвязанные подсистемы, «висячие» вершины. Данный параметр достаточно прост для понимания, однако его оценка включает несколько подзадач. Как видно из определения, понятие связанности включает понятие достижимости. Поэтому необходимо сначала проверить достижимость вершин графа. Это является самостоятельной подзадачей анализа. Для определения достижимости всех вершин графа, т.е. элементов системы, используется матрица непосредственных путей графа.
Результаты проверки достижимости удобно представлять в виде матрицы достижимости Ад графа. Элементы матрицы достижимости строятся следующим образом:
1, если из вершины i к вершине j существует путь;
a ij = (6)
0, в противном случае.
УКАЗАНИЯ
Данная контрольная работа может быть выполнена от руки на листах формата А4 или представлена в распечатанном варианте в результате использования программы «GRAF TOOLBOX». Все примеры в основных положениях к данной работе выполнены в программе «GRAF TOOLBOX».
Перед решением задач контрольной работы рекомендуется ознакомиться со следующими методическими указаниями:
1. Халимон В.И., Рогов А.Ю., Проститенко О.В., Крюков А.В. Использование программного комплекса «Комплекс ГРАФ» для исследования структур сложных систем: Методические указания СПбГТИ(ТУ).- СПб, 2001.- 43 с.
2. Халимон В.И., Рогов А.Ю., Зайцева В.С. Анализ структур сложных систем графовыми методами: Учебное пособие СПбГТИ(ТУ).- СПб, 2001.- 88 с.
3. Нечепуренко М.И. Алгоритмы и программя решения задач на графах и сетях.- Новосибирск: Наука, 1990.- 515 с.
4. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженеров. – М.:Энергия, 1980. – 814 с.
5. Горбатов В.А. Фундаментальные основы дискретной математики. Информационная математика: Учебник для взузов. – М.: Наука.
6. Белоусов А.И., Ткачев С.В. Дискретная математика: Учеб. для вузов/ под. ред. В.С. Зарубина, А.П. Крищенко.- М.: Изд-во МГТУ им. Н.Э.Баумана, 2001. – 744 с
ЗАДАНИЕ: Необходимо изучить теоретический материал учебного пособия и решить следующие задачи:
1.Построить граф, состоящий из Z изолированных компонент мощностью N1,N2,…,NZ и T изолированных вершин. Во всём графе должно быть I истоков, S стоков, V висячих вершин, R регулярных вершин, три из которых имеют степени r1, r2, r3. Максимальная степень кратности дуг графа должна быть K. В графе должно быть не меньше, чем M пар противоположных дуг.
В отчете представить построенный граф с выделением всех построенных элементов. Надписать полустепени исхода и захода для каждой вершины. (1 картинка)
2.Построить ориентированный граф из 7 вершин и 14 дуг, содержащий один исток, один сток, одну изолированную вершину, одну регулярную вершину, одну петлю, пару одинаково направленных дуг, пару противоположно направленных дуг. С истоком и со стоком должно быть связано более двух дуг.
Построить и проанализировать следующие способы представления графов: матрица смежности, матрица инцидентности, матрицы окрестностей вершин по входам и по выходам, список дуг. В отчете представить построенный граф и матричные представления графа с описанием. (1 граф и 5 матриц)
3.Построить связанный граф из N вершин, не содержащий висячих и изолированных вершин, но содержащий T точек сочленения так, чтобы они не были смежны. Рассчитать ранги вершин этого графа.
В отчете представить построенный граф с выделенными точками сочленения и подписанными рангами каждой вершины. (1 картинка)
4.Построить связанный ориентированный граф, содержащий K сильных компонент связанности мощностью N1,N2,…,NK. Свернуть граф по найденным компонентам.
В отчете представить граф, раскрашенный по компонентам и граф-свертку. (2 картинки)
5.Построить связанный ориентированный ациклический непоследова-тельный граф, состоящий из L порядковых уровней мощностью N1,N2,…,NL. Граф содержит N1 истоков и NL стоков. Свернуть граф по найденным уровням.
В отчете представить граф, упорядоченный по уровням слева направо и граф-свертку. (2 картинки)
6.Построить связанный граф из P вершин и Q дуг. Используя метод, описанный в учебном пособии, перечислить все маршруты этого графа длиной 1, 2, 3. В отчете привести граф и выкладки по вычислению матриц. (1 граф и 3 матрицы)
7.Построить связанный ориентированный граф из N вершин, содержащий один исток и один сток, не содержащий петель. Задать веса на дугах графа и пронумеровать все вершины. Между истоком и стоком построить P путей через остальные вершины, длиной больше k-дуг.
Изменяя веса на дугах модифицировать граф так, чтобы кратчайшие пути по сумме весов и по количеству дуг между истоком и стоком не имели ни одной общей дуги (не совпадали). В отчете представить граф с выделенными путями, указать длину путей по весам и по количеству дуг. (1 картинка)
На этом же графе построить исходящее дерево кратчайших путей с корнем в истоке и заходящее дерево кратчайших путей с корнем в стоке. (2 картинки)
8.Построить связанный ориентированный граф имеющий как минимум две центральные вершины, как минимум две периферийные вершины, как минимум две обычные вершины так, чтобы его радиус был не равен нулю и не равен диаметру. Начать построение с 6 вершин, добиться результата добавлением и удалением дуг и вершин. Построить максимальное покрывающее дерево кратчайших путей.
В отчете представить построенный граф с выделенным деревом, центром и периферией, над вершинами надписать их эксцентриситеты, указать значения радиуса и диаметра графа. (1 картинка)
9.Придумать Q свойств некой системы из N элементов. Построить ориентированный граф системы, задать в качестве вспомогательного веса вершин текстовые идентификаторы, а в качестве основного веса – бинарные цепочки (ширина равна количеству свойств). Проставить на вершинах основные веса в виде цепочки нулей и единиц в зависимости от того обладает вершина соответствующим свойством (1) или нет (0). Используя метод «свертка по кодам» выполнить три свертки построенного графа при различных сочетаниях нулей и единиц в маске макро-свойств. В отчете представить описание свойств, описание элементов системы, исходный граф системы с бинарными весами, три графа свертки по трем маскам макросвойств. (1 граф и 3 свертки).
Выполнение почти всех частей данной работы возможно на домашнем персональном компьютере. Для этого необходимо получить разрешение у преподавателя на установку программного обеспечения дома. Запрещается распространение полученных программ или какое-либо коммерческое их использование.
Вариант № 1.
1. T=1 и Z=3 : N1=6, N2=8, N3=9 // I=2, S=3, V=2 // R=4 : r1=2, r2=3, r4=4 K=4 и M>2
2. Матрицы: VV, VU, FO, FI, IO.
3. N=17 и T=4
4. K=5 : N1=2, N2=3, N3=4, N4=5, N5=6
5. L=5 : N1=2, N2=3, N3=4, N4=3, N5=2
6. Перечислить маршруты:
7. N=20 // P>4 и k>4
9. Q=6 и N=12
Вариант № 2.
1. T=1 и Z=4 : N1=2, N2=5, N3=6, N4=7 // I=3, S=3, V=3 // R=4 r1=2,r2=3, r4=4 // K=4 и M>3
2. Матрицы: VV, VU, FO, FI, IO.
3. N=12 и T=3
4. K=5 : N1=4, N2=3, N3=1, N4=5, N5=6
5. L=5 : N1=3, N2=4, N3=2, N4=4, N5=3
6. Перечислить маршруты:
7. N=23 // P>5 и k>4
9. Q=6 и N=14
Вариант № 3.
1. T=2 и Z=4 : N1=3, N2=4, N3=5, N4=6 // I=2, S=2, V=2 // R=5 : r1=3, r2=4, r4=5 // K=5 и M>3
2. Матрицы: VV, VU, FO, FI, IO.
3. N=11 и T=3
4. K=4 : N1=4, N2=5, N3=6, N4=7
5. L=5 : N1=3, N2=1, N3=2, N4=4, N5=2
6. Перечислить маршруты:
7. N=20 // P>4 и k>5
9. Q=7 и N=16
Вариант № 4.
1. T=2 и Z=4 : N1=4, N2=5, N3=6, N4=7 // I=2, S=3, V=3 // R=5 : r1=1, r2=2, r4=3 // K=3 и M>3
2. Матрицы: VV, VU, FO, FI, IO.
3. N=9 и T=2
4. K=4 : N1=3, N2=4, N3=5, N4=6
5. L=5 : N1=3, N2=2, N3=4, N4=2, N5=3
6. Перечислить маршруты:
7. N=20 // P>4 и k>4
9. Q=7 и N=14
Вариант № 5.
1. T=2 и Z=3 : N1=6, N2=7, N3=8 // I=3, S=2, V=3 // R=4 : r1=2, r2=3, r4=4 // K=5 и M>4
2. Матрицы: VV, VU, FO, FI, IO.
3. N=8 и T=2
4. K=5 : N1=3, N2=4, N3=5, N4=6, N5=7
5. L=5 : N1=2, N2=1, N3=4, N4=4, N5=2
6. Перечислить маршруты:
7. N=22 // P>3 и k>6
9. Q=7 и N=15
Вариант № 6.
1. T=3 и Z=3 : N1=5, N2=6, N3=7 // I=2, S=2, V=2 // R=3 : r1=2, r2=3, r4=4 // K=5 и M>3
2. Матрицы: VV, VU, FO, FI, IO.
3. N=18 и T=4
4. K=5 : N1=4, N2=5, N3=6, N4=7, N5=1
5. L=5 : N1=3, N2=4, N3=5, N4=3, N5=2
6. Перечислить маршруты:
7. N=25 // P>5 и k>5
9. Q=6 и N=15
Вариант № 7.
1. T=1 и Z=5 : N1=2, N2=4, N3=5, N4=6, N5=7 // I=4, S=3, V=3 // R=5 : r1=3, r2=4, r4=5 // K=5 и M>4
2. Матрицы: VV, VU, FO, FI, IO.
3. N=14 и T=4
4. K=6 : N1=4, N2=4, N3=3, N4=3, N5=5, N6=5
5. L=5 : N1=1, N2=3, N3=1, N4=2, N5=2
6. Перечислить маршруты:
7. N=25 // P>6 и k>4
9. Q=8 и N=14
Вариант № 8.
1. T=2 и Z=5 : N1=3, N2=4, N3=5, N4=6, N5=7 // I=3, S=4, V=3 // R=5 : r1=2, r2=3, r4=4 // K=4 и M>4
2. Матрицы: VV, VU, FO, FI, IO.
3. N=15 и T=4
4. K=4 : N1=2, N2=3, N3=4, N4=5
5. L=6 : N1=2, N2=2, N3=1, N4=3, N5=3, N6=2
6. Перечислить маршруты:
7. N=23 // P>4 и k>6
9. Q=8 и N=12
Вариант № 9.
1. T=3 и Z=5 : N1=3, N2=5, N3=5, N4=6, N5=6 // I=3, S=3, V=2 // R=4 : r1=3, r2=4, r4=5 // K=5 и M>3
2. Матрицы: VV, VU, FO, FI, IO.
3. N=13 и T=3
4. K=6 : N1=3, N2=3, N3=4, N4=4, N5=5, N6=5
5. L=5 : N1=2, N2=3, N3=4, N4=3, N5=2
6. Перечислить маршруты:
7. N=25 // P>6 и k>4
9. Q=6 и N=13
Вариант № 10.
1. T=3 и Z=5 : N1=2, N2=5, N3=5, N4=7, N5=7 // I=2, S=2, V=2 // R=4 : r1=2, r2=4, r4=6 // K=6 и M>4
2. Матрицы: VV, VU, FO, FI, IO.
3. N=11 и T=2
4. K=6 : N1=4, N2=4, N3=5, N4=5, N5=6, N6=6
5. L=5 : N1=2, N2=3, N3=4, N4=3, N5=2
6. Перечислить маршруты:
7. N=25 // P>7 и k>4
9. Q=7 и N=13
Вариант № 11.
1. T=2 и Z=6 : N1=3, N2=5, N3=5, N4=6, N5=6, N6=7 // I=3, S=4, V=3 // R=5 : r1=4, r2=5, r4=6 // K=5 и M>4
2. Матрицы: VV, VU, FO, FI, IO.
3. N=14 и T=3
4. K=6 : N1=2, N2=3, N3=3, N4=4, N5=4, N6=5
5. L=4 : N1=2, N2=4, N3=3, N4=2
6. Перечислить маршруты:
7. N=22 // P>6 и k>6
9. Q=8 и N=13
Вариант № 12.
1. T=3 и Z=6 : N1=4, N2=4, N3=5, N4=5, N5=6, N6=6 // I=4, S=4, V=3 // R=5 : r1=3, r2=4, r4=5 // K=5 и M>4
2. Матрицы: VV, VU, FO, FI, IO.
3. N=10 и T=2
4. K=6 : N1=1, N2=2, N3=3, N4=4, N5=5, N6=6
5. L=4 : N1=3, N2=2, N3=4, N4=3
6. Перечислить маршруты:
7. N=22 // P>3 и k>7
9. Q=8 и N=15
Вариант № 13.
1. T=1 и Z=3 : N1=5, N2=6, N3=7 // I=2, S=2, V=1 // R=3 : r1=1, r2=2, r4=3 // K=3 и M>2
2. Матрицы: VV, VU, FO, FI, IO.
3. N=10 и T=2
4. K=5 : N1=3, N2=4, N3=5, N4=6, N5=6
5. L=5 : N1=2, N2=1, N3=2, N4=3, N5=2
6. Перечислить маршруты:
7. N=18 // P>3 и k>3
9. Q=5 и N=12
Вариант № 14.
1. T=2 и Z=5 : N1=3, N2=8, N3=4, N4=5, N5=6 // I=4, S=3, V=2 // R=6 : r1=1, r2=2, r4=3 // K=5 и M>3
2. Матрицы: VV, VU, FO, FI, IO.
3. N=20 и T=5
4. K=6 : N1=3, N2=3, N3=4, N4=4, N5=5, N6=5
5. L=7 : N1=2, N2=3, N3=4, N4=3, N5=2, N6=3, N7=2
6. Перечислить маршруты:
7. N=24 // P>6 и k>5
9. Q=6 и N=15
Вариант № 15.
1. T=2 и Z=4 : N1=6, N2=6, N3=5, N4=5 // I=3, S=3, V=1 // R=4 : r1=2, r2=3, r4=4 // K=4 и M>2
2. Матрицы: VV, VU, FO, FI, IO.
3. N=12 и T=3
4. K=5 : N1=4, N2=4, N3=5, N4=5, N5=6
5. L=7 : N1=2, N2=1, N3=3, N4=2, N5=1, N6=3, N7=2
6. Перечислить маршруты:
7. N=25 // P>5 и k>4
9. Q=6 и N=20
Вариант № 16.
1. T=3 и Z=3 : N1=8, N2=9, N3=10 // I=3, S=4, V=3 // R=5 : r1=2, r2=3, r4=4 // K=5 и M>3
2. Матрицы: VV, VU, FO, FI, IO.
3. N=20 и T=4
4. K=6 : N1=3, N2=3, N3=4, N4=4, N5=5, N6=5
5. L=7 : N1=2, N2=3, N3=1, N4=2, N5=4, N6=3, N7=3
6. Перечислить маршруты:
7. N=22 // P>4 и k>5
9. Q=7 и N=15
Вариант № 17.
1. T=2 и Z=5 : N1=5, N2=6, N3=7, N4=8, N5=9 // I=4, S=4, V=3 // R=6 : r1=3, r2=4, r4=6 // K=6 и M>4
2. Матрицы: VV, VU, FO, FI, IO.
3. N=20 и T=5
4. K=8 : N1=3, N2=3, N3=4, N4=4, N5=5, N6=5, N7=6, N8=6
5. L=8 : N1=2, N2=3, N3=1, N4=4, N5=2, N6=2, N7=3, N8=3
6. Перечислить маршруты:
7. N=26 // P>6 и k>5
9. Q=7 и N=20
Вариант № 18.
1. T=3 и Z=5 : N1=4, N2=5, N3=6, N4=7, N5=8 // I=5, S=3, V=3 // R=6 : r1=3, r2=4, r4=5 // K=6 и M>3
2. Матрицы: VV, VU, FO, FI, IO.
3. N=22 и T=6
4. K=7 : N1=3, N2=3, N3=4, N4=4, N5=5, N6=5, N7=6
5. L=8 : N1=3, N2=2, N3=4, N4=1, N5=2, N6=3, N7=2, N8=3
6. Перечислить маршруты:
7. N=27 // P>7 и k>4
9. Q=5 и N=10
Вариант № 19.
1. T=1 и Z=5 : N1=2, N2=4, N3=6, N4=8, N5=10 // I=3, S=5, V=3 // R=6 : r1=3, r2=4, r4=5 // K=6 и M>4
2. Матрицы: VV, VU, FO, FI, IO.
3. N=23 и T=6
4. K=6 : N1=4, N2=4, N3=5, N4=5, N5=6, N6=6
5. L=9 : N1=2, N2=2, N3=3, N4=1, N5=2, N6=2, N7=3, N8=4, N9=3
6. Перечислить маршруты:
7. N=25 // P>4 и k>7
9. Q=4 и N=10
Вариант № 20.
1. T=3 и Z=5 : N1=6, N2=6, N3=7, N4=7, N5=8 // I=4, S=4, V=2 // R=5 : r1=3, r2=4, r4=5 // K=6 и M>3
2. Матрицы: VV, VU, FO, FI, IO.
3. N=25 и T=6
4. K=6 : N1=3, N2=6, N3=5, N4=5, N5=4, N6=8
5. L=8 : N1=3, N2=2, N3=1, N4=2, N5=4, N6=3, N7=4, N8=3
6. Перечислить маршруты:
7. N=25 // P>4 и k>5
9. Q=7 и N=15
Вариант № 21.
1. T=2 и Z=3 : N1=10, N2=9, N3=8 // I=4, S=4, V=2 // R=5 : r1=3, r2=4, r4=5 // K=5 и M>3
2. Матрицы: VV, VU, FO, FI, IO.
3. N=14 и T=2
4. K=6 : N1=2, N2=3, N3=4, N4=5, N5=6, N6=7
5. L=7 : N1=2, N2=3, N3=2, N4=4, N5=3, N6=2, N7=3
6. Перечислить маршруты:
7. N=20 // P>3 и k>5
9. Q=6 и N=12
Вариант № 22.
1. T=2 и Z=2 : N1=12, N2=14 // I=2, S=2, V=2 // R=4 : r1=1, r2=2, r4=3 // K=5 и M>4
2. Матрицы: VV, VU, FO, FI, IO.
3. N=14 и T=2
4. K=5 : N1=2, N2=3, N3=4, N4=5, N5=6
5. L=8 : N1=3, N2=2, N3=4, N4=3, N5=2, N6=4, N7=3, N8=2
6. Перечислить маршруты:
7. N=29 // P>5 и k>7
9. Q=6 и N=18
Вариант № 23.
1. T=2 и Z=3 : N1=10, N2=9, N3=8 // I=4, S=4, V=2 // R=5 : r1=3, r2=4, r4=5 // K=5 и M>3
2. Матрицы: VV, VU, FO, FI, IO.
3. N=14 и T=3
4. K=6 : N1=2, N2=3, N3=4, N4=5, N5=6, N6=7
5. L=5 : N1=2, N2=3, N3=2, N4=4, N5=3
6. Перечислить маршруты:
7. N=20 // P>3 и k>5
9. Q=6 и N=12
Вариант № 24.
1. T=2 и Z=2 : N1=12, N2=14 // I=2, S=2, V=2 // R=4 : r1=1, r2=2, r4=3 // K=5 и M>4
2. Матрицы: VV, VU, FO, FI, IO.
3. N=12 и T=2
4. K=5 : N1=2, N2=3, N3=4, N4=5, N5=6
5. L=8 : N1=3, N2=2, N3=3, N4=3, N5=2, N6=4, N7=3, N8=2
6. Перечислить маршруты:
7. N=22 // P>5 и k>7
9. Q=6 и N=18
Вариант № 25.
1. T=1 и Z=3 : N1=6, N2=8, N3=9 // I=2, S=3, V=2 // R=4 : r1=2, r2=3, r4=5 // K=4 и M>2
2. Матрицы: VV, VU, FO, FI, IO.
3. N=12 и T=3
4. K=5 : N1=2, N2=3, N3=4, N4=5, N5=6
5. L=5 : N1=3, N2=4, N3=2, N4=4, N5=3
6. Перечислить маршруты:
7. N=20 // P>4 и k>4
9. Q=6 и N=12
О б р а з е ц в ы п о л н е н и я з а д а н и я
Цель работы
Изучение основ теории графов, базовых понятий и определений; ознакомление с задачами, возникающими в теории графов и методами их решения; освоение компьютерных способов представления графов и алгоритмов машинной обработки графов.
Освоение компьютерных технологий обработки графов; изучение специализированных программных продуктов для ввода, редактирования и анализа графов на ЭВМ.
Практическая часть
Практическая часть работы была реализована с помощью программы GRAPH TOOLBOX 1.3 (build 3010.20.02) с использованием материалов методического пособия «Анализ структур сложных систем графовыми методами».
Задание 1
Построить граф, состоящий из 3 изолированных компонент мощностью 4, 5, 6 и 1 изолированных вершины. Во всём графе должно быть 2 истока, 2 стока, 1 висячие вершины, 3 регулярных вершин, три из которых имеют степени 1, 2, 3. Максимальная степень кратности дуг графа должна быть 3. В графе должно быть не меньше, чем 2 пар противоположных дуг.
В отчете представить построенный граф с выделением всех построенных элементов. Надписать полустепени исхода и захода для каждой вершины.
Вершины изолированных компонент:
2, 3, 4, 5 (мощность 4);
6, 7, 8, 9, 10 (мощность 5);
11, 12, 13, 14, 15, 16 (мощность 6).
Изолированные вершины: 1.
Вершины-истоки: 4, 6.
Вершины-стоки: 5, 16.
Висячие вершины: 16.
Регулярные вершины:
2 (степень 1), 8 (степень 2), 11 (степень 3).
Пары противоположных дуг:
9-11, 12-13, 18-19, 20-23, 16-24.
Полустепени исхода и захода вершин:
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
|
|
р+ |
0 |
1 |
1 |
0 |
3 |
0 |
2 |
2 |
2 |
2 |
3 |
1 |
3 |
1 |
2 |
1 |
|
р- |
0 |
1 |
2 |
2 |
0 |
3 |
1 |
2 |
1 |
1 |
3 |
2 |
2 |
3 |
1 |
0 |
Рисунок 11
Задание 2
Построить ориентированный граф из 7 вершин и 14 дуг, содержащий один исток, один сток, одну изолированную вершину, одну регулярную вершину, одну петлю, пару одинаково направленных дуг, пару противоположно направленных дуг. С истоком и со стоком должно быть связано более двух дуг.
Построить и проанализировать следующие способы представления графов: матрица смежности, матрица инцидентности, матрицы окрестностей вершин по входам и по выходам, список дуг. В отчете представить построенный граф и матричные представления графа с описанием. (1 граф и 5 матриц)
Рисунок 12
Матрица смежности: Матрица инцидентности:
Из матрицы смежности:
Единица в четвертой строке на главной диагонали говорит о том, что четвертая вершина имеет дугу-петлю. Вершины 4 и 3 имеют противоположно направленные дуги, т. к. соответствующие элементы матрицы, симметричные главной диагонали, заполнены. Т.к. число во второй строке третьего столбца - 2, то в графе имеются две кратные дуги, направленные от 2-ой к 3-ей вершине. Строки матрицы соответствуют выходным окрестностям вершин, а столбцы - входным окрестностям. Сумма элементов по строке равна полустепени исхода соответствующей вершины, а сумма элементов по столбцу - полустепени захода. Вершине-истоку 1 соответствует нулевой столбец 1 и ненулевая строка 1, а вершине-стоку 6 соответствует нулевая строка 6 и ненулевой столбец 6. Изолированной вершине 7 соответствует нулевая строка 7 и нулевой столбец 7.
Из матрицы инцидентности:
Дуге-петле 11 в матрице инцидентности соответствует единственная единица в 11-ом столбце, расположенная в строке с номером вершины, которой она принадлежит. Столбцы 7 и 8 одинаковы, следовательно, соответствующие дуги являются кратными. Столбцы 13 и 9 станут одинаковыми, если в них поменять местами -1 и 1, следовательно, соответствующие им дуги противоположно направлены. Количество -1 в любой строке равно полустепени исхода соответствующей вершины, а количество 1 равно полустепени захода. Изолированной вершине 7 соответствует нулевая 7-ая строка. Вершине-истоку 1 соответствует 1-ая строка, в которой имеются -1 и нет 1. Вершине-стоку 6 соответствует 6-ая строка, в которой имеются 1 но нет -1.
Из списка дуг:
Дуге-петле 11 графа соответствует столбец матрицы списка дуг, в котором элементы равны между собой и равны номеру вершины, которой эта дуга принадлежит. Т.к. дуги 7 и 8 кратны, им соответствуют одинаковые столбцы 7 и 8 матрицы. Противоположно направленным дугам 9 и 13 соответствуют 9 и 13 столбцы матрицы, которые оказываются одинаковыми, если в одном из них переставить местами элементы. Полустепень исхода любой вершины - количество повторений ее номера в первой строке матрицы, а полустепень захода - количество повторений ее номера во второй строке матрицы. Изолированная вершина 7 имеет номер, который не встречается ни в первой, ни во второй строке. Вершина-исток 1 имеет номер, который встречается в первой и не встречается во второй строке, а вершина-сток 6 имеет номер, который встречается во второй и не встречается в первой строке.
Из матриц окрестностей вершин:
Если в графе имеются кратные дуги, то в i-ой окрестности массива FO (FI) имеются повторяющиеся номера вершин. Противоположные дуги между вершинами i и j находятся как номер j встречается в окрестности i-ой вершины и одновременно номер i есть в окрестности j-ой вершины.
Задание 3
Построить связанный граф из 20 вершин, содержащий 5 точек сочленения, и не содержащий висячих и изолированных вершин. Рассчитать ранги вершин этого графа.
В отчете представить построенный граф с выделенными точками сочленения и подписанными рангами каждой вершины.
Рисунок 13
Матрица достижимости графа А и ранги вершин графа.
Очевидно, в матрице достижимости графа все элементы - единицы, следовательно матрица достижимости - единичная матрица 20x20. Следовательно, все элементы матрицы R = A + AA будут равны 21.
Т.к. ранг вершины графа равен отношению суммы элементов соответствующей строки к сумме элементов всей матрицы, то ранги всех вершин графа будут равны:
Построить связанный граф из 10 вершин, содержащий 2 точек сочленения, и не содержащий висячих и изолированных вершин. Рассчитать ранги вершин этого графа.
В отчете представить построенный граф с выделенными точками сочленения и подписанными рангами каждой вершины.
Рисунок 14
Матрица достижимости графа А и ранги вершин графа:
Ранги элементов вычисляются по следующей формуле: R = А + АА , где А - матрица достижимости графа.
Рисунок 15
Т.к. ранг вершины графа равен отношению суммы элементов соответствующей строки к сумме элементов всей матрицы, то ранги вершин графа будут равны:
Задание 4
Построить связанный ориентированный граф, содержащий 5 сильных компонент связанности мощностью 3,4, 5, 6, 6. Свернуть граф по найденным компонентам.
В отчете представить граф, раскрашенный по компонентам и граф-свертку.
Сильные компоненты :
Свертка графа:
Рисунок 16
Задание 5
Построить связанный ориентированный ациклический непоследовательный граф, состоящий из 5 порядковых уровней мощностью 2, 1,3, 3, 2. Граф содержит 2 истоков и 2 стока. Свернуть граф по найденным уровням. В отчете представить граф, упорядоченный по уровням слева направо и граф-свертку.
Свертка графа:
Рисунок 17
Задание 6
Построить связанный граф из 5 вершин и 7 дуг. Используя метод, описанный в учебном пособии, перечислить все маршруты этого графа длиной 1, 2, 3. В отчете привести граф и выкладки по вычислению матриц. (1 граф и 3 матрицы)
.
Рисунок 18
Задание 7
Построить связанный ориентированный граф из 22 вершин, содержащий один исток и один сток, не содержащий петель. Задать веса на дугах графа и пронумеровать все вершины. Между истоком и стоком построить Р>6 путей через остальные вершины, длиной больше 5 дуг.
Изменяя веса на дугах модифицировать граф так, чтобы кратчайшие пути по сумме весов и по количеству дуг между истоком и стоком не имели ни одной общей дуги (не совпадали). В отчете представить граф с выделенными путями, указать длину путей по весам и по количеству дуг. (1 картинка)
На этом же графе построить исходящее дерево кратчайших путей с корнем в истоке и заходящее дерево кратчайших путей с корнем в стоке.
Рисунок 19
Вершина-исток - 1, вершина сток - 22. Между истоком и стоком существует более 6-ти путей, длиной более 5-и дуг. Кратчайший путь по количеству дуг (6 дуг, вес 25) и кратчайший путь по весам дуг (7 дуг, вес 17) не имеют ни одной общей дуги.
Рисунок 20
Заходящее дерево кратчайших путей с корнем в вершине-стоке (22):
Рисунок 21
Задание 8
Построить связанный ориентированный граф, имеющий как минимум две центральные вершины, как минимум две периферийные вершины, как минимум две обычные вершины так, чтобы его радиус был не равен нулю и не равен диаметру. Начать построение с 6 вершин, добиться результата добавлением и удалением дуг и вершин. Построить максимальное покрывающее дерево кратчайших путей.
В отчете представить построенный граф с выделенным деревом, центром и периферией, над вершинами надписать их эксцентриситеты, указать значения радиуса и диаметра графа.
Рисунок 22
Эксцентриситеты вершин:
ехс(1)=4; ехс(2)=3; ехс(3)=3; ехс(4)=3;
ехс(5)=4; ехс(б)=4; ехс(7)=5; ехс(8)=5.
Центральные вершины:
2, 3, 4 (ехс=3).
Периферийные вершины:
7, 8 (ехс=5).
Обычные вершины:
1, 5, 6 (ехс=4).
Радиус графа:
R=exc(2)=ехс(3)=ехс(4)=3¹0.
Диаметр графа:
D=exc(7)=ехс(8)=5¹R.
Вывод:
В данной лабораторной работе были изучены различные способы представления графов и методы исследования топологических структур с использованием основных положений теории графов.
Основные законы булевой алгебры и правила преобразований
ОСНОВНЫЕ ПОЛОЖЕНИЯ
ЛОГИЧЕСКИЕ (БУЛЕВЫ) ФУНКЦИИ
Основные понятия
В курсе математического анализа изучаются функции, определённые на числовой прямой или на отрезке числовой прямой или на плоскости и т.п. Так или иначе область определения – непрерывное множество. В курсе дискретной математики изучаются функции, область определения которых – дискретное множество. Простейшим (но нетривиальным) таким множеством является множество, состоящее из двух элементов. Таким образом, частным случаем функции y=f(x1;x2;…;xn) является функция, значения которой и значения компонент её аргумента принадлежат множеству {0;1}. Такую функцию называют логической. Аргумент логической функции (x1;x2;…;xn) часто называют двоичным(или булевым) вектором, а его компоненты-двоичными(или булевыми) переменными.
Логическую функцию также называют логической операцией, т.к. значения функции и её аргументов принадлежат одному множеству {0;1}. Знаки логических операций называют логическими связками.
Алгебру, носителем которой является множество X=(x1;x2;…¼xn,y}, элементы которого принимают значения на множестве {0;1}, а сигнатура которой определена множеством логических связок(логических операций), называют алгеброй логики.
Два возможных значения логических переменных называют ИСТИНА (TRUE) и ЛОЖЬ (FALSE), иногда их называют ДА и НЕТ, а чаще всего их обозначают 1 и 0. При этом следует помнить, что эти логические 0 и 1 нельзя трактовать как числа, над ними нельзя производить арифметические действия.
Логическая функция может быть задана четырьмя способами:
– словесно (описанием ситуации),
– алгебраическим выражением,
– таблицей истинности
– электрической схемой, состоящей из контактов переключателей.
Например:
1.Лифт можно вызвать, если закрыты двери лифта на первом этаже и на втором этаже и на третьем этаже.
2.Если закрытые двери на первом этаже обозначить как А = 1, на втором – В = 1, на третьем – С = 1, возможность вызвать лифт обозначить как F = 1, а логическую функцию И обозначить знаком умножения " × ", то алгебраическое выражение будет иметь вид :
F = A×B×C (7)
3.В таблицу истинности заносятся все возможные комбинации входных аргументов и соответствующие этим комбинациям значения выходной функции. Входные комбинации записываются в порядке возрастания их значений от всех нулей до всех единиц сверху вниз. Таблица истинности, соответствующая данному примеру будет иметь следующий вид:
4.Электрическая контактная схема обладает хорошей наглядностью, но может быть легко построена лишь для самых простых логических функций. Для нашего примера эта схема может иметь следующий вид:
Рисунок 23
Многообразие значений логической функции f(x1;x2;….;.xn) определено многообразием значений её аргумента, т.е. |y|=2|(x1;x2;…. . .xn)|.
Например, для вектора (x1;x2;x3) имеем: |{(x1;x2;x3)}|=23=8, т.е. {(0;0;0);(0;0;1);(0;1;0);(0;1;1);(1;0;0);(1;0;1);(1;1;0);(1;1;1)}. Для функции y=f(x1;x2;…x8) имеем: |y|=28=256.
Для изображения аргумента логической функции, используют n-мерный куб с длиной ребра 1. Так, для вектора (x1;x2;x3), представленного на рис. 24-а), каждая вершина графа куба имеет единственный набор значений компонент этого вектора. Для вектора (x1;x2;x3;x4), представленного на рис. 24-б), каждая вершина 4-мерного куба также имеет единственный набор значений компонент вектора.
а) x3 б) x3
(0;0;1)
(1;0;1) (0;1;1) (0;0;1;0)
(1;1;1) (0;1;1;0)
(0;0;0) (1;0;1;0)
(1;1;1;0)
(0;1;0) (0;0;0;0)
(1;0;0) x2 (0;1;0;0) x3
(1;0;0;0)
x1 x2
(1;1;0;0) (0;0;1;1)
x1
(1;0;1;1) (1;1;1;0)
(0;0;0;1)
(1;0;0;1)
x2
x1 (1;1;0;1) x4
Рисунок 24. Единичные кубы для векторов (x1;x2;x3) и (x1;x2;x3;x4).
Булевый вектор (x1;x2;x3;x4) часто называют тетрадой, как содержащий четыре компоненты.
Следует обратить внимание, что две вершины куба, принадлежащие одному ребру, отличаются между собой только значениями одной компоненты; четыре вершины, принадлежащие одной плоскости, отличаются между собой только значениями двух компонент булевого вектора.
При табличном задании функции необходимо для каждого набора двоичного вектора, т.е. аргумента логической функции, указать её значение (см. таблицу 1). Если значение функции определено не для всех наборов двоичного вектора, то функция называется частично определённой. Число строк полностью определённой функции от n компонентов аргумента равно 2n.
Таблица 1
|
x1 |
x2 |
¼… |
xn |
f(x1;x2;¼…xn) |
|
0 1 0 1 …¼ 1 |
0 0 1 1 …¼ 1 |
…¼ …¼ ¼ ¼… …¼ …¼ |
0 0 0 0 …¼ 1 |
0 0 1 1 …¼ 0 |
При аналитическом задании логической функции используют элементарные унарные и бинарные операции , а также правила подстано-вки и замещения при формировании формул
логической функции.
Описание логической функции одной и двух двоичных переменных.
Как уже было отмечено, число логических функций для n компонентов аргумента определяется выражением: 2p, где p=2n.
Таблица 2.
|
X |
y=f(x) |
|||
|
f0(x) |
f1(x) |
f2(x) |
f3(x) |
|
|
0 |
0 |
0 |
1 |
1 |
|
1 |
0 |
1 |
0 |
1 |
Для n=1 число возможных значений логической функции равно 4 (см. табл. 2).
Анализ таблицы 2 позволяет дать определение каждой из четырёх логических функций:
f0(x) - функция-константа “0”, т.к. она не изменяет своего значения при изменении аргумента, т.е. (y=0), переменная x для этой функции несущественна;
f1(x) - функция повторитель, т.к. она принимает значения, равные значению аргумента, т.е. (y=x);
f2(x) – функция отрицания, т.к. она принимает значения противоположные значению аргумента, т.е. (y=`x), эта функция может еще обозначаться: ùx, ¬x, `x;
f3(x) - функция-константа “1”, т.к. она не изменяет своего значения при изменении аргумента, т.е. (y=1) и, как для функции f0(x), переменная x для этой функции несущественна.
Все функции таблицы 22 – унарные, т.к. это функции от одной переменной.
Для n=2 число возможных значений логической функции равно 16 (см. табл. 3).
Таблица 3
|
Аргум. |
Функция y=fi(x1,x2) |
||||||||||||||||
|
x1 |
x2 |
f0 |
f1 |
f2 |
f3 |
f4 |
f5 |
f6 |
f7 |
f8 |
f9 |
f10 |
f11 |
f12 |
f13 |
f14 |
f15 |
|
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 |
В таблице 4 приведены имена всех логических функций.
Таблица 4
|
№№ |
имя логической функции |
формула логической функции |
“чтение” логической функции |
|
f0 |
константа “0” |
0 |
“любой ноль” |
|
f1 |
конъюнкция (логическое “И” совпадение) |
(x1×x2) |
“x1 и x2“ |
|
f2 |
отрицание импликации |
ù(x1®x2)=x1×`x2=ù(`x1Úx2) |
“не если x1, то x2” |
|
f3 |
повторитель первого аргумента |
x1 |
“как x1“ |
|
f4 |
отрицание обратной импликации |
ù(x2®x1)=`x1×x2=ù(x1Ú`x2) |
“не если x2, то x1” |
|
f5 |
повторитель второго аргумента |
x2 |
“как x2“ |
|
f6 |
отрицание эквивалентности (сложение по модулю 2) |
ù(x1«x2)=(x1Åx2)= (`x1×x2Ú x1×`x2) |
“или x1,или x2“ |
|
f7 |
дизъюнкция (логическое “ИЛИ”, разделение) |
(x1Úx2) |
“x1 или x2” |
|
f8 |
отрицание дизъюнкции (стрелка Пирса) |
ù(x1Úx2)=x1¯x2=`x1×`x2 |
“не x1 и не x2” |
|
f9 |
эквиваленция (равнозначность) |
(x1«x2)=(`x1×`x2Úx1×x2) |
“x1 как x2” |
|
f10 |
отрицание второго аргумента |
`x2 |
“не как x2” |
|
f11 |
обратная импликация |
(x2®x1)=`x2×x1 |
“если x2,то x1” |
|
f12 |
отрицание первого аргумента |
`x1 |
“не как x1” |
|
f13 |
прямая импликация |
(x1®x2)=`x1×x2 |
“если x1, то x2” |
|
f14 |
отрицание конъюнкции (штрих Шеффера) |
ù(x1×x2)=x1½x2=(`x1Ú`x2) |
“не x1 или не x2” |
|
f15 |
константа “1” |
1 |
“любая единица” |
Перечислим 7 важнейших функций:
1) f1 - конъюнкция (функция И), конъюнкция – это фактически обычное умножение (нулей и единиц). Иногда эту функцию обозначают x1& x2 или x1 x2.
2) f7 - дизъюнкция (функция ИЛИ).
3) f13 - импликация (следование).
Иногда импликацию обозначают x1 x2, это очень важная функция, особенно в логике. Ее можно рассматривать следующим образом: если x1 = 0 (т. е. x1 “ложно”), то из этого факта можно вывести и “ложь”, и “истину” (и это будет правильно), если x2= 1 (т. е. x2 “истинно”), то истина выводится и из “лжи” и из “истины”, и это тоже правильно. Только вывод “из истины ложь” является неверным.
4) f6 - сложение по модулю 2. Иногда эту функцию обозначают x1∆ x2 или x1≢x2.
5) f9 - эквивалентность или подобие. Эта функция f9= 1 тогда и только тогда, когда x1 = x2. Иногда эту функцию обозначают x1≡ x2 или x1~x2.
6) f14 - штрих Шеффера.
7) f8 - стрелка Пирса (иногда эту функцию называют штрих Лукасевича).
Анализ логических функций одной и двух переменных показывает, что среди множества значений существуют функции от меньшего числа переменных. Так, для n=2 имеем : f0(x1;x2) и f15(x1;x) вообще не зависят от двоичных переменных, а функции f3(x1;x2),f5(x1;x),f10(x1;x2) и f12(x1;x2) зависят только от значений одной переменной.
Функция, которая сводится к зависимости от меньшего числа двоичных переменных, называется вырожденной, а функция, существенно зависящая от всех двоичных переменных, - невырожденной.
Двоичная переменная xi в функции f(x1;x2;…;xi-1;xi;xi+1;…;xn) называется фиктивной, если выполняется условие:
f(x1;x2;…¼;xi-1;0;xi+1;…¼;xn)=f(x1;x2;…¼;xi-1;1;xi+1;…¼;xn).
Удаление фиктивной переменной упрощает анализ функции, а её введение позволяет всякую функцию сделать функцией от большего числа переменных.
Суперпозиция логических функций. Формулы.
Часто рассматриваются функции от функций, т. е. суперпозиции перечисленных выше функций. Функция f, получаемая из функций f1;f2;…;fn с помощью операций подстановки их друг в друга и переименования аргументов, называется суперпозицией функций.
Алгебраическое выражение, описывающее логическую функцию и содержащее только двоичные переменные и логические связки, называют формулами F над F0, где F0сигнатура(множество операций ) алгебры логики. Двоичные переменные иногда называют формулами глубины 0, а элементарные формулы, аргументами которых являются только двоичные переменные, - формулами глубины 1. При этом последовательность действий указывается (как обычно) скобками. Исключение составляет конъюнкция (которая на самом деле является обычным умножением в двоичной системе).Поэтому конъюнкция совершается первой даже если отсутствуют скобки. Например, запись x1 & x2 x2 & x3 означает (x1 & x2) (x2 & x3).
Всякая формула, выражающая функцию f как суперпозицию других функций f1;f2;…. . .;fn, задаёт способ её вычисления: формулу можно вычислить, только если уже вычислены значения всех её подформул. Значение подформулы можно вычислить по известному набору значений двоичных переменных.
По каждой формуле можно восстановить таблицу логической функции, но не наоборот, т.к. каждой логической функции можно представить несколько формул.
Формулы Fi и Fj представляющие одну и ту же логическую функцию fi, называются эквивалентными или равносильными. Так, эквивалентными формулами являются:
f8(x1;x2)=(`x1×`x2)= ù(x1x2)=x1¯x2;
f14(x1;x2)=(`x1x2)= ù(x1×x2)=x1½x2.
Равенство Fi=Fj означает, что формулы Fi и Fj описывают одну и ту же логическую функцию.
Если какая-либо формула F содержит в качестве подформулы Fi, то замена Fi на эквивалентную Fj не изменяет значения формулы F при любом наборе булевого вектора, но изменяет форму её описания. Вновь полученная формула F` эквивалентна формуле F.
При формировании формул следует придерживаться следующих правил
Число левых скобок равно числу правых скобок;
Нет двух стоящих рядом логических связок, т.е. между ними должны быть формулы;
Нет двух стоящих рядом формул, т.е. между ними должны быть логические связки;
Логическая связка “` “ сильнее любой двухместной операции и выполняется прежде всего;
Логическая связка “& “ сильнее любой двухместной логической связки;
Эти правила облегчают запись формул и их преобразование.
Из перечисленных функций особую роль играют три функции, а именно конъюнкция, дизъюнкция и отрицание, поэтому рассмотрим более подробно их свойства.
Булева алгебра и минимизация булевых функций
Алгебру, носителем которой является множество X=(x1;x2;…¼xn,y}, элементы которого принимают значения на множестве {0;1}, а сигнатура которой определена логическими операциями дизъюнкции, конъюнкции и отрицания называют булевой алгеброй в честь английского математика Дж. Буля.
Таким образом булева алгебра есть: A=<Х; &; Ú;` ; 0; 1>,
где:
Х - множество, элементы которого принимают значения “1” или “0”;
¯ - унарная операция отрицания значения х;
& - бинарная операция конъюнкции двух элементов множества Х;
Ú - бинарная операция дизъюнкции двух элементов множества Х;
Особая роль двух функций (из этих трех) определяется тем обстоятельством, что определение этих функций легко может быть перенесено на любое число переменных:
Конъюнкцией n переменных f (x1, x2, …, xn) = x1 & x2… & xn называется функция, которая принимает значение 1, если и только если все переменные равны 1 (и, значит, равна 0, если хотя бы одна из этих переменных равна 0).
Дизъюнкцией n переменных f (x1, x2, …, xn) = x1 Úx2 … Ú xn называется такая функция, которая равна 0 если и только если все переменные равны 0 (и, значит, равна 1 тогда и только тогда, когда хотя бы одна переменная равна 1).
Из этих определений видно, что конъюнкция и дизъюнкция коммутативны, т. е. обе функции не зависят от порядка переменных. Опираясь на законы булевой алгебры, можно выполнять эквивалентные преобразования любых алгебраических выражений, усложняя или упрощая их описание. Эквивалентные преобразования алгебраических выражений необходимы для поиска наименьшего числа вычислительных операций или достижения результатов вычислений за меньшее число шагов. Последовательное применение законов булевой алгебры, формирующее минимальное по вычислительной сложности алгебраическое выражение, называют стратегией преобразования. Для облегчения исполнения преобразований формул булевой алгебры в единой таблице представлены основные законы и правила (см. табл. 5).
Таблица 5
|
Наименование закона, правила |
Эквивалентные формулы |
|
1. коммутативности |
1. (х1Úх2)= х2Úх1; (х1 ×х2)= х2×х1; |
|
2. ассоциативности |
2. х1Ú(х2Úх3)= (х1Úх2)Úх3; х1× (х2×х3)= (х1×х2) ×х3; |
|
3. дистрибутивности |
3. х1Ú(х2×х3)= (х1Úх2)×(х1Úх3); х1×(х2Úх3)= (х1×х2)Ú(х1×х3); |
|
4.идемпотентности |
4. хÚх=х; х×х=х; |
|
5. поглощения |
5. х1Ú(х1×х3)=х1; х1×(х1Úх3)=х1; |
|
6. противоречия |
6. хÚùх=1; х×ùх=0; |
|
7. де Моргана |
7.ù(х1Úх2)=`ùх1×ùх2; ù(х1×х2)=`х1Ú`х2; |
|
свойство “1” |
8. хÚ1=1; х×1=х; |
|
9. свойство “0” |
9. хÚ0=х; х×0=0; |
|
10. двойное отрицание |
10.ù(ùх)=х. |
Рассмотрим стратегию преобразования формулы F:
F=х1×х2Ú`х1×(х2Úх1×х3)×ù( х1×(`х2Úх3)Ú х2×х3);
1) выполним преобразование по закону дистрибутивности
F=х1×х2Ú(`х1×х2Ú`х1×х1×х3)×ù( х1×(`х2Úх3)Ú х2×х3);
2) используем закон противоречия
F=х1×х2Ú`х1×х2×ù( х1×(`х2Úх3)Ú х2×х3);
3) воспользуемся законом де Моргана
F=х1×х2Ú`х1×х2×(ù(х1×(`х2Úх3))×ù(х2×х3));
4) повторим использование закона де Моргана
F=х1×х2Ú`х1×х2×((`х1Úù(х2Úх3))×(`х2Ú`х3));
5) используем еще раз закон де Моргана
F=х1×х2Ú`х1×х2×((`х1Ú(ù(ùх2)×`х3))×(`х2Ú`х3));
6) используем закон двойного отрицания
F=х1×х2Ú`х1×х2×(`х1Úх2×`х3)×(`х2Ú`х3));
7) выполним преобразование по закону дистрибутивности
F=х1×х2Ú(`х1×х2×`х1Úх1×х2×х2×`х3)×(`х2Ú`х3);
8) используем закон идемпотентности
F=х1×х2Ú(`х1×х2Úх1×х2×`х3)×(`х2Ú`х3);
9) выполним преобразование по закону дистрибутивности
F=х1×х2Ú`х1×х2×`х2Ú`х1×х2×`х3Úх1×х2×`х3×`х2Úх1×х2×`х3×`х3;
10) используем закон поглощения и идемпотентности
F=х1×х2Ú`х1×х2×`х3;
Итак, сложное алгебраическое выражение в результате эквивалентных преобразований, содержит меньшее число операций для тех же трех элементов множества х1,х2,х3.
Используя некоторые дополнительные преобразования, можно еще упростить формулу F.
11) выполним преобразование по закону дистрибутивности
F=х2×(х1Ú`х1×`х3);
12) исполним процедуру обобщенного склеивания и поглощения
F=х2×(х1Ú`х1×`х3Ú`х3)=х2×(х1Ú`х3);
Окончательное выражение формулы имеет вид: F= х2×(х1Ú`х3).
На шаге 12) было использовано одно из правил Блейка- Порецкого, а именно обобщенного склеивания:
Если К1 и К2 - какие-то логические функции, тогда:
х×К1Ú`х×К2 =х×К1Ú`х×К2 Ú К1 × К2 ,
Следствием из этого правила являются следующие выражения:
х×К Ú`х×К = К; х Ú`х×К = х Ú К.
При этом К, К1, К2 быть как логическими функциями, так и
простыми переменными, что можно представить, например, в следующих равнозначных записях:
х×у Ú`х×у =у или х×у Ú ùх×у =у или х×у Ú ¬ х×у =у
Точно также равнозначными являются записи:
и
ù(а & (ùb Ú ùc & d) =ùa Ú (ùùb & ùùc Úùd).
Дизъюнктивная и конъюнктивной нормальная формы
Простой конъюнкцией называется конъюнкция одной или нескольких переменных, при этом каждая переменная встречается не более одного раза. Например, х1×х2×х3 является простой конъюнкцией.
Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция простых конъюнкций. Например, `х3×`х2Úх1×х2 является ДНФ.
Простой дизъюнкцией называется дизъюнкция одной или нескольких переменных, при этом каждая переменная встречается не более одного раза. Например, х1Ú х2 Ú`х3 является простой дизъюнкцией.
Конъюнктивной нормальной формой (КНФ) называется конъюнкция простых дизъюнкций. Например, (х1Ú х2 Ú`х3 )× (х2Ú`х3 )× (х1Ú х3) – КНФ.
УКАЗАНИЯ
Перед решением задач контрольной работы рекомендуется ознакомиться со следующими методическими указаниями:
ЗАДАНИЕ: Опираясь на законы булевой алгебры, выполнить эквивалентные преобразования алгебраических выражений.
Вариант № 1.
1.
2.
Вариант № 2.
1.
2.
Вариант № 3.
1.
2.
Вариант № 4.
1.
2.
Вариант № 5.
1.
2.
Вариант № 6.
1.
2.
Вариант № 7.
1.
2.
Вариант № 8.
1.
2.
Вариант № 9.
1.
2.
Вариант № 10.
1.
2.
Вариант № 11.
1.
2.
Вариант № 12.
1.
2.
Вариант № 13.
1.
2.
Вариант № 14.
1.
2.
Вариант № 15.
1.
2.
Вариант № 16.
1.
2.
Вариант № 17.
1.
2.
Вариант № 18.
1.
2.
Вариант № 19.
1.
2.
Вариант № 20.
1.
2.
Вариант № 21.
1.
2.
Вариант № 22.
1.
2.
Вариант № 23.
1.
2.
Вариант № 24.
1.
2.
Вариант № 25.
1.
2.
О б р а з е ц в ы п о л н е н и я з а д а н и я
Цель работы:
Целью работы является изучение основ алгебры логики и особенностей булевой алгебры и минимизация булевых функций.
Задание на работу:
Используя методические указания, освоить последовательное применение законов булевой алгебры, формирующее минимальное по вычислительной сложности алгебраическое выражение
Упростить следующее выражение и указать, какие правила и законы булевой алгебры были применены на каждом шаге преобразований:
Решение:
Шаги преобразования исходного выражения:
1. правило де Моргана
2. правило де Моргана
3. закон двойного отрицания
4. правило де Моргана
5. закон дистрибутивности
6. закон дистрибутивности
7. закон идемпотентности
8. закон противоречия
9. свойство «0»
10. свойство «0»
Вывод:
В результате проведенных преобразований исходное выражение булевой функции приведено к дизъюнктивной нормальной формой (ДНФ).
Представление функций алгебры логики в виде схем из функциональных элементов
ОСНОВНЫЕ ПОЛОЖЕНИЯ
СХЕМЫ ИЗ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ
Представлению функций алгебры логики можно придать некоторый «инженерно-конструктивный » смысл. Можно рассматривать формулу Ф(х1, х2 ………. xn ) над каким-то произвольным фиксированным множеством элементарных функций F как «черный ящик», некое устройство, на вход которого подаются всевозможные наборы значений логических переменных, а на выходе появляются соответствующие этим наборам значения функции f , представляемой формулой Ф (рис.25)
x1
. f (x1,…,xn)
.
.
xn
Рисунок 25
«Черный ящик» функционирует как процесс построения формулы из подформул , добираясь
при этом до «базисных» формул из множества F, которые являются структурными элементами,
из которых собран «черный ящик», вычисляющий функцию f.
Базисом на множестве элементарных функций F для булевой алгебры являются: конъюнкция, дизъюнкция и отрицание. Структурные элементы, соответствующие этим операциям называются соответственно: конъюнктор, дизъюнктор и инвертор и могут быть изображены как показано на рис.26
a б в
Рисунок 26
Например формулу можно представить следующей схемой из функциональных элементов (рис.27)
x1
x1 x2
x2
Рисунок 27
Математически «схема» определяется как ориентированный граф специального вида, в котором и вершины и дуги снабжены некоторыми метками.
Пусть фиксированы множества: F (булевых функций) и X (булевых переменных).
Схемой из функциональных элементов над базисом FX (СФЭ), или просто схемой над базисом FX, также (F,X)-схемой, называют бесконтурный ориентированный граф (т.е. сеть), каждая вершина которого помечена одним из элементов множества FX.
При изображении схем входы обозначаются кружочками, а вершины, не являющиеся входами, - треугольниками, внутри которых записано обозначение функции, помечающей данную вершину. Выходы отмечаются «выходными» стрелками.
УКАЗАНИЯ
Перед решением задач контрольной работы рекомендуется ознакомиться со следующими методическими указаниями:
1. Белоусов А.И., Ткачев С.В. Дискретная математика: Учеб. для вузов/ под. ред. В.С. Зарубина, А.П. Крищенко.- М.: Изд-во МГТУ им. Н.Э.Баумана, 2001. – 744 с.
2. Пономарев В.Ф. Основы дискретной математики. Учебное пособие. -Калининград: КГТУ, 1997.– 152 с.
ЗАДАНИЕ: Опираясь на законы булевой алгебры, представить в виде схем из функциональных элементов формулы булевой алгебры
Вариант № 1.
Вариант № 2.
Вариант № 3.
Вариант № 4.
Вариант № 5.
Вариант № 6.
Вариант № 7.
Вариант № 8.
Вариант № 9.
Вариант № 10.
Вариант № 11.
Вариант № 12.
Вариант № 13.
Вариант № 14.
Вариант № 15.
Вариант № 16.
Вариант № 17.
Вариант № 18.
Вариант № 19.
Вариант № 20.
Вариант № 21.
Вариант № 22.
Вариант № 23.
Вариант № 24.
Вариант № 25.
О б р а з е ц в ы п о л н е н и я з а д а н и я
Цель работы:
Целью работы является изображение схемами из функциональных элементов вычислений формул булевой алгебры
Задание на работу:
Используя методические указания, освоить представление формул булевой алгебры в виде схем из функциональных элементов (конъюнктора, дизъюнктора и инвертора). Построить схему из функциональных элементов соответствующую заданной логической формуле.
Упростить заданную логическую формулу и указать, какие правила и законы булевой алгебры были применены на каждом шаге преобразований. Построить схему из функциональных элементов соответствующую упрощенной логической формуле.
Задана формула:
Схема из функциональных элементов соответствующая заданной формуле:
x1
x2
(
)
x3
Рисунок 28
Упрощение формулы:
Шаги преобразования исходного выражения:
Закон дистрибутивности.
Правило де Моргана.
Закон дистрибутивности.
Закон противоречия.
Закон дистрибутивности.
Свойство «1».
Схема из функциональных элементов соответствующая упрощенной формуле:
x1
x2
x3
Рисунок 29
Кафедра менеджмента высоких технологий
Учебное пособие
Дискретная математика
(Операции на графах, булева алгебра)
Виктория Ивановна Халимон
Александр Юрьевич Рогов
Олег Владимирович Проститенко
Отпечатано с оригинал-макета. Формат 6090 116.
Печ. л. 3 Тираж 40 экз.
Государственное образовательное учреждение высшего профессионального образования
Санкт-Петербургский государственный технологический институт (Технический университет)
190013, Санкт-Петербург, Московский пр., 26
–
–
Вершины 4 и 8 не имеют путей к остальным вершинам графа и они являются выходами системы. У данных элементов отсутствует влияние на остальные элементы, поэтому ранги равны нулю. Элементы 2 и 6, 3, 5, 7 и 9 имеют одинаковые ранги, что свидетельствует о их одинаковой значимости в системе. Выход из строя любого из элементов 2 и 6; 3, 5, 7 и 9 будет иметь примерно одинаковые последствия - система лишится одной из своих функций, но будет продолжать функционировать.
–
Ф
–
–
–
–
–
–