Quellcodebibliothek Statistik Leitseite products/Sources/formale Sprachen/GAP/pkg/thelma/doc/   (Algebra von RWTH Aachen Version 4.15.1©)  Datei vom 3.2.2022 mit Größe 22 kB image not shown  

Quellcode-Bibliothek chap2.html   Sprache: HTML

 
 products/Sources/formale Sprachen/GAP/pkg/thelma/doc/chap2.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>
<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.html">Top</a>  <a href="chap1.html">1</a>  <a href="chap2.html">2</a>  <a href="chap3.html">3</a>  <a href="chap4.html">4</a>  <a href="chap5.html">5</a>  <a href="chapBib.html">Bib</a>  <a href="chapInd.html">Ind</a>  </div>

<div class="chlinkprevnexttop"> <a href="chap0.html">[Top of Book]</a>   <a href="chap0.html#contents">[Contents]</a>    <a href="chap1.html">[Previous Chapter]</a>    <a href="chap3.html">[Next Chapter]</a>   </div>

<p id="mathjaxlink" class="pcenter"><a href="chap2_mj.html">[MathJax on]</a></p>
<p><a id="X830F6677819A6656" name="X830F6677819A6656"></a></p>
<div class="ChapSects"><a href="chap2.html#X830F6677819A6656">2 <span class="Heading">Boolean Functions</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap2.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.html#X7D8A971A84186BF0">2.1-1 LogicFunction</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X7C34DEE27EC3A009">2.1-2 IsLogicFunction</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X857A4F117BDDF1B6">2.1-3 PolynomialToBooleanFunction</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X78B9DD8E81EE65A8">2.1-4 IsUnateInVariable</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X8203046F7C97EAFE">2.1-5 IsUnateBooleanFunction</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X7D0DEF0B7E9FE027">2.1-6 InfluenceOfVariable</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X86C000FE831CFEDE">2.1-7 SelfDualExtensionOfBooleanFunction</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X7C09D66E84201A77">2.1-8 SplitBooleanFunction</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X8108DE5280908841">2.1-9 KernelOfBooleanFunction</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.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: Z_2^n -> Z_2</span> be a Boolean function. The vector</p>

<p class="pcenter">
  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 ∈ {0,1,...,2^n-1}</span> is the value of <span class="SimpleMath">f(x_1,...,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: Z_k^n -> 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.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">‣ 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">‣ 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.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">‣ 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">‣ 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,... ,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≠ i</span> we have</p>

<p class="pcenter">
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,... ,x_n)</span> is <var class="Arg">negative unate</var> in <span class="SimpleMath">x_i</span> if</p>

<p class="pcenter">
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">‣ 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.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">‣ 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">‣ 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:Z_2^n -> Z_2</span> of <span class="SimpleMath">n</span> variables is a Boolean function <span class="SimpleMath">f^n+1:Z_2^n+1 -> Z_2</span> of <span class="SimpleMath">n+1</span> variables defined as</p>

<p class="pcenter">
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="pcenter">
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 ⊕ 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.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">‣ 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,...,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="pcenter">
\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="pcenter">
f_a(x_1,\ldots,x_n)=0, \quad \textrm{if} \quad x_i=1;
</p>

<p>and</p>

<p class="pcenter">
f_b(x_1,\ldots,x_n)= 0 \quad \textrm{if} \quad x_i=0,\quad
</p>

<p class="pcenter">
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">‣ 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,...,x_n)</span> we define the following two sets (see <a href="chapBib.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="pcenter">
K(f)=f^{-1}(1), \quad \textrm{ if } \quad |f^{-1}(1)| \geq |f^{-1}(0)|;
</p>

<p class="pcenter">
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 ∈ {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">‣ ReducedKernelOfBooleanFunction</code>( <var class="Arg">Ker</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Let <span class="SimpleMath">f(x_1,...,x_n)</span> be a Boolean function with the kernel <span class="SimpleMath">K(f)={ a_1,...,a_m }</span>, where <span class="SimpleMath">m ≤ 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 ∈ K(f)</span> is the following set (see <a href="chapBib.html#biBGecheBovdi80">[ABGG80]</a>):</p>

<p class="pcenter">
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">⊕</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="pcenter">
T(f)=\big\{ \;K(f)_i \;\mid\; i=1,2,\ldots,m  \;\big\}.
</p>

<p>For the <span class="SimpleMath">m × 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.html">[Top of Book]</a>   <a href="chap0.html#contents">[Contents]</a>    <a href="chap1.html">[Previous Chapter]</a>    <a href="chap3.html">[Next Chapter]</a>   </div>


<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a>  <a href="chap1.html">1</a>  <a href="chap2.html">2</a>  <a href="chap3.html">3</a>  <a href="chap4.html">4</a>  <a href="chap5.html">5</a>  <a href="chapBib.html">Bib</a>  <a href="chapInd.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>

100%


¤ Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.0.4Bemerkung:  (vorverarbeitet)  ¤

*Bot Zugriff




Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.