Decision Making statements that allows to estimate a measure of refutation statements of experts (a measure of refutation above at formula of the first order language with smaller number of elements satisfying it) and to specify their probabilities (an average share probabilities realizations for formulas with variables). It allows solve problems of the best reconciliation of expert statements, constructions of decision functions in pattern recognition, creation of bases of knowledge and expert systems [1].

A number of natural metrics on probabilities knowledge of experts is offered with use of suitable class of models (with metrics) some theory and modifications symmetric difference, by analogue, par example [4] for logical Lbov’s the predicat for unique model. Properties of these metrics, connected to them measures of refutation of formulas (distance from the formula up to class of equivalence of identically true formula) and probability are established. From the point of view of importance of the information presented by an expert, it is natural to assume that a measure of refutation of the formula (nonempty predicate) the above, than it is les measure of elements satisfying it (i.e. a measure determined on subsets, set by predicate formulas).

We introduce the measure of refutation similarly to a case of formulas without probabilities. We call R P x = вер P x, ( ) ( ) ( ( ) ) the measure of refutation of formula P(x), where 1 is an identical true predicate, that is, x = x. All stated for predicates (and Lbov’s predicate aussi without probability) fairly and for formulas of the first order language with probabilities.

The distance between the formulas of Sentence Logic is entered in [1], properties of the entered distance are given and proved in the same place. Ways of introduction of distance between the formulas of the first order language are offered in [2]. Measures of refutation and probabilities of formulas are entered and their properties are formulated in [3]. The distance between the formulas of Sentence Logic with probabilities is entered in [3,5].

In the given work the way of introduction of distances between probabilities statements of experts represented as the formulas of the first order language theory T with probabilities is offered.

Distance between Statements of Experts Represented as the Formulas of the First Order Language with Probabilities in Theory p Let experts speak about probabilities of predicates on the product.

Dx j j=Then the given by expert probability is interpreted as follows: "the knowledge" Bli =< Pli (x1,..., xp), pli > means, that the predicate Pli (x1,..., xp ) is true on nP = pli trains of length p in model Mi, where i n l k n = Dx - measure of model.

j j=Let's find distance between predicates Pl and Pj. For this purpose all over again we shall calculate distance i (Bli, Bi ) between probabilities interpretations Bli =< Pli (x), pli > and Bi =< Pji (x), pi > of predicates j j j Pl and Pj in each model Mi. Distances are calculated between predicates of identical district and from the same variables plus measure protjaga p.e. [4], and without in stable theory.

Then interpreting the probabilities given by experts the described above way we receive that the predicate Pli (x) is true on nP trains in model Mi and the predicate Pji (x) is true on nP trains in model Mi theory i i l j T. We shall note that is not known on what trains each predicate true and number ( or mera) of trains on which these predicates are simultaneously true.

XII-th International Conference "Knowledge - Dialogue - Solution" We shall consider the following task. Let the predicate Pli (x) is true on nP trains in model Mi and the i l predicate Pji (x) is true on nP trains in model Mi and ki - number of trains on which these predicates are i j simultaneously true. It is required to calculate distance between Bli =< Pli (x), pli > and Bi =< Pji (x), pi >.

j j Distances arising in further we shall designate through k (Bli, Bi ), where, ki = t,t +1,…,min(nP, nP ), i i i j l j t = max(0, nP + nP - n) hereinafter.

i i l j Distance k (Bli, Bi ) we shall define as a modifies (as ask above) symmetric difference, i.e.

i j k (Bli, Bi ) = (nP + nP - 2ki ), (1) ii i j l j n for every one ki = t,t +1,…, min(nP,nP ). All properties of distances formulated in [1] are fair for i i l j k (Bli, Bi ). Let's offer some ways of calculation distance i (Bli, Bi ) between probabilities interpretations i j j Bli =< Pli (x), pli > and Bi =< Pji (x), pi > of predicates Pl and Pj in each model Mi theory T. If the j j number ki is not known (the number of trains on which these predicates are simultaneously true in model Mi ) and if there are no preferences for value ki (preference can be stated by experts) it is possible to act as follows.

We shall assume, that all values for number ki are equally probability. Then distance between probabilities interpretations Bli =< Pli (x), pli > and Bi =< Pji (x), pi > of predicates Pl and Pj in model Mi we shall j j define as average of distances k (Bli, Bi ) on all values ki, i.e.

i j min(n,n ) Pli Pi j k (Bli, Bi ) i j (2) ki =t (Bli, Bi ) =.

j min(nP, nP ) +1- t i i l j For this distance all properties of distances formulated in [1] also are executed.

If by experts it is stated what value for ki is more preferable in quality i (Bli, Bi ) it undertakes k (Bli, Bi ), i j j i.e.

(Bli, Bi ) = k (Bli, Bi ).

(3) i j j In the offered formulas (1) – (3) of distances the kind of formulas between which the distance is calculated is not taken into account. Therefore it is natural to offer distance by which takes into account a kind of formulas.

s Applying the model approach [1-3] to elements of set {Mi}i=1 we shall find probabilities PM (Pji ), PM (Pji ) i i ([3]) and distance M (Pli, Pji ) in model Mi ([2]), then we shall calculate probability i i ([3]) and we shall find k0 = [PM (Pli Pji )n] PM (Pli Pji ) = (PM (Pli ) + PM (Pji ) - (Pli, Pji )) i i i i i - the number of trains on which predicates are simultaneously true. Having k0 (calculated on models), it is possible to reduce number of possible values for ki. Three cases here are possible:

i i i i 1) if t < k0 < min(nP,nP ), then ki = k0 -1, k0, k0 +1;

i i l j i i i i i i 2) if k0 = t or k0 = min(nP,nP ), then, for example, ki = k0, k0 +1; or ki = k0 -1, k0;

i i l j i i 3) if k0 < t or k0 > min(nP,nP ), then ki = t or ki = min(nP, nP ).

i i i i l j l j Decision Making And already to these values for ki apples offered above formulas (1) - (3) of distances. As required probably some expansion of number of values for ki.

The offered ways it is possible to calculate distance between the following statements: Bli =< Pli (x), pli > - the information received from one expert, and Blj =< Pl j (x), plj > - the information received from other expert.

Thus we have calculated distance i(Bli, Bi ) between probabilities interpretations Bli =< Pli (x), pli > and j Bi =< Pji (x), pi > of predicates Pl and Pj and degree elongate in each model Mi theory T. Then as j j distance вер (Pl, Pj ) between predicates Pl and Pj we shall take size s вер (Pl, Pj ) = i (Bli, Bi ).

j s i=For all properties of distance formulated in ([5]) are carried out for вер (Pl, Pj ).

Acknowledgements This work was financially supported by the Russian Foundation for Basic Research, project no. 04-01-00858a.

[2] Vikent'ev A.A., Koreneva L.N. “Setting the metric and measures of informativity in predicate formulas corresponding to the statements of experts about hierarchical objects”, Pattern Recognition and Image Analysis, V. 10, N. 3, (2000), 303--308.

[4] G.S.Lbov, M.K.Gerasimov. Determining the distance between logical statements in forecasting problems. In: Artificial Intelligence, 2’2004 [in Russian]. Institute of Artificial Intelligence, Ukraine.

[5] Викентьев А.А., Лбов Г.С., Коренева Л.Н. “Расстояние между вероятностными высказываниями экспертов”, Искусственный интеллект, 2’2002, НАН Украины, 58-64.

[6] Keisler G., Chang C. Model theory. M.: Mir, 1977.

Author’s Information Alexander Vikent’ev – Institute of Mathematics, SB RAS, Acad. Koptyuga St., bl.4, Novosibirsk, Russia;

e-mail: vikent@math.nsc.ru Mathematical Foundations of AI DECOMPOSITION OF BOOLEAN FUNCTIONS BY LOOKING FOR TRACKS OF A GOOD SOLUTION Arkadij Zakrevskij Abstract: The problem of two-block Boolean function decomposition, generally non-disjunctive, is regarded in case when a good solution does exist. A new heuristic combinatorial algorithm is offered, optimized on speed.

The problem is reduced mainly to finding an appropriate weak partition on the set of arguments of the considered Boolean function, which should be decomposable at this partition. At first the randomized search for "tracks" of the appropriate partition is fulfilled. The recognized tracks are represented by some "triads" - the simplest weak partitions corresponding to non-trivial decompositions. After that the whole sought-for partition is restored from the discovered track. The results of computer experiments testify the high practical efficiency of the algorithm.

Introduction The well-known problem of Boolean functions decomposition consists in possible replacement of the considered function by an equivalent composition of several functions with smaller number of variables. Different sorts of the decomposition were offered, including sequential two-block decomposition, called simple decomposition, disjunctive or non-disjunctive.

As a result of the disjunctive decomposition the initial Boolean function f(x) is substituted by a composition g(h(u), v) at the partition u/v on the set of arguments x = (x, x, …, x ): u v = x, u v =. In this case the 1 2 n partition u/v is named strong) [1, 2]. The more general case is represented by non-disjunctive decomposition, when function f(x) is substituted by the composition g(h(u, w), w, v) at the weak partition u/v, where x = u w v, u w = u v = w v = [3, 4]. In both cases the conditions |u| > 1 and |v| > 0 must be satisfied, otherwise the decomposition is trivial – it exists always.

Solving the following two tasks are laying in the basis of decomposition methods.

The task 1. For a given function f(x) and partition u/v (strong either weak) to find out, whether f(x) is decomposable at u/v, i. e. whether there exists a non-trivial composition (g(h(u), v) or g(h(u, w), w, v)) equivalent to function f (and, maybe, to find functions g and h).

If such a composition does exist, we shall term partition u/v as appropriate.

The task 2. For a given function f(x) to find an appropriate partition.

Solving Task The task of checking a Boolean function f(x) for decomposability at a given partition u/v on the set of arguments x was regarded in [1-3], where a necessary and sufficient condition for that was found, which could be formulated as in the following assertion:

Assertion 1. Let f (u, v) be the coefficients of the Shannon disjunctive decomposition of Boolean function f(x) by i variables of set w. Then function f(x) is decomposable at partition u/v, if and only if the coefficients of the similar decomposition of each function f (u, v) by variables from set u accept not more than two different values.

i 212 Mathematical Foundations of AI Checking Boolean functions for satisfying this condition was laid into the base of many known methods offered for solving task 1.

A new algorithm for solving the same problem is developed, based on representation of considered functions by Boolean vectors and using efficient component-wise operations above them. It is checking a Boolean function for satisfying a certain condition formulated in terms of symmetry operations introduced in [4] and defined as follows:

S f(x) = f (x, …, x, …, x ) f (x, …, ¬x, …, x ) is disjunctive symmetrization of Boolean function f(x) by xi 1 i n 1 i n argument x, i S f(x) = S ( S … (S f(x))…) is disjunctive symmetrization of Boolean function f(x) over the given subset u u1 u2 uk u = (u, u, …,u ) of set x.

1 2 k In result of applying operator S to Boolean space of variables from set x, where function f(x) is defined, any u interval with inner variables taken from set u, which has if only one 1, is filled up with 1s completely.

Operator S f(x) is defined in the same way.

v The suggested algorithm checks function f(x) for satisfying the condition formulated in Assertion 1. It takes the initial coefficient f of Shannon decomposition of function f(x) by set u, then, by using operation f+(x) = f(x) f, u0 umodifies function f(x) in such a way that all coefficients coinciding with f are changed for 0, and finally finds out if uall the remaining coefficients are equal to each other.

In other words, the algorithm is working in accordance with the following assertion.

Assertion 2. A Boolean function f(x) is decomposable at partition u/v, if and only if (f+(x) S f+(x)) S f+(x) = 0.

u v So, checking a Boolean function for decomposability at a given partition is reduced to several operations over Boolean vectors.

The second task is more difficult. A heuristic combinatorial algorithm is offered below to solve it, optimized on speed.

Relations on the Set of Partitions. Triads Consider two partitions u/v and u*/v*, such that u* u and v* v. Let's speak, that partition u*/v* submits to partition u/v. The following assertions are fair by that.

Assertion 3. If the function f(x) is decomposable at partition u/v, it is decomposable as well at partition u*/v*.

Hence, if the function f(x) is not decomposable at partition u*/v*, it is not decomposable also at partition u/v.

Let's assume |u| = k and |v| = m. Partition with k = 2 and m = 1 we shall term as a triad. It is the simplest of partitions, at which a nontrivial decomposition can be defined.

n( n - 1)( n - 2) Assertion 4. The number of triads is equal to C (n – 2) =.

nAssertion 5. The Boolean function f(x) is not decomposable, if it is not decomposable at any of triads.

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.