Tam tikrai loginei funkcijai f dualioji funkcija yra tokia funkcija f* , kad kiekvienam parametrų rinkiniui galioja lygybė f ∗ ( x 1 , x 2 , . . . , x n ) = ¬ f ( ¬ x 1 , ¬ x 2 , . . . , ¬ x n ) {\displaystyle f^{*}(x_{1},x_{2},...,x_{n})=\neg f(\neg x_{1},\neg x_{2},...,\neg x_{n})} .
Pavyzdžiui, Būlio algebros funkcijai IR dualioji funkcija yra ARBA , nes x ∧ y = ¬ ( ¬ x ∨ ¬ y ) {\displaystyle x\land y=\neg (\neg x\lor \neg y)} [1]
Formuluotė: Jei f ( x 1 , x 2 , . . . , x n ) = g ( x 1 , x 2 , . . . , x n ) {\displaystyle f(x_{1},x_{2},...,x_{n})=g(x_{1},x_{2},...,x_{n})} , tai f ∗ ( x 1 , x 2 , . . . , x n ) = g ∗ ( x 1 , . . . , x n ) {\displaystyle f^{*}(x_{1},x_{2},...,x_{n})=g^{*}(x_{1},...,x_{n})}
Įrodymas: f ∗ ( x 1 , . . . , x n ) = ¬ f ( ¬ x 1 , . . . , ¬ x n ) = ¬ g ( ¬ x 1 , . . . , ¬ x n ) = g ∗ ( x 1 , . . . , x n ) {\displaystyle f^{*}(x_{1},...,x_{n})=\neg f(\neg x_{1},...,\neg x_{n})=\neg g(\neg x_{1},...,\neg x_{n})=g^{*}(x_{1},...,x_{n})} . Remėmės prielaida, kad f ( x 1 , . . . , x n ) = g ( x 1 , . . . , x n ) ⇒ f ( ¬ x 1 , . . . , ¬ x n ) = g ( ¬ x 1 , . . . , ¬ x n ) {\displaystyle f(x_{1},...,x_{n})=g(x_{1},...,x_{n})\Rightarrow f(\neg x_{1},...,\neg x_{n})=g(\neg x_{1},...,\neg x_{n})} , o tai teisinga, nes su bet kokias argumentais f ir g reikšmės sutampa.
Išvada: f ( x 1 , x 2 , . . . , x n ) = g ( x 1 , x 2 , . . . , x n ) {\displaystyle f(x_{1},x_{2},...,x_{n})=g(x_{1},x_{2},...,x_{n})} tada ir tik tada , kai f ∗ ( x 1 , x 2 , . . . , x n ) = g ∗ ( x 1 , . . . , x n ) {\displaystyle f^{*}(x_{1},x_{2},...,x_{n})=g^{*}(x_{1},...,x_{n})}
(f*)* =f
lengva įsitikinti…
Dualumo dėsnis
Įrodymas ankstesnioje pastraipoje
Jei f ( x 1 , . . . , x n ) = g ( f 1 ( x 11 , . . . , x 1 n ) , . . . , f n ( x n 1 , . . . , x n n ) {\displaystyle f(x_{1},...,x_{n})=g(f_{1}(x_{11},...,x_{1n}),...,f_{n}(x_{n1},...,x_{nn})} , tai f ∗ ( x 1 , . . . , x n ) = g ∗ ( f 1 ∗ ( x 11 , . . . , x 1 n ) , . . . , f n ∗ ( x n 1 , . . . , x n n ) ) {\displaystyle f*(x_{1},...,x_{n})=g*(f_{1}*(x_{11},...,x_{1n}),...,f_{n}*(x_{n1},...,x_{nn}))}
f ∗ ( x 1 , . . . , x n ) = ¬ g ( f 1 ( ¬ x 11 , . . . , ¬ x 1 n ) , . . . , f n ( ¬ x n 1 , . . . , ¬ x n n ) {\displaystyle f*(x_{1},...,x_{n})=\neg g(f_{1}(\neg x_{11},...,\neg x_{1n}),...,f_{n}(\neg x_{n1},...,\neg x_{nn})} = ¬ g ( ¬ ¬ f 1 ( ¬ x 11 , . . . , ¬ x 1 n ) , . . . , ¬ ¬ f n ( ¬ x n 1 , . . . , ¬ x n n ) {\displaystyle =\neg g(\neg \neg f_{1}(\neg x_{11},...,\neg x_{1n}),...,\neg \neg f_{n}(\neg x_{n1},...,\neg x_{nn})} = ¬ g ( ¬ f 1 ∗ ( x 11 , . . . , x 1 n ) , . . . , ¬ f n ∗ ( x n 1 , . . . , x n n ) {\displaystyle =\neg g(\neg f_{1}*(x_{11},...,x_{1n}),...,\neg f_{n}*(x_{n1},...,x_{nn})} = g ∗ ( f 1 ∗ ( x 11 , . . . , x 1 n ) , . . . , f n ∗ ( x n 1 , . . . , x n n ) {\displaystyle =g*(f_{1}*(x_{11},...,x_{1n}),...,f_{n}*(x_{n1},...,x_{nn})} Autodualių funkcijų klasė
redaguoti
Apibrėžimas: f 1 ( x 1 , . . . , x n ) ∈ S ⇔ f ∗ = f {\displaystyle f_{1}(x_{1},...,x_{n})\in S\Leftrightarrow f^{*}=f}
Teorema: Jei f ( x 1 , . . . , x n ) ∉ S {\displaystyle f(x_{1},...,x_{n})\notin S} , tai pakeitę joje kai kuriuos kintamuosius į x ir ¬ x {\displaystyle \neg x} galime gauti funkciją - konstantą
,
Pavyzdys: f ( ¬ x , x , x , ¬ x ) = s ( x ) = c {\displaystyle f(\neg x,x,x,\neg x)=s(x)=c}
Įrodymas: Jei f ( x 1 , . . . , x n ) ∉ S {\displaystyle f(x_{1},...,x_{n})\notin S} , tai atsiras toks a 1 , . . . , a n ( a i = 0 ∨ a i = 1 , 1 ≤ i ≤ n {\displaystyle a_{1},...,a_{n}(a_{i}=0\lor a_{i}=1,1\leq i\leq n} reikšmių rinkinys, kad f ( a 1 , . . . , a n ) = f ( ¬ a 1 , . . . , ¬ a n ) {\displaystyle f(a_{1},...,a_{n})=f(\neg a_{1},...,\neg a_{n})} . Pažymėkime visus a kaip x a i {\displaystyle x^{a_{i}}} , kas ai =1 reikštų x, o ai =0 – ¬ x {\displaystyle \neg x} ir apibrėžkime ϕ ( x ) = f ( x a 1 , … , a n ) {\displaystyle \phi (x)=f(x^{a_{1}},\ldots ,^{a_{n}})} . Tada ϕ ( x ) = f ( x a 1 , … , a n ) = f ( ¬ x a 1 , … , ¬ x a 1 ) = ϕ ( ¬ x ) {\displaystyle \phi (x)=f(x^{a_{1}},\ldots ,^{a_{n}})=f(\neg x^{a_{1}},\ldots ,\neg x^{a_{1}})=\phi (\neg x)} . Matome, jog ϕ {\displaystyle \phi } funkcija nepriklauso nuo x, todėl ji yra konstanta
Aibė S yra uždara
Tarkime, kad f ( x 1 , … , x n ) ∈ S , f 1 ( x 1 1 , … , x n 1 ) ∈ S , … , f m ( x 1 m , … , x n m ) ∈ S {\displaystyle f(x_{1},\ldots ,x_{n})\in S,f_{1}(x_{1}^{1},\ldots ,x_{n}^{1})\in S,\ldots ,f_{m}(x_{1}^{m},\ldots ,x_{n}^{m})\in S} , g = f ( f 1 , … , f m ) {\displaystyle g=f(f_{1},\ldots ,f_{m})} . Tada pagal 3 dualių funkcijų savybę ir autodualių funkcijų apibrėžimą: g ∗ = f ∗ ( f 1 ∗ ( … ) , … , f m ∗ ( … ) ) {\displaystyle g^{*}=f^{*}(f_{1}^{*}(\ldots ),\ldots ,f_{m}^{*}(\ldots ))} . Autoduali funkcija g egzistuos tada ir tik tada kai, f ir fi funkcijos bus autodualios, todėl ši aibė yra uždara
Richard Lassaigne, Michel de Rougemont „Logika ir Informatikos pagrindai“. vert. Stanislovas Norgėla. 1996 Leidykla „Žodynas“