 |
Главная |
Второй этап (получение минимальной формы).
 2019-07-03 |
 221 |
 Обсуждений (0) |
из
5.00
|
Сокращенная форма может содержать лишние члены, исключение которых из выражения функции не повлияет на значение функции.
Таким образом, дальнейшее упрощение логического выражения достигается исключением из выражения лишних членов. В этом и заключается содержание второго этапа минимизации. Покажем этот этап минимизации логического выражения на примере построения логического устройства для функции в таблице 19.
Рисунок 38 – Схема логического устройства в базисе И, ИЛИ, НЕ
Таблица 19
| x1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| x2 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| x3 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| x 4 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| f(x1,x2,x3, x4) | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
Совершенная ДНФ.данной функции
| (3.14) |
Для получения сокращенной формы проводим операции склеивания и поглощения
Полученное выражение представляет собой сокращенную форму логического выражения заданной функции, а члены его — простые импликанты функции. Переход от сокращенной формы к минимальной осуществляется с помощью импликантной матрицы, приведенной в таблице 20.
В столбцы импликантной матрицы вписываются члены СДНФ заданной функции, в строки — простые импликанты функции, т. е. члены сокращенной формы логического выражения функции.
Таблица 20.
Простые импликанты
Члены СДНФ
Отмечаются (например, крестиками) столбцы членов СДНФ, поглощаемых отдельными простыми импликантами. В таблице 20 простая импликанта поглощает члены , , и в первом и во втором столбцах первой строки поставлены крестики; вторая импликанта поглощает первый и третий члены СДНФ, и поставлены крестики в первом и третьем столбцах второй строки и т. д. Импликанты, которые не могут быть лишними и, следовательно, не могут быть исключены из сокращенной формы, составляют ядро. Входящие в ядро импликанты легко определяются по импликантной матрице. Для каждой из них имеется хотя бы один столбец, перекрываемый только данной импликантой.
В рассматриваемом примере ядро составляют импликанты и, (только ими перекрываются второй и шестой столбцы матрицы). Исключение из сокращенной формы одновременно всех импликант, не входящих в ядро, невозможно, так как исключение одной из импликант может превратить другую уже в нелишний член.
Для получения минимальной формы достаточно выбрать из импликант, не входящих в ядро, такое минимальное их число с минимальным количеством букв в каждой из этих импликант, которое обеспечит перекрытие всех столбцов импликантной матрицы, не перекрытых членами ядра. В рассматриваемом примере необходимо импликантами, не входящими в ядро, перекрыть третий и четвертый столбцы матрицы. Это может быть достигнуто различными способами, но так как необходимо выбирать минимальное число импликант, то, очевидно, для перекрытия этих столбцов следует выбрать импликанту . Минимальная дизъюнктивная нормальная форма (МДНФ) заданной функции
Роль этих имликант в выражении сокращенной формы функции (3.15) заключается лишь в том, чтобы на приведенных наборах (3.17) значений аргументов присваивать функции значение 1. Однако при этих наборах функция имеет значение 1 из-за остальных импликант выражения (3.15). Действительно, подставляя значения (3.17) в (3.16), получаем:
исходной для минимизации формой логического выражения заданной функции является СКНФ;
пары склеиваемых членов имеют вид и ;
операция поглощения проводится в соответствии с выражением.
Склеивающиеся пары членов:
первый и третий члены (результат склеивания );
первый и четвертый члены (результат склеивания ):
