Dualioji funkcija

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

Dualumo dėsnis

Formuluotė: Jei ${\displaystyle f(x_{1},x_{2},...,x_{n})=g(x_{1},x_{2},...,x_{n})}$, tai ${\displaystyle f^{*}(x_{1},x_{2},...,x_{n})=g^{*}(x_{1},...,x_{n})}$

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

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

Autodualių funkcijų klasė

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

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

Įrodymas: Jei ${\displaystyle f(x_{1},...,x_{n})\notin S}$, tai atsiras toks ${\displaystyle a_{1},...,a_{n}(a_{i}=0\lor a_{i}=1,1\leq i\leq n}$reikšmių rinkinys, kad ${\displaystyle f(a_{1},...,a_{n})=f(\neg a_{1},...,\neg a_{n})}$. Pažymėkime visus a kaip ${\displaystyle x^{a_{i}}}$, kas a_i=1 reikštų x, o a_i =0 – ${\displaystyle \neg x}$ ir apibrėžkime ${\displaystyle \phi (x)=f(x^{a_{1}},\ldots ,^{a_{n}})}$. Tada ${\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 ${\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}$, ${\displaystyle g=f(f_{1},\ldots ,f_{m})}$. Tada pagal 3 dualių funkcijų savybę ir autodualių funkcijų apibrėžimą: ${\displaystyle 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“