Dualioji funkcija

Tam tikrai loginei funkcijai f dualioji funkcija yra tokia funkcija f*, kad kiekvienam parametrų rinkiniui galioja lygybė .

Pavyzdžiui, Būlio algebros funkcijai IR dualioji funkcija yra ARBA, nes

Dualumo dėsnis 
Formuluotė: Jei , tai 

Įrodymas: . Remėmės prielaida, kad , o tai teisinga, nes su bet kokias argumentais f ir g reikšmės sutampa.

Išvada:  tada ir tik tada, kai

Savybės 
 (f*)* =f lengva įsitikinti…
 Dualumo dėsnis Įrodymas ankstesnioje pastraipoje
 Jei , tai

Autodualių funkcijų klasė 
Apibrėžimas: 

Teorema: Jei , tai pakeitę joje kai kuriuos kintamuosius į x ir  galime gauti funkciją - konstantą
,
Pavyzdys: 

Įrodymas: Jei , tai atsiras toks reikšmių rinkinys, kad . Pažymėkime visus a kaip , kas ai=1 reikštų x, o ai =0 –  ir apibrėžkime . Tada . Matome, jog  funkcija nepriklauso nuo x, todėl ji yra konstanta

 Aibė S yra uždara Tarkime, kad , . Tada pagal 3 dualių funkcijų savybę ir autodualių funkcijų apibrėžimą: . Autoduali funkcija g egzistuos tada ir tik tada kai, f ir fi funkcijos bus autodualios, todėl ši aibė yra uždara

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

Algoritmų teorija