Dualioji funkcija

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.

Tam tikrai loginei funkcijai f dualioji funkcija yra tokia funkcija f^*, kad su kiekvienam parametrų rinkiniu 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 \and y = \neg ( \neg x \or \neg y)$

[taisyti] 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)$

[taisyti] Savybės

(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)$ , tai $f * (x 1,..., x n) = g * (f 1 * (x 11,..., x 1 n),..., f n * (x n 1,..., x n n))$: $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 1 n),..., f n * (x n 1,..., x n n)$

[taisyti] 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 \or 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 $φ$ 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ų sąvybę 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