|
Модераторы: Alx, Fixin |
|
Дамаскин |
|
|||
Новичок Профиль Группа: Участник Сообщений: 8 Регистрация: 17.11.2008 Репутация: нет Всего: нет |
http://obdamaskin.livejournal.com/4035.html
http://moiidei.com/nauka-estestvennyie/min...-mnozhestv.html Минимизация булевых функций по совпадению множеств В "Представление информации булевой формулой" ( http://moiidei.com/nauka-estestvennyie/pre...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 = 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) + f3(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-f1-x1-f3 (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. |
|||
|
||||
destrd |
|
|||
Бывалый Профиль Группа: Участник Сообщений: 157 Регистрация: 1.10.2008 Репутация: нет Всего: 4 |
Ну ещё можно было и диаграммы Вейча упомянуть для функций до четырёх аргументов. А что нового? Нашёл список литературы, там книги датированы 1987 годом. Думаю ещё и более ранние есть.
Вот ещё источник оформлено неплохо. http://ptca.narod.ru/lec/lec1.html --------------------
Some people, when confronted with a problem, think, "I known, I'll use regular expressions." Now they have two problems. -- Jamie Zawinski in comp.lang.emacs |
|||
|
||||
Дамаскин |
|
|||
Новичок Профиль Группа: Участник Сообщений: 8 Регистрация: 17.11.2008 Репутация: нет Всего: нет |
Новое заключается в том, что предлагается совершенно новый метод. Минимизация по "совпадению множеств", этого ни в какой литературе Вы не найдёте, и этот метод действительно минимизирует функцию. что и показано в этой небольшой заметке. Если Вы действительно интересуетесь этим вопросом, обратитесь к более подробному описанию
http://obdamaskin.livejournal.com/4035.html или http://moiidei.com/nauka-estestvennyie/min...-mnozhestv.html |
|||
|
||||
dontcaredontknow |
|
|||
Новичок Профиль Группа: Участник Сообщений: 1 Регистрация: 9.10.2011 Репутация: нет Всего: нет |
Есть сайт - http://logicsimplificator.narod2.ru/ - с программой и услугами по пятимерной минимизации булевых функций.
|
|||
|
||||
Дамаскин |
|
|||
Новичок Профиль Группа: Участник Сообщений: 8 Регистрация: 17.11.2008 Репутация: нет Всего: нет |
Существенное отличие предлагаемого мною подхода к минимизации булевых функции заключается в том, что он осуществляет минимизацию числа букв в практически применимой булевой формуле, т.е. в формуле, по которой может быть построена логическая схема с минимальным числом элементов, в то время как все ранее разработанные методы молчаливо предполагают минимизацию дизъюнктивной (или конъюктивной) нормальной формы (ДНФ или КНФ) булевой функции, которую ещё надо будет сокращать практически чисто интуитивно.
Не является исключением и программа на сайте http://logicsimplificator.narod2.ru/. Она тоже минимизирует ДНФ. В приводимом на сайте примере получена ДНФ f(a,b,c,d,e)=(ac¬d) or (¬a¬de) or (¬b¬de) or (abce) or (abde) or (bcde) or (¬a¬bd¬e) or (¬a¬cd¬e) or (¬a¬b¬cd) "¬" операция not. из 33 бвукв. Эту формулу ещё можно и нужно сократить. Как? А вот формула, полученная по моему методу f(a,b,c,d,e)=(e(-d or b) or -ad-c or c-da)(c or -d(-b or -a) or -e or -b) or (eba or -a-e-b)d "-" операция not. из 22 букв. На основе указанного у данной теме подхода мною разработана медодика, включающая и программу, по которой можно найти действительно минимальную формулу пока, по крайней мере, и для 6-мерных булевых функций. http://moiidei.com/nauka-estestvennyie/pra...h-funktsiy.html |
|||
|
||||
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | Интересные и занимательные задачи по программированию | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |