<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>
<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="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="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="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>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>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="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="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 <spanclass="SimpleMath">n</span> is the number of variables of <code class="code">Func</code>).</p>
<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>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="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>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="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>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="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 <spanclass="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>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>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
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.
