КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Метод неопределенных коэффициентов
Метод может быть применен для минимизации функции любого числа аргументов, однако для простоты изложения и большей наглядности рассмотрим его на примере минимизации функции трех аргументов [5-13].
Представим функцию f(x1,x2,x3) в виде следующей ДНФ:
f(x1,x2,x3)=K11x1ÚK10`x1ÚK21x2ÚK20`x2ÚK31x3ÚK30`x3Ú
ÚK1211x1x2ÚK1210x1`x2ÚK1201`x1x2ÚK1200`x1`x2Ú
ÚK1311x1x3ÚK1310x1`x3ÚK1301`x1x3ÚK1300`x1`x3Ú
ÚK2311x2x3ÚK2310x2`x3ÚÚK2301`x2x3ÚK2300`x2`x3Ú (4.12)
ÚK123111x1x2x3ÚK123110x1x2`x3ÚK123101x1`x2x3Ú
ÚK123100x1`x2`x3ÚK123011`x1x2x3ÚK123010x1`x2x3Ú
ÚK123001`x1`x2x3ÚK123000`x1`x2`x3.
Здесь представлены всевозможные конъюнктивные члены, которые могут входить в ДНФ функции f(x1,x2,x3). Коэффициенты K с различными индексами являются неопределенными и подбираются так, чтобы получающаяся после этого дизъюнктивная форма была минимальной. Если задавать всевозможные наборы значений аргументов <x1, x2, x3> и приравнивать полученное после этого выражение (отбрасывая нулевые конъюнкции) значению функции на выбранных наборах, получим систему 2n уравнений для определения коэффициентов K:
Пусть таблично задана некоторая функция f(x1,x2,x3). Если набор <x1,x2,x3> таков, что функция на этом наборе равна 0, то в правой части соответствующего уравнения будет стоять 0. Для удовлетворения этого уравнения необходимо приравнять 0 все коэффициенты K, входящие в левую часть рассматриваемого уравнения.
В уравнениях, где справа стоят единицы, вычеркнем слева все нулевые коэффициенты. Из оставшихся коэффициентов приравняем единицекоэффициенты, определяющие конъюнкции наименьшего возможного ранга, а остальные примем равными 0 (это можно сделать, так как дизъюнкция обращается в 1, если хотя бы один член ее равен 1). Единичные коэффициенты Ki определят минимальную ДНФ (МДНФ).
Пример 4.12. Минимизировать данную функцию
f(x1,x2,x3)=x1x2x3Vx1x2`x3Vx1`x2x3Vx1`x2`x3V`x1`x2`x3.
Составляем систему:
Из пятого, шестого и седьмого уравнений вытекает, что
K10=K20=K21=K30=K31=K1200=K1201=K1300=K1301=K2301=K2310=
=K2311=K123001=K123010=K123011=0.
После этого данная система примет вид:
Приравняем 0 в каждом уравнении все коэффициенты, кроме тех, которые отвечают конъюнкциям, содержащим наименьше число переменных:
K1211=K1201=K1311=K1310=K123111=K123110=K123101=K123100=K123000=0.
После этого получаем систему:
Отсюда находим МДНФ для данной функции: f(x1,x2,x3)=x1V`x2`x3.
Дата добавления: 2015-08-05; просмотров: 143; Мы поможем в написании вашей работы!; Нарушение авторских прав |