Как найти тупиковую днф
Перейти к содержимому

Как найти тупиковую днф

  • автор:

32. Минимальные , кратчайшие и тупиковые днф.

Элементарную конъюнкцию К будем называть импликантой функции f , если для ∀ã , K(ã)=1 влечет за собой выполнение условия f(ã)=1.

Импликант К –простой, если выражение получающееся из его выбрасывания любых их множителей не является импликантой f.

ДНФ называют минимальной, если она содержит наименьшее число литералов, среди всех ДНФ, эквивалентных ей.

Длиной ДНФ называют число входящих в нее элементарных конъюнкций.

ДНФ называют кратчайшей, если она имеет наименьшую длину среди всех эквивалентных ей ДНФ.

Заметим, что кратчайшая ДНФ не обязана быть в то же время минимальной среди всех ДНФ, эквивалентных исходной функции. Но поиск минимальных ДНФ проводится среди кратчайших ДНФ.

Тупиковой ДНФ функции f( n ) называется такая ДНФ её простых импликант из которой нельзя выбросить ни одного импликанта не изменив функцию f.

Следовательно для получения минимальной ДНФ необходимо построить все её тупиковые ДНФ и выбрать те из них которые содержат наименьшее количество переменных.

Алгоритм построения тупиковой ДНФ:

Пусть f( n ) – функция алгебры логики (булевая).

1)находим табличные значения функции f( n )=(101…01)

2)по табличным значениям строим СДНФ

3)строим СДНФ функции f в виде: f=K1˅ K2˅….˅Km , где Ki – простые импликанты.

4)строим матрицу покрытий простых импликант функции f

5)для каждого столбца j (1jK) находим множество Ej номеров строк для которых aj=1.

Cоставляем множество Ejтаких элементов, Ej= (ej1 ,ej2 ,…, eji), где eji– импликанты соответствующие значению 1.

Полученное выражение A=˅(j=1,k)Ej– называется решёточным покрытием ДНФ функции f.

Удаляя все дублирующиеся символы получаем тупиковую ДНФ.

33. Сокращённые днф. Построение сокращённых днф булевых функций методом Блейка.Пример.

Элементарную конъюнкцию К будем называть импликантой функции f , если для ∀ ã, K(ã)=1 влечет за собой выполнение условия f(ã)=1.

Импликант К –простой, если выражение получающееся из его выбрасывания любых их множителей не является импликантой f.

Теорема: Всякая функция реализуется дизъюнкцией своих простых импликант. Сокращённая –дизъюнкция всех простых импликант функции f.

Любая функция f реализуется своей СДНФ.

Для преобразования ДНФ в СДНФ:

(полное склеивание)

(неполное склеивание)

(обобщенное склеивание)

A˅A=A ; A&A=A (удаление дублирующих членов)

Метод Блейка: получение СДНФ состоит в применении правил обобщенного склеивания и поглощения, причем правила применяются слева направо.

На первом этапе производится операция обобщенного склеивания, до тех пор пока это возможно. На втором этапе операция поглощения.

34. Построение сокращённых днф булевых функций методом Квайна.Пример.

Теорема Квайна: Если в ДНФ функции f провести все операции неполного склеивания, после чего все операции поглощения и удаления дублирующих членов, то в результате получится СДНФ функции f.

Пример:f( 4 )=(0101101001101001) ;

ДНФ=⌐x1⌐ x2⌐ x3 x4 ˅⌐x1⌐x2 x3 x4 ˅⌐x1 x2⌐x3 ⌐ x4 ˅⌐x1 x2 x3 x4 ˅x1⌐x2⌐ x3 x4 ˅x1⌐x2 x3 ⌐ x4 ˅x1 x2⌐x3 ⌐ x4 ˅x1 x2 x3 x4

2.2.2.3. Построение всех тупиковых ДНФ

Определение. Тупиковой ДНФ (ТДНФ) функции f называется такая ДНФ ее простых импликант, из которых нельзя выбросить ни одного импликанта, не изменив функции f.

Теорема. Всякая минимальная ДНФ некоторой функции является ее тупиковой ДНФ.

Для получения МДНФ функции f необходимо построить все ТДНФ функции f и выбрать те из них, которые содержат минимальное число букв.

Алгоритм построения всех тупиковых ДНФ.

Пусть f(x1, x2, …, xn) есть булева функция.

Шаг 1. Построим СДНФ функции f и пусть P1, P2, …,Pn есть ее конституенты (единицы).

Шаг 2. Построим сокращенную ДНФ функции f и пусть К1, К2, …, Кm – ее простые импликанты.

Шаг 3. Построим матрицу покрытий простых импликант функции f ее коституентами единицы (табл. 34), полагая, что

Таблица 34

N P1 P2 … Pj … Pn
K1 a11 a12 … a1j … a1n
K2 a21 a22 … a2j … a2n
Ki ai1 ai2 … aij … ain
Km am1 am2 … amj … amn

Шаг 4. Для каждого столбца j (1 £ j £ n)найдем множество Ej всех тех номеров i строк, для которых aij=1. Пусть Составим выражение Назовем его решеточным выражением. Это выражение можно рассматривать как формулу, построенную в свободной дистрибутивной решетке с образующими 1, 2, …, m и с операциями конъюнкции и дизъюнкции.

Шаг 5. В выражении А раскроем скобки приведя выражение А к равносильному выражению , где перечислены все конъюнкции элементы ei1, ei2, …, ein которой взяты из скобок 1, 2, …, n соответственно в выражении А.

Шаг 6. В выражении В проведем все операции удаления дублирующих членов и все операции поглощения. В результате получим равносильное выражение С, представляющее собой дизъюнкцию элементарных конъюнкций.

Построить все минимальные ДНФ для функции f=1111010010101111.

Сокращенная ДНФ для данной функции имеет вид

Строим матрицу покрытий (табл. 35).

Таблица 35

№ Простые импликанты Конституенты единицы функции f
x1 x2 x3 x4 0000 0001 0010 0011 0101 1000 1010 1100 1101 1110 1111
1 1 1 — — + + + +
2 0 0 — — + + + +
3 — 0 — 0 + + + +
4 1 — — 0 + + + +
5 0 — 0 1 + +
6 — 1 0 1 + +

Пошагово будем выбирать слагаемые, которые войдут в минимальную ДНФ.

Шаг 1. Выбираем слагаемое 1 (табл. 36):

Таблица 36

№ Простые импликанты Конституенты единицы функции f
x1 x2 x3 x4 0000 0001 0010 0011 0101 1000 1010 1100 1101 1110 1111
1 1 1 — — + + + +
2 0 0 — — + + + +
3 — 0 — 0 + + + +
4 1 — — 0 + + + +
5 0 — 0 1 + +
6 — 1 0 1 + +

Шаг 2. Выбираем слагаемое 2 (табл. 37):

Таблица 37

№ Простые импликанты Конституенты единицы функции f
x1 x2 x3 x4 0000 0001 0010 0011 0101 1000 1010 1100 1101 1110 1111
1 1 1 — — + + + +
2 0 0 — — + + + +
3 — 0 — 0 + + + +
4 1 — — 0 + + + +
5 0 — 0 1 + +
6 — 1 0 1 + +

Шаг 3. Выбираем слагаемое 4 (табл.

Таблица 38

№ Простые импликанты Конституенты единицы функции f
x1 x2 x3 x4 0000 0001 0010 0011 0101 1000 1010 1100 1101 1110 1111
1 1 1 — — + + + +
2 0 0 — — + + + +
3 — 0 — 0 + + + +
4 1 — — 0 + + + +
5 0 — 0 1 + +
6 — 1 0 1 + +

Шаг 4. Выбираем слагаемое 5 (табл. 39):

Таблица 39

№ Простые импликанты Конституенты единицы функции f
x1 x2 x3 x4 0000 0001 0010 0011 0101 1000 1010 1100 1101 1110 1111
1 1 1 — — + + + +
2 0 0 — — + + + +
3 — 0 — 0 + + + +
4 1 — — 0 + + + +
5 0 — 0 1 + +
6 — 1 0 1 + +

Поскольку все конституенты единицы покрыты, то одна из ТДНФ имеет вид

Поскольку выбор включаемых слагаемых произволен, то функция может иметь несколько ТДНФ.

Минимальная ДНФ булевой функции

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

Основные методы получения минимальной ДНФ функции это: равносильные преобразования, метод карт Карно, метод Квайна (или Квайна-МакКласки), преобразования по булевому кубу. Все они разобраны ниже. В некоторых задачах также построены релейно-контактные или функциональные схемы.

Типовые задачи снабжены подробным решением, формулами, пояснениями. Используйте их, чтобы научиться решать подобные задачи или закажите решение своей работы нам.

Другие примеры решений о булевых функциях:

  • Булевы формулы
  • Таблицы истинности
  • КНФ, ДНФ, СДНФ, СКНФ, полином Жегалкина
  • Полнота системы функций

Задачи и решения о минимизации ДНФ булевых функций

Задача 1. Применяя равносильные преобразования привести булеву функцию $f=(\bar x \to \bar y)\to (yz \to \bar xz)$ к минимальной ДНФ.

Задача 2. Для заданной логической функции: $$F= \overline <(\bar A \vee B\cdot \bar C)>\cdot \overline<( \overline <(B \downarrow C)>\cdot D> $$ — найти дизъюнктивную нормальную форму;
— составить таблицу истинности и построить диаграмму Карно;
— получить минимальную дизъюнктивную нормальную форму;
— от минимальной дизъюнктивной нормальной формы перейти к конъюнктивной нормальной форме.

Задача 3. Для функции $f(x_1,x_2,x_3,x_4)$, заданной списком номеров наборов из $Nf$ методом Квайна найти сокращенную и минимальные ДНФ.
Список номеров: 0,1,2,3,6,7,8,9,11,15.

Задача 4. С помощью карт Карно найдите сокращенную, все тупиковые и минимальные ДНФ или КНФ булевой функции f(x1,x2,x3,x4), заданной вектором своих значений.
(1100 0101 0011 0011)

Задача 5. Найти минимальные КНФ булевых функций, зависящих от аргументов $A, B, C, D$. В квадратных скобках указаны неопределенные состояния

$$f = ( 1, 2, 5, 6, 14), [4, 9, 11, 12, 15].$$

Задача 6. Найти минимальные ДНФ и КНФ булевых функций, зависящих от аргументов $A, B, C, D$

$$f = (1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 15).$$

Задача 7. Для булевой функции $f(x, y, z)$ найти методом преобразования минимальную ДНФ. По таблице истинности построить СКНФ. По минимальной ДНФ построить релейно-контактную схему.

$$f(x,y,z)=(\bar x \vee \bar y)\wedge (\bar y \vee \bar z) \to (\bar x \vee \bar z)$$

Задача 8. Переключательная функция от трех аргументов задана номером в десятичной системе счисления. Получить номер ПФ в двоичном, восьмеричном и шестнадцатеричном кодах, таблицу истинности, определить СДНФ, СКНФ, символическую форму функции с восьмеричной нумерацией наборов. Минимизировать функцию по кубу соседних чисел и карте Карно. Определить свойства функции. Реализовать функцию переключательной схемой на функциональных элементах в базисах а) И, ИЛИ, НЕ, б) И-НЕ, в) ИЛИ-НЕ.

Задача 9. Для булевой функции f, заданной в таблице 1:
а) найти сокращённую ДНФ;
б) найти ядро функции;
в) получить все тупиковые ДНФ и указать, какие из них являются минимальными;
г) на картах Карно указать ядро и покрытия, соответствующие минимальным ДНФ.

Задача 10. Двумя способами: с помощью карты Карно и методом Квайна найти сокращенную, ядровую и все минимальные дизъюнктивные нормальные формы булевой функции $f$, заданной вектором значений 0101101001001110. Построить минимальную функциональную (над системой $\<\vee, \wedge, \neg\>$ ) и минимальную контактную схемы для функции $f$.

Решение задач о минимальной ДНФ на заказ

Выполняем для студентов очников и заочников решение заданий, контрольных и практических работ о минимизации булевых функций. Также оказываем помощь в сдаче тестов. Подробное оформление, таблицы, графики, пояснение, использование специальных программ при необходимости. Стоимость примера от 150 рублей , оформление производится в Word, срок от 2 дней.

Сокращенная и минимальная ДНФ

Сокращенная ДНФ — форма записи булевой функции, для которой 1) любые два слагаемых различаются как минимум в двух позициях, 2) ни один из конъюнктов не содержится в другом. Для булевой функции может существовать несколько сокращенных ДНФ

Минимальная ДНФ — такая сокращенная ДНФ, в которой содержится минимальное количество вхождений переменных.

Минимизация переключательных функций

  • Операция попарного неполного склеивания:
  • Операция элементарного поглощения:

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

Итерационый алгоритм. Задача в нахождении по полной системе импликант (конституэнт единицы) полной системы простых импликант.

  1. Исходным является множество конституэнт единицы функции — импликанты нулевого ранга.
  2. Выполняются все возможные операции неполного попарного склеивания для элементарных конъюнкций длины n. (где n-кол-во аргументов).


  • подмножество элементарных конъюнкций длины n (оставшиеся)
  • подмножество элементарных конъюнкций длины n-1

Алгоритм завершается, когда подмножество является пустым, либо нельзя выполнить ни одной операции неполного попарного склеивания.

Таким образом, получаем систему простых импликант функции.

Нахождение тупиковых ДНФ

Стратегическая задача нахождения приведенной системы простых импликант заключается в нахождении наилучших покрытий единиц функции простыми импликантами.

Для системы простых импликант для заданной функции может быть получено несколько приведенных систем. Следует считать, что среди них есть такая, которая дает тупиковую нормальную форму минимальной длины.


    Находятся такие единицы функции, которые покрываются только какой-то одной импликантой из системы простых импликант (для каждой единицы считаем сколько ее покрывает импликант и отмечаем их).

Повторяем шаг 1 и шаг 2 для оставшихся множеств (находится псевдоядро). Но перед повторением должен быть дополнительный шаг, который уменьшает перебор. (выкидываем из тех, которые покрывают одни и те же единицы(из оставшихся) ту импликанту, которая имеет наибольшую длину)

И так далее до тех пор, пока не будут покрыты все единицы функции.

Велика вероятность, что на каком-то шаге не найдется ни одной единицы функции, которая покрывается одной импликантой. В этом случае ищется наилучшее (наименьшей длины) покрытие оставшихся единиц функции методом перебора:

  • Пусть A входит в ТДНФ, а B,C. нет.
  • Пусть В входит в ТДНФ, а A,C. нет.
  • Пусть C входит в ТДНФ, а A,B. нет.
  • .

Пример минимизации переключательной функции методом Квайна

Функция задана вектором: 883F . Запишем 16-ричное число 883F в двоичной виде в столбец значений функции таблицы истинности.

Цена ДНФ является суммой длин всех входящих в нее конъюнкций.

Минимизация функции методом Квайна.

В результате на данном шаге получаем простые импликанты:
,

СкДНФ:
v v v

Нахождение тупиковых форм.

  • Единицы ДНФ, покрываемые импликантами СкДНФ, обозначаются «+».Импликанты, попадающие в ядро помечаются «*».
  • Единицы функции, которые покрываются только какой-то одной импликантой из системы простых импликант, помечаются “>”.
  • Единицы функции, покрываемые ядром, но не покрываемые только какой-то одной импликантой из системы простых импликант, помечаются “>>”.

МДНФ: v v , цена=7

Графический метод минимизации — Карты Карно

Карты Карно рассматриваются как перестроенная соответствующим образом таблица истинности функции.

Карты Карно — определенная плоская развертка n-мерного булева куба.

Строится таблица истинности функции определенным образом. Каждая клетка таблицы соответствует вполне определенной вершине булева куба. Нулевые значения не записываются.

Карта Карно для функции 4-х переменных:
Карта Карно

Карта Карно рассматривается как поверхность фигуры под названием тор («бублик»).

p-клетки — клетки карты Карно, соответствующие единичному значению функции.

Соседние наборы — наборы, которые различаются только одним аргументом (одной орбитой).

Любой паре соседних наборов в Карте Карно соответствуют соседние клетки.

Две соседние p-клетки на карте Карно дают импликанту первого ранга. Например, клетки 1100 и 1101 отличаются только значением переменной x3, следовательно, они дают импликанту 124.

Две соседние импликанты первого ранга образуют импликанту второго ранга.
Карта Карно

На этой карте соседние клетки образуют импликанты a,b,c,d,e. При этом импликанты a и b являются соседними, поэтому они образуют импликанту второго ранга.

Если функция имеет 5 переменных, то рисуются 2 Карты Карно: для x5=0 и для x5=1. Если 6 переменных — 4 Карты, так чтобы в соседних картах соседние клетки имели одинаковые координаты:
Карты Карно для 6 переменных

Соседние p-клетки, соответствующие импликанте образуют компактную группу.

Количество p-клеток в компактной группе является степенью двойки.

Задача минимизации переключательной функции с помощью карт Карно заключается в нахождении импликант высшего ранга (соответствующих компактным группам наибольшей размерности), покрывающих p-клетки функции наилучшим образом.

Если на картах Карно выделить все компактные группы наибольшей размерности, то дизъюнкция соответствующих конъюнкций даст СкДНФ.

Пример минимизации функции 4-х переменных методом Карт Карно

Нахождение тупиковых форм.

Машинно-ориентированные методы минимизации переключательных функций.

Основаны на применении соответствующих алгебр(или соответствующих алгебраический преобразований).

Вопрос 1. Интервальная форма задания функции. Постановка задачи минимизации.

Геометрический представление: (отображение функции на n-мерный булев куб) Любому набору значений аргументов соответствует элементарная конъюнкция, содержащая все эти переменные — конституента единицы.

Те вершины n-мерного булева куба, в которых функция принимает единичное значение называются 0-кубами.

Два 0-куба образуют 1-куб, если соответствующие булевы вектора(их координаты) отличаются между собой значением только одной координаты(или одной компоненты). Эти координаты носят название свободной координаты. Обозначение x, остальные координаты 0-куба называются связанными и имеют либо 1, либо 0 значение. 0-кубы, образующие 1-куб называются его гранями. Два 1-куба образуют 2-куб, если свободная координата у них одинакова и они различаются значением только одной связанной компоненты.( 1-кубы — грани соответствующего 2-куба).

И так далее до n-куба( в случае тавтологии).

В общем случае, r-куб-это такой куб в булевом пространстве, у которого r свободных компонент и n-r связанных компонент.

Пример:
(1x1xx1) — 3-куб
(1x1x01),(1x1x11)- два 2-куба. Они являются гранями этого 3-куба(образуют его).

Если для какой-то функции взять все возможные кубы одинаковой размерности, то получаем множество кубов(или комплекс кубов).
K r (f) — комплекс r-кубов функции f/

Для некоторой функции всегда есть комплекс

(Если K n (f) содержит куб, то f — константа 1

Подмножество вершин булева куба, соответствующие кубу размерности r называется интервалом булева пространства ранга r. (интервал 1 ранга — 1×1, интервал 2 ранга — x1x)
Для нашего примера:
K 0 (f)=<101,110,111,010,011>
K 1 (f)=<01x,11x,1x1,x11,x10>
K 2 (f)=

В общем случае комплекс кубов определенного ранга не является покрытием исходной функции(за исключением K 0 ).

В нашем примере K 2 не является покрытием, хотя K 1 — покрытие. K(f)=K 0 ∪K 1 ∪K 2 — для нашей функции

Куб большей размерности покрывает кубы меньшей размерности, если они могут быть получены из него последовательным применением оператора граней.
(x1x) имеет грани (01x) и (11x), которые имеют грани : (010),(011) и (110),(111)

Если взять интервал булева пространства, то аналитически его можно описать в виде соответствующих элементарных конъюнкций.

Некоторый комплекс кубов — L, таких, что каждая вершина из комплекса K 0 (f) включена по крайней мер в один из кубов комплекса L, называется покрытием комплекса K функции f.

Каждое покрытие комплекса K(f) определяет некоторую ДНФ переключательной функции.

Не учитывается инверсия аргументов на нулевом уровне.

Минимизация
Цена r-куба: c=n-r — число связанных переменных, количество символов в элементарной конъюнкции(совпадает с ценой в смысле Квайне)
цена покрытия—цена покрытия, где qr-количество кубов размерности r в покрытии L.
цена покрытия-вторая функция цены покрытия(учитывает число кубов)

Задача минимизации: Найти такое покрытие L комплекса K(f), цена которого будет минимальна — минимизация в смысле Квайне.

Задача решается алгебраически, вводится свой математический аппарат. Это аппарат исчисления кубических комплексов (задает операции над кубами).

Каждая операция проходит в два этапа:
I Этап. Предварительное вычисление путем покоординатной обработки кубов по правилам, задаваемым с помощью таблиц покоординатной обработки.
II Этап. Окончательный.

Операция вычитания кубов удаляет из куба a общую часть кубов уменьшаемого и вычитаемого (т.е. пересечение кубов a и b).

В результате вычитания можем иметь несколько кубов.
Если куб a входит в куб b, то результат — ∅
Пример:

a#b = (1×1)#(x11) = (z0z) = (101)
c#b = (1xx)#(x11) = (z00) =

Нахождение множества простых импликант

K(f)=K 0 ∪K 1 ∪. ∪K i ∪. ∪K n-1 — комплекс K функции f

z⊆K является простой импликантой этого комплекса, если δi(z)=∅ (δi — оператор сограней), то есть не существует какого-либо другого куба, который бы включал в себя исходный куб z.

Z(f)= — множество импликант для функции f

Необходимо получить весь комплекс K функции f, используя операторы граней и сограней.

Берем куб z из K и проверяем, есть ли какой-то куб, гранью которого является рассматриваемый.

Операция *(«звездочка») позволяет получить множество Z — кубов, соответствующих простым импликантам функции.

Алгоритм (*) — нахождение множества кубов, соответствующих простым импликантам функции.

  1. Ĉ0(f) — неупорядоченное покрытие
    причем одна и та же единица функции может покрываться несколькими кубами
  2. C0 = Ĉ0 — 1 | c1 ∈ Ĉ0 ∧ c2 ∈ Ĉ0 ∧ c1 ⊆ c2>
    (тоже, что и поглощение в методе Квайне)
  3. C0*C0попарно
  4. в результате 3) находится множество 0-кубов:

C1(f) и т.д. в общем случае покрытием функции не являются

Алгоритм заканчивается, когда на каком-то шаге получаем множество C, содержащее один куб.

Результат — множество Z — множество простых импликант.
Z = ∪Zi

Алгоритм извлечения

  1. Является покрытием исходного множества кубов функции;
  2. С минимальной ценой покрытия, если покрытий несколько.

Для решения этой задачи исходные данные фактически — исходный комплекс функции, то есть некоторый исходный комплекс K 0 (f) и Z(f).

Определение: возьмем некоторую вершину d∈K0. Говорят, что эта вершина является обособленной вершиной комплекса на множестве простых импликант Z, если существует такой куб z∈Z, что вершина d накрывается только этой импликантой z.

Такая импликанта будет простая. Вершина d называется различающей. А импликанта получила название экстремаль.

Любое минимальное покрытие содержит экстремали нулевого ранга.

Пример:

Различающие вершины: (0;0;1) и (0;1;0)
E0=< a, d>, осталось покрыть одну вершину — (1;1;1)

Задача минимизации: необходимо найти все обособленные вершины и выделить импликанты, накрывающие эти обособленные вершины.

Такие импликанты образуют множество экстремалей.

Задача решается, если известно K 0 (f), то есть все вершины.


    Некоторая простая импликанта e∈Z является экстремалью, если e∩K ≠ e∩U'(e,Z)∩K, а e∩K ≠ ∅,
    U'(e,Z) = U(e,Z) — e,
    U(e,Z) = < z | z∈Z, Z∩e ≠ ∅>.
    Z — множество простых импликант,
    U(e,Z) — окрестность куба e, т.е. все простые импликанты из Z, которые имеют общие части с импликантой e.
    U'(e,Z) — окрестность без самой импликанты.

Функция может быть не полностью определена:

L — комплекс, где функция определена и равна 1,

D — комплекс, где значение функции не определено,

Если из простой импликанты e удалить все подкубы (Z-e), и остается, по крайней мере, одна вершина булева куба, которая содержится в исходном комплексе функции, то оставшиеся вершины является выделенными, или отмеченными.

Нахождение множества экстремалей

  1. Каждая простая импликанта проверяется на наличие в ней выделенной вершины, т.е. вычисляется e#(Z-e), если результат вычитания кубов не пустой, то такая импликанта может быть экстремалью.

Если результат пересечения не пустой, значит в L (комплексе единичных значений) имеются обособленные вершины, а e является экстремалью.

Операция, которая позволяет сократить в последующем перебор и исключить из i не максимальные кубы — упорядочивание.

  1. L = ∅ => покрытие единственное
    E = ∪Ei
  2. L ≠ ∅ Если проверка на экстремальность не дает результата, т.е. ни одна простая импликанта не содержит квазеопорных вершин, а операция упорядочивания не дает результата.
    Пример:

В этом случае не остается никакого другого варианта решения, кроме волюнтаристского.


    простая импликанта входит в минимальное покрытие

Все вычисления в ручном варианте сводятся к вычислениям над таблицами.

Минимизация функции методом кубических покрытий.

Рассмотрим комплекс кубов К(f) = L D, где L – множество единичных наборов, D – множество наборов, на которых ДНФ не определена.

Нахождение тупиковых форм.

Содержание

  1. Постановка задачи
  2. Решение задачи
    1. Анализ переключательной функции
    2. Метод Квайна
    3. Карты Карно
    4. Кубические покрытия

    1. Постановка задачи

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

    y => (2) v (3B) v (20) v (21) v (1D) v (6) v (1B) v (D) v (24) v (2C) v (23) v (B) v 36 v 1C v 3A v 7 v A v 8 v 10 v 38 v 12 v 15 v 5 v 1F v 3F v 1A v 17 v 3E v 3D v 39 v 9 v 37 v 19 v 2A v 11 v 18 v 4 v 3C v 2E v 29 v 0 v 2D v 28 v 25 v 14 v 1E

    Необходимо выполнить следующие задачи:

    1. Доопределить функцию нулями, минимизировать полученную функцию методом Квайна;
    2. Доопределить функцию единицами и произвести минимизацию, используя карты Карно;
    3. Минимизировать исходную функцию методом кубических покрытий;
    4. Проанализировать полученные результаты;

    2. Решение задачи

    2.1 Анализ переключательной функции

    Представим исходную последовательность в виде таблицы истинности.

    (2) v (3B) v (20) v (21) v (1D) v (6) v (1B) v (D) v (24) v (2C) v (23) v (B) v 36 v 1C v 3A v 7 v A v 8 v 10 v 38 v 12 v 15 v 5 v 1F v 3F v 1A v 17 v 3E v 3D v 39 v 9 v 37 v 19 v 2A v 11 v 18 v 4 v 3C v 2E v 29 v 0 v 2D v 28 v 25 v 14 v 1E

    Таблица истинности исходной функции

    Набор Значение исходной функции Набор Значение исходной функции
    x 1 x 2 x 3 x 4 x 5 x 6 x 1 x 2 x 3 x 4 x 5 x 6
    000000 1 100000 ?
    000001 0 100001 ?
    000010 ? 100010 0
    000011 0 100011 ?
    000100 1 100100 ?
    000101 1 100101 1
    000110 ? 100110 0
    000111 1 100111 0
    001000 1 101000 1
    001001 1 101001 1
    001010 1 101010 1
    001011 ? 101011 0
    001100 0 101100 ?
    001101 ? 101101 1
    001110 0 101110 1
    001111 0 101111 0
    010000 1 110000 0
    010001 1 110001 0
    010010 1 110010 0
    010011 0 110011 0
    010100 1 110100 0
    010101 1 110101 0
    010110 0 110110 1
    010111 1 110111 1
    011000 1 111000 1
    011001 1 111001 1
    011010 1 111010 1
    011011 ? 111011 ?
    011100 1 111100 1
    011101 ? 111101 1
    011110 1 111110 1
    011111 1 111111 1

    ‘?’ обозначено значение наборов, на которых функция не определена.

    Цена ДНФ является суммой длин всех входящих в нее конъюнкций.

    2.2 Минимизация функции методом Квайна.

    Доопределим функцию нулями, получим конституэнты единицы, затем выполним операции попарного неполного склеивания и элементарного поглощения.

    На данном шаге все импликанты участвовали в операциях попарного неполного склеивания и были поглощены своими собственными частями. Поэтому простые импликанты на этом шаге не получены.

    В результате на данном шаге получаем простые импликанты:
    x 2 x 3 x 4 x 5 x 6 , x 1 x 2 x 4 x 5 x 6

    В результате на данном шаге получаем простые импликанты:
    x 3 x 4 x 5 , x 3 x 4 x 6 , x 2 x 3 x 6

    Нахождение тупиковых форм.

    • Единицы ДНФ, покрываемые импликантами СкДНФ, обозначаются «+».Импликанты, попадающие в ядро помечаются «*».
    • Единицы функции, которые покрываются только какой-то одной импликантой из системы простых импликант, помечаются “>”.
    • Единицы функции, покрываемые ядром, но не покрываемые только какой-то одной импликантой из системы простых импликант, помечаются “>>”.

    2.3 Минимизация функции методом Карт Карно.

    Дополним функцию единицами и построим Карты Карно.

    Нахождение тупиковых форм.

    2.4 Минимизация функции методом кубических покрытий.

    Рассмотрим комплекс кубов К(f) = L D, где L – множество единичных наборов, D – множество наборов, на которых ДНФ не определена.

    Будем выполнять операцию «*» для получения множества простых импликант.

    Нахождение тупиковых форм.

    E:

    11x11x
    0xx0x0
    01xx0x
    1x1xx0
    x11xxx
    0x01x1
    xx1x01
    x0010x

    МДНФ: x 1 x 2 x 4 x 5 v x 1 x 4 x 6 v x 1 x 2 x 5 v x 1 x 3 x 6 v x 2 x 3 v x 1 x 3 x 4 x 6 v x 3 x 5 x 6 v x 2 x 3 x 4 x 5 , цена=26

    3. Анализ полученных результатов

    Результат метода Кубических покрытий
    f3 = x 1 x 2 x 4 x 5 v x 1 x 4 x 6 v x 1 x 2 x 5 v x 1 x 3 x 6 v x 2 x 3 v x 1 x 3 x 4 x 6 v x 3 x 5 x 6 v x 2 x 3 x 4 x 5 , цена=26

    Общая таблица истинности

    Набор Исходная После Квайна После Карно После Кубических покрытий
    x 1 x 2 x 3 x 4 x 5 x 6 f0 f1 f2 f3
    000000 1 1 1 1
    000001 0 0 0 0
    000010 ? 0 1 1
    000011 0 0 0 0
    000100 1 1 1 1
    000101 1 1 1 1
    000110 ? 0 1 0
    000111 1 1 1 1
    001000 1 1 1 1
    001001 1 1 1 1
    001010 1 1 1 1
    001011 ? 0 1 0
    001100 0 0 0 0
    001101 ? 0 1 1
    001110 0 0 0 0
    001111 0 0 0 0
    010000 1 1 1 1
    010001 1 1 1 1
    010010 1 1 1 1
    010011 0 0 0 0
    010100 1 1 1 1
    010101 1 1 1 1
    010110 0 0 0 0
    010111 1 1 1 1
    011000 1 1 1 1
    011001 1 1 1 1
    011010 1 1 1 1
    011011 ? 0 1 1
    011100 1 1 1 1
    011101 ? 0 1 1
    011110 1 1 1 1
    011111 1 1 1 1
    100000 ? 0 1 0
    100001 ? 0 1 0
    100010 0 0 0 0
    100011 ? 0 1 0
    100100 ? 0 1 1
    100101 1 1 1 1
    100110 0 0 0 0
    100111 0 0 0 0
    101000 1 1 1 1
    101001 1 1 1 1
    101010 1 1 1 1
    101011 0 0 0 0
    101100 ? 0 1 1
    101101 1 1 1 1
    101110 1 1 1 1
    101111 0 0 0 0
    110000 0 0 0 0
    110001 0 0 0 0
    110010 0 0 0 0
    110011 0 0 0 0
    110100 0 0 0 0
    110101 0 0 0 0
    110110 1 1 1 1
    110111 1 1 1 1
    111000 1 1 1 1
    111001 1 1 1 1
    111010 1 1 1 1
    111011 ? 0 1 1
    111100 1 1 1 1
    111101 1 1 1 1
    111110 1 1 1 1
    111111 1 1 1 1

    АНАЛИЗ

    По таблице истинности видно, что минимизация функции проведена верно.

    В результате минимизации получили минимальные дизъюнктивные нормальные формы:

    1. Доопределив функцию нулями, методом Квайна получили МДНФ цены 46
    2. Доопределив функцию единицами, методом карт Карно получили МДНФ цены 37
    3. Доопределяя функцию по ходу выполнения алгоритма, методом кубических покрытий получили МДНФ цены 26

    Метод кубических покрытий приводит к наименьшей МДНФ. Это связано с тем, что минимизируется не полностью определенная функция. В результате минимальная форма принимает на наборах, на которых исходная функция не определена, такие значения, которые соответствуют наиболее оптимальному покрытию. Из всех методов наиболее трудоемким оказывается также метод кубических покрытий, но он удобен для программной реализации минимизации. Наименее трудоемким оказался метод Квайне.

    Похожие публикации:
    1. Как включить сенсорную плиту neff
    2. Как открыть авито в браузере
    3. Как открыть порты для стима
    4. Х меньше 4 какой промежуток

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

Ваш адрес email не будет опубликован. Обязательные поля помечены *