Samodvojná funkce

Samoduální funkce je booleovská funkce , která je sama se sebou duální. Funkce duální k funkci se nazývá funkce . Funkce je tedy samoduální, pokud . Jinými slovy, samodvojná funkce na opačných sadách hodnot argumentů nabývá opačných hodnot. $f(x_{1},\ldots ,x_{n})$ $f^{*}(x_{1},\ldots ,x_{n})={\overline {f))({\overline {x))_{1},\ldots ,{\overline { x}}_{n})$ $f(x_{1},\ldots ,x_{n})$ ${\overline {f}}({\overline {x}}_{1},\ldots ,{\overline {x}}_{n})=f(x_{1},\ldots ,x_ {n})$

Sada samoduálních funkcí je označena symbolem . Sada je uzavřená třída . Pokud jsou funkce autoduální, pak je funkce také autoduální: $S$ $S$ $f(x_{1},\ldots ,x_{n}),f_{1}(x_{1},\ldots ,x_{n}),\ldots ,f_{k}(x_{1} ,\ldots ,x_{n})$ $g(x_{1},\ldots ,x_{n})=f(f_{1}(x_{1},\ldots ,x_{n}),\ldots ,f_{k}(x_{ 1},\ldots ,x_{n}))$

G ¯ ( X ¯ jeden , … , X ¯ n ) = F ¯ ( F jeden ( X ¯ jeden , … , X ¯ n ) , … , F k ( X ¯ jeden , … , X ¯ n ) ) = F ¯ ( F ¯ jeden ( X jeden , … , X n ) , … , F ¯ k ( X jeden , … , X n ) ) = F ( F jeden ( X jeden , … , X n ) , … , F k ( X jeden , … , X n ) ) = G ( X jeden , … , X n ) {\displaystyle {\begin{alignedat}{2}{\overline {g}}({\overline {x}}_{1},\ldots ,{\overline {x}}_{n})&={ \overline {f}}(f_{1}({\overline {x}}_{1},\ldots ,{\overline {x}}_{n}),\ldots ,f_{k}({\ overline {x}}_{1},\ldots ,{\overline {x}}_{n}))\\&={\overline {f}}({\overline {f}}_{1}( x_{1},\ldots ,x_{n}),\ldots ,{\overline {f))_{k}(x_{1},\ldots ,x_{n}))\\&=f(f_ {1}(x_{1},\ldots ,x_{n}),\ldots ,f_{k}(x_{1},\ldots ,x_{n}))\\&=g(x_{1} ,\ldots ,x_{n})\end{alignedat}}} ${\begin{alignedat}{2}{\overline {g}}({\overline {x}}_{1},\ldots ,{\overline {x}}_{n})&={ \overline {f}}(f_{1}({\overline {x}}_{1},\ldots ,{\overline {x}}_{n}),\ldots ,f_{k}({\ overline {x}}_{1},\ldots ,{\overline {x}}_{n}))\\&={\overline {f}}({\overline {f}}_{1}( x_{1},\ldots ,x_{n}),\ldots ,{\overline {f))_{k}(x_{1},\ldots ,x_{n}))\\&=f(f_ {1}(x_{1},\ldots ,x_{n}),\ldots ,f_{k}(x_{1},\ldots ,x_{n}))\\&=g(x_{1} ,\ldots ,x_{n})\end{alignedat}}$

$S$ je předkompletní třída .

Příklady sebeduálních funkcí: . Konjunkce , disjunkce a konstanty zase nejsou samoduální. $x,{\overline {x)),(x\klín y)\vee (x\klín z)\vee (y\klín z)$

Literatura

Yablonsky S.V. Úvod do diskrétní matematiky. — M.: Nauka. — 1986
Marčenkov S.S. Uzavřené třídy booleovských funkcí. — M.: Fizmatlit. - 2000