Logical Expression

In this section, we explain the logical expression class and its peripheral functions.

Building Logical Expressions

The logical expression class LogicPoly can represent logic expressions. Since it is premised to be input to Ising machines, it has a polynomial of binary variables as its internal representation, and can be converted to a polynomial object.

A logical expression object is constructed by giving the index of a Boolean variable as follows:

from amplify import LogicPoly

x0 = LogicPoly(0)
>>> x0
x_0

You can also build it by giving it a Boolean value.

t = LogicPoly(True)
f = LogicPoly(False)
>>> t
1
>>> f
0

Thus, a logical expression object is marked with 1 if it is True and 0 if it is False. This is due to the fact that the internal representation is a polynomial of a binary variable. So if it is displayed as a string, it will be in a polynomial expression of a binary variable, the form BinaryPoly.

Note

The internal representation of LogicPoly is a polynomial of binary variables BinaryPoly, where the possible values are restricted to be 1 (True) or 0 (False). Users cannot directly manipulate this polynomial object.

If the same logical expression object is given as the constructor argument, a copy can be made.

from amplify import LogicPoly

x0 = LogicPoly(0)
x_copy = LogicPoly(x0)
>>> x0
x_0
>>> x_copy
x_0

Logical Expression Operators

The logical expression class defines equivalence, disjunction, logical product, exclusive disjunction, logical negation, and their compound assignment operators between logical expression objects and Boolean variables.

>>> LogicPoly(0) | LogicPoly(1)
- x_0 x_1 + x_0 + x_1
>>> LogicPoly(0) & LogicPoly(1)
x_0 x_1
>>> LogicPoly(0) ^ LogicPoly(1)
- 2 x_0 x_1 + x_0 + x_1
>>> ~(LogicPoly(0) & LogicPoly(1))
- x_0 x_1 + 1
>>> ~(LogicPoly(0) | LogicPoly(1)) == ~LogicPoly(0) & ~LogicPoly(1)
True

Construction and Evaluation Using Variable Arrays

As with the polynomial class, the gen_symbols() and decode_solution() functions can be used to generate Boolean variable arrays and evaluate the solutions. See Construction using variable arrays, Assigning values to variable arrays, and Getting solutions using variable arrays for more details.

from amplify import LogicPoly, gen_symbols

x = gen_symbols(LogicPoly, 10)
>>> x
[x_0, x_1, x_2, x_3, x_4, x_5, x_6, x_7, x_8, x_9]

Auxiliary Functions for Formulation

Similar to the sum_poly() function in the polynomial class, the following functions are provided to assist the formulation of logical expressions.

  • The intersection() function, which is equivalent to all logical products \(\land_i\)

  • The union() function, which is equivalent to all logical ORs \(\lor_i\)

  • The symmetric_difference() functions, which is equivalent to all exclusive ORs \(\oplus_i\)

These functions have the following three functions.

Operations on Lists

The following operations are performed on a list x.

\[ \begin{align}\begin{aligned}l &= \bigwedge_{i = 0}^{n - 1} x_\left[ i \right]\\l &= \bigvee_{i = 0}^{n - 1} x_\left[ i \right]\\l &= \bigoplus_{i = 0}^{n - 1} x_\left[ i \right]\end{aligned}\end{align} \]
from amplify import LogicPoly, gen_symbols, intersection, union, symmetric_difference

x = gen_symbols(LogicPoly, 3)
>>> intersection(x)
x_0 x_1 x_2
>>> union(x)
x_0 x_1 x_2 - x_0 x_1 - x_0 x_2 - x_1 x_2 + x_0 + x_1 + x_2
>>> symmetric_difference(x)
4 x_0 x_1 x_2 - 2 x_0 x_1 - 2 x_0 x_2 - 2 x_1 x_2 + x_0 + x_1 + x_2

Operations on Indices

The following operations are performed on variables x_i:

\[ \begin{align}\begin{aligned}l &= \bigwedge_{i = 0}^{n - 1} x_i\\l &= \bigvee_{i = 0}^{n - 1} x_i\\l &= \bigoplus_{i = 0}^{n - 1} x_i\end{aligned}\end{align} \]

The first through third arguments can be the same as the built-in class range, or the first argument can be an enumerated type.

>>> intersection(3)
x_0 x_1 x_2
>>> intersection(1, 4)
x_1 x_2 x_3
>>> intersection(1, 6, 2)
x_1 x_3 x_5
>>> intersection(range(2, 7, 2))
x_2 x_4 x_6
>>> union(3)
x_0 x_1 x_2 - x_0 x_1 - x_0 x_2 - x_1 x_2 + x_0 + x_1 + x_2
>>> union(1, 4)
x_1 x_2 x_3 - x_1 x_2 - x_1 x_3 - x_2 x_3 + x_1 + x_2 + x_3
>>> union(1, 6, 2)
x_1 x_3 x_5 - x_1 x_3 - x_1 x_5 - x_3 x_5 + x_1 + x_3 + x_5
>>> union(range(2, 7, 2))
x_2 x_4 x_6 - x_2 x_4 - x_2 x_6 - x_4 x_6 + x_2 + x_4 + x_6
>>> symmetric_difference(3)
4 x_0 x_1 x_2 - 2 x_0 x_1 - 2 x_0 x_2 - 2 x_1 x_2 + x_0 + x_1 + x_2
>>> symmetric_difference(1, 4)
4 x_1 x_2 x_3 - 2 x_1 x_2 - 2 x_1 x_3 - 2 x_2 x_3 + x_1 + x_2 + x_3
>>> symmetric_difference(1, 6, 2)
4 x_1 x_3 x_5 - 2 x_1 x_3 - 2 x_1 x_5 - 2 x_3 x_5 + x_1 + x_3 + x_5
>>> symmetric_difference(range(2, 7, 2))
4 x_2 x_4 x_6 - 2 x_2 x_4 - 2 x_2 x_6 - 2 x_4 x_6 + x_2 + x_4 + x_6

Note

As with the polynomial class, a logical expression class can be given as the last argument, but it can be omitted.

Operations on Functions

The following operations are performed on functions g(i).

\[ \begin{align}\begin{aligned}l &= \bigwedge_{i = 0}^{n - 1} g\left( i \right)\\l &= \bigvee_{i = 0}^{n - 1} g\left( i \right)\\l &= \bigoplus_{i = 0}^{n - 1} g\left( i \right)\end{aligned}\end{align} \]

Examples of Operations on Expressions

\[l = \bigwedge_{i = 0}^{n - 1} \lnot x_{2 i}\]
from amplify import LogicPoly, intersection
>>> intersection(3, lambda i: ~LogicPoly(2 * i))
- x_0 x_2 x_4 + x_0 x_2 + x_0 x_4 + x_2 x_4 - x_0 - x_2 - x_4 + 1

Example of Nested Operations

Satisfiability problem (k-SAT)

\[l = \bigwedge_{i} \bigvee_{j \in C_i} l_j\]
from amplify import LogicPoly, intersection, union

x = gen_symbols(LogicPoly, 5)
l = intersection(3, lambda i: union(3, lambda j: x[i + j] if j == 1 else ~x[i + j]))
>>> l
x_0 x_1 x_2 x_3 x_4 - x_0 x_1 x_2 x_4 - x_0 x_2 x_3 x_4 + x_0 x_1 x_2 + x_0 x_2 x_4 + x_1 x_2 x_3 + x_2 x_3 x_4 - x_0 x_2 - x_1 x_3 - x_2 x_4 + 1

Methods of Logical Expression Class

It has the same interface as the polynomial class for most of its methods. Please see Methods of the polynomial class.

Variable Transformation

change_variables()

Number of Terms

count()

Convertibility to Boolean Values

Returns whether the Boolean expression object consists only of Boolean values. If it is True, implicit conversion to Boolean is possible.

from amplify import LogicPoly

p = LogicPoly(0) | ~LogicPoly(0)
>>> p.is_bool()
True
>>> "TRUE" if p else "FALSE"
TRUE

Maximum Index Value

max_index()

Assigning Values to a Polynomial

replace()

Evaluating the Value of a Polynomial

replace_all()

Converting to a Polynomial of Binary Variables

Converts a logical expression to a polynomial of binary variables.

from amplify import LogicPoly

p = LogicPoly(0) | LogicPoly(1)
f = (~p).to_Poly()
>>> p
- x_0 x_1 + x_0 + x_1
>>> f
q_0 q_1 - q_0 - q_1 + 1

Note

In the logical expression class, True is treated as 1 and False is treated as 0. Considering a polynomial obtained by some logical expressions with Boolean variables (i.e. p in the above example), the polynomial has a larger numerical value with True than False. Therefore, when treating polynomials of binary variables in optimization (minimization) problems, we need to perform NOT operation and call to_Poly() function afterward so that the minimum value of the polynomial after conversion consistently corresponds to the True state of the original polynomial.