Booleovská funkce - Boolean function

tento článek potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: "Booleovská funkce"  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Únor 2020) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v matematika a logika, a Booleovská funkce je funkce jehož argumenty, stejně jako samotná funkce, předpokládají hodnoty ze sady dvou prvků (obvykle {0,1}).^[1] Výsledkem je, že se někdy označuje jako „spínací funkce“.

Booleovská funkce má podobu ${ displaystyle f: {0,1 } ^ {k} až {0,1 }}$, kde ${ displaystyle {0,1 }}$ se nazývá a Booleovská doména a ${ displaystyle k}$ je nezáporné celé číslo zvané arity funkce. V případě, že ${ displaystyle k = 0}$„funkce“ je v podstatě konstantní prvek ${ displaystyle {0,1 }}$.

Každý ${ displaystyle k}$-ary boolovská funkce může být vyjádřena jako a výrokový vzorec v ${ displaystyle k}$ proměnné ${ displaystyle x_ {1}, ..., x_ {k}}$, a dva výrokové vzorce jsou logicky ekvivalentní právě když vyjadřují stejnou booleovskou funkci. Existují ${ displaystyle 2 ^ {2 ^ {k}}}$ ${ displaystyle k}$-ary funkce pro každého ${ displaystyle k}$.

Booleovské funkce v aplikacích

Logická funkce je funkce, kterou lze použít k vyhodnocení libovolného logického výstupu ve vztahu k jeho logickému vstupu logickým typem výpočtů. Tyto funkce hrají základní roli v otázkách teorie složitosti stejně jako návrh obvodů a čipů pro digitální počítače. Vlastnosti booleovských funkcí hrají v kryptografie, zejména v designu algoritmy symetrického klíče (vidět box pro střídání ).

Booleovské funkce jsou často reprezentovány větami v výroková logika, a někdy jako vícerozměrné polynomy přes GF (2), ale účinnější reprezentace jsou binární rozhodovací diagramy (BDD), negace normální formy, a výrokové směrované acyklické grafy (PDAG).

v kooperativní hra teorie, monotónní booleovské funkce se nazývají jednoduché hry (hlasovací hry); tento pojem se uplatňuje při řešení problémů v teorie sociální volby.

Za účelem optimalizace elektronických obvodů mohou být booleovské funkce minimalizováno za použití Algoritmus Quine – McCluskey nebo Karnaugh mapa.

Viz také

Reference

Další čtení

• Crama, Y; Hammer, P. L. (2011), Booleovské funkce: Teorie, algoritmy a aplikace, Cambridge University Press, doi:10.1017 / CBO9780511852008, ISBN  9780511852008.
• "Booleovská funkce", Encyclopedia of Mathematics, Stiskněte EMS, 2001 [1994]
• Janković, Dragan; Stanković, Radomir S .; Moraga, Claudio (listopad 2003). "Optimalizace aritmetických výrazů pomocí vlastnosti dvojí polarity" (PDF). Srbský žurnál elektrotechniky. 1 (71–80, číslo 1): 71–80. doi:10,2298 / SJEE0301071J. Archivovány od originál (PDF) dne 2016-03-05. Citováno 2015-06-07.
• Bradford Henry Arnold (1. ledna 2011). Logická a booleovská algebra. Courier Corporation. ISBN  978-0-486-48385-6.
• Mano, M. M .; Ciletti, M. D. (2013), Digitální design, Pearson.