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)

Turinys

[taisyti] Dualumo dėsnis

Formuluotė: Jei f(x1,x2,...,xn) = g(x1,x2,...,xn), tai f * (x1,x2,...,xn) = g * (x1,...,xn)

Į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(x1,x2,...,xn) = g(x1,x2,...,xn) tada ir tik tada, kai f * (x1,x2,...,xn) = g * (x1,...,xn)

[taisyti] Savybės

(f*)* =f 
lengva įsitikinti...
Dualumo dėsnis
Įrodymas ankstesnioje pastraipoje
Jei f(x1,...,xn) = g(f1(x11,...,x1n),...,fn(xn1,...,xnn), tai f * (x1,...,xn) = g * (f1 * (x11,...,x1n),...,fn * (xn1,...,xnn))
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 * (f1 * (x11,...,x1n),...,fn * (xn1,...,xnn)

[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 nreikš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 ai=1 reikštų x, o ai =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 fi funkcijos bus autodualios, todėl ši aibė yra uždara

[taisyti] Nuorodos

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