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)=\mathrm{\neg }f(\mathrm{\neg }{x}_1,\mathrm{\neg }{x}_2,...,\mathrm{\neg }{x}_n)$.

Pavyzdžiui, Būlio algebros funkcijai IR dualioji funkcija yra ARBA, nes $x\wedge y=\mathrm{\neg }(\mathrm{\neg }x\vee \mathrm{\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)=\mathrm{\neg }f(\mathrm{\neg }{x}_1,...,\mathrm{\neg }{x}_n)=\mathrm{\neg }g(\mathrm{\neg }{x}_1,...,\mathrm{\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(\mathrm{\neg }{x}_1,...,\mathrm{\neg }{x}_n)=g(\mathrm{\neg }{x}_1,...,\mathrm{\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)=\mathrm{\neg }g(f_1(\mathrm{\neg }{x}_{11},...,\mathrm{\neg }{x}_{1n}),...,f_n(\mathrm{\neg }{x}_{n1},...,\mathrm{\neg }{x}_{nn})$ $=\mathrm{\neg }g(\mathrm{\neg }\mathrm{\neg }{f}_1(\mathrm{\neg }{x}_{11},...,\mathrm{\neg }{x}_{1n}),...,\mathrm{\neg }\mathrm{\neg }{f}_n(\mathrm{\neg }{x}_{n1},...,\mathrm{\neg }{x}_{nn})$ $=\mathrm{\neg }g(\mathrm{\neg }{f}_1*(x_{11},...,x_{1n}),...,\mathrm{\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\iff f^{*}=f$

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

Įrodymas: Jei $f(x_1,...,x_n)\notin S$, tai atsiras toks $a_1,...,a_n(a_i=0\vee a_i=1,1\le i\le n$reikšmių rinkinys, kad $f(a_1,...,a_n)=f(\mathrm{\neg }{a}_1,...,\mathrm{\neg }{a}_n)$. Pažymėkime visus a kaip $x^{a_i}$, kas a_i=1 reikštų x, o a_i =0 – $\mathrm{\neg }x$ ir apibrėžkime $\varphi (x)=f(x^{a_1},\dots {,}^{a_n})$. Tada $\varphi (x)=f(x^{a_1},\dots {,}^{a_n})=f(\mathrm{\neg }{x}^{a_1},\dots ,\mathrm{\neg }{x}^{a_1})=\varphi (\mathrm{\neg }x)$. Matome, jog $\varphi$ funkcija nepriklauso nuo x, todėl ji yra konstanta

Aibė S yra uždara

Tarkime, kad $f(x_1,\dots ,x_n)\in S,f_1(x_1^1,\dots ,x_n^1)\in S,\dots ,f_m(x_1^m,\dots ,x_n^m)\in S$, $g=f(f_1,\dots ,f_m)$. Tada pagal 3 dualių funkcijų savybę ir autodualių funkcijų apibrėžimą: $g^{*}=f^{*}(f_1^{*}(\dots ),\dots ,f_m^{*}(\dots ))$. 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“