Dualioji funkcija

Tam tikrai loginei funkcijai f dualioji funkcija yra tokia funkcija f^*, kad kiekvienam parametrų rinkiniui galioja lygybė $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\land y=\neg (\neg x\lor \neg y)$

Dualumo dėsnis

Formuluotė: Jei $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})$

Įrodymas: $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})\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})$ tada ir tik tada, kai $f^{*}(x_{1},x_{2},...,x_{n})=g^{*}(x_{1},...,x_{n})$

Savybės

(f*)* =f

lengva įsitikinti…

Dualumo dėsnis

Įrodymas ankstesnioje pastraipoje

Jei $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_{1n}),...,f_{n}*(x_{n1},...,x_{nn}))$

$f*(x_{1},...,x_{n})=\neg g(f_{1}(\neg x_{11},...,\neg x_{1n}),...,f_{n}(\neg x_{n1},...,\neg x_{nn})$ $=\neg g(\neg \neg f_{1}(\neg x_{11},...,\neg x_{1n}),...,\neg \neg f_{n}(\neg x_{n1},...,\neg x_{nn})$ $=\neg g(\neg f_{1}*(x_{11},...,x_{1n}),...,\neg f_{n}*(x_{n1},...,x_{nn})$ $=g*(f_{1}*(x_{11},...,x_{1n}),...,f_{n}*(x_{n1},...,x_{nn})$

Autodualių funkcijų klasė

Apibrėžimas: $f_{1}(x_{1},...,x_{n})\in S\Leftrightarrow f^{*}=f$

Teorema: Jei $f(x_{1},...,x_{n})\notin S$, tai pakeitę joje kai kuriuos kintamuosius į x ir $\neg x$ galime gauti funkciją - konstantą , Pavyzdys: $f(\neg x,x,x,\neg x)=s(x)=c$

Įrodymas: Jei $f(x_{1},...,x_{n})\notin S$, tai atsiras toks $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(\neg a_{1},...,\neg a_{n})$. Pažymėkime visus a kaip $x^{a_{i}}$, kas a_i=1 reikštų x, o a_i =0 – $\neg x$ ir apibrėžkime $\phi (x)=f(x^{a_{1}},\ldots ,^{a_{n}})$. Tada $\phi (x)=f(x^{a_{1}},\ldots ,^{a_{n}})=f(\neg x^{a_{1}},\ldots ,\neg x^{a_{1}})=\phi (\neg x)$. Matome, jog $\phi$ funkcija nepriklauso nuo x, todėl ji yra konstanta

Aibė S yra uždara

Tarkime, kad $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},\ldots ,f_{m})$. Tada pagal 3 dualių funkcijų savybę ir autodualių funkcijų apibrėžimą: $g^{*}=f^{*}(f_{1}^{*}(\ldots ),\ldots ,f_{m}^{*}(\ldots ))$. Autoduali funkcija g egzistuos tada ir tik tada kai, f ir f_i funkcijos bus autodualios, todėl ši aibė yra uždara

Literatūra

• Richard Lassaigne, Michel de Rougemont „Logika ir Informatikos pagrindai“. vert. Stanislovas Norgėla. 1996 Leidykla „Žodynas“