| products/Sources/formale Sprachen/GAP/pkg/thelma/doc/chap2_mj.html |
 |
<?xml version= "1.0" encoding= "UTF-8"?>
<! DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
< html xmlns= "http://www.w3.org/1999/xhtml" xml:lang= "en">
< head>
< script type= "text/javascript"
src= "https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.0/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</ script>
< title>GAP (Thelma) - Chapter 2: Boolean Functions</ title>
< meta http-equiv= "content-type" content= "text/html; charset=UTF-8" />
< meta name= "generator" content= "GAPDoc2HTML" />
< link rel= "stylesheet" type= "text/css" href= "manual.css" />
< script src= "manual.js" type= "text/javascript"></ script>
< script type= "text/javascript">overwriteStyle();</ script>
</ head>
< body class= "chap2" onload= "jscontent()">
< div class= "chlinktop">< span class= "chlink1">Goto Chapter: </ span>< a href= "chap0_mj.html">Top< /a> <a href="chap1_mj.html">1</a> <a href="chap2_mj.html">2</a> <a href="chap3_mj.html">3</a> <a href="chap4_mj.html">4</a> <a href="chap5_mj.html">5</a> <a href="chapBib_mj.html">Bib</a> <a href="chapInd_mj.html">Ind</a> </div>
<div class="chlinkprevnexttop"> <a href="chap0_mj.html">[Top of Book]</a> <a href="chap0_mj.html#contents">[Contents]</a> <a href="chap1_mj.html">[Previous Chapter]</a> <a href="chap3_mj.html">[Next Chapter]</a> </div>
<p id="mathjaxlink" class="pcenter"><a href="chap2.html">[MathJax off]</a></p>
<p><a id="X830F6677819A6656" name="X830F6677819A6656"></a></p>
<div class="ChapSects"><a href="chap2_mj.html#X830F6677819A6656">2 <span class="Heading">Boolean Functions</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap2_mj.html#X82EB5BE77F9F686A">2.1 <span class="Heading">Basic Operations</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X7D8A971A84186BF0">2.1-1 LogicFunction</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X7C34DEE27EC3A009">2.1-2 IsLogicFunction</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X857A4F117BDDF1B6">2.1-3 PolynomialToBooleanFunction</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X78B9DD8E81EE65A8">2.1-4 IsUnateInVariable</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X8203046F7C97EAFE">2.1-5 IsUnateBooleanFunction</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X7D0DEF0B7E9FE027">2.1-6 InfluenceOfVariable</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X86C000FE831CFEDE">2.1-7 SelfDualExtensionOfBooleanFunction</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X7C09D66E84201A77">2.1-8 SplitBooleanFunction</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X8108DE5280908841">2.1-9 KernelOfBooleanFunction</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap2_mj.html#X7B1B54877B354F23">2.1-10 ReducedKernelOfBooleanFunction</a></span>
</div></div>
</div>
<h3>2 <span class="Heading">Boolean Functions</span></h3>
<p><a id="X82EB5BE77F9F686A" name="X82EB5BE77F9F686A"></a></p>
<h4>2.1 <span class="Heading">Basic Operations</span></h4>
<p>Let <span class="SimpleMath">\(f: \mathbb{Z}_2^n \to \mathbb{Z}_2\)</span> be a Boolean function. The vector</p>
<p class="center">\[
F=(\;f(0),\; f(1),\; \ldots,\; f(2^n-1)\;)^T,
\]</p>
<p>where <span class="SimpleMath">\(f(i)\)</span> for each <span class="SimpleMath">\(i \in \{0,1,\ldots,2^n-1\}\)</span> is the value of <span class="SimpleMath">\(f(x_1,\ldots,x_n)\)</span> of the i-th row in the truth table, is called the <var class="Arg">truth vector</var>.</p>
<p>As a generalization of Boolean logic we can consider the <span class="SimpleMath">\(k\)</span>-valued logic, thus <span class="SimpleMath">\(f: \mathbb{Z}_k^n \to \mathbb{Z}_k\)</span>. Other way to generalize the concept of Boolean functions is the introduction of discrete logic functions, defined in Chapter <a href="chap5_mj.html#X8735CBCC80897D83"><span class="RefLink">5</span></a>.</p>
<p><a id="X7D8A971A84186BF0" name="X7D8A971A84186BF0"></a></p>
<h5>2.1-1 LogicFunction</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; LogicFunction</code>( <var class="Arg">NumVars</var>, <var class="Arg">Dimension</var>, <var class="Arg">Output</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>For the positive integer <code class="code">NumVars</code> - the number of variables, a positive integer <code class="code">Dimension</code> - the number of possible logical values and a list non-negative integers <code class="code">Output</code> - the truth vector of the given <code class="code">Dimension</code>-valued logic function of <code class="code">NumVars</code> variables, the function <code class="code">LogicFunction</code> returns an object, representing the corresponding logic function.</p>
<p>Note that <code class="code">Dimension</code> can be also a list of <code class="code">NumVars</code> positive integer numbers if we deal with discrete logic functions.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">f:=LogicFunction(2,2,[0,0,1,1]);</span>
< Boolean function of 2 variables >
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(f);</span>
Boolean function of 2 variables.
[ 0, 0 ] || 0
[ 0, 1 ] || 0
[ 1, 0 ] || 1
[ 1, 1 ] || 1
<span class="GAPprompt">gap></span> <span class="GAPinput">f:=LogicFunction(2,3,[0,0,1,1,2,1,2,0,1]);</span>
< 3-valued logic function of 2 variables >
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(f);</span>
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
</pre></div>
<p><a id="X7C34DEE27EC3A009" name="X7C34DEE27EC3A009"></a></p>
<h5>2.1-2 IsLogicFunction</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; IsLogicFunction</code>( <var class="Arg">Obj</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>For the object <code class="code">Obj</code> the function <code class="code">IsLogicFunction</code> returns <code class="code">true</code> if <code class="code">Obj</code> is a logic function (see <code class="func">LogicFunction</code> (<a href="chap2_mj.html#X7D8A971A84186BF0"><span class="RefLink">2.1-1</span></a>)), and <code class="code">false</code> otherwise.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">f:=LogicFunction(2,2,[0,1,1,1]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsLogicFunction(f);</span>
true
</pre></div>
<p><a id="X857A4F117BDDF1B6" name="X857A4F117BDDF1B6"></a></p>
<h5>2.1-3 PolynomialToBooleanFunction</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; PolynomialToBooleanFunction</code>( <var class="Arg">Pol</var>, <var class="Arg">NumVars</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>For the polynomial <code class="code">Pol</code> over <span class="SimpleMath">\(GF(2)\)</span> and the number of variables <code class="code">NumVar</code> the function <code class="code">PolynomialToBooleanFunction</code> returns a Boolean logic function which is realized by <code class="code">Pol</code>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x:=Indeterminate(GF(2),"x");;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">y:=Indeterminate(GF(2),"y");;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">pol:=x+y;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">f:=PolynomialToBooleanFunction(pol,2);</span>
< Boolean function of 2 variables >
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(f);</span>
Boolean function of 2 variables.
[ 0, 0 ] || 0
[ 0, 1 ] || 1
[ 1, 0 ] || 1
[ 1, 1 ] || 0
</pre></div>
<p><a id="X78B9DD8E81EE65A8" name="X78B9DD8E81EE65A8"></a></p>
<h5>2.1-4 IsUnateInVariable</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; IsUnateInVariable</code>( <var class="Arg">Func</var>, <var class="Arg">Var</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>A Boolean function <span class="SimpleMath">\(f(x_1,\ldots ,x_n)\)</span> is <var class="Arg">positive unate</var> in <span class="SimpleMath">\(x_{i}\)</span> if for all possible values of <span class="SimpleMath">\(x_{j}\)</span> with <span class="SimpleMath">\(j\neq i\)</span> we have</p>
<p class="center">\[
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}).
\]</p>
<p>A Boolean function <span class="SimpleMath">\(f(x_1,\ldots ,x_n)\)</span> is <var class="Arg">negative unate</var> in <span class="SimpleMath">\(x_{i}\)</span> if</p>
<p class="center">\[
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}).
\]</p>
<p>For the Boolean function <code class="code">Func</code> and the positive integer <code class="code">Var</code> (which represents the number of the variable) the function <code class="code">IsUnateBooleanFunction</code> returns <code class="code">true</code> if <code class="code">Func</code> is unate (either positive or negative) in this variable and <code class="code">false</code> otherwise.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">f:=LogicFunction(3,2,[0,0,0,0,0,1,1,0]);</span>
< Boolean function of 3 variables >
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(f);</span>
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
<span class="GAPprompt">gap></span> <span class="GAPinput">IsUnateInVariable(f,1);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsUnateInVariable(f,2);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsUnateInVariable(f,3);</span>
false
</pre></div>
<p><a id="X8203046F7C97EAFE" name="X8203046F7C97EAFE"></a></p>
<h5>2.1-5 IsUnateBooleanFunction</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; IsUnateBooleanFunction</code>( <var class="Arg">Func</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>If a Boolean function <span class="SimpleMath">\(f\)</span> is either positive or negative unate in each variable then it is said to be <var class="Arg">unate</var> (note that some <span class="SimpleMath">\(x_{i}\)</span> may be positive unate and some negative unate to satisfy the definition of unate function). A Boolean function <span class="SimpleMath">\(f\)</span> is <var class="Arg">binate</var> if it is not unate (i.e., is neither positive unate nor negative unate in at least one of its variables).</p>
<p>All threshold functions are unate. However, the converse is not true, because there are certain unate functions, that can not be realized by STE <a href="chapBib_mj.html#biBAvedillo1999">[AQR99]</a>.</p>
<p>For the Boolean function <code class="code">Func</code> the function <code class="code">IsUnateBooleanFunction</code> returns <code class="code">true</code> if <code class="code">Func</code> is unate and <code class="code">false</code> otherwise.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">f:=LogicFunction(2,2,[0,1,1,1]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsUnateBooleanFunction(f);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">f:=LogicFunction(2,2,[0,1,1,0]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsUnateBooleanFunction(f);</span>
false
</pre></div>
<p><a id="X7D0DEF0B7E9FE027" name="X7D0DEF0B7E9FE027"></a></p>
<h5>2.1-6 InfluenceOfVariable</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; InfluenceOfVariable</code>( <var class="Arg">Func</var>, <var class="Arg">Var</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The influence of a variable <span class="SimpleMath">\(x_i\)</span> measures how many times out of the total existing cases a change on that variable produces a change on the output of the function.</p>
<p>For the Boolean function <code class="code">Func</code> and the positive integer <code class="code">Var</code> the function <code class="code">InfluenceOfVariable</code> returns a positive integer - the weighted influence of the variable <code class="code">Var</code> (to obtain integer values we multiply the influence of the variable by <span class="SimpleMath">\(2^n\)</span>, where <span class="SimpleMath">\(n\)</span> is the number of variables of <code class="code">Func</code>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">f:=LogicFunction(3,2,[0,0,0,0,0,1,1,0]);</span>
< Boolean function of 3 variables >
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(f);</span>
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
<span class="GAPprompt">gap></span> <span class="GAPinput">InfluenceOfVariable(f,2);</span>
2
</pre></div>
<p><a id="X86C000FE831CFEDE" name="X86C000FE831CFEDE"></a></p>
<h5>2.1-7 SelfDualExtensionOfBooleanFunction</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; SelfDualExtensionOfBooleanFunction</code>( <var class="Arg">Func</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>The <var class="Arg">self-dual extension</var> of a Boolean function <span class="SimpleMath">\(f^{n}:\mathbb{Z}_2^n \to \mathbb{Z}_2\)</span> of <span class="SimpleMath">\(n\)</span> variables is a Boolean function <span class="SimpleMath">\(f^{n+1}:\mathbb{Z}_2^{n+1} \to \mathbb{Z}_2\)</span> of <span class="SimpleMath">\(n+1\)</span> variables defined as</p>
<p class="center">\[
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,
\]</p>
<p class="center">\[
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,
\]</p>
<p>where <span class="SimpleMath">\(\overline x_i = x_i \oplus 1\)</span> is the negation of the <span class="SimpleMath">\(i\)</span>-th variable.</p>
<p>Every threshold function is unate. However, in <a href="chapBib_mj.html#biBFranco2006">[FSAJ06]</a> was shown that the unatness in the self-dual space of <span class="SimpleMath">\(n+1\)</span> variables is much stronger condition.</p>
<p>For the Boolean function <code class="code">Func</code> the function <code class="code">SelfDualExtensionOfBooleanFunction</code> returns the self-dual extension of <code class="code">Func</code>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">f:=LogicFunction(2,2,[0,0,0,1]);</span>
< Boolean function of 2 variables >
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(f);</span>
Boolean function of 2 variables.
[ 0, 0 ] || 0
[ 0, 1 ] || 0
[ 1, 0 ] || 0
[ 1, 1 ] || 1
<span class="GAPprompt">gap></span> <span class="GAPinput">fsd:=SelfDualExtensionOfBooleanFunction(f);</span>
< Boolean function of 3 variables >
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(fsd);</span>
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
</pre></div>
<p><a id="X7C09D66E84201A77" name="X7C09D66E84201A77"></a></p>
<h5>2.1-8 SplitBooleanFunction</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; SplitBooleanFunction</code>( <var class="Arg">Func</var>, <var class="Arg">Var</var>, <var class="Arg">Bool</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>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.</p>
<p>Let <span class="SimpleMath">\(f(x_1,\ldots,x_n)\)</span> be a Boolean function. Decompose <span class="SimpleMath">\(f\)</span> as a disjunction of the following two Boolean functions <span class="SimpleMath">\(f_a\)</span> and <span class="SimpleMath">\(f_b\)</span> defined as:</p>
<p class="center">\[
\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,
\]</p>
<p class="center">\[
f_a(x_1,\ldots,x_n)=0, \quad \textrm{if} \quad x_i=1;
\]</p>
<p>and</p>
<p class="center">\[
f_b(x_1,\ldots,x_n)= 0 \quad \textrm{if} \quad x_i=0,\quad
\]</p>
<p class="center">\[
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.
\]</p>
<p>If we are intended to use conjunction, we can apply the same equations with 1 for undetermined outputs instead of 0.</p>
<p>For the Boolean function <code class="code">Func</code>, a positive integer <code class="code">Var</code> (the number of variable), Boolean variable <code class="code">Bool</code> (<code class="code">true</code> for disjunction and <code class="code">false</code> for conjunction) the function <code class="code">SplitBooleanFunction</code> returns a list with two entries: the resulting Boolean logic functions.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">f:=LogicFunction(2,2,[0,1,1,0]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(f);</span>
Boolean function of 2 variables.
[ 0, 0 ] || 0
[ 0, 1 ] || 1
[ 1, 0 ] || 1
[ 1, 1 ] || 0
<span class="GAPprompt">gap></span> <span class="GAPinput">out:=SplitBooleanFunction(f,1,false);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Print(out[1]);</span>
[2, 2,[ 0, 1, 1, 1 ]]
<span class="GAPprompt">gap></span> <span class="GAPinput">Print(out[2]);</span>
[2, 2,[ 1, 1, 1, 0 ]]
<span class="GAPprompt">gap></span> <span class="GAPinput">out:=SplitBooleanFunction(f,1,true);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Print(out[1]);</span>
[2, 2,[ 0, 1, 0, 0 ]]
<span class="GAPprompt">gap></span> <span class="GAPinput">Print(out[2]);</span>
[2, 2,[ 0, 0, 1, 0 ]]
</pre></div>
<p><a id="X8108DE5280908841" name="X8108DE5280908841"></a></p>
<h5>2.1-9 KernelOfBooleanFunction</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; KernelOfBooleanFunction</code>( <var class="Arg">Func</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>For a Boolean function <span class="SimpleMath">\(f(x_1,\ldots,x_n)\)</span> we define the following two sets (see <a href="chapBib_mj.html#biBGecheBovdi80">[ABGG80]</a>):</p>
<p>The kernel <span class="SimpleMath">\(K(f)\)</span> of the Boolean function <span class="SimpleMath">\(f\)</span> is defined as</p>
<p class="center">\[
K(f)=f^{-1}(1), \quad \textrm{ if } \quad |f^{-1}(1)| \geq |f^{-1}(0)|;
\]</p>
<p class="center">\[
K(f)=f^{-1}(0), \quad \textrm{otherwise,}
\]</p>
<p>where <span class="SimpleMath">\(|f^{-1}(i)|\)</span> is the cardinality of the set <span class="SimpleMath">\(f^{-1}(i)\)</span> with <span class="SimpleMath">\(i \in \{0,1\}\)</span>.</p>
<p>For the Boolean function <code class="code">Func</code> the function <code class="code">KernelOfBooleanFunction</code> returns a list in which the first element of the output list represents the kernel, and the second element equals either <span class="SimpleMath">\(1\)</span> or <span class="SimpleMath">\(0\)</span>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">f:=LogicFunction(3,2,[0,1,1,0,1,0,0,0]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">k:=KernelOfBooleanFunction(f);</span>
[ [ [ 0, 0, 1 ], [ 0, 1, 0 ], [ 1, 0, 0 ] ], 1 ]
</pre></div>
<p><a id="X7B1B54877B354F23" name="X7B1B54877B354F23"></a></p>
<h5>2.1-10 ReducedKernelOfBooleanFunction</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; ReducedKernelOfBooleanFunction</code>( <var class="Arg">Ker</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Let <span class="SimpleMath">\(f(x_1,\ldots,x_n)\)</span> be a Boolean function with the kernel <span class="SimpleMath">\(K(f)=\{\;a_1,\ldots,a_m\;\}\)</span>, where <span class="SimpleMath">\(m \leq 2^{n-1}\)</span>. The reduced kernel <span class="SimpleMath">\(K(f)_i\)</span> of the function <span class="SimpleMath">\(f\)</span> relative to the element <span class="SimpleMath">\(a_i \in K(f)\)</span> is the following set (see <a href="chapBib_mj.html#biBGecheBovdi80">[ABGG80]</a>):</p>
<p class="center">\[
K(f)_i=\big\{\;a_1 \oplus a_i, \; a_2 \oplus a_i,\; \ldots,\; a_m \oplus a_i \; \big\},
\]</p>
<p>where <span class="SimpleMath">\(\oplus\)</span> is a component-wise addition of vectors from <span class="SimpleMath">\(K(f)\)</span> over <span class="SimpleMath">\(GF(2)\)</span>.</p>
<p>The reduced kernel <span class="SimpleMath">\(T(f)\)</span> of <span class="SimpleMath">\(f\)</span> is the following set:</p>
<p class="center">\[
T(f)=\big\{ \;K(f)_i \;\mid\; i=1,2,\ldots,m \;\big\}.
\]</p>
<p>For the <span class="SimpleMath">\(m \times n\)</span> matrix <code class="code">Ker</code>, which represents the kernel of some Boolean function <span class="SimpleMath">\(f\)</span>, the function <code class="code">ReducedKernelOfBooleanFunction</code> returns the reduced kernel <span class="SimpleMath">\(T(f)\)</span> of <span class="SimpleMath">\(f\)</span>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">## Continuation of Example 2.2.4</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">rk:=ReducedKernelOfBooleanFunction(k[1]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">j:=1;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">for i in rk do Print(j,".\n"); Display(i); Print("\n"); j:=j+1; od;</span>
1.
. . .
. 1 1
1 . 1
2.
. 1 1
. . .
1 1 .
3.
1 . 1
1 1 .
. . .
</pre></div>
<div class="chlinkprevnextbot"> <a href="chap0_mj.html">[Top of Book]</a> <a href="chap0_mj.html#contents">[Contents]</a> <a href="chap1_mj.html">[Previous Chapter]</a> <a href="chap3_mj.html">[Next Chapter]</a> </div>
<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0_mj.html">Top</a> <a href="chap1_mj.html">1</a> <a href="chap2_mj.html">2</a> <a href="chap3_mj.html">3</a> <a href="chap4_mj.html">4</a> <a href="chap5_mj.html">5</a> <a href="chapBib_mj.html">Bib</a> <a href="chapInd_mj.html">Ind</a> </div>
<hr />
<p class="foot">generated by <a href="http://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>
¤ Dauer der Verarbeitung: 0.12 Sekunden
¤
*© Formatika GbR, Deutschland
|
|