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.
        

Ну ещё можно было и диаграммы Вейча упомянуть для функций до четырёх аргументов. А что нового? Нашёл список литературы, там книги датированы 1987 годом. Думаю ещё и более ранние есть.
Вот ещё источник оформлено неплохо. http://ptca.narod.ru/lec/lec1.html

Новое заключается в том, что предлагается совершенно новый метод. Минимизация по "совпадению множеств", этого ни в какой литературе Вы не найдёте, и этот метод действительно минимизирует функцию. что и показано в этой небольшой заметке. Если Вы действительно интересуетесь этим вопросом, обратитесь к более подробному описанию
http://obdamaskin.livejournal.com/4035.html  
или                           
http://moiidei.com/nauka-estestvennyie/min...-mnozhestv.html
  

Есть сайт - http://logicsimplificator.narod2.ru/ - с программой и услугами по пятимерной минимизации булевых функций.

Существенное отличие предлагаемого мною подхода к минимизации булевых функции заключается в том, что он осуществляет минимизацию числа букв в практически применимой булевой формуле, т.е. в формуле, по которой может быть построена логическая схема с минимальным числом элементов, в то время как все ранее разработанные методы молчаливо предполагают минимизацию дизъюнктивной (или конъюктивной) нормальной формы (ДНФ или КНФ) булевой функции, которую ещё надо будет сокращать практически чисто интуитивно.
Не является исключением и программа на сайте 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