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

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

livejournal - http://obdamaskin.livejournal.com/4375.html

  Этот адрес электронной почты защищен от спам-ботов. У вас должен быть включен JavaScript для просмотра.

                                    Два определения информации

          Изначально в теории информации понятие информации связывали и связывают с понятием вероятности (А.М. Яглом и И.М. Яглом. Вероятность и информация. 1960г.)  Количество информации определялось как мера изменения неопределённости (энтропии) некоторого события. Грубо говоря, если вероятность некоторого события равна 1, то сообщение об этом событии несёт 0 информации, соответственно количество информации может быть в пределах от 0 до 1. Можно сказать, что это понятие информации связано со смыслом сообщения. Количество информации в сообщении, не имеющем смысла, равно 0.

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

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

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

          Сообщение, собственно, и превращается в информацию в результате его осмысления.

                  

                              Язык как средство представления информации

          При взаимодействии с окружающей средой и общении  друг с другом люди получают и передают информацию.

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

·                                                          Два типа методов представления информации

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

·                                                          Первичное представление информации

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

·                                                       Язык - средство представления абстрагированной информации.

          Методы второго типа не отображают объекты как таковые, а служат средством передачи абстрактного представления об объектах после переработки человеком данных, полученных от окружающей среды. Эти представления выражаются словами языка. Правила языка позволяют использовать слова, чтобы формировать предложения и тексты, которые более или менее детально описывают реальные объекты и явления. Язык, среди прочего, способствует снижению количества информации, уменьшает нагрузку на перерабатывающие механизмы и препятствует передаче ненужных данных. Например, можно передать информацию о некоем доме путём отсылки фотографии или письменного описания. Картинка содержит много больше информации, чем описание, если измерять её в битах, но часто для принятия решения требуются только определённые данные, которые могут быть выражены словами. Язык позволяет позволяет существенно сжать информацию за счёт отбрасывания ненужных деталей.

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

·                                     Двоичное представление информации.

Сейчас в технических устройствах, в частности в компьютерах, наиболее широко распространено   двоичное представление информации посредством последовательности единиц и нулей.

Двоичное представление не является языком. Фактически это либо точечное отображение реальных объектов (фотография, телевидение, изображение на экране монитора), либо кодирование.

 

                                               Язык булевых формул

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

Зададим алфавит алфавит из букв (он может быть достаточно велик)

                                             a, b, c... ,

которые фактически являются словами языка, и введём вспомогательные символы

                                                        || , & , - , ( , ) ,

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

                                                          a, b, c... ,

являются формулами, т.е. предложениями языка.

Сочетания

                                               ( a&b)|| (-c&d)  или     ( a||b)&(-c||d) 

также являются предложениями языка. Символ &  часто опускаются, и вышеприведенные предложения могут выглядеть как

                                                ( ab)|| (-cd)  или     ( a||b)(-c||d)

Необходимо отметить, что символ "=" в выражении

                                                   ab||ad = a(b||d)

не является символом языка булевых формул, поэтому вышеприведенное выражение не является предложением языка, а только показывает, что эти два предложения эквивалентны.

0  и   1 также являются буквами языка, обладающие особыми свойствами:

                                              a0 = 0 , a1 = a , a||0 = 0 , a||1 = 1

                       

 Есть и другие правила. Применяя эти правила можно объединять отдельные предложения в более сложные, уменьшая число букв в предложениях без изменения смысла предложения или создавая предложения с новым смыслом, как в обычном языке.

 

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

   Одной из интерпретаций булевой алгебры является теория множеств. Именно эта интерпретация позволяет применить язык булевых формул в качестве языка представления информации. Это означает, что применить предлагаемый метод представления информации булевой формулой можно только к информации, которая предварительно представлена множеством объектов.

На первом этапе таким множеством является множестово нулей и единиц.

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

                                                                          

                                                           ___________________________________ 

                                                          I  0   I   1  I   2   I  3   I  4   I   5  I   6   I   7  I 

                                                          I____I____I____I____I____I____I____I____I
       I  8   I   9  I  10  I 11  I  12  I 13  I  14  I  15 I

                                                          I____I____I____I____I____I____I____I____I
       I  16  I  17 I  18  I  19 I  20  I  21 I  22  I  23 I

       I____I____I____I____I____I____I____I____I
       I  24  I  25 I  26  I  27 I  28  I  29 I  30  I  31 I
       I____I____I____I____I____I____I____I____I
       I  32  I  33 I  34  I  35 I  36  I  37 I  38  I  39 I
       I____I____I____I____I____I____I____I____I
       I  40  I  41 I  42  I  43 I  44  I  45 I  46  I  47 I
       I____I____I____I____I____I____I____I____I

     I  48  I  49  I  50 I  51  I  52 I  53  I  54 I  55 I

     I____I____I____I____I____I____I____I____I

     I  56  I  57  I  58 I  59  I  60 I  61 I  62 I  63  I

                                                         I____I____I____I____I____I____I____I____I


                   

                                                                          Рис.1. Pole

      На Рис. 1 представлен пример такого поля из 64 клеток.

                                                                  

·                                                                                                                   Информация

          Поле, представленное на Рис.1 не несёт никакой информации. Это просто "сетчатка", инструмент для получения информации. Информация возникает тогда, когда это поле превращается в множество единиц и нулей. Последовательность

                     11000000010000000010000000010000000010000000010000000010000000010000000

                                        Рис. 2.   Информация Inf[1]

     уже является информацией Inf[1].

     Или та же последовательность, но на поле другой конфигурации

                                                                 11000000       

 01000000

 01000000

 01000000

 01000000

 01000000

 01000000

 01000000

Рис.3.    Информация Inf[1]

  

          Информация (или сообщение) представляется всем множеством единиц и нулей. Количество информации определяется размерами поля. В данном конкретном примере оно равно 64 битам.

 С другой стороны, при строго определённом конечном размере поля для представления информации достаточно задать только расположение  единиц (или, наоборот) нулей, т.е. определить множество единиц (или множество нулей).

Конечное информационное поле Pole разбивается на не менее чем

                                               Alf = log(основание 2)M                                        (1)

 пар взаимонепересекающихся множеств. В формуле (1) M  обозначает мощность множества ( число клеток) Pole.  В нашем случае  M = 64 и Al f =  6 пар, соответственно. Пары множеств по конфигурации могут быть самые разные. Во многом это зависит от конкретной задачи и статистических свойств информационных сообщений. В данном примере применено следующее разбиение. Первые три пары сформированы из строк Pole:

                                  x1, -x1;      x2, -x2;      x3,  -x3;

Множество x1 - четыре верхних строки Pole (клетки 0 -- 31),

                 -x1 - четыре нижних  строки Pole (клетки 32 -- 63),

                  x2 - две верхних строки множества x1 (0--15) и две верхних строки  множества -x1 (32--47),

                 -x2 - две нижних строки множества x1 (16--31) и две нижних строки  множества -x1 (48--63),

                  x3 - все нечётные строки Pole (клетки 0--7, 16--23, 32--39, 48--55),

                 -x3 - все чётные строки Pole (клетки 8--15, 24--31, 40--47, 56--63).

Ещё три пары множеств сформированы из столбцов поля аналогичным образом:

                                   y1, -y1;      y2, -y2;       y3, -y3;

 y1 - четыре левых столбца (клетки 0,8,16,24,32,40,48,56,  1,9,17,25,33,41,49,57,  2,10,18,26,34,42,50,58,       3,11,19,27,35,43,51,59)

-y1 -четыре правых столбца (4,12,20,28,36,44,52,60,  5,13,21,29,37,45,53,61,  6,14,22,30,38,46,54,62,    7,15,23,31,39,47,55,63)

 y2 - два левых столбца множества  y1 (0,8,16,24,32,40,48,56,  1,9,17,25,33,41,49,57)  и  два левых столбца множества  -y1 (4,12,20,28,36,44,52,60,  5,13,21,29,37,45,53,61) 

-y2 - два правых столбца множества  y1 (2,10,18,26,34,42,50,58,   3,11,19,27,35,43,51,59) и два правых столбца множества  -y1 ( 6,14,22,30,38,46,54,62,    7,15,23,31,39,47,55,63)

 y3 - нечётные столбцы поля ( 0,8,16,24,32,40,48,56,  2,10,18,26,34,42,50,58,  4,12,20,28,36,44,52,60,   6,14,22,30,38,46,54,62)   

-y3 - чётные столбцы поля ( 1,9,17,25,33,41,49,57,  3,11,19,27,35,43,51,59,  5,13,21,29,37,45,53,61,  7,15,23,31,39,47,55,63)

 

                                              Алфавит         

 В принципе в качестве алфавита можно применить те же обозначения, которые применены для  множеств. Однако. по соображениям удобства записи применим в качестве алфавита только буквы (без прибавления цифр и знака "-") в соответствии с табл. 1.

                                               Табл 1

                                        Буква            Множество

m                    y3

z                    -y3

l                      y2

y                    -y2

k                     y1

x                    -y1

j                      x3

w                    -x3

i                      x2

v                     -x2

h                      x1

u                     -x1

Кроме букв введём в алфавит знаки " ( ", " ) " и знак " + " вместо знака " || ", который применяется к множествам.

 

                                         Идея метода

 

Выше уже говорилось о том, что при заданном поле  Pole для передачи и обработки информации достаточно задать не всё поле Inf[i] (например, Inf[0] ), а только множество единиц (или нулей).  На этом свойстве конечного множества и основана идея метода. С помощью методов булевой алгебры применительно к однородным конечным множествам мы выделяем множество, содержащее только единицы. Положение этого множества на поле Pole определяет соответствующая ему булева формула, записанная буквами алфавита.

                                   

                                          Процедура

Предлагается пошаговая процедура определения множества единиц. Сначала находится некоторое исходное множество из Табл.1  ar[0], наиболее близкое к искомому, затем находится множество ar[1] путём объединения или пересечения исходных  множеств из Табл.1, третьим шагом находится множество ar[2] как комбинация трёх исходных множеств и т.д. Но что понимать под близостью некоторого множества ar[i]  искомому множеству, которое обозначим как ark?  В качестве критерия близости множеств введём понятие совпадения  множеств.             

 

                                           Совпадение множеств 

Пусть s1[i] - число единиц в некотором множестве Inf[i], а s0[i] - число нулей в том же множестве. Соответственно обозначим как s1ar[i] число единиц в произвольном ar[i]  множестве Inf[i], а число нулей в ar[i] на том же множестве обозначим как s0ar[i]. Тогда  совпадение sov[i]  множества ar[i] относительно искомого множества ark будет определяться выраженим:

                                             sov[i] = s1ar[i] / s1[i] - s0ar[i]  / s0[i],                     (2)

т.е. величина sov определяется как разность относительных чисел единиц и нулей в множестве ar[i] к исходному полю Inf[i].

Если множество  содержит все единицы и ни одного нуля, то совпадение, как нетрудно заметить, равно 1.

И, наоборот, если множество не содержит ни одной единицы, а содержит все нули, то совпадение равно -1, т.е. значения sov находятся в пределах от -1 до 1.

Заметим, что этим понятием можно пользоваться для определения совпадения не только между произвольным множеством и исходным полем Inf[i], но и между любыми двумя множествами на поле Inf[i].

 

 

 

                                                                         Суть метода

 

       Конечное информационное поле Pole разбивается на не менее чем  m = log(основание 2)n пар взаимонепересекающихся множеств. Вводится алфавит из m пар букв, соответствующий этоту разбиению.

Этот алфавит может быть расширен введением новых букв, соответствующих произвольным множествам

на Pole. Вводятся также символы пересечения и объединения  множеств, скобки. Основываясь на этом алфавите, формируется булевая формула, представляющая конкретную информацию Inf[i] на поле Pole, путём многошаговой процедуры следующим образом.

     На первом шаге выбирается формула (буква), соответствующая одному множеству. На втором шаге находится формула, соответствующая пересечению или объединению двух множеств, на третьем - трёх и т.д.

     Критерием для выбора формулы является совпадение множеств, значение которого отражает близость двух множеств, и которая определяется как разность отношения числа единиц и нулей в формируемом иножестве и в множестве Inf[i].

                                              

                                                                       Что   это   даёт

            Вот некоторые соображения.

·Язык второго уровня. Прежде всего это показывает, что помимо привычного двоичного кода, информация может быть представлена более сложным языком, я бы назвал его языком второго уровня, а именно языком булевых формул. 

·Искусственный интеллект. Этот метод основан на множественной интерпретации булевой алгебры. Как известно, ещё одной интерпретацией булевой алгебры является алгебра логики. Есть высокая вероятность того, что мыслительные процессы проистекают именно в соответствии с законами логики. Конечно, можно смоделировать логические операции на основе числовых процессоров, как это и стало делаться с появлением компьютеров, но логичней и естественней, на мой взгляд, осуществлять такие операции с помощью логических устройств, созданных с помощью алгебры логики и обрабатывающих информацию, представленную булевыми формулами.

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

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

·Структурная избыточность информации.  Сжатие информации. Указанная выше возможность позволяет  передавать не всю информацию за счёт смысловой избыточности. Но есть ещё и структурная избыточность информации, под которой можно понимать число информационных элементов (единиц) и  определённые связи между отдельными элементами информационного сообщения, т.е. закономерности их распределения на информационном поле при данном разбиении поля на подмножества. Фактически это сводится к длине формулы для данной информации. От числа и взаимного расположения единиц на поле Inf[i], а также от разбиения исходного Pole,  зависит длина формулы для этого сообщения.

· Единая формула в памяти. В принципе, вся информация по мере поступления может сжиматься, если каждую формулу добавлять в память, преобразуя при этом имеющуюся в памяти формулу методами булевой алгебры.

                      

                                                     Отношение к существующим компьютерам

 

В принципе этот метод предлагается в качестве основы для построения универсальной логической машины.

Но, вероятно, его можно применить и на существующих компьютерах, например, для сжатия информации, если

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

Однако, очевидно, что эффект от такого преобразования может быть получен только при больших объёмах информации.   В соответствии с формулой (1)  число букв алфавита  Alf растёт гораздо медленнее чем мощность поля M ( число элементов ) и, соответственно, растёт вероятность, что длина   формулы будет меньше мощности поля, т.е. произойдёт сжатие. 

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

В принципе, можно разработать программу для выборки определённого участка формулы с применением операция умножения (конъюнкция) формул.

В любом случае этим придётся заняться для проверки идей, изложенных здесь, если кто то заинтересуется ими.

 

                                             Примеры и комментарии

·Пример 1.

     Рассмотрим построение булевой формулы для информационного сообщения Inf[1]  рис.3. Число  единиц в множестве Inf[1] равно 9, т.е. s1[1] = 9, а число нулей s0[1] = 55. Нетрудно определить, что наибольшее совпадение  имеют два множества y1  и  y2 , так как у них s1(y1) = s1(y2) = 9 и s0(y1) = s0(y2) = 23  и соответственно по формуле (2)

                              sov(y1) = sov(y2) =  9/9 - 23/55 = 0,58

Поэтому выберем одно из них, например, y1, и тогда первой  формулой  F[0]  будет только одна буква k (Табл 1):

                                                         F1[0] = k;

Формула F[0]  уже несёт некоторую информацию. Если осуществить обратное преобразование, то получится информационное поле, показанное на рис.4. Это поле уже несёт некоторую смысловую информацию об объекте на Рис.3, например, что  если под объектом понимать некоторую фигуру , то она расположена слева. Кроме того,

       11110000     s1(y1)/ s1[1] = 1,  т.е. все единицы расположены в y1, а значит множество -y1 можно исключить

11110000    из дальнейшего процесса построения формулы, сократив процедуру.

11110000

11110000

11110000

11110000

11110000

11110000

 Рис.4       

На втором  шаге находим формулу из двух букв. Нетрудно определить, что наибольшее совпадение будет у пересечения множеств y1y2, т.е  формула

                                                                      F1[1] = kl;  (рис. 5)      sov(y1y2) =1- 7/55 =  0.87

На третьем

                                                            F1[2] = klz;     (рис.6)  sov (y1y2-y3) =8/9 - 0/55 = 0.89

далее

                                                            F1[3] = kl(z +h) (рис.7)  sov(y1y2(-y3||x1)) = 9/9 - 3/55 = 0.94

                                                            F1[4] = kl(z+ hi)  (рис.8)  sov(y1y2(-y3||x1x2)) = 9/9 - 1/55 = 0.98

                                                            F1[5] = kl(z + hij) (рис.9)  sov(y1y2(-y3||x1x2x3) = 9/9 - 0/55 = 1

 

     11000000               01000000           11000000           11000000

     11000000               01000000           11000000           11000000

     11000000               01000000           11000000           01000000

     11000000               01000000           11000000           01000000

     11000000               01000000           01000000           01000000

     11000000               01000000           01000000           01000000

     11000000               01000000           01000000           01000000

     11000000               01000000           01000000           01000000

        Рис.5                    Рис.6                 Рис.7                Рис.8

 

По рисункам 5 - 8 можно проследить, как постепенно информация становится всё более точной.

 

                  Два примера более сложного, с точки зрения нашего разбиения, изображения

·  Пример 2.

                         

                               00011100            00001100

                               00100010            00000000

                               01000010            00000000

                               00000100            00000000

                               00001000            00000000

                               00010000            00000000

                               00100000            00000000

                               01111110            11111111

                                 Рис.9                  Рис.10

                 Формула для изображения Рис. 9 :

                  F2 =  v(uw(x(l+m)+k(y+z))+(h+k)(jym(x+u)+zlh(wx+jk)) + i(h(ywm+j(xl+zky))+u(jxlm+wkyz)),

         но на одном из первых шагов  получена гораздо более простая формула

                                          vuw + hijxl

         изображение которой показано на рис.10 и видно, что эта формула уже несёт некоторую смысловую

         информацию.

                

· Пример 3                

 

                            F3= (vuw+hij)(x+y+z)(k+l+m) +xl(mj(i+h)+izw)+vy(wkz+umx)  (Рис. 11)

 

         01111110                   11111111

00000100                   00001100

00001000                   00001100

00010000                   00001100

00001000                   00001100

00000100                   00001100

00000010                   00001100

01111110                   11111111

  Рис.11                       Рис. 12

    В этом примере тоже на одном из первых шагов получается формула

                                     xl + vuw + hij    (Рис. 12),

т.е.различия для изображений всех трёх примеров очевидны с первых шагов.

 

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

               Попробуйте сократить (уменьшить число букв) представленные в примерах формулы. Пришлите результаты.                  

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


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

Комментарии