Funcție auto-duală

O funcție auto-duală este o funcție booleană care este duală cu ea însăși. O funcție duală cu o funcție se numește funcție . Deci o funcție este auto-duală dacă . Cu alte cuvinte, o funcție auto-duală pe seturi opuse de valori argumente preia valori opuse. $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})$

Setul de funcții auto-duale este notat cu simbolul . Setul este o clasă închisă . Într-adevăr, dacă funcțiile sunt auto-duale, atunci funcția este, de asemenea, auto-duală: $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 ¯ unu , … , X ¯ n ) = f ¯ ( f unu ( X ¯ unu , … , X ¯ n ) , … , f k ( X ¯ unu , … , X ¯ n ) ) = f ¯ ( f ¯ unu ( X unu , … , X n ) , … , f ¯ k ( X unu , … , X n ) ) = f ( f unu ( X unu , … , X n ) , … , f k ( X unu , … , X n ) ) = g ( X unu , … , 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$ este o clasă precompletă .

Exemple de funcții auto-duale: . La rândul lor , conjuncția , disjuncția și constantele nu sunt auto-duale. $x,{\overline {x)),(x\wedge y)\vee (x\wedge z)\vee (y\wedge z)$

Literatură

Yablonsky S.V. Introducere în matematica discretă. — M.: Nauka. — 1986
Marchenkov S.S. Clase închise de funcții booleene. — M.: Fizmatlit. - 2000