Let f: Z_2^n -> Z_2 be a Boolean function. The vector
F=(\;f(0),\; f(1),\; \ldots,\; f(2^n-1)\;)^T,
where f(i) for each i ∈ {0,1,...,2^n-1} is the value of f(x_1,...,x_n) of the i-th row in the truth table, is called the truth vector.
As a generalization of Boolean logic we can consider the k-valued logic, thus f: Z_k^n -> Z_k. Other way to generalize the concept of Boolean functions is the introduction of discrete logic functions, defined in Chapter 5.
‣ LogicFunction( NumVars, Dimension, Output ) | ( function ) |
For the positive integer NumVars - the number of variables, a positive integer Dimension - the number of possible logical values and a list non-negative integers Output - the truth vector of the given Dimension-valued logic function of NumVars variables, the function LogicFunction returns an object, representing the corresponding logic function.
Note that Dimension can be also a list of NumVars positive integer numbers if we deal with discrete logic functions.
gap> f:=LogicFunction(2,2,[0,0,1,1]); < Boolean function of 2 variables > gap> Display(f); Boolean function of 2 variables. [ 0, 0 ] || 0 [ 0, 1 ] || 0 [ 1, 0 ] || 1 [ 1, 1 ] || 1 gap> f:=LogicFunction(2,3,[0,0,1,1,2,1,2,0,1]); < 3-valued logic function of 2 variables > gap> Display(f); 3-valued logic function of 2 variables. [ 0, 0 ] || 0 [ 0, 1 ] || 0 [ 0, 2 ] || 1 [ 1, 0 ] || 1 [ 1, 1 ] || 2 [ 1, 2 ] || 1 [ 2, 0 ] || 2 [ 2, 1 ] || 0 [ 2, 2 ] || 1
‣ IsLogicFunction( Obj ) | ( function ) |
For the object Obj the function IsLogicFunction returns true if Obj is a logic function (see LogicFunction (2.1-1)), and false otherwise.
gap> f:=LogicFunction(2,2,[0,1,1,1]);; gap> IsLogicFunction(f); true
‣ PolynomialToBooleanFunction( Pol, NumVars ) | ( function ) |
For the polynomial Pol over GF(2) and the number of variables NumVar the function PolynomialToBooleanFunction returns a Boolean logic function which is realized by Pol.
gap> x:=Indeterminate(GF(2),"x");; gap> y:=Indeterminate(GF(2),"y");; gap> pol:=x+y;; gap> f:=PolynomialToBooleanFunction(pol,2); < Boolean function of 2 variables > gap> Display(f); Boolean function of 2 variables. [ 0, 0 ] || 0 [ 0, 1 ] || 1 [ 1, 0 ] || 1 [ 1, 1 ] || 0
‣ IsUnateInVariable( Func, Var ) | ( function ) |
A Boolean function f(x_1,... ,x_n) is positive unate in x_i if for all possible values of x_j with j≠ i we have
f(x_{1},\ldots ,x_{i-1},1,x_{i+1},\ldots ,x_{n})\geq f(x_{1},\ldots ,x_{i-1},0,x_{i+1},\ldots ,x_{n}).
A Boolean function f(x_1,... ,x_n) is negative unate in x_i if
f(x_{1},\ldots ,x_{i-1},0,x_{i+1},\ldots ,x_{n})\geq f(x_{1},\ldots ,x_{i-1},1,x_{i+1},\ldots ,x_{n}).
For the Boolean function Func and the positive integer Var (which represents the number of the variable) the function IsUnateBooleanFunction returns true if Func is unate (either positive or negative) in this variable and false otherwise.
gap> f:=LogicFunction(3,2,[0,0,0,0,0,1,1,0]); < Boolean function of 3 variables > gap> Display(f); Boolean function of 3 variables. [ 0, 0, 0 ] || 0 [ 0, 0, 1 ] || 0 [ 0, 1, 0 ] || 0 [ 0, 1, 1 ] || 0 [ 1, 0, 0 ] || 0 [ 1, 0, 1 ] || 1 [ 1, 1, 0 ] || 1 [ 1, 1, 1 ] || 0 gap> IsUnateInVariable(f,1); true gap> IsUnateInVariable(f,2); false gap> IsUnateInVariable(f,3); false
‣ IsUnateBooleanFunction( Func ) | ( function ) |
If a Boolean function f is either positive or negative unate in each variable then it is said to be unate (note that some x_i may be positive unate and some negative unate to satisfy the definition of unate function). A Boolean function f is binate if it is not unate (i.e., is neither positive unate nor negative unate in at least one of its variables).
All threshold functions are unate. However, the converse is not true, because there are certain unate functions, that can not be realized by STE [AQR99].
For the Boolean function Func the function IsUnateBooleanFunction returns true if Func is unate and false otherwise.
gap> f:=LogicFunction(2,2,[0,1,1,1]);; gap> IsUnateBooleanFunction(f); true gap> f:=LogicFunction(2,2,[0,1,1,0]);; gap> IsUnateBooleanFunction(f); false
‣ InfluenceOfVariable( Func, Var ) | ( function ) |
The influence of a variable x_i measures how many times out of the total existing cases a change on that variable produces a change on the output of the function.
For the Boolean function Func and the positive integer Var the function InfluenceOfVariable returns a positive integer - the weighted influence of the variable Var (to obtain integer values we multiply the influence of the variable by 2^n, where n is the number of variables of Func).
gap> f:=LogicFunction(3,2,[0,0,0,0,0,1,1,0]); < Boolean function of 3 variables > gap> Display(f); Boolean function of 3 variables. [ 0, 0, 0 ] || 0 [ 0, 0, 1 ] || 0 [ 0, 1, 0 ] || 0 [ 0, 1, 1 ] || 0 [ 1, 0, 0 ] || 0 [ 1, 0, 1 ] || 1 [ 1, 1, 0 ] || 1 [ 1, 1, 1 ] || 0 gap> InfluenceOfVariable(f,2); 2
‣ SelfDualExtensionOfBooleanFunction( Func ) | ( function ) |
The self-dual extension of a Boolean function f^n:Z_2^n -> Z_2 of n variables is a Boolean function f^n+1:Z_2^n+1 -> Z_2 of n+1 variables defined as
f^{n+1}(x_1,\ldots,x_n,x_{n+1})=f^{n}(x_1,\ldots,x_n) \quad \textrm{if} \quad x_{n+1}=0,
f^{n+1}(x_1,\ldots,x_n,x_{n+1})=1-f^{n}(\overline x_1,\ldots,\overline x_n) \quad \textrm{if} \quad x_{n+1}=1,
where overline x_i = x_i ⊕ 1 is the negation of the i-th variable.
Every threshold function is unate. However, in [FSAJ06] was shown that the unatness in the self-dual space of n+1 variables is much stronger condition.
For the Boolean function Func the function SelfDualExtensionOfBooleanFunction returns the self-dual extension of Func.
gap> f:=LogicFunction(2,2,[0,0,0,1]); < Boolean function of 2 variables > gap> Display(f); Boolean function of 2 variables. [ 0, 0 ] || 0 [ 0, 1 ] || 0 [ 1, 0 ] || 0 [ 1, 1 ] || 1 gap> fsd:=SelfDualExtensionOfBooleanFunction(f); < Boolean function of 3 variables > gap> Display(fsd); Boolean function of 3 variables. [ 0, 0, 0 ] || 0 [ 0, 0, 1 ] || 0 [ 0, 1, 0 ] || 0 [ 0, 1, 1 ] || 1 [ 1, 0, 0 ] || 0 [ 1, 0, 1 ] || 1 [ 1, 1, 0 ] || 1 [ 1, 1, 1 ] || 1
‣ SplitBooleanFunction( Func, Var, Bool ) | ( function ) |
The method of splitting a function in terms of a given variable is known as Shannon decomposition and it was formally introduced in 1938 by Shannon.
Let f(x_1,...,x_n) be a Boolean function. Decompose f as a disjunction of the following two Boolean functions f_a and f_b defined as:
\textstyle f_a(x_1,\ldots,x_n)=f(x_1,\ldots,x_{i-1},0,x_{i+1},\ldots,x_n) \quad \textrm{if} \quad x_i=0,
f_a(x_1,\ldots,x_n)=0, \quad \textrm{if} \quad x_i=1;
and
f_b(x_1,\ldots,x_n)= 0 \quad \textrm{if} \quad x_i=0,\quad
f_b(x_1,\ldots,x_n)=f(x_1,\ldots,x_{i-1},1,x_{i+1},\ldots,x_n) \quad \textrm{if} \quad x_i=1.
If we are intended to use conjunction, we can apply the same equations with 1 for undetermined outputs instead of 0.
For the Boolean function Func, a positive integer Var (the number of variable), Boolean variable Bool (true for disjunction and false for conjunction) the function SplitBooleanFunction returns a list with two entries: the resulting Boolean logic functions.
gap> f:=LogicFunction(2,2,[0,1,1,0]);; gap> Display(f); Boolean function of 2 variables. [ 0, 0 ] || 0 [ 0, 1 ] || 1 [ 1, 0 ] || 1 [ 1, 1 ] || 0 gap> out:=SplitBooleanFunction(f,1,false);; gap> Print(out[1]); [2, 2,[ 0, 1, 1, 1 ]] gap> Print(out[2]); [2, 2,[ 1, 1, 1, 0 ]] gap> out:=SplitBooleanFunction(f,1,true);; gap> Print(out[1]); [2, 2,[ 0, 1, 0, 0 ]] gap> Print(out[2]); [2, 2,[ 0, 0, 1, 0 ]]
‣ KernelOfBooleanFunction( Func ) | ( function ) |
For a Boolean function f(x_1,...,x_n) we define the following two sets (see [ABGG80]):
The kernel K(f) of the Boolean function f is defined as
K(f)=f^{-1}(1), \quad \textrm{ if } \quad |f^{-1}(1)| \geq |f^{-1}(0)|;
K(f)=f^{-1}(0), \quad \textrm{otherwise,}
where |f^-1(i)| is the cardinality of the set f^-1(i) with i ∈ {0,1}.
For the Boolean function Func the function KernelOfBooleanFunction returns a list in which the first element of the output list represents the kernel, and the second element equals either 1 or 0.
gap> f:=LogicFunction(3,2,[0,1,1,0,1,0,0,0]);; gap> k:=KernelOfBooleanFunction(f); [ [ [ 0, 0, 1 ], [ 0, 1, 0 ], [ 1, 0, 0 ] ], 1 ]
‣ ReducedKernelOfBooleanFunction( Ker ) | ( function ) |
Let f(x_1,...,x_n) be a Boolean function with the kernel K(f)={ a_1,...,a_m }, where m ≤ 2^n-1. The reduced kernel K(f)_i of the function f relative to the element a_i ∈ K(f) is the following set (see [ABGG80]):
K(f)_i=\big\{\;a_1 \oplus a_i, \; a_2 \oplus a_i,\; \ldots,\; a_m \oplus a_i \; \big\},
where ⊕ is a component-wise addition of vectors from K(f) over GF(2).
The reduced kernel T(f) of f is the following set:
T(f)=\big\{ \;K(f)_i \;\mid\; i=1,2,\ldots,m \;\big\}.
For the m × n matrix Ker, which represents the kernel of some Boolean function f, the function ReducedKernelOfBooleanFunction returns the reduced kernel T(f) of f.
gap> ## Continuation of Example 2.2.4 gap> rk:=ReducedKernelOfBooleanFunction(k[1]);; gap> j:=1;; gap> for i in rk do Print(j,".\n"); Display(i); Print("\n"); j:=j+1; od; 1. . . . . 1 1 1 . 1 2. . 1 1 . . . 1 1 . 3. 1 . 1 1 1 . . . .
generated by GAPDoc2HTML