Dualioji funkcija

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Peršokti į: navigaciją, paiešką

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)

Dualumo dėsnis[taisyti | redaguoti kodą]

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[taisyti | redaguoti kodą]

(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ė[taisyti | redaguoti kodą]

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 \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ų 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

Nuorodos[taisyti | redaguoti kodą]

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