Усиление метода выделения переменных при решении логических уравнений за счет выбора функций для приведения из числа обновленных на предыдущих шагах и декомпозиции промежуточных результатов

Размещено на http://www.allbest.ru/

УСИЛЕНИЕ МЕТОДА ВЫДЕЛЕНИЯ ПЕРЕМЕННЫХ ПРИ РЕШЕНИИ ЛОГИЧЕСКИХ УРАВНЕНИЙ ЗА СЧЕТ ВЫБОРА ФУНКЦИЙ ДЛЯ ПРИВЕДЕНИЯ ИЗ ЧИСЛА ОБНОВЛЕННЫХ НА ПРЕДЫДУЩИХ ШАГАХ И ДЕКОМПОЗИЦИИ ПРОМЕЖУТОЧНЫХ РЕЗУЛЬТАТОВ

Пошерстник Марат Самуилович



В работе [1] для решения логических уравнений вида был предложен метод выделения переменных, усовершенствованный затем в [2]. Хотя с момента публикации работы [1] прошло уже более 35 лет, по мнению японских и некоторых российских ученых она не утратила актуальности до сих пор [3, 4]. В настоящей работе с целью дальнейшего повышения эффективности представленного в [1, 2] метода предлагается ряд приемов и алгоритмов, заменяющих промежуточные формы, получаемые при его реализации, семействами подмножеств логических функций меньшей сложности. Задача нахождения корней логических уравнений рассматривается в постановке, основы которой приведены в [1]. Часть применяемых далее понятий, терминов, определений и обозначений также заимствована из [1, 2] с небольшими дополнениями, изменениями и новой нумерацией. Некоторые формулировки упрощены по сравнению с [1, 2]. Так, например, вместо принятого в [1] выражения «формула, реализующая функцию» применяется выражение «формула функции». Напомним постановку задачи и некоторые определения.

Задана совокупность множеств ранга

включающие независимые переменные и дизъюнктивные формы (ДФ) локальных функций

Конъюнкции каждой из них содержат символы локальных функций низших рангов и независимых аргументов (со знаком инверсии или без него).

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

Определение 1. Приведенной относительно формой функции будем называть реализующую ее дизъюнктивную форму

де - выражения, не зависящие от переменной .

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

Условимся также процесс преобразования любой произвольно заданной функции к виду (2) называть выделением переменной в функции

Определение 2. Будем говорить, что переменная графически определяет функцию или функция графически зависит от , если существенно зависит от переменной и представлена (с точностью до вынесения за скобки ) в приведенной относительно форме.

Определение 3. Числа называются рангами независимой переменной либо локальной функции и определяются следующим образом:



где - ранг локальной функции либо простой переменной, входящей в ДФ функции.

Определение 4. Переменную будем называть отсекающей (неотсекающей), если хотя бы одна (ни одна) из конъюнкций , полученных в ходе реализации метода поэтапной подстановки локальных функций, (не) содержит выражение .

Чтобы проверить, является ли переменная отсекающей, достаточно при реализации поэтапной подстановки локальных функций опустить в них символы остальных переменных и локальных функций , не зависящих от .Наличие или отсутствие нуль-конъюнкции в полученной после выделения ДНФ относит к классу отсекающих либо неотсекающих переменных соответственно [1].

Определение 5. Согласно [2], при логическом умножении выражений и можно, не раскрывая скобки полностью, получить приведенное по выражение из 5-и конъюнкций вместо 7-и при обычном вычислении. В дальнейшем такую реализацию операции логического перемножения будем называть перемножением с неполным раскрытием скобок.

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

Определение7. Суммарное число конъюнкций в исходной совокупности (усеченной совокупности ) до (после) выделения переменной будем обозначать символом Суммарное число конъюнкций в ДНФ суперпозиции задаваемой исходной совокупностью (усеченной по совокупностью ), до (после) выделения переменной будем определять, считая, что нуль-конъюнкции () всех не выделенных перед подсчетом переменных ( в ,в ) соответствующей совокупности не обнулены . Величины , , (, ) будем называть соответственно числами конъюнкций в КФ ( в ДНФ) совокупностей Наряду с ними в зависимости от контекста будем использовать обозначения

Для любых локальных функций 1-го ранга числа конъюнкций в КФ и ДНФ одинаковы и равны числу дизъюнктивных членов в формуле :, а для любых выражений ранга величину можно определить по формуле



Определение 8. Критерием эффективности выделения переменной в [1] было выбрано число локальных функций, которые она графически определяет до выделения. Очевидно, что более точно указанная эффективность может быть определена величиной, прямо пропорциональной величине

уменьшения числа конъюнкций в ДНФ суперпозиции и обратно (прямо) пропорциональной увеличению (уменьшению) числа конъюнкций в КФ суперпозиции в результате выделения переменной То есть

если

если

если

Поправка введена для однозначности значений при

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

MОДИФИКАЦИЯ АЛГОРИТМА ВЫДЕЛЕНИЯ ПЕРЕМЕННЫХ, ПРИВОДЯЩАЯ К ОБРАЗОВАНИЮ СЕМЕЙСТВ СУПЕРПОЗИЦИЙ МЕНЬШЕЙ СЛОЖНОСТИ

Алгоритм выделения переменных , изложенный в [1, 2], можно модифицировать так, чтобы при формировании каждой промежуточной совокупности функций , приведенных по переменной с - ым () порядковым номером этапа происходило уменьшение ее объема по сравнению с прежней процедурой [2] . В настоящей работе предлагается производить указанное упрощение с помощью следующих приемов.

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

2. В случае, если после реализации нескольких шагов алгоритма множество функций, которые должны рассматриваться на следующем шаге, оказывается пустым, происходит прерывание процесса выделения. Реализованную до прерывания часть указанного процесса будем называть циклом выделений . После окончания текущего цикла выделений рассматриваем последнюю полученную локально усеченную суперпозицию . По построению ее главная функция графически зависит от переменной первого этапа цикла выделений : . Из-за этого становится возможным разложение полученной усеченной суперпозиции на так называемое декомпозиционное семейство (ДС), состоящее из двух или трех суперпозиций меньшей сложности либо, если - одночлен, сведениек новой неразделимой совокупности () . Во избежание повторной обработки совокупности , из которой была получена усеченная совокупность , удаляем из специального списка суперпозиций, предназначенных для дальнейшей обработки. Если в ДФ входит более одного члена, производим разложение усеченной суперпозиции по коэффициентам выделения функции на совокупности , , меньшей сложности.В каждую из них входит совокупность-основа , отличающаяся от отсутствием в ней ДФ локальных функций , и одно из дополнений основы ()[], которое включает ДФ соответствующих коэффициентов выделения () [] и одно из выражений () [], образуемых в результате подстановки в функцию нулевых значений пар коэффициентов и ( и ) [и ] соответственно. Подставляя в ДФ членов ДС , , нулевые значения вместо пар коэффициентов выделения и , и , и и, произведя дальнейшие вычисления, находим сужения , ,[5] множеств , , , формируемые из логических сумм сужений основы и функций ()[] соответствующих дополнений. Такой подход вытекает из широко известного метода неопределенных коэффициентов [7].

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

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

Предложенная выше модификация метода выделения переменных в большинстве случаев уменьшает объемы промежуточных форм по сравнению с результатами прежнего варианта [2] потому, что:

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

2) увеличивается «удельный вес» символов выделяемых переменных текущего цикла выделений в формулах локально приведенных функций, построенных в результате его выполнения. Из-за этого усиливается «отсев» конъюнкций, получаемых при перемножении, так как значительно возрастает вероятность образования нуль-конъюнкций. Следовательно, сильнее проявляются те свойства метода выделения переменных, которые обеспечили преимущество и высокую практическую ценность как ему, так и его предшественнику - методу последовательного перемножения ДНФ[6].

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

4) из-за значительного ограничения числа подставляемых функций происходит досрочное по сравнению с вариантом из [2] окончание циклов модифицированного процесса . То есть прежний вариант процесса [2] заменяется несколькими субпроцессами (циклами) с меньшими числами подставляемых функций и операций выделения.

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

Кроме того каждый из коэффициентов выделения в конце цикла может обратиться в нуль. В этом случае соответствующий член семейства исключается из дальнейшего рассмотрения. Даже если все коэффициенты выделения не обнуляются, производится декомпозиция рассматриваемой суперпозиции на ДС меньшей сложности. При прежнем варианте метода такое разложение до момента получения полностью усеченной суперпозиции функций при завершении задачи произойти не могло.

Таким образом, при выполнении каждого процесса (субпроцесса) модифицированного выделения переменных происходит намного меньший (по сравнению с прежним вариантом [2]) рост максимальных объемов используемой памяти ЭВМ и расхода времени на их обработку.

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

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

Определение 10. Отсекающим [локально отсекающим] будем называть первый [-ый ] этап выделения переменной из произвольно выбранной суперпозиции локальных функций, в результате выполнения которого образуются приведенные формы всех зависящих от локальных функций [только тех локальных функций, которые сформировались либо изменили вид своих формул на предшествующем -ом отсекающем этапе] и была исключена из дальнейшего рассмотрения хотя бы одна нуль-конъюнкция .

Определение 11. Циклом выделений будем называть последовательность всех возможных отсекающих либо локально отсекающих этапов выделения независимых переменных, производных от обновлений предыдущих, которая не может быть дополнена ни одним локально отсекающим этапом.

Опираясь на прежние формулировки метода[1, 2] , приведенные выше предложения и приемы упрощения исходной совокупности функций, правила распознавания новых или обновленных функций по величине их кода можно сформулировать модифицированный алгоритм решения логических уравнений. В дальнейшем будем называть его алгоритмом с разложением (декомпозицией) промежуточных форм суперпозиции локальных функций по коэффициентам выделения главной функции. Его описание включает основную часть и набор вспомогательных процедур, отделенных друг от друга и остального текста строкой звездочек. Упрощая описание алгоритма, условимся по умолчанию передавать управление внутри каждого модуля следующему пункту алгоритма.

Окончательная формулировка алгоритма решения поставленной задачи состоит из 20-и пунктов и 4-х процедур.

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

2. Если множество пусто, переходим в п. 8. Иначе пересылаем первую по порядку размещения совокупность (top-совокупность) функций из стека в текущую рабочую область памяти. Запоминаем в переменной максимальное значение кода любого независимого аргумента . Затем формируем коды всех локальных функций так, чтобы их значения превышали значения кодов любого независимого аргумента То есть так, чтобы . Заносим в переменную максимальный по величине код простых переменных( функций) совокупности, в которой предусматривается очередное выделение. Начальное значение переменной. А в переменную заносим максимальный по величине код локальных функций совокупности, полученной после очередного выделения. Начальное значение переменной . Пока выделение переменных в совокупности не начато будем полагать индекс рассматриваемых независимых переменных и порядковый номер очередного отсекающего этапа цикла выделений равными нулю, а обозначения и идентичными. Создаем соответствующее текущей совокупности функций множествонезависимых аргументов локальных функций . Способом, изложенным в [1], находим неотсекающие переменные. Исключаем их из множества.

3. Если все переменные отмечены как локально неотсекающие и существует непустое множество , полученное из в результате -го этапа цикла выделений, локально усеченное по всем переменным, выполняем для него процедуру формирования ДС,описанную в пп. 17,18, исключаем из и переходим в п. 2. Иначе переходим в п. 4.

4. Увеличиваем на единицу индекс u: независимых аргументов и рассматриваем переменную . Если она не входит в множество переменных или помечена как неотсекающая переменная , переходим в п.4 Если ||, переходим в п. 5.Иначе рассматриваем совокупность , размещенную в рабочей области памяти. В пробном режиме выполняем процедуру модифицированного выделения переменной , описанную в пп. 9-12. Для этого заносим в переменную значение переменной . Затем для всех локальных функций 1-го ранга, графически зависящих от , и тех функций более высоких рангов, у которых изменился вид формул либо коды которых превышают текущее значение переменной Пробный режим выделения в отличие от штатного не приводит после своего выполнения к замене исходной совокупности локальных функций результатами выделения. Если функций, удовлетворяющих указанным выше условиям, не найдено, фиксируем нулевое значение показателя эффективности выделения рассматриваемой переменной , помечаем ее как локально неотсекающую и переходим в п.4.Иначе в ходе пробного выделения определяем по формуле (3) показатель эффективности выделения очередной непомеченной переменной . Запоминаем текущее значение переменной и значения переменных , .

5.По результатам пробного выделения всех рассмотренных ранее переменных выбираем переменную с максимальным значением показателя эффективности выделения. Если значит все показатели имеют нулевые значения, то есть текущий цикл выделения завершен. Тогда переходим в п. 7, иначе переходим в п. 6.

6. Выделяем переменную в штатном режиме с помощью процедуры, описанной в пп. 9 - 12 . Для этого заносим в переменную значение переменной . Затем получаем результат выделения - совокупность в рабочей области памяти.

Полагаем , увеличиваем на единицу значение . Запоминаем в переменной максимальный код локальных функций полученной совокупности приведенных функций .

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

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

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

Перед началом цикла выделения в переименованной неразделимой совокупности , (если - одночлен), или в очередном члене семейства или его сужении , производим пробные выделения переменных с помощью подпрограмм прежнего [2] (пп. 13-16) варианта алгоритма. Если максимальные объемы промежуточных совокупностей, сформированных в результате пробного выделения согласно прежнему варианту[2], больше соответствующих объемов, полученных после выполнения предшествующего цикла выделений модифицированного варианта, производим переименование текущего члена ДС и дописывание его функций или функций переименованной неразделимой совокупности в начало (вершину) спискасовокупностей, предназначенных для дальнейшей обработки по модифицированному варианту алгоритма . В противном случае преобразование рассматриваемого члена семейства, его сужения или совокупности совершается в штатном режиме прежней процедурой [2] (пп. 13-16). В результате указанных действий получаем часть корней исходного уравнения , которыми дополняем множество , исключая все возможные повторы и поглощения.

Переходим в п. 2.

8. Конец работы.

9. Начало модифицированной процедуры выделения переменной с параметрами:

1. Переменная 2. Переменная

3. Переменная 3. Переменная

4. Режим работы. Варианты значений: пробный, штатный.

Запоминаем в переменной значение переменной .

сли режим работы - штатный, в переменную заносим значение переменной .

Рассматриваем локальные функции первого ранга , существенно зависящие от и с помощью операции вынесения за скобки выделяем в них переменную 

Согласно определению 3 находим ранги выражений После обработки всех функций первого ранга переходим в п. 10.

10.Рассматриваем очередную локальную функцию ранга существенно зависящую от значение кода которой больше значения переменной Это свойство кода выбранной функцииозначает, что она сформирована на предыдущем этапе выделения. Увеличиваем : и переходим в п. 10. Применяя вместо операции логического перемножения приведенных форм функций ее модификацию с неполным раскрытием скобок, приведенную в [2], и заменяя функции низших рангов выражениями графически зависящими от переменной находим приведенные формы Если является главной функцией суперпозиции и ее приведенная форма исключаем из множества и переходим в п.12. Иначе согласно определению 3 находим приведенную форму и выражения Если проверяем, найдена ли хотя бы одна функция со значением кода, превышающим . Если не найдена, помечаем , фиксируем показатель эффективности выделения и переходим в п. 12. Если такая функция найдена, значит в данный момент получена ТУС. Тогда, исключая из результата выделения все выражения, графически зависящие от от которых главная функция суперпозиции перестала зависеть , получаем ТУБСи переходим в п. 11. Иначе увеличиваем порядковый номер локальной функции : и переходим в п. 10.

11. Совокупность локальных функций полученной ранее ТУБСпреобразуем согласно приведенному в [2] алгоритму в МУБС, Если режим работы - пробный, определяем и фиксируем идентификатор текущей переменной , показатель эффективности ее выделения , значение переменной, помечаем и переходим в п. 12.

Если режим работы - штатный, увеличиваем порядковый номер этапа цикла выделений: . Присваиваем полученной МУБС новое обозначение . Заносим в переменную максимальный по величине код всех локальных функций полученной совокупности .

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

Обнуляем индекс независимых аргументов .

Анализируем полученную форму . И выполняем формирование и обработку ДС или неразделимой совокупности функций с помощью подпрограммы пп. 17-18.

12.Конец модифицированной процедуры выделения .

13. Начало процедуры получения усеченного по всем переменным множества функций с помощью варианта алгоритма выделения, описанного в [2], не разлагающего промежуточные скобочные формы на семейство подмножеств.

14. Полагаем .

15. Увеличиваем значение Если переходим в п.16. Иначе выделяем переменную в функциях члена очередного семейства множеств или исходной совокупности функций с помощью варианта алгоритма выделения, описанного в [2]. Он не предусматривает разложения промежуточных форм совокупности на подмножества и реализуется процедурой пп. 9-12 в пробном и штатном режимах при значении параметра . Переходим в п.15. переменный цикл множество

16. Конец процедуры получения усеченного по всем переменным множества.

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

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

Организуем цикл по перебору коэффициентов выделения . Для каждого ненулевого коэффициента {}выделения строим соответствующую суженную усеченную совокупность, считая коэффициенты, отличные от , равными нулю. Рассматриваем сначала главную функцию и подставляем в нее нулевые значения функций, принадлежащих разности множеств { } . Затем, в порядке убывания рангов продолжаем рассмотрение остальных функций совокупности , подставляя в них значения функций меньших рангов. Так как часть функций, не соответствующих рассматриваемому члену семейства, обращается в ноль, а другие функции можно опустить как несущественные аргументы главной функции, получаем суженные усеченные совокупности , , множеств , , меньшей размерности. Они сформированы из логических сумм сужений основы и функций ()[] соответствующих дополнений.

Полученные множества упорядочиваем в порядке возрастания их сложности и , реализуя подпрограммы пп. 13 - 16, поочередно осуществляем с ними в пробном режиме выделения переменных с помощью прежнего варианта [2] выделения как с независимыми совокупностями функций. Если максимальный объем промежуточных совокупностей, сформированных в результате пробного выделения согласно прежнему варианту[2], больше соответствующего объема, полученного после выполнения предшествующего цикла модифицированного варианта выделения, присваиваем рассмотренной совокупности новое значение индекса : и производим дописывание функций рассмотренного члена семейства в начало (вершину) списка совокупностей функций, предназначенных для дальнейшей обработки. Если рассмотрены не все члены семейства, продолжаем их обработку ( п.17). Иначе переходим в п.18. Если пробный режим прежней процедуры выделения (пп.13-16) рассматриваемого члена семейства или его сужения эффективнее модернизированного варианта, реализуем соответствующий штатный режим. Затем , исключая повторения и поглощения полученных корней, дополняем ими множество .

18. Конец процедуры обработки ДС подмножеств

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

Если приведенная форма главной функции суперпозиции обратилась в 0, оставляем без изменений множествокорней исходного уравнения и переходим в п. 20. Иначе с помощью лексикографического перебора [2, 7] находим часть корней исходного уравнения, получая комбинации дизъюнкций локальных функций усеченной по всем переменным совокупности и дополняем найденными комбинациями множество корней исходного уравнения. Рассматриваем множество и удаляем из него повторы и поглощаемые варианты корней. Удаляем совокупность из множества

20. Конец процедуры формирования корней.

Пример 1. С помощью предложенного алгоритма решим уравнение, приведенное в [6, с. 20]. Если привести обозначения переменных и функций из [6] к обозначениям, принятым в настоящей работе,

т.е.

то указанное уравнение может быть задано следующей совокупностью отношений:

, ,

, ,

, ,

{ .

1. Заносим исходную совокупность локальных функций в множество .

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

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

Создаем соответствующее множество {} независимых аргументов. C помощью способа, приведенного в [1], убеждаемся, что все переменные множества являются отсекающими. Поэтому его состав не изменяется. Так как процесс реализации цикла выделений еще не запущен, обнуляем значения порядкового номера этапа цикла выделений и индекса переменной выделения.
3.Так как множество не пусто и не все его элементы отмечены квк локально неотсекающие, полагаем индекс независимой переменной равным нулю. Переходим в п. 4.

4. Порядковый номер этапа выделения Поэтому рассматриваем текущую совокупность .

Организуем арифметический цикл с параметром таким, что его начальное значение и шаг изменения равны 1, а конечное значение равно || = . В теле цикла с помощью процедуры пп.9-12 производим пробное выделение каждой из непомеченных независимых переменных для совокупности В начале процедуры производим обновление значения переменной . Так как значение меньше значения кода любой из локальных функций по построению, то при пробном выделении ищем приведенные формы всех функций и функции существенно зависящих от переменной выделения Так как все переменные множества не помечены, выполняем || = пробных попыток выделения переменных из функций множества . Фиксируем характеристики процесса получения различных вариантов множества следующего этапа цикла выделений, и когда превысит значение || , переходим в п. 5.

5. Выбираем переменнуюкак наиболее эффективную из испытанных в п.4 независимых переменных. Процесс ее выделения имеет следующие характеристики:

1) уменьшение числа конъюнкций в ДНФ функции : ;

2) увеличение числа конъюнкций в КФ совокупности : ;

3) оценка эффективности выделения - Переходим в п.6

6. С помощью процедуры пп. 9-12 производим штатное выделение выбранной в п.5 переменной . Вначале обновляем значение переменной , пересылая в нее значение переменной . Так как переменная выбрана в п. 5 в первый раз после образования множеств и, т.е. в случае, когда исключаем из как неотсекающую и снимаем пометки всех переменных о неотсекаемости . Затем увеличиваем на единицу значение порядкового номера этапа цикла выделения: и обозначаем полученную совокупность как . В завершение штатного выделения переменной обновляем значение переменной максимальным значением кодов функций совокупности , равным 44. Это код функции .Так как при первом по порядку этапе выделения работа данного алгоритма не отличается от работы алгоритма, описанного в [1, 2], множество из 26-и функций, сформированное в результате его выполнения, приводить не будем.

Полагаем и переходим в п. 3.

3. . Поэтому рассматриваем множество Так как множество не пусто и не все его элементы отмечены квк неотсекающие, полагаем индекс независимой переменной равным нулю. Переходим в п. 4.

4. С помощью процедуры пп. 9-12 производим пробные выделения каждой из 9-и непомеченных независимых переменных (1, 2, 3, 4, 5, 6, 7, 9, 10) совокупности. Вначале значение переменной заносим в . Это код функции . Затем ищем приведенные формы всех функций существенно зависящих от переменной выделения у которых ранг либо код больше значения переменной либо изменились формулы на предыдущем этапе выделения. Помечаем локально неотсекающие переменные.Фиксируем характеристики пробных выделений остальных переменных и переходим в п. 3. После рассмотрения всех непомеченных переменных из множества переходим в п. 5.

5. Выбираем переменную как наиболее эффективную из испытанных в п.4 независимых переменных. Процесс ее выделения имеет следующие характеристики:

Переходим в п.6.

6. С помощью процедуры пп. 9-12 производим штатное выделение выбранной в п. 5 переменной . Вначале обновляем значение переменной , пересылая в нее значение переменной Получаем приведенные формы функций совокупности . В завершение штатного режима выделения увеличим порядковый номер этапа цикла выделения: , обозначим полученную совокупность как . В завершение штатного выделения переменной обновляем значение переменной максимальным значением кодов функций совокупности , равным 57. Т. к. значения индексов вновь образованных функций совпадают с их кодами, это код функции .

Совокупность состоит из 33 функций:

{

{

{

{

{

{



{ {

В завершение процедуры штатного выделения снимаем отметки о локальной неотсекаемости со всех независимых переменных множества . Полагаем индекс и переходим в п. 3.

3. . Поэтому рассматриваем множество Так как множество не пусто и не все его элементы отмечены квк неотсекающие, полагаем индекс независимой переменной равным нулю. Переходим в п.

4. С помощью процедуры пп. 9-12 производим пробные выделения каждой из 9-и непомеченных независимых переменных (1, 3, 4, 5, 6, 7, 9, 10) совокупности и фиксируем их характеристики. Вначале значение переменной заносим в . Это код функции .

Отмечаем, что переменные , имеют нулевой показатель эффективности выделения. Отмечаем их как локально неотсекающие и переходим в п. 5.

5. и - наиболее эффективные из испытанных в п.4 переменных. Процессы их выделения имеют близкие по величине характеристики:

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

6. С помощью процедуры пп. 9-12 производим штатное выделение выбранной в п. 5 переменной . Вначале обновляем значение переменной , пересылая в нее значение переменной Получаем приведенные формы функций совокупности . В завершение штатного режима выделения увеличим порядковый номер этапа цикла выделения: , обозначаем полученную совокупность как . После штатного выделения переменной обновляем значение переменной максимальным значением кодов функций совокупности , равным 68. Т. к. значения индексов вновь образованных функций совпадают с их кодами, это код функции .

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

\

{

{ {

{ {

{ {{, {

{

В завершение процедуры штатного выделения снимаем все пометки о неотсекаемости независимых переменных . Полагаем индекс и переходим в п. 3.

3. . Поэтому рассматриваем множество Так как множество не пусто и не все его элементы отмечены как неотсекающие, полагаем индекс независимой переменной равным нулю. Переходим в п. 4.

4. С помощью процедуры пп. 9-12 производим пробные выделения каждой из 9-и непомеченных независимых переменных (1, 3, 4, 5, 6, 7, 9, 10) совокупности и фиксируем их характеристики. Вначале значение переменной заносим в . Это код функции .

Отмечаем, что переменные и имеют нулевой показатель эффективности выделения . Отмечаем их как локально неотсекающие и переходим в п. 5.

5. Выбираем как единственную эффективную из испытанных в п.3 независимых переменных. Процесс ее выделения имеет следующие характеристики: Переходим в п.6.

6. С помощью процедуры пп. 9-12 производим штатное выделение выбранной в п. 5 переменной . Вначале обновляем значение переменной , пересылая в нее значение переменной Получаем приведенные формы функций совокупности . В завершение штатного режима выделения увеличиваем порядковый номер этапа цикла выделения: и обозначаем полученную совокупность как . После штатного выделения переменной обновляем значение переменной максимальным значением кодов функций совокупности , равным 85. Т. к. значения индексов вновь образованных функций совпадают с их кодами, это код функции .

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



{

{ {

{ {

{ { { {

4. С помощью процедуры пп. 9-12 производим пробные выделения каждой из 9-и непомеченных независимых переменных (1, 3, 4, 5, 6, 7, 9, 10) совокупности и фиксируем их характеристики. Вначале значение переменной заносим в .

Отмечаем, что все переменные имеют нулевой показатель эффективности выделения. Фиксируем наибольшее число символов , использованных к настоящему моменту при реализации этапов текущего цикла выделений Поэтому прерываем реализацию текущего цикла выделений. Отмечаем, что в процессе его выполнения при одном выделении потребовалось запоминать не более 175 символов . Теперь для разложения суперпозиции по коэффициентам главной функции переходим в п. 7.

7, 17, 18, 13-16.Рассматриваем приведенную формуглавной функции суперпозиции . Применяя метод неопределенных коэффициентов и удаляя функции , от которых перестала зависеть, находим суженные множества членов ДС.

:

;

; ;

; ;

; ;

; ; ; ; . :

:

; ;

; ; ;

; ; ;

; .

:

; ;

;

; ; ; ;

; .

Рассматриваем все суженные множества ДС и с помощью прежней процедуры пп. 13-16 [2] в пробном режиме находим корни соответствующих логических уравнений и фиксируем необходимые для их получения объемы памяти.

Совокупность . При нахождения корней для одного выделения потребовалось запомнить не более 163 символов.Корней не найдено.Совокупность . При нахождения корней для одного выделения потребовалось запомнить не более 88 символов.После нахождения и минимизации конечной ДНФ получено 3 корня: , которые заносятся в множество . Они полностью совпадают с окончательными результатами того же примера из работы [6].Совокупность . При нахождения корней для одного выделения потребовалось запомнить не более 37 символов.Корней не найдено.Заметим, что при реализации предложенного варианта метода до момента прерывания для одного выделения требовалось запоминать не более 175 символов.
Так как эта величина больше любого из приведенных выше объемов памяти, необходимых для реализации членов ДС с помощью прежней процедуры не будем пополнять ими список для применения к ним в дальнейшем модифицированной процедуры выделения. Вместо этого реализуем для членов семейства штатный режим прежней процедуры выделения и занесем его результаты во множество .

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

2. Так как стек оказался пустым, переходим в п. 8.

8. Конец работы.

Для оценки эффективности предложенного метода найдем с помощью прежней процедуры пп. 13-16 [2] корни исходного уравнения , заданного совокупностью . При их нахождении для одного выделения потребовалось запомнить не более 262 символов.

Следовательно модифицированный вариант выделения эффективнее прежнего варианта в раза.



Заключение

В предлагаемой статье рассматривается применение метода выделения переменных [1, 2] не только для всего объема исходной суперпозиции локальных функций, но и для ее отдельных областей . Это позволяет ограничить величиной, пропорциональной доле области в общем объеме исходной суперпозиции, максимальные размеры промежуточных форм и умерить взрывной характер их роста при формировании. Описаны приемы разложения исходной суперпозиции на ДС суперпозиций меньшей сложности. На конкретном примере из книги [6] А.Д. Закревского показано, что применение предложенного варианта метода уменьшает максимальный объем промежуточных форм в 1,5 раза по сравнению с прежней процедурой [2] выделения.

Дополнительная экспериментальная проверка показала, что для решения с помощью вышеизложенного алгоритма логического уравнения из примера 4 работы [1] потребовалось размещать в памяти компьютера до 322 символов вместо 350 символов, необходимых при применении вырианта алгоритма из работы [2]. Исправляя опечатку, допущенную в решении указанного примера в работе [1], укажем правильное значение корня заданного в нем логического уравнения: .

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



Библиографический список

1. Пошерстник М. С. Решение логических уравнений методом выделения переменных. Автоматика и телемеханика, № 2, стр.132-140, 1979.

2. Пошерстник М. С. Об усовершенствовании метода выделения переменных при решении логических уравнений . Таврический вестник математики и информатики, №3, стр. 68-90, 2016

3. Владимирова Ю. С. Компьютеризация булевой алгебры в диалоговой системе структурированного программирования. Дис. … канд. физ.-матем. наук. М.: МГУ, 2004,

4. Донской В. И. Дискретная математика. Издательство «Сонат», Cимферополь, 2000, 360 c.

5. Закревский А. Д. Логические уравнения. «Едиториал УРСС», Москва, 2003.

6. Шнейдер В. Е., Слуцкий А. И., Шумов А. С. Краткий курс высшей математики - 1972 - Математика он-лайн - Высшая математика



Аннотация

В журнале «Автоматика и телемеханика» №2 за1979 год для решения логических уравнений вида был предложен метод выделения переменных.

В настоящей работе предлагается модификация указанного метода, уменьшающая сложность получаемых промежуточных форм за счет 1)реализации выделения группы переменных последовательностью шагов, называемых циклами; 2) выделения первой переменной цикла, если при этом образуется хотя бы одна нуль-конъюнкция , исключаемая из дальнейшего рассмотрения; 3) выделения остальных переменных цикла в локальных функциях, реализуемых формулами, которые либо содержат символы выделяемой переменной либо были изменены (сформированы) на предыдущем шаге выделения и образуют не менее одной нуль-конъюнкции при преобразовании их к ДФ . После реализации нескольких шагов алгоритма выделение очередной переменной завершается получением пустого множества функций, которые подлежат рассмотрению на следующем шаге. Тогда текущий цикл выделений заканчивается и производится разложение последней полученной суперпозиции с главной функцией , ДФ которой по построению имеет не менее 2-х членов с ненулевыми коэффициентами , на так называемое декомпозиционное семейство из нескольких суперпозиций меньшей сложности. Каждое из них состоит из суперпозиции-основы, не включающей функций , и дополнений основы, каждое из которых состоит из функций либо либо . Затем преобразованию подвергается каждый член семейства, формируемый сужением объединения множеств функций основы и функций соответствующих дополнений. Затем промежуточные суперпозиции обрабатываются либо новыми циклами выделений либо прежним вариантом алгоритма выделения в зависимости от их сравнительной эффективности. Работа алгоритма завершается после обработки всех полученных суперпозиций. Библ. 7.

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

Размещено на Allbest.ru

...