Замкнутость и полнота.

Р₂ – множество всех БФ. R – какие-нибудь функции из множества Р₂. можно выразить любую функцию из Р₂, используя только функции системы R. Система R называется полной в Р₂, если любая функция из Р₂ может быть реализована над системой R. Чтобы узнать, будет ли система полной, существует критерий полноты: пусть система функций R ={f1,f2,…} – полная и пусть задана система функций S={g1,g2,…}. Если каждую функцию системы R можно выразить через функции системы S, то система S- полная. С понятием полноты часто связано понятие замкнутости. Замыканием системы R называется множество булевых функций, которые можно реализовать над системой R. Очевидно, что если R полная система, то замыкание совпадает с Р₂. [R]= Р₂.

Реализация функций многочленом Жегалкина.

R={1,ху,ху}- полная, поэтому любую БФ можно реализовать над этой системой. Полученная при этом форма называется многочленом Жегалкина. Многочленом Жегалкина называется представлении функции в виде суммы по модулю 2, конъюнкции переменных и, быть может, 1. f(x,y)=α₁xyα₂xα₃yα₄. α_i находится методом неопределенных коэффициентов, т.е. зная табличное задание функции и подставляя различные наборы в многочлен Жегалкина, получим систему для определения α_i. f(0,0)=0, => x=0 и у=0 => α₄=0. Более простой алгоритм: 1)выписываем через интервал значения ф-и, 2)будем складывать соседние члены по модулю 2 и записывать ниже, 3) и т.д., 4) в таблице отмечаем те строки, кот-е соответ-ют единицам, стоящим на левой стороне треугольника, 5) в каждой отмеченной строке таблицы записываем конъюн-ю переменных, кот-е в этих строках равны 1 (если все переменные равны 0, то ставим на место конъюнкции ставим 1), 6) полученные конъюнкции объединяем знаком .

Важнейшие замкнутые классы.

В теории булевых функций особую роль играют 5 замкнутых классов. Пусть имеем систему R БФ, назовем эту систему функционально замкнутым классом, если вместе с функциями системы R он содержит все булевы функции, полученные суперпозицией функций системы R (т.е. как угодно сложную функцию, полученную из функций системы R).

1) класс Т₀={ f(x_n)| f(0)=0} – множество функций, которые на нулевом наборе равны 0. 2) класс Т₁={ f(x_n)| f(1)=1}. 3) класс S (класс самодвойственных функций). S={ f(x_n)| f=f*}, где f*- двойственная функция. 4) класс монотонных функций M={ f(x_n)| (α1…αn) (1…n)} (если набор α_i предшествует набору _i ). Если функция не принадлежит к классам Т0 и Т1, то она не может быть монотонна. 5) класс линейных функций L={ f(x_n)| α₁x1α₂x2…α_nx_nα_n+1x_n+1…=f }, где αi={0,1}. Теорема о функциональной полноте: чтобы система R была полной в Р₂, необходимо и достаточно, чтобы для каждого класса T₀,Т₁,S,M,L нашлась бы функция из система R, не принадлежащая этому классу.

Функции Пирса и Шеффера.

Реализация таблично-заданной функции через эти функции.

Рассмотрим свойства, которыми обладают эти функции: 1) они подчиняются коммутативному закону: xy=yx; x/y=y/x; 2) эти функции не подчиняются сочетательному закону: x(yz)≠(xy) z; x/(y/z)≠(x/y)/z, 3) законы де Моргана: not(xy)=x/y; not(x/y)=xy; 4) действие с нулем: x0=x; x/0=1; 5) действие с единицей: x¯1=0; x/1=`x; 6) связь с отрицанием: `x=x¯x; x¯`x=0; `x=x/x; x/`x=1; 7) связь с конъюнкцией (дизъюнкцией): xy=not(xy)=(x¯y)¯(x¯y); xy=not(not(xy)) =not(`x`y)= `x¯`y=(x¯x)¯(y¯y); xy=not(x¯y)= `x/`y=(x/x)/(y/y); xy=not(not(xy))=not(x/y)=(x/y)/(x/y). По аналогии с двуместными функциями можно вводить n-местные функции, т.е. x1¯x2¯x3¯…¯xn= not(x1x2x3…xn); x1/x2/x3/…/xn=not(x1x2x3…xn). n- местные функции обладают всеми свойствами двуместных, но поскольку сочетательный закон не справедлив, то x/y/z≠x/(y/z).