Practical minimization of Boolean functions..

http://moiidei.com/nauka-estestvennyie/prakticheskaya-minimizatsiya-bulevyih-funktsiy.
http://idshoohov.livejournal.com/155488.
http://obdamaskin.livejournal.com/87309.html


Практическая минимизация булевых функций.
Practical minimization of Boolean functions.
Представление информации булевой формулой.
Submission of information through a Boolean formula.

Определения.
Definitions
Под минимизацией булевых функций понимается построение булевой
формулы, описывающей булеву функцию, с минимальным числом букв.
Under the minimization of Boolean functions is understood to build a
Boolean formula with a minimum number of letters describing the
Boolean function.

Буква, входящая в формулу, обозначает одну из двоичных переменных,
являющуюся аргументом булевой функции.
The letter, included in the formula, represents one of the binary
variables that are arguments of a Boolean function.
Пример формулы:
Formula example
((ym+i)(j+zy)+u)(ml+h+vw)+lvwz
В этой формуле 16 букв.
In this formula, 16 letters.
Функция задаётся таблицей истинности, т.е. таблицей, устанавливающей
связь между значением аргумента (входящей переменной) и значением
самой функции.
Напомню, что и входящие переменные, и сама функция могут принимать
только одно из двух значений - 0 и 1. В некоторых случаях значения
функции могут быть не определены.
Function is given truth table, i.e. table, which establishes the
connection between the value of the argument (input variables) and the
value of the function.Let me remind you that the incoming variables
and the function itself can only take one of two values - 0 and 1.
In some cases, the values of the function can not be determined.

Пример таблицы истинности для 6 пар переменных.
An example of the truth table for 6 pairs of variables.

Переменные попарно:
The variables in pairs:
{h,u}; {i,v}; {j,w}; {k,x}; {l,y}; {m,z}.


Таблица истинности
Truth table
1 2 3
номер значения переменных значение функции F для примеров
строки values of variables value of the function F for examples
line
number 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

Методика минимизации булевых функций
The method of minimization of Boolean functions

В принципе методика разработана для практически любого числа
переменных, но пока она всё ещё отрабатывается только для 6 пар
переменных или меньше. Программа работает достаточно медленно, так как
процедура построения требуемой булевой формулы предусматривает
перебор вариантов, а число вариантов определяется, в том числе, и
структурой искомой формулы. Чем сложнее формула, тем больше времени
требуется для её построения.
Исходной информацией для программы являются данные графы 3 таблицы
истинности, т.е. последовательность из 64 знаков 0, 1 или отсутствия
любого их этих знаков. Для удобства записи вместо пустого места в
последовательности будем писать букву "a", чтобы видны были границы
последовательности.
Например, для построения формулы булевой функции F(1) для 5 пар
переменных (исключена пара k,x) из графы 3 таблицы истинности нужно
ввести в программу последовательность

In principle, the technique developed for virtually any number of
variables, but so far it has worked only for 6 pairs of variables or
less. The program works very slowly, as the procedure for constructing
a Boolean formula provides options for sorting and duration determined
by the number of options, depending on the structure of the formula. A
more complicated formula takes longer to build.
The input to the program are the data column 3 of the truth table,
i.e. sequence of 64 digits 0, 1, or the absence of any of these signs.
For convenience, instead of an empty place in the sequence, we write
the letter "a", so we could see the boundaries of the sequence.
For example, to construct a formula of a Boolean function F (1) 5
pairs of variables (removed a couple of k, x) from column 3 of the
truth table must be entered in the program sequence

1111aaaa0001aaaa0010aaaa0100aaaa1000aaaa1000aaaa1000aaaa1111aaaa (1)
Через некоторое время программа выдаст формулу для данной последовательности, т.е.
After some time, the program will give a formula for the sequence, i.e.

F(1) = ((ym+i)(j+zy)+u)(ml+h+vw)+lvwz (16 букв в формуле) (16 letters in the formula)

Для F(2) (для тех же переменных) таблица истинности даёт несколько
иную последовательность
For F (2) (for the same variables) truth table gives a slightly different sequence

1111aaaa0001aaaa0010aaaa0100aaaa0010aaaa0001aaaa0001aaaa1111aaaa (2)
и, соответственно, программа другую формулу для F(2)
and, accordingly, the program gives another formula for F (2)

F(2) = (v(lz+u)w+(i+(m+u)y)(hj+y(z+ji)))(h+v+m+w) (19)

Функция F(3) определяется всеми 6-ю парами переменных.
Последовательность её значений из таблицы истинности не содержит
пустых мест и выглядит так
The function F (3) is defined by all 6 pairs of variables. The
sequence of its values from the truth table contains no empty seats
and looks like

1111111100010001001000100100010010000010100000011000000111111111 (3)
Формула для F(3), определённая с помощью программы,
The program has found the formula for 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).
Finally, we turn our attention to another example of a function F (4)
of the same 5 pairs of variables, characterized in that there is a
truth table corresponding box missing values of not only the lack of
a pair of x and k, but simply because that the values of this
function for one reason or another are not determined. For example, a
developer logic is absolutely indifferent to what value will be a
Boolean function for a given combination of variables. In this case,
the program itself as it chooses a value function for an empty place,
which ensures minimal formula. This is a significant difference
between the models for F (1), F (2) and the function F (4).
Последовательность для F(4) будет выглядеть так
Sequence for F (4) would look like

1000aaaa000aaaaa1110aaaa1a1aaaaa0110aaaa11a1aaaa1aaaaaaaaaa1aaaa (4)

а сама формула, как
and the formula as

F(4) = (l+m)((j+z)u+v)+uw +ljhm (12)

Если в последовательности (1) все буквы a заменить на 0, то
последовательность будет выглядеть следующим образом
If all the letters a replaced by 0 in the sequence (1), the sequence
is as follows

1111000000010000001000000100000010000000100000001000000011110000 (1.1)
и соответствующая формула
and the corresponding formula

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

Практически формула осталась та же, но появилась ещё одна буква k за
счёт фактического перехода от 5 пар переменных к 6 парам.
Замена же всех букв a на 0 в последовательности (4) приведёт к другой
формуле F(4.1) с определённо бОльшим числом букв в ней.
Almost formula remained the same, but there is another letter k for
the actual transition from 5 to 6 pairs of variables pairs.
Substitution of all the letters a to 0 in the sequence (4) leads to
another formula F (4.1) with a definitely a great number of letters in
it.

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}. В этом случае последовательность значений
функции выглядит так
Example of a function F (5) of the truth table for the same 5 pairs of
variables, but there is no pair {h, u}. In this case, the sequence of
the function looks like this

10000001100010011001010111100011aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa (5)
Для последовательности (5) программа даёт результат
For a sequence (5) the program gives the result

F(5) = (l(iw+k)m+(y+(j+k)v)(xz+v(w+zy)))(x+l+j+m) (19)

Небольшое заключение.
Finally, a small.
Таким образом, если надо получить формулу для некоторой булевой
функции, то просто присылайте последовательность значений функции из
таблицы истинности. Можно прислать и просто формулу для данной
функции, полученную каким то другим способом. Программа может и в
этом случае построить свой вариант формулы.
So, if you need to get a formula for some Boolean function, then just
send the sequence of the function of the truth table. You can send and
simple formula for this function, obtained some other way. The program
can also in this case to construct its own version of the formula.

Понятие "похожести" множеств в теории множеств The concept of "similarity" of sets in set theory

http://moiidei.com/nauka-estestvennyie/kolichestvennaya-otsenka-pohozhesti-uporyadochennyih-konechnyih-mnozhestv-raznotipnyih-element.html

Количественная оценка похожести упорядоченных конечных
множеств разнотипных элементов


Поле множеств

Под полем множеств Р здесь будет пониматься конечное упорядоченное
множество элементов - ячеек , в которые могут размещаться или не
размещаться элементы сравниваемых множеств. Если обозначить элемент
буквой "a" , то графически поле множеств с числом ячеек n(P) = 32 можно представить, например, так


aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa (P1)

aaaa
aaaa aa
aaaa aaaaaa
или так aaaa (P2) или так aaaaaaaa (P3)
aaaa aaaaaaaa
aaaa aaaaaa
aaaa aa
aaaa



В дальнейшем мы будем пользоваться в основном представлением (Р1) для удобства записи.


Сравниваемые бинарные множества

Сначала мы будем рассматривать бинарные множества, т.е. множества
двоичных элементов S. Примерами таких элементов могут служить чёрная и
белая точки, 1 и 0, слова "да" и "нет" и пр.

Вот один из примеров множества нулей и единиц на поле множеств Р

10001110001101101100011101011100 (S1)

Другой пример

10101110001101101101010101011100 (S2)

Вопрос: насколько похожи эти два множества?

В принципе, для классических множеств, которые состоят из элементов одного типа, существует такая оценка. Она называется коэффициентом Жаккара J(Jaccard) , который вычисляется как отношение числа элементов пересечения
двух множеств к числу элементов объединения этих множеств. Коэффициент
равен нулю, когда множества не имеют общих элементов, и единице, когда множества равны, в остальных случаях значение где-то посередине.

Этот коэффициент нельзя напрямую применить к множествам типа S1 и S2, состоящим из двух видов элементов, но можно его модернизировать применительно к таким множествам.

Для этого введём нумерацию ячеек поля множеств Р.
Тогда каждое из множеств S на поле множеств Р можно представить как
объединение подмножества номеров ячеек C1S поля Р, в которых содержатся
элементы 1 и подмножества номеров ячеек C0S поля Р, в которых содержатся
элементы 0. При таком представлении множеств похожесть двух множеств S1
и S2 можно определить как разность похожестей двух подмножеств.

Будем обозначать число элементов произвольного множества S как n(S), а
похожесть множеств S1, S2 как J(S1,S2).

Тогда n(C1S1ПC1S2) обозначает число элементов 1 в пересечении множеств C1S1,C1S2, а n(C0S1ПC0S2) обозначает число элементов 0 в пересечении множеств C0S1,C0S2.
Знак "П" обозначает операцию пересечения множеств.

Соответственно, n(C1S1UC1S2) обозначает число элементов 1 в объединении множеств C1S1,C1S2, а n(C0S1UC0S2) обозначает число элементов 0 в объединении множеств C0S1,C0S2.
Знак "U" обозначает операцию объединения множеств .

Тогда

J(C1S1,C1S2) = n(C1S1ПC1S2) / n(C1S1UC1S2) ;

J(C0S1,C0S2) = n(C0S1ПC0S2) / n(C0S1UC0S2) ;

знак "/" обозначает операцию деления (отношения).

Найдём значение cхожести для множеств S1 и S2, которую обозначим
как J(S1,S2).

Введём нумерацию ячеек для поля множеств P1.

0 1 2 3 4 5 6 7 8 910111213141516171819202122232425262728293031
a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a P1

Соответственно, множества S1 и S2

0 1 2 3 4 5 6 7 8 910111213141516171819202122232425262728293031
1 0 0 0 1 1 1 0 0 0 1 1 0 1 1 0 1 1 0 0 0 1 1 1 0 1 0 1 1 1 0 0 S1

0 1 2 3 4 5 6 7 8 910111213141516171819202122232425262728293031
1 0 1 0 1 1 1 0 0 0 1 1 0 1 1 0 1 1 0 1 0 1 0 1 0 1 0 1 1 1 0 0 S2

Множества C1S1,C1S2

C1S1 = {0,4,5,6,10,11,13,14,16,17,21,22,23,25,27,28,29}

C1S2 = {0,2,4,5,6,10,11,13,14,16,17,19,21,23,25,27,28,29}

их пересечение

C1S1ПC1S2 = {0,4,5,6,10,11,13,14,16,17,21,23,25,27,28,29}

Число элементов в пересечении n(C1S1ПC1S2) = 16

Объединение этих множеств

C1S1UC1S2 ={0,2,4,5,6,10,11,13,14,16,17,19,21,22,23,25,27,28,29}

Число элементов в объединении n(C1S1UC1S2) = 19

Тогда похожесть множеств C1S1,C1S2 равна

J(C1S1,C1S2) = n(C1S1ПC1S2)/ n(C1S1UC1S2) = 16/19 = 0,842;

Проделаем те же операции над множествами C0S1,C0S2

C0S1 = {1,2,3,7,8,9,12,15,18,19,20,24,26,30,31}

С0S2 = {1,3,7,8,9,12,15,18,20,22,24,26,30,31}

их пересечение

C0S1ПC0S2 = {1,3,7,8,9,12,15,18,20,24,26,30,31}

Число элементов в пересечении n(C0S1ПC0S2) = 13

Объединение этих множеств

C0S1UC0S2 = {1,2,3,7,8,9,12,15,18,19,20,22,24,26,30,31}

Число элементов в объединении n(C0S1UC0S2) = 16

Тогда похожесть множеств C0S1,C0S2 равна

J(C0S1,C0S2) = n(C0S1ПC0S2) / n(C0S1UC0S2)= 13/16 = 0,8125;

Пока что мы нашли схожести двух пар множеств двух типов на поле P - пары множеств C1S1,C1S2 с элементами 1 и пары множеств C0S1,C0S2 с
элементами 0.

А какова схожесть множеств S1 и S2 в целом?

Понятно, что схожести этих множеств C1S1,C1S2 и C0S1,C0S2
определяют и схожесть множеств S1 и S2, но в какой мере?

Введём понятия веса пары подмножеств, например C1S1,C1S2 или
С0S1,C0S2 на поле P как отношение числа элементов в объединении
пары к общему числу элементов поля P. Тогда

w(C1S1,C1S2 ) = n(C1S1UC1S2)/n(P)= 19/32 = 0.594;

w(C0S1,C0S2 ) = n(C0S1UC0S2)/n(P)= 16/32 = 0.5,

где символом w обозначен вес каждой пары множеств на
поле P.

И, наконец, найдём схожесть множеств S1 и S2 по следующей формуле
(знак * обозначает операцию умножения, а знак + обозначает операцию
сложения)

J(S1,S2) = J(C1S1,C1S2) *w(C1S1,C1S2 ) + J(C0S1,C0S2) * w(C0S1,C0S2 )

= 0.842*0.594+0.812*0.5 = 0.906



Количественная оценка похожести множеств с
разнотипными элементами



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

Принципы, заложенные в предложенных методике и формуле, могут быть распространены и на вычисление похожести двух множеств на поле P,
каждое из которых содержит элементы, число типов которых превышает 2. Например, множества могут содержать не только белые и чёрные точки, но и серые точки разной степени серости, а также цветные точки. .

Пусть имеется поле P с числом ячеек n(P).

На этом поле последовательно сформированы два множества
разнотипных элементов S1 и S2 с разным, в общем случае, числом типов
элементов.

0 1 2 3 4.............63 64........................1278 1279..............n-1 P
a b b c d.............d c ......................... a e.............. k S1
b k b c d.............c c.............................b e .............. l S2

Отметим, кстати, что каждое множество может содержать и пустые
элементы, т.е. незаполненные ячейки "a" на поле P, которые тоже рассматриваются как один из типов элементов множеств S1,S2.
Типы элементов (a, b, c, d, ...,e,...,k,l, ...) множеств S1 и S2 тоже можно рассматривать как множества соответственно T1и T2, которые образуют объединённое множество

T1UT2;

с соответствующим общим числом типов n(T1UT2).

Введём переменную t и упорядочим множество T1UT2, введя нумерацию типов
от 0 до n(T1UT2), и найдём все множества ячеек множеств на поле P
для S1,S2 и для всех типов элементов от 0 до n(T1UT2)

C0S1, C1S1, C2S1, ..., CtS1,..., Cn(T1UT2)S1

C0S2, C1S2, C2S2, ..., CtS2,..., Cn(T1UT2)S2

Затем находим пересечения вышеприведенных множеств

C0S1ПC0S2, C1S1ПC1S2 , ... CtS1ПCtS2 , ... Cn(T1UT2)S1ПCn(T1UT2)S2

и их объединения

C0S1UC0S2, C1S1UC1S2 , ... CtS1UCtS2 ,... Cn(T1UT2)S1UCn(T1UT2)S2

Для каждого пересечения и объединения находим число элементов

n(C0S1ПC0S2), n(C1S1ПC1S2) ,...n(CtS1ПCtS2) ,...n(Cn(T1UT2)S1ПCn(T1UT2)S2)

n(C0S1UC0S2), n(C1S1UC1S2) ,...n(CtS1UCtS2) ,... n(Cn(T1UT2)S1UCn(T1UT2)S2)

Для каждой пары множеств CtS1, CtS2 вычисляем значение похожести по
формуле

J(CtS1,CtS2) = n(CtS1ПCtS2) / n(CtS1UCtS2)

Затем для каждой пары множеств CtS1,CtS2 вычисляем вес по формуле

w(CtS1,CtS2 ) = = n(CtS1UCtS2)/n(P)

И, наконец, найдём схожесть множеств S1 и S2 по следующей формуле


t=n(T1UT2)-1
J(S1,S2) = E J(CtS1,CtS2) * w(CtS1,CtS2 ) ,
t=0

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




Область применения количественной
оценки похожести множеств



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

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

Сравнение и измерение похожести кодов одинаковой длины и, естественно, одинаковой природы. Например, двоичный код или генетический код.