Главная 
Наука Наука | Естественные Минимизация булевых функций по совпадению множеств
Наука Наука | Естественные Минимизация булевых функций по совпадению множеств
| Минимизация булевых функций по совпадению множеств |
|
|
| Автор Олег Дамаскин | |
| 07.09.2008 г. | |
|
Минимизация булевых функций по совпадению множеств Minimization of Boolean Functions applying Equivalence of Sets livejournal - http://obdamaskin.livejournal.com/4630.html В "Представление информации булевой формулой" ( http://moiidei.com/nauka-estestvennyie/predstavlenie-informatsii-bulevoy-formuloy-2.html ) уже упоминалось, что одной из проблем представления информации булевой формулой является проблема формирования формулы по крайней мере с минимальным числом букв в ней. Эта проблема часто стоит и перед разработчиками логических схем для различных устройств, включая конечные автоматы и микросхемы для компьтеров. Ведь число букв в формуле булевой функции, реализуемой логической схемой, определяет число элементов в схеме. "Существуют несколько способов минимизации булевых функций.Прежде всего,это аналитический символьный и аналитический кодовый методы,метод Квайна - Мак-Класки, метод Блека - Порецкого, метод обобщенных кодов[11] и графическая минимизация с помощью карт Карно[12]. Пример для демонстрации аналитических методов: z = x_y+xy_+xy = (x_y+xy)+(xy_+xy) = y(x_+x) + x(y_+y) = x+y. z = 01+10+11 = (01+11)+(10+11) = -1+1- = x+y. Первые четыре метода чрезвычайно громоздки и малоэффективны уже при количестве аргументов более четырёх. Метод обобщенных кодов ориентирован на использование ЭВМ,однако может использоваться и при ручном синтезе для функций от большого числа переменных." (http://ruslogic.narod.ru/lectures/3.htm ) Я бы добавил к этому высказыванию несколько субъективных замечений. 1. Большинство методов фактически минимизируют функцию только на уровне ДНФ (дизъюнктивной нормальной формы), т.е. в отсутствии скобок, которые то и дают реальное уменьшение числа букв в формуле. 2. Сокращение числа букв осуществляется по правилам булевой алгебры (метод Блейка) и зависит от от вашего опыта. (http://www.sgu.ru/ie/mehmat/odfka/r3/R3-1.htm) 3. Практически нет гарантий, что полученная формула, если она достаточно сложна, является минимальной, что её нельзя сократить ещё. Я в своё время принимал участие в разработке автоматических устройств (в теории - конечные автоматы) для ракетной техники, и могу сказать, что большинство проектировщиков составляли схемы устройств, руководствуясь не столько теорией, сколько здравым смыслом. Я думаю, это происходило потому, что теория достаточно сложна и недостаточно проработана для практического применения. Идеи, которые я хочу здесь представить, зародились именно в те времена. Суть метода Коротко, суть предлагаемого метода заключается в следующем. На основании таблицы истинности, которая, как правило, является основой проектирования логической схемы, для искомой функции составляется множество из нулей и единиц. Множество разбивается на определённое число пар взаимнонепересекающихся подмножеств. Число пар равно числу входных переменных, и каждой паре сответствует пара букв, одна из которых обозначает переменную, а вторая её отрицание. Задача сводится к тому, чтобы на этом множестве сформировать множество, которое включает только единицы. Формула этого множества как раз и будет искомой функцией. Формирование множества осуществляется посредством пошаговой процедуры, на каждом шаге которой в формулу множества добавляется одна буква таким образом, чтобы полученное множество имело наибольшее совпадение с искомым множеством, т.е. имело бы как можно больше единиц и как можно меньше нулей. Величина совпадения определяется как sov(i) = s1(i)/s1 - s0(i)/s0 , где s1 и s0 - число единиц и нулей в исходном множестве, а s1(i) и s0(i) - соответственно число единиц и нулей в множестве, полученном на i - том шаге. Так как на каждом шаге в формулу добавляется только одна буква, то на каждом i - том шаге мы будем получать формулу из минимального числа i букв, определяющей множество с максимальным совпадением. Процедура будет закончена, когда будет получено множество с совпадением sov(i) =1. Формула будет иметь i букв. Результаты Предлагаемый метод был применён при определения системы функций для реализаций логической сети "Мышь в лабиринте" , синтез которых приведен в книге "Н.Е. Кобринский и Б.А. Трахтенброт Введение в теорию конечных автоматов. 1962 г." Всего надо найти 5 функций z1, z2, f1(t+1), f2(t+1), f3(t+1) от 5 переменных x1, x2, f1(t), f2(t), f3(t) , каждая из которых задаётся таблицей истинности. Таблица истинности для всех пяти функций приведена на Рис. 1. Таблица взята из упомянутой книги с некоторыми корректировками для удобства записи. Таблица истинности для системы функций "Мышь в лабиринте" №стр. код входа входн. состояния код вых. выходное состояние --------------- ------------------------- ------------ ---------------------------- № кол 1 2 3 4 5 6 7 8 9 10 x1 x2 f1(t) f2(t) f3(t) z1 z2 f1(t+1) f2(t+1) f3(t+1) 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 2 0 0 0 1 0 1 0 0 0 0 3 0 0 0 1 1 1 0 0 0 0 4 0 0 1 0 0 1 0 0 0 0 5 0 0 1 0 1 1 0 0 0 0 6 0 0 1 1 0 1 0 0 0 0 7 0 0 1 1 1 ( 1) (0) (0) (0) (0) 8 0 1 0 0 0 0 1 1 1 0 9 0 1 0 0 1 0 0 1 1 0 10 0 1 0 1 0 0 0 1 1 0 11 0 1 0 1 1 0 0 1 0 1 12 0 1 1 0 0 1 0 0 1 1 13 0 1 1 0 1 (1) (0) (0) (1) (1) 14 0 1 1 1 0 1 0 0 1 1 15 0 1 1 1 1 (1) (0) (0) (1) (1) 16 1 0 0 0 0 0 0 0 0 1 17 1 0 0 0 1 0 0 1 1 0 18 1 0 0 1 0 0 1 1 1 0 19 1 0 0 1 1 0 0 1 0 0 20 1 0 1 0 0 1 1 1 1 1 21 1 0 1 0 1 0 1 1 1 0 22 1 0 1 1 0 (1) (1) (1) (1) (1) 23 1 0 1 1 1 1 1 1 1 1 24 1 1 0 0 0 1 1 1 1 1 25 1 1 0 0 1 (1) (1) ( 1) (1) (1) 26 1 1 0 1 0 (1) (1) ( 1) (1) (1) 27 1 1 0 1 1 (1) (1) ( 1) (1) (1) 28 1 1 1 0 0 (1) (1) ( 1) (1) (1) 29 1 1 1 0 1 (1) (1) ( 1) (1) (1) 30 1 1 1 1 0 (1) (1) ( 1) (1) (1) 31 1 1 1 1 1 1 1 1 1 1
Рис. 1
Для этой таблицы истинности в книге методом графов была найдена следующая система уравнений для пяти функций, реализующих автомат "Мышь в лабиринте" . Система уравнений 1 z1 = -x1{-x2[f2(t) + f3(t)] + f1(t)} + x1{f1(t)[f2(t) +-f3(t)] + x2} (1) 10 z2 = x2[-f1(t)-f2(t)-f3(t) + x1] + x1[f2(t)-f3(t) +f1(t)] (2) 9 f1(t+1) = x2[x1 + -f1(t)] + x1[f1(t) + f2(t) +3(t)] (3) 7 f2(t+1) = -x1{x2[f1(t) + -f2(t) + -f3(t)] + -f1(t)-f2(t)-f3(t)} + x1[x2 + f1(t)+ -f2(t)f3(t) + f2(t)-f3(t)] (4) 15 f3(t+1) = -x1{x2[f2(t)f3(t) + f1(t)]} + x1{-f2(t)-f3(t) +f1(t)[f2(t)+f3(t)] +x2} (5) 12 Цифры, приведенные в конце каждой строки с формулами (1) - (5) показывают число букв (входных переменных) в каждой формуле С помощью предлагаемого метода была получена Система уравнений 2 z1 = f1(t)[-f3(t)+f2(t)] + -x1-x2[f2(t)+f3(t)] +x2x1 (6) 9 z2 = x1{f1(t)+ -f3(t)[x2+f2(t)]} +x2-f2(t)-f1(t)-f3(t) (7) 9 f1(t+1) = x1[f1(t)+f3(t)+f2(t)] +x2-f1(t) (8) 6 f2(t+1) = [x2+x1]{f1(t) + [-f2(t)+ -f3(t)][x2+f3(t)+f2(t)]} +-f2(t)-f1(t)-x1-f3(t) (9) 12 f3(t+1) = x2[f1(t)+f2(t)f3(t)] +x1[-f3(t)-f2(t)+f1(t)f2(t)] (10) 9 В этой системе уравнений (6) - (10), как и в системе уравнений 1 (1) - (5), цифры в конце строк показывают число букв в каждой формуле. В четырёх формулах из пяти предлагаемый метод позволил сократить число букв. Общее число букв сократилось с 53 до 45. Добавление 14.10.2011 На основе изложенных выше идей были разработаны методика, включающая программу, которая позволяет по данным таблицы истинности найти булеву функцию с минимальным числом букв в ней. http://moiidei.com/nauka-estestvennyie/prakticheskaya-minimizatsiya-bulevyih-funktsiy.html Эта методика была применена к Таблице истинности для задачи "Мышь в лабиринте". Результаты показаны ниже. Для простоты записи булевых формул введём следующие обозначения. x1 = u; -x1 = h; x2 = v; -x2 = i; f1(t) = w; -f1(t) = j; f2(t) = y; -f2(t) = l; f3(t) = z; -f3(t) = m. Ниже приведены полученные с помощью указанной методики формулы. z1 = ih(y+z) + w(m+y) +vu (11) 9 z2 = (ym+w)u + lvjm (12) 8 f1(t+1) = (z+w+y)u + vj (13) 6 f2(t+1) = (l+m)((y+z)u+v) +uw + ljhm (14) 12 f3(t+1) = (y+m)((l+w)u+v(w+z)) (15) 8 Как видим, с помощью этой методики формулы для z2 (формула 12) и для f3(t+1) (формула 15) удалось сократитить ещё на одну букву каждую. |
Комментарии
RSS лента комментариев этой записи