Приветствую!

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

Ваш покойный слуга .

Ить Карты Карно - это для человека метод, графически-визуальный, чтобы удобнее было. Машинный метод - это построить дерево и применять к нему упрощающие подстановки рекурсивно, пока применяются.

Я все понимаю. Сам алгоритм составить могу, но времени нет. Вот я и спрашиваю Где достать а не Как сделать.

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

ага, вот еще... там про импликанты и про кубы разные упоминается

Ой, давай, давай...
Кубы? Это если количество булевых переменных больше 4-х....

http://www.etel.dn.ua/~shurik/carno

Если сайт не будет активным, то могу выслать прогу на мыло

neutrino выслал

Как обычно, открываем Апорт. Делаем запрос "минимизация булевой функции методом карт Карно".

http://kai4x03.narod.ru/files/files.html

Правда, ссылка, которая на страничке, у меня не работает. Но можно связаться с автором...

Помню когда-то давным давно (3 года назад) писал диплом. Одним из его пунктов было "создание алгоритма минимизации булевых функций". Метод был изобретён свой, адаптированный под вычислительные машины. Критерий минимизации - минимум операций. Базис: дизъюнкция, конъюнкция, отрицание и сложение по модулю два. Число булевых переменных и сложность функций - любая. Язык программирования quick basic.

Есть исходники. Но хотелось бы переписать прогу на что-нибудь современное (C#, C++, php или delphi).
У самого времени нет этим заниматься. Если кому интересно, могу выслать код (ICQ: 459-783-892).

Привет! Помогите плиз)) Я тоже с этим столкнулся) только я не сс картами карно , а с Квайном)) Помжет кто нить чемто помочь? Интересует алгоритм (поиск покрытий)

конъюнкция - *
дизъюнкция - +
отрицание - !
сложение по модулю два - (+)

В итоге: 

x1 (+) x2 = ((!x1) * x2) + (x1 * (!x2))

Скобки расставил для того чтобы не задавать приоритеты.

Но вот беда, никак не пойму, где здесь базис. Если одна функция может быть получена через комбинацию(линейную) других, то базисом никаким и не пахнет. Мммм.... Или я может быть путаюсь в понятиях?

Это сообщение отредактировал(а) Dude03 - 21.1.2008, 13:10

Надо исключить лишние операторы (дизьюнкцию и отрицание или сложение) и получишь одно из представлений: полином Жигалкина или совершенную дизъюнктивную нормальную форму (ДНф) - вот там базисы и ищи.


Это сообщение отредактировал(а) AndreyK - 29.1.2008, 17:09

Наверно, не  совсем то, что Вам нужно, но может пригодиться.

 Минимизация булевых функций по совпадению множеств

В  "Представление информации булевой формулой" ( 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.
        
Подробнее:
 http://obdamaskin.livejournal.com/4035.html  
или                           
http://moiidei.com/nauka-estestvennyie/min...-mnozhestv.html
  

<Spawn>, если не трудно и не стёр ешё програмку, может и мне пришлёш?