.. -*- coding: utf-8 -*- .. role:: sref(numref) .. role:: xref(numref) .. Copyright (C) 2019, Wolfgang Scherer, .. .. This file is part of Development. .. .. Permission is granted to copy, distribute and/or modify this document .. under the terms of the GNU Free Documentation License, Version 1.3 .. or any later version published by the Free Software Foundation; .. with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. .. A copy of the license is included in the section entitled "GNU .. Free Documentation License". .. inline comments (with du_comment_role) .. role:: rem(comment) .. role:: html(raw) :format: html .. role:: shx(code) :language: sh .. rst-class:: narrow xmedium xlarge xhuge xultra ################################################## :rem:`|||:sec:|||`\ Logic ################################################## .. >>CODD See `the components of a doctoral dissertation and their order `_ .. >>CODD Dedication .. >>CODD Epigraph .. >>CODD Abstract .. compound:: On Wikipedia, the English entry `Truth function`_ has the most elaborate `table of binary truth functions`_ with various representations for all 16 functions. The German entry `Logische Verknüpfung`_ shows a systematic and complete table of all binary Boolean functions, while the English entry `Logical connective`_ does not. The German entry `Boolesche Funktion`_ dicusses general arity of n-ary logical funtions for n=0 (truth values), n=1, n=2. Wikiversity offers an interesting article about `3-ary Boolean functions`_. .. \|:here:| .. >>CODD Introduction .. >>CODD Chapter ================================================== :rem:`|||:sec:|||`\ Logic symbols ================================================== Some logical symbols used in this documentation. See also `List of logic symbols`_ on Wikipedia. +-------------------------+---------+-------+-------------------------------------------------------------------+ | Symbol | Text | Name |Alternatives | +=========================+=========+=======+===================================================================+ | :math:`\neg` | ``!`` | NOT | :math:`\sim` | +-------------------------+---------+-------+-------------------------------------------------------------------+ | :math:`\wedge` | ``&`` | AND | | +-------------------------+---------+-------+-------------------------------------------------------------------+ | :math:`\vee` | ``|`` | OR | | +-------------------------+---------+-------+-------------------------------------------------------------------+ | :math:`\to` | ``->`` | IF | | +-------------------------+---------+-------+-------------------------------------------------------------------+ | :math:`\leftrightarrow` | ``<->`` | IFF | :math:`\Leftrightarrow`, :math:`\equiv` | +-------------------------+---------+-------+-------------------------------------------------------------------+ | :math:`\veebar` | ``^`` | XOR | :math:`\oplus`, :math:`\not\leftrightarrow`, :math:`\not\equiv` | +-------------------------+---------+-------+-------------------------------------------------------------------+ | :math:`\uparrow` | ``!&`` | NAND | | +-------------------------+---------+-------+-------------------------------------------------------------------+ | :math:`\downarrow` | ``!|`` | NOR | | +-------------------------+---------+-------+-------------------------------------------------------------------+ | :math:`\bot` | ``F`` | FALSE | ``0`` | +-------------------------+---------+-------+-------------------------------------------------------------------+ | :math:`\top` | ``T`` | TRUE | ``1`` | +-------------------------+---------+-------+-------------------------------------------------------------------+ ================================================== :rem:`|||:sec:|||`\ Notation ================================================== For index notation of sequences, e.g.: .. math:: \mathop{(x_k)}_{k=0}^{n-1} = {(x_k)}_{k=0}^{n-1} = (x_0, x_1, \dotsc, x_{n-1}) see article `Indexing`_. For mathematical families in general see `Indexed family`_ or `Familie (German)`_. .. _`Familie (German)`: https://de.wikipedia.org/wiki/Familie_(Mathematik) .. _`Indexed family`: https://en.wikipedia.org/wiki/Indexed_family .. _`Indexing`: https://en.wikipedia.org/wiki/Sequence#Indexing For functions, see `Notation for functions`_ and `Table of symbols for functions (German)`_. .. _`Notation for functions`: https://en.wikipedia.org/wiki/Function_(mathematics)#Notation .. _`Table of symbols for functions (German)`: https://de.wikipedia.org/wiki/Funktion_(Mathematik)#Symbolik ================================================== :rem:`|||:sec:|||`\ Combinatorics ================================================== Fundamental logic is mainly governed by variations without repetition (or `n-sequences in X`_\ [#]_): When the ordering of objects matters, and an object can be chosen more than once, we are talking about **variations with repetition**, and the number of variations is: .. math:: c^n where :math:`c` is the number of objects from which you can choose and :math:`n` is the number of objects we can choose (repetitions allowed). (Source: `Variations with repetition`_) .. \||||:here:|||| Distributing :math:`c=2` balls from a sequence :math:`B=(b_0,b_1)=(0,1),` to :math:`n` boxes :math:`x_k`, results in a distribution .. math:: A=\mathop{(x_k)}_{k=0}^{n-1} . Since order matters and there can be more boxes than unique balls are available, the distribution must be **variations with repetition**. The following figure shows an example for distributing :math:`c=2` balls to :math:`n=3` boxes: .. uml:: :html_format: png :latex_format: png :scale: 75% @startditaa /------+------\ B | b0 | b1 | +------+------+ | c5F5 | c4E4 | | 0 | 1 | \------+------/ || | || \------+ |\-----\ | | | | v v v +------+------+------+ A | x0 | x1 | x2 | +------+------+------+ | cAFA | cAFA | c9E9 | | 0 | 0 | 1 | +------+------+------+ @endditaa .. \|:here:| For :math:`c=|B|=2` balls and :math:`n=|A|` boxes, the total number of possible variations :math:`A_j` is :math:`c^n`. The sequence :math:`X` of variations :math:`A_j` is then .. math:: X = \mathop{(A_j)}_{j=0}^{2^n-1} . The following figure shows an example for :math:`n=3 \Rightarrow |X|=8`: .. graphviz:: digraph variations { rankdir=LR; splines=polyline; // 10 e6ffe6 cfe6cf // 20 ccffcc // // 40 99ff99 8ae68a // 50 80ff80 // // 70 4dff4d 45e645 // 80 33ff33 // // 100 00ff00 00e600 00cc00 subgraph cluster_table_A { node [fontname="FreeSans",fontsize="12",shape=record]; table_A [shape=plaintext,label=<
x0 x1 x2 X
000 A0
001 A1
010 A2
011 A3
100 A4
101 A5
110 A6
111 A7
>,style=solid]; } subgraph cluster_tree_A { node [fontname="FreeSans",fontsize="12",shape=circle]; // ↦ // -> AL111 [shape=plaintext,label=<
111
A7 ↦ y7
>] AL110 [shape=plaintext,label=<
110
A6 ↦ y6
>] AL101 [shape=plaintext,label=<
101
A5 ↦ y5
>] AL100 [shape=plaintext,label=<
100
A4 ↦ y4
>] AL011 [shape=plaintext,label=<
011
A3 ↦ y3
>] AL010 [shape=plaintext,label=<
010
A2 ↦ y2
>] AL001 [shape=plaintext,label=<
001
A1 ↦ y1
>] AL000 [shape=plaintext,label=<
000
A0 ↦ y0
>] AL11 [label="11",shape=diamond,fillcolor="#8ae68a",style=filled]; AL10 [label="10",shape=diamond,fillcolor="#99ff99",style=filled]; AL01 [label="01",shape=diamond,fillcolor="#8ae68a",style=filled]; AL00 [label="00",shape=diamond,fillcolor="#99ff99",style=filled]; AL1 [label="1",shape=diamond,fillcolor="#cfe6cf",style=filled]; AL0 [label="0",shape=diamond,fillcolor="#e6ffe6",style=filled]; A [shape=oval]; A -> AL0; A -> AL1; AL0 -> AL00; AL0 -> AL01; AL1 -> AL10; AL1 -> AL11; AL00 -> AL000; AL00 -> AL001; AL01 -> AL010; AL01 -> AL011; AL10 -> AL100; AL10 -> AL101; AL11 -> AL110; AL11 -> AL111; } table_A -> A [style=invis]; // 10 ffece6 e6d5cf // 20 ffdacc e6c4b8 // 30 ffc7b3 e6b3a1 // 40 ffb499 e6a28a // 50 ffa280 e69173 // 60 ff8f66 e6805c // 70 ff7c4d e66f45 // 80 ff6933 e65e2e // 00 e63d00 cc3600 subgraph cluster_table_Y { node [fontname="FreeSans",fontsize="12",shape=record]; table_Y [shape=plaintext,label=<
Y Y0 Y1 Y2 Y3
y0 0 0 0 0
y1 0 0 0 0
y2 0 0 0 0
y3 0 0 0 0
y4 0 0 0 0
y5 0 0 0 0
y6 0 0 1 1
y7 0 1 0 1
>,style=solid]; } AL011 -> table_Y [style=invis]; AL100 -> table_Y [style=invis]; } .. \|:here:| Correlating each distribution :math:`A_j` to a new box :math:`y_j` generates a sequence of boxes .. math:: Y = \mathop{(y_j)}_{j=0}^{2^n-1}, The number of possible distributions for :math:`2` balls to boxes :math:`y_j` is :math:`2^{|Y|} = 2^{2^n}`, which generates a sequence of distributions .. math:: F = \mathop{(Y_i)}_{i=0}^{2^{2^n}-1} . The following figure shows an example for :math:`n=3 \Rightarrow |A|=8 \Rightarrow |F|=256`: .. \|:here:| .. graphviz:: digraph variations { // rankdir=LR; splines=polyline; // 10 ffece6 e6d5cf // 20 ffdacc e6c4b8 // 30 ffc7b3 e6b3a1 // 40 ffb499 e6a28a // 50 ffa280 e69173 // 60 ff8f66 e6805c // 70 ff7c4d e66f45 // 80 ff6933 e65e2e // 00 e63d00 cc3600 subgraph cluster_table_Y { node [fontname="FreeSans",fontsize="12",shape=record]; table_Y [shape=plaintext,label=<
Y Y0 Y1 Y2 Y3
y0 0 0 0 0
y1 0 0 0 0
y2 0 0 0 0
y3 0 0 0 0
y4 0 0 0 0
y5 0 0 0 0
y6 0 0 1 1
y7 0 1 0 1
>,style=solid]; } subgraph cluster_tree_Y { node [fontname="FreeSans",fontsize="12",shape=circle]; YL0 [label="0" ,shape=diamond,style=filled,fillcolor="#ffece6"]; YL00 [label="00" ,shape=diamond,style=filled,fillcolor="#ffdacc"]; YL000 [label="000" ,shape=diamond,style=filled,fillcolor="#ffc7b3"]; YL0000 [label="0000" ,shape=diamond,style=filled,fillcolor="#ffb499"]; YL00000 [label="00000" ,shape=diamond,style=filled,fillcolor="#ffa280"]; YL000000 [label="000000" ,shape=diamond,style=filled,fillcolor="#ff8f66"]; YL0000000 [label="0000000" ,shape=diamond,style=filled,fillcolor="#ff7c4d"]; YL00000000 [shape=plaintext,label=<
00000000
Y0
>] YL00000001 [shape=plaintext,label=<
00000001
Y1
>] YL0000001 [label="0000001" ,shape=diamond,style=filled,fillcolor="#e66f45"]; YL00000010 [shape=plaintext,label=<
00000010
Y2
>] YL00000011 [shape=plaintext,label=<
00000011
Y3
>] YL000001 [label="000001" ,shape=diamond,style=filled,fillcolor="#e6805c"]; YL00001 [label="00001" ,shape=diamond,style=filled,fillcolor="#e69173"]; YL0001 [label="0001" ,shape=diamond,style=filled,fillcolor="#e6a28a"]; YL001 [label="001" ,shape=diamond,style=filled,fillcolor="#e6b3a1"]; YL01 [label="01" ,shape=diamond,style=filled,fillcolor="#e6c4b8"]; YL1 [label="1" ,shape=diamond,style=filled,fillcolor="#e6d5cf"]; YL10 [label="10" ,shape=diamond,style=filled,fillcolor="#ffdacc"]; YL11 [label="11" ,shape=diamond,style=filled,fillcolor="#e6c4b8"]; YL110 [label="110" ,shape=diamond,style=filled,fillcolor="#ffc7b3"]; YL111 [label="111" ,shape=diamond,style=filled,fillcolor="#e6b3a1"]; YL1110 [label="1110" ,shape=diamond,style=filled,fillcolor="#ffb499"]; YL1111 [label="1111" ,shape=diamond,style=filled,fillcolor="#e6a28a"]; YL11110 [label="11110" ,shape=diamond,style=filled,fillcolor="#ffa280"]; YL11111 [label="11111" ,shape=diamond,style=filled,fillcolor="#e69173"]; YL111110 [label="111110" ,shape=diamond,style=filled,fillcolor="#ff8f66"]; YL111111 [label="111111" ,shape=diamond,style=filled,fillcolor="#e6805c"]; YL1111110 [label="1111110" ,shape=diamond,style=filled,fillcolor="#ff7c4d"]; YL11111100 [shape=plaintext,label=<
11111100
Y252
>] YL11111101 [shape=plaintext,label=<
11111101
Y253
>] YL1111111 [label="1111111" ,shape=diamond,style=filled,fillcolor="#e66f45"]; YL11111110 [shape=plaintext,label=<
11111110
Y254
>] YL11111111 [shape=plaintext,label=<
11111111
Y255
>] Y [shape=oval]; Y -> YL0; Y -> YL1; YL0 -> YL00; YL0 -> YL01; YL00 -> YL000; YL00 -> YL001; YL000 -> YL0000 ; YL000 -> YL0001 ; YL0000 -> YL00000 ; YL0000 -> YL00001 ; YL00000 -> YL000000 ; YL00000 -> YL000001 ; YL000000 -> YL0000000 ; YL000000 -> YL0000001 ; YL0000000 -> YL00000000; YL0000000 -> YL00000001; YL0000001 -> YL00000010; YL0000001 -> YL00000011; YL1 -> YL10; YL1 -> YL11; YL11 -> YL110; YL11 -> YL111; YL111 -> YL1110; YL111 -> YL1111; YL1111 -> YL11110; YL1111 -> YL11111; YL11111 -> YL111110; YL11111 -> YL111111; YL111110 -> YL1111110; YL111111 -> YL1111111; YL1111110 -> YL11111100; YL1111110 -> YL11111101; YL1111111 -> YL11111110; YL1111111 -> YL11111111; } YL11111110 -> table_Y [style=invis]; YL00000001 -> table_Y [style=invis]; } .. \|:here:| ====================================================== :rem:`|||:sec:|||`\ Boolean functions and truth tables ====================================================== Quoting from article `Boolean function`_: In mathematics and logic, a (finitary) Boolean function (or switching function) is a function of the form :math:`ƒ : B^{\,n} \rightarrow B`, where :math:`B = (0, 1)` is a Boolean domain and :math:`n` is a non-negative integer called the arity of the function. In the case where :math:`n = 0`, the "function" is essentially a constant element of :math:`B`. Every :math:`n`-ary Boolean function can be expressed as a propositional formula in :math:`n` variables :math:`x_0, \dotsc, x_n`. .. _`Boolean function`: https://en.wikipedia.org/wiki/Boolean_function Boolean functions are classified by arity :math:`n \in \mathbb{N}_0` as :math:`f^n : B^{\,n} \to B^{\,1}`, such that each function :math:`f^n` maps a sequence :math:`A=\mathop{(x_k)}_{k=0}^{n-1}` of :math:`n` values :math:`x_k \in B` to a single value :math:`y \in B`: .. math:: f^n : A \mapsto y . The number of possible variations for :math:`A` is :math:`|(B \rightarrow A)| = |B|^{|A|} = 2^n`, which generates the sequence of possible input variations .. math:: X=\mathop{\left(A_j\right)}_{j=0}^{2^n-1} , and the corresponding sequence of output values .. math:: Y=\mathop{(y_j)}_{j=0}^{2^n-1} . The number of possible output sequences is :math:`|(B \rightarrow Y)| = |B|^{|Y|} = 2^{2^n}`. Therefore the sequence :math:`F^n` of :math:`n`-ary Boolean functions is .. math:: F^n = {\left(f^{n}_{i} \left| \begin{split} f^{n}_{i} :\,& X \rightarrow Y_i,\\ &A_j \mapsto y_j\\ \end{split} \right. \right)}_{i=0}^{2^{2^n}-1} . A truth table defines a function :math:`f^n_i` by specifying an output value :math:`y_j` for each combination :math:`A_j` of input values :math:`x_k`. -------------------------------------------------- :rem:`||:sec:||`\ Universal lookup function -------------------------------------------------- The order of sequences :math:`F^n, X, Y` is defined such that each truth table row :math:`j` .. math:: f^n_i(A_j) = y_j can be calculated independently given arity :math:`n`, function index :math:`i` and output value index :math:`j`. Function :math:`\mathrm{bin}(d,m)` converts an integer :math:`d` into a sequence of binary digits: .. math:: \mathrm{bin}(d,m) : d \mapsto (b_e|b_e = \left\lfloor\frac{d}{2^{m-1-e}}\right\rfloor \bmod 2)_{e=0}^{m-1}, d \in \mathbb{N}_0, b_e \in B . The sequence of output values :math:`Y_i` for :math:`f^n_i` is generated by .. math:: Y_i = \mathrm{bin}(i, 2^n) . The truth table row :math:`j` is then defined by .. math:: f^n_i(A_j) = Y_{i_j} . Given :math:`f^{3}_{23}`, the sequence of ouptut values :math:`Y_{23}` is :math:`(0,0,0,1,0,1,1,1)` and truth table row :math:`j=3` is then defined by :math:`f^{3}_{23}(0, 1, 1) = 1`. The follwing table shows the complete complete truth table for :math:`f^{3}_{23}`: +-----------------------+-------------+-------------+-------------++--------------------+ | :math:`k \rightarrow` | 0 | 1 | 2 || | +-----------------------+-------------+-------------+-------------++--------------------+ | :math:`j \downarrow` | :math:`x_0` | :math:`x_1` | :math:`x_2` || :math:`f^{3}_{23}` | +=======================+=============+=============+=============++====================+ | 0 | 0 | 0 | 0 || 0 | +-----------------------+-------------+-------------+-------------++--------------------+ | 1 | 0 | 0 | 1 || 0 | +-----------------------+-------------+-------------+-------------++--------------------+ | 2 | 0 | 1 | 0 || 0 | +-----------------------+-------------+-------------+-------------++--------------------+ | 3 | 0 | 1 | 1 || 1 | +-----------------------+-------------+-------------+-------------++--------------------+ | 4 | 1 | 0 | 0 || 0 | +-----------------------+-------------+-------------+-------------++--------------------+ | 5 | 1 | 0 | 1 || 1 | +-----------------------+-------------+-------------+-------------++--------------------+ | 6 | 1 | 1 | 0 || 1 | +-----------------------+-------------+-------------+-------------++--------------------+ | 7 | 1 | 1 | 1 || 1 | +-----------------------+-------------+-------------+-------------++--------------------+ -------------------------------------------------- :rem:`||:sec:||`\ Nullary Boolean functions -------------------------------------------------- These are the truth constants from :math:`B` expressed as functions :math:`(f^0_i())_{i=0}^1` without parameters. +-------------------+-------------------+ | :math:`f^{0}_{0}` | :math:`f^{0}_{1}` | +-------------------+-------------------+ | :math:`\bot` | :math:`\top` | +===================+===================+ | 0 | 1 | +-------------------+-------------------+ -------------------------------------------------- :rem:`||:sec:||`\ Unary Boolean functions -------------------------------------------------- +-----------++-------------------+-------------------+-------------------+-------------------+ | || :math:`f^{1}_{0}` | :math:`f^{1}_{1}` | :math:`f^{1}_{2}` | :math:`f^{1}_{3}` | +-----------++-------------------+-------------------+-------------------+-------------------+ | :math:`p` || :math:`\bot` | :math:`p` | :math:`\neg p` | :math:`\top` | +===========++===================+===================+===================+===================+ | 0 || 0 | 0 | 1 | 1 | +-----------++-------------------+-------------------+-------------------+-------------------+ | 1 || 0 | 1 | 0 | 1 | +-----------++-------------------+-------------------+-------------------+-------------------+ -------------------------------------------------- :rem:`||:sec:||`\ Binary Boolean functions -------------------------------------------------- +-----------+-----------++-------------------+-------------------+-------------------+-------------------+--------------------------+-------------------+-------------------+-------------------+----------------------+---------------------------+--------------------+----------------------+--------------------+-----------------------+--------------------+--------------------+ | | || :math:`f^{2}_{0}` | :math:`f^{2}_{1}` | :math:`f^{2}_{2}` | :math:`f^{2}_{3}` | :math:`f^{2}_{4}` | :math:`f^{2}_{5}` | :math:`f^{2}_{6}` | :math:`f^{2}_{7}` | :math:`f^{2}_{8}` | :math:`f^{2}_{9}` | :math:`f^{2}_{10}` | :math:`f^{2}_{11}` | :math:`f^{2}_{12}` | :math:`f^{2}_{13}` | :math:`f^{2}_{14}` | :math:`f^{2}_{15}` | +-----------+-----------++-------------------+-------------------+-------------------+-------------------+--------------------------+-------------------+-------------------+-------------------+----------------------+---------------------------+--------------------+----------------------+--------------------+-----------------------+--------------------+--------------------+ | :math:`p` | :math:`q` || :math:`\bot` | :math:`\wedge` | :math:`\not\to` | :math:`p` | :math:`\not\leftarrow` | :math:`q` | :math:`\veebar` | :math:`\vee` | :math:`\downarrow` | :math:`\leftrightarrow` | :math:`\neg q` | :math:`\leftarrow` | :math:`\neg p` | :math:`\rightarrow` | :math:`\uparrow` | :math:`\top` | +===========+===========++===================+===================+===================+===================+==========================+===================+===================+===================+======================+===========================+====================+======================+====================+=======================+====================+====================+ | 0 | 0 || 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | +-----------+-----------++-------------------+-------------------+-------------------+-------------------+--------------------------+-------------------+-------------------+-------------------+----------------------+---------------------------+--------------------+----------------------+--------------------+-----------------------+--------------------+--------------------+ | 0 | 1 || 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | +-----------+-----------++-------------------+-------------------+-------------------+-------------------+--------------------------+-------------------+-------------------+-------------------+----------------------+---------------------------+--------------------+----------------------+--------------------+-----------------------+--------------------+--------------------+ | 1 | 0 || 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | +-----------+-----------++-------------------+-------------------+-------------------+-------------------+--------------------------+-------------------+-------------------+-------------------+----------------------+---------------------------+--------------------+----------------------+--------------------+-----------------------+--------------------+--------------------+ | 1 | 1 || 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | +-----------+-----------++-------------------+-------------------+-------------------+-------------------+--------------------------+-------------------+-------------------+-------------------+----------------------+---------------------------+--------------------+----------------------+--------------------+-----------------------+--------------------+--------------------+ ================================================== :rem:`|||:sec:|||`\ Mask operation ================================================== Let :math:`m, d, b \in B`, let :math:`g^1_c \in F^1` be an arbitrary unary logical function. Then an operation :math:`\mbox{O}_{\mbox{mask}} : B^{\,2} \to B^{\,1}` is a mask operation, iff for all combinations of input bits :math:`\mathop{\left((m, d)_j\right)}_{j=0}^{2^2}` there exists a constant :math:`b` so that function :math:`f^2_i(m, d) = d`, if :math:`m = b`, and :math:`f^2_i(m, d) = g^1_c(d)`, if :math:`m = \neg b`. .. math:: \mbox{O}_{\mbox{mask}}: B^{\,2} \to B^{\,1} \Leftrightarrow \forall m, d\, \exists b : f^2_i(m, d) = \left\{ \begin{array}{ll} d & \mbox{if}\,\, m = b\\ g^1_c(d) & \mbox{if}\,\, m = \neg b \end{array} \right. Truth table, using :math:`p` as mask bit, :math:`q` as data bit: +-----------+-----------++-------------------+-------------------+-------------------+-------------------+--------------------------+-------------------+-------------------+-------------------+----------------------+---------------------------+--------------------+----------------------+--------------------+-----------------------+--------------------+--------------------+ | | || :math:`f^{2}_{0}` | :math:`f^{2}_{1}` | :math:`f^{2}_{2}` | :math:`f^{2}_{3}` | :math:`f^{2}_{4}` | :math:`f^{2}_{5}` | :math:`f^{2}_{6}` | :math:`f^{2}_{7}` | :math:`f^{2}_{8}` | :math:`f^{2}_{9}` | :math:`f^{2}_{10}` | :math:`f^{2}_{11}` | :math:`f^{2}_{12}` | :math:`f^{2}_{13}` | :math:`f^{2}_{14}` | :math:`f^{2}_{15}` | +-----------+-----------++-------------------+-------------------+-------------------+-------------------+--------------------------+-------------------+-------------------+-------------------+----------------------+---------------------------+--------------------+----------------------+--------------------+-----------------------+--------------------+--------------------+ | :math:`m` | :math:`d` || :math:`\bot` | :math:`\wedge` | :math:`\not\to` | :math:`m` | :math:`\not\leftarrow` | :math:`d` | :math:`\veebar` | :math:`\vee` | :math:`\downarrow` | :math:`\leftrightarrow` | :math:`\neg d` | :math:`\leftarrow` | :math:`\neg m` | :math:`\rightarrow` | :math:`\uparrow` | :math:`\top` | +===========+===========++===================+===================+===================+===================+==========================+===================+===================+===================+======================+===========================+====================+======================+====================+=======================+====================+====================+ | 0 | 0 || 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | +-----------+-----------++-------------------+-------------------+-------------------+-------------------+--------------------------+-------------------+-------------------+-------------------+----------------------+---------------------------+--------------------+----------------------+--------------------+-----------------------+--------------------+--------------------+ | 0 | 1 || 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | +-----------+-----------++-------------------+-------------------+-------------------+-------------------+--------------------------+-------------------+-------------------+-------------------+----------------------+---------------------------+--------------------+----------------------+--------------------+-----------------------+--------------------+--------------------+ | 1 | 0 || 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | +-----------+-----------++-------------------+-------------------+-------------------+-------------------+--------------------------+-------------------+-------------------+-------------------+----------------------+---------------------------+--------------------+----------------------+--------------------+-----------------------+--------------------+--------------------+ | 1 | 1 || 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | +-----------+-----------++-------------------+-------------------+-------------------+-------------------+--------------------------+-------------------+-------------------+-------------------+----------------------+---------------------------+--------------------+----------------------+--------------------+-----------------------+--------------------+--------------------+ Only those functions qualify as candidates for mask operations, which either have 2 entries for :math:`f^2_i(m, d)` with :math:`f^2_i(0, 0) = 0` and :math:`f^2_i(0, 1) = 1`, or 2 entries with :math:`f^2_i(1, 0) = 0` and :math:`f^2_i(1, 1) = 1`: +-----------+-----------++-------------------+--------------------------+-------------------+-------------------+-------------------+---------------------------+-----------------------+ | | || :math:`f^{2}_{1}` | :math:`f^{2}_{4}` | :math:`f^{2}_{5}` | :math:`f^{2}_{6}` | :math:`f^{2}_{7}` | :math:`f^{2}_{9}` | :math:`f^{2}_{13}` | +-----------+-----------++-------------------+--------------------------+-------------------+-------------------+-------------------+---------------------------+-----------------------+ | :math:`m` | :math:`d` || :math:`\wedge` | :math:`\not\leftarrow` | :math:`d` | :math:`\veebar` | :math:`\vee` | :math:`\leftrightarrow` | :math:`\rightarrow` | +===========+===========++===================+==========================+===================+===================+===================+===========================+=======================+ | 0 | 0 || 0 | 0 | 0 | 0 | 0 | 1 | 1 | +-----------+-----------++-------------------+--------------------------+-------------------+-------------------+-------------------+---------------------------+-----------------------+ | 0 | 1 || 0 | 1 | 1 | 1 | 1 | 0 | 1 | +-----------+-----------++-------------------+--------------------------+-------------------+-------------------+-------------------+---------------------------+-----------------------+ | 1 | 0 || 0 | 0 | 0 | 1 | 1 | 0 | 0 | +-----------+-----------++-------------------+--------------------------+-------------------+-------------------+-------------------+---------------------------+-----------------------+ | 1 | 1 || 1 | 0 | 1 | 0 | 1 | 1 | 1 | +-----------+-----------++-------------------+--------------------------+-------------------+-------------------+-------------------+---------------------------+-----------------------+ -------------------------------------------------- :rem:`||:sec:||`\ Clearing data bits -------------------------------------------------- :math:`f^{2}_{1}` (AND) allows clearing data bits by setting the corresponding mask value to 0. For mask values of 1, the data bits remain unmodified (:math:`b=1, g^1_c=f^{1}_{0}`): +------+-----+-----+-----+-----+-----+-----+-----+-----+ | MASK | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | +------+-----+-----+-----+-----+-----+-----+-----+-----+ | DATA | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | +------+-----+-----+-----+-----+-----+-----+-----+-----+ | AND | |v| | |v| | |v| | |v| | |v| | |v| | |v| | |v| | +------+-----+-----+-----+-----+-----+-----+-----+-----+ | RES | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | +------+-----+-----+-----+-----+-----+-----+-----+-----+ -------------------------------------------------- :rem:`||:sec:||`\ Setting data bits -------------------------------------------------- :math:`f^{2}_{7}` (OR) allows setting data bits by setting the corresponding mask value to 1. For mask values of 0, the data bits remain unmodified (:math:`b=0, g^1_c=f^{1}_{3}`): +------+-----+-----+-----+-----+-----+-----+-----+-----+ | MASK | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | +------+-----+-----+-----+-----+-----+-----+-----+-----+ | DATA | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | +------+-----+-----+-----+-----+-----+-----+-----+-----+ | OR | |v| | |v| | |v| | |v| | |v| | |v| | |v| | |v| | +------+-----+-----+-----+-----+-----+-----+-----+-----+ | RES | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | +------+-----+-----+-----+-----+-----+-----+-----+-----+ -------------------------------------------------- :rem:`||:sec:||`\ Inverting data bits -------------------------------------------------- :math:`f^{2}_{6}` (XOR) allows inverting data bits by setting the corresponding mask value to 1. For mask values of 0, the data bits remain unmodified (:math:`b=0, g^1_c=f^{1}_{2}`): +------+-----+-----+-----+-----+-----+-----+-----+-----+ | MASK | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | +------+-----+-----+-----+-----+-----+-----+-----+-----+ | DATA | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | +------+-----+-----+-----+-----+-----+-----+-----+-----+ | XOR | |v| | |v| | |v| | |v| | |v| | |v| | |v| | |v| | +------+-----+-----+-----+-----+-----+-----+-----+-----+ | RES | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | +------+-----+-----+-----+-----+-----+-----+-----+-----+ Special mask operations are: .. math:: \begin{array}{llll} \hphantom{\neg}f^{2}_{6}(m, \hphantom{\neg}m) & = & \hphantom{\neg}(m \veebar \hphantom{\neg}m) & = 0\\ \hphantom{\neg}f^{2}_{6}(m, \neg m) & = & \hphantom{\neg}(m \veebar \neg m) & = 1\\ \neg f^{2}_{6}(m, \hphantom{\neg}m) & = & \neg (m \veebar \hphantom{\neg}m) & = 1 \end{array} .. |v| replace:: :math:`\downarrow` -------------------------------------------------- :rem:`||:sec:||`\ Other mask operations -------------------------------------------------- The other mask operations can all be expressed in terms of AND, OR, XOR. :math:`f^{2}_{4}` allows clearing data bits by setting the corresponding mask value to 1. For mask values of 0, the data bits remain unmodified (:math:`b=0, g^1_c=f^{1}_{0}`). This can simply be replaced by inverting the mask bits and performing an AND operation: .. math:: f^{2}_{4}(m, d) = f^{2}_{1}(\neg m, d) = \neg m \wedge d :math:`f^{2}_{5}` leaves all data bits unmodified (:math:`b=0, g^1_c=f^{1}_{1}` and :math:`b=1, g^1_c=f^{1}_{1}`). It is therefore really a NOOP, i.e., just using the data bits is sufficient. However, to fulfill the requirements of a binary operation with arbitrary mask bits, any mask operation can be used by transforming the mask so as to leave the data bits unmodified. .. math:: \begin{array}{lllll} f^{2}_{5}(m, d) & = f^{2}_{1}(f^{2}_{6}(m,\neg m), d) & = (m \veebar \neg m) \wedge d & = 1 \wedge d\\ f^{2}_{5}(m, d) & = f^{2}_{7}(f^{2}_{6}(m,\hphantom{\neg}m), d) & = (m \veebar \hphantom{\neg}m) \vee d & = 0 \vee d\\ f^{2}_{5}(m, d) & = f^{2}_{6}(f^{2}_{6}(m,\hphantom{\neg}m), d) & = (m \veebar \hphantom{\neg}m) \veebar d & = 0 \veebar d \end{array} :math:`f^{2}_{9}` (IFF) allows inverting data bits by setting the corresponding mask value to 0. For mask values of 1, the data bits remain unmodified (:math:`b=1, g^1_c=f^{1}_{2}`). This can be achieved, by inverting the mask for :math:`f^{2}_{7}`: .. math:: f^{2}_{9}(m, d) = f^{2}_{7}(\neg m, d) = \neg m \veebar d :math:`f^{2}_{13}` allows setting data bits by setting the corresponding mask value to 0. For mask values of 1, the data bits remain unmodified (:math:`b=1, g=f^{1}_{3}`). This can be achieved by inverting the mask for :math:`f^{2}_{6}`: .. math:: f^{2}_{13}(m, d) = f^{2}_{6}(\neg m, d) = \neg m \vee d ================================================== :rem:`|||:sec:|||`\ Functional completeness ================================================== - See `Truth Function, section Functional completeness `_ and main article `Functional completeness`_. - See also "You cannot NOT have NOT" in `Is XOR a combination of AND and NOT operators?`_. It is established that functions NOT and AND are sufficient to generate all other binary logical functions. Since function AND can be generated with functions NOT and OR: .. math:: \begin{array}{ll} &(p \wedge q)\\ =&\neg(\neg(p \wedge q)))\\ =&\neg(\neg p \vee \neg q), \end{array} functions NOT and OR are also functionally complete. When looking for a single binary Boolean function that is functionally complete, candidates are all functions that generate a unary NOT: :math:`f^2_i(p,p) = \neg p`: +-----------+-----------++----------------------+--------------------+--------------------+--------------------+ | | || :math:`f^{2}_{8}` | :math:`f^{2}_{10}` | :math:`f^{2}_{12}` | :math:`f^{2}_{14}` | +-----------+-----------++----------------------+--------------------+--------------------+--------------------+ | :math:`p` | :math:`q` || :math:`\downarrow` | :math:`\neg q` | :math:`\neg p` | :math:`\uparrow` | +===========+===========++======================+====================+====================+====================+ | 0 | 0 || 1 | 1 | 1 | 1 | +-----------+-----------++----------------------+--------------------+--------------------+--------------------+ | 1 | 1 || 0 | 0 | 0 | 0 | +-----------+-----------++----------------------+--------------------+--------------------+--------------------+ this identifies :math:`f^{2}_{8}` (NOR), :math:`f^{2}_{10}` (:math:`\neg q`), :math:`f^{2}_{12}` (:math:`\neg p`), :math:`f^{2}_{14}` (NAND). Functions :math:`f^{2}_{10}` and :math:`f^{2}_{12}` are actually unary functions, each ignoring one of the inputs while negating the other. Since they are equivalent to a unary negation, they cannot be functionally complete, as NOT by itself is not functionally complete. +-----------+-----------++--------------------+--------------------+ | | || :math:`f^{2}_{10}` | :math:`f^{2}_{12}` | +-----------+-----------++--------------------+--------------------+ | :math:`p` | :math:`q` || :math:`\neg q` | :math:`\neg p` | +===========+===========++====================+====================+ | 0 | 0 || 1 | 1 | +-----------+-----------++--------------------+--------------------+ | 0 | 1 || 0 | 1 | +-----------+-----------++--------------------+--------------------+ | 1 | 0 || 1 | 0 | +-----------+-----------++--------------------+--------------------+ | 1 | 1 || 0 | 0 | +-----------+-----------++--------------------+--------------------+ However, functions :math:`f^{2}_{8}` (NOR) and :math:`f^{2}_{14}` (NAND) are already very close to the functions AND and OR. Both provide NOT via :math:`f^2_{8}(p,p) = f^2_{14}(p,p) = \neg p` as shown above. +-----------+-----------++----------------------+--------------------+ | | || :math:`f^{2}_{8}` | :math:`f^{2}_{14}` | +-----------+-----------++----------------------+--------------------+ | :math:`p` | :math:`q` || :math:`\downarrow` | :math:`\uparrow` | +===========+===========++======================+====================+ | 0 | 0 || 1 | 1 | +-----------+-----------++----------------------+--------------------+ | 0 | 1 || 0 | 1 | +-----------+-----------++----------------------+--------------------+ | 1 | 0 || 0 | 1 | +-----------+-----------++----------------------+--------------------+ | 1 | 1 || 0 | 0 | +-----------+-----------++----------------------+--------------------+ :math:`f^{2}_{8}` (NOR) can be used to express :math:`f^{2}_{7}` (OR) as: .. math:: \begin{array}{ll} \neg p &= p \downarrow p\\ p \vee q &= \neg ( p \downarrow q )\\ p \vee q &= ( p \downarrow q ) \downarrow ( p \downarrow q ), \end{array} which makes :math:`f^{2}_{8}` functionally complete. :math:`f^{2}_{14}` (NAND) can be used to express :math:`f^{2}_{1}` (AND) as: .. math:: \begin{array}{ll} \neg p &= p \uparrow p\\ p \wedge q &= \neg ( p \uparrow q )\\ p \wedge q &= ( p \uparrow q ) \uparrow ( p \uparrow q ), \end{array} which makes :math:`f^{2}_{14}` functionally complete. For :math:`\{\mathrm{AND}, \mathrm{XOR}, \top\}`, negation can be expressed as: .. math:: \neg p = \top \veebar p. The resulting set of functions :math:`\{\mathrm{AND}, \mathrm{XOR}, \top, \mathrm{NOT}\}` is a superset of the functionally complete set :math:`\{\mathrm{AND}, \mathrm{NOT}\}`, and therefore also functionally complete. -------------------------------------------------------------------------------------------- :rem:`||:sec:||`\ Composition of Boolean functions with NOT and AND -------------------------------------------------------------------------------------------- .. |BOTx| replace:: :math:`f^{0}_{0}` aka ( FALSE , F , :math:`\bot` ) .. |TOPx| replace:: :math:`f^{0}_{1}` aka ( TRUE , T , :math:`\top` ) .. |NOTx| replace:: :math:`f^{1}_{2}` aka ( NOT , :math:`\neg` ) .. |ANDx| replace:: :math:`f^{2}_{1}` aka ( AND , :math:`\wedge` ) .. |ORx| replace:: :math:`f^{2}_{7}` aka ( OR , :math:`\vee` ) Proposition: All Boolean functions in :math:`F^n, n \in \mathbb{N}_0` can be composed from Boolean functions |NOTx| and |ANDx|. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ :rem:`|:sec:|`\ Composing nullary functions from NOT and AND ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Article `Truth Function`_ argues that only functions in :math:`F^m, m \in \mathbb{N}` can be composed. However, the nullary function |BOTx| is quite obviously equivalent to all functions :math:`f^m_0` for all combinations of input values :math:`((x_k)_j)`: .. math:: f^{m}_{0}(x_0, x_1, \dotsc, x_{m-1}) = f^{m-1}_{0}(x_0, x_1, \dotsc, x_{m-2}) . So any function :math:`f^{m}_{0}` with arbitrary input values can always be reduced to :math:`f^{0}_{0}`: .. math:: f^{2}_{0}(p, q) = f^{1}_{0}(p) = f^{0}_{0}(). When trying to expand a function :math:`f^{n}_{0}` to :math:`f^{n+1}_{0}`, the problem arises, where the input variables should come from: .. math:: f^{0}_{0}() = f^{1}_{0}(\dotsc) = f^{2}_{0}(\dotsc) . An obvious choice would be constant values, which avoids inventing arbitrary variables: .. math:: f^{0}_{0}() = f^{1}_{0}(0) = f^{2}_{0}(0,0) . Another possibility is using a variable symbol like :math:`\phi`, that is not generally used: .. math:: f^{0}_{0}() = f^{1}_{0}(\phi) = f^{2}_{0}(\phi, \phi) , which makes all functions :math:`f^n_0` equivalent: .. math:: f^{n}_{0}(x_0, x_1, \dotsc, x_{n-1}) = f^{n+1}_{0}(x_0, x_1, \dotsc, x_{n-1}, \phi) . Therefore :math:`f^0_0` is proved expressable by a set of functions if any representative :math:`f^{n}_{0}` can be composed. :math:`f^{1}_{0}` and :math:`f^{2}_{0}` can be defined by NOT and AND in various ways, which are all equivalent t0 :math:`f^{0}_{0}`: .. math:: \begin{array}{lll} f^{1}_{0}(p) &= f^{2}_{1}(p,f^{1}_{2}(p)) &= p \wedge \neg p,\\ f^{2}_{0}(p, q) &= f^{2}_{1}(f^{2}_{1}(p,q),f^{1}_{2}(f^{2}_{1}(p,q))) &= (p \wedge q ) \wedge \neg (p \wedge q ),\\ &= f^{1}_{0}(f^{2}_{1}(p,q)) &= (p \wedge q ) \wedge \neg (p \wedge q ),\\ &= f^{2}_{1}(f^{1}_{0}(p),f^{1}_{0}(q)) &= (p \wedge \neg p) \wedge (q \wedge \neg q),\\ &= f^{2}_{1}(p,f^{1}_{0}(q)) &= p \wedge (q \wedge \neg q),\\ &= f^{2}_{1}(f^{1}_{0}(p),q) &= (p \wedge \neg p) \wedge q . \end{array} The expression .. math:: f^{2}_{1}(\phi,f^{1}_{2}(\phi)) is used to expand :math:`f^0_0`. This ensures that the full expansion of a formula contains only the functions :math:`f^1_2` and :math:`f^2_1`, formally satisfying functional completeness. Trivially the nullary function |TOPx| is defined as negation of :math:`f^{0}_{0}`: .. math:: f^{0}_{1} = f^{1}_{2}(f^{0}_{0}()) = \neg \bot = \top . ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ :rem:`|:sec:|`\ Convenience definition of OR ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ It is convenient to use |ORx| in addition to NOT and AND, so this is proved first by induction over the complete truth table: .. math:: &p \vee q = \neg ( \neg ( p \vee q )) = \neg ( \neg p \wedge \neg q )\\ &f^{2}_{7}(p,q) = f^{1}_{2}( f^{2}_{1}( f^{1}_{2}(p), f^{1}_{2}(q) ) ) +-----------+-----------++----------------+----------------+------------------------------+------------------------------------+------------------------------+ | :math:`p` | :math:`q` || :math:`\neg p` | :math:`\neg q` | :math:`\neg p \wedge \neg q` | :math:`\neg(\neg p \wedge \neg q)` | :math:`f^{2}_{7}(p,q), \vee` | +===========+===========++================+================+==============================+====================================+==============================+ | 0 | 0 || 1 | 1 | 1 | 0 | 0 | +-----------+-----------++----------------+----------------+------------------------------+------------------------------------+------------------------------+ | 0 | 1 || 1 | 0 | 0 | 1 | 1 | +-----------+-----------++----------------+----------------+------------------------------+------------------------------------+------------------------------+ | 1 | 0 || 0 | 1 | 0 | 1 | 1 | +-----------+-----------++----------------+----------------+------------------------------+------------------------------------+------------------------------+ | 1 | 1 || 0 | 0 | 0 | 1 | 1 | +-----------+-----------++----------------+----------------+------------------------------+------------------------------------+------------------------------+ -------------------------------------------------- :rem:`||:sec:||`\ Universal composition function -------------------------------------------------- It is obvious, that a truth table for a Boolean function :math:`f^m_i(x_0, x_1, \dotsc, x_{m-1})` can be partitioned into an upper half, where :math:`x_0=0` and a lower half, where :math:`x_0=1`. Each half without :math:`x_0` is then a truth table for a function :math:`f^{m-1}_u(x_1, \dotsc, x_{m-1})` and a function :math:`f^{m-1}_v(x_1, \dotsc, x_{m-1})` of arity :math:`m-1`, :math:`u,v \in (0, 1, \dotsc, 2^{2^{m-1}}-1), z \in (0, 1, \dotsc, 2^{2^{m}}-1)`. E.g.: .. graphviz:: digraph f3_23_composition { rankdir=LR; splines=polyline; subgraph cluster_table_A { node [fontname="FreeSans",fontsize="12",shape=record]; table_A [shape=plaintext,label=<
j x0 x1 x2 Y23
0 000 0
1 001 0
2 010 0
3 011 1
4 100 0
5 101 1
6 110 1
7 111 1
>,style=solid]; } } The composition function for :math:`m > 1` .. math:: c^m_i : B^{\,m} \to B^{\,1}, c^m_i(x_0, x_1, \dotsc, x_k) = \left\{ \begin{array}{ll} f^{m-1}_{u}(x_1, \dotsc, x_k) & \mbox{if}\,\, x_0 = 0\\ f^{m-1}_{v}(x_1, \dotsc, x_k) & \mbox{if}\,\, x_0 = 1 ,\\ \end{array} \right. and the composition function for :math:`m = 1` .. math:: c^1_z : B \to B, c^1_z(x_0) = \left\{ \begin{array}{ll} f^{0}_{u}() = Y_{z_0} & \mbox{if}\,\, x_0 = 0\\ f^{0}_{v}() = Y_{z_1} & \mbox{if}\,\, x_0 = 1 ,\\ \end{array} \right. can be expressed in terms of logical operators :math:`\{ \bot, \top, \mathrm{NOT}, \mathrm{AND}, \mathrm{OR} \}`: .. math:: c^m_i(x_0, x_1, \dotsc, x_k) &~= ( \neg x_0 \wedge f^{m-1}_{u}(x_1, \dotsc, x_k) ) \vee ( x_0 \wedge f^{m-1}_{v}(x_1, \dotsc, x_k) ) ,\\ c^1_z(x_0) &~= ( \neg x_0 \wedge f^{0}_{u}() ) \vee ( x_0 \wedge f^{0}_{v}() ) .\\ This is equivalent to the functional notation .. math:: c^m_i(x_0, x_1, \dotsc, x_k) &~= f^{2}_{7}( f^{2}_{1}( f^{1}_{2}(x_0), f^{m-1}_{u}(x_1, \dotsc, x_k) ), f^{2}_{1}( x_0, f^{m-1}_{v}(x_1, \dotsc, x_k) ) ),\\ c^1_z(x_0) &~= f^{2}_{7}( f^{2}_{1}( f^{1}_{2}(x_0), f^{0}_{u}() ), f^{2}_{1}( x_0, f^{0}_{v}() ) . Therefore the composition mechanism :math:`c^m_i` can be applied recursively to define any required Boolean function. The recursion is guaranteed to terminate at a function :math:`c^1_z`, which only uses the previously defined functions |BOTx|, |TOPx|, |NOTx|, |ANDx|, |ORx|. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ :rem:`|:sec:|`\ Unary functions defined by composition function ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ The unary funtions :math:`f^{1}_{i}` for example, are such defined as: .. math:: f^1_0(p) &= f^{2}_{7}( f^{2}_{1}( f^{1}_{2}(p), f^{0}_{0}() ), f^{2}_{1}( p, f^{0}_{0}() ) ), \\ f^1_1(p) &= f^{2}_{7}( f^{2}_{1}( f^{1}_{2}(p), f^{0}_{0}() ), f^{2}_{1}( p, f^{0}_{1}() ) ), \\ f^1_3(p) &= f^{2}_{7}( f^{2}_{1}( f^{1}_{2}(p), f^{0}_{1}() ), f^{2}_{1}( p, f^{0}_{1}() ) ) . Substituting :math:`\bot` for :math:`f^{0}_{0}()` and :math:`\top` for :math:`f^{0}_{1}()` gives: .. math:: f^1_0(p) &= f^{2}_{7}( f^{2}_{1}( f^{1}_{2}(p), \bot ), f^{2}_{1}( p, \bot ) ), \\ f^1_1(p) &= f^{2}_{7}( f^{2}_{1}( f^{1}_{2}(p), \bot ), f^{2}_{1}( p, \top ) ), \\ f^1_3(p) &= f^{2}_{7}( f^{2}_{1}( f^{1}_{2}(p), \top ), f^{2}_{1}( p, \top ) ) . Applying :math:`p \wedge \bot = \bot` and :math:`p \wedge \top = p` gives: .. math:: f^1_0(p) &= f^{2}_{7}( \bot, \bot ), \\ f^1_1(p) &= f^{2}_{7}( \bot, p ), \\ f^1_3(p) &= f^{2}_{7}( f^{1}_{2}(p), p ) . Finally applying :math:`p \vee \bot = p` and :math:`p \vee \neg p = \top` gives: .. math:: f^1_0(p) &= \bot \\ f^1_1(p) &= p \\ f^1_3(p) &= \top . ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ :rem:`|:sec:|`\ Example composition function for :math:`f^3_{23}` ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ .. math:: c^3_{23}(x_0, x_1, x_2) = f^{2}_{7}( &f^{2}_{1}( f^{1}_{2}(x_0), f^{2}_{7}(f^{2}_{1}( f^{1}_{2}(x_1), f^{2}_{7}(f^{2}_{1}( f^{1}_{2}(x_2), f^{0}_{0}() ), f^{2}_{1}( x_2, f^{0}_{0}() )) ), f^{2}_{1}( x_1, f^{2}_{7}(f^{2}_{1}( f^{1}_{2}(x_2), f^{0}_{0}() ), f^{2}_{1}( x_2, f^{0}_{1}() )) )) ),\\ &f^{2}_{1}( x_0, f^{2}_{7}(f^{2}_{1}( f^{1}_{2}(x_1), f^{2}_{7}(f^{2}_{1}( f^{1}_{2}(x_2), f^{0}_{0}() ), f^{2}_{1}( x_2, f^{0}_{1}() )) ), f^{2}_{1}( x_1, f^{2}_{7}(f^{2}_{1}( f^{1}_{2}(x_2), f^{0}_{1}() ), f^{2}_{1}( x_2, f^{0}_{1}() )) )) )) . Optimized: .. math:: \begin{array}{llll} c^3_{23}(x_0, x_1, x_2) &~= f^{2}_{7}( &f^{2}_{1}( f^{1}_{2}(x_0), f^{2}_{7}(f^{2}_{1}( f^{1}_{2}(x_1), f^{0}_{0}() ), f^{2}_{1}( x_1, x_2 )) ), & |~\mbox{subst}~\bot, \top\\ &&f^{2}_{1}( x_0, f^{2}_{7}(f^{2}_{1}( f^{1}_{2}(x_1), x_2 ), f^{2}_{1}( x_1, f^{0}_{1}() )) ))\\ &~= f^{2}_{7}( &f^{2}_{1}( f^{1}_{2}(x_0), f^{2}_{7}(f^{2}_{1}( f^{1}_{2}(x_1), \bot ), f^{2}_{1}( x_1, x_2 )) ), & \left|~p \wedge \bot = \bot, p \wedge \top = p\right.\\ &&f^{2}_{1}( x_0, f^{2}_{7}(f^{2}_{1}( f^{1}_{2}(x_1), x_2 ), f^{2}_{1}( x_1, \top )) )) & \left|~p \vee \bot = p, p \vee \top = \top\right.\\ &~= f^{2}_{7}( &f^{2}_{1}( f^{1}_{2}(x_0), f^{2}_{1}( x_1, x_2 ) ), & |~\mbox{subst}~\wedge, \vee\\ &&f^{2}_{1}( x_0, f^{2}_{7}(f^{2}_{1}( f^{1}_{2}(x_1), x_2 ), x_1 ) ))\\ &~= & (\neg x_0 \wedge x_1 \wedge x_2) \vee {} & |~\mbox{normalize}\\ && (x_0 \wedge ((\neg x_1 \wedge x_2) \vee x_1))\\ &~= & (\neg x_0 \wedge x_1 \wedge x_2) \vee {}\\ && (x_0 \wedge \neg x_1 \wedge x_2) \vee {}\\ && (x_0 \wedge x_1) . \end{array} .. >>CODD Conclusion .. >>CODD Appendix A .. \|:here:| .. >>CODD Notes .. ================================================== .. :rem:`|||:sec:|||`\ Footnotes .. ================================================== :html:`
` .. [#] The German Wikipedia article `Abzählende Kombinatorik`_ has a table for permutations, variations and combinations with and without repetition. The English Wikipedia disambiguates variations as: Variations with repetition, a term in combinatorics commonly used by non-English authors for n-tuples which does not lead to the right place. The article `Twelvefold way`_ describes several classifications of combinatorial objects, with `n-sequences in X`_ as equivalent of variations with repetition. .. >>CODD Reference List/Bibliography .. ================================================== .. :rem:`|||:sec:|||`\ References .. ================================================== .. _`n-sequences in X`: https://en.wikipedia.org/wiki/Twelvefold_way#case_f .. _`Twelvefold way`: https://en.wikipedia.org/wiki/Twelvefold_way .. _`Variations with repetition`: http://www.emathematics.net/combinavrepeticion.php .. _`Abzählende Kombinatorik`: https://de.wikipedia.org/wiki/Abz%C3%A4hlende_Kombinatorik .. include:: doc_defs.inc .. include:: doc_defs_combined.inc .. .. \||<-snap->|| doc_standalone .. include:: doc/doc_defs_secret.inc .. \||<-snap->|| doc_standalone .. \||<-snap->|| not_doc_standalone .. include:: doc_defs_secret.inc .. \||<-snap->|| not_doc_standalone .. _`Wolfgang Scherer`: wolfgang.scherer@gmx.de