В начало

Булевы полиномы

Работа с булевыми полиномами, описанная ниже, собрана в два файла:
booleanf.h - заголовочный файл
booleanf.cpp - реализация.

Для ее работы не требуются никакие дополнительные библиотеки. Из стандартных include-файлов подключается только stdlib.h. Динамическое выделение памяти также не используется. Даже при конвертировании объектов в строку (методы toString классов SC и BP) используется всегда один и тот же массив, выделяемый статически. С одной стороны, это создает определенные неудобства для пользователя, с другой - уменьшает риск возникновения ``утечек памяти``, (подробнее - см. далее).

В заголовочном файле описан тип кортежа: 

typedef unsigned char corteg;
а также два класса: 
class SC{..} // Set of Corteges (множество кортежей)
и 
class BP{..} // Boolean polynoms (булевы полиномы)

Кортеж (corteg)

Определение. Кортежем будем называть цепочку из битов фиксированной длины. Ее длину будем считать фиксированной и обозначать nVar.

Настройка пакета на работу с булевыми многочленами от данного количества переменных осуществляется с помощью константы nVar, определенной в файле booleanf.h: 

#define nVar 8   // the number of boolean variables
Таким образом, количество булевых переменных задается один раз и до конца работы программы. Это, конечно же, является недостатком реализации но, с другой стороны, заметно упрощает работу с системой. В реальных задачах, где приходилось использовать булевы полиномы, количество исходных переменных всегда оставалось одним и тем же, поэтому указанный недостаток не являлся существенным.

Обычно в наших примерах nVar будет равно 8, то есть кортеж является байтом, но не исключаются и другие варианты. Кортеж определяется беззнаковым числом, лежащим в пределах от 0 до 2nVar-1. Поэтому при nVar ≤ 8 кортеж представлен байтом (unsigned char), при nVar ≤ 16 - беззнаковым коротким числом (unsigned short), при nVar ≤ 32 - беззнаковым целым(unsigned). Никаких особых операций над кортежами, помимо обычных арифметических и битовых операций над беззнаковыми числами мы пока не определяем.

Множество кортежей, класс SC

Следующий класс представляем множество кортежей. Фактически, это просто массив из 2nVar битов. Его же можно рассматривать как функцию на множестве всех кортежей со значениями {0,1}. Основные методы класса: 
 void set0();        // this = 0
 void ins(corteg a); // добавить к множеству кортеж a
 void join (SC &s);  // добавить к this множество s
 void inters(SC &s); // this := this пересечение с множеством s
 void xor (SC &s);   // this := this XOR s
 bool get(corteg a); // входит ли кортеж a в множество
 bool isBitSymmetric( int k );  // симметрично ли множество
                     // относительно бита k
 int  weight();      // количество элементов в множестве char
 *toString();

Они достаточно очевидны и не требуют особых комментариев, кроме последнего (toString). Чтобы не сталкиваться с проблемами выделения и освобождения памяти, эта функция строит ответ всегда в одной и той же статически созданной строке и именно её возвращает в качестве результата. Это удобно, так как пользователю не надо заботиться ни о выделении, ни об освобождении памяти. С другой стороны, это приводит к невозможности одновременного использования двух и более объектов в одном выражении, типа 

 printf( "s=%s; t=%s\n", s.toString(), t.toString() );

Булевы полиномы, класс BP

Булевы полиномы - это суммы некоторого количества мономов. Каждый моном определяется списком переменных, в него входящих, то есть некоторым кортежем. Поэтому как множество, булев полином - то же самое, что и множество кортежей. Различаются они набором операций и методов.

Замечание. Каждому кортежу b длины N соответствует булев моном M(b) от переменных (x0, ... , xnVar-1), например 

        M(10010011) = x0 * x1 * x4 * x7
Значение монома M(b) на кортеже a равно 1, если b&a==b. В противном случае это значение равно 0.

Основные методы класса: 

 void set0();             // обнулить полином
 void set1(corteg a);     // коэффициент при мономе a := 1
 void add1(corteg a);     // прибавить моном a к полиному
 void add(BP &b);         // this += b
 void mult(BP &b, BP &c); // this = b*c
 bool get(corteg a);      // значение полинома в точке a
 void values(SC &r);      // r:= значение полинома во всех точках
 void Roots (SC &r);      // r:= множество корней полинома
 void OneUnit(corteg a);  // строим полином равный 1 в точке a
                          // и 0 в остальных
 void OneRoot(corteg a);  // строим полином равный 0 в точке a
                          // и 1 в остальных
 void or(BP &b, BP &c);   // this = b OR c
 void givenRoots(SC &r);  // строим полином с данным набором корней
 void givenUnits(SC &r);  // строим полином с данным набором единиц
                          // (т.е. не корней)
 char *toString();

Использование пакета

Единственная требуемая настройка пакета - выбор количества булевых переменных. Она осуществляется с помощью константы nVar, определенной в файле booleanf.h: 

#define nVar 8   // the number of boolean variables
Таким образом, количество булевых переменных задается один раз и до конца работы программы.

В зависимости от величины nVar тип corteg имеет разные определения: 

#if nVar<= 8
typedef unsigned char corteg;   // <= BYTE
#elif nVar<= 16 
typedef unsigned short corteg;  // <= __in16
#elif nVar<= 32
typedef unsigned corteg;        // <= __in32
#elif nVar<= 64
typedef unsigned __int64 corteg;// <= __in64
#else
#error nVar too large
#endif

Таким образом, константа nVar не должна принимать значения, большие 64. На самом деле, при nVar > 32 объекты типов SC и BP потребуют слишком много памяти и работа с ними может быть затруднена или вообще невозможна. Даже при nVar=32 следует очень осторожно подходить созданию объектов из этих классов. 

#include "BP.h"
...
	SC s, t;
	s.ins(7);
	s.ins(17);
	s.ins(200);
	printf( "s=%s>\n", s.toString() );

Будет выведено на экран множество, состоящее из трех элементов: {7,17,200}. 

#include "BP.h"
...
	BP f;
	SC r;
	f.add1(2);f.add1(5); 
	printf( "f=<%s>\n", f.toString() );
	f.Roots(r);
	printf( "r=<%s>\n", r.toString() );
	f.givenRoots(r);
	printf( "F=<%s>\n", f.toString() );


free counters