30.9.2 Access to the original POLYBORI interface

The re-implementation POLYBORI's native wrapper is available to the user too:

sage: from polybori import *
sage: declare_ring([Block('x',2),Block('y',3)],globals())
Boolean PolynomialRing in x(0), x(1), y(0), y(1), y(2)
sage: r
Boolean PolynomialRing in x(0), x(1), y(0), y(1), y(2)

sage: [Variable(i) for i in xrange(r.ngens())]
[x(0), x(1), y(0), y(1), y(2)]

For details on this interface see:

http://polybori.sourceforge.net/doc/tutorial/tutorial.html.

Note that due to this duality of this interface some functions do not obey Sage's naming convention. For instance, f.zerosIn should be called f.zeros_in by Sage's standards. However, POLYBORI expects the function f.zerosIn.

Also, the interface provides functions for compatibility with Sage accepting convenient Sage datatypes which are slower than their native POLYBORI counterparts. For instance, sets of points can be represented as tuples of tuples (Sage) or as BooleSets (POLYBORI) and naturally the second option is faster.

REFERENCES: [BD07] Michael Brickenstein, Alexander Dreyer; 'POLYBORI: A Groebner basis framework for Boolean polynomials'; http://www.itwm.fraunhofer.de/zentral/download/berichte/bericht122.pdf

Module-level Functions

VariableBlock( )

add_up_polynomials( )

append_ring_block( )

change_ordering( )

contained_vars( )

free_m4ri( )

get_cring( )

Return the currently active global ring, this is only relevant for the native POLYBORI interface.

sage: from polybori import declare_ring, get_cring, Block
sage: R = declare_ring([Block('x',2),Block('y',3)],globals())
sage: Q = get_cring(); Q
Boolean PolynomialRing in x(0), x(1), y(0), y(1), y(2)
sage: R is Q
True

get_order_code( )

get_var_mapping( )

Return a variable mapping between variables of other and ring. When other is a parent object, the mapping defines images for all variables of other. If it is an element, only variables occuring in other are mapped.

Raises NameError if no such mapping is possible.

sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: R.<z,y> = QQ[]
sage: sage.rings.polynomial.pbori.get_var_mapping(P,R)
[z, y]
sage: sage.rings.polynomial.pbori.get_var_mapping(P, z^2)
[z, None]

sage: R.<z,x> = BooleanPolynomialRing(2)
sage: sage.rings.polynomial.pbori.get_var_mapping(P,R)
[z, x]
sage: sage.rings.polynomial.pbori.get_var_mapping(P, x^2)
[None, x]

have_degree_order( )

if_then_else( )

The opposite of navigating down a ZDD using navigators is to construct new ZDDs in the same way, namely giving their else- and then-branch as well as the index value of the new node.

Input:

root: - a variable
a: - the if branch, a BooleSet or a BoolePolynomial
b: - the else branch, a BooleSet or a BoolePolynomial

sage: from polybori import if_then_else
sage: B = BooleanPolynomialRing(6,'x')
sage: x0,x1,x2,x3,x4,x5 = B.gens()
sage: f0 = x2*x3+x3
sage: f1 = x4
sage: if_then_else(x1, f0, f1)
{{x1,x2,x3}, {x1,x3}, {x4}}

sage: if_then_else(x1.lm().index(),f0,f1)
{{x1,x2,x3}, {x1,x3}, {x4}}

sage: if_then_else(x5, f0, f1)
Traceback (most recent call last):
...
IndexError: index of root must be less than the values of roots of the
branches.

interpolate( )

interpolate_smallest_lex( )

ll_red_nf( )

ll_red_nf_noredsb( )

map_every_x_to_x_plus_one( )

mod_mon_set( )

mod_var_set( )

mult_fact_sim_C( )

nf3( )

parallel_reduce( )

recursively_insert( )

red_tail( )

set_cring( )

Set the currently active global ring, this is only relevant for the native POLYBORI interface.

sage: from polybori import *
sage: declare_ring([Block('x',2),Block('y',3)],globals())
Boolean PolynomialRing in x(0), x(1), y(0), y(1), y(2)
sage: R = get_cring(); R
Boolean PolynomialRing in x(0), x(1), y(0), y(1), y(2)

sage: declare_ring([Block('x',2),Block('y',2)],globals())
Boolean PolynomialRing in x(0), x(1), y(0), y(1)

sage: get_cring()
Boolean PolynomialRing in x(0), x(1), y(0), y(1)

sage: set_cring(R)
sage: get_cring()
Boolean PolynomialRing in x(0), x(1), y(0), y(1), y(2)

set_variable_name( )

top_index( )

Return the highest index in the parameter s.

Input:

s: - BooleSet, BooleMonomial, BoolePolynomial

sage: B.<x,y,z> = BooleanPolynomialRing(3)
sage: from polybori import top_index
sage: top_index(x.lm())
0
sage: top_index(y*z)
1
sage: top_index(x + 1)
0

unpickle_BooleanPolynomial( )

Unpickle boolean polynomials

sage: T = TermOrder('deglex',2)+TermOrder('deglex',2) 
sage: P.<a,b,c,d> = BooleanPolynomialRing(4,order=T) 
sage: loads(dumps(a+b)) == a+b # indirect doctest
True

unpickle_BooleanPolynomialRing( )

Unpickle boolean polynomial rings.

sage: T = TermOrder('deglex',2)+TermOrder('deglex',2) 
sage: P.<a,b,c,d> = BooleanPolynomialRing(4,order=T) 
sage: loads(dumps(P)) == P  # indirect doctest
True

zeros( )

Class: BooleanMonomial

class BooleanMonomial

Functions: deg, $\,$ degree, $\,$ divisors, $\,$ index, $\,$ iterindex, $\,$ multiples, $\,$ reducibleBy, $\,$ set, $\,$ stableHash, $\,$ variables

deg( )

Return degree of this monomial.

sage: from polybori import BooleanMonomialMonoid
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: M = BooleanMonomialMonoid(P)
sage: M(x*y).deg()
2

sage: M(x*x*y*z).deg()
3

degree( )

Return degree of this monomial.

sage: from polybori import BooleanMonomialMonoid
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: M = BooleanMonomialMonoid(P)
sage: M(x*y).degree()
2

divisors( )

Return a set of boolean monomials with all divisors of this monomial.

sage: B.<x,y,z> = BooleanPolynomialRing(3)
sage: f = x*y
sage: m = f.lm()
sage: m.divisors()
{{x,y}, {x}, {y}, {}}

index( )

Return the variable index of the first variable in this monomial.

sage: B.<x,y,z> = BooleanPolynomialRing(3)
sage: f = x*y
sage: m = f.lm()
sage: m.index()
0

iterindex( )

Return an iterator over the indicies of the variables in self.

sage: from polybori import BooleanMonomialMonoid
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: M = BooleanMonomialMonoid(P)
sage: list(M(x*z).iterindex())
[0, 2]

multiples( )

Return a set of boolean monomials with all multiples of this monomial up the bound rhs.

Input:

rhs: - a boolean monomial

sage: B.<x,y,z> = BooleanPolynomialRing(3)
sage: f = x
sage: m = f.lm()
sage: g = x*y*z
sage: n = g.lm()
sage: m.multiples(n)
{{x,y,z}, {x,y}, {x,z}, {x}}
sage: n.multiples(m)
{{x,y,z}}

NOTE: The returned set always contains self even if the bound rhs is smaller than self.

reducibleBy( )

Return True if self is reducible by rhs.

Input:

rhs: - a boolean monomial

sage: B.<x,y,z> = BooleanPolynomialRing(3)
sage: f = x*y
sage: m = f.lm()
sage: m.reducibleBy((x*y).lm())
True
sage: m.reducibleBy((x*z).lm())
False

set( )

Return a boolean set of variables in this monomials.

sage: B.<x,y,z> = BooleanPolynomialRing(3)
sage: f = x*y
sage: m = f.lm()
sage: m.set()
{{x,y}}

variables( )

Return a list of the variables in this monomial.

sage: from polybori import BooleanMonomialMonoid
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: M = BooleanMonomialMonoid(P)
sage: M(x*z).variables() # indirect doctest
[x, z]

Special Functions: __add__, $\,$ __call__, $\,$ __eq__, $\,$ __ge__, $\,$ __gt__, $\,$ __init__, $\,$ __iter__, $\,$ __le__, $\,$ __len__, $\,$ __lt__, $\,$ __ne__, $\,$ __radd__, $\,$ _eval, $\,$ _repr_

__add__( )

Addition operator. Returns a boolean polynomial.

sage: from polybori import BooleanMonomialMonoid
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: M = BooleanMonomialMonoid(P)
sage: x = M(x); xy = M(x*y)
sage: x + xy
x*y + x

sage: x+0
x
sage: 0+x   # todo: not implemented
x

sage: x+1
x + 1
sage: 1 + x     # todo: not implemented
x + 1

__call__( )

Evaluate this monomial.

sage: B.<x,y,z> = BooleanPolynomialRing(3)
sage: f = x*y
sage: m = f.lm()
sage: m(B(0),B(1))
0
sage: m(x=B(1))
y

__iter__( )

Return an iterator over the variables in this monomial.

sage: from polybori import BooleanMonomialMonoid
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: M = BooleanMonomialMonoid(P)
sage: list(M(x*z)) # indirect doctest
[x, z]

_eval( )

Evaluate this monomial.

Input:

d: - dictionary with integer indicies

sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: m = P._monom_monoid(x*y)
sage: m._eval({0:y,1:z})
y*z

_repr_( )

Return a string representing self.

sage: P.<x,y> = BooleanPolynomialRing(2)
sage: M = sage.rings.polynomial.pbori.BooleanMonomialMonoid(P)
sage: M(x*y) # indirect doctest
x*y

sage: R.<t,u> = BooleanPolynomialRing(2)
sage: M(x*y)
x*y

Class: BooleanMonomialIterator

class BooleanMonomialIterator: An iterator over the variable indices of a monomial.

Functions: next

next( ): x.next() -> the next value, or raise StopIteration

Special Functions: __iter__, $\,$ __next__

__iter__( )

sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: f = x*y + z + 1
sage: for m in f: list(m.iterindex())# indirect doctest
[0, 1]
[2]
[]

__next__( )

sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: f = x*y + z + 1
sage: m = f.lm()
sage: m.iterindex().next()
0

Class: BooleanMonomialMonoid

class BooleanMonomialMonoid

Functions: gen, $\,$ gens, $\,$ ngens

gen( )

Return the i-th generator of self.

Input:

i: - an integer

sage: from polybori import BooleanMonomialMonoid
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: M = BooleanMonomialMonoid(P)
sage: M.gen(0)
x
sage: M.gen(2)
z

sage: P = BooleanPolynomialRing(1000, 'x')
sage: M = BooleanMonomialMonoid(P)
sage: M.gen(50)
x50

gens( )

Return the tuple of generators of this monoid.

sage: from polybori import BooleanMonomialMonoid
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: M = BooleanMonomialMonoid(P)
sage: M.gens()
(x, y, z)

ngens( )

Returns the number of variables in this monoid.

sage: from polybori import BooleanMonomialMonoid
sage: P = BooleanPolynomialRing(100, 'x')
sage: M = BooleanMonomialMonoid(P)
sage: M.ngens()
100

Special Functions: __call__, $\,$ __init__, $\,$ _coerce_impl, $\,$ _repr_

__call__( )

Convert elements of other objects to elements of this monoid.

Input:

other: - element to convert, - if None a BooleanMonomial representing 1 is returned - only BooleanPolynomials with the same parent ring as self which have a single monomial is converted

sage: from polybori import BooleanMonomialMonoid
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: M = BooleanMonomialMonoid(P)
sage: x_monom = M(x); x_monom
x

sage: M(x*y)
x*y

sage: M(x+y)
Traceback (most recent call last):
...
TypeError: cannot convert to BooleanMonomialMonoid

Convert elements of self.

sage: M(x_monom)
x

Convert from other BooleanPolynomialRings.

sage: R.<z,x> = BooleanPolynomialRing(2)
sage: t = M(z); t
z
sage: t.parent() is M
True

Convert BooleanMonomials over other BooleanPolynomialRings.

sage: N = BooleanMonomialMonoid(R)
sage: t = M(N(x*z)); t
x*z
sage: t.parent() is M
True

__init__( )

Construct a boolean monomial monoid given a boolean polynomial ring.

This object provides a parent for boolean monomials.

Input:

polring: - the polynomial ring our monomials lie in

sage: from polybori import BooleanMonomialMonoid
sage: P.<x,y> = BooleanPolynomialRing(2)
sage: M = BooleanMonomialMonoid(P)
sage: M
MonomialMonoid of Boolean PolynomialRing in x, y

sage: M.gens()
(x, y)
sage: type(M.gen(0))
<type 'sage.rings.polynomial.pbori.BooleanMonomial'>

_coerce_impl( )

Canonical conversion of elements from other objects to this monoid.

Coerce elements of self.

sage: from polybori import BooleanMonomialMonoid
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: M = BooleanMonomialMonoid(P)
sage: x_monom = M(x); x_monom
x
sage: M._coerce_(x_monom) # indirect doctest
x

Coerce elements from BooleanMonomialMonoids where the generators of self include the generators of the other monoid.

sage: from polybori import BooleanMonomialMonoid
sage: R.<z,y> = BooleanPolynomialRing(2)
sage: N = BooleanMonomialMonoid(R)
sage: m = M._coerce_(N(y*z)); m
y*z
sage: m.parent() is M
True

TESTS:

sage: from polybori import BooleanMonomialMonoid
sage: R.<t,y> = BooleanPolynomialRing(2)
sage: N = BooleanMonomialMonoid(R)
sage: m = M._coerce_(N(y)); m
Traceback (most recent call last):
...
ValueError: cannot coerce monomial y to MonomialMonoid of Boolean
PolynomialRing in x, y, z: name t not defined

sage: from polybori import BooleanMonomialMonoid
sage: R.<t,x,y,z> = BooleanPolynomialRing(4)
sage: N = BooleanMonomialMonoid(R)
sage: m = M._coerce_(N(x*y*z)); m
Traceback (most recent call last):
...
TypeError: coercion from <type
'sage.rings.polynomial.pbori.BooleanMonomial'> to MonomialMonoid of Boolean
PolynomialRing in x, y, z not implemented

_repr_( )

sage: from polybori import BooleanMonomialMonoid
sage: P.<x,y> = BooleanPolynomialRing(2)
sage: M = BooleanMonomialMonoid(P)
sage: M # indirect doctest
MonomialMonoid of Boolean PolynomialRing in x, y

Class: BooleanMonomialVariableIterator

class BooleanMonomialVariableIterator

Functions: next

next( ): x.next() -> the next value, or raise StopIteration

Special Functions: __iter__, $\,$ __next__

__iter__( )

Return an iterator over the variables of a boolean monomial.

sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: f = x*y + z + 1
sage: for m in f: list(m)# indirect doctest
[x, y]
[z]
[]

__next__( )

sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: f = x*y + z + 1
sage: m = f.lm()
sage: iter(m).next()
x

Class: BooleanPolynomial

class BooleanPolynomial

Functions: constant, $\,$ deg, $\,$ degree, $\,$ elength, $\,$ firstTerm, $\,$ gradedPart, $\,$ hasConstantPart, $\,$ is_constant, $\,$ is_equal, $\,$ is_homogeneous, $\,$ is_one, $\,$ is_unit, $\,$ is_zero, $\,$ isOne, $\,$ isZero, $\,$ lead, $\,$ lexLead, $\,$ lexLmDeg, $\,$ lm, $\,$ lm_degree, $\,$ lmDeg, $\,$ lmDivisors, $\,$ lt, $\,$ mapEveryXToXPlusOne, $\,$ monomial_coefficient, $\,$ monomials, $\,$ navigation, $\,$ nNodes, $\,$ nvariables, $\,$ nVars, $\,$ reduce, $\,$ reducibleBy, $\,$ ring, $\,$ set, $\,$ spoly, $\,$ stableHash, $\,$ subs, $\,$ total_degree, $\,$ totalDegree, $\,$ variables, $\,$ varsAsMonomial, $\,$ zerosIn

constant( )

Return True if this element is constant.

sage: B.<x,y,z> = BooleanPolynomialRing(3)
sage: x.constant()
False

sage: B(1).constant()
True

deg( )

Return the degree of self. This is usually equivalent to the total degree except for weighted term orderings which are not implemented yet.

sage: P.<x,y> = BooleanPolynomialRing(2)
sage: (x+y).degree()
1

sage: P(1).degree()
0

sage: (x*y + x + y + 1).degree()
2

degree( )

Return the total degree of self.

sage: P.<x,y> = BooleanPolynomialRing(2)
sage: (x+y).degree()
1

sage: P(1).degree()
0

sage: (x*y + x + y + 1).degree()
2

elength( )

Return elimination length as used in the SlimGB algorithm.

sage: P.<x,y> = BooleanPolynomialRing(2)
sage: x.elength()
1
sage: f = x*y + 1
sage: f.elength()
2

REFERENCES: Michael Brickenstein; SlimGB: Groebner Bases with Slim Polynomials http://www.mathematik.uni-kl.de/~zca/Reports_on_ca/35/paper_35_full.ps.gz

firstTerm( )

Return the first term with respect to the lexicographical term ordering.

sage: B.<a,b,z> = BooleanPolynomialRing(3,order='lex')
sage: f = b*z + a + 1
sage: f.firstTerm()
a

gradedPart( )

Return graded part of this boolean polynomial of degree deg.

Input:

deg: - a degree

sage: B.<a,b,c,d> = BooleanPolynomialRing(4)
sage: f = a*b*c + c*d + a*b + 1
sage: f.gradedPart(2)
a*b + c*d

sage: f.gradedPart(0)
1

TESTS:

sage: f.gradedPart(-1)
0

hasConstantPart( )

Return True if this boolean polynomial has a constant part, i.e. if is a term.

sage: B.<a,b,c,d> = BooleanPolynomialRing(4)
sage: f = a*b*c + c*d + a*b + 1
sage: f.hasConstantPart()
True

sage: f = a*b*c + c*d + a*b
sage: f.hasConstantPart()
False

is_constant( )

Check if self is constant.

sage: P.<x,y> = BooleanPolynomialRing(2)
sage: P(1).is_constant()
True

sage: P(0).is_constant()
True

sage: x.is_constant()
False

sage: (x*y).is_constant()
False

is_equal( )

sage: B.<a,b,z> = BooleanPolynomialRing(3)
sage: f = a*z + b + 1
sage: g = b + z
sage: f.is_equal(g)
False

sage: f.is_equal( (f + 1) - 1 )
True

is_homogeneous( )

Return True if this element is a homogeneous polynomial.

sage: P.<x, y> = BooleanPolynomialRing()
sage: (x+y).is_homogeneous()
True 
sage: P(0).is_homogeneous() 
True 
sage: (x+1).is_homogeneous()
False

is_one( )

Check if self is 1.

sage: P.<x,y> = BooleanPolynomialRing(2)
sage: P(1).is_one()
True

sage: P.one_element().is_one()
True

sage: x.is_one()
False

sage: P(0).is_one()
False

is_unit( )

Check if self is invertible in the parent ring.

Note that this condition is equivalent to being 1 for boolean polynomials.

sage: P.<x,y> = BooleanPolynomialRing(2)
sage: P.one_element().is_unit()
True

sage: x.is_unit()
False

is_zero( )

Check if self is zero.

sage: P.<x,y> = BooleanPolynomialRing(2)
sage: P(0).is_zero()
True

sage: x.is_zero()
False

sage: P(1).is_zero()
False

isOne( )

Return True if this element is one.

sage: B.<x,y,z> = BooleanPolynomialRing(3)
sage: x.isOne()
False
sage: B(0).isOne()
False
sage: B(1).isOne()
True

isZero( )

Return True if this element is zero.

sage: B.<x,y,z> = BooleanPolynomialRing(3)
sage: x.isZero()
False
sage: B(0).isZero()
True
sage: B(1).isZero()
False

lead( )

Return the leading monomial of boolean polynomial, with respect to to the order of parent ring.

sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: (x+y+y*z).lead()
x

sage: P.<x,y,z> = BooleanPolynomialRing(3, order='deglex')
sage: (x+y+y*z).lead()
y*z

lexLead( )

Return the leading monomial of boolean polynomial, with respect to the lexicographical term ordering.

sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: (x+y+y*z).lexLead()
x

sage: P.<x,y,z> = BooleanPolynomialRing(3, order='deglex')
sage: (x+y+y*z).lexLead()
x

lexLmDeg( )

Return degree of leading monomial with respect to the lexicographical ordering.

sage: B.<x,y,z> = BooleanPolynomialRing(3,order='lex')
sage: f = x + y*z
sage: f
x + y*z
sage: f.lexLmDeg()
1

sage: B.<x,y,z> = BooleanPolynomialRing(3,order='deglex')
sage: f = x + y*z
sage: f
y*z + x
sage: f.lexLmDeg()
1

lm( )

Return the leading monomial of this boolean polynomial, with respect to the order of parent ring.

sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: (x+y+y*z).lm()
x

sage: P.<x,y,z> = BooleanPolynomialRing(3, order='deglex')
sage: (x+y+y*z).lm()
y*z

lm_degree( )

Returns the total degree of the leading monomial of self.

sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: p = x + y*z
sage: p.lm_degree()
1

sage: P.<x,y,z> = BooleanPolynomialRing(3,order='deglex')
sage: p = x + y*z
sage: p.lm_degree()
2

sage: P(0).lm_degree()
0

lmDeg( )

Return the degree of the leading monomial with respect to the lexicographical orderings.

sage: B.<x,y,z> = BooleanPolynomialRing(3,order='lex')
sage: f = x + y*z
sage: f
x + y*z
sage: f.lmDeg()
1

sage: B.<x,y,z> = BooleanPolynomialRing(3,order='deglex')
sage: f = x + y*z
sage: f
y*z + x
sage: f.lmDeg()
2

lmDivisors( )

Return a BooleSet of all divisors of the leading monomial.

sage: B.<a,b,z> = BooleanPolynomialRing(3)
sage: f = a*b + z + 1
sage: f.lmDivisors()
{{a,b}, {a}, {b}, {}}

lt( )

Return the leading term of this boolean polynomial, with respect to the order of the parent ring.

Note that for boolean polynomials this is equivalent to returning leading monomials.

sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: (x+y+y*z).lt()
x

sage: P.<x,y,z> = BooleanPolynomialRing(3, order='deglex')
sage: (x+y+y*z).lt()
y*z

mapEveryXToXPlusOne( )

Map every variable x_i in this polynomial to .

sage: B.<a,b,z> = BooleanPolynomialRing(3)
sage: f = a*b + z + 1; f
a*b + z + 1
sage: f.mapEveryXToXPlusOne()
a*b + a + b + z + 1
sage: f(a+1,b+1,z+1)
a*b + a + b + z + 1

monomial_coefficient( )

Return the coefficient of the monomial mon in self, where mon must have the same parent as self.

Input:

mon: - a monomial

sage: P.<x,y> = BooleanPolynomialRing(2)
sage: x.monomial_coefficient(x)
1
sage: x.monomial_coefficient(y)
0
sage: R.<x,y,z,a,b,c>=BooleanPolynomialRing(6)
sage: f=(1-x)*(1+y); f
x*y + x + y + 1

sage: f.monomial_coefficient(1)
1

sage: f.monomial_coefficient(0)
0

monomials( )

Return a list of monomials appearing in self ordered largest to smallest.

sage: P.<a,b,c> = BooleanPolynomialRing(3,order='lex') 
sage: f = a + c*b 
sage: f.monomials() 
[a, b*c]

sage: P.<a,b,c> = BooleanPolynomialRing(3,order='degrevlex') 
sage: f = a + c*b 
sage: f.monomials() 
[c*b, a]

nvariables( )

Return the number of variables used to form this boolean polynomial.

sage: B.<a,b,c,d> = BooleanPolynomialRing(4)
sage: f = a*b*c + 1
sage: f.nvariables()
3

nVars( )

Return the number of variables used to form this boolean polynomial.

sage: B.<a,b,c,d> = BooleanPolynomialRing(4)
sage: f = a*b*c + 1
sage: f.nVars()
3

reduce( )

Return the normal form of self w.r.t. I, i.e. return the remainder of self with respect to the polynomials in I. If the polynomial set/list I is not a Groebner basis the result is not canonical.

Input:

I: - a list/set of polynomials in self.parent(). If I is an ideal, the generators are used.

sage: B.<x0,x1,x2,x3> = BooleanPolynomialRing(4)
sage: I = B.ideal((x0 + x1 + x2 + x3, \
                   x0*x1 + x1*x2 + x0*x3 + x2*x3, \
                   x0*x1*x2 + x0*x1*x3 + x0*x2*x3 + x1*x2*x3, \
                   x0*x1*x2*x3 + 1))
sage: gb = I.groebner_basis()
sage: f,g,h,i = I.gens()
sage: f.reduce(gb)
0
sage: p = f*g + x0*h + x2*i
sage: p.reduce(gb)
0
sage: p.reduce(I)
x1*x2*x3 + x2

NOTE: If this function is called repeatedly with the same I then it is advised to use POLYBORI's GroebnerStrategy object directly, since that will be faster. See the source code of this function for details.

reducibleBy( )

Return True if this boolean polynomial is reducible by the polynomial rhs.

Input:

rhs: - a boolean polynomial

sage: B.<a,b,c,d> = BooleanPolynomialRing(4,order='degrevlex')
sage: f = (a*b + 1)*(c + 1)
sage: f.reducibleBy(d)
False
sage: f.reducibleBy(c)
True
sage: f.reducibleBy(c + 1)
True

ring( )

Return the parent of this boolean polynomial.

sage: B.<a,b,c,d> = BooleanPolynomialRing(4)
sage: a.ring() is B
True

set( )

Return a BooleSet with all monomials apprearing in this polynomial.

sage: B.<a,b,z> = BooleanPolynomialRing(3)
sage: (a*b+z+1).set()
{{a,b}, {z}, {}}

spoly( )

Return the S-Polynomial of this boolean polynomial and the other boolean polynomial rhs.

sage: B.<a,b,c,d> = BooleanPolynomialRing(4)
sage: f = a*b*c + c*d + a*b + 1
sage: g = c*d + b
sage: f.spoly(g)
a*b + a*c*d + c*d + 1

subs( )

Fixes some given variables in a given boolean polynomial and returns the changed boolean polynomials. The polynomial itself is not affected. The variable,value pairs for fixing are to be provided as dictionary of the form {variable:value} or named parameters (see examples below).

Input:

in_dict: - (optional) dict with variable:value pairs
**kwds: - names parameters

sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: f = x*y + z + y*z + 1
sage: f.subs(x=1)
y*z + y + z + 1
sage: f.subs(x=0)
y*z + z + 1

sage: f.subs(x=y)
y*z + y + z + 1

sage: f.subs({x:1},y=1)
0
sage: f.subs(y=1)
x + 1
sage: f.subs(y=1,z=1)
x + 1
sage: f.subs(z=1)
x*y + y
sage: f.subs({'x':1},y=1)
0

This method can work fully symbolic:

sage: f.subs(x=var('a'),y=var('b'),z=var('c'))
b*c + c + a*b + 1

sage: f.subs({'x':var('a'),'y':var('b'),'z':var('c')})
b*c + c + a*b + 1

total_degree( )

Return the total degree of self.

sage: P.<x,y> = BooleanPolynomialRing(2)
sage: (x+y).total_degree()
1

sage: P(1).total_degree()
0

sage: (x*y + x + y + 1).total_degree()
2

totalDegree( )

Return total degree of this boolean polynomial.

sage: B.<a,b,c,d> = BooleanPolynomialRing(4)
sage: f = a*b*c + 1
sage: f.totalDegree()
3

variables( )

Return a list of all variables appearing in self.

sage: P.<x,y,z> = BooleanPolynomialRing(3)  
sage: (x + y).variables()  
[x, y]

sage: (x*y + z).variables()  
[x, y, z]

sage: P.zero_element().variables()  
[]

sage: P.one_element().variables()  
[1]

varsAsMonomial( )

Return a boolean monomial with all the variables appearing in self.

sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: (x + y).varsAsMonomial()
x*y

sage: (x*y + z).varsAsMonomial()
x*y*z

sage: P.zero_element().varsAsMonomial()
1

sage: P.one_element().varsAsMonomial()
1

TESTS:

sage: R = BooleanPolynomialRing(1, 'y')
sage: y.varsAsMonomial()
y
sage: R
Boolean PolynomialRing in y

zerosIn( )

Return a set containing all elements of s where this boolean polynomial evaluates to zero.

If s is given as a BooleSet, then the return type is also a BooleSet. If s is a set/list/tuple of tuple this function returns a tuple of tuples.

Input:

s: - candidate points for evaluation to zero

sage: B.<a,b,c,d> = BooleanPolynomialRing(4)
sage: f = a*b + c + d + 1

Now we create a set of points:

sage: s = a*b + a*b*c + c*d + 1
sage: s = s.set(); s
{{a,b,c}, {a,b}, {c,d}, {}}

This encodes the points (1,1,1,0), (1,1,0,0), (0,0,1,1) and (0,0,0,0). But of these only (1,1,0,0) evaluates to zero.

sage: f.zerosIn(s)
{{a,b}}

sage: f.zerosIn([(1,1,1,0), (1,1,0,0), (0,0,1,1), (0,0,0,0)])
((1, 1, 0, 0),)

Special Functions: __call__, $\,$ __eq__, $\,$ __ge__, $\,$ __gt__, $\,$ __init__, $\,$ __iter__, $\,$ __le__, $\,$ __len__, $\,$ __lt__, $\,$ __ne__, $\,$ __neg__, $\,$ __pow__, $\,$ __reduce__, $\,$ __rpow__, $\,$ _latex_, $\,$ _magma_, $\,$ _repr_, $\,$ _repr_with_changed_varnames

__call__( )

Evaluate this boolean polynomials.

sage: B.<x,y,z> = BooleanPolynomialRing(3)
sage: f = x*y + z + 1
sage: f(0,1,1)
0
sage: f(z,y,x)
x + y*z + 1
sage: f(x=z)
y*z + z + 1

sage: P.<a,b,c> = PolynomialRing(QQ)
sage: f(a,b,c)
a*b + c + 1
sage: f(x=a,y=b,z=1)
a*b + 2

Evaluation of polynomials can be used fully symbolic:

sage: f(x=var('a'),y=var('b'),z=var('c'))
c + a*b + 1
sage: f(var('a'),var('b'),1)
a*b

__iter__( )

Return an iterator over the monomials of self, in the order of the parent ring.

sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: p = x + z + x*y + y*z + x*y*z
sage: list(iter(p))
[x*y*z, x*y, x, y*z, z]

sage: P.<x,y,z> = BooleanPolynomialRing(3, order='deglex')
sage: p = x + z + x*y + y*z + x*y*z
sage: list(iter(p))
[x*y*z, x*y, y*z, x, z]

sage: P.<x,y,z> = BooleanPolynomialRing(3, order='degrevlex')
sage: p = x + z + x*y + y*z + x*y*z
sage: list(iter(p))
[z*y*x, y*x, z*y, x, z]

TESTS:

sage: R = BooleanPolynomialRing(1,'y')
sage: list(iter(y))
[y]
sage: R
Boolean PolynomialRing in y

__neg__( )

Return -self.

sage: B.<a,b,z> = BooleanPolynomialRing(3)
sage: f = a*z + b + 1
sage: -f
a*z + b + 1

__reduce__( )

sage: P.<a,b> = BooleanPolynomialRing(2)
sage: loads(dumps(a)) == a
True

_latex_( )

Return a LaTeXrepresentation of this boolean polynomial.

sage: B.<a,b,z> = BooleanPolynomialRing(3)
sage: latex(a+b+a*z^2+1) # indirect doctest
a z + a + b + 1

_magma_( )

Returns the MAGMA representation of self.

sage: R.<x,y> = BooleanPolynomialRing()
sage: f = y*x + x +1
sage: f._magma_() #optional
x*y + x + 1

_repr_( )

sage: B.<a,b,z> = BooleanPolynomialRing(3)
sage: repr(a+b+z^2+1) # indirect doctest
'a + b + z + 1'

_repr_with_changed_varnames( )

Return string representing this boolean polynomial but change the variable names to varnames.

sage: B.<a,b,z> = BooleanPolynomialRing(3)
sage: a._repr_with_changed_varnames(['x','y','z'])
'x'

TESTS:

sage: a._repr_with_changed_varnames([1,'y','z'])
Traceback (most recent call last):
...
TypeError: varnames has entries with wrong type.

sage: a
a

Class: BooleanPolynomialIdeal

class BooleanPolynomialIdeal

Functions: groebner_basis, $\,$ reduce

groebner_basis( )

Return a Groebner basis of this ideal.

Input:

red_tail: - tail reductions in intermediate polynomials, this options affects mainly heuristics. The reducedness of the output polynomials can only be guaranteed by the option redsb (default: True)
minsb: - return a minimal Groebner basis (default: True)
redsb: - return a minimal Groebner basis and all tails are reduced (default: True)
deg_bound: - only compute Groebner basis up to a given degree bound (default: False)
faugere: - turn off or on the linear algebra (default: False)
linear_algebra_in_last_block: - this affects the last block of block orderings and degree orderings. If it is set to True linear algebra takes affect in this block.(default: True)
selection_size: - maximum number of polynomials for parallel reductions (default: 1000)
heuristic: - Turn off heuristic by setting heuristic=False (default: True)
lazy: - (default: True)
invert: - setting invert=True input and output get a transformation for each variable , which shouldn't effect the calculated GB, but the algorithm.
other_ordering_first: - possible values are False or an ordering code. In practice, many Boolean examples have very few solutions and a very easy Groebner basis. So, a complex walk algorithm (which cannot be implemented using the POLYBORI data structures) seems unnecessary, as such Groebner bases can be converted quite fast by the normal Buchberger algorithm from one ordering into another ordering. (default: False)
prot: - show protocol (default: False)
full_prot: - show full protocol (default: False)

sage: P.<x0, x1, x2, x3> = BooleanPolynomialRing(4)
sage: I = P.ideal(x0*x1*x2*x3 + x0*x1*x3 + x0*x1 + x0*x2 + x0)
sage: I.groebner_basis()
[x0*x1 + x0*x2 + x0, x0*x2*x3 + x0*x3]

reduce( )

Reduce an element modulo the reduced Groebner basis for this ideal. This returns 0 if and only if the element is in this ideal. In any case, this reduction is unique up to monomial orders.

sage: P = PolynomialRing(GF(2),10, 'x')
sage: B = BooleanPolynomialRing(10,'x')
sage: I = sage.rings.ideal.Cyclic(P)
sage: I = B.ideal([B(f) for f in I.gens()])
sage: gb = I.groebner_basis()
sage: I.reduce(gb[0])
0
sage: I.reduce(gb[0] + 1)
1
sage: I.reduce(gb[0]*gb[1])
0
sage: I.reduce(gb[0]*B.gen(1))
0

Special Functions: __init__

__init__( )

Construct an ideal in the boolean polynomial ring.

Input:

ring: - the ring this ideal is defined in
gens: - a list of generators
coerce: - coerce all elements to the ring ring (default: True)

sage: P.<x0, x1, x2, x3> = BooleanPolynomialRing(4)
sage: I = P.ideal(x0*x1*x2*x3 + x0*x1*x3 + x0*x1 + x0*x2 + x0)
sage: I
Ideal (x0*x1*x2*x3 + x0*x1*x3 + x0*x1 + x0*x2 + x0) of Boolean
PolynomialRing in x0, x1, x2, x3

Class: BooleanPolynomialIterator

class BooleanPolynomialIterator: Iterator over the monomials of a boolean polynomial.

Functions: next

next( ): x.next() -> the next value, or raise StopIteration

Special Functions: __iter__, $\,$ __next__

__iter__( )

sage: B.<a,b,c,d> = BooleanPolynomialRing()
sage: list(B.random_element()) # indirect doctest
[a*c, a*d, a, b*d, 1]

__next__( )

sage: B.<a,b,c,d> = BooleanPolynomialRing()
sage: it = iter(B.random_element())
sage: it.next() # indirect doctest
a*c

Class: BooleanPolynomialRing

class BooleanPolynomialRing

Functions: cover_ring, $\,$ defining_ideal, $\,$ gen, $\,$ gens, $\,$ ideal, $\,$ interpolation_polynomial, $\,$ ngens, $\,$ random_element

cover_ring( )

Return $R = \mathbf{F}_2[vars]$ if is the ordered list of variable names of this ring. also has the same term ordering as this ring.

sage: B.<x,y> = BooleanPolynomialRing(2)
sage: R = B.cover_ring(); R
Multivariate Polynomial Ring in x, y over Finite Field of size 2

sage: B.term_order() == R.term_order()
True

defining_ideal( )

Return $I = <x_i^2 + x_i> \subset R$ where $R = \mathbf{F}_2[vars]$ , the ordered list of variables/variable names of this ring and any element in .

sage: B.<x,y> = BooleanPolynomialRing(2)
sage: I = B.defining_ideal(); I
Ideal (x^2 + x, y^2 + y) of Multivariate Polynomial Ring
in x, y over Finite Field of size 2

gen( )

Returns the i-th generator of this boolean polynomial ring.

Input:

i: - an integer or a boolean monomial in one variable

sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: P.gen()
x
sage: P.gen(2)
z
sage: m = x.monomials()[0]
sage: P.gen(m)
x

TESTS:

sage: P.<x,y,z> = BooleanPolynomialRing(3, order='dp')
sage: P.gen(0)
x

gens( )

Return the tuple of variables in this ring.

sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: P.gens()
(x, y, z)

sage: P = BooleanPolynomialRing(10,'x')
sage: P.gens()
(x0, x1, x2, x3, x4, x5, x6, x7, x8, x9)

TESTS:

sage: P.<x,y,z> = BooleanPolynomialRing(3,order='degrevlex')
sage: P.gens()
(x, y, z)

ideal( )

Create an ideal in this ring.

Input:

gens: - list or tuple of generators
coerce: - bool (default: True) automatically coerce the given polynomials to this ring to form the ideal

sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: P.ideal(x+y)
Ideal (x + y) of Boolean PolynomialRing in x, y, z

sage: P.ideal(x*y, y*z)
Ideal (x*y, y*z) of Boolean PolynomialRing in x, y, z

sage: P.ideal([x+y, z])
Ideal (x + y, z) of Boolean PolynomialRing in x, y, z

interpolation_polynomial( )

Return the lexicographically minimal boolean polynomial for the given sets of points.

Given two sets of points zeros - evaluating to zero - and ones - evaluating to one -, compute the lexicographically minimal boolean polynomial satisfying these points.

Input:

zeros: - the set of interpolation points mapped to zero
ones: - the set of interpolation points mapped to one

First we create a random-ish boolean polynomial.

sage: B.<a,b,c,d,e,f> = BooleanPolynomialRing(6)
sage: f = a*b*c*e + a*d*e + a*f + b + c + e + f + 1

Now we find interpolation points mapping to zero and to one.

sage: zeros = set([(1, 0, 1, 0, 0, 0), (1, 0, 0, 0, 1, 0), \
                    (0, 0, 1, 1, 1, 1), (1, 0, 1, 1, 1, 1), \
                    (0, 0, 0, 0, 1, 0), (0, 1, 1, 1, 1, 0), \
                    (1, 1, 0, 0, 0, 1), (1, 1, 0, 1, 0, 1)])
sage: ones = set([(0, 0, 0, 0, 0, 0), (1, 0, 1, 0, 1, 0), \
                  (0, 0, 0, 1, 1, 1), (1, 0, 0, 1, 0, 1), \
                  (0, 0, 0, 0, 1, 1), (0, 1, 1, 0, 1, 1), \
                  (0, 1, 1, 1, 1, 1), (1, 1, 1, 0, 1, 0)])
sage: [f(*p) for p in zeros]
[0, 0, 0, 0, 0, 0, 0, 0]
sage: [f(*p) for p in ones]
[1, 1, 1, 1, 1, 1, 1, 1]

Finally, we find the lexicographically smallest interpolation polynomial using POLYBORI.

sage: g = B.interpolation_polynomial(zeros, ones); g
b*f + c + d*f + d + e*f + e + 1

sage: [g(*p) for p in zeros]
[0, 0, 0, 0, 0, 0, 0, 0]
sage: [g(*p) for p in ones]
[1, 1, 1, 1, 1, 1, 1, 1]

Alternatively, we can work with POLYBORI's native BooleSet's. This example is from the POLYBORI tutorial:

sage: B = BooleanPolynomialRing(4,"x0,x1,x2,x3")
sage: x = B.gen
sage: V=(x(0)+x(1)+x(2)+x(3)+1).set(); V
{{x0}, {x1}, {x2}, {x3}, {}}
sage: f=x(0)*x(1)+x(1)+x(2)+1
sage: z = f.zerosIn(V); z
{{x1}, {x2}}
sage: o = V.diff(z); o
{{x0}, {x3}, {}}
sage: B.interpolation_polynomial(z,o)
x1 + x2 + 1

ALGORITHM: Calls interpolate_smallest_lex as described in the POLYBORI tutorial.

ngens( )

Returns the number of variables in this boolean polynomial ring.

sage: P.<x,y> = BooleanPolynomialRing(2)
sage: P.ngens()
2

sage: P = BooleanPolynomialRing(1000, 'x')
sage: P.ngens()
1000

random_element( )

Return a random boolean polynomial. Generated polynomial has the given number of terms, and at most given degree.

Input:

degree: - maximum degree (default: 2)
terms: - number of terms (default: 5)
choose_degree: - choose degree of monomials randomly first, rather than monomials uniformly random
vars_set: - list of integer indicies of generators of self to use in the generated polynomial

sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: P.random_element(degree=3, terms=4)
x*y*z + x*z + y*z + z

sage: P.random_element(degree=1, terms=2)
z + 1

TESTS:

sage: P.random_element(degree=4)
Traceback (most recent call last):
...
ValueError: Given degree should be less than or equal to number of
variables (3)

sage: t = P.random_element(degree=1, terms=5)
Traceback (most recent call last):
...
ValueError: Cannot generate random polynomial with 5 terms and maximum
degree 1 using 3 variables

sage: t = P.random_element(degree=2,terms=5,vars_set=(0,1))
Traceback (most recent call last):
...
ValueError: Cannot generate random polynomial with 5 terms using 2
variables

Special Functions: __call__, $\,$ __eq__, $\,$ __ge__, $\,$ __gt__, $\,$ __init__, $\,$ __le__, $\,$ __lt__, $\,$ __ne__, $\,$ __reduce__, $\,$ _change_ordering, $\,$ _magma_, $\,$ _magma_init_, $\,$ _random_monomial_dfirst, $\,$ _random_monomial_uniform, $\,$ _random_uniform_rec, $\,$ _repr_, $\,$ _set_variable_name, $\,$ _singular_init_

__call__( )

Convert elements of other objects to this boolean polynomial ring.

sage: P.<x,y> = BooleanPolynomialRing(2)
sage: P(5)
1

sage: P(x+y)
x + y

sage: P.<x,y> = BooleanPolynomialRing(2)
sage: R = BooleanPolynomialRing(1,'y')
sage: p = R(y); p
y
sage: p.parent()
Boolean PolynomialRing in y

sage: P = BooleanPolynomialRing(2,'x,y')
sage: R.<z,x,y> = ZZ['z,x,y']
sage: t = x^2*y + 5*y^3
sage: p = P(t); p
x*y + y
sage: p.parent()
Boolean PolynomialRing in x, y

TESTS:

sage: P.<x,y> = BooleanPolynomialRing(2)
sage: R = BooleanPolynomialRing(1,'y')
sage: p = R(x+y+x*y+1)
Traceback (most recent call last):
...
ValueError: cannot convert polynomial x*y + x + y + 1 to Boolean
PolynomialRing in y: name x not defined

sage: P = BooleanPolynomialRing(2,'x,y')
sage: R.<z,x,y> = ZZ['z,x,y']
sage: t = x^2*z+5*y^3
sage: p = P(t)
Traceback (most recent call last):
...
ValueError: cannot convert polynomial z*x^2 + 5*y^3 to Boolean
PolynomialRing in x, y: name z not defined

__reduce__( )

sage: P.<a,b> = BooleanPolynomialRing(2)
sage: loads(dumps(P)) == P # indirect doctest
True

_change_ordering( )

Change the ordering of this boolean polynomial ring. Do NOT call this method, unless you know very well what you are doing.

Input:

order: - an integer (0 <= order <= 4)

sage: B.<x,y,z> = BooleanPolynomialRing(3,order='deglex')
sage: y*z > x
True

Now we call the internal method and change the ordering to 'lex':

sage: B._change_ordering(0)
sage: y*z > x
False

However, this change is not - and should not be - picked up by the public interface.

sage: B.term_order()
Degree lexicographic term order

WARNING: Do not use this method. It is provided for compatibility reasons with POLYBORI but parents are supposed to be immutable in Sage.

_magma_( )

Return a MAGMA representation of this boolean polynomial ring.

Input:

magma: - a magma instance (default: default instance)

sage: B.<x,y,z> = BooleanPolynomialRing(3)
sage: B._magma_() # optional requires magma
Affine Algebra of rank 3 over GF(2)
Lexicographical Order
Variables: x, y, z
Quotient relations:
[
x^2 + x,
y^2 + y,
z^2 + z
]

_magma_init_( )

Return a a string which when evaluated with MAGMA returns a MAGMA representaion of this boolean polynomial ring.

Input:

magma: - a magma instance (default: default instance)

sage: B.<x,y,z> = BooleanPolynomialRing(3)
sage: B._magma_() # optional requires magma, indirect doctest
Affine Algebra of rank 3 over GF(2)
Lexicographical Order
Variables: x, y, z
Quotient relations:
[
x^2 + x,
y^2 + y,
z^2 + z
]

NOTE: This method actually calls MAGMA.

_random_monomial_dfirst( )

Choose a random monomial using variables indexed in vars_set up to given degree. The degree of the monomial, , is chosen uniformly in the interval [0,degree] first, then the monomial is generated by selecting a random sample of size from vars_set.

Input:

degree: - maximum degree
vars_set: - list of variable indicies of self

sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: [P._random_monomial_dfirst(3, (0,1,2)) for _ in range(10)]
[x*y*z, x*y*z, x*y*z, y*z, x*z, z, z, y*z, x*y*z, 1]

_random_monomial_uniform( )

Choose a random monomial uniformly from set of monomials in the variables indexed by vars_set in self.

Input:

monom_counts: - list of number of monomials up to given degree
vars_set: - list of variable indicies to use in the generated monomial

sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: [P._random_monomial_uniform([1, 3, 4], (0,1)) for _ in range(10)]
[x*y, x*y, x, x, x, x*y, x, y, x*y, 1]

_random_uniform_rec( )

Recursively generate a random polynomial in in this ring, using the variables from vars_set.

Input:

degree: - maximum degree
monom_counts: - a list containing total number of monomials up to given degree
vars_set: - list of variable indicies to use in the generated polynomial
dfirst: - if True choose degree first, otherwise choose the monomial uniformly
l: - number of monomials to generate

sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: P._random_uniform_rec(2, [1, 3, 4], (0,1), True, 2)
x + y
sage: P._random_uniform_rec(2, [1, 3, 4], (0,1), True, 2)
0

_repr_( )

sage: P.<x, y> = BooleanPolynomialRing(2)
sage: P # indirect doctest
Boolean PolynomialRing in x, y

_set_variable_name( )

Set variable name of i-th variable to s.

This function is used by POLYBORI python functions.

Input:

i: - index of variable
s: - new variable name

sage: P.<x0,x1> = BooleanPolynomialRing(2)
sage: P
Boolean PolynomialRing in x0, x1

sage: P._set_variable_name(0, 't')
sage: P
Boolean PolynomialRing in t, x1

WARNING: Do not use this method. It is provided for compatibility reasons with POLYBORI but parents are supposed to be immutable in Sage.

_singular_init_( )

Return a newly created SINGULAR quotient ring matching this boolean polynomial ring.

NOTE & TODO: This method does not only return a string but actually calls SINGULAR.

sage: B.<x,y> = BooleanPolynomialRing(2)
sage: B._singular_()
//   characteristic : 2
//   number of vars : 2
//        block   1 : ordering lp
//                  : names    x y
//        block   2 : ordering C
// quotient ring from ideal
_[1]=x2+x
_[2]=y2+y

Class: BooleanPolynomialVector

class BooleanPolynomialVector

Functions: append

Special Functions: __getitem__, $\,$ __init__, $\,$ __iter__, $\,$ __len__

__getitem__( )

__iter__( )

Class: BooleanPolynomialVectorIterator

class BooleanPolynomialVectorIterator

Functions: next

next( ): x.next() -> the next value, or raise StopIteration

Special Functions: __iter__, $\,$ __next__

__iter__( )

__next__( )

Class: BooleSet

class BooleSet

Functions: cartesianProduct, $\,$ change, $\,$ diff, $\,$ divide, $\,$ empty, $\,$ includeDivisors, $\,$ minimalElements, $\,$ navigation, $\,$ nNodes, $\,$ nSupport, $\,$ ring, $\,$ set, $\,$ stableHash, $\,$ subset0, $\,$ subset1, $\,$ union, $\,$ vars

cartesianProduct( )

Return the cartesian product of this set and the set rhs.

The Cartesian product of two sets X and Y is the set of all possible ordered pairs whose first component is a member of X and whose second component is a member of Y.

$\displaystyle X\times Y = \{(x,y) \vert x\in X\;\mathrm{and}\;y\in Y\}.$

sage: B = BooleanPolynomialRing(5,'x')
sage: x0,x1,x2,x3,x4 = B.gens()
sage: f = x1*x2+x2*x3
sage: s = f.set(); s
{{x1,x2}, {x2,x3}}
sage: g = x4 + 1
sage: t = g.set(); t
{{x4}, {}}
sage: s.cartesianProduct(t)
{{x1,x2,x4}, {x1,x2}, {x2,x3,x4}, {x2,x3}}

diff( )

Return the set theoretic difference of this set and the set rhs.

The difference of two sets and is defined as:

$\displaystyle X\\ Y = \{x \vert x\in X\;\mathrm{and}\;x\not\in Y\}.$

sage: B = BooleanPolynomialRing(5,'x')
sage: x0,x1,x2,x3,x4 = B.gens()
sage: f = x1*x2+x2*x3
sage: s = f.set(); s
{{x1,x2}, {x2,x3}}
sage: g = x2*x3 + 1
sage: t = g.set(); t
{{x2,x3}, {}}
sage: s.diff(t)
{{x1,x2}}

empty( )

Return True if this set is empty.

sage: B.<a,b,c,d> = BooleanPolynomialRing(4)
sage: BS = (a*b + c).set()
sage: BS.empty()
False

sage: BS = B(0).set()
sage: BS.empty()
True

navigation( )

Navigators provide an interface to diagram nodes, accessing their index as well as the corresponding then- and else-branches.

You should be very careful and always keep a reference to the original object, when dealing with navigators, as navigators contain only a raw pointer as data. For the same reason, it is necessary to supply the ring as argument, when constructing a set out of a navigator.

sage: from polybori import BooleSet
sage: B = BooleanPolynomialRing(5,'x')
sage: x0,x1,x2,x3,x4 = B.gens()
sage: f = x1*x2+x2*x3*x4+x2*x4+x3+x4+1
sage: s = f.set(); s
{{x1,x2}, {x2,x3,x4}, {x2,x4}, {x3}, {x4}, {}}

sage: nav = s.navigation()
sage: BooleSet(nav,s.ring())
{{x1,x2}, {x2,x3,x4}, {x2,x4}, {x3}, {x4}, {}}

sage: nav.value()
1

sage: nav_else = nav.elseBranch()

sage: BooleSet(nav_else,s.ring())
{{x2,x3,x4}, {x2,x4}, {x3}, {x4}, {}}

sage: nav_else.value()
2

nNodes( )

Return the number of nodes in the ZDD.

sage: B = BooleanPolynomialRing(5,'x')
sage: x0,x1,x2,x3,x4 = B.gens()
sage: f = x1*x2+x2*x3
sage: s = f.set(); s
{{x1,x2}, {x2,x3}}
sage: s.nNodes()
4

ring( )

Return the parent ring.

sage: B = BooleanPolynomialRing(5,'x')
sage: x0,x1,x2,x3,x4 = B.gens()
sage: f = x1*x2+x2*x3*x4+x2*x4+x3+x4+1
sage: f.set().ring() is B
True

set( )

Return self.

sage: B.<a,b,c,d> = BooleanPolynomialRing(4)
sage: BS = (a*b + c).set()
sage: BS.set() is BS
True

union( )

Return the set theoretic union of this set and the set rhs.

The union of two sets and is defined as:

$\displaystyle X \cup Y = \{x \vert x\in X\;\mathrm{or}\;x\in Y\}.$

sage: B = BooleanPolynomialRing(5,'x')
sage: x0,x1,x2,x3,x4 = B.gens()
sage: f = x1*x2+x2*x3
sage: s = f.set(); s
{{x1,x2}, {x2,x3}}
sage: g = x2*x3 + 1
sage: t = g.set(); t
{{x2,x3}, {}}
sage: s.diff(t)
{{x1,x2}}

Special Functions: __contains__, $\,$ __init__, $\,$ __iter__, $\,$ __len__, $\,$ __mod__, $\,$ __repr__, $\,$ __rmod__

__iter__( )

Create an iterator over elements of self.

sage: P.<x, y> = BooleanPolynomialRing(2)
sage: f = x*y+x+y+1; s = f.set()
sage: list(s)
[x*y, x, y, 1]

__mod__( )

__repr__( )

sage: from polybori import BooleSet
sage: B.<a,b,c,d> = BooleanPolynomialRing(4)
sage: BS = BooleSet(B)
sage: repr(BS) # indirect doctest
'{}'

Class: BooleSetIterator

class BooleSetIterator

Functions: next

next( ): x.next() -> the next value, or raise StopIteration

Special Functions: __iter__, $\,$ __next__

__iter__( )

__next__( )

sage: B.<a,b,c,d> = BooleanPolynomialRing()
sage: f = B.random_element()
sage: f
a*c + a*d + a + b*d + 1
sage: it = iter(f.set())
sage: it.next()
a*c

Class: BooleVariable

class BooleVariable

Class: CCuddNavigator

class CCuddNavigator

Functions: constant, $\,$ elseBranch, $\,$ terminalOne, $\,$ thenBranch, $\,$ value

Special Functions: __call__

__call__( )

Class: DD

class DD

Functions: empty, $\,$ navigation, $\,$ subset0, $\,$ subset1, $\,$ union

Special Functions: __call__

__call__( )

Class: GroebnerStrategy

class GroebnerStrategy

Functions: addAsYouWish, $\,$ addGenerator, $\,$ addGeneratorDelayed, $\,$ allGenerators, $\,$ allSpolysInNextDegree, $\,$ cleanTopByChainCriterion, $\,$ containsOne, $\,$ faugereStepDense, $\,$ implications, $\,$ llReduceAll, $\,$ minimalize, $\,$ minimalizeAndTailReduce, $\,$ nextSpoly, $\,$ nf, $\,$ npairs, $\,$ select, $\,$ smallSpolysInNextDegree, $\,$ someSpolysInNextDegree, $\,$ suggestPluginVariable, $\,$ symmGB_F2, $\,$ topSugar, $\,$ variableHasValue

Special Functions: __delattr__, $\,$ __getattribute__, $\,$ __getitem__, $\,$ __init__, $\,$ __len__

__getitem__( )

Class: VariableBlock_base

class VariableBlock_base

Special Functions: __init__

Class: VariableBlockFalse

class VariableBlockFalse

Special Functions: __call__, $\,$