Asymptotic properties of the set of solutions for the distorted systems of equations.pdf Пусть П = {0,1,... , k - 1}, Fk(n) = {/ : П^ ^ П} -множество всех n-местных функций k-значной логики от переменных x1,..., xn, n, k Е N. Рассмотрим систему из T Е N уравнений /t(x) = 0, /t Е Ffc(n), t =1,...,T. (1) Через S обозначим множество решений системы (1). Каждой функции / Е F& (n) сопоставим множества А0(/) и А1(/) тех значений аргумента, на которых она принимает значение нуль и отлична от нуля соответственно. Обозначим а0(/) = |А0(/)|, а1(/) = |А1(/)|. Для каждой функции / Е Fk(n) и целого числа 0 ^ d ^ а0(/) рассмотрим множество функций B(/,d) = {g Е Ffc(n) : |Ac(/) U A1(g)| + |Л(/) U A(g)| = d}, таких, что при g Е B(/, d) число значений аргументов, в которых одна из функций / и g принимает значение нуль, а другая отлична от нуля, равно d. На множествах B(/1, d),..., B(/t, d) зададим равномерные вероятностные распределения, в соответствии с которыми выберем случайно и независимо функции /1,... , /т. Рассмотрим систему случайных уравнений /t(xb...,x„) = 0, /t Е B(/t,d), t =1,...,T. (2) Множество её решений обозначим через S. Рассматривается задача нахождения связи между множествами S и S решений систем уравнений (1) и (2) при выполнении следующих асимптотических условий: при T, n ^ то сами функции /1,... , /т меняются так, что 1) число решений системы (1) имеет конечный предел, т.е. |S| ^ У Е N; 2) число значений аргументов, на которых функции ft, t = 1, . . . , T, принимают значение нуль, неограниченно возрастает, т. е. a0(/t) ^ то, t = 1,..., T. В [1] данная задача рассматривается для случая булевых уравнений, при этом предполагается, что каждая функция системы (1) является уравновешенной, т. е. принимает каждое из значений нуль и единица ровно на 2n-1 значениях аргумента. В данной работе рассматривается обобщение на случай произвольных функций k-значной логики с учётом асимптотических условий 1 и 2, при этом уравновешенности функций не требуется. Обозначим «min = min{a0(/i),... , «0/)}, «max = max{«0(fi),. . . ,«0(/т)}. Теорема 1. Пусть n,T ^ го, |S| ^ Е G N, T/amin ^ 0. Тогда: i) d d £ Nn - «0(/tК 1) если параметр d меняется так, что d -, . Л7--> го, то t=i «0 (/t)Nn P{S П S = 0} ^ 1; 2) d d f Nn - gp(/t) t (0 ) Td < 2) если параметр d меняется так, что d > - - ^ к G (0, го) и - < с, t=i «0(/t)Nn «min с = const > 0, то распределение случайной величины |S П S| сходится к Bi(E,e-K) - биномиальному распределению с параметрами Е и е-к; 3) d d £ Nn - «0(/t) ---^ 0 и amax < -, то t=i «0 (/t)Nn 2 P{S С £} ^ 1.

Скачать электронную версию публикации