Внимание!
Предложения и заявки заказчиков

Размещение рекламных материалов

коммерческая реализация изобретений - ООО 'Адвансед Девелопмент Проджект' смотреть>>>

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

Требуются разработки по использованию низкопотенциальной энергии смотреть >>>

Практическая минимизация булевых функций.

                          Практическая минимизация булевых функций.

                           
       
                           Представление информации булевой формулой.



                                 
                                     Определения.

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

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

Пример формулы:
((ym+i)(j+zy)+u)(ml+h+vw)+lvwz 

В этой формуле 16 букв.

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

                                                 Пример
           таблицы истинности для 6 пар переменных.
Переменные попарно: 
{h,u}; {i,v}; {j,w}; {k,x}; {l,y}; {m,z}. 
                                      
                                                Таблица истинности

   1                                    2                                                            3

номер        значения переменных          значение  функции F  для примеров
строки        h  u  i   v   j  w  k  x   l   y  m  z     F(1)  F(2)  F(3)     F(4)    F(5)  F(6)

    0            1  0  1  0  1  0  1  0  1  0  1   0        1       1       1        1         1
    1            1  0  1  0  1  0  1  0  1  0  0   1        1       1       1        0         0
    2            1  0  1  0  1  0  1  0  0  1  1   0        1       1       1        0         0
    3            1  0  1  0  1  0  1  0  0  1  0   1        1       1       1        0         0
   4             1  0  1  0  1  0  0  1  1  0  1   0                           1                   0 
   5             1  0  1  0  1  0  0  1  1  0  0   1                           1                   0
   6             1  0  1  0  1  0  0  1  0  1  1   0                           1                   0
    7            1  0  1  0  1  0  0  1  0  1  0   1                           1                   1
   8             1  0  1  0  0  1  1  0  1  0  1   0        0       0        0        0        1
   9             1  0  1  0  0  1  1  0  1  0  0   1        0       0        0        0        0
  10            1  0  1  0  0  1  1  0  0  1  1   0        0       0        0        0        0
  11            1  0  1  0  0  1  1  0  0  1  0   1        1       1        1                  0
  12            1  0  1  0  0  1  0  1  1  0  1   0                            0                  1
  13            1  0  1  0  0  1  0  1  1  0  0   1                            0                  0
  14            1  0  1  0  0  1  0  1  0  1  1   0                            0                  0
  15            1  0  1  0  0  1  0  1  0  1  0   1                            1                  1
  16            1  0  0  1  1  0  1  0  1  0  1   0        0       0        0         1       1
  17            1  0  0  1  1  0  1  0  1  0  0   1        0       0        0         1       0
  18            1  0  0  1  1  0  1  0  0  1  1   0        1       1        1         1       0
  19            1  0  0  1  1  0  1  0  0  1  0   1        0       0        0         0       1
  20            1  0  0  1  1  0  0  1  1  0  1   0                            0                  0
  21            1  0  0  1  1  0  0  1  1  0  0   1                            0                  1
  22            1  0  0  1  1  0  0  1  0  1  1   0                            1                  0
  23            1  0  0  1  1  0  0  1  0  1  0   1                            0                  1
  24            1  0  0  1  0  1  1  0  1  0  1   0        0       0        0          1      1
  25            1  0  0  1  0  1  1  0  1  0  0   1        1       1        1                  1
  26            1  0  0  1  0  1  1  0  0  1  1   0        0       0        0          1      1  
  27            1  0  0  1  0  1  1  0  0  1  0   1        0       0        0                  0
  28            1  0  0  1  0  1  0  1  1  0  1   0                            0                  0          
  29            1  0  0  1  0  1  0  1  1  0  0   1                            1                  0
  30            1  0  0  1  0  1  0  1  0  1  1   0                            0                  1
  31            1  0  0  1  0  1  0  1  0  1  0   1                            0                  1
  32            0  1  1  0  1  0  1  0  1  0  1   0        1       0        1           0
  33            0  1  1  0  1  0  1  0  1  0  0   1        0       0        0           1
  34            0  1  1  0  1  0  1  0  0  1  1   0        0       1        0           1
  35            0  1  1  0  1  0  1  0  0  1  0   1        0       0        0           0
  36            0  1  1  0  1  0  0  1  1  0  1   0                            0
  37            0  1  1  0  1  0  0  1  1  0  0   1                            0
  38            0  1  1  0  1  0  0  1  0  1  1   0                            1
  39            0  1  1  0  1  0  0  1  0  1  0   1                            0
  40            0  1  1  0  0  1  1  0  1  0  1   0        1        0        1          1
  41            0  1  1  0  0  1  1  0  1  0  0   1        0        0        0          1
  42            0  1  1  0  0  1  1  0  0  1  1   0        0        0        0
  43            0  1  1  0  0  1  1  0  0  1  0   1        0        1        0          1
  44            0  1  1  0  0  1  0  1  1  0  1   0                             0
  45            0  1  1  0  0  1  0  1  1  0  0   1                             0
  46            0  1  1  0  0  1  0  1  0  1  1   0                             0
  47            0  1  1  0  0  1  0  1  0  1  0   1                             1
  48            0  1  0  1  1  0  1  0  1  0  1   0         1       0        1           1
  49            0  1  0  1  1  0  1  0  1  0  0   1         0       0        0
  50            0  1  0  1  1  0  1  0  0  1  1   0         0       0        0
  51            0  1  0  1  1  0  1  0  0  1  0   1         0       1        0
  52            0  1  0  1  1  0  0  1  1  0  1   0                            0     
  53            0  1  0  1  1  0  0  1  1  0  0   1                            0
  54            0  1  0  1  1  0  0  1  0  1  1   0                            0
  55            0  1  0  1  1  0  0  1  0  1  0   1                            1
  56            0  1  0  1  0  1  1  0  1  0  1   0         1       1        1
  57            0  1  0  1  0  1  1  0  1  0  0   1         1       1        1
  58            0  1  0  1  0  1  1  0  0  1  1   0         1       1        1
  59            0  1  0  1  0  1  1  0  0  1  0   1         1       1        1            1
  60            0  1  0  1  0  1  0  1  1  0  1   0                             1
  61            0  1  0  1  0  1  0  1  1  0  0   1                             1
  62            0  1  0  1  0  1  0  1  0  1  1   0                             1
  63            0  1  0  1  0  1  0  1  0  1  0   1                             1



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



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

Исходной информацией для программы являются данные графы 3 таблицы истинности, т.е. последовательность из 64 знаков 0, 1 или отсутствия любого
из этих знаков. Для удобства записи вместо пустого места в
последовательности будем писать букву "a", чтобы видны были границы
последовательности.

Например, для построения формулы булевой функции F(1) для 5 пар
переменных (исключена пара k,x)  из графы 3 таблицы истинности нужно
ввести в программу последовательность
 
1111aaaa0001aaaa0010aaaa0100aaaa1000aaaa1000aaaa1000aaaa1111aaaa
   (1)

Через некоторое время получим формулу для данной последовательности, т.е.
            
      F(1) =   ((ym+i)(j+zy)+u)(ml+h+vw)+lvwz       (16 букв в формуле)

Для F(2) (для тех же переменных)  таблица истинности даёт несколько иную
последовательность                     
                    1111aaaa0001aaaa0010aaaa0100aaaa0010aaaa0001aaaa0001aaaa1111aaaa
   (2)   

и, соответственно, будет  другая формулу для F(2)
                       
F(2) =   (v(lz+u)w+(i+(m+u)y)(hj+y(z+ji)))(h+v+m+w)   (19)

Функция F(3) определяется всеми 6-ю парами переменных.
Последовательность её значений из таблицы истинности не содержит пустых
мест и выглядит так
 
1111111100010001001000100100010010000010100000011000000111111111
   (3)

Формула для F(3), определённая с помощью программы,
                       
F(3) =  (u+lz)vw+(j+zy+u)(klm+h)(i+ym+u)+yxu((v+w)z+ijm)   (26)

Наконец, обратим внимание на ещё один пример  функции F(4) всё тех же
5 пар переменных, отличающийся тем, что там в соответствующей графе
таблицы истинности отсутствуют значения функции не только в связи с
отсутствием пары переменных x и k, но и просто потому, что значения этой
функции по тем или иным причинам не определены. Например, разработчику логической схемы абсолютно безразлично какое значение будет у булевой
функции при данном сочетании значений  переменных. В этом случае
программа сама как бы выбирает такое значение функции для пустого места, которое гарантирует минимальность формулы. В этом заключается
существенное различие между примерами для F(1), F(2) и функцией F(4).

Последовательность для F(4) будет выглядеть так
                         1000aaaa000aaaaa1110aaaa1a1aaaaa0110aaaa11a1aaaa1aaaaaaaaaa1aaaa
(4)

а сама формула, как
                            
F(4) =   (l+m)((j+z)u+v)+uw +ljhm    (12)

Если в последовательности (1) все буквы а   заменить на 0, то
последовательность будет выглядеть следующим образом  
                      
1111000000010000001000000100000010000000100000001000000011110000
  (1.1)

и соответствующая формула

      F(1.1) =   k(((ym+i)(j+zy)+u)(ml+h+vw)+lvwz )    (17)

Практически формула осталась та же, но появилась ещё одна буква k за счёт фактического перехода от 5 пар переменных к 6 парам.

Замена же всех букв a на 0 в последовательности (4) приведёт к другой
формуле F(4.1) с определённо бОльшим числом букв в ней.
                        
100000000000000111000001010000001100000110100001000000000010000
(4.1)

           F(4.1) = k((m(hv+jl)+(zwy+i(l+jm))u)(v+w+h+y+z)+ljhv)  (23)

Пример функции F(5)  в таблице истинности тоже для 5 пар переменных, но отсутствует пара {h,u}. В этом случае последовательность значений функции выглядит так 
                       
10000001100010011001010111100011aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
  (5)

Для последовательности (5) программа  даёт результат
                            
F(5)  = (l(iw+k)m+(y+(j+k)v)(xz+v(w+zy)))(x+l+j+m)   (19)



                                 Небольшое заключение.

Таким образом, если надо получить формулу для некоторой булевой функции,
то  просто присылайте последовательность значений функции из таблицы истинности. Можно прислать и просто формулу для данной функции,
полученную каким то другим способом.  Программа может и в этом случае построить свой вариант формулы.
 
     Этот адрес электронной почты защищен от спам-ботов. У вас должен быть включен JavaScript для просмотра.

Добавить комментарий


Защитный код
Обновить

Комментарии