|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
|
|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Кафедра «Автоматизированные системы управления»Стр 1 из 3Следующая ⇒
ГОСУДАРСТВЕННОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «БЕЛОРУССКО-РОССИЙСКИЙ УНИВЕРСИТЕТ» Кафедра «Автоматизированные системы управления»
ДИСКРЕТНАЯ МАТЕМАТИКА Методические рекомендации к самостоятельной работе Направление подготовки: 09.03.01 Информатика и вычислительная техника Направленность (профиль): Автоматизированные системы обработки информации и управления Квалификация: Бакалавр
Могилев 2017 УДК 519.6 ББК 22.176 М 48 Рекомендовано к изданию учебно-методическим отделом Белорусско-Российского университета
Одобрено кафедрой «Автоматизированные системы управления» «07» февраля 2017 г., протокол № 9
Составители: канд. техн. наук, доц. А. И. Якимов, канд. техн. наук Е. А. Якимов
Рецензент
Изложены рекомендации по решению задач к контрольной работе, приведены примеры решения задач, а также учебно-методическая литература. Предназначены для выполнения самостоятельной работы студентами направления подготовки 09.03.01 Информатика и вычислительная техника.
Учебно-методическое издание
ДИСКРЕТНАЯ МАТЕМАТИКА
Ответственный за выпуск С. К. Крутолевич Технический редактор А. И. Якимов Компьютерная верстка Е. А. Якимов
Подписано в печать . Формат 60х84/16. Бумага офсетная. Гарнитура Таймс. Печать трафаретная. Усл.-печ. л. . Уч.-изд. л. . Тираж 31 экз. Заказ №
Издатель и полиграфическое исполнение Государственное учреждение высшего профессионального образования «Белорусско-Российский университет» Свидетельство о государственной регистрации издателя, изготовителя, распространителя печатных изданий № 1/156 от 24.01.2014 г. Пр. Мира, 43, 212000, Могилев.
© ГУ ВПО «Белорусско-Российский университет», 2017 Содержание 1 Множества. 4 1.1 Операции над множествами. 4 1.2 Задания для самостоятельной работы.. 5 2 Отношения. 7 2.1 Свойства отношений. 7 2.2 Задания для самостоятельной работы.. 9 3 Операции над графами. 9 3.2 Пересечение графов. 11 3.3 Задания для самостоятельной работы.. 13 4 Минимизация функций алгебры логики методом диаграмм Вейча 4.1 Задача минимизации булевых функций. 15 4.2 Правила минимизации с использованием диаграмм Вейча 4.2 Минимизация частично определенных булевых функций. 18 4.3 Задания для самостоятельной работы.. 18 5 Синтез и анализ логических схем. 19 5.1 Задача синтеза логической схемы.. 19 5.2 Синтез логических устройств в заданном базисе. 19 5.3 Задания для самостоятельной работы.. 21 6 Способы задания абстрактного конечного автомата. 24 6.1 Понятие конечного автомата. 24 6.2 Способы задания конечного автомата. 26 6.3 Примеры конечных автоматов. 26 6.4 Задания для самостоятельной работы.. 29 7 Требования к контрольной работе. 33 Список литературы.. 33
Множества Операции над множествами Если объект x является элементом множества M, то говорят, что x принадлежит множеству M. Обозначение: xÎ M. В противном случае говорят, что x не принадлежит множеству M. Обозначение: xÏ M. Множество, не содержащее элементов, называется пустым. Обозначение: Множество A содержится в множестве B (множество B включает множество A), если каждый элемент A есть элемент B:
В этом случае A называют подмножеством B, B – надмножеством A. По определению
Пример – Какие из приведенных соотношений:
верны? Ответ обосновать.
Обычно рассматривают следующие операции над множествами: 1) объединение A È B = { x | xÎ A 2) пересечение A Ç B = { x | xÎ A & xÎ B}; 3) разность A \ B = { x | xÎ A 4) симметричная разность A D B =(A È B) \ (A Ç B); 5) дополнение Пример – Даны множества М = {7, 2, 3, 5}, N = {1, 2, 4, 7, 9}, X = (M Ç N) È (M Ç К) \ (N Ç К) È (N \ K); Z = (M È N) Ç (M È К) \ (N È К) È (N \ K). Порядок определения множеств X и Z следующий. 1) M Ç N= {7, 2}; 2) M Ç К = {7}; 3) N Ç К ={7, 9}; 4) M È K ={2, 3, 5, 6, 7, 9}; 5) M È N = {1, 2, 3, 4, 5, 7, 9}; 6) N È K ={1, 2, 4, 6, 7, 9}; 7) N \ K={1, 2, 4}; 8) Р = (M Ç N) È (M Ç К) = {7, 2}È {7}= {7, 2}; 9) Р \ (N Ç К)= {7, 2}\{7, 9}={2}; 10) 11) D\ (N È К) ={2, 3, 5, 7, 9}\{1, 2, 4, 6, 7, 9}={3, 5}. X = (M Ç N) È (M Ç К) \ (N Ç К) È (N \ K) = (1, 2, 4); Множество всех подмножеств множества M называется булеаном и обозначается 2M. Пример – Для заданного множества Булеан для заданного множества A:
1.2 Задания для самостоятельной работы Задание 1 Какие из приведенных соотношений верны? Ответ обосновать. 1) 2) 3) 4) 5) 6) 7) 8) 9) 10 Задание 2 Какие из приведенных соотношений верны? Ответ обосновать. 1) 2) 3) 4) 5) 6) 7) 8) 9) 10) Задание 3 Привести примеры множеств A, B, C, D и F, которые удовлетворяют заданным условиям.
Задание 4 Пусть
Задание 5 Для заданного множества A определить множество всех подмножеств множества A, т. е. булеан множества A.
Отношения Свойства отношений
Пусть R – есть отношение между A и B: R Ì A ´ B. Введем следующие понятия: 1)обратное отношение: R‑ 1 = {(a, b) | (b, a)Î R}Ì B ´ A; 2) дополнение отношения: 3) тождественное отношение: I = {(a, a) | aÎ A}Ì A ´ A; 4) универсальное отношение: U = {(a, b) | aÎ A & bÎ B} = A ´ B. Пусть R – отношение на множестве А (R Ì A ´ A) и |А| = n, тогда R можно представить матрицей
Пусть R – есть отношение на множестве А: R Ì A ´ А. Тогда отношение R называется рефлексивным, если антирефлексивным, если симметричным, если антисимметричным, если транзитивным, если линейным, если Пример ‑ Пусть на множестве Х = {3, 5, 7} задано отношение R: = «меньше» (т.е. первый элемент меньше второго). Записать декартово произведение X ´ X. Из этого множества следует выбрать элементы, которые должны удовлетворять отношению R: = «меньше». Декартово произведение X ´ Х может быть записано в виде множества из упорядоченных пар: X ´ Х= {(3; 3), (3; 5), (3; 7), (5; 3), (5; 5), (5; 7), (7; 3), (7; 5), (7; 7)}. Из этого множества выбираются элементы, которые удовлетворяют отношению R: = «меньше». В результате получится новое множество из упорядоченных пар: R = {(3; 5), (3; 7), (5; 7)}. В новом множестве все пары являются элементами декартова произведения X ´ X. Отношение «меньше» на множестве Х является подмножеством декартова произведения X ´ X: R Ì X ´ X. Пусть R1 Ì A ´ C – отношение между A и C, а R2 Ì С ´ B – отношение между C и B. Композицией двух отношений R1 и R2 называется отношение R Ì A ´ B между A и B, определяемое следующим образом:
Другими словами,
Теорема ‑ Пусть R Ì A ´ А, тогда: 1) R рефлексивно тогда и только тогда, когда I Ì R; 2) R симметрично тогда и только тогда, когда R = R‑ 1; 3) R транзитивно тогда и только тогда, когда 4) R антисимметрично тогда и только тогда, когда RÇ R‑ 1Ì I; 5) R антирефлексивно тогда и только тогда, когда R Ç I = Æ; 6) R линейно тогда и только тогда, когда R È I È R‑ 1 = U. Пример ‑ Пусть бинарное отношение R на M задано в виде диаграммы, состоящей из узлов и стрелок так, что узлам взаимно однозначно соответствуют элементы множества М, а стрелкам, соединяющим пару а и b в направлении от а к b, ‑ наличие отношения a R b. Определить графические особенности диаграммы в зависимости от характера свойств отношения R. Отношение Отношение R антирефлексивно, если ни для каких а Отношение R симметрично, если из a R b следует b R а. В диаграмме симметричного отношения для каждой стрелки, соединяющей два узла, существует также стрелка, соединяющая эти узлы в обратном направлении. Отношение R антисимметрично, если из a R b и b R a следует а = b. В диаграмме антисимметричного отношения не существует двух различных узлов, связанных парой (разнонаправленных) стрелок. Отношение R транзитивно, если из a R b и b R c следует a R с. В диаграмме транзитивного отношения для любых двух стрелок таких, что одна направлена от а к b, а другая – от b к с, существует стрелка, соединяющая а и с в направлении от а к с.
2.2 Задания для самостоятельной работы
Определить, является ли отношение R на множестве 1 2 3 4 5 6 7 8 9 10 Операции над графами Объединение графов Пусть G1(V1, E1) и G2(V2, E2) – произвольные графы. Объединением G1È G2графов G1 и G2 называется граф с множеством вершин V1È V2, и множеством ребер (дуг) E1È E2. Рассмотрим операцию на примере графов G1(V1, E1) и G2(V2, E2), приведенных на рисунке 1. Множества вершин первого и второго графов соответственно равны V1 = {v1, v2, v3} и V2 = {v2, v3, v4}, а множество вершин результирующего графа определится как V = V1È V2 = {v1, v2, v3, v4}. Аналогично определяем множества дуг графа: E1 = {(v1, v2), (v1, v3), (v2, v1), (v 3, v3)}. E2= {(v2, v4), (v3, v2), (v4, v2)}. E ={(v1, v2), (v1, v3), (v2, v1), (v3, v3), (v2, v4), (v3, v2), (v4, v2)}. Результирующий граф G(V, E) = G1(V1, E1)È G2(V2, E2) также приведен на рисунке 1.
Рисунок 1 – Операция объединения графов
Операция объединения обладает следующими свойствами, которые следуют из определения операции и свойств операций на множествах: G1È G2 = G2È G1 – свойство коммутативности; G1È (G2È G3) = (G1È G2)È G3 – свойство ассоциативности. Операция объединения графов может быть выполнена в матричной форме. Для графов с одним и тем же множеством вершин справедлива следующая теорема. Теорема 1. Пусть G1 и G2 – два графа (ориентированные или не ориентированные одновременно) с одним и тем же множеством вершин V, и пусть A1 и A2 – матрицы смежности вершин этих графов. Тогда матрицей смежности вершин графа G1È G2 является матрица A = A1È A2, образованная поэлементным логическим сложением матриц A1 и A2. Рассмотрим выполнение операции объединения графов, множества вершин которых не совпадают. Пусть G1(V1, E1) и G2(V2, E2) – графы без параллельных ребер и множества V1 и V2 вершин этих графов не совпадают. Пусть A1 и A2 – матрицы смежности их вершин графов. Для таких графов операция объединения может быть выполнена следующим образом. В соответствии с определением операции объединения графов найдем множество вершин результирующего графа как V1È V2. Построим вспомогательные графы G’1 и G’2, множества вершин которых есть множество V1È V2, а множество ребер (дуг) определяется множествами E1 для графа G ’1 и E2 для графа G ’2. Очевидно, что матрицы A’1 и A’2 смежности вершин этих графов могут быть получены из матриц A1 и A2 путем добавления в них дополнительных столбцов и строк с нулевыми элементами. Применив к графам G’1 и G’2 теорему 1, найдем матрицу смежности вершин графа G’1È G’2 как A’1È A’2. Очевидно, что полученной матрице смежности вершин соответствует граф, множество вершин которого равно V1È V2, а множество ребер определяется, как E1È E2, что соответствует операции объединения графов. Пример ‑ Выполнить в матричной форме операцию объединения графов G1 и G2, представленных на рисунке 1. Составим матрицы смежности вершин графов.
Множество вершин результирующего графа V1È V2 = {v1, v2, v3, v4}. Составим матрицы смежности вершин вспомогательных графов G’1 и G’2.
Матрица A = A’1È A’2 имеет вид
Полученная матрица смежности вершин A’1È A’2 соответствует графу G1È G2, изображенному на рисунке1. Пересечение графов Пусть G1(V1, E1) и G2(V2, E2) – произвольные графы. Пересечением G1Ç G2 графов G1 и G2 называется граф с множеством вершин V1Ç V2 и множеством ребер (дуг) E = E1Ç E2. Операция пересечения обладает следующими свойствами, которые следуют из определения операции и свойств операций на множествах: G1Ç G2 = G2Ç G1 – свойство коммутативности; G1Ç (G2Ç G3) = (G1Ç G2)Ç G3 – свойство ассоциативности. Для того, чтобы операция пересечения была всеобъемлющей, необходимо ввести понятие пустого графа. Граф G( V, E) называется пустым, если множество V вершин графа является пустым (V = Æ ). Заметим, что в этом случае и множество E ребер (дуг) графа также пустое множество (E = Æ ). Пустой граф обозначается символом Æ. Такой граф может быть получен в результате выполнения операции пересечения графов, у которых V1Ç V2=Æ. В этом случае говорят о непересекающихся графах. Рассмотрим выполнение операции пересечения графов, изображенных на рисунке 2.
Рисунок 2 – Операция пересечения графов
Для нахождения множества вершин результирующего графа запишем множества вершин исходных графов и выполним над этими множествами операцию пересечения: V1 = {v1, v2, v3}; V2 = {v1, v2, v3, v4}; V = V1Ç V2 = {v1, v2, v3}. Аналогично определяем множество E дуг результирующего графа: E1 = {(v1, v2), (v1, v3), (v2, v1), (v2, v3), (v3, v2)}; E2 = {(v1, v3), (v2, v1), (v2, v3), (v2, v4), (v3, v1)}; E = E1Ç E2 = {(v1, v3), (v2, v1)}. Графы G1(V1, E1), G2(V2, E2) и их пересечение приведены на рисунке 2. Операция пересечения графов может быть выполнена в матричной форме. Теорема 2. Пусть G1 и G2 – два графа (ориентированные или неориентированные одновременно) с одним и тем же множеством вершин V, и пусть A1 и A2 – матрицы смежности вершин этих графов. Тогда матрицей смежности вершин графа G1Ç G2 является матрица A = A1Ç A2 образованная поэлементным логически умножением матриц A1 и A2. Рассмотрим выполнение операции пересечения для графов с несовпадающим множеством вершин. Пусть G1(V1, E1) и G2(V2, E2) – графы без параллельных ребер, множества V1 и V2 вершин графов не совпадают, а A1 и A2 – матрицы смежности вершин графов. В соответствии с определением операции пересечения графов найдем множество вершин результирующего графа как V1Ç V2. Построим вспомогательные графы G’1 и G’2, множества вершин которых есть множество V1Ç V2, а множество ребер (дуг) определяется множествами E’1 и E’2 всех ребер (дуг), инцидентных этим вершинам. Очевидно, что матрицы A’1 и A’2 смежности вершин этих графов могут быть получены из матриц A1 и A2 путем удаления из них столбцов и строк, соответствующих вершинам, не вошедшим во множество V1Ç V2. Применив к графам G’1 и G’2 теорему 2, найдем матрицу смежности вершин графа G’1Ç G’2 как A’1Ç A’2. Очевидно, что полученной матрице смежности вершин соответствует граф, множество вершин которого равно V1Ç V2, а множество ребер определяется, как E1Ç E2, что соответствует операции пересечения графов. Пример ‑ Выполнить в матричной форме операцию пересечения графов G1 и G2, представленных на рисунке 2. Составим матрицы смежности вершин исходных графов.
Находим множество вершин V результирующего графа: V = V1Ç V2 = {v1, v2, v3}. Составим матрицы смежности вершин вспомогательных графов G’1 и G’2.
Найдем матрицу смежности вершин A = A1Ç A2
Полученная матрица смежности вершин A’1Ç A’2 соответствует графу G1Ç G2, изображенному на рисунке 2.
3.3 Задания для самостоятельной работы
Даны графы G1 и G2. Найти G1È G2, G1Ç G2 и их матрицы смежности вершин.
Примеры конечных автоматов
Приведем несколько примеров конечных автоматов. Пример 1. Элемент задержки (элемент памяти). Элементы задержки представляют собой устройство, имеющее один вход и один выход. Причем значение выходного сигнала в момент времени t совпадает со значением сигнала в предыдущий момент. Схематично элемент задержки можно изобразить следующим образом (рисунок 7).
Рисунок 8 – Элемент задержки
Предположим, что входной и, следовательно, выходной алфавиты есть X = {0, 1}; Y = {0, 1}. Тогда Q = {0, 1}. Под состоянием элемента задержки в момент времени t понимается содержание элемента памяти в данный момент. Таким образом, q(t) = x(t – 1), a y(t) = q(t) = x(t – 1). Зададим элемент задержки таблицей 8, где а1= 0, а2 = 1, q1= 0, q2= 1,
Таблица 8 – Автоматная таблица элемента задержки
Диаграмма Мура изображена на рисунке 9.
Рисунок 9 – Диаграмма Мура элемента задержки
Для представления этого автомата системой булевых функций используем таблицу автомата и вышеизложенный алгоритм. При этом кодирование производить не нужно, так как входной и выходной алфавиты и состояния уже закодированы. Обратим внимание на то, что т = п = р = 2. Тогда k = r = s = l, и поэтому элемент задержки задается функциями δ и λ. Таблица истинности этих функций содержит 2k + r = 22 = 4 строки и k + r + r + s = 4 столбца.
Таблица 9 – Значения функций δ и λ элемента задержки
Пример 2 –Схема сравнения на равенство. Схема сравнения на равенство представляет собой устройство, сравнивающее числа x1и х2, заданные в двоичной системе исчисления. Это устройство работает следующим образом. На вход устройства поступают по двум каналам числа x1и х2. Число x1является результатом сложения по модулю 2 байта данных, хранящегося в памяти компьютера. Число x2является битом паритета, дополняющего число x1 так, чтобы их сумма сложения по модулю 2 была равна нулю. Это достигается при равенстве x1и х2. Поэтому эти числа сравниваются устройством сравнения. При совпадении разрядов на выходе схемы формируется выходной сигнал 0, в противном случае на выходе появляется сигнал 1, что говорит о сбое в памяти. Ясно, что появление 1 в выходной последовательности означает, что сравниваемые числа x1и х2различны. Если же выходная последовательность является нулевой, то x1 = х2. Для этого автомата X = {00; 01; 10; 11}; Y = {0, 1}. Функционирование схемы определяется двумя состояниями. Состояние q0 соответствует равенству сравниваемых в данный момент разрядов. При этом автомат остается в этом же состоянии. Если в следующий момент сравниваемые разряды будут различны, то автомат перейдет в новое состояние q1и в нем остается. Так как это означает, что числа различны. Таким образом, схему сравнения можно задать таблицей 10.
Таблица 10 – Автоматная таблица схемы сравнения
Диаграмма Мура схемы сравнения на равенство изображена на рисунке 10.
Рисунок 10 – Диаграмма Мура схемы сравнения на равенство
6.4 Задания для самостоятельной работы
Задание 1 Для автомата, заданного таблицей, постройте диаграмму Мура. Задайте этот автомат системой булевых функций.
Задание 2 Для автомата, заданного диаграммой Мура, выпишите соответствующую таблицу и систему булевых функций (рисунки 11–26).
Требования к контрольной работе
Аудиторная контрольная работа (АКР) выполняется согласно методическим рекомендациям кафедры. АКР включает задачи по основам теории множеств, отношений, булевой алгебре, основам теории графов, конечных автоматов. Образец с заданиями по АКР: Задание 1. Для данного множества А построить множество всех подмножеств, т. е. булеан множества Задание 2. Определить, является ли отношение R, заданное на множестве Задание 3. Синтезировать в базисе ИЛИ-НЕ устройство, заданное логической функцией: Задание 4. Даны графы G1 и G2. Найдите
Задание 5. Для автомата, заданного диаграммой Мура, выпишите соответствующую таблицу.
Список литературы
1 Новиков, Ф. А. Дискретная математика для программистов: Учебник / Ф. А. Новиков. ‑ 2-е изд. ‑ СПб.: Питер, 2006. – 364 с. 2 Вороненко, А. А. Дискретная математика. Задачи и упражнения с решениями: Учебно-методическое пособие / А.А. Вороненко. – М.: ООО " Научно-издательский центр ИНФРА-М", 2014. – 104 с. 3 Поздняков, С. Н. Дискретная математика: учебник для вузов / С. Н. Поздняков, С. В. Рыбин. ‑ М.: Академия, 2008. – 448 с. 4 Хопкрофт, Дж. Введение в теорию автоматов, языков и вычислений: [пер. с англ.] / Дж. Хопкрофт, Р. Мотвани, Дж. Ульман. – 2-е изд. – М.: Вильямс, 2008. – 528с. 5 Шевелев, Ю. П. Дискретная математика: учеб. пособие для вузов / Ю. П. Шевелев. – СПб.: Лань, 2008. – 592 с. 6 Окулов С. М. Дискретная математика. Теория и практика решения задач по информатике: учеб. пособие / С. М. Окулов. – М.: Бином, 2008. – 422 с. 7 Шапорев С. Д. Дискретная математика. Курс лекций по практическим занятиям: Курс лекций по практическим занятиям для вузов / С. Д. Шапорев. ‑ СПб.: БХВ-Петербург, 2007. – 400 с. 8 Певзнер, Л. Д. практикум по математическим основам теории систем: учеб. Пособие / Л. Д. Певзнер. СПб.; М.; Краснодар: Лань, 2013. – 400 с. 9 Галушкина, Ю. И. Конспект лекций по дискретной математике / Ю. И. Галушкина, А. Н. Марьямов. – М.: Айрис-Пресс, 2007. – 176 с. 10 Трохимчук, Р. М. Основы дискретной математики. Практикум / Р. М. Трохимчук. – Киев: МАУП, 2004. – 168 с. 11 Прикладная теория цифровых автоматов / К. Г. Самофалов [и др.]. – Киев: Вища шк., Головное изд-во, 1987. – 375 с.
ГОСУДАРСТВЕННОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «БЕЛОРУССКО-РОССИЙСКИЙ УНИВЕРСИТЕТ» Кафедра «Автоматизированные системы управления»
ДИСКРЕТНАЯ МАТЕМАТИКА Методические рекомендации к самостоятельной работе Направление подготовки: 09.03.01 Информатика и вычислительная техника Направленность (профиль): Автоматизированные системы обработки информации и управления Квалификация: Бакалавр
Могилев 2017 УДК 519.6 ББК 22.176 М 48 Рекомендовано к изданию учебно-методическим отделом Белорусско-Российского университета
Одобрено кафедрой «Автоматизированные системы управления» «07» февраля 2017 г., протокол № 9
Составители: канд. техн. наук, доц. А. И. Якимов, канд. техн. наук Е. А. Якимов
Рецензент
Изложены рекомендации по решению задач к контрольной работе, приведены примеры решения задач, а также учебно-методическая литература. Предназначены для выполнения самостоятельной работы студентами направления подготовки 09.03.01 Информатика и вычислительная техника.
Учебно-методическое издание
ДИСКРЕТНАЯ МАТЕМАТИКА
Ответственный за выпуск С. К. Крутолевич Технический редактор А. И. Якимов Компьютерная верстка Е. А. Якимов
Подписано в печать . Формат 60х84/16. Бумага офсетная. Гарнитура Таймс. Печать трафаретная. Усл.-печ. л. . Уч.-изд. л. . Тираж 31 экз. Заказ №
Издатель и полиграфическое исполнение Государственное учреждение высшего профессионального образования «Белорусско-Российский университет» Свидетельство о государственной регистрации издателя, изготовителя, распространителя печатных изданий № 1/156 от 24.01.2014 г. Пр. Мира, 43, 212000, Могилев.
© ГУ ВПО «Белорусско-Российский университет», 2017 Содержание 1 Множества. 4 1.1 Операции над множествами. 4 1.2 Задания для самостоятельной работы.. 5 2 Отношения. 7 2.1 Свойства отношений. 7 2.2 Задания для самостоятельной работы.. 9 3 Операции над графами. 9 3.2 Пересечение графов. 11 3.3 Задания для самостоятельной работы.. 13 4 Минимизация функций алгебры логики методом диаграмм Вейча 4.1 Задача минимизации булевых функций. 15 4.2 Правила минимизации с использованием диаграмм Вейча 4.2 Минимизация частично определенных булевых функций. 18 4.3 Задания для самостоятельной работы.. 18 5 Синтез и анализ логических схем. 19 5.1 Задача синтеза логической схемы.. 19 5.2 Синтез логических устройств в заданном базисе. 19 5.3 Задания для самостоятельной работы.. 21 6 Способы задания абстрактного конечного автомата. 24 6.1 Понятие конечного автомата. 24 6.2 Способы задания конечного автомата. 26 6.3 Примеры конечных автоматов. 26 6.4 Задания для самостоятельной работы.. 29 7 Требования к контрольной работе. 33 Список литературы.. 33
Множества Операции над множествами Если объект x является элементом множества M, то говорят, что x принадлежит множеству M. Обозначение: xÎ M. В противном случае говорят, что x не принадлежит множеству M. Обозначение: xÏ M. Множество, не содержащее элементов, называется пустым. Обозначение: Множество A содержится в множестве B (множество B включает множество A), если каждый элемент A есть элемент B:
В этом случае A называют подмножеством B, B – надмножеством A. По определению
Пример – Какие из приведенных соотношений:
верны? Ответ обосновать.
Обычно рассматривают следующие операции над множествами: 1) объединение A È B = { x | xÎ A 2) пересечение A Ç B = { x | xÎ A & xÎ B}; 3) разность A \ B = { x | xÎ A 4) симметричная разность A D B =(A È B) \ (A Ç B); 5) дополнение Пример – Даны множества М = {7, 2, 3, 5}, N = {1, 2, 4, 7, 9}, X = (M Ç N) È (M Ç К) \ (N Ç К) È (N \ K); Z = (M È N) Ç (M È К) \ (N È К) È (N \ K). Порядок определения множеств X и Z следующий. 1) M Ç N= {7, 2}; 2) M Ç К = {7}; 3) N Ç К ={7, 9}; 4) M È K ={2, 3, 5, 6, 7, 9}; 5) M È N = {1, 2, 3, 4, 5, 7, 9}; 6) N È K ={1, 2, 4, 6, 7, 9}; 7) N \ K={1, 2, 4}; 8) Р = (M Ç N) È (M Ç К) = {7, 2}È {7}= {7, 2}; 9) Р \ (N Ç К)= {7, 2}\{7, 9}={2}; 10) 11) D\ (N È К) ={2, 3, 5, 7, 9}\{1, 2, 4, 6, 7, 9}={3, 5}. X = (M Ç N) È (M Ç К) \ (N Ç К) È (N \ K) = (1, 2, 4); Множество всех подмножеств множества M называется булеаном и обозначается 2M. Пример – Для заданного множества Булеан для заданного множества A:
1.2 Задания для самостоятельной работы Задание 1 Какие из приведенных соотношений верны? Ответ обосновать. 1) 2) 3) 4) 5) 6) 7) 8) 9) 10 Задание 2 Какие из приведенных соотношений верны? Ответ обосновать. 1) 2) 3) 4) 5) 6) 7) 8) 9) 10) Задание 3 Привести примеры множеств A, B, C, D и F, которые удовлетворяют заданным условиям.
Задание 4 Пусть
Задание 5 Для заданного множества A определить множество всех подмножеств множества A, т. е. булеан множества A.
Отношения Свойства отношений
Пусть R – есть отношение между A и B: R Ì A ´ B. Введем следующие понятия: 1)обратное отношение: R‑ 1 = {(a, b) | (b, a)Î R}Ì B ´ A; 2) дополнение отношения: 3) тождественное отношение: I = {(a, a) | aÎ A}Ì A ´ A; 4) универсальное отношение: U = {(a, b) | aÎ A & bÎ B} = A ´ B. Пусть R – отношение на множестве А (R Ì A ´ A) и |А| = n, тогда R можно представить матрицей
Пусть R – есть отношение на множестве А: R Ì A ´ А. Тогда отношение R называется рефлексивным, если антирефлексивным, если симметричным, если антисимметричным, если транзитивным, если линейным, если Пример ‑ Пусть на множестве Х = {3, 5, 7} задано отношение R: = «меньше» (т.е. первый элемент меньше второго). Записать декартово произведение X ´ X. Из этого множества следует выбрать элементы, которые должны удовлетворять отношению R: = «меньше». Декартово произведение X ´ Х может быть записано в виде множества из упорядоченных пар: X ´ Х= {(3; 3), (3; 5), (3; 7), (5; 3), (5; 5), (5; 7), (7; 3), (7; 5), (7; 7)}. Из этого множества выбираются элементы, которые удовлетворяют отношению R: = «меньше». В результате получится новое множество из упорядоченных пар: R = {(3; 5), (3; 7), (5; 7)}. В новом множестве все пары являются элементами декартова произведения X ´ X. Отношение «меньше» на множестве Х является подмножеством декартова произведения X ´ X: R Ì X ´ X. Пусть R1 Ì A ´ C – отношение между A и C, а R2 Ì С ´ B – отношение между C и B. Композицией двух отношений R1 и R2 называется отношение R Ì A ´ B между A и B, определяемое следующим образом:
Другими словами,
Теорема ‑ Пусть R Ì A ´ А, тогда: 1) R рефлексивно тогда и только тогда, когда I Ì R; 2) R симметрично тогда и только тогда, когда R = R‑ 1; 3) R транзитивно тогда и только тогда, когда 4) R антисимметрично тогда и только тогда, когда RÇ R‑ 1Ì I; 5) R антирефлексивно тогда и только тогда, когда R Ç I = Æ; 6) R линейно тогда и только тогда, когда R È I È R‑ 1 = U. Пример ‑ Пусть бинарное отношение R на M задано в виде диаграммы, состоящей из узлов и стрелок так, что узлам взаимно однозначно соответствуют элементы множества М, а стрелкам, соединяющим пару а и b в направлении от а к b, ‑ наличие отношения a R b. Определить графические особенности диаграммы в зависимости от характера свойств отношения R. Отношение Отношение R антирефлексивно, если ни для каких а Отношение R симметрично, если из a R b следует b R а. В диаграмме симметричного отношения для каждой стрелки, соединяющей два узла, существует также стрелка, соединяющая эти узлы в обратном направлении. Отношение R антисимметрично, если из a R b и b R a следует а = b. В диаграмме антисимметричного отношения не существует двух различных узлов, связанных парой (разнонаправленных) стрелок. Отношение R транзитивно, если из a R b и b R c следует a R с. В диаграмме транзитивного отношения для любых двух стрелок таких, что одна направлена от а к b, а другая – от b к с, существует стрелка, соединяющая а и с в направлении от а к с.
2.2 Задания для самостоятельной работы
Определить, является ли отношение R на множестве 1 2 3 4 5 6 7 8 9 10 Операции над графами Объединение графов Пусть G1(V1, E1) и G2(V2, E2) – произвольные графы. Объединением G1È G2графов G1 и G2 называется граф с множеством вершин V1È V2, и множеством ребер (дуг) E1È E2. Рассмотрим операцию на примере графов G1(V1, E1) и G2(V2, E2), приведенных на рисунке 1. Множества вершин первого и второго графов соответственно равны V1 = {v1, v2, v3} и V2 = {v2, v3, v4}, а множество вершин результирующего графа определится как V = V1È V2 = {v1, v2, v3, v4}. Аналогично определяем множества дуг графа: E1 = {(v1, v2), (v1, v3), (v2, v1), (v 3, v3)}. E2= {(v2, v4), (v3, v2), (v4, v2)}. E ={(v1, v2), (v1, v3), (v2, v1), (v3, v3), (v2, v4), (v3, v2), (v4, v2)}. Результирующий граф G(V, E) = G1(V1, E1)È G2(V2, E2) также приведен на рисунке 1.
Рисунок 1 – Операция объединения графов
Операция объединения обладает следующими свойствами, которые следуют из определения операции и свойств операций на множествах: G1È G2 = G2È G1 – свойство коммутативности; G1È (G2È G3) = (G1È G2)È G3 – свойство ассоциативности. Операция объединения графов может быть выполнена в матричной форме. Для графов с одним и тем же множеством вершин справедлива следующая теорема. Теорема 1. Пусть G1 и G2 – два графа (ориентированные или не ориентированные одновременно) с одним и тем же множеством вершин V, и пусть A1 и A2 – матрицы смежности вершин этих графов. Тогда матрицей смежности вершин графа G1È G2 является матрица A = A1È A2, образованная поэлементным логическим сложением матриц A1 и A2. Рассмотрим выполнение операции объединения графов, множества вершин которых не совпадают. Пусть G1(V1, E1) и G2(V2, E2) – графы без параллельных ребер и множества V1 и V2 вершин этих графов не совпадают. Пусть A1 и A2 – матрицы смежности их вершин графов. Для таких графов операция объединения может быть выполнена следующим образом. В соответствии с определением операции объединения графов найдем множество вершин результирующего графа как V1È V2. Построим вспомогательные графы G’1 и G’2, множества вершин которых есть множество V1È V2, а множество ребер (дуг) определяется множествами E1 для графа G ’1 и E2 для графа G ’2. Очевидно, что матрицы A’1 и A’2 смежности вершин этих графов могут быть получены из матриц A1 и A2 путем добавления в них дополнительных столбцов и строк с нулевыми элементами. Применив к графам G’1 и G’2 теорему 1, найдем матрицу смежности вершин графа G’1È G’2 как A’1È A’2. Очевидно, что полученной матрице смежности вершин соответствует граф, множество вершин которого равно V1È V2, а множество ребер определяется, как E1È E2, что соответствует операции объединения графов. Пример ‑ Выполнить в матричной форме операцию объединения графов G1 и G2, представленных на рисунке 1. Составим матрицы смежности вершин графов.
Множество вершин результирующего графа V1È V2 = {v1, v2, v3, v4}. Составим матрицы смежности вершин вспомогательных графов G’1 и G’2.
Матрица A = A’1È A’2 имеет вид
Полученная матрица смежности вершин A’1È A’2 соответствует графу G1È G2, изображенному на рисунке1. Пересечение графов Пусть G1(V1, E1) и G2(V2, E2) – произвольные графы. Пересечением G1Ç G2 графов G1 и G2 называется граф с множеством вершин V1Ç V2 и множеством ребер (дуг) E = E1Ç E2. Операция пересечения обладает следующими свойствами, которые следуют из определения операции и свойств операций на множествах: G1Ç G2 = G2Ç G1 – свойство коммутативности; G1Ç (G2Ç G3) = (G1Ç G2)Ç G3 – свойство ассоциативности. Для того, чтобы операция пересечения была всеобъемлющей, необходимо ввести понятие пустого графа. Граф G( V, E) называется пустым, если множество V вершин графа является пустым (V = Æ ). Заметим, что в этом случае и множество E ребер (дуг) графа также пустое множество (E = Æ ). Пустой граф обозначается символом Æ. Такой граф может быть получен в результате выполнения операции пересечения графов, у которых V1Ç V2=Æ. В этом случае говорят о непересекающихся графах. Рассмотрим выполнение операции пересечения графов, изображенных на рисунке 2.
Рисунок 2 – Операция пересечения графов
Для нахождения множества вершин результирующего графа запишем множества вершин исходных графов и выполним над этими множествами операцию пересечения: V1 = {v1, v2, v3}; V2 = {v1, v2, v3, v4}; V = V1Ç V2 = {v1, v2, v3}. Аналогично определяем множество E дуг результирующего графа: E1 = {(v1, v2), (v1, v3), (v2, v1), (v2, v3), (v3, v2)}; E2 = {(v1, v3), (v2, v1), (v2, v3), (v2, v4), (v3, v1)}; E = E1Ç E2 = {(v1, v3), (v2, v1)}. Графы G1(V1, E1), G2(V2, E2) и их пересечение приведены на рисунке 2. Операция пересечения графов может быть выполнена в матричной форме. Теорема 2. Пусть G1 и G2 – два графа (ориентированные или неориентированные одновременно) с одним и тем же множеством вершин V, и пусть A1 и A2 – матрицы смежности вершин этих графов. Тогда матрицей смежности вершин графа G1Ç G2 является матрица A = A1Ç A2 образованная поэлементным логически умножением матриц A1 и A2. Рассмотрим выполнение операции пересечения для графов с несовпадающим множеством вершин. Пусть G1(V1, E1) и G2(V2, E2) – графы без параллельных ребер, множества V1 и V2 вершин графов не совпадают, а A1 и A2 – матрицы смежности вершин графов. В соответствии с определением операции пересечения графов найдем множество вершин результирующего графа как V1Ç V2. Построим вспомогательные графы G’1 и G’2, множества вершин которых есть множество V1Ç V2, а множество ребер (дуг) определяется множествами E’1 и E’2 всех ребер (дуг), инцидентных этим вершинам. Очевидно, что матрицы A’1 и A’2 смежности вершин этих графов могут быть получены из матриц A1 и A2 путем удаления из них столбцов и строк, соответствующих вершинам, не вошедшим во множество V1Ç V2. Применив к графам G’1 и G’2 теорему 2, найдем матрицу смежности вершин графа G’1Ç G’2 как A’1Ç A’2. Очевидно, что полученной матрице смежности вершин соответствует граф, множество вершин которого равно V1Ç V2, а множество ребер определяется, как E1Ç E2, что соответствует операции пересечения графов. Пример ‑ Выполнить в матричной форме операцию пересечения графов G1 и G2, представленных на рисунке 2. Составим матрицы смежности вершин исходных графов.
Находим множество вершин V результирующего графа: V = V1Ç V2 = {v1, v2, v3}. Составим матрицы смежности вершин вспомогательных графов G’1 и G’2.
Найдем матрицу смежности вершин A = A1Ç A2
Полученная матрица смежности вершин A’1Ç A’2 соответствует графу G1Ç G2, изображенному на рисунке 2.
3.3 Задания для самостоятельной работы
Даны графы G1 и G2. Найти G1È G2, G1Ç G2 и их матрицы смежности вершин.
Последнее изменение этой страницы: 2019-03-20; Просмотров: 425; Нарушение авторского права страницы Главная | Случайная страница | Обратная связь | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
или {}. Обычно элементы всех множеств берутся из одного, достаточно широкого множества U, которое называют универсальным множеством или универсумом.
.
. Два множества равны, если они являются подмножествами друг друга: 
.
‑ верно, т.к. 
; 
‑ не верно, т.к. 
, но 
.
xÎ B}; 
= { x | x Ï A }. Операция дополнение подразумевает некоторый универсум U: 
; 
.
определить множество всех подмножеств множества A, т. е. булеан множества A.
.
; 
; 
; 
; 
; 
; 
; 
; 
; 
.
; 
; 
; 
; 
; 
; 
; 
; 
; 
; 2) 
; 3) 
; 4) 
; 5) 
; 
; 7) 
; 8) 
; 9) 
; 10) 
. 
‑ универсальное множество, 
, 
, 
, 
. Определить, какие элементы составляют следующее множество.
; 
; 
; 
; 
; 
; 
; 
; 
; 
. 
; 2) 
; 3) 
; 4) 
; 5) 
; 
; 7) 
; 8) 
; 9) 
; 10) 
. 
= {(a, b) | (a, b) Ï R }Ì A ´ B; 
, элементы которой определяются следующим образом: 
; 
; 
; 
; 
; 
.
.
.
; 
рефлексивно, если a R а для любых а 
М. Соответствующая диаграмма рефлексивного отношения должна содержать петли во всех узлах (т.е. стрелки, начинающиеся и заканчивающиеся в одном узле).
симметричным, антисимметричным, рефлексивным, антирефлексивным, транзитивным, линейным. Построить граф и матрицу отношения R.
.
.
.
.
.
.
.
.
.
.
; 
; 
; 
; 
; 
; 
; 
.
.
рефлексивным, симметричным, антирефлексивным, антисимметричным. Построить граф и матрицу отношения 
.
.
, 
. Найдите матрицы смежности, инцидентности: 
