It follows from here that the function is decomposable, if and only if it is decomposable if only at one of triads.
Let's estimate the probability of decomposability of a random Boolean function f(x) of n variables. Consider some triad u/v, having put for example u = (a, b) and v = (c), and some arbitrary coefficient (a, b, c) of function f(x) Shannon decomposition by variables of set w = x \ (u v).
Assertion 6. The number of different values of the coefficients of the Shannon decomposition of an arbitrary Boolean function (a, b, c) by variables a and b does not exceed two, if the coefficients and of the 0 decomposition of function by c obey to the condition: = ¬ or at any rate one of the coefficients and 0 1 0 represents constant 0 or 1.
It follows from this condition Assertion 7. Among 256 different Boolean functions (a, b, c) there are 74 functions, for which the number of different values of coefficients of Shannon decomposition by variables a and b does not exceed two.
Let's designate through the share of such functions ( = 74/256).
Considering the above assertions and taking into account, that in any triad |w| = n - 3 and, therefore, the number of coefficients of the function f(x) Shannon decomposition by w is equal to 2n-3, we shall formulate XII-th International Conference "Knowledge - Dialogue - Solution" Assertion 8. At equiprobable sampling of function f(x) from the set of all Boolean functions of n variables the probability of the function f(x) decomposability is bounded above by the value n - C (n – 2).
nIt is important to note, that this value fast tends to zero with growth of n. For example, at n = 6, 12, 18, 24 it receives accordingly values 0.003, 10-135, 10-8827, 10-565200.
It is obvious from this that decomposability of arbitrary Boolean functions is rather improbable. Therefore, the task of decomposition has practical sense only for such a function, which, as it must be known a priori, is decomposable, and it is necessary only to find the appropriate composition. The task in this setting is considered below.
Search for Tracks of an Appropriate Partition Let's assume, that function f(x) is known, obtained as a result of the composition g(h(u, w), w, v) of two random Boolean functions g and h on a given, also random, weak partition u/v of the set of arguments x. It is required to detect this composition by the analysis of function f(x). This problem can be reduced mainly to finding the appropriate partition u/v.
The elementary way of finding this partition consists in exhaustive search of all nontrivial weak partitions on the set of arguments x (such, that k > 1 and m > 0) and checking the function f(x) for the decomposability on everyone of these partitions. However such a way is rather time-consuming, what is evident from the following assertion.
Assertion 9. The number of all nontrivial weak partitions on the set of n arguments equals 3n – 2n+1 – n2n-1 + n + 1.
This estimate is obtained by deleting from the set of all three-block partitions (their number equals 3n) such ones, which do not obey to the condition “k > 1 and m > 0”.
For example, at n = 6, 12, 18, 24 this number receives accordingly following values: 416; 498,686; 384,536,924;
Analyzing such big number of partitions one by one is practically impossible. Search for appropriate partition u/v can be accelerated by preliminary random looking for some track of partition u/v, i. e. some partition u*/v* submitting to u/v, after which the latter could be found by corresponding expansion of sets u* and v*.
Assertion 10. The number of partitions submitting to partition u/v, is equal to 2k+m. So the random search for partition u/v can be accelerated in 2k+m times.
Let's assume, that during the search q partitions are selected by random and analyzed, until a track of u/v is found.. Suppose, that each appropriate partition submits to the required partition u/v (another case will be analyzed a little later). At this supposition the following assertion is fair.
Assertion 11. The expectation M(q) of the value q is equal approximately to 3n / 2k+m.
For example, at n = 6, 12, 18, 24 expectation M(q) receives accordingly values 11.4, 130, 1478, 16834, if k = m = n/2 (in that case the formula is simplified to (3/2)n ), and values 45; 2,076; 94,577; 4,309,504, if k = m = n/3.
Nevertheless, expectation M(q) remains rather big, and that is why more efficient method is suggested, which is looking for tracks between the simplest weak partitions (i.e. triads), as their number is much less. For example, at the same values n = 6, 12, 18, 24 the total number of triads according to the assertion 3 receives values 60, 660, 2448, 6072.
Assertion 12. The number of triads submitting to partition u/v, is equal to C m.
kThe next assertion follows from here.
Assertion 13. When looking track between triads the expectation M(q) is equal to C (n – 2) / C m.
n2 kThat is too far less, compared with preceding methods. For example, on the same series of values n = 6, 12, 18, 24 the expectation M(q) receives accordingly values 30, 27.5, 27.2, 27.1, if k = m = n/3 and values 6.7, 7.3, 7.6, 7.7, if k = m = n/2. That testifies the essential reducing of the number of checked triads by looking for an appropriate one as well as weak dependence of the run-time on the number of variables, what is very important.
Let's remark in this connection, that if k = m = n/t, then the ratio representing the value M(q) can be approximated by constant t 3, for example, by constant 27, when t = 3, and constant 8, when t = 2.
214 Mathematical Foundations of AI False Tracks and Side Solutions Let's remark, that not any appropriate triad submits to the required partition, what is illustrated by results of a conducted experiment, with parameters n = 6, k = 3, m = 3. During this experiment there were generated the random partition u/v = (a, d, e) / (b, c, f) on the set of variables x = (a, b, c, d, e, f) and a couple of random Boolean functions h(u) and g(v). Then the composition g(h(u), v) was constructed and the corresponding Boolean function f(x) obtained, after which all triads on the set x were checked and appropriate ones were selected between them. The discovered appropriate triads are marked by 1s in the following table of triads: for example, in the first row the triads bd/a, be/a, cd/a, de/a and df/a are marked. It appears that from 35 appropriate triads only 9 submit to partition u/v - they are marked by the bold font. The remaining 26 triads represent tracks of some side solutions, and that is why they are called false triads below.
a a a a a b b b b c c c d d e b c d e f c d e f d e f e f f a...... 1 1. 1.. 1 1.
b.. 1 1..... 1.. 1 1.
c.. 1 1.. 1..... 1 1.
d 1 1. 1 1 1. 1 1. 1 1.. e 1. 1... 1.. 1... 1.
f.. 1 1.. 1.. 1.. 1..
However, with growth of the number of variables n the quota of false triads promptly diminishes.
Let's estimate the probability of violation of the supposition “any appropriate triad submits to partition u/v“ in the regarded situation of checking function f(x) for satisfying the condition of decomposability at the given partition u/v and at a random sampling of functions g and h in the composition g(h(u, w), w, v).
Each of three units of a current triad can be selected from one of the sets u, v or w. Therefore, there are 33 = situations, which can symbolically be presented as uu/u, uu/v, uu/w, uv/u, uv/v, uv/w, uw/u, uw/v, uw/w, vu/u, vu/v, vu/w, vv/u, vv/v, vv/w, vw/u, vw/v, vw/w, wu/u, wu/v, wu/w, wv/u, wv/v, wv/w, ww/u, ww/v, ww/w. Only in one of them (namely in uu/v) the triad submits to partition u/v, and among remaining ones the maximum probability the considered supposition gains in situation uu/u.
Assertion 14. The probability that a random triad in situation uu/u will appear to be appropriate is equal to n - m -.
For example, if n = 12 or n = 18, the probability receives accordingly values 2.010-3, 1.410-5 at m = n/3 and values 2.410-2, 5.810-4 at m = n/2.
In remaining situations (excepting uu/v) this probability is no more. It follows from here, that in practical situations (when n exceeds 10) any appropriate triad, most likely, submits to the required partition, therefore, we can relay on Assertion 11 for estimating the time needed to find a true track.
This conclusion is confirmed by results of two series of computer experiments, during which 10 random compositions for each considered set of parameters n, k, m were generated and any appearance of a false triad was registered. In the first series, where 150 experiments were carried out at 15 sets (6, 2, 2), (7, 3, 2), (8, 3, 3), …, (20, 7, 7), the false triads have appeared only at n = 6 and n = 7. In the second series (on 15 sets (6, 3, 3), (7, 4, 3), (8, 4, 4), …, (20, 10, 10)) the false triads were met at n = 6, 7, 8, 9, 10. At n = 10 only one such triad on experiments has appeared.
It follows from here, that for finding required partition at n 10 it is enough to expand properly sets u and v, which constitute the detected appropriate triad.
XII-th International Conference "Knowledge - Dialogue - Solution" Meanwhile, when n 10 and a good solution does exist (with k > 2 and m > 1), false tracks can be eliminated by using the following procedure of initial expansion. One by one we test variables from set x, not coming in the triad, until discover such one, which inclusion into set u* results in a new (expanded) appropriate value of partition u*/v*. If such a variable is not found, we eliminate that triad as false and look for another appropriate triad. When we find such variable, we try similarly to expand set v*. If the appropriate element misses, we again eliminate the triad and look for another one. If both checks lead to the positive result, the regarded triad is recognized as a true track and is accepted for the next expansion.
Let's return to reviewing the former example of the set of appropriate triads. Some of its elements are rejected by this procedure because they cannot be expanded by addition of a new element into set u*. Some other elements safely passed the first trial but not sustained the second one (when trying to expand set v*), so they are rejected also. In such a way all 26 false tracks are rejected.
Heuristic Search Algorithm Taking into account the explained reasons, we shall offer the following heuristic algorithm of detection of a good (with k > 2 and m > 1) partition u/v, at which the considered function f(x) is decomposable.
A. We consider a sequence of triads selected by random. As soon as a current triad happens to be appropriate, we apply the described above procedure of elimination of false tracks between appropriate triads. In result we find a perspective appropriate triad and regard it as the initial value of variable partition u*/v*.
B. We consider successively all elements of set x \ (u*/v*). Regarding the current element, we include it into set u*. If the obtained by that extended partition u*/v* appears not to be appropriate, the element is deleted from u* and put into v*. If the extended partition is not appropriate now, the element is deleted from v*.
C. Obtained after exhaustive search of all variables the partition u*/v* is accepted as the solution. Adduced above estimations allow to affirm, that with a high probability it will coincide with the required partition u/v.
In case of large number of variables (ten and more) the algorithm can be simplified by excluding the procedure of elimination of false tracks, because the probability of side solutions becomes negligibly small.
In the case, when a complete partition u/v does exist, at which the function f (x) can be decomposed, the search of this partition can be essentially speeded up by looking only for the set v, as set u can be obtained as the complement of set v up to set x.
The set v can be obtained by way of expansion of set v* in the found appropriate triad by fast iterative algorithm, which includes the current variable x into set v, if i S (T S ( S T)) = 0, xi xi u where S is the operator of symmetrization a Boolean function by EXOR-operation, known as differential xi operator, and T = S f+ = S ( f(x) f ).
v v uIn case of weak partition, when w, the redundant check of variables from set x\v for possibility of inclusion into set u will be carried out.
Results of Experiments The offered heuristic algorithm was programmed in C++ (by I. Vasilkova) and tested on computer (Pentium IV, 2.8 GHz). In a series of experiments the parameters n, k, m were fixed, a random partition u/v on the set x and functions g, h were generated, then function f(x) was calculated. After that the above described algorithm was fulfilled, which found partition u/v for the function f(x), the number q of triads scanned by search for tracks was ascertained, and the total time t (in seconds) spent during search for the partition was measured. The obtained results are represented in the following table, which right part corresponds to splitting of the set of arguments x in three parts u, w and v, whenever possible the same size, and left part - in two: u and v.
It should be noted that the table begins with n = 14, because t 0.00, if n 14.
216 Mathematical Foundations of AI n k/m q t k/m q t 14 7/7 3 0.00 5/5 39 0.15 8/7 2 0.00 5/5 78 0.16 8/8 1 0.00 6/5 18 0.17 9/8 11 0.02 6/6 34 0.18 9/9 4 0.02 6/6 42 0.19 10/9 3 0.03 7/6 39 0.20 10/10 9 0.11 7/7 3 0.21 11/10 1 0.11 7/7 3 0.22 11/11 3 0.48 8/7 6 2.23 12/11 9 2.17 8/8 16 7.24 12/12 3 2.48 8/8 26 18.25 13/12 4 5.61 9/8 19 33.26 13/13 4 11.64 9/9 3 52.27 14/13 19 60.13 9/9 36 187.28 14/14 19 1280.67 10/9 3 1585.As can be seen from the table, the regarded task of Boolean function decomposition is solved in less than one minute, when the number of arguments does not exceed 26. The amount of memory for representation of Boolean function f(x) grows quickly, reaching 228 = 268 435 456 bits when n = 28. This value is critical for the given experiment because of the restrictions on the used operation memory, and that leads to an essential decrease of the calculation speed.
Conclusion A new heuristic algorithm for Boolean function f(x) decomposition g(h(u, w), w, v) is developed, which recognizes the weak partition u/v on the set of arguments x by finding first some track of it in the form of a triad, and using then this track for restoring the partition u/v as a whole. As computer experiments show, the algorithm is very efficient.
Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.