|
The text of the original in Russian
Presentation of a Boolean formula
Two definitions of information
Initially, the concept of information theory and the associated information linked to the notion of probability (AM Яглом and IM Яглом. Probability and Information. 1960.) Amount of information was defined as a measure of changes in uncertainty (entropy) for some events. Roughly speaking, if the probability of a certain event is 1, the message of this event has the information 0, respectively, the amount of information can be in the range from 0 to 1. We can say that this notion of information related to the meaning of the message. Number of information in the message, not having the sense of 0.
On the other hand, the fact is there is another notion of information as just a certain message without regard to the meaning of the message, sometimes the word "information" using the word "data".
When it became widely used binary coding, a new concept and the amount of information that is not linked to the likelihood and meaning, it simply reflects the length of the message as the number of binary digits, bits.
Is it possible to reconcile these two notions of information? I think you can, if the problem of receiving and transmitting information to consider in relation to the processing of information and the purposes of this treatment.
The message, in fact, turned into information as a result of its reflection.
Language as a means of providing information
Interaction with the environment and communicating with each other, people receive and transmit information.
Man receives information from the environment interpreting physical and chemical properties of objects using their senses. We can say that using sensory properties of objects are transformed into information, but we do not know the exact form in which information is presented in the human brain.
Two types of methods of presenting information
Mezhchelovecheskoe communication is carried out at least two types of methods. Methods of the first type are trying to provide facilities and events as well as their sees and feels the person, such as photography, television. Different systems of signals (including the human language) can be attributed to the second type.
Initial presentation of information
The signals emanating from the environment are the primary information, and information by any person or with a secondary or pererabotannnoy. The amount of information from the environment, unlimited, and the methods of transmission limits. The purpose of the first type is to present the environment as accurately as possible, ie convey as much information as possible.
Language - a tool for presentation of abstract information.
Methods of the second type does not show the objects as such, as a means of transmission of abstract representations of objects after the processing of human data obtained from the environment. These representations are expressed by language. Rules of language you can use words to shape the proposals and texts that are more or less detail describe real objects and phenomena. Language, among other things, reduces the amount of information, reduces the load on the processing mechanisms and prevents the transfer of unnecessary data. For example, you can send information on certain home by sending a photo or written description. The picture contains a lot more information than a description of where to measure it in bits, but it is often required to decide only certain data, which can be expressed in words. The language allows significantly compress the information from the reject unnecessary detail.
Simultaneously. Music, visual arts, too, in my opinion, can be attributed to the language.
Binary representation of information.
Now the technical devices, especially in computers, the most common presentation of a binary information through a sequence of ones and zeros.
Binary representation is not a language. In fact, this is a spot to display real objects (picture, television, the image on the screen), or coding.
Language of Boolean formulas
Many mathematics consider Boolean formulas, together with the rules of their formation and operations of their language. Definition of the language quite easily.
Set alphabet alphabet letters (it can be quite large)
a, b, c. .. ,
which are the words of language, and introduce the auxiliary symbols
| |, &, -, (,)
to denote the relationship between letters, words and language proposals. A set of rules that define the grammar of the language, ie Rules of the proposals are well known from Boolean algebra, let some of them. For example, letters
a, b, c. .. ,
are formulas, ie proposed language.
Combinations
(A & b) | | (-c & d) or (a | | b) & (-c | | d)
are also proposed language. The symbol & is often omitted, and the above suggestions may seem like a
(Ab) | | (-cd) or (a | | b) (-c | | d)
It should be noted that the symbol "=" in terms
ab | | ad = a (b | | d)
is not a symbol of the language of Boolean formulas, so the above expression is not the language of the proposal, but only shows that these two sentences are equivalent.
0 and 1 are also the letters of the language, have special properties:
a0 = 0, a1 = a, a | | 0 = 0, a | | 1 = 1
There are other rules. Applying these rules, you can combine the individual proposals into a more complex, reducing the number of letters in sentences without changing the meaning of a proposal or a proposal with a new meaning, as in ordinary language.
Sets and Presentation Information Boolean foriuloy.
One interpretation of Boolean algebra is the theory of sets. It is this interpretation allows to use the language of Boolean formulas in the language of information. This means that to apply the proposed method of reporting a Boolean formula can be only to information that previously represented by a set of objects.
In the first phase of this set is mnozhestovo zeros and ones.
The initial set of information is called a field Pole. Formally Pole may be empty, but divided into a finite number of cells, each of which may be empty or it may be an element 0 or element 1. In a Pole can be graphically represented by a sequence of cells, either in the form of an arbitrary form of figures, including the multi-dimensional.
Information
The field, represented in Figure 1 does not carry any information. It is simply a "retina", a tool for obtaining information. Information occurs when the field turns into a lot of ones and zeros. Sequence
11000000010000000010000000010000000010000000010000000010000000010000000
Fig. 2. Information Inf [1]
information is already Inf [1].
Or, the same sequence, but on the field of another configuration
11000000
01000000
01000000
01000000
01000000
01000000
01000000
01000000
Fig.3. Information Inf [1]
Information (or message) to all the multitude of ones and zeros. Number of information is determined by the size of the field. In this particular example, it equals 64 bits.
On the other hand, is strictly defined by a finite amount of fields for providing information to specify only the location of units (or vice versa) of zeros, ie define the set of units (or a lot of zeros).
Final Pole information field is divided into at least
Alf = log (base 2) M (1)
pairs vzaimoneperesekayuschihsya sets. In the formula (1) M denotes the power set (the number of cells) Pole. In our case, M = 64 and Al f = 6 pairs, respectively. Pairs of sets of configurations can be very different. Much of this depends on the specific tasks and the statistical properties of messages. In this example, apply the following decomposition. The first three pairs of lines formed Pole:
x1,-x1; x2,-x2; x3,-x3;
Many x1 - four top-line Pole (cell 0 - 31)
-x1 - four bottom-line Pole (cells 32 - 63)
x2 - the top two lines set x1 (0 - 15) and two top-line set-x1 (32 - 47)
-x2 - two sets of bottom-line x1 (16 - 31) and two bottom-line set-x1 (48 - 63)
x3 - all the odd lines Pole (cells 0 - 7, 16 - 23, 32 - 39, 48 - 55)
-x3 - all even-numbered lines Pole (cells 8 - 15, 24 - 31, 40 - 47, 56 - 63).
Another three pairs of sets formed from the columns of the field the same way:
y1,-y1; y2,-y2; y3,-y3;
y1 - the four left column (cell 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-four right-hand column (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 - the two left columns set y1 (0,8,16,24,32,40,48,56, 1,9,17,25,33,41,49,57), and two left column set-y1 (4, 12,20,28,36,44,52,60, 5,13,21,29,37,45,53,61)
-y2 - two right-hand column set y1 (2,10,18,26,34,42,50,58, 3,11,19,27,35,43,51,59), and two right-hand column set-y1 (6 , 14,22,30,38,46,54,62, 7,15,23,31,39,47,55,63)
y3 - the odd-numbered columns of the field (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 - even-numbered columns of the field (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)
Alphabet
In principle, as the alphabet, you can use the same designations that apply to sets. However. for convenience as a record applies only to letters of the alphabet (without adding the digits and the sign "-") in accordance with the table. 1.
Table 1
Letter A lot
m y3
z-y3
l y2
y-y2
k y1
x-y1
j x3
w-x3
i x2
v-x2
h x1
u-x1
Besides the letters enter the characters in the alphabet "(" ")" and "+" instead of "| |", which applies to sets.
The idea of the method
We have already talked about that for a given field, Pole for the transmission and processing of information rather than ask all field Inf [i] (eg, Inf [0]), but many units (or zeros). This property of finite sets and is based idea of the method. With the help of Boolean algebra with respect to the uniform finite set we select the set that contains only one. Regulation of this set on the field Pole determines the corresponding Boolean formula, written letters of the alphabet.
Procedure
A step-by-step procedure for determining the set of units. First, there is some initial set of Table 1 ar [0], the closest to the desired, then there is a lot of ar [1] by merging or intersection of the baseline sets of Table 1, the third step is a lot of ar [2] as a combination of three sets of baseline etc. But what is meant by the proximity of a set of ar [i] the required set, which is denoted as the ark? As a criterion of proximity to introduce the notion of sets of overlapping sets.
Match Sets
Let s1 [i] - number of units in a set of Inf [i], and s0 [i] - the number of zeros in the same set. Accordingly, we denote as s1ar [i] the number of units in an arbitrary ar [i] the set Inf [i], and the number of zeros in the ar [i] to denote the same set as s0ar [i]. Then the convergence of sov [i] the set of ar [i] on the set of desired ark will be determined by the expression:
sov [i] = s1ar [i] / s1 [i] - s0ar [i] / s0 [i], (2)
ie sov value is defined as the difference in the relative numbers of ones and zeros in the set of ar [i] to the original field Inf [i].
If the set contains all of the unit and not a single zero, the convergence is difficult to notice, is 1.
By contrast, if the set does not contain a single unit, and contains all zeros, the convergence is equal to -1, ie sov values range from -1 to 1.
Note that this concept can be used to determine not only the overlap between an arbitrary set of source and field Inf [i], but also between any two sets in the field Inf [i].
The essence of the method
Final Pole information field is divided into at least m = log (base 2) n pairs vzaimoneperesekayuschihsya sets. We introduce the alphabet of m pairs of letters that corresponds to this partitioning.
This script can be expanded introduction of new characters that correspond to an arbitrary set
at the Pole. Introduced to the symbols of union and intersection of sets, brackets. Based on the alphabet, a Boolean formula, to provide specific information Inf [i] on the field Pole, through the multi-procedure as follows.
The first step is selected formula (letter), corresponding to one set. The second step is the formula representing the intersection or union of two sets, the third - three, etc.
The criterion for the selection formula is a convergence of sets, the value of which reflects the closeness of two sets, and which is defined as the difference between the number of ones and zeros in inozhestve formed in the set Inf [i].
What this gives
Here are some considerations.
Language of second tier. First of all, it shows that, in addition to the usual binary code, the information can be presented more complex language, I would call it the language of the second level, namely the language of Boolean formulas.
Artificial Intelligence. This method is based on multiple interpretations of a Boolean algebra. As is known, one interpretation of Boolean algebra is the algebra of logic. There is a high probability that mental processes derived in accordance with the laws of logic. Of course, it is possible to simulate the logical operation on the basis of number of processors, as was done with the advent of computers, but a logical and natural, in my opinion, to carry out such operations with the help of logical devices created using the algebra of logic and process information provided by Boolean formulas.
At the time, I participated in the design of automatic devices for missile technology, that's when I became interested in the minimization of Boolean functions and, indeed, the proposed method here has been developed as a means of minimizing the number of logical devices. But with the advent of programmable high-speed digital machines universal interest in the creation of individual devices has fallen, all tasks have been dealt with on-board digital computers (BTSVM). But can you can create a logical machine to the universal language of Boolean formulas.
Meaning redundancy information. I would like to draw attention to another feature of the method. Step-by-step procedure is the method allows for the formation of sets to get rough, inaccurate information. In information theory, there is the concept of redundancy in the meaning that to understand the meaning of information is often not required absolutely accurate information. We will not go into the theory of the matter, but in a step-by-step procedure, it is possible at each step to evaluate the sufficiency or insufficiency of information for a particular task, for example, raspoznovaniya images. This method would be classified as information. In the following examples, it will be shown.
The structural redundancy of information. The compression of information. The above opportunity is not able to send all information through semantic redundancy. But there is a structural redundancy, which can be understood as the number of data elements (units) and a relationship between the individual elements of information communication, ie regularities of their distribution in the information field when this field decomposition in subsets. In fact, this boils down to the length of the formula for this information. From the number and relative position of units on the field Inf [i], as well as from the decomposition of the original Pole, dependent formula for the length of the message.
A single formula in the memory. In principle, all information as soon as may shrink if every formula to add memory, changing with the current formula in the memory means Boolean algebra.
Relation to existing computers
In principle, this method is proposed as the basis for building a universal logical machine.
But perhaps it can be applied to existing computers, for example, data compression, if
develop a program to convert the information provided by a binary code, the Boolean formula.
However, it is clear that the effect of such a transformation can be obtained only when large amounts of information. In accordance with the formula (1) the number of letters of the alphabet Alf is growing much more slowly than output field M (the number of elements) and, consequently, increasing the likelihood that the length of the formula would be less than the capacity of the field, ie compression occurs.
You can also develop a program of addition (disjunction) of formulas, but to my mind, mathematical apparatus, guarantees a minimum formula, derived from association, does not exist yet.
In principle, it is possible to develop a program to sample some of the formulas with the use of the operation of multiplication (conjunction) of formulas.
In any case, it will have to deal with for verification of the ideas presented here, if anyone is interested in them.
Examples and comments
Example 1.
Consider the construction of a Boolean formula for the information communication Inf [1] Figure 3. The number of units in the set Inf [1] is equal to 9, ie s1 [1] = 9, while the number of zeros s0 [1] = 55. Is not difficult to determine what the greatest overlap with the two sets y1 and y2, as they are s1 (y1) = s1 (y2) = 9 and s0 (y1) = s0 (y2) = 23, respectively, and by the formula (2)
sov (y1) = sov (y2) = 9 / 9 - 23/55 = 0.58
Therefore, we choose one of them, for example, y1, and then the first formula for F [0] is only one letter k (Table 1):
F1 [0] = k;
Formula F [0] already has some information. If you implement the reverse conversion, you get the information box, as shown in Fig.4. This field already has some semantic information about the object in Figure 3, for example, that if the object to understand some of the figure, it is located on the left. Besides,
11110000 s1 (y1) / s1 [1] = 1, ie All units are located in y1, and so many-y1 can be excluded
11110000 from the further process of constructing a formula, reducing the procedure.
11110000
11110000
11110000
11110000
11110000
11110000
Fig.4
In a second step, we find the formula of the two letters. Is not difficult to determine what would be the biggest match of the intersection of the sets y1y2, ie a formula
F1 [1] = kl; (Fig. 5) sov (y1y2) = 1 - 7 / 55 = 0.87
The third
F1 [2] = klz; (Fig.6) sov (y1y2-y3) = 8 / 9 - 0 / 55 = 0.89
furthermore
F1 [3] = kl (z + h) (Fig.7) sov (y1y2 (-y3 | | x1)) = 9 / 9 - 3 / 55 = 0.94
F1 [4] = kl (z + hi) (Fig.8) sov (y1y2 (-y3 | | x1x2)) = 9 / 9 - 1 / 55 = 0.98
F1 [5] = kl (z + hij) (Fig.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
Fig.5 Fig.6 Fig.7 Fig.8
According to figures 5 - 8 can be traced as the information is gradually becoming more accurate.
Two examples of more complex, in terms of our decomposition, the image
Example 2.
00011100 00001100
00100010 00000000
01000010 00000000
00000100 00000000
00001000 00000000
00010000 00000000
00100000 00000000
01111110 11111111
Fig.9 Fig.10
The formula for the image Fig. 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)),
but one of the first steps of a much more simple formula
vuw + hijxl
image which is shown in Fig.10, and shows that this formula already has some meaning
information.
Example 3
F3 = (vuw + hij) (x + y + z) (k + l + m) + xl (mj (i + h) + izw) + vy (wkz + umx) (Fig. 11)
01111110 11111111
00000100 00001100
00001000 00001100
00010000 00001100
00001000 00001100
00000100 00001100
00000010 00001100
01111110 11111111
Fig.11 Fig. 12
In this example, too, at one of the first steps is the formula
xl + vuw + hij (Fig. 12),
t.e.razlichiya for images of all three examples are obvious from the very first steps.
The request to the experts for the minimization of Boolean functions.
Try to reduce (reduce the number of letters) presented in the formula. Send results.
|
Science 
