Презентация на тему: Белорусский государственный университет информатики и радиоэлектроники

Белорусский государственный университет информатики и радиоэлектроники
Литература
Основные понятия теории множеств
Основные понятия теории множеств
Основные понятия теории множеств
Способы задания множеств
Операции над множествами
Операции над множествами
Операции над множествами
О сновные законы булевой алгебры множеств ( , ,  )
О сновные законы булевой алгебры множеств ( , ,  )
О сновные законы булевой алгебры множеств ( , ,  )
Отношения
Бинарные отношения (соответствия)
Бинарные отношения (соответствия)
Бинарные отношения (соответствия)
Представления б инарны х отношени й
Бинарные отношения
Операции над бинарными отношениями
Функциональные отношения
Функциональные отношения
Функциональные отношения
Бинарные отношения на множестве
Бинарные отношения на множестве
Основные понятия теории графов
Основные понятия теории графов
Основные понятия теории графов
Основные понятия теории графов
Матричные представления графа
Матричные представления графа
Части графа
Части графа
Обобщения графов
Изоморфизм графов
Изоморфизм графов
Изоморфизм графов
Изоморфизм графов
Изоморфизм графов
Циклы и разрезы
Циклы и разрезы
Циклы и разрезы
Циклы и разрезы
Циклы и разрезы
Циклы и разрезы
Циклы и разрезы
Доминирующие множества графа
Доминирующие множества графа
Независимые множества графа
Независимые множества графа
Независимые множества графа
Независимые множества графа
Независимые множества графа
Независимые множества графа
Независимые множества графа
Раскраска графа
Раскраска графа
Раскраска графа
Раскраска графа
Обходы графа
Обходы графа
Обходы графа
Обходы графа
Обходы графа
Планарные графы
Планарные графы
Планарные графы
Комбинаторные задачи и методы комбинаторного поиска
Комбинаторные задачи и методы комбинаторного поиска
Комбинаторные задачи и методы комбинаторного поиска
Комбинаторные задачи и методы комбинаторного поиска
Комбинаторные задачи и методы комбинаторного поиска
Комбинаторные задачи и методы комбинаторного поиска
Комбинаторные задачи и методы комбинаторного поиска
Задача о кратчайшем покрытии
Задача о кратчайшем покрытии
Задача о кратчайшем покрытии
Задача о кратчайшем покрытии
Задача о кратчайшем покрытии
Булевы функции
Булевы функции
Булевы функции
Булевы функции
Булевы функции
Булевы функции
Булевы функции
Булевы функции
Булевы функции
Булевы функции
Булевы функции
Булевы функции
Булев а алгебра
Булев а алгебра
Булев а алгебра
Интерпретации алгебры логики
Интерпретации алгебры логики
Булевы функции. Операции над характеристическими множествами
Нормальные формы
Нормальные формы
Нормальные формы
Нормальные формы
Нормальные формы
Функциональная полнота
Функциональная полнота
Реализация б улевы х функци й комбинационными схемами
Реализация б улевы х функци й комбинационными схемами
Реализация б улевы х функци й комбинационными схемами
Булевы функции. Графическое представление
Булевы функции. Графическое представление
Булевы функции. Графическое представление
Булевы функции. Карта Карно
Булевы функции. Карта Карно
Булевы функции. Карта Карно
Булевы функции. Карта Карно
Булевы функции. Карта Карно
Булевы функции. Карта Карно
Булевы функции. Карта Карно
Булевы функции. Карта Карно
Булевы функции. Карта Карно
Булевы функции. Карта Карно
Булевы функции. Карта Карно
Троичные векторы и матрицы
Троичные векторы и матрицы
Троичные векторы и матрицы
Троичные векторы и матрицы
Троичные векторы и матрицы
Анализ троичной матрицы на вырожденность
Анализ троичной матрицы на вырожденность
Анализ троичной матрицы на вырожденность
Анализ троичной матрицы на вырожденность
Локальные упрощения ДНФ
Локальные упрощения ДНФ
Локальные упрощения ДНФ
Локальные упрощения ДНФ
Локальные упрощения ДНФ
Минимизация ДНФ
Минимизация ДНФ
Минимизация ДНФ
Минимизация ДНФ
Минимизация ДНФ
Минимизация ДНФ
Минимизация ДНФ
Минимизация ДНФ
Минимизация ДНФ
Минимизация ДНФ
Минимизация ДНФ
Минимизация ДНФ
Минимизация ДНФ
Минимизация ДНФ
Минимизация ДНФ
Минимизация ДНФ
Минимизация ДНФ
Минимизация ДНФ
Минимизация ДНФ
Минимизация ДНФ
Минимизация ДНФ
Минимизация ДНФ
Минимизация ДНФ
Минимизация ДНФ
Минимизация ДНФ
Минимизация ДНФ
Минимизация не полностью определенных булевых функций
Минимизация не полностью определенных булевых функций
Минимизация не полностью определенных булевых функций
Минимизация не полностью определенных булевых функций
Минимизация слабо определенной функции
Минимизация слабо определенной функции
Минимизация слабо определенной функции
Минимизация слабо определенной функции
Минимизация слабо определенной функции
Минимизация слабо определенной функции
Минимизация слабо определенной функции
Минимизация слабо определенной функции
Минимизация слабо определенной функции
1/173
Средняя оценка: 4.8/5 (всего оценок: 49)
Код скопирован в буфер обмена
Скачать (916 Кб)
1

Первый слайд презентации: Белорусский государственный университет информатики и радиоэлектроники

Дискретная математика

Изображение слайда
2

Слайд 2: Литература

1. А.Д. Закревский, Ю.В. Поттосин, Л.Д. Черемисинова. Логические основы проектирования дискретных устройств. – М.: Физматлит, 2007. – 589 c. 2. А.Д. Закревский, Ю.В.   Поттосин, Л.Д. Черемисинова. Основы логического проектирования. В 3 кн игах. – Минск: ОИПИ НАН Беларуси, 2004, 2004, 2006. – 226 с., 240 с., 254 с. 3. Ю.В. Поттосин. Основы теории проектирования цифровых устройств. – Saarbr ü cken : LAP LAMBERT Academic Publishing, 2011. – 336 c. 4. Электронный учебно-методический комплекс «Дискретная математика». – БГУИР. – 2012.

Изображение слайда
3

Слайд 3: Основные понятия теории множеств

а является элементом множества М : а      М. а не принадлежит М : а      М или а     М. А является подмножеством множества В : А     В. А  =  В, если А     В и В     А.  – пустое множество.       М для любого М.  и М – несобственные подмножества множества М. Если А     В и А     В, то А – собственное подмножество множества М, А     В. 2 М – множество всех подмножеств множества М, булеан. Среди элементов булеана 2 М находятся  и М.

Изображение слайда
4

Слайд 4: Основные понятия теории множеств

| М | – мощность множества М (число элементов). 2  М  – мощность булеана множества М. Мощность бесконечного множества выражается через соответствие. Если | А | = | В |, то между множества ми А и В можно установить взаимно однозначное соответствие. Для бесконечных множеств отношение равномощности устанавливается путем нахождения взаимно однозначного соответствия между их элементами.

Изображение слайда
5

Слайд 5: Основные понятия теории множеств

Примеры бесконечных множеств: N     {1, 2, … } – множество натуральных чисел ; Z     { … , – 2, – 1, 0, 1, 2, … } – множество целых чисел R – множество действительных чисел (рациональные и иррациональные числа). Множества, равномощные с множеством N, называются счетными. Множество P положительных рациональных чисел счетно. М ножество всех действительных чисел отрезка [0, 1] несчетно. Это континуум. Булеан бесконечного счетного множества также не является счетным множеством.

Изображение слайда
6

Слайд 6: Способы задания множеств

Перечисление элементов : А     { а 1,  а 2, … ,  а п }. Указание свойств элементов : М     { х  /  х     2 k,  k      N } – множество натуральных степеней двоек. Индуктивный способ : бесконечно е множеств о М     {1,   2, 4, 8, 16, …} задается следующ им образом : 1) 1     М ; 2) если т      М, то 2 т      М. Алгебраический способ. Визуальное представление множеств (д иаграмм ы Эйлера–Венна ). Булевы векторы. В водится универсальное множество U ( универсум ). Если U     { a,   b,  c,  d,  e } и М     { a,   b,  d }. Тогда М задается вектором 11010.  и U задаются векторами 00000 и 11111

Изображение слайда
7

Слайд 7: Операции над множествами

Объединение множеств А и В : А      В     { x      x      A или x      В }. Пересечением множеств А и В : А      В     { x      x      A и x      В }. Разность множеств А и В : А  \  В     { x      x      A и x      В }. Сумма или симметрическ ая разность множеств А и В : А  +  В     { x      ( x      A и x      В ) или ( x      В и x      А )}. Дополнение множества А :  А     { x      x      U и x      А }.

Изображение слайда
8

Слайд 8: Операции над множествами

Диаграммы Эйлера-Венна

Изображение слайда
9

Слайд 9: Операции над множествами

Некоторые операции выражаются через другие: А  +  В     ( А     В )    (  А      В )    ( А      В ) \ ( А      В );  А      U  \  А ; A  \  B      A     B. Операции ,  и  составляют булеву алгебру множеств.

Изображение слайда
10

Слайд 10: О сновные законы булевой алгебры множеств ( , ,  )

Коммутативность : А      В      В      А ; А В      В А. Ассоциативность : А     ( В      С )    ( А      В )     С ; А  ( В С )    ( А В )  С. Дистрибутивность : А  ( В      С )     А   В      А   С ; А      В   С     ( А      В ) ( А      С ). Идемпотентность : А      А      А ; А А      А. Законы де Моргана : =  А  В ; =  А     В.

Изображение слайда
11

Слайд 11: О сновные законы булевой алгебры множеств ( , ,  )

Законы операций с константами (  и U ) : А            А ; А   U      А ; А      U      U ; А          ; А     А      U ; А  А      . Закон двойного дополнения :    А. П ринцип двойственности.

Изображение слайда
12

Слайд 12: О сновные законы булевой алгебры множеств ( , ,  )

Вывод формулы А      В   С     ( А      В ) ( А      С ): По закону дистрибутивности пересечения: ( А      В ) ( А      С ) = АА  ВА  АС  ВС. Ис пользуем константу U и закон идемпотентности : А   А      А     А   U ; АА  ВА  АС  ВС = А   U  ВА  АС  ВС. Выносим за скобки А и используем формулу А      U      U : А   U  ВА  АС  ВС = А  ( U      В      С )     В   С = А      В   С.

Изображение слайда
13

Слайд 13: Отношения

А      В – декартово произведение множеств А и В. А      В = { ( a,   b ) /   a      A, b      В } Если А =  { a,   b,   c } и B  =  { l,   m }, т о А      В =  {( a,   l ), ( b,   l ), ( c,   l ), ( a,   m ), ( b,   m ), ( c,   m )}. R    R  =  R 2 – множество координат точек на плоскости. Обобщение: А 1  А 2  …  А п = {( а 1,  а 2, …,  а п ) / а 1  A 1,  а 2  A 2, …,  а п  A п }. Отношения: унарное R      А ; бинарное R      А 1      А 2 ; тернарное R      А 1      А 2      А 3 ; п -арное R      А 1      А 2     …     А п.

Изображение слайда
14

Слайд 14: Бинарные отношения (соответствия)

R      А      В. ( a,   b )    R можно записывать как a R b – а и b находятся в отношении R. Пример: a R b – a есть делитель b. Пусть А  = {1, 2, 3} и B   = {1, 2, 3, 4, 5, 6}. Тогда R   =   {(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 2), (2, 4), (2, 6), (3, 3), (3, 6)}.

Изображение слайда
15

Слайд 15: Бинарные отношения (соответствия)

А  = {1, 2, 3} и B   = {1, 2, 3, 4, 5, 6}. R   =   {(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 2), (2, 4), (2, 6), (3, 3), (3, 6)}. Элемент а – проекция элемента ( a, b ) множества А      В на А. Проекция множества Е      А      В на А – множество всех тех элементов из А, которые являются проекциями элементов из Е на множество А. Проекцией элемента (2, 4) на множество А является элемент 2, а проекцией множества {(1, 2), (2, 2), (2, 4)} – множество {1, 2}. Сечение R ( a ) множества R      А      В по а – множество всех тех элементов у      В, для которых ( a,   у )    R. Сечение R ( Х ) множества R по Х      А – объединение сечений для всех элементов из Х. R (2) = {2, 4, 6 }, а если Х  = {2, 3}, то R ( Х ) = {2, 3, 4, 6}.

Изображение слайда
16

Слайд 16: Бинарные отношения (соответствия)

Область определения отношения R      А      В – проекция множества R на А. Область значений отношения R      А      В – сечение множества R по А. Если А  = { a 1,  a 2,  a 3 }, B   = { b 1,  b 2,  b 3,  b 4 } и R   =   {( a 1, b 1 ), ( a 1, b 3 ), ( a 3, b 3 ), ( a 3, b 4 )}, то { a 1,  a 3 } – область определения, { b 1,  b 3,  b 4 } – область значений. { b   /   b      В, х      Х, ( х,  b )     R } – образ множества Х      А относительно R. { a   /   a      A, y      Y, ( a,   y )     R } – прообраз множества Y      В относительно R. Образом множества { a 1,  a 3 } относительно R является { b 1,  b 3,  b 4 }, а прообразом множества { b 3,  b 4 } является { а 1,  а 3 }.

Изображение слайда
17

Слайд 17: Представления б инарны х отношени й

О тношение R между элементами множеств A      { a 1,   a 2,   a 3 } и B      { b 1,   b 2,   b 3,   b 4,   b 5 } : R      {( a 1,   b 1 ), ( a 1,   b 2 ), ( a 1,   b 3 ), ( a 1,   b 5 ), ( a 2,   b 2 ), ( a 2,   b 4 ), ( a 3,   b 3 )}. Матричное представление Графическое представление

Изображение слайда
18

Слайд 18: Бинарные отношения

Обратн ое отношение R  – 1 для отношения R      А      В : R  – 1      {( b, a ) / ( a,   b )  R }. M ( R ) =, M ( R  – 1 ) = M T ( R ) =.

Изображение слайда
19

Слайд 19: Операции над бинарными отношениями

Применимы все операции над множествами. Композиция отношений: Заданы А, В, С и R      А      В и S      В      С. Это такое отношение между элементами множеств А и С, что для всех а      А сечение множества SR по а совпадает с сечением множества S по подмножеству R ( a )      B. R =, S =, SR =.

Изображение слайда
20

Слайд 20: Функциональные отношения

R      А      В является функциональным отношение м, если |{( a,  b ) / ( a,  b )     R, b      B }|    1 для каждого а      А. С ним связана функция f   :  A      B. Используется запись f ( x ) = y для ( х, у )    R. х – аргумент. у – значение функции f. f ( a ) = f ( c ) = b ; f ( b ) = f ( e ) = d ; f ( d ) = e. Если R  – 1 для функционального R, также функциональн ое, то R – взаимно однозначн ое отношение.

Изображение слайда
21

Слайд 21: Функциональные отношения

Для функции f   :  A      B { x   /   ( x,  y )     R } – область определения функции f. Если это множество совпадает с А, то f является всюду определенной. Это отображение А в В. В противном случае функция частичная. { у   /   ( x,  y )     R } – область значений функции f. Если она совпадает с В, то f – отображение А на В, сюръективное отображение, или сюръекция. Необходимо  А        В . Если отношение R      А      В, определяющее f, является взаимно однозначным, то f называют инъективным отображением, или инъекцией. В этом случае существует функция f   – 1, которая является обратной к f. При этом если у  =  f  ( x ), то х  =  f   – 1 ( у ), а мощность области определения функции f не должна превышать  В . Функция f называется биективным отображением, или биекцией, если она является как сюръективным, так и инъективным отображением. Такое отображение называется еще 1-1 соответствием.

Изображение слайда
22

Слайд 22: Функциональные отношения

Сюръекция Инъекция Биекция

Изображение слайда
23

Слайд 23: Бинарные отношения на множестве

R      А      А. Возможные свойства: рефлексивность : если a   =   b, то a   R   b ; иррефлексивность : если a   R   b, то a      b ; симметричность : если a   R   b, то b   R   a ; антисимметричность : если a   R   b и b   R   a, то a   =   b ; транзитивность : если a   R   b и b   R   с, то a   R   с ; дихотомия : если a      b, то либо a   R   b, либо b   R   a.

Изображение слайда
24

Слайд 24: Бинарные отношения на множестве

Т ипы бинарных отношений : Отношение э квивалентност и рефлексивн о, симметричн о и транзитивно ( равносильность формул, подобие геометрических фигур и т. п. ). Классы эквивалентности. Отношение совместимости рефлексивно и симметрично ( близость чисел, знакомство людей и т. п. ). Отношение нестрогого порядка рефлексивно, антисимметрично и транзитивно ( , , ,  ). Отношение строгого порядка иррефлексивно, антисимметрично и транзитивно ( , , ,  ). Порядок полный ( линейны й ), порядок частичный. Л ексикографический порядок.

Изображение слайда
25

Слайд 25: Основные понятия теории графов

G   =   ( V,  E ), V – непустое множество вершин, Е – произвольное множество реб е р – пар ( v i,  v j ) элементов из V, т. е. v i      V, v j      V, Е      V  2. Неориентированный Ориентированный ( орграф )

Изображение слайда
26

Слайд 26: Основные понятия теории графов

Ребро е 2      v 1 v 3 имеет концы v 1 и v 3. Ориентированное ребро ( дуга ) a 4   =   ( v 3,   v 2 ) имеет начало v 3 и конец v 2 (дуга a 4 исходит из v 3 и заходит в v 2 ). В неориентированном графе v и ребро е инцидентны, если v – один из концов ребра е. В орграфе v и дуга а инцидентны, если v – либо начало, либо кон е ц дуги а.

Изображение слайда
27

Слайд 27: Основные понятия теории графов

В неориентированно м граф е д ве вершины смежны, если они инцидентны одному и тому же ребру. О крестность N ( v ) вершины v – м ножество всех вершин, смежных v. |N ( v ) | = d ( v ) – степень вершины v. В орграфе: полуокрестность исхода N   + ( v ): полуокрестность за хода N   ‑ ( v ). Полустепени d + ( v ), d ‑ ( v ).

Изображение слайда
28

Слайд 28: Основные понятия теории графов

Г раф ы конечны е, графы бесконечные. Граф G   =   ( V,  E ) пуст ой, если Е      . Неориентированный граф полны й, если любые две его вершины смежны. K n – полный п -вершинный граф.  G   =   ( V,  E ) – д ополнение графа G   =   ( V,  E ),  E   =   U   \   E, где U – множество ребер полного графа с множеством вершин V. Д вудольны й граф G   =   ( V ,  V ,  E ) – для любого е = ху      Е : х      V , у      V . Дерево – связный граф без циклов.

Изображение слайда
29

Слайд 29: Матричные представления графа

М атриц а смежности

Изображение слайда
30

Слайд 30: Матричные представления графа

М атриц а инцидентности

Изображение слайда
31

Слайд 31: Части графа

Н  = ( W,   F ) – подграф графа G  = ( V,   E ), если W      V, F      E. Н  = ( W,   F ) – остовный подграф, если W   =   V. Н  = ( W,   F ) – подграф, порожденны й множеством W, если F содержит все ребра, оба конца которых принадлежат W. v 1,   e 1,   v 2,   e 2,   …,   e k,   v k   +   1 – маршрут, e i  =  v i v i   +   1, i  = 1,   2,   …,   k. Длин а маршрута – количество ребер. Ц епь – м аршрут, все ребра которого различны. П рост ая цепь – ц епь, все вершины которой различны. Р асстояни е между вершинами – длина кратчайшей цепи.

Изображение слайда
32

Слайд 32: Части графа

Маршрут v 1,   e 1,   v 2,   e 2,   …  ,   e k,   v 1 – циклически й. Ц икл – ц иклическая цепь. Простой цикл. Граф связны й, если любы е дв е его вершин ы связаны цепь ю. К омпонент а связности графа – с вязный подграф, не содержащийся ни в каком другом его связном подграфе. В орграфе : v 1,   а 1,   v 2,   а 2,   …  ,   а k,   v k   +   1 – маршрут, если а i  =  ( v i, v i   +   1 ). Путь – маршрут, где все вершины различны. v 1,   а 1,   v 2,   а 2,   …  ,   а k,   v 1 – контур. Вершина v j достижим а из v i, если имеется путь из v i в v j. Орг раф сильно связны й, если любая вершина достижима из любой вершины.

Изображение слайда
33

Слайд 33: Обобщения графов

М ультиграф – граф, в котором любые две вершины могут быть связаны любым количеством ребер (допускает кратные ребра). В звешенны й граф – вершины и/или ребра снабжаются весами в виде действительных чисел. С мешанны й граф – наряду с элементами ориентированного графа (дугами) имеются элементы неориентированного графа (ребра). Г иперграф. Е сли ребром графа является пара вершин, то ребром гиперграфа может быть любое непустое подмножество множества вершин. О т гиперграфа можно перейти к двудольному графу, долями которого являются множество вершин и множество ребер гиперграфа, а ребра показывают принадлежность вершин гиперграфа его ребрам.

Изображение слайда
34

Слайд 34: Изоморфизм графов

Два графа G  = ( V,   Е ) и H  = ( W,   F ) изоморфны, если между их множествами вершин имеется взаимно однозначное соответствие, сохраняющее отношение смежности.    :   V     W,    :   E      F, и если   ( v i )     w k и  ( v j )     w l, то  ( v i v j )     w k w l. v 1 v 2 v 3 w 1 w 2 w 3 w 4 v 4 v 5 v 6 w 5 w 6  ( v 1 )      w 1,  ( v 2 )      w 3,  ( v 3 )      w 6,  ( v 4 )      w 4,  ( v 5 )      w 5,  ( v 6 )      w 2.  ( v 1 v 4 )      w 1 w 4,  ( v 1 v 5 )      w 1 w 5,  ( v 1 v 6 )      w 1 w 2,  ( v 2 v 4 )      w 3 w 4,  ( v 2 v 5 )      w 3 w 5,  ( v 2 v 6 )      w 2 w 3,  ( v 3 v 4 )      w 4 w 6,  ( v 3 v 5 )      w 5 w 6,  ( v 3 v 6 )      w 2 w 6.

Изображение слайда
35

Слайд 35: Изоморфизм графов

Канонизация графа Величина а инвариантна относительно преобразования Т, если она не меняет свое значение при преобразовании Т. а называется инвариантой относительно Т. В нашем случае Т – перенумерация вершин. Инварианты графа: число вершин, число ребер, число компонент связности… Инварианты вершины: степень, полустепени, число вершин, отстоящих от данной вершины на определенном расстоянии… Канонизация графа заключается в упорядочении его вершин по значениям инвариант. Пусть для вершин графа имеется система инвариант  1,   2, … ,   р. Считаем, что задано отношение частичного порядка на множестве вершин графа V   =   { v 1,  v 2, … ,  v n }, такое, что v i v j, если  k ( v i )       k ( v j ) для некоторого k      {1,   2,   …  ,   р ) и  l ( v i )   =    l ( v j ) для всех l      k.

Изображение слайда
36

Слайд 36: Изоморфизм графов

Канонизация графа Полная канонизация графа достигается, когда порядок оказывается полным и строгим. Разобьем множество V вершин графа G на подмножества S 1,  S 2,   …  ,  S m, число т которых равно числу различных степеней вершин и в каждом из которых присутствуют вершины с одинаковой степенью. Инварианта вершины v i      V – вектор размерности т, компоненты которого соответствуют множествам S 1,   S 2,   …  ,   S m и значением j -й компоненты является число вершин из множества S j, смежных с v i. Если в одном и том же S k ( k   =   1,   2,   …  ,   m ) оказались вершины с различными векторами, то разобьем это S k так, чтобы в каждом из получившихся множеств оставались вершины с одинаковыми векторами, соответственно увеличив размерность векторов и придав их компонентам новые значения.

Изображение слайда
37

Слайд 37: Изоморфизм графов

Канонизация графа v 1 v 2 v 4 v 3 v 5 v 6

Изображение слайда
38

Слайд 38: Изоморфизм графов

Пример однородных неизоморфных графов

Изображение слайда
39

Слайд 39: Циклы и разрезы

Цикломатическое число графа Дерево – это связный граф, число ребер которого на единицу меньше числа вершин. Дерево – это связный граф, не имеющий циклов. Дерево – это граф, в котором каждая пара вершин связана одной и только одной цепью. Лес – граф, каждая компонента связности которого является деревом. Пусть G – неориентированный граф с п вершинами, т ребрами и р компонентами связности. Остовное дерево – остовный подграф в виде дерева связного графа ( р  = 1). Число ребер в остовном дереве п  – 1. Число ребер в остовном лесе п  –  р.  ( G )      m   –   n      p – цикломатическое число  ( G )      n   –   p – коцикломатическое число.

Изображение слайда
40

Слайд 40: Циклы и разрезы

Базис циклов Т – остовное дерево связного графа G   =   ( V,   E ). Добавление одного ребра из Е к Т приводит к появлению точно одного простого цикла. m   –   n      1 – число таких циклов в графе G. Оно совпадает с  ( G ). Эти циклы независимы (каждый из них имеет ребро, не принадлежащее никакому другому). Фундаментальные циклы. Они составляют базис циклов графа G. Любой цикл, не принадлежащий базису, может быть выражен в виде линейной комбинации фундаментальных циклов. Всякий цикл графа G представим т -мерным булевым вектором, в котором i -я компонента имеет значение 1 или 0 в зависимости от того, принадлежит или нет i -е ребро данному циклу. Любой цикл можно выразить как покомпонентную сумму по модулю 2 векторов, представляющих фундаментальные циклы. Сумма по модулю 2: 0    0    0, 0    1    1, 1    0    1, 1    1    0.

Изображение слайда
41

Слайд 41: Циклы и разрезы

Базис циклов v 2 v 3 е 3 е 5 е 1 е 4 е 6 v 4 е 7 v 1 е 2 v 5 Фундаментальные циклы: v 1, е 1, v 2, е 3, v 3, е 6, v 5, е 2, v 1 ; v 2, v 3, v 5 ; v 3, v 4, v 5. е 1 е 2 е 3 е 4 е 5 е 6 е 7 е 1 е 2 е 3 е 4 е 5 е 6 е 7 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 0 0 0 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 0 1 1 1 0 1 1 1 1

Изображение слайда
42

Слайд 42: Циклы и разрезы

Базис разрезов v 2 v 3 е 3 е 5 е 1 е 4 е 6 v 4 е 7 v 1 е 2 v 5 Разрез графа – множество ребер, удаление которых увеличивает число компонент связности. Под разрезом будем понимать минимальный разрез, т.е. такой, что при удалении из него любого ребра он перестает быть разрезом. Фундаментальный разрез содержит одно и только одно ребро е, принадлежащее остовному дереву Т. Кроме е, он содержит все ребра, не принадлежащие Т, но входящие в фундаментальные циклы, содержащие е.

Изображение слайда
43

Слайд 43: Циклы и разрезы

Базис разрезов v 2 v 3 е 3 е 5 е 1 е 4 е 6 v 4 е 7 v 1 е 2 v 5 Базис разрезов – множество фундаментальных разрезов. е 1 е 2 е 3 е 4 е 5 е 6 е 7 0 1 1 1 0 0 0 0 1 0 1 0 1 1 0 0 1 0 0 1 1

Изображение слайда
44

Слайд 44: Циклы и разрезы

Матрицы циклов и разрезов v 2 v 3 е 3 е 5 е 1 е 4 е 6 v 4 е 7 v 1 е 2 v 5 Матрица фундаментальных циклов Матрица фундаментальных разрезов

Изображение слайда
45

Слайд 45: Циклы и разрезы

Матрицы циклов и разрезов Матрица фундаментальных циклов Матрица фундаментальных разрезов

Изображение слайда
46

Слайд 46: Доминирующие множества графа

S – доминирующее множество ( S      V ), если S      N ( S )      V, где N ( S )   . Если S – доминирующ ее множество некоторого графа G, то всякое S       S также является доминирующим. М инимальн ое доминирующ ее множеств о – ни одно его собственное подмножество не является доминирующим. Н аименьш ее доминирующ ее множеств о – имеет наименьшую мощность  ( G ).  ( G ) – число доминирования графа G. Задача о ферзях.

Изображение слайда
47

Слайд 47: Доминирующие множества графа

v 2 v 3 v 1 v 4 v 7 v 6 v 5 Строка v i матрицы представляет множество { v i }  N ( v i ). Минимальные доминирующие множества: { v 1,  v 3, v 5 }, { v 1,  v 3, v 6 }, { v 1,  v 4, v 5 }, { v 1,  v 4, v 6 }, { v 2,  v 3, v 5 }, { v 2,  v 3, v 6 }, { v 2,  v 4, v 5 }, { v 2,  v 4, v 6 }, { v 3, v 7 }, { v 5, v 7 } и { v 6, v 7 }.

Изображение слайда
48

Слайд 48: Независимые множества графа

S – независим ое множество ( S      V ), если S      N ( S )      . Если S – независим ое множество некоторого графа G, то всякое S       S также является независим ы м. Макси мальн ое независим ое множеств о – не является собственн ым подмножество м ни одно го независим ого множества. Н аи бол ьш ее независим ое множеств о – имеет наибольшую мощность  ( G ).  ( G ) – число независим ости графа G. Задача о ферзях.

Изображение слайда
49

Слайд 49: Независимые множества графа

v 2 v 3 v 1 v 4 v 7 v 6 v 5 Максимальные независим ые множеств а: { v 1, v 3, v 6 }, { v 1, v 4, v 5 }, { v 1, v 4, v 6 }, { v 2, v 4, v 5 }, { v 2, v 4, v 6 }, { v 5, v 7 }

Изображение слайда
50

Слайд 50: Независимые множества графа

Нахождение всех максимальных независимых множеств V      { v 1,   v 2,   …  ,   v n } – множество вершин граф а G   =   ( V, Е ). G 1,   G 2,   …  ,   G n – последовательность порожденных подграфов : G i   =   ( V i, Е i ), где V i   =   { v 1,   v 2,   …  ,   v i } ( i   =   1,   2,   …  ,   n ). S  i   =   { S 1 i,   S 2 i,   …  , } – совокупность всех максимальных независимых множеств графа G i. К каждому S j i ( j   =   1,   2,   …  ,   k i ) применяется формула S      ( S j i  \  N ( v i     1 ))    { v i     1 }.

Изображение слайда
51

Слайд 51: Независимые множества графа

Сколько всего может быть максимальных независимых множеств в графе с п вершинами ? 2 · 3 k   –   1, если п  = 3 k   –   1; 3 · 3 k   –   1, если п  = 3 k ; 4 · 3 k   –   1, если п  = 3 k   +   1. …

Изображение слайда
52

Слайд 52: Независимые множества графа

Н ахождени е наибольшего независимого множества. Вершинн ое покрытие графа G  = ( V,   E ) – множество В      V такое, что каждое ребро из Е инцидентно хотя бы одной вершине из В. Е сли В – наименьшее вершинное покрытие, то V   \   B  – наибольшее независимое множество. v 2 е 3 v 3 е 1 е 4 е 7 е 5 v 1 е 2 е 8 v 4 е 10 v 7 е 6 v 6 е 9 v 5 В   =  { v 1,   v 3,  v 5,  v 7 }, V   \   B   =  { v 2,   v 4,  v 6 }.

Изображение слайда
53

Слайд 53: Независимые множества графа

Н ахождени е наибольшего независимого множества. «Жадный» алгоритм. v 3 v 3 v 2 v 1 v 4 v 4 v 5 v 5 v 6 v 7 v 7 v 7 v 8 v 8 v 8 v 9 v 9 v 9 { v 1 } { v 1, v 3 } { v 1, v 3, v 7 }

Изображение слайда
54

Слайд 54: Независимые множества графа

Н ахождени е наибольшего независимого множества. «Жадный» алгоритм. v 3 v 2 v 1 v 4 v 1 v 2 v 5 v 6 v 7 v 6 v 7 v 6 v 7 v 8 v 8 v 8 v 8 v 9 v 9 v 9 v 9 { v 4 } { v 2, v 4 } { v 2, v 4, v 6 } { v 2, v 4, v 6, v 8 }

Изображение слайда
55

Слайд 55: Раскраска графа

Раскраск а графа G  = ( V,   Е ) – такое разбиение множества V на непересекающиеся подмножества V 1,  V 2,   …  ,   V k, что никакие две вершины из любого V i ( i = 1, 2, …, k ) не смежны. Задача : раскрасить вершины графа G в минимальное число цветов.  ( G ) – хроматическ ое число графа G (минимум k ). Л юбо е V i ( i = 1, 2, …, k ) – независимое множество. Раскраск а V 1,  V 2,   …  ,   V k – совокупность независимых множеств.

Изображение слайда
56

Слайд 56: Раскраска графа

Неточность «жадного» алгоритма видна на последовательности: ,,, … Граф G является k -хроматическим, если  ( G ) =  k. Т е о р е м а К ё н и г а. Непустой граф является бихроматическим тогда и только тогда, когда он не содержит циклов нечетной длины.

Изображение слайда
57

Слайд 57: Раскраска графа

Метод раскраски графа k – число задействованных цветов; А – множество еще не раскрашенных вершин; В 1,  В 2,   …  ,   В k – совокупность подмножеств множества вершин V, такая, что B i ( i  = 1, 2,   …  ,   k ) содержит те и только те вершины из множества А, которые нельзя раскрасить в i -й цвет. 1. Имеется вершина v      A, такая, что v      B i для всех i  = 1, 2,   …  ,   k. v красится в ( k   +   1)-й цвет, удаляется из множества А и из всех B i. Формируется В k   +   1 и k := k + 1. Если таких вершин несколько, из них выбирается та, для которой В k   +   1 имеет максимальную мощность. 2. Имеется вершина v      A и цвет i, такие, что v      B i и N ( v )      A      B i. v красится в i -й цвет, удаляется из А и из всех B j. В остальных случаях выбираются цвет i и вершина v из А такие, что v      B i и приращение  B i  минимально среди всех пар v,   Bi ( v      A, i  = 1, 2,   …  ,   k ). Вершина v красится в i -й цвет и удаляется из А из всех B j.

Изображение слайда
58

Слайд 58: Раскраска графа

Метод раскраски графа Цвет Вершины B i 1 1 {2,6,8,10} 1 1 {6,8,10} 2 2 {4,5} 1 1 {6,10} 2 2,8 {4,5} 1 1,7 {3,6,10} 2 2,8 {4,5} 1 1,7 {3,10} 2 2,6,8 {4,5,9} 1 1,7 {10} 2 2,3,6,8 {4,5,9} 1 1,7 {10}, 1. Имеется вершина v      A, такая, 2 2,3,6,8 {4,5,9} что v      B i для всех i  = 1, 2,   …  ,   k. 1 1,7  2. Имеется вершина v      A и цвет i 2 2,3,6,8,10 {4,5,9} такие, что v      B i и N ( v )      A      B i 1 1,4,7 {5,9} 2 2,3,6,8,10 {5,9} Результат: { 1, 4, 7 }, {2,3,6,8,10}, { 5 }, { 9 }. Точный алгоритм дает { 1,3,4 }, { 2,8,9 }, { 5,6,7,10 }.

Изображение слайда
59

Слайд 59: Обходы графа

Эйлеровы цепи и циклы З адач а о кёнигсбергских мостах ( 1736 г. ) Э йлеров цикл содержи т все ребра графа. Э йлеров а цепь. Т е о р е м а Э й л е р а. Связный неориентированный граф имеет эйлеров цикл тогда и только тогда, когда степени всех его вершин четны. В связном неориентированном графе существует эйлерова цепь тогда и только тогда, когда он имеет не более двух вершин с нечетной степенью.

Изображение слайда
60

Слайд 60: Обходы графа

Эйлеровы цепи и циклы Э йлеров граф – г раф, имеющий эйлеров цикл. А лгоритм Флёри : 1. Идем из некоторой вершины по ребру и удаляем каждое пройденное ребро, помещая его в получаемую последовательность. Начальная вершина выбирается произвольно. 2. Отправляясь из очередной вершины, никогда не идем по ребру, удаление которого делает граф несвязным. З адача китайского почтальона : Каждому ребру e i графа G приписывается положительный вес с ( e i ) (расстояние). Требуется найти маршрут, проходящий через каждое ребро графа G по крайней мере один раз и такой, что сумма величин n i c ( e i ) минимальна, где n i – число прохождений ребра е i.

Изображение слайда
61

Слайд 61: Обходы графа

Гамильтоновы цепи и циклы Цикл называется гамильтоновым, если он проходит каждую вершину графа ровно один раз. Гамильтонов а цепь – цепь, проходящая каждую вершину графа ровно один раз. Граф, содержащий гамильтонов цикл, называется гамильтоновым графом. v 3 v 1 : v 2, v 4, v 5, v 6 ; ( v 1,   v 2,   v 3,   v 4,   v 6 ) v 2 : v 1, v 3, v 4, v 5 ; ( v 1,   v 2,   v 3,   v 4 ) v 5 v 4 v 3 : v 2, v 4, v 5 ; ( v 1,   v 2,   v 3 ) v 2 v 4 : v 1, v 2, v 3, v 6 ; ( v 1,   v 2,   v 3,   v 5 ) v 5 : v 1, v 2, v 3 ; ( v 1,   v 2,   v 4 ) v 6 : v 1, v 4. ( v 1,   v 2,   v 4,   v 3,   v 5 ) v 1 v 6 ( v 1,   v 2,   v 4,   v 6 ) ( v 1,   v 2,   v 5,   v 3,   v 4,   v 6,   v 1 )

Изображение слайда
62

Слайд 62: Обходы графа

Кратчайшие пути в графе Р ебра графа G   =   ( V,   E ) взвешены действительными положительными числами. Вес ребра e   =   v i v j будем считать его длиной l ( e )   =   l ( v i v j ). Н айти цепь С минимальной длины, соединяющую вершины v 1 и v n в графе G, т. е. такую цепь, для которой величина минимальна. А лгоритм Форда Каждой вершине v i      V припишем индекс  ( v i ). При этом положим  ( v 1 )      0 и  ( v i )      +    для i      1. На каждом шаге находим такое ребро v i v j, что  ( v i )   –    ( v j )      l ( v i v j ), и индекс  ( v i ) заменяе м на  ( v i )   =    ( v j )   +   l ( v i v j ). Ш аг и повторяются, пока находятся ребра, для которых выполняется неравенство  ( v i )   –    ( v j )      l ( v i v j ). П уть строи м, начиная с v п и двигаясь обратно к v 1. После вершины v i выбира ем вершину v j чтобы выполнялось  ( v i )   –    ( v j )   =   l ( v i v j ).

Изображение слайда
63

Слайд 63: Обходы графа

Кратчайшие пути в графе v 2 10 v 5 1 10 1 2 5 v 3 v 6 v 1 10 4 2 v 8 6 4 1 5 8 v 4 3 v 7 v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 ______________________________ 0        1 10 6 11 14 9 16 13 15

Изображение слайда
64

Слайд 64: Планарные графы

Граф укладывается на некоторой поверхности, если его можно так нарисовать на этой поверхности, что никакие два ребра не будут иметь общей точки, кроме, возможно, общей вершины. Граф планарны й, если его можно уложить на плоскости. Плоский граф – граф, уложенный на плоскости. Грань плоского графа – область плоскости, ограниченная ребрами, любые две точки которой могут быть соединены линией, не пересекающей ребра графа. Грани внешняя и внутренние. Т е о р е м а Э й л е р а. Для всякого связного плоского графа, имеющего f 1 f 2 f 3 п вершин, т ребер и f граней, имеет место соотношение п  –  т      f     2. (Формула Эйлера)

Изображение слайда
65

Слайд 65: Планарные графы

Максимальны й планарны й граф и п ростейшие непланарные графы Т е о р е м а П о н т р я г и н а – К у р а т о в с к о г о. Необходимым и достаточным условием непланарности графа является любое из следующих условий: 1) в графе можно выделить пять вершин, каждая из которых связана цепью с любой другой из них, причем все эти цепи не пересекаются по ребрам; 2) в графе можно выделить два множества, состоящие из трех вершин каждое, так, что каждая вершина одного множества связана цепью со всеми вершинами другого множества, причем все эти цепи не пересекаются по ребрам.

Изображение слайда
66

Слайд 66: Планарные графы

Раскраска планарных графов (раскраска карт) Плоский граф и его двойственный граф Раскраска граней плоского графа, при которой соседние грани раскрашиваются в различные цвета, эквивалентна раскраске вершин его двойственного графа. Г ипотеза четырех красок доказана с помощью ЭВМ в 1976 г. 1 482 конфигурации. 2 000 ч машинного времени.

Изображение слайда
67

Слайд 67: Комбинаторные задачи и методы комбинаторного поиска

Т ри типа комбинаторных задач: З адачи подсчета – сколько конфигураций определенного вида ? П еречислительные задачи – получение все х конструкци й определенного вида. О птимизационные комбинаторные задачи – получение конструкци и, обладающ ей оптимальным значением некоторого параметра среди всех конструкций данного вида.

Изображение слайда
68

Слайд 68: Комбинаторные задачи и методы комбинаторного поиска

З адачи подсчета: Число размещений (разместить п предметов по т ящикам) U ( m,   n )   =   т п. Число перестановок Р ( n )   =   п  · ( п  – 1) · … · 2 · 1 =  п !. Число размещений без повторений А ( m,   n )   =   т  · ( т  – 1) · … · ( т  –  п  + 1) = Число сочетаний

Изображение слайда
69

Слайд 69: Комбинаторные задачи и методы комбинаторного поиска

Особенности оптимизационных комбинаторных задач Р ешение комбинаторной задачи сводится зачастую к полному перебору различных вариантов. В елика зависимост ь трудоемкост и задачи от размера области возможных решений. М ножество, среди элементов которого отыскивается решение, всегда конечно. Реализовав полный перебор, либо найдем решение, либо убедимся в том, что решения нет.

Изображение слайда
70

Слайд 70: Комбинаторные задачи и методы комбинаторного поиска

Вычислительная сложность оптимизационных задач Трудоемкость алгоритма оцени вается функцией f ( n ), где п – натуральное число, выражающее объем исходных данных. f ( n )   =   O ( g ( n )), если найдется такая константа с, что f ( n )      с g ( n ) для любого n      0, где g ( n )  некоторая конкретная функция от n. О (1)  трудоемкость не зависит от объема исходных данных. О ( п )  а лгоритм линейны й. О ( п b )  а лгоритм полиномиальны й. g ( n ) = 2 п  а лгоритм обладает неполиномиальной, или экспоненциальной, сложностью.

Изображение слайда
71

Слайд 71: Комбинаторные задачи и методы комбинаторного поиска

Связь трудоемкости алгоритма с максимальным размером задачи, решаемой за единицу времени

Изображение слайда
72

Слайд 72: Комбинаторные задачи и методы комбинаторного поиска

Связь размера задачи, решаемой за заданное время, с быстродействием вычислительной машины

Изображение слайда
73

Слайд 73: Комбинаторные задачи и методы комбинаторного поиска

Комбинаторный поиск представляется как обход дерева поиска. Вершины соответствуют ситуациям, возникающим в процессе поиска, ребра – отдельным шагам процесса. Корень дерева – вершина, соответствующая начальной ситуации. Выделение корня придает дереву ориентацию, при которой все пути ведут из корня в остальные вершины. Некоторые ситуации соответствуют решениям.

Изображение слайда
74

Слайд 74: Задача о кратчайшем покрытии

Дано: А  = { a 1,   a 2,   …,   a n } ; В 1,   В 2,   …,   В т ; B i      A, i   =   1,   2,   …,   m, причем В 1      В 2      …      В т   =   А. Требуется выделить так, чтобы выполнялось при минимальном k. М атричн ая формулировк а: т ребуется найти наименьшее множество строк за данной булевой матрицы, чтобы каждый ее столбец имел единицу хотя бы в одной строке из этого множества.

Изображение слайда
75

Слайд 75: Задача о кратчайшем покрытии

Для матрицы { B 4,   B 6,   B 7 } – кратчайшее покрытие.

Изображение слайда
76

Слайд 76: Задача о кратчайшем покрытии

Алгоритмы решения «Жадный» алгоритм повторяет операцию: выбор строки с максимальным числом единиц, включение ее в решение и удаление ее и покрываемых ею столбцов из матрицы. Для матрицы находит покрытие { B 1,   B 2,   B 3 }, хотя кратчайшее – { B 2,   B 3 }. М инимаксн ый алгоритм повторяет операцию: выбор столбца с минимальным числом единиц, выбор покрывающей его строки с максимальным числом единиц, включение ее в решение и удаление ее и покрываемых ею столбцов из матрицы. Точный алгоритм совершает обход дерева поиска.

Изображение слайда
77

Слайд 77: Задача о кратчайшем покрытии

Обход дерева поиска a 1 B 2 B 5 a 3 B 1 B 3 B 5 a 4 a 4 [1] B 4 B 4 Одно из покрытий (не обязательно кратчайшее) – B 1, B 2, B 4.

Изображение слайда
78

Слайд 78: Задача о кратчайшем покрытии

Обход дерева поиска. Правила редукции 1. Если столбец k имеет единицы везде, где имеет единицы столбец l, то столбец k можно удалить.  2. Если строка i имеет единицы везде, где имеет единицы строка j, то строку j можно удалить. 

Изображение слайда
79

Слайд 79: Булевы функции

х 1,  х 2, ... ,  х n – булевы переменные, принимаю т значени я из {0, 1}. х = ( х 1,  х 2, ... ,  х n ) – n ‑компонентный булев вектор. п – длина вектора, или размерность. 2 п – число всех различных векторов, состоящи х из констант 0 и 1 и образующих булево пространство. f  :   {0,   1} n      {0,   1} – б улев а функци я. М  = {0,   1} n – о бласть определения, {0,   1} – область значений. M f 1 – область, где функция f принимает значение 1. M f 0 – область, где функция f принимает значение 0. M f 1 – характеристическ ое множество функции f.

Изображение слайда
80

Слайд 80: Булевы функции

Способы задания Т аблиц а истинности :

Изображение слайда
81

Слайд 81: Булевы функции

Способы задания М атричны й способ – перечисление элементов M f 1 : Более компактное задание:

Изображение слайда
82

Слайд 82: Булевы функции

Способы задания М атричны й способ ( интервальны й) – т роичная матрица : Булевы векторы а  = ( а 1,  а 2, … ,  а п ) и b  = ( b 1,  b 2, … ,  b п ) находятся в отношении  ( а      b, а меньше b ), если а i      b i   для любого i  = 1, 2, … ,  п, в противном случае они несравнимы. При этом считается, что 0    1. И нтервал булева пространства – множество векторов, среди которых есть минимальный и максимальный векторы, а также все векторы, меньшие максимального и большие минимального. И нтервал представляется троичным вектором.

Изображение слайда
83

Слайд 83: Булевы функции

Способы задания Векторное задание – булев вектор, компоненты которого соответствуют наборам значений аргументов. Функция задается вектором (0   1   1   1   0   1   0   1).

Изображение слайда
84

Слайд 84: Булевы функции

А лгебраический способ задания булев ых функци й. Карты Карно. Функции полностью определенные. Функции не полностью определенные, или частичные. Частичная булева функция делит булево пространство на три части: M f 1, M f 0 и M f  –. Обычно задаются M f 1 и M f 0.

Изображение слайда
85

Слайд 85: Булевы функции

В екторн ая форм а задания булевой функции позволяет легко определить число булевых функций от п переменных – это число всех 2 n -компонентных булевых векторов. – число булевых функций от п переменных. Функция f ( х 1,  х 2, ... ,  х n ) существенно зависит от аргумента х i, если f ( х 1,  х 2, ... ,  х i   – 1,   0,  х i  + 1,   … ,  х n )     f ( х 1,  х 2, ... ,  х i  – 1,   1,  х i  + 1,   … ,  х n ). х i – существенны й аргумент. В противном случае х i – не существенны й, или фиктивны й аргумент.

Изображение слайда
86

Слайд 86: Булевы функции

Элементарные булевы функции и алгебраические формы Элементарны е булевы функции – функции от одной и двух переменных. Булевы функции от одно й переменной Из табл ицы видно, что  0 = 1 и  1 = 0.

Изображение слайда
87

Слайд 87: Булевы функции

Булевы функции от двух переменных

Изображение слайда
88

Слайд 88: Булевы функции

Булевы функции от двух переменных Все представленные операции составляют алгебру логики.

Изображение слайда
89

Слайд 89: Булевы функции

А лгебраическ ое задани е Любая булева функция от любого числа аргументов может быть представлена формулой алгебры логики. Формулу, содержащую более чем одну операцию, можно рассматривать как суперпозицию элементарных функций, т.е. использование одних функций в качестве аргументов других функций. Определение формулы : 1) каждый символ переменной есть формула; 2) если А и В – формулы, то формулами являются  А и ( А      В ), где  – любая операция алгебры логики; 3) других формул нет. Приоритеты: 1)  ; 2)  ; 3)  и  ; 4) ~ и .

Изображение слайда
90

Слайд 90: Булевы функции

Вычисление по формуле f ( x 1,   x 2,   x 3 )   = А = В – равносильность формул А и В.

Изображение слайда
91

Слайд 91: Булев а алгебра

Б улев а а лгебра содерж ит только три операции : ,  и . О сновные законы булевой алгебры : Коммутативность : х      у      у      х ; х у      у х. Ассоциативность : х     ( у      z )    ( x      y )     z ; x  ( y z )    ( x y )  z. Дистрибутивность : x  ( y    z )     x y      x z ; x    y  z     ( x     y ) ( x      z ). Идемпотентность : x     x      x ; x   x      x.

Изображение слайда
92

Слайд 92: Булев а алгебра

О сновные законы булевой алгебры : Законы де Моргана : ; =  x    y. Законы операций с константами : x     0     x ; x  1     x ; x  0    0; x     1    1; х    х     1; х  х     0. Закон двойного отрицания : . П ринцип двойственности.

Изображение слайда
93

Слайд 93: Булев а алгебра

Вывод формул х      х   у     х и х  ( х      у )      х : х      х   у     х  1     х   у     х  (1     у )      х 1 = х ; х  ( х      у )      х х      х   у      х      х   у     х. Все операции алгебры логики можно выразить через булевы операции : х      у   =   x  y    x   y ; х   ~   у   =  x  y      x   y ; х      у   =  x      y. Преобразование формулы алгебры логики в булеву формулу: (( х      у )      ( х      z ))  y   = = (  x      y      x  z    x   z )  y   =   (  x      y    z )  y   =  x  y    y  z.

Изображение слайда
94

Слайд 94: Интерпретации алгебры логики

Булева алгебра множеств : Константам 1 и 0 соответствуют множества U и . Операциям ,  и  соответствуют ,  и  Алгебра событий, используемая в теории вероятностей: Операции отрицания (  ), объединения (  ) и пересечения (  ). А    В или АВ – произведение независимых событий, А    В – сумма несовместимых событий. И счислени е высказываний :  a – « не а ». a      b – « a либо b ». a    b – « a и b ». a   ~   b – « a равносильно b ». a    b – « a или b ». a      b – «если a, то b ».

Изображение слайда
95

Слайд 95: Интерпретации алгебры логики

Алгебра переключательных схем : а     b а b   с a b b  а    b a    b a   +   b а  b   +   b  c   +  a  b a  a a ab a a    b b b a  a  a   b b  a   b  а  b = a    b а  b  b

Изображение слайда
96

Слайд 96: Булевы функции. Операции над характеристическими множествами

Е сли f   =   f 1    f 2, то ; если f   =   f 1    f 2, то ; если f   =   f 1    f 2, то ; если f   =   f 1    f 2, то ; если f   =   f 1    f 2, то ; если f 1   =  f 2, то.

Изображение слайда
97

Слайд 97: Нормальные формы

Дизъюнктивные нормальные формы x i и  x j – литералы. О бозначи м а , где а   =  . K i  = – э лементарн ая конъюнкци я, r – ее ранг. – полная э лементарн ая конъюнкци я. K i – д изъюнктивная нормальная форма (ДНФ). Пример : х 1  х 2    х 2   х 3   х 4   х 1  х 3.

Изображение слайда
98

Слайд 98: Нормальные формы

Дизъюнктивное разложение Шеннона Т е о р е м а Ш е н н о н а. Любая булева функция f ( x 1,   x 2,   …, x n ) при любом т (1  m  n ) может быть представлена в следующем виде: f ( x 1,   x 2,   …, x n ) = f (  1,  2, …,  m, x m +1, …, x n ), где дизъюнкция берется по всевозможным 2 m наборам значений переменных x 1,  x 2, … ,  x m. f (  1,    2,   …  ,    m,   x m +1,   …,   x n ) – коэффициент разложения. При т = 1 для любого i  = 1, 2,   … ,  n : f ( x 1,   x 2,   …  ,   x n ) = x i f ( x 1, x 2, …, x i -1, 1, x i +1, …, x n )    x i f ( x 1, x 2, …, x i -1, 0, x i +1, …, x n ). При т = п : f ( x 1,   x 2,   …  ,   x n ) = f (  1,  2, …,  n ).

Изображение слайда
99

Слайд 99: Нормальные формы

С овершенн ая дизъюнктивн ая нормальн ая форм а (СДНФ) : f ( x 1,   x 2,   …  ,   x n ) = f (  1,  2, …,  n ). Получение СДНФ по таблице истинности: В ыделить наборы (  1,   2, … ,   n ), на которых функция принимает значение 1, и для каждого из них ввести в СДНФ полную элементарную конъюнкцию, где любая переменная x i присутствует с отрицанием, если  i = 0, и без отрицания, если  i = 1. f ( x,   y, z )   =  x  y  z      x  y  z      x  y z. СДНФ – каноническая форма. – конститу е нт единицы.

Изображение слайда
100

Слайд 100: Нормальные формы

Конъюнктивные нормальные формы D i  =   – э лементарн ая дизъюнкци я, r – ее ранг. – полная э лементарн ая дизъюнкци я. D i – к онъюнктивная нормальная форма (КНФ). Пример: ( х 2   х 3    х 4 )( х 1   х 2 ). К онъюнктивн ое разложение : f   ( x 1,  x 2, … ,  x n ) = = f (  1,  2, …,  m, x m +1, …, x n )). С овершенн ая конъюнктивн ая нормальн ая форм а (СКНФ) : f ( x 1,   x 2,   …, x n ) = f (  1,  2, …,  n )).

Изображение слайда
101

Слайд 101: Нормальные формы

Конъюнктивные нормальные формы Получение СКНФ по таблице истинности: В ыделить наборы (  1,   2, … ,   n ), на которых функция принимает значение 0, и для каждого из них ввести в С К НФ полную элементарную диз ъюнкцию, где любая переменная x i присутствует с отрицанием, если  i = 1, и без отрицания, если  i = 0. f ( x,   y, z )   =( х    y    z )( х    y   z )( х   y   z )( х   y    z )( х   y   z ). С К НФ – каноническая форма. – конститу е нт нуля.

Изображение слайда
102

Слайд 102: Функциональная полнота

{ f 1,  f 2, … ,  f т } – функционально полн ая, или просто полн ая система, если любая булева функция может быть представлена в виде суперпозиции функций из эт ого множества. Другое название – базис. Минимальны й базис. {,  , } – полная система по теореме Шеннона. {,   } и {, } – минимальные базисы. Система { , } не является полной.

Изображение слайда
103

Слайд 103: Функциональная полнота

{|} и {} – полные системы. {1, , } – полная система.  a    а   1; a      b      а b    b   а  1  1 = а b    b   а.

Изображение слайда
104

Слайд 104: Реализация б улевы х функци й комбинационными схемами

Диодные схемы у = х 1  х 2  …  х п у = х 1 х 2 … х п у =  а   b   c    a  c

Изображение слайда
105

Слайд 105: Реализация б улевы х функци й комбинационными схемами

Транзисторные схемы + + R R  a a r а = 0, R    r а = 1, R  r

Изображение слайда
106

Слайд 106: Реализация б улевы х функци й комбинационными схемами

Транзисторные схемы + + + у у у а a a с b b b у = у = у =

Изображение слайда
107

Слайд 107: Булевы функции. Графическое представление

Два вектора являются соседними, если они отличаются друг от друга значением только одной компоненты. П ример : (1   0   0   1) и (1   1   0   1). Отношение соседства представляется графом. П олны й булев граф, или п - мерны й гиперкуб имеет 2 п вершин и п 2 п  – 1 ребер. 0000 1000 000 100 00 10 0010 1010 0100 1100 0 1 001 101 0001 1001 010 110 0110 1110 01 11 0011 1011 011 111 0101 1101 0111 1111 Интервал – порожденный подграф в виде ( n – k )-мерного гиперкуба ( гипергрань ).

Изображение слайда
108

Слайд 108: Булевы функции. Графическое представление

Х арактеристическо е множеств о M f 1 функции f, выражаемой одной элементарной конъюнкцией, есть интервал. П ример : х 1  х 3   х 4 представляе тся троичным вектором (1 – 0 1). Представление булев ой функци и на гиперкубе : 000 100 001 101 010 110 011 111 СДНФ:  х 1  х 2   х 3   х 1   х 2  х 3   х 1   х 2   х 3    х 1  х 2   х 3    х 1   х 2   х 3 Можно задать интервал ами (– – 1) и (0 1 –) или х 3   х 1   х 2.

Изображение слайда
109

Слайд 109: Булевы функции. Графическое представление

Демонстрация справедливости формул. 000 100 000 100 001 101 001 101 010 110 010 110 011 111 011 111 х 3   х 1   х 2  х 3   = х 3   х 1   х 2  х 1   х 2    х 1   х 2  =  х 2 000 100 001 101 010 110 011 111  х 1  х 2    х 2  х 3  = х 1  х 2    х 2  х 3   х 1  х 3

Изображение слайда
110

Слайд 110: Булевы функции. Карта Карно

Развертка гиперкуба на плоскости : 000 100 000 100 101 001 001 101 010 110 011 111 010 110 111 011 f   ( х 1,  х 2,  х 3 ) =  х 1   х 2   х 1  х 2   х 3 x 1 x 3 x 1 x 3 0 0 0 1  0 1 1 0   x 2 x 2

Изображение слайда
111

Слайд 111: Булевы функции. Карта Карно

Строки и столбцы карты Карно кодируются кодом Грея. Длина кода п для кодирования N объектов должна быть такой, чтобы выполнялось N    2 п, или п   =  log 2 N , где  а  – ближайшее к а сверху целое число. 0 0 … 0 – код первого объекта. Для получения следующего кода берется последний код и в нем меняется значение той самой правой компоненты, изменение значения которой приводит к новому коду. 000 101 Другой способ: 0 0 00 00 000 001 100 1 1 01 01 001 011 1 11 11 011 010 0 10 10 010 110 10 110 111 11 111

Изображение слайда
112

Слайд 112: Булевы функции. Карта Карно

О тношение соседства элементов булева пространства представляется отношением симметрии в карте Карно. Каждая ось имеет свою зону симметрии, ширина которой определяется рангом оси.

Изображение слайда
113

Слайд 113: Булевы функции. Карта Карно

Упрощение ДНФ. Поиск максимальных интервалов. Поиск определяющих элементов и обязательных интервалов. х 6 х 4 х 5                 х 1 х 2 х 3 х 2  х 3   х 4  х 6   х 1   х 3  х 4   х 5    х 2   х 3  х 4   х 5    х 2   х 3   х 5   х 6   х 1   х 3  х 4   х 6     х 1   х 2  х 3   х 5  х 6.

Изображение слайда
114

Слайд 114: Булевы функции. Карта Карно

Упрощение ДНФ. Формирование элементарных конъюнкций х 6 х 4 х 5                 х 1 х 2 х 3 х 2  х 3   х 4  х 6  .

Изображение слайда
115

Слайд 115: Булевы функции. Карта Карно

Упрощение ДНФ. Формирование элементарных конъюнкций. х 6 х 4 х 5                 х 1 х 2 х 3 х 2  х 3   х 4  х 6   х 1   х 3  х 4   х 5.

Изображение слайда
116

Слайд 116: Булевы функции. Карта Карно

Упрощение ДНФ. Формирование элементарных конъюнкций. х 6 х 4 х 5                 х 1 х 2 х 3 х 2  х 3   х 4  х 6   х 1   х 3  х 4   х 5    х 2   х 3  х 4   х 5.

Изображение слайда
117

Слайд 117: Булевы функции. Карта Карно

Упрощение ДНФ. Формирование элементарных конъюнкций. х 6 х 4 х 5                 х 1 х 2 х 3 х 2  х 3   х 4  х 6   х 1   х 3  х 4   х 5    х 2   х 3  х 4   х 5    х 2   х 3   х 5   х 6.

Изображение слайда
118

Слайд 118: Булевы функции. Карта Карно

Упрощение ДНФ. Формирование элементарных конъюнкций. х 6 х 4 х 5                 х 1 х 2 х 3 х 2  х 3   х 4  х 6   х 1   х 3  х 4   х 5    х 2   х 3  х 4   х 5    х 2   х 3   х 5   х 6   х 1   х 3  х 4   х 6.

Изображение слайда
119

Слайд 119: Булевы функции. Карта Карно

Упрощение ДНФ. Формирование элементарных конъюнкций. х 6 х 4 х 5                 х 1 х 2 х 3 х 2  х 3   х 4  х 6   х 1   х 3  х 4   х 5    х 2   х 3  х 4   х 5    х 2   х 3   х 5   х 6   х 1   х 3  х 4   х 6    х 1   х 2  х 3   х 5  х 6.

Изображение слайда
120

Слайд 120: Булевы функции. Карта Карно

Упрощение ДНФ. «Жадный» способ не устраняет избыточность: х 3 х 4         х 1 х 2 f ( x 1, x 2, x 3, x 4 ) =  х 3   х 4   х 1  х 2   х 4   х 1 х 2   х 3    х 1   х 2   х 4    х 1  х 2   х 3. х 3   х 4 – избыточная конъюнкция.

Изображение слайда
121

Слайд 121: Троичные векторы и матрицы

В ектор (0 – 1 0 – 1) задает {(0 0 1 0 0 1), (0 0 1 0 1 1), (0 1 1 0 0 1), (0 1 1 0 1 1)} – интервал булева пространства. Интервал – характеристическое множество элементарной конъюнкции. Например, вектор (0 – 1 0 – 1) представляет конъюнкцию  х 1   х 3  х 4   х 6. Тогда всякую троичную матрицу (строками которой являются троичные векторы) можно считать представлением ДНФ некоторой булевой функции.

Изображение слайда
122

Слайд 122: Троичные векторы и матрицы

Отношения на множестве троичных векторов Ортогональность. В екторы и и v ортогональны по i -й компоненте, если и только если i -я компонента имеет 0 в одном из них и 1 – в другом. Троичные векторы ортогональны, если они ортогональны хотя бы по одной компоненте. П ример : (0 – 1 0 – 1) и (0 1 0 – 1 0). Симметрично, иррефлексивно. Пересечение. Если векторы и и v неортогональны, то они находятся в отношении пересечения. Пример : (0 – 1 0 – 1) и (0 0 1 – 1– ). Рефлексивно, симметрично. Смежность. Векторы и и v, ортогональные только по одной компоненте, являются смежными. Им соответствуют смежные элементарные конъюнкции. Пример : (0 – 1 0 – 1) и (0 1 0 – 1 –). Симметрично, иррефлексивно.

Изображение слайда
123

Слайд 123: Троичные векторы и матрицы

Отношения на множестве троичных векторов Соседство. Векторы и и v являются соседними, если по некоторой i -й компоненте они ортогональны, а значения остальных одноименных компонент совпадают. Пример : (0 – 1 0 – 1) и (0 – 1 0 – 0). Симметрично, иррефлексивно. Поглощение. Вектор и поглощает вектор v, если и только если все компоненты вектора и, значения которых отличны от «–», совпадают с одноименными компонентами вектора v. Интервал, представляемый вектором v, является подмножеством интервала, представляемого вектором и. П ример : (0 – 1 0 – –) поглощает (0 – 1 0 – 0). Рефлексивно, транзитивно.

Изображение слайда
124

Слайд 124: Троичные векторы и матрицы

Эквивалентность матриц Троичная матрица U эквивалентна булевой матрице W, если каждая из строк матрицы W поглощается хотя бы одной строкой матрицы U, а любой вектор, не совпадающий ни с одной из строк матрицы W, не поглощается ни одной строкой матрицы U. Троичные матрицы U и V эквивалентны, если существует булева матрица, эквивалентная обеим матрицам U и V. Бинарное отношение эквивалентности матриц рефлексивно, симметрично и транзитивно.

Изображение слайда
125

Слайд 125: Троичные векторы и матрицы

Операции над троичными векторами Склеивание соседних строк : Поглощение : Обобщенное склеивание смежных строк : Разложение строки по i -й компоненте.

Изображение слайда
126

Слайд 126: Анализ троичной матрицы на вырожденность

Троичная матрица U является вырожденной, если не существует троичного вектора, ортогонального каждой строке матрицы U. С овокупность интервалов, представляемая вырожденной матрицей, покрыва ет все булево пространство. Функция, ДНФ которой представляется вырожденной матрицей, является константой 1. Для заданной троичной матрицы U требуется найти троичный вектор v, ортогональный каждой ее строке, или убедиться в том, что такого вектора не существует. Вектор v в этом случае представляет набор значений аргументов, обращающий в нуль функцию, задаваемую матрицей U.

Изображение слайда
127

Слайд 127: Анализ троичной матрицы на вырожденность

Троичный вектор, имеющий k компонент со значением «–», представляет множество 2 k булевых векторов. Л юбой из этих булевых векторов покрывается данным троичным вектором. В ектор (0, 0, –) ортогонален обеим строкам троичной матрицы. Следовательно, матрица не вырожденная. Ни один из покрываемых в ектор ом (0, 0, –) двух булевых векторов (0, 0, 0) и (0, 0, 1) не является строкой булевой матрицы. Р ешить задачу о вырожденности троичной матрицы можно простым перебором всех 2 п различных булевых векторов. Следует использовать более эффективны й редукционный метод, опира ющийся на комбинаторный поиск.

Изображение слайда
128

Слайд 128: Анализ троичной матрицы на вырожденность

К омбинаторный поиск a а = 1 0 1 Т = e d 1 0 d = 1 с а = 0 w = (1 – – 1 –) 0 е = 1 с = 0 w = (0 – 0 – 1)

Изображение слайда
129

Слайд 129: Анализ троичной матрицы на вырожденность

П равила редукции Правило 1. Из матрицы Т удаляются столбцы, содержащие только «–». Правило 2. Из матрицы Т удаляются строки, ортогональные вектору w, а затем столбцы, которым соответствуют компоненты вектора w со значением 0 или 1. Правило 3. Если в матрице Т имеется строка, где лишь одна компонента обладает значением, отличным от «–», то соответствующей компоненте вектора w приписывается инверсное значение. Правило 4. Если в матрице Т существует столбец, не содержащий значения 0 (или 1), то это значение приписывается соответствующей компоненте вектора w. Правило расщепления предписывает перебор значений 0 и 1 некоторой компоненты вектора w. Правило нахождения решения. Если непосредственно после удаления строки по правилу 2 матрица становится пустой, w – иском ый вектор. Правило возврата. Если матрица Т становится пустой после удаления столбца или она содержит строку без значений 0 и 1, то следует возврати ться к последней точке ветвления. Правило прекращения поиска. Если при полном обходе дерева поиска вектор v найти не удалось, то это свидетельствует о вырожденности матрицы U.

Изображение слайда
130

Слайд 130: Локальные упрощения ДНФ

Дизъюнктивная нормальная форма безызбыточна, если из нее нельзя удалить ни одной элементарной конъюнкции и ни одного литерала из какой-либо конъюнкции. Простейшие случаи подобного сокращения : А х    А  =  А ; А  х    х  =  А    х ; А   х    В  х    АВ  =  А   х    В  х. Более сложный случай :  х 1  х 2  х 3    х 1  х 2  х 4    х 1   х 2  х 3   х 1   х 2  х 4    х 3  х 4, где конъюнкция х 3  х 4 является избыточной. Д ва вида избыточности: D   =   k    D   =   D, D   =   х k    D   =   k    D.

Изображение слайда
131

Слайд 131: Локальные упрощения ДНФ

Удаление избыточных элементарных конъюнкций D = k    D   =   D k и D находятся в отношении формальной импликации, т. е. k    D. Функция g имплицирует функцию f, если f имеет значение 1 везде, где имеет значение 1 функция g. М атрица V представляет ДНФ D, а вектор v – конъюнкцию k. Р езульт ат подстановки в D значений переменных, обращающих k в единицу – минор матрицы V, образованный строками, не ортогональными v и столбцами, соответствующими компонентам v, имеющими значение «–». Если этот минор – вырожденн ая матриц а, то k – избыточна я конъюнкция. В ектор, ортогональный всем строкам полученного минора, представляет набор значений переменных, обращающий D в нуль.

Изображение слайда
132

Слайд 132: Локальные упрощения ДНФ

Удаление избыточных элементарных конъюнкций = Результат подстановки значений х 1 = 0, х 2 = 1, х 4 = 0, х 5 = 1: – вырожденная матрица.

Изображение слайда
133

Слайд 133: Локальные упрощения ДНФ

Удаление избыточных литералов D   =   х k    D   =   k    D. k    D   =   k ( х   х )   D   =   х k    D   х k   =   D   х k. Л итерал х в выражении х k    D является избыточным, если конъюнкция  х k является избыточной в выражении D   х k. Следовательно, задача определения избыточности литерала в ДНФ сводится к предыдущей задаче – задаче определения избыточности элементарной конъюнкции. Н адо построить минор, образованный столбцами, где i -я строка имеет значения «–», и строками, не ортогональными вектору, полученному из i -й строки заменой нуля (или единицы) в j -м столбце на противоположное значение. Если полученный минор оказался вырожденной матрицей, то замена нуля (или единицы) на «–» возможна.

Изображение слайда
134

Слайд 134: Локальные упрощения ДНФ

Удаление избыточных литералов = Результат подстановки значений х 1 = 1, х 2 = 1, х 3 = 1, х 4 = 0, х 6 = 0: – вырожденная матрица.

Изображение слайда
135

Слайд 135: Минимизация ДНФ

Метод Квайна-МакКласки К ратчайш ая ДНФ имеет миним ум элементарных конъюнкций. М инимальн ая ДНФ имеет миним ум литералов. Функция g имплицирует функцию f, т. е. g    f, если f имеет значение 1 везде, где это значение имеет g. g – импликант а функции f. В сякая элементарная конъюнкция, входящая в ДНФ функции f, является импликантой функции f. Простая импликанта – это импликанта в виде элементарной конъюнкции, которая перестает быть импликантой при удалении любого литерала. М аксимальный интервал – х арактеристическ ое множество простой импликанты. С окращенн ая ДНФ функции f – д изъюнкция всех простых импликант функции f.

Изображение слайда
136

Слайд 136: Минимизация ДНФ

Метод Квайна-МакКласки требует представление заданной булевой функции в виде совершенной ДНФ. Процесс минимизации состоит из двух этапов: 1) нахождение сокращенной ДНФ ; 2) выделение из множества простых импликант минимального подмножества, составляющего ДНФ за данной функции. На этапе 1формируется последовательность С 0,  С 1, … ,  C k, где С i – множество конъюнкций ранга п  –  i, полученных путем простого склеивания конъюнкций из множества C i   – 1. Если удалить все поглощаемые конъюнкции, то останутся только все простые импликанты. На этапе 2 решается задача о покрытии: элементы множества М 1 покрываются максимальными интервалами.

Изображение слайда
137

Слайд 137: Минимизация ДНФ

Метод Квайна-МакКласки Этап 1: получение сокращенной ДНФ С 0 =, С 1 =, С 2 =.

Изображение слайда
138

Слайд 138: Минимизация ДНФ

Метод Квайна-МакКласки Этап 2: решение задачи о покрытии. Заданы множество А = М 1 и совокупность подмножеств В 1,  В 2, … ,  В т множества А в виде матриц и. Требуется выделить минимум подмножеств B i, покрывающих все множество А.

Изображение слайда
139

Слайд 139: Минимизация ДНФ

Метод Квайна-МакКласки Этап 2 Зад ача в матричной форме: в следующей матрице выбрать минимальное количество строк так, чтобы каждый столбец имел единицу хотя бы в одной из них. В 1, В 4 и В 6 – решение.

Изображение слайда
140

Слайд 140: Минимизация ДНФ

Метод Квайна-МакКласки Решением примера является матрица . В алгебраической форме:  х 1  х 2  х 4    х 1  х 2  х 3    х 3   х 4.

Изображение слайда
141

Слайд 141: Минимизация ДНФ

Метод Квайна-МакКласки Поиск определяющих элементов и обязательных интервалов. Для элемент а m i достаточно найти в М 1 все соседние с ним элементы, а затем построить содержащий их минимальный поглощающий интервал U, представляе мый вектором u. Д ля элементов m 1,  m 2, … ,  m k вектор u получается следующим образом: если i -я компонента во всех векторах m 1,  m 2, … ,  m k имеет значение 0, то и имеет в этой компоненте 0, если 1, то 1. Если i -я компонента имеет различные значения в этих векторах, то i -я компонента вектора и имеет значение «–». Если все элементы полученного таким образом интервала U принадлежат М 1, то он является максимальным в М 1 и притом обязательным, а m i является определяющим элементом. В противном случае U не содержится целиком в М 1, а m i не является определяющим ни для какого интервала.

Изображение слайда
142

Слайд 142: Минимизация ДНФ

Метод Квайна-МакКласки Поиск определяющих элементов и обязательных интервалов. Чтобы определить, содержится ли интервал U во множестве М 1, достаточно для матрицы, представляющей множество М 1, построить минор, определяемый столбцами, где вектор и имеет значение «–», и строками, не ортогональными вектору и. Число строк в этом миноре не превышает 2 р, где р – число компонент вектора и, имеющих значение «–». Очевидно, интервал U целиком содержится в М 1 тогда и только тогда, когда число строк в этом миноре равно 2 р.

Изображение слайда
143

Слайд 143: Минимизация ДНФ

Метод Квайна-МакКласки. Поиск обязательных интервалов. 0 1 0 0 0 * 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 0 0 1 0 1 0 * ––––––– 1 1 0 0 0 * – 1 0 – 0 0 1 1 1 0 1 1 0 1 0 * 1 1 0 0 1 1 0 1 0 1 1 0 1 1 0 1 1 0 1 1 1 1 1 1 0 1 1 1 0 1

Изображение слайда
144

Слайд 144: Минимизация ДНФ

Метод Квайна-МакКласки. Поиск обязательных интервалов. 0 1 0 0 0 * 0 1 0 0 0 0 0 1 1 0 0 0 1 1 0 * 0 1 0 1 0 0 1 1 1 0 1 0 0 0 1 1 1 0 0 0 1 0 1 1 0 0 1 0 1 0 * ––––––– ––––––– 1 1 0 0 0 * – 1 0 – 0 – – 1 1 0 0 1 1 1 0 * 1 1 0 1 0 * 1 1 0 0 1 1 0 1 0 1 1 0 1 1 0 * 1 1 0 1 1 1 1 1 1 0 * 1 1 1 0 1

Изображение слайда
145

Слайд 145: Минимизация ДНФ

Метод Квайна-МакКласки. Поиск обязательных интервалов. 0 1 0 0 0 * 0 1 0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 1 1 0 * 0 1 0 1 0 0 1 1 1 0 1 1 0 0 1 1 0 0 0 1 * 1 1 0 0 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 * ––––––– ––––––– ––––––– 1 1 0 0 0 * – 1 0 – 0 – – 1 1 0 1 – – 0 1 0 1 1 1 0 * 1 1 0 1 0 * 1 1 0 0 1 * 1 0 1 0 1 * 1 0 1 1 0 * 1 1 0 1 1 1 1 1 1 0 * 1 1 1 0 1 *

Изображение слайда
146

Слайд 146: Минимизация ДНФ

Метод Квайна-МакКласки. Поиск обязательных интервалов. 0 1 0 0 0 * 0 1 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 0 1 1 0 0 1 1 0 * 0 1 0 1 0 0 1 1 1 0 1 1 0 0 1 1 1 0 1 0 1 0 0 0 1 * 1 1 0 0 0 1 0 1 1 0 1 0 1 0 1 1 1 0 0 1 0 1 0 1 0 * ––––––– ––––––– ––––––– ––––––– 1 1 0 0 0 * – 1 0 – 0 – – 1 1 0 1 – – 0 1 1 1 0 – – 0 1 1 1 0 * Обязательные интервалы покрывают всё М 1. 1 1 0 1 0 * Решение: – 1 0 – 0 1 1 0 0 1 * – – 1 1 0 1 0 1 0 1 * 1 – – 0 1 1 0 1 1 0 * 1 1 0 – – 1 1 0 1 1 * 1 1 1 1 0 * x 2  x 3  x 5  x 3 x 4  x 5  x 1  x 4 x 5  x 1 x 2  x 3 1 1 1 0 1 *

Изображение слайда
147

Слайд 147: Минимизация ДНФ

Метод Квайна-МакКласки В предыдущем примере только один обязательный интервал. 0  0  0 0 0 0 0 0 0 0 1 0 1 0 0 0 0  0 1 1 0 0 1 0 0 0 1 0 0  0   0  0 0   0  0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0  1  1 1 0 0  1 0 1  1  1 0 0  1  1 – 0 – 0 0 0 – – – 0 0 – 1 0  1   1 1 0 0  1 – – 1 – 0 1  1  1 1 0 0 1 0 1  1  1 1  0   1   1 1 0 0 0 0 0  1  1 1  1   1   1 1  0   1   1 1  1   1   1 1 0 – – – – 1 1

Изображение слайда
148

Слайд 148: Минимизация ДНФ

Метод Квайна-МакКласки В предыдущем примере только один обязательный интервал. 0  0  0 0 1 2 3 4 0 0 1 0 1 0  0  0 0 * 0 0 – 0 + 1 1 1 0 0 0 2 0 0 1 0 * –  0   0  0 1 1 0 0  1  1 3 1 0 0 0 * 0 0  1 – 1 1 0 0  1 4 1 0 0  1 * 1 0 0 – + 1 1 0 1  1  1 – – 1 1 1 0 – 1 1 1  0   1   1 – – 1 1 1  1   1   1 Решение: 0 0 – 0 1 0 0 – – – 1 1

Изображение слайда
149

Слайд 149: Минимизация ДНФ

Метод Блейка-Порецкого Функция задается в произвольной ДНФ. Если преобразовать х 1   х 2   х 3   х 5    х 2   х 3   х 4   х 5   х 1 в СДНФ, то получим 18 конъюнкций. Применение обобщенного склеивания: х 1   х 2   х 3   х 5    х 2   х 3   х 4   х 5   х 1  = =   х 1   х 2   х 3   х 5    х 2   х 3   х 4   х 5   х 1    х 2   х 3   х 5  = х 1    х 2   х 3   х 5. Процесс минимизации состоит из двух этапов: 1) нахождение сокращенной ДНФ ; 2) выделение из множества простых импликант минимального подмножества, составляющего ДНФ за данной функции. На этапе 1 выполняются операци и обобщенного склеивания и простого поглощения : А х    В  х  =  А х    В  х    А В и А    А В = А.

Изображение слайда
150

Слайд 150: Минимизация ДНФ

Метод Блейка-Порецкого Этап 1: получение сокращенной ДНФ: 

Изображение слайда
151

Слайд 151: Минимизация ДНФ

Метод Блейка-Порецкого Этап 1: получение сокращенной ДНФ: 

Изображение слайда
152

Слайд 152: Минимизация ДНФ

Метод Блейка-Порецкого Этап 2: решение задачи о покрытии. Поиск ядра и антиядра. З адача поиска ядра сводится к нахождению избыточных элементарных конъюнкций в ДНФ. К онъюнкция k избыточна в D   =   k    D  , если k    D   =   D. Если, подставив в D любой набор значений переменных, обращающий k в единицу, получим D   =   1, то k избыточна. Конъюнкция х 2 х 3 (строка 5) не избыточна, т.к. результат подстановки х 2 = х 3 = 1, представляемый матрицей, не является тождественной единицей (матрица не вырожденная).

Изображение слайда
153

Слайд 153: Минимизация ДНФ

Метод Блейка-Порецкого Этап 2: решение задачи о покрытии. Поиск ядра и антиядра. Для каждой строки строим минор, образованный столбцами, где она имеет «–», и не ортогональными ей строками. Если минор – невырожденная матрица, то строка принадлежит ядру. 1) 2) 3) 4) я 5) 6) 7) я 8)

Изображение слайда
154

Слайд 154: Минимизация ДНФ

Метод Блейка-Порецкого Этап 2: решение задачи о покрытии. – ядро Антиядра нет Элементы, не покрытые ядром:

Изображение слайда
155

Слайд 155: Минимизация ДНФ

Метод Блейка-Порецкого Этап 2: решение задачи о покрытии. надо покрыть интервалами Решение: 

Изображение слайда
156

Слайд 156: Минимизация ДНФ

Метод Блейка-Порецкого Этап 2: решение задачи о покрытии. Для получения окончательного решения к ядру добавляем Результат: В алгебраической форме: x 1 x 2  x 4  x 2 x 3  x 1  x 2 x 4   x 1  x 2  x 3  x 1  x 2  x 4

Изображение слайда
157

Слайд 157: Минимизация ДНФ

Метод Блейка-Порецкого Р ( U ) – совокупность непустых подмножеств множества номеров строк матрицы U так ая, что для каждого элемента множества М 1 имеется подмножество в Р ( U ), из номеров всех строк матрицы U, представляющих интервалы, содержащие данный элемент. x 4 x 3 3,7 4,7 3,6 4,5 5 1 1,5 5,8 2,8 2,6 x 1 x 2 Р ( U ) = { (1 ), (5), (1,5), (2,6), ( 2,8), (3,6), (3,7), (4,5), (4,7), ( 5,8)} Задача: Выбрать минимум строк из U так, чтобы каждый элемент из Р ( U ) содержал номер хотя бы одной из этих строк.

Изображение слайда
158

Слайд 158: Минимизация ДНФ

Метод Блейка-Порецкого У т в е р ж д е н и е. Если из матриц U 1 и U 2 построить матрицу U, приписав столбцы матрицы U 2 к столбцам U 1, то множество Р ( U ) можно получить, взяв за его элементы всевозможные непустые пересечения элементов Р ( U 1 ) с элементами Р ( U 2 ). Р ( U 1 ) = {(1,2,5,6,8), (3,4,5,6,7)}; Р ( U 2 ) = {(1,5,8), (4,5), ( 2,6,8), (3,4,6,7)}; Р ( U 3 ) = {(1 ), ( 2,6), (3,6,7), (1,5,8), (4,5), ( 2,8), (4,7)}; Р ( U 4 ) = Р ( U ) = { (1 ), (5), (1,5), (2,6), ( 2,8), (3,6), (3,7), (4,5), (4,7), ( 5,8)} Задача: Выбрать минимум строк из U так, чтобы каждый элемент из Р ( U ) содержал номер хотя бы одной из этих строк.

Изображение слайда
159

Слайд 159: Минимизация ДНФ

Метод Блейка-Порецкого Правила редукции: 1. Если А    Р ( U ), В    Р ( U ) и А    В, то В удаляется из Р ( U ). 2. Если номер i присутствует только в тех элементах множества Р ( U ), где присутствует номер k, то i удаляется отовсюду. Р ( U ) = { (1 ), (5), (1,5), (2,6), ( 2,8), (3,6), (3,7), (4,5), (4,7), ( 5,8)}. Строки 1 и 5 составляют ядро. Результат применения правила 1: {(2,6), ( 2,8), (3,6), (3,7), (4,7)}. Результат применения правила 2: {(2,6), ( 2), (3,6), (3,7), (7)}. Для получения окончательного решения надо к обязательным строкам 1, 2, 5 и 7 добавить строку 3 либо строку 6.

Изображение слайда
160

Слайд 160: Минимизация ДНФ

Метод Блейка-Порецкого Решения

Изображение слайда
161

Слайд 161: Минимизация не полностью определенных булевых функций

М 1, М 0 и М – – области, где соответственно функция имеет значения 1, 0 и не определена. Достаточно задать два подмножества, например, М 1 и М 0. х 3 x 4 х 3 x 4 x 1 x 2 x 1 x 2 Результат минимизации:  х 1  х 4   х 3

Изображение слайда
162

Слайд 162: Минимизация не полностью определенных булевых функций

Отношение реализации : функция g реализует функцию f ( g      f ), если M 1 f    M 1 g и M 0 f    M 0 g. Постановка задачи: Для функции f найти минимальную (или кратчайшую) ДНФ среди всех ДНФ всех функций g, удовлетворяющих условию f    g. Число вариантов доопределения:. Выделим два из них – f min и f max : , ; ,.

Изображение слайда
163

Слайд 163: Минимизация не полностью определенных булевых функций

Распространение метод а Квайна-МакКласки Этапы: 1) нахождение множества всех максимальных интервалов для f max ; 2) покрытие ими элементов из. х 3 x 4 х 3 x 4 х 3 x 4 x 1 x 2 x 1 x 2 x 1 x 2 f f min f max Элементы надо покрыть интервалами.

Изображение слайда
164

Слайд 164: Минимизация не полностью определенных булевых функций

Распространение метод а Квайна-МакКласки Элементы надо покрыть интервалами. Матрица покрытия: Результат: f   = х 1  х 4   х 3,

Изображение слайда
165

Слайд 165: Минимизация слабо определенной функции

Если | М 1 | + | М 0 | << | М – |, то применение описанного метода потребует формирования большого количества бесполезных интервалов. Интервально поглощаем ое множество – множество элементов из М 1, для которых существует интервал, содержащий все эти элементы и не пересекающийся с множеством М 0. М аксимальн ое и нтервально поглощаемое множество – не содержится в качестве собственного подмножества в другом интервально поглощаемом множестве. Этапы: получени е всех максимальных интервально поглощаемых множеств ; получени е кратчайшего покрытия ими элементов множества М 1 ; максимально е расшир ение выбранных интервалов.

Изображение слайда
166

Слайд 166: Минимизация слабо определенной функции

Этап 1: получени е всех максимальных интервально поглощаемых множеств. Используется лексикографический перебор. Для п роверк и, является ли M 1 i  М 1 интервально поглощаемым множеством, н адо построить минимальный покрывающий интервал для M 1 i, т. е. наименьший по мощности интервал, содержащий все элементы множества M 1 i, и затем проверить, не пересекается ли он с множеством М 0. Нахождение минимальн ого покрывающ его интервал а для M 1 i : если значения одноименных компонент булевых векторов, принадлежащих M 1 i, совпадают, то это значение присваивается соответствующей компоненте получаемого троичного вектора, а если нет, то данная компонента принимает значение «–». Д ля (1 0 1 1 1 0 0), (0 0 1 0 1 1 0) и (1 0 1 1 0 1 0) получим (– 0 1 – – – 0),

Изображение слайда
167

Слайд 167: Минимизация слабо определенной функции

Этап 1: получени е всех максимальных интервально поглощаемых множеств. ,. Элементы – 1, 2; интервал – (– 0 1 – – 0). Не пересекается с M 0, следовательно, {1, 2} – интервально поглощаем ое множеств о. Элементы – 1, 2, 3 ; интервал – (– – – – – 0). Пересекается с M 0. Максимальные множества: {1, 2, 4} Интервалы: (– 0 1 – – –) {1, 3} (– – – 1 1 0) {1, 5} (– 0 – –  1  –) {2, 4, 5} (– 0 – 0  – –) {3, 5} (0 – 0  –  1 –)

Изображение слайда
168

Слайд 168: Минимизация слабо определенной функции

Этап 2: получени е кратчайшего покрытия элементов множества М 1 максимальны ми интервально поглощаемы ми множеств ами. Максимальные множества: {1, 2, 4} Интервалы: (– 0 1 – – –) {1, 3} (– – – 1 1 0) {1, 5} (– 0 – –  1  –) {2, 4, 5} (– 0 – 0  – –) {3, 5} (0 – 0  –  1 –) Кратчайшее покрытие: {1, 2, 4}, {3, 5}. Кратчайшая ДНФ:. Этап 3: максимально е расшир ение выбранных интервалов.  x 2   x 3   x 3   x 5

Изображение слайда
169

Слайд 169: Минимизация слабо определенной функции

Метод конкурирующих интервалов Задана слабо определенная булева функция с помощью характеристических множеств М 0 и М 1. Требуется найти по возможности минимальную (или близкую к ней) совокупность интервалов из множества М 0    М 1, покрывающую М 1. Процесс решения – последовательность шагов. Характеристика т екущ ей ситуаци и (после i -го шага итерации) : V i – с овокупность интервалов множества M 1  M  ; M i * – множество элемент ов из M 1, которые не принадлежат ни одному из интервалов множества V i. На очередном, ( i  + 1)-м шаге множество V i преобразуется в новое частичное решение V i  + 1, причем так, чтобы непокрытый остаток M i * сократился, по крайней мере, на один элемент. Очередной шаг выбирается на основе информации о совместимости элементов из M i * с интервалами из V i.

Изображение слайда
170

Слайд 170: Минимизация слабо определенной функции

Метод конкурирующих интервалов М 1 =, М 0 =. Матрица расстояний Матрица совместимости по Хэммингу

Изображение слайда
171

Слайд 171: Минимизация слабо определенной функции

Метод конкурирующих интервалов Если в матрице С i существует строка без единиц, то соответствующий ей элемент m из M i * не совместим ни с одним из интервалов, принадлежащих множеств у V i. В этом случае множество V i дополняется новым интервалом, содержащи м лишь m. Данная строка удаляется из С i. Если в C i существует столбец без единиц, то что соответствующий интервал из V i не может быть расширен так, чтобы покрыть какой-либо из элементов множества M i *. О н расширяется, если это возможно, и вносится в р ешени е. Данный столбец удаляется из С i. Если в C i существует столбец, содержащий единственную единицу, то соответствующий интервал u может быть использован для покрытия только одного элемент а из M i *. Интервал u расширяется на тот элемент и включается в решение. Соответствующие строка и столбец удаляются из матрицы С i.

Изображение слайда
172

Слайд 172: Минимизация слабо определенной функции

Метод конкурирующих интервалов М 1 =, М 0 =. Матрицы совместимости {3} вносится в решение. Матрица расстояний

Изображение слайда
173

Последний слайд презентации: Белорусский государственный университет информатики и радиоэлектроники: Минимизация слабо определенной функции

Метод конкурирующих интервалов М 1 =, М 0 =. Матрица совместимости Решение {3}, {1,  5, 7}, { 2, 4,  6 }

Изображение слайда