2015-03-08
895
Предназначен для получения линейных форм логических формул, может быть применен для минимизации логических формул для любого числа переменных. В ручном варианте применяют для числа переменных не более пяти. Логическую функцию представляют в виде ДНФ. В общем виде, например, для трех переменных она имеет следующий вид:
f(x1,x2,x3) = k11x1Ú k01x1Ú k12x2Ú k02x2Ú k13x3Ú k03x3Ú k1112x1x2Ú k1012x1x2Ú k12x1x2Ú k0112x1x2 Ú k0012x1x2 k1113x1x3Ú k1013x1x3Ú k0013x1x3 Ú k1123x2x3 Ú k1023x2x3Ú k0123x2x3Ú k0023x2x3Ú k111123x1x2x3Ú k110123x1x2x3Ú k101123x1x2x3Ú k100123x1x2x3Ú k011123x1x2x3Ú k010123x1x2x3Ú k001123x1x2x3Ú k000123x1x2x3
В этой дизъюнктивной норм. форме коэффициенты с индексами – это определенный коэффициент, принимающий значение 0 и 1 и подбирается таким образом, чтобы ДНФ была минимальная. Задавая различные наборы переменных x1,x2,x3 и приравнивая полученные выражения соответствующим значениям функции, получают систему уравнений для определения коэффициента к:
f (0,0,0) = k 01Ú k 02 Ú k 03Ú k 0012Ú k 0023Ú k 000123
f (0,0,1) = k 01Ú k 02 Ú k 13Ú k 0012Ú k 0113Ú k 0123Ú k 001123
|
|
|
……………………………………………
f (1,1,1) = k 11Ú k 12 Ú k 13Ú k 1112Ú k 1113Ú k 1123Ú k 111123
f (x 1, x 2, x 3) = 0 Ú 1
Задание некоторой функции определяет значение первых частей системы: если f = 0 на соответствующем наборе переменных, то все коэффициенты входящие в уравнение, будут равны нулю. Это следует из свойства дизъюнкции. Тогда и в уравнении, где функция принимает единичное значение, надо вычеркивать все нулевые коэффициенты. Из оставшихся коэффициентов надо выбрать такой, который определяет темп наименьшего, и приравнять его к единице. А остальные коэффициенты приравнять к 0. Т.о. единичные коэффициенты определяют искомую ДНФ для системы уравнений.
Рассмотрим f (x 1, x 2, x 3) = Ú F (0,2,4,7), так называется десятичная форма записи для логического выражения f (x 1, x 2, x 3)=,, Ú, x 2, Ú x 1,, Ú x 1, x 2, x 3
Для получения коэффициентов: 1) Выбрать строку, в которой функция равна нулю, и все коэффициенты приравнять к нулю. Если все нулевые строки просмотрены, то переходим к шагу 2. 2) Просмотрим строки, где функция равна еденице, и в этих строках вычеркиваем коэффициенты, которые принадлежат строкам с нулевым значением функции. 3) Переписывают все модифицированные уровнения.
В полученной системе уравнений просматривают каждую строку и вычеркивают максимально возможное количество коэффициентов таким образом, чтобы ранг оставшихся терминов был минимальным.
k0023Ú k0013Ú k000123=1
k0013Ú k000123=1
k0023Ú k000123=1
k000123=1
В модифицированной системе вычеркивают коэффициенты максимального ранга. Оставшиеся коэффициенты позволяют получить минимальную форму:
|
|
|
f *(x 1, x 2, x 3)=,Ú, Ú x 1, x 2, x 3
