Математика \ Математика

Дифференциал и интеграл булевой функции, страница 16

Доказано,                                                                                m

что интеграл логической функции f(x1,x2,..., xn) = Ú fi(x1,x2,..., xn)

i=1

включает следующие функции от  n+1 переменных:

m

{      Ú   fi(x1,x2,..., xn) Ú fj(x1,x2,..., xn)& xn+1  (j = 1¸ m);

i=1 (i ¹j )

m                                                                  _

Ú   fi(x1,x2,..., xn) Ú  fj(x1,x2,..., xn)& xn+1  (j = 1¸ m)}

i=1 (i ¹j )

В данной работе определяется полное множество логических функций интеграла от f(x1,x2,..., xn) по переменной xn+1 для операции дизъюнкция.

q                                      q                                     q

            Пусть xn+1= 0 , если q = 0; xn+1= 1 , если q = 1; xn+1= xn+1 , если q = 2;

q      _

xn+1= xn+1 , если q = 3.

            Теорема 1.

Полное       множество      логических    функций интеграла логической

m

функции f(x1,x2,..., xn) =Ú fi(x1,x2,..., xn) для операции дизъюнкция

i=1

по переменной  xn+1  включает следующие логические функции:

m                                            m                                  p

ò f(x1,x2,..., xn)dxn+1 = ò Ú fi(x1,x2,..., xn) dxn+1 = {Ú fi(x1,x2,..., xn)& xn+1} ,

Ú                                   i=1                                     i=1

где p = {0,1,2,3} (все возможные различные комбинации).

Доказательство.

m                                  p

 Найдем дифференциал логической функции Ú fi(x1,x2,..., xn)& xn+1  по

i=1

переменной xn+1 для операции дизъюнкция:

                                             m                                   p

¶   Ú fi(x1,x2,..., xn)& xn+1  

i=1                                               

_____________________

¶хn+1                              Ú

p                                      p                                          p

При p=0 и xn+1 =0 - xn+1 = 0; p=0 и xn+1 =1 - xn+1 = 0; p=1 и xn+1 =0 - xn+1 = 1;   

p                                      p                                          p

p=1 и xn+1 =1 - xn+1 = 1; p=2 и xn+1 =0 - xn+1 = 0; p=2 и xn+1 =1 - xn+1 = 1;   

p                                      p              p

p=3 и xn+1 =0 - xn+1 = 1; p=3 и xn+1 =1 - xn+1 = 0.

p

Отсюда следует, что fi(x1,x2,..., xn)& xn+1 = 0 при {p=0, xn+1 =(0,1)},

{p=2, xn+1 = 0},{p=3, xn+1 = 1};

p

fi(x1,x2,..., xn)& xn+1 = fi(x1,x2,..., xn) при {p=1, xn+1 =(0,1)}, {p=2, xn+1 = 1},

{p=3, xn+1 = 0}.

Следовательно,

                       m                                   p

¶   Ú fi(x1,x2,..., xn)& xn+1             m

i=1                                        =  Ú fi(x1,x2,..., xn)  = f(x1,x2,..., xn).

_____________________           i=1

¶хn+1                           Ú

Далее докажем, что не существует логических функций от n+1 переменных

m                                  p

{Ú fi(x1,x2,..., xn)& xn+1} ,

i=1

дифференциал от которых равен логической функции f(x1,x2,..., xn) =

m

=  Ú fi(x1,x2,..., xn) для операции дизъюнкция.

i=1

Допустим существует функция Fj(x1,x2,..., xn,xn+1), не входящая в множество

m                                  p

{Ú fi(x1,x2,..., xn)& xn+1} .

i=1

      Отсюда следует, что

p1         p2                 pn

Fj(x1,x2,..., xn,xn+1) = x1   &  x2    & ... & xn  = f(x1,x2,..., xn)

Данная функция включена в заданное множество. Теорема доказана.

Попытка реализовать нечто подобное была предпринята в последнем программном продукте крупнейшего производителя программного обеспечения, корпорации Майкрософт — Windows XP. Но в связи с допущенными ошибками в программном коде и слабой проработкой степеней его защиты, эта операционная система явилась еще одним ярким примером активной и в большинстве случаев успешной деятельности компьютерных пиратов. В настоящее время Windows ХР пополнила длинный список незаконно распространяемых и используемых программных продуктов.

Скачать файл