Parallel processing of information by means of a network of logic without a computer

odamaskin@gmail.com Oleg Damaskin


Parallel processing of information by means of a network of logic without a computer


"the brain is not computer but it works fast"


Statement of the Problem

It does not pretend to offer any specific decisions or specific devices for parallel processing information without a computer. It does not offer specific ideas for artificial intelligence systems. It simply discusses some possible principles of information processing that are linked to the idea of ??providing information of a Boolean formula.

It is assumed that the input information at each time represents the state of binary information elements of an ordered set of these elements in the power of n elements. For ease of understanding, we shall call the set of state elements, ie, "picture", as if it were drawn from ones and zeros in a certain moment of time, we shall call "the frame".

Traditionally, information processing begins with the presentation of "frame" in the form of a sequence of points, ie sequence of binary elements, stretching the "picture" in time, and introducing it into the computer to conduct operations in accordance with laid down in the computer program. It is clear that the parallel operations simultaneously on all points "paintings" in theory should provide faster results. Perhaps even more important aspect of the parallel approach is that such an approach may allow the right to see the "picture" in general, to get a general idea about it, and then proceed to detail. This is especially important when creating complex control machines such as robots. Instead of the traditional approach "from specific to general," you can implement the principle "from general to specific."


The theoretical basis for solving the problems of parallel processing of information is considered before, "Presentation of information by a Boolean formula" ( http://moiidei.com/nauka-estestvennyie/predstavlenie-informatsii-bulevoy-formuloy.html ), where it was shown that the sequence of zeros and ones can be replaced by a Boolean formula in which each letter displays a subset of the main sequence and, in general formula displays a subset formed by the consolidation and the intersection of basic subsets. It is important to note that the operations of intersection and union of subsets can be interpreted as corresponding to the logical operations of conjunction ("and") and disjunction ("or"), indicating that the ability to use logic when processing information.

Breaking into subsets

The introduction of the alphabet


In the "Presentation of information by a Boolean formula," it was shown that for a correct presentation of information by a Boolean formula original set of n elements should be divided into at least m pairs of mutually disjoint subsets, where m is given by n = 2 to the degree m. If for each subset to associate some of the letters, the alphabet of the language of Boolean formulas will consist of 2m letters. Obviously, the larger the number of elements n in the set, the smaller the number of letters in the alphabet is required for the realization of a Boolean formula. For example, for a set of 8 elements are required 6 letters almost as much as the and elements, as for the set of the 1024 elements are required only 20 letters.. The more elements in the set, the more economical the alphabet is. Moreover, the number of letters in the alphabet can be reduced by half, given that the original set is divided into pairs of opposite sets.However, then it will be necessary to introduce in the alphabet special character of opposition or of denial, that lengthens itself a Boolean formula.

Breaking into subsets

Actually one can to break the initial set of m pairs on opposite (mutually disjoint) subsets by many ways depending on the purpose of a particular device which will apply parallel processing of information, but the essence the decomposition is independent from this.
So here would be considered a method that was used in the program to minimize Boolean function ("Practical minimization of Boolean functions" http://moiidei.com/nauka-estestvennyie/prakticheskaya-minimizatsiya-bulevyih-funktsiy.html) because it is relatively easy to implement dynamically (earlier this principle Andrew Plakhov suggested to me http://www.membrana.ru/particle/2121), although to speed up the program it would be better to use a static fragmentation.


This fragmentation will be shown in the example for the set of 8 elements (n = 8). Denote the elements of the letter э. Then the set of elements can be written as


mD = { э1, э2, э3, э4, э5, э6, э7, э8 }


To further decomposition will apply a simple principle.
We will form the first pair of subsets as the first and second half of set D, then each of the resulting subsets are also split into two halves, and from first halves compiled one of the subsets of the second pair, a second subset from the second halves. Next, have each half of the newly obtained subsets is divided into halves and out of quarters we form the new sets, etc. The result will be obtained the following sets


mC = { э1, э2, э3, э4 } mCp = { э5, э6, э7, э8 }


mB = { э1, э2, э5, э6 } mBp = { э3, э4 , э7, э8 }


mA = { э1, э3, э5, э7 } mAp = { э2, э4, э6, э8 }


Obviously, mCp, mBp, mAp respectively denote the sets of opposing subsets of designated mC, mB, mA.

Circuit of the parallel formation of a Boolean formula


In the "Minimization of Boolean Functions applying Equivalence of Sets" ( http://moiidei.com/nauka-estestvennyie/minimizatsiya-bulevyih-funktsiy-po-sovpadeniyu-mnozhestv.html ) and "Practical minimization of Boolean functions" forming a Boolean formula occurs sequentially through the steps. At each step, each set can be seen and chose a set of with the greatest similarities (and in fact, the set with the smallest number of zeros and with the largest number of units). Naturally, such an approach is unacceptable for the parallel processing of information, and no computational operations, in principle, should not be.
Here we propose a fundamentally different approach. Everything should be based only on logical operations. Variant of this approach is seen again at the example of constructing a Boolean formula for the information set of 8 elements. For convenience, review the relevant schemes are constructed for each pair of subsets separately, although the practical implementation of these schemes will be combined. Scheme 1 shows the three separate schemes, but together, not to make three drawings, moreover, it shows that the scheme consists of the same can be said to elementary subcircuits





э1 э2 э3 э4 э5 э6 э7 э8 set ( mD = mC + mCp)
э1 э2 э5 э6 э3 э4 э7 э8 set ( mD = mB + mBp)
э1 э3 э5 э7 э2 э4 э6 э8 set ( mD = mA + mAp)
| | | | | | | |
o o o o o o o o disconnection elements
\ and / \ and / \ and / \ and /
\or / \or / \or / \or / switching logic level 1
\ / \ /
\--- and----/ \--- and----/
\---or--- / \---or----/ switching logic level 2
| |
sC(sB,sA) sCp(sBp,sAp) signals
| ------->and<-------no---------|
| | |
| C(A,B) | output letters
| -----no---->and<--------------|
\ | /
\ Сp (Ap,Bp) / output letters
\ ­­­------> and <--------/
\---------->or <--------/ switching logic level 3
| \
sD

Scheme 1

How does work the scheme? The work is illustrated in Table 1 for some typical examples. For example, option 1, when state of at all levels of logic in the position "or" all the signals from the original set of data elements equal to zero and the on output of the circuit not appears at least one letter. This means that the set is "empty", ie There is no element in the state 1 (the Boolean formula - 0). Or, conversely, option 2, when all logic elements are in a state "and" and all the signals are equal to one, it means that the set of "fully occupied" (a Boolean formula - 1). Each of these results obtained instantly, in one step. In one step the same results are obtained if only one element of the information field at 1 (all others 0) or, conversely, is only one element in the state 0 (all others 1) (options 3 and 5), and in some cases and in two or 6 active elements (versions 4 and 6). ВIn some cases, on the first step appears at the output of only one letter (versions 10 and 11), ie the first step is determined only by the first letter of the formula. This character shows that in this subset are concentrated all (version 10) or majority (version 11) of the excited elements. And finally, there are options (8.9), when there is not a single character, or, conversely, are all. In all these cases should proceed to the second step. For this part of the elements is disconnected. As a result, can get the scheme type of Scheme 2, the operation of which is illustrated in Table 2.


Table 1
v logic
e level signals Boolean
r. 3 2 1 sC sCp sB sBp sA sAp letters formula
1 or or or 0 0 0 0 0 0 0 0 final
2 or and and 1 1 1 1 1 1 1 1 final
3 or or or 1 0 1 0 1 0 С,B,A C*B*A final
4 or or or 1 0 1 0 1 1 C,B C*B final
5 or and and 1 0 1 0 1 0 С,B,A C+B+A final
6 or and and 1 0 1 0 1 1 C,B C+B final
7 or and and 0 0 0 0 0 0 0 move to version 8
8 or or and 0 0 0 0 0 0 0 disconnect mCp (Sch.2a) and move to Table 2.
9 или или и 1 1 1 1 1 1 0 disconnect mCp (Sch.2a) and move to Table 2
10 или или или 1 0 1 1 1 1 C C* disconnect mCp(Sch.2a) and move to Table 2
11 или и и 1 0 0 0 0 0 C C+ disconnect mCp(Sch.2b) and move to Table 2


Schemes 2a and 2b are working on exactly the same principle as Scheme 1, but due to the fact that half of the elements from multiple mD is disabled, the options are fewer.

э1 э2 э3 э4 set ( mC )
э1 э2 э3 э4 set ( mB + mBp)
э1 э3 э2 э4 set ( mA + mAp)
| | | | | | | |
o o o o o o o o disconnection elements
\ and / \ / \ and / \ /
\or / \or / \or / \ or / switching logic level 1
\ / \ /
\---- or----/ \---- or-----/
| |
sB(A) sBp(Ap) signals
| ------->and<-------no-------------|
| | |
| B(A) | output letters
|----------no------>and<------------|
|
Bp(Ap) output letters




Scheme 2a.


э5 э6 э7 э8 set ( mCp)
э5 э6 э7 э8 set ( mB + mBp)
э5 э7 э6 э8 set ( mA + mAp)
| | | | | | | |
o o o o o o o o disconnection elements
\ / \ and / \ / \ and /
\ or / \or / \ or/ \or / switching logic level 1
\ / \ /
\------ or------/ \-----or----/
| |
sB(A) sBp(Ap) signals
| ------->and<-------no----------------|
| | |
| B(A) | output letters
| -----no--------->and<----------------|
|
Bp(Ap) output letters


Scheme 2b.





Table 2


v logic
e level signals Boolean
r. Scheme 1 sB sBp sA sAp letters formula
1 Sch.2a and 1 1 1 1 1 С*1 final
2 Sch.2a and 1 0 1 0 B,A C*(B+A) final
3 Sch.2b and 1 0 1 0 B,A C+BA final
4 Sch.2a and 0 0 0 0 disconnect mBp (Sch.3)and move to Tables 3а и 3b


э1 э2 э3 э4 set ( mC )
э1 э2 set ( mB )
э1 э3 э2 э4 set ( mA + mAp)
| | | | | | | |
o o o o o o o o disconnection elements
\ and / \ or / \ and / \ or /
\or / \ / \or / \ / switching logic level 1
\ / \ /
\-----or----/ \------or----/
| |
sA sAp signals
| ------->and<---------no-----------|
| | |
| A | output letters
| -----no------>and<----------------|
|
Ap output letters


Scheme 3.


Table 3a


v logic
e level signals Boolean
r. 1 sA sAp letters formula
1 and 1 0 A С*(B*A+Bp*Ap) final
2 and 1 0 A C*B*A+Cp*Bp*Ap final

Table 3b

v logic
e level signals Boolean
r. 1 sA sAp letters formula
1 and 1 0 A С*(B+A)(Bp+Ap) final
2 and 1 0 A (C+B+A)(Cp+Bp+Ap) final


Control for scheme


In the formation process of Boolean formulas to represent the information is occur specific transformation of scheme, the on output of which appear, in the end, the Boolean formula in the form of a sequence of letters. Actually, for process control are apply two types of signals: switching logic and disabling the input elements.

Switching logic


The scheme provides for n levels of logic, ie number of levels equal to the number of pairs of opposite subsets, in fact is used by one level less, and the formal number of different combinations of logic states can be equal to 2n-1. I say officially, because I have not been carefully studied this question, but in fact, as seen from the above example, the number of steps and, consequently, the number of switching logic depends on the specific problem, the specific structure of the transformed set of information elements. It is not excluded that it is possible to construct a circuit without switching logic, if you just build a separate circuit with logic elements, "or" and a separate circuit with logic elements "and".


As logic switches


Switching logic is to translate all the logical elements of a given level from one state to another, ie of status "or" c "and" or vice versa. This switching is carried out by teams from the clock generator (and hence must be a clock generator) , flow and sequence of which, in turn, be controlled from the output of the main scheme in accordance with the results at each step and specific to that particular device for processing information. The first step on the first tact, usually can be the installation of logic elements at all levels in status "or" although, for example, you can start (a very powerful sets with many thousands of elements) with "and" on the first levels (artificial decrease in sensitivity, "visual acuity"). Termination of the work should be done when a signal about getting formula is, it is not necessary that the formula is built to the end, it is possible that for the solution of some problems enough only part of the formula. Go to the next steps, respectively, is carried out when the formula is ready.

Disconnection elements


Disabling the elements implemented on the same principles as the switching logic and for disconnection are used scheme, similar schemes for formation information (see dawn).


Processing of information presented by the Boolean formula

What does the presentation of information by a Boolean formula

Speaking informally, the information submitted this on the language of a much higher level than binary encoding, with relevant consequences. Each letter of the language, not to mention every word carries a lot of information. One can confirm this assertion on the easiest example, the fields of information of m black and white dots of rectangular shape. ЭThis field can be divided into n = 2 in the degree m pairs mutually disjoint subsets, each of which matched as the future character (the letter) of a Boolean formula. A break on the set of pairs can be like this. The left and right halves, top and bottom, center and periphery . Then the first letter of the same formula indicates which part of the field contains most of the black, for example, points, and, perhaps, in some control systems that may be enough to make a decision. The evolution of the Boolean formula, respectively, and specifies the conditions for a decision.

From a formal point of view presentation of information by Boolean formula makes it possible to apply Boolean formula for the information processing through the aid of well-known apparatus of Boolean algebra in at least two areas. To process the information itself - in accordance with the theory of sets, while the use of control information - in accordance with the algebra of logic. In fact. For example, the operation of the disjunction of two formulas will unite the information presented by each formula, while shortening the total formula, and operation of the conjunction will highlight the specific information required by the intersection of the sets of and, in particular, to restore to this fragment the entire formula, ie all the information. Moreover, these operations can be implemented by not computer methods, but logic by circuits similar to those used above .

However, in real devices, a Boolean formula, which carries the information may be submitted not letters of the alphabet, but all the same to the same binary code that will allow process the information by logical means. It is also clear that the length of the encoded formula(word) is rather important parameter in terms of reducing the amount of memory of storage devices. On what does the length of the encoded formula? Well, first of all, the length of the formula. I have developed a method of minimizing Boolean formula is exactly the formula provides minimality. First of all, we note that in this method, the length of the formula depends on the nature of the information,the nature of the "image", is the location of zeros and ones on the set. A length is always different. It may be just one letter or formula may consist of a maximum number of characters is based on the number of sensors and the complexity of information, note. For example, for data sets of 8 elements the maximum length of the formula is 6 letters (not counting the other characters). Perhaps a professional mathematician can determine the maximum number of characters in the formula in the general case for any number of elements in the set.


The second factor - the length of the code letters, which depends primarily on the number of letters in the alphabet. The number of letters, in turn, depends on the number of pairs of subsets into which is divided the entire field of information, ie in fact from the size of the field. For example, an alphabet of about 64 characters of information provides a 2 to the power of 64 bits. This is quite a lot (as shown in the famous parable about the number of grains on a chess board) for some of the technical project in the field of cybernetics, and this example shows that the number of bits per letter grows much slower than the increase in the amount of information. Thus, for the amount of information 2 to the power 3 = 8 bits per letter requires 3 bits of information for 2 to the 64 bits requires 8 bits, ie only on 5 bits more . True, in fact, and in either case in the alphabet it must be added of some of the signs for set operations, which will increase the length of the code letters for a bit, which leads to redundancy, which in principle can be used for certain reductions in the most formula, as shown below.


It was noted above that the proposed method of presentation provides a minimal formula in terms of Boolean algebra.It was also noted that, on the other hand, the presentation of information by the formulas of Boolean algebra can be regarded as a language of a higher level than binary coding. Like other languages, it has its own, we can say, linguistic laws, it is determined to transform the binary information in the words of this language. This issue deserves a separate study, but a few examples worth considering now. For example, the formulas in Tables 3a and 3b were obtained in only three steps, because for the first two steps, it was determined that the location of zeros and ones in the opposite symmetric subsets, and therefore for the final construction of the formula was sufficient to determine the location of zeros and ones in only one of subsets. This property of symmetry can also be used to reduce the formula by introducing a special character "sim" (coded as one letter). Then, for example, the formula C * B * A + Cp * Bp * Ap can be written as C * B * A + sim. In short, we can find a lot of opportunities to reduce the formula by some recurring combinations of letters in formulas.

But, in my opinion, more important is the semantic essence of the proposed method for reducing formula. In particular, the formula for this method is constructed gradually from a more general picture of a more private details, and, in many cases does not necessarily bring the construction of the formula to the end. You do not need to look for a house on a street, if you are not in that city.

Storage and data compression
Memorizing information is one of the stages of information processing. Presentation of information by a Boolean formula allows you to compress a information and hence reduce the amount of memory in the device. In the beginning we talked about the "frame" and "picture". Under the frame refers to the amount of information that can be obtained with parallel processing of information on a given set of information elements. The more elements, the more information. But by repeatedly applying this set of elements can be obtained much more information and to form is all the "big picture". When the binary representation of the information actually remembered every "frame", although, of course, and the binary representation, there are methods of compression, but not common, but with respect to a given specific information. Data compression capabilities can be illustrated by a simple example. We assume in our case there are two 8-cell frame, ie overall "picture" consists of 16 elements, and then you have to count the total number of letters in the total number of elements, ie, out of 16. This means that to the set D must be added the set Dp, and any of the formulas derived above should include the letter D. For example, the CBA formula can be written as


DCBA (1)


(the sign of the conjunction "*" is omitted), and it is this formula displays the first frame. And on the set Dp (second frame) has received information in the form of the formula


DpC(B+A) (2)


Then the total information will be obtained from the disjunction of these two formulas, ie

DCBA+DpC(B+A) (3)

This formula consists of 8 letters (Dp - this is a letter opposing the letter D). However, this formula can be reduced by the rules of Boolean algebra and present, such as

C(B(A+Dp)+DpA), (4) which consists of 6 letters. I do not know how to implement the reduction of the formula so as to guarantee its minimum after the reduction, although the idea of ​​such a reduction, I have. In any case, it may be that this will be a complex process and to reduce the formula will need quite a long time. Perhaps it would be advisable to divide memory into two parts: the operational, storage formula without abbreviations and main which will be to memorize the reduced formula.


Replicating


Replicating "frame" as disabling elements, can be done about the same principle as the formation of the formula. To replicating, a network is built like in the opposite direction compared to the net to get the formula. We show that network as an example of the formula C (B + A). In this relatively simple case replicating proceeds as follows.

э1 э2 э3 э4 э5 э6 э7 э8 sets ( mD = mC + mCp)
э1 э2 э5 э6 э3 э4 э7 э8 sets ( mD = mB + mBp)
э1 э3 э5 э7 э2 э4 э6 э8 sets ( mD = mA + mAp)
| | | | | | | |
o o o o o o o o switching on 0 or 1
\ / \ / \ / \ /
\ / \ / \ / \ /
\ / \ /
\ / \ /
\__________/ \_________/
| |
sC(sB,sA) sCp(sBp,sAp) input signals
| ------------------------------|
| | |
| C (A,B) | input letters
| ------------------------------|
|
Сp (Ap,Bp) input letters



Scheme 4.

This scheme differs from Scheme 1 not only the direction of signals but also the lack of logic elements. In Scheme 1 the logical elements are needed to determine the form of a Boolean formula (conjunctive or disjunctive ).In Scheme 4 it not required, as here, on the contrary, the type of formula is already known, and accordingly the type of formula determines the state of elements (which elements of more units or zeros) and this is done, including through switching elements to 0 or 1 . In general, the procedure is about the same as in the construction of the formula, the set of replicable elements constructed in steps. Therefore, after the elements have to be excited for a while. Replicating "pictures" can be carried out by "cadres" or on row, or in any order. For this we need to implement the conjunction of the formulas for the entire picture with a formula designating a particular frame. For example, to get the first shot for "paintings" by the formula C (B (A + Dp) + DpA), must reproduce the formula DC (B (A + Dp) + DpA), and for the second shot must reproduce the formula
DpC (B (A + Dp) + DpA).

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 обозначает операцию суммирования переменных членов последовательности.




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



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

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

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

Ястреб на балконе в Бостоне

Он как то ночевал у нас на балконе