ДИСКРЕТНАЯ МАТЕМАТИКА F.4 МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ Alexander Sudnitson Tallinn University of Technology. - презентация

1 ДИСКРЕТНАЯ МАТЕМАТИКА F.4 МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ Alexander Sudnitson Tallinn University of Technology

2 2 F.4.1. Постановка задачи минимизации Задача минимизации булевой фонкции заключается в том, чтобы найти оптимальное по некоторому критерию (обычно наиболее компактное) её представление в виде суперпозиции элементарных булевых фонкций, составляющих некоторую фонкционально полную систему. Наиболее детально эта задача исследована в классе нормальных форм (ДНФ или КНФ) – для случая фонкционально полной системы, состоящей из дизъюнкции конъюнкции и отрицания. При изучении задачи минимизации мы сосредоточимся на классе ДНФ, учитывая, что переход к решению в классе КНФ, учитывая принцип двойственности, не должен вызвать принципиальных трудностей.

3 3 F.4.2 Алгебраическое упрощение ДНФ В принципе, упрощение ДНФ может быть выполнено путём эквивалентных алгебраических преобразований. Рассмотрим 3 основные операции, которые могут быть использованы для локального упрощения ДНФ. 1. Поглощение. Даны две элементарные конъюнкции k i и k i k j (во вторую конъюнкцию входят все литералы первой). Тогда Действительнно k i k i k j = k i k i k i k j = k i (1 k j ) = k i 1 = k i Говорят, что k i k j поглощается эл. конъюнкцией k i. Пример: x 1 x 2 x 3 x 4 x 1 x 2 = x 1 x 2

4 4 Локальное упрощение ДНФ (склеивание) 2. Склеивание. Даны две элементарные конъюнкции xk i и xk i, т.е. они различаются в точности по одному литералу (переменная в одном случае без отрицания, а в другом – с отрицанием). Тогда x k i x k i = k i Действительнно x k i x k i = k i (x x ) = k i 1 = k i Говорят, что x k i и x k i склеиваются по переменной x. Кроме того эти элементарные конъюнкции являются соседними и они ортогональны по единственной переменной. Пример: x 1 x 2 x 3 x 4 x 1 x 2 x 3 x 4 = x 2 x 3 x 4

5 5 Иллюстрация применения оп-и склеивания x 1 x 2 x 3 x 1 x 2 x 3 x 1 x 2 ( x 3 x 3 ) x 1 x 2 x 3 x 1 x 2 x 3 x 1 x 2 x 1 x 2 x 3 x 1 x 2 x

6 6 3. Удаление литерала. Даны две элементарные конъюнкции x и xk i (одна из эл. конъюнкций состоит из одного литерала, в другую входит литерал противоположный первому, но от той же переменной). Тогда Локальное упрощение ДНФ x x k i = x k i Пример: x 1 x 1 x 2 x 3 x 4 = x 1 x 2 x 3 x 4 Действительнно x x k i = x 1 x k i = x (k i k i ) x k i = x k i x k i x k i = = (x k i x k i ) (x k i x k i ) = x (k i k i ) k i (x x) = x k i

7 7 Приёмы локального упрощения ДНФ Дублирование элементарных конъюнкций k i = k i k i Пример. x 1 x 2 x 3 Дана ДНФ: = x 2 x 3 x 1 x 2 x 1 x 3 x 1 x 2 x 3 x 1 x 2 x 3 x 1 x 2 x 3 = ( x 1 x 2 x 3 x1 )x1 ) ( x 3 x 1 x 2 x3 )x3 ) ( x 2 x 1 x 3 x2 )x2 ) = =

8 8 Иллюстрация применения дублирования x 1 x 2 x x 2 x 3 x 1 x 3 x 1 x 2 x 1 x 2 x 3 x 1 x 2 x 3 x 1 x 2 x 3 x 1 x 2 x 3

9 9 Приёмы локального упрощения ДНФ Дизъюнктивное разложение эл. конъюнкций по одной и более отсутствующих в них переменным v x y v z x y z = v x y v z (v x y z v x y z) = = (v x y v x y z) (v z v x y z) = v x y v z Здесь по переменной v расщепляется последняя эл. конъюнкция в исходной ДНФ. Пример.

10 10 F.4.3. Минимальная ДНФ и этапы её поиска В классе ДНФ задача минимизации заключается в том, что надо найти такую ДНФ для заданной булевой фонкции, которая содержала бы минимальное число букв (литералов). В результате мы получаем так называемую минимальную ДНФ (МДНФ). В рассматриваемых нами методах решения задачи нахождения МДНФ можно выделить два этапа: Получение множества всех простых импликант. Выделение из него некоторого подмножества, которое и будет представлять решение (задача покрытия). Далее мы рассмотрим последовательно эти этапы и основные понятия необходимые для решения задачи минимизации.

11 11 Исходное задание минимизируемой фон-и Мы полагаем, что задана полностью опрнделённая булева фонкция f. Причем исходным заданием является ее СДНФ, которая может быть задана геометрически посредством указания характеристического множества, т.е. однозначно определяющего конкретную булеву фонкцию, например, путём представления «единичных» наборов аргументов этой фонкции посредством двоичной матрицы.

12 12 Пример 1: фонкция от 3-х аргументов x2x2 x3x3 x1x x 1 x 2 x 3 x 1 x 2 x 3

13 13 F.4.4. Простые импликанты. Говорят, что формула (булева фонкция) А имплицирует формулу В (А В), если формула В принимает значение 1 всюду, где принимает значение 1 формула А. Другими словами множество возможных значений переменных, при которых А равна 1, является подмножеством возможных значений переменных, при которых В тоже равна 1. Например, a & b a b Простой импликантой булевой фонкции f(x 1, x 2, …,x n ) называется такая элементарная конъюнкция k, которая имплицирует фонкцию f, но не будет ее имплицировать при удалении из k любого символа. Дизъюнкция всех простых импликант называется сокращенной ДНФ.

14 14 Пример: простые импликанты и сокр. ДНФ x2x2 x3x3 x1x x 1 x 2 x 2 x 3 x 1 x 3 простые импликанты x 1 x 2 x 2 x 3 x 1 x 3 сокращённая ДНФ

15 15 F.4.5. Основная теорема минимизации ТЕОРЕМА. Любая минимальная ДНФ состоит только из простых импликант. ТЕОРЕМА КВАЙНА. Если в СДНФ булевой фонкции выполнить все операции неполного склеивания, а затем все операции поглощения, то получится сокращённая ДНФ этой фонкции, т.е дизъюнкция всех её простых импликант. Таким образом при решении задачи нахождения минимальной ДНФ надо предварительно найти множество всех простых импликант заданной булевой фонкции, что и является первым этапом в классических методах минимизации, который опирается на следующую теорему.

16 16 F.4.6. Поиск простых импликант по Квайну Во-вторых в соответствии с процедурой минимизации применяется операция поглощения ( F &G) G = G Формально метод Квайна основан во-первых на применении операции т. н. неполного склеивания x k x k = k x k x k т.е. после применении операции склеивания в правой части тождества остаются оба терма участвовавшие в склеивании (отсюда слово «неполного»)

17 17 Пример 1: получение простых импликант x 1 x 2 x 3 x 1 x 2 x 3 x 1 x 2 x 3 x 1 x 2 x 2 x 3 x 1 x 3 Применив все возможные неполные склеивания получаем следующее множество элементарных конъюнкций x 1 x 2 x 3

18 18 Пример 1: Сокращённая ДНФ x 1 x 2 x 2 x 3 x 1 x 3 Выполнив все возможные поглощения получаем все простые импликанты, дизъюнкция которых даёт сокращённую ДНФ x 1 x 2 x 2 x 3 x 1 x 3 сокращённая ДНФ x 1 x 2 x 2 x 3 x 1 x 3 x 1 x 2 x 3 Здесь мы выполнили только 1-ый этап минимизации. Минимальную ДНФ для нашей фонкции мы получим лишь после выполнения 2-го этапа минимизации.

19 19 Процедура поиска всех простых импликант По Квайну сначала склеиваются все исходные конъюнкции (ранга n), находящиеся в отношении соседства. После завершения этой операции производятся все возможные поглощения. Затем склеиваются все соседние конъюнкции ранга n-1, после чего опять выполняются операции поглощения. Так повторяется до тех пор, пока на очередном этапе не окажется, что в преобразуемой ДНФ не существует уже таких конъюнкций, которые находятся в отношении соседства или поглощения. Таким образом будут найдены все простые импликанты (сокращенная ДНФ). ВСЕ ВОЗМОЖНЫЕ СКЛЕВАНИЯ ВСЕ ВОЗМОЖНЫЕ ПОГЛОЩЕНИЯ

20 20 F.4.7. Безызбыточная ДНФ Иногда при решении задачи минимизации ограничиваются поиском т.н. безызбыточной ДНФ. Безызбыточной будет ДНФ, из которой нельзя (не изменив при этом представленную фонкцию) выбросить ни одной элементарной конъюнкции и ни одной буквы (литерала) из входящих в нее элементарных конъюнкций. Важно понимать, что безызбыточная ДНФ вовсе не обязательно будет минимальной ДНФ, хотя может быть и достаточно близка к ней по нашему критерию оптимальности. МДНФ всегда является безызбыточной. Очевидно, что и безызбыточная ДНФ тоже состоит только из простых импликант.

21 21 F.4.7. Векторная интерпретация Мак Класки Принципиальным является то, что операции склеивания и поглощения интерпретируются над троичными векторами (множества М 1 ), представляющими интервалы (кубы) булева пространства аргументов (булевых переменных) и соответствующие им элементарные конъюнкции. С целью упрощения и большей эффективности вычислений Мак Класки усовершенствовал метод Квайна. В булевом пространстве простой импликантой будет один из максимальных интервалов (кубов), включающий в себя (покрывающий) «единичные» точки, но не содержащий ни одной «нулевой» точки. Очевидно, что при поиске простейших ДНФ достаточно ограничиться рассмотрением только таких максимальных кубов (чем больше «черточек» в кубе, тем меньше букв в соответствующей эл. конъюнкции).

22 22 Геометрическая интерпретация поиска МДНФ Таким образом нашей постановке задачи минимизации при геометрическом задании булевой фонкции соответствует поиск некоторой троичной матрицы с минимальным числом строк и в то же время – с минимальным совокупным числом 1 и 0 (с максимальным числом «черточек»). Другими словами надо найти минимальное число максимальных интервалов (кубов) булева пространства (второй этап минимизации), покрывающих в своей совокупности все «единичные» точки, но ни одной «нулевой» точки в булевом пространстве. Первый этап минимизации сводится к поиску всех максимальных интервалов, из которых затем, на втором этапе, выбирается их оптимальная совокупность. Подчеркнём, что на первом этапе мы все максимальные кубы, чтобы не упустить ни одной возможности выбора на втором этапе поиска МДНФ.

23 23 От СДНФ к МДНФ (как цель) M1 =M1 = M1 =M1 =

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

25 25 Отношения между троичными векторами Более общим является отношение смежности: векторы смежны, если они ортогональны ровно по одной компоненте. Отношение поглощения: вектор u поглощает вектор v, если значения его компонент, отличные от « - » совпадают со значениями одноименных компонент вектора v. векторы 1 0 – ортогональны, но смежными не являются Например, векторы 1 0 – смежные вектор 0 – – 1 поглощает вектор 0 1 – 1 Например,

26 26 Геометрическая интерпретация операций Будем далее при решении задачи минимизации рассматривать ДНФ булевой фонкции в виде троичной (в частностном случае, исходном, СДНФ – двоичной) матрицы. Если у этой матрицы существует пара соседних строк, то их можно «склеить» образовав новую строку, соответствующую продукту склевания. Добавление в матрицу получаемой новой строки является опрерацией склеивания. Операцией поглощения является удаление из матрицы некоторой строки, поглощаемой какой-либо из других строк этой матрицы.

27 27 Сокращение перебора при поиске пр. им-т Для сокращения перебора пар интервалов (конъюнкций), проверки свойства их ортогональности вся их совокупность подразделяется на группы по числу единиц в их записи. Тогда достаточно сравнивать попарно лишь элементы соседних групп (в данном примере имеем 3 группы). (0) (1) (4) (6) (0/1) (0/4) (4/6) десятичный эквивалент двоичного числа соответствущего набору аргументов x 1 x 2 x 2 x 3 x 1 x 3 простые импликанты

28 28 Обязательные импликанты До сих пор мы рассматривали построение сокращённой ДНФ (поиск всех простых импликант). Второй этап минимизации заключается в переходе от сокращённой ДНФ к минимальной ДНФ. Этот переход можно представить себе как вычёркивание максимального числа термов (простых импликант) из сокращённой ДНФ, но с тем условием, что оставшиеся импликанты образуют формулу описывающую исходную фонкцию. Наметим путь решения поставленной задачи, которая является принципиально сложной комбинаторной задачей. Первым делом введём понятие обязательного (существенного) импликанта. Обязателным будет импликант, который в любом случае будет присутствовать в минимальной ДНФ.

29 29 Пример 1: обязательные импликанты x 1 x 2 x 2 x 3 x 1 x 3 обязательный импликант Матрица показывает какие единичные точки принадлежат соответствующему интервалу Обязательный - значит без него не обойтись - он войдёт в любую МДНФ

30 30 Пример 1: сокращённая и минимальная ДНФ x 1 x 2 x 2 x 3 x 1 x 3 обязательный импликант x 1 x 2 x 2 x 3 x 1 x 3 сокращённая ДНФ x 1 x 2 x 1 x 3 минимальная (кратчайшая) ДНФ

31 31 Пример 1: поиск минимального покрытия обязательный импликант обязательный импликант В результате имеем, что все единичные точки покрыты двумя максимальными интервалами (кубами), которые образуют минимальное покрытие

32 32 Пример 2: фонкция от 4-х аргументов M1 =M1 =

33 33 Генерация всех простых импликант (пример) (8) (9) (3) (5) (11) (13) (14) (15) (8/9) (9/11) (9/13) (3/11) (5/13) (11/15) (13/15) (14/15) Исходным является является множество всех 0-кубов соответствующих конституентам заданной фонкции Шаг 1. Находим все возможные 1-кубы соответствующие парам ортогональных векторов (или заданным 0-кубам) представляющим наборы аргументов, на которых фонкция равна единице.

34 34 Генерация всех простых импликант (пример) (8/9) (9/11) (9/13) (3/11) (5/13) (11/15) (13/15) (14/15) Шаг 2. Выполняем все возможные поглощения. В данном примере все исходные 0-кубы поглощаются найденными на предыдущем шаге 1- кубами, т.е. ни один из 0-кубов не образует простого импликанта. Мнжество кубов исходное для следующего шага склеиваний.

35 35 Генерация всех простых импликант (пример) (8/9) (9/11) (9/13) (3/11) (5/13) (11/15) (13/15) (14/15) (9/11/13/15) (9/13/11/15) Шаг 3. Находим все возможные 2-кубы соответствующие парам ортогональных векторов (1-кубов) полученных на предыдущем шаге (применив к ним операцию склевания).

36 36 Генерация всех простых импликант (пример) Шаг 4. Выполняем все возможные поглощения на множестве кубов полученных на двух последних шагах склеивания (8/9) (3/11) (5/13) (14/15) (9/11/13/15) (8/9) (9/11/13/15) (9/13/11/15) (3/11) (5/13) (11/15) (13/15) (14/15)

37 37 Останов первого этапа минимизации (8/9) (3/11) (5/13) (14/15) (9/11/13/15) Поскольку следующиший шаг склеиваний невозможен, то оставшееся множество кубов соответствует множеству всех простых импликант минимизируемой фонкции. Их дизъюнкция образует сокращённую ДНФ: x 1 x 2 x 3 x 2 x 3 x 4 x 2 x 3 x 4 x 1 x 2 x 3 x 1 x 4

38 38 Сводная таблица построения мн-ва пр. им-т (8) (9) (3) (5) (11) (13) (14) (15) (8/9) (9/11) (9/13) (3/11) (5/13) (11/15) (13/15) (14/15) (9/11/13/15) (9/13/11/15)

39 39 Пошаговое изменение покрывающего мн-ва (8) (9) (3) (5) (11) (13) (14) (15) (8/9) (9/11) (9/13) (3/11) (5/13) (11/15) (13/15) (14/15) (8/9) (9/11/13/15) (3/11) (5/13) (14/15)

40 40 Иллюстрация найденной совкупности кубов (8/9) (9/11/13/15) (3/11) (5/13) (14/15)

41 41 Сокр. ДНФ и её различное представление x3x3 x4x4 x1x1 x2x x1 x2 x3x1 x2 x x 1 x 2 x x 2 x 3 x x 2 x 3 x x 1 x

42 42 F.4.8. Второй этап минимизации Строится импликантная матрица (таблица Квайна) К. Это бинарная матрица, задающая бинарное отношение включения между конституентами минимизируемой фонкции (соответствуют столбцам матрицы) и найденными простыми импликантами (соответствуют строкам матрицы). k ( i, j ) = 1, если j -тый конституент имплицирует i -тый простой импликант. В противном случае k ( i, j ) = 0.

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

44 44 Обязательный импликант (пример) x 1 x 2 x 3 [ ] есть обязательный импликант (импликант входящий в любую МДНФ), т.к. только он покрывет единичную точку (коституент) [ ].

45 45 Решение задачи покрытия (пример - шаг 1) Включаем этот импликант в строимое множество простых импликант включаемых в МДНФ и редуцируем (упрощаем) матрицу. { x 1 x 2 x 3 }

46 46 Решение задачи покрытия (пример) x 2 x 3 x 4 [ ] есть обязательный импликант

47 47 Решение задачи покрытия (пример - шаг 2) Включаем этот импликант в строимое множество простых импликант включаемых в МДНФ и редуцируем (упрощаем) матрицу. { x 1 x 2 x 3, x 2 x 3 x 4 }

48 48 Решение задачи покрытия (пример - шаг 3) x 2 x 3 x 4 [ ] есть обязательный импликант Включаем этот импликант в строимое множество членов МДНФ и редуцируем (упрощаем) матрицу.

49 49 Останов алгоритма поиска покрытия x 1 x 2 x 3 [ ] есть обязательный импликант В результате очередного редуцирования получили в остатке пустое множество столбцов, т. е. все единичные точки покрыты 4-мя интервалами и соответствующая МДНФ (она же кратчайшая) будет: x 1 x 2 x 3 x 2 x 3 x 4 x 2 x 3 x 4 x 1 x 2 x 3 [ ][ ] [ ][ ] { x 1 x 2 x 3, x 2 x 3 x 4, x 2 x 3 x 4, x 1 x 2 x 3 }

50 50 Пример 2: иллюстрация решения M1 =M1 =

51 51 Различные интерпретации МДНФ (пример 2) x3x3 x4x4 x1x1 x2x x 1 x 2 x x1 x2 x3x1 x2 x x 2 x 3 x x 2 x 3 x 4

52 52 Пример 3 - (требуется дать ответ) M1 =M1 = Как изменится решение в случае фонкции отличающейся от предыдущей (пример 2) тем, что в М 1 добавлен ?

53 53 Замечания к решению задачи покрытия Включение обязательных импликант в искомую МДНФ является очевидным шагом в решении задачи минимизации. Если после этого редуцированная матрица не становится вырожденной, то дальнейшее решение задачи поиска минимального покрытия, в общем случае, есть принципиально сложная кобинаторная прблема требующая отдельного изучения. Мы будем исходить из того, что при нескольких вариантах выбора мы не будем забывать, что предпочтение отдаётся варианту покрытия с минимальным суммарным числом в простых импликантах, обрзующих покрытие. При этом может появиться и несколько равноценных решений.

54 54 F.4.9. Метод карт Карно Правила минимизации: 2 i смежных клеток, расположенных в виде прямоугольника, соответствуют одной элементарной конъюнкции, ранг (число литерал) которой меньше ранга конституенты единиц. Чем больше клеток в выделенной группе, тем проще выражаемый ею импликант логической фонкции. В любой карте Карно соседними клетками, к которым можно применить правило склеивания, являются не только смежные клетки, но и клетки находящиеся на противоположных концах любой строки и любого столбца.

55 55 Процесс минимизации (карты Карно) Таким образом, процесс минимизации сводится к нахождению наиболее крупных групп из 2 i соседних единичных клеток. Причем каждая из единичных клеток должна входить в некоторую группу (блок, контур), а общее количество таких максимальных групп должно быть минимально. Простой импликант соответствующий максимальному блоку будет содержать в себе символы тех переменных, значения истинности которых совпадают у всех объединенных клеток.

56 56 Минимизация в классе ДНФ Закон поглощения: ( F & G) G = G Закон склеивания: ( F & x ) ( F & x ) = F x2x2 x3x3 x1x1 x 1 & x 3 ( x 1 & x 2 & x 3 ) = x 1 & x 3 ( x 1 & x 2 & x 3 )

57 57 Карта Карно для фонкции от 3-х аргументов Карта Карно есть двумерная развёртка гиперкуба. x1x1 x3x3 x2x2 x2x2 x3x3 x1x1 x1x1 x2x2 x3x3

58 58 Карта Карно для фонкции от 4-х аргументов Карта Карно есть двумерная развёртка гиперкуба. x2x2 x4x4 x3x3 x1x1 x4x4

59 59 Пример 4: бул. фонкция от 4-х аргументов M1 =M1 = x3x3 x4x4 x1x1 x2x2 x 1 x 2 x 3 x

60 60 Пример 4: метод карт Карно (в классе ДНФ) x3x3 x4x4 x1x1 x2x x3x3 x4x4 x1x1 x2x x1 x2 x3x1 x2 x3 x1 x2 x3x1 x2 x3 x 2 x 3 x 4 x 1 x 2 x 3 x 1 x 4 МДНФ: x 1 x 2 x 3 x 2 x 3 x 4 x 2 x 3 x 4 x 1 x 2 x 3

61 61 Иллюстрация оптимального решения x3x3 x4x4 x1x1 x2x2 x 1 x 2 x 3 x

62 62 Развертка 5-мерного гиперкуба x5x5

63 63 Карта Карно для фонкции от 5-и аргументов x5x5 x3x3 x4x4 x2x2 x1x1 x2x2 x1x1 x3x3 x3x3 x4x4 x5x5 Карта Карно (слева) есть двумерная развёртка гиперкуба.

64 64 Пример 5: фонкция от 5-и аргументов x2x2 x1x1 x3x3 x3x3 x4x4 x5x5 x1x1 x2x2 x3x3 x4x4 x5x M 1 = Здесь приведён пример булевой фонкции f ( x 1, x 2, x 3, x 4, x 5 ) заданной картой Карно и геометрически посредством троичной матрицы М 1. Эта фонкция имеет 8 простых импликантов (интервалов). (Пример взят из книги А. Д. Закревского)

65 65 Карта Карно для фонкции от 5-и аргументов x5x5 x3x3 x4x4 x2x2 x1x x2x2 x1x1 x3x3 x3x3 x4x4 x5x5 Порядок построения максимальных блоков (простых импликантов) следует из порядка развёртки гиперкуба.

66 66 x1 x3 x4x1 x3 x4 x2 x3 x4x2 x3 x4 x 2 x 3 x 4 x 5 x 1 x 2 x 4 x 5 Пример 5: простые импликанты x2x2 x1x1 x3x3 x3x3 x4x4 x5x x2x2 x1x1 x3x3 x3x3 x4x4 x5x x2x2 x1x1 x3x3 x3x3 x4x4 x5x x2x2 x1x1 x3x3 x3x3 x4x4 x5x5

67 67 x1 x2 x4x1 x2 x x2x2 x1x1 x3x3 x3x3 x4x4 x5x5 x 1 x 2 x 4 x x2x2 x1x1 x3x3 x3x3 x4x4 x5x5 x3 x5x3 x5 x 1 x 3 x 4 x x2x2 x1x1 x3x3 x3x3 x4x4 x5x5 Пример 5: простые импликанты x2x2 x1x1 x3x3 x3x3 x4x4 x5x5

68 68 Пример 5: минимальная ДНФ x2x2 x1x1 x3x3 x3x3 x4x4 x5x5 МДНФ Способность визуального восприятия позволяет нам легко увидеть, что миним-ное покрытие состоит из 6 импликантов. x5x5 x4x4 x3x3 x2x2 x1x x 2 x 3 x 4 x 5 x 1 x 2 x 4 x 5 x 1 x 2 x 4 x 5 x 1 x 3 x 4 x 2 x 3 x 4 x 3 x 5

69 69 Пример 5: исходное задание f ( x 1, x 2, x 3, x 4, x 5 ) x1x1 x2x2 x3x3 x4x4 x5x M 1 =

70 70 Карта Карно для фонкции от 5-и аргументов x5x5 x3x3 x4x4 x2x2 x1x1

71 71 Пример 5: фонкция от 5-и аргументов x2x2 x1x1 x3x3 x3x3 x4x4 x5x5

72 72 F Минимизация в классе КНФ Минимизация в классе КНФ заключается в том, что надо найти такую KНФ для заданной булевой фонкции, которая содержала бы или минимальное число букв - литералов (минимальная КНФ (МКНФ)). Очевидно, что такая КНФ будет содержать и минимальное число дизъюнкций (говорят, что является кратчайшей КНФ) Аналогично ДНФ можно определить и безызбыточную КНФ.

73 73 Минимизация в классе КНФ Закон поглощения: ( F G) & G = G Закон склеивания: ( F x ) & ( F x ) = F x2x2 x3x3 x1x1 x 1 x 3 ( x 1 x 2 x 3 ) & = x 1 x 3

74 74 Пример: метод карт Карно (в классе КНФ) x3x3 x4x4 x1x1 x2x x3x3 x4x4 x1x1 x2x x 1 x 2 x 3 x 2 x 3 x 4 МКНФ: x 1 x 4 x 1 x 2 x 3 x 2 x 3 x 4 (x 1 x 2 x 3 ) (x 2 x 3 x 4 )

75 75 F Неполностью определённые б. ф-и. Понятие неполностью определенной булевой фонкции. Если значения некоторой булевой фонкции заданы на всех наборах значений аргументов, то она называется полностью определенной (или всюду определенной) фонкцией. Иногда значения б. ф. определены почему-либо не всюду, а лишь на некоторых наборах значений аргументов, и в этом случае она называется частичной или неполностью определенной б. ф.. Будем считать. что на остальных наборах такая фонкция принимает неопределенное значение (неизвестно, 0 или 1), обзначаемое символом « – ». На практике существует два типа неопределённости: по входу и по выходу (либо входное воздействие в принципе не может поступить из внешней среды, либо реакция системы на него не важна).

76 76 Неопределённость Dont Care Неполностью определённые б. ф-и y x3x x2x2 x1x Частичную фонкцию удобно рассматривать как множество полностью определенных фонкций получаемых соответствующим доопределением (делая все возможные подстановки вместо «-» 0 или 1). Решая конкретную задачу, мы можем выбирать любую из них, «наиболее выгодную» для получения оптимального решения.

77 77 Неполностью определённые б. ф-и y x3x x2x2 x1x y x3x x2x2 x1x y x3x x2x2 x1x y x3x x2x2 x1x y x3x x2x2 x1x

78 78 Неполностью определённые б. ф-и. { 0, 1 } { 0, 1 }... { 0, 1 } { 0, 1, - } { 0, 1 } n { 0, 1, - } n Неполностью определенная б. ф. может быть задана геометрически разбиением булева пространства М на три части М 1, М 0 и М -, образуемые наборами, на которых фонкция получает соответственно значение 1, 0 или «-» М 0 = М 1 = М - = Очевидно, чтобы описать такую фонкцию, достаточно задать лишь две из этих матриц (выбрав, например, те из них, которые содержат меньше элементов). Формальное определение частичной б. фонкции:

79 79 Минимизация неполностью опред. б. ф-и. 1-(1) x2x2 x3x3 x1x1 x2x2 x 1 & x 3 y = x 2 x 1 x 3

80 80 Пример 2 x3x3 x4x4 x1x1 x2x М 0 = М 1 = М - = x 1 x 2 x 3 x 4

81 81 Минимизация частичной б. ф-и. (пример 2) x3x3 x4x4 x1x1 x2x (0) 1 -(1) x3x3 x4x4 x1x1 x2x (0) 0 1 -(1) x 2 x 3 x 1 x 4 ( x 1 x 4 ) ( x 3 x 4 ) ( x 1 x 2 ) МКНФ МДНФ

82 82 Минимизация частичной б. ф. (Мак Класки) Решение задачи минимизации методом Мак Класки модифицируется следующим образом: Получение множества всех простых импликантов (максимальных интервалов). Чтобы найти все из них, доопределяем единицами все «-», т. е. находим максимальные интервалы в общей совокупности М 1 и М -. Однако при решении задачи покрытия обязательному покрытию подлежит лишь множество М 1.

83 83 Замечания к решению примера (МДНФ) М 0 = М 1 = М - = Например, чтобы найти МДНФ методом Мак Класки для частичной фонкции (пример 2) При генерации всех простых импликант надо исходить из Во втором этапе минимизации требуется решить задачу покрытия лишь относительно

84 М 0 = М - = Во втором этапе минимизации требуется решить задачу покрытия лишь относительно При генерации всех простых имплицентов надо исходить из Замечания к решению примера (МДНФ)

85 ПРИМЕР РЕШЕНИЯ ДОМАШНЕЙ РАБОТЫ 85

86 Задание Найти минимальные ДНФ и КНФ методом Карт Карно. Найти минимальные ДНФ и КНФ методом Мак Класки. Преобразовать МКНФ и МДНФ к соответствующим формулам, в которых встречаются только операции конъюнкции и отрицания. Представить данную фонкцию в базисе, т.е. «штрих Шеффера». Реализовать данную фонкцию с использованием только 2-х входового элемента И-НЕ. 86

87 Исходная фонкция x2 x4x2 x4 x1 x3x1 x x4x4 x2x2 x3x3 x1x1

88 Отмеченная карта Карно x4x4 x2x2 x3x3 x1x x4x4 x2x2 x3x3 x1x1 Это представление рекомендуется использовать, чтобы лучше понять связь между различными методами минимизации.

89 Метод карт Карно - МДНФ 89 x4x4 x2x2 x3x3 x1x1 x 1 x 4 x 2 x 3 x 3 x x4x4 x2x2 x3x3 x1x1 Карта Карно соответствующей полностью определенной Булевой фонкции

90 Метод карт Карно - МКНФ 90 x4x4 x2x2 x3x3 x1x1 (x 1 x 2 x 3 ) ( x 2 x 4 ) ( x 3 x 4 ) x4x4 x2x2 x3x3 x1x1

91 Метод Мак-Класки – МДНФ – этап I(1) 91

92 Метод Мак-Класки – МДНФ – этап I(2) 92

93 Метод Мак-Класки – МДНФ – этап II 93 Построение импликантной матрицы и решение задачи покрытия. Здесь имеем 2 обязательных импликанта, а третий простой импликант выбран исходя из «разумных» рассуждений.

94 Метод Мак-Класки – МДНФ (9/11/13/15) 00 (0/1/8/9) 11 (3/7/11/15). Таким образом все «единичные точки» покрываются тремя максимальными интервалами: Соответствующая МДНФ будет: Следует обратить внимание на то, что данное решение совпадает с найденным методом карт Карно.

95 Метод Мак-Класки – МKНФ – этап I(1) 95

96 96 Метод Мак-Класки – МKНФ – этап I(2)

97 Метод Мак-Класки – МKНФ – этап II(1) 97

98 Метод Мак-Класки – МKНФ – этап II(2) 98 Следует обратить внимание на то, что здесь мы имем два раноценных решения. Одно из них совпадает с рещеннием найденным ранее методом карт Карно. Тем не менее мы должны убедиться, что и второе решение может быть получено методом карт Карно (см. след. слайд).

99 Получение альтернативного решения 99 x4x4 x2x2 x3x3 x1x x4x4 x2x2 x3x3 x1x1 Здесь мы доопределили фонкцию на наборе аргументов « 1, 0, 0 » (клетка 8) до 0.

100 Преобразование к базису &, ~ 100 Преобразование МДНФ: Преобразование МКНФ:

101 Преобразование к базису 101

102 102 Представление (реализация) схемой В интересах оптимальности за исходную лучше взять МДНФ.

103 Верификация методом истинностных таблиц 103