Funkční úplnost - Functional completeness

v logika, a funkčně kompletní množina logické spojky nebo Booleovské operátory je ten, kterým lze vyjádřit vše možné pravdivostní tabulky spojením členů soubor do Booleovský výraz.^[1]^[2] Známá úplná sada spojovacích prostředků je {AND, NOT}, skládající se z binárních souborů spojení a negace. Každý z jedináček sady {NAND } a {ANI } je funkčně kompletní.

Brána nebo sada bran, která je funkčně kompletní, lze také nazvat univerzální bránou / branami.

Funkčně kompletní sada bran může využívat nebo generovat „odpadkové bity“ jako součást svého výpočtu, které buď nejsou součástí vstupu, nebo nejsou součástí výstupu do systému.

V kontextu výroková logika, nazývají se také funkčně kompletní sady spojek (výslovně) adekvátní.^[3]

Z pohledu digitální elektronika, funkční úplnost znamená, že vše možné logická brána lze realizovat jako síť bran typů předepsaných sadou. Zejména lze všechny logické brány sestavit buď pouze z binárních Brány NAND, nebo pouze binární Brány NOR.

Úvod

Moderní texty o logice obvykle berou jako primitivní některou podmnožinu spojek: spojení ( ${displaystyle land}$ ); disjunkce ( ${displaystyle lor}$ ); negace ( ${displaystyle eg}$ ); materiál podmíněný ( ${displaystyle o}$ ); a možná dvojpodmínečné ( ${displaystyle leftrightarrow}$ ). Další spojky lze definovat, pokud je to žádoucí, jejich definováním z hlediska těchto primitiv. Například NOR (někdy označeno ${displaystyle downarrow}$ , negaci disjunkce) lze vyjádřit jako spojení dvou negací:

{displaystyle Adownarrow B: = např. Aland např. B}

Podobně negace spojení, NAND (někdy označována jako ${displaystyle uparrow}$ ), lze definovat z hlediska disjunkce a negace. Ukazuje se, že každé binární pojivo lze definovat z hlediska ${displaystyle {eg, land, lor, o, leftrightarrow}}$ , takže tato sada je funkčně kompletní.

Stále však obsahuje určitou redundanci: tato sada není minimální funkčně úplná množina, protože podmíněné a dvojpodmínečné lze definovat z hlediska ostatních spojek jako

{displaystyle {egin {aligned} A o B &: = např. Alor B Aleftrightarrow B &: = (A o B) land (B o A) .end {aligned}}}

Z toho vyplývá, že menší sada ${displaystyle {eg, land, lor}}$ je také funkčně kompletní. Ale to stále není minimální, protože ${displaystyle lor}$ lze definovat jako

{displaystyle Alor B: = např. (např. Aland např. B).}

Alternativně, ${displaystyle land}$ mohou být definovány z hlediska ${displaystyle lor}$ podobným způsobem, nebo ${displaystyle lor}$ mohou být definovány z hlediska ${displaystyle ightarrow}$ :

{displaystyle Avee B: = např. Aightarrow B.}

Další zjednodušení nejsou možná. Proto každá dvouprvková sada spojek obsahuje ${displaystyle eg}$ a jeden z ${displaystyle {land, lor, ightarrow}}$ je minimální funkčně kompletní podmnožina z ${displaystyle {eg, land, lor, o, leftrightarrow}}$ .

Formální definice

Vzhledem k Booleovská doména B = {0,1}, množina F booleovských funkcí ƒ_i: B^n_i → B je funkčně kompletní pokud klon na B generované základními funkcemi ƒ_i obsahuje všechny funkce ƒ: Bⁿ → B, pro všechny přísně pozitivní celá čísla n ≥ 1. Jinými slovy, sada je funkčně úplná, pokud lze každou booleovskou funkci, která přebírá alespoň jednu proměnnou, vyjádřit pomocí funkcí ƒ_i. Protože každou booleovskou funkci alespoň jedné proměnné lze vyjádřit pomocí binárních booleovských funkcí, F je funkčně kompletní právě tehdy, když lze každou binární booleovskou funkci vyjádřit pomocí funkcí v F.

Přirozenějším stavem by bylo, že klon generovaný F se skládají ze všech funkcí ƒ: Bⁿ → B, pro všechna celá čísla n ≥ 0. Výše uvedené příklady však nejsou funkčně úplné v tomto silnějším smyslu, protože není možné napsat a nullary funkce, tj. konstantní výraz, ve smyslu F -li F sama o sobě neobsahuje alespoň jednu funkci nullary. S touto silnější definicí by nejmenší funkčně úplné sady měly 2 prvky.

Další přirozenou podmínkou by bylo, že klon generovaný F společně se dvěma nullovými konstantními funkcemi být funkčně kompletní nebo ekvivalentně funkčně kompletní v silném smyslu předchozího odstavce. Příklad booleovské funkce dané S(X, y, z) = z -li X = y a S(X, y, z) = X jinak ukazuje, že tento stav je přísně slabší než funkční úplnost.^[4]^[5]^[6]

Charakterizace funkční úplnosti

Emil Post dokázal, že sada logických spojek je funkčně úplná právě tehdy, pokud nejde o podmnožinu žádné z následujících sad spojek:

The monotóní spojky; změna hodnoty pravdivosti všech připojených proměnných z F na T beze změny z T na F nikdy nedovolí těmto spojovacím prvkům změnit jejich návratovou hodnotu T na F, např. ${displaystyle vee, wedge, op, ot}$ .
The afinní spojky, takže každá připojená proměnná vždy nebo nikdy neovlivní pravdivostní hodnotu, kterou tyto spojky vracejí, např. ${displaystyle eg, op, ot, leftrightarrow, leftrightarrow}$ .
The self-dual spojky, které jsou stejné jako jejich vlastní de Morgan dual; pokud jsou pravdivostní hodnoty všech proměnných obráceny, tak je i pravdivostní hodnota, kterou tyto spojky vracejí, např. ${displaystyle eg}$ , MAJ (p,q,r).
The uchování pravdy spojky; vrátí pravdivostní hodnota T pod jakýmkoli výkladem, který přiřadí T na všechny proměnné, např. ${displaystyle vee, wedge, op, ightarrow, leftrightarrow}$ .
The uchování falešnosti spojky; vrátí hodnotu pravdy F pod jakýmkoli výkladem, který přiřadí F na všechny proměnné, např. ${displaystyle vee, wedge, ot, rightarrow, leftrightarrow}$ .

Ve skutečnosti Post poskytl úplný popis mříž ze všech klony (sady operací uzavřené ve složení a obsahující všechny projekce) na dvouprvkové sadě {T, F}, dnes volaný Postova mříž, což implikuje výše uvedený výsledek jako jednoduchý důsledek: pět zmíněných sad spojek je přesně maximální klony.

Minimálně funkčně kompletní sady operátorů

Když je jeden logický spojovací nebo booleovský operátor sám o sobě funkčně kompletní, nazývá se a Shefferova funkce^[7] nebo někdy a jediný dostatečný operátor. Nejsou k dispozici žádné unární operátory s touto vlastností. NAND a ANI , což jsou duální navzájem, jsou jediné dvě binární Shefferovy funkce. Ty byly objeveny, ale nebyly zveřejněny, uživatelem Charles Sanders Peirce kolem roku 1880 a znovuobjeveny samostatně a publikovány Henry M. Sheffer v roce 1913.^[8]V terminologii digitální elektroniky binární Brána NAND a binární NOR brána jsou jediné binární univerzální logické brány.

Následuje minimálně funkčně kompletní sada logických spojek s arity ≤ 2:^[9]

Jeden prvek: {↑}, {↓}.
Dva prvky: ${displaystyle {vee, eg}}$ , ${displaystyle {wedge, eg}}$ , ${displaystyle {o, eg}}$ , ${displaystyle {gets, eg}}$ , ${displaystyle {o, ot}}$ , ${displaystyle {gets, ot}}$ , ${displaystyle {o, leftrightarrow}}$ , ${displaystyle {gets, leftrightarrow}}$ , ${displaystyle {o, rightarrow}}$ , ${displaystyle {o, leftarrow}}$ , ${displaystyle {gets, rightarrow}}$ , ${displaystyle {gets, leftarrow}}$ , ${displaystyle {rightarrow, eg}}$ , ${displaystyle {leftarrow, eg}}$ , ${displaystyle {rightarrow, op}}$ , ${displaystyle {leftarrow, op}}$ , ${displaystyle {rightarrow, leftrightarrow}}$ , ${displaystyle {leftarrow, leftrightarrow}.}$
Tři prvky: ${displaystyle {lor, leftrightarrow, ot}}$ , ${displaystyle {lor, leftrightarrow, leftrightarrow}}$ , ${displaystyle {lor, leftrightarrow, op}}$ , ${displaystyle {land, leftrightarrow, ot}}$ , ${displaystyle {land, leftrightarrow, leftrightarrow}}$ , ${displaystyle {land, leftrightarrow, op}.}$

Neexistují žádné minimální funkčně úplné sady více než tří nanejvýš binárních logických spojek.^[9] Aby byly výše uvedené seznamy čitelné, byly vynechány operátory, které ignorují jeden nebo více vstupů. Například operátor, který ignoruje první vstup a výstupy negace druhého, může být nahrazen unární negací.

Příklady

Příklady použití NAND(↑) úplnost. Jak dokládá,^[10]
- ¬A ≡ A ↑ A
- A ∧ B ≡ ¬ (A ↑ B) ≡ (A ↑ B) ↑ (A ↑ B)
- A ∨ B ≡ (A ↑ A) ↑ (B ↑ B)
Příklady použití ANI(↓) úplnost. Jak dokládá,^[11]
- ¬A ≡ A ↓ A
- A ∨ B ≡ ¬ (A ↓ B) ≡ (A ↓ B) ↓ (A ↓ B)
- A ∧ B ≡ (A ↓ A) ↓ (B ↓ B)

Pamatujte, že elektronický obvod nebo softwarová funkce mohou být optimalizovány opětovným použitím, aby se snížil počet bran. Například operace „A ∧ B“, vyjádřená branami ↑, je implementována s opětovným použitím „A ↑ B“,

X ≡ (A ↑ B); A ∧ B ≡ X ↑ X

V jiných doménách

Kromě logických spojek (booleovských operátorů) lze funkční úplnost zavést i v jiných doménách. Například sada reverzibilní gates se nazývá funkčně kompletní, pokud dokáže vyjádřit každého reverzibilního operátora.

3-vstup Fredkinova brána je funkčně kompletní vratná brána sama o sobě - jediný dostatečný operátor. Existuje mnoho dalších univerzální logická hradla se třemi vstupy, tak jako Toffoli brána.

v kvantové výpočty, Hadamardova brána a T brána jsou univerzální, i když s trochu restriktivnější definice než funkční úplnost.

Teorie množin

Tady je izomorfismus mezi algebra množin a Booleova algebra, to znamená, že mají stejné struktura. Pokud tedy mapujeme booleovské operátory na operátory množin, výše uvedený „přeložený“ text platí i pro množiny: existuje mnoho „minimálních úplných množin operátorů teorie množin“, které mohou generovat jakékoli další relace množin. Nejoblíbenější „Minimální kompletní sady operátorů“ jsou {¬, ∩} a {¬, ∪}. Pokud univerzální sada je zakázáno, operátory množin jsou omezeny na zachování falsity (Ø) a nemohou být ekvivalentem funkčně kompletní booleovské algebry.

Viz také

Reference

^ Enderton, Herbert (2001), Matematický úvod do logiky (2. vyd.), Boston, MA: Akademický tisk, ISBN 978-0-12-238452-3. ("Kompletní sada logických spojek").
^ Nolt, John; Rohatyn, Dennis; Varzi, Achille (1998), Schaumův nástin teorie a problémů logiky (2. vyd.), New York: McGraw – Hill, ISBN 978-0-07-046649-4. („[F] unctional úplnost [a] množiny logických operátorů“).
^ Smith, Peter (2003), Úvod do formální logiky, Cambridge University Press, ISBN 978-0-521-00804-4. (Definuje „výslovně adekvátní“, v záhlaví sekce zkráceno na „adekvátní sadu spojovacích prostředků“.)
^ Wesselkamper, T.C. (1975), „Jediný dostatečný operátor“, Deník Notre Dame formální logiky, 16: 86–88, doi:10.1305 / ndjfl / 1093891614
^ Massey, G.J. (1975), „O údajné Shefferově funkci“, Deník Notre Dame formální logiky, 16 (4): 549–550, doi:10.1305 / ndjfl / 1093891898
^ Wesselkamper, T.C. (1975), "Oprava mého příspěvku" A. Jediný dostatečný operátor ", Deník Notre Dame formální logiky, 16 (4): 551, doi:10.1305 / ndjfl / 1093891899
^ Termín byl původně omezen na binární operace, ale od konce 20. století se používá obecněji. Martin, N.M. (1989), Logické systémy, Cambridge University Press, str. 54, ISBN 978-0-521-36770-7.
^ Scharle, T.W. (1965), „Axiomatizace výrokového počtu pomocí Shefferových funktorů“, Notre Dame J. Formální logika, 6 (3): 209–217, doi:10.1305 / ndjfl / 1093958259.
^ ^A ^b Wernick, William (1942) „Kompletní sady logických funkcí“ Transakce Americké matematické společnosti 51: 117–32. Ve svém seznamu na poslední stránce článku Wernick nerozlišuje mezi ← a → nebo mezi ${displaystyle leftarrow}$ a ${displaystyle rightarrow}$ .
^ "NAND Gate Operations" ve společnosti http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nand.html
^ "NOR Gate Operations" ve společnosti http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nor.html

[Enderton2001-1] Enderton, Herbert (2001), Matematický úvod do logiky (2. vyd.), Boston, MA: Akademický tisk, ISBN 978-0-12-238452-3. ("Kompletní sada logických spojek").

[Nolt1998-2] Nolt, John; Rohatyn, Dennis; Varzi, Achille (1998), Schaumův nástin teorie a problémů logiky (2. vyd.), New York: McGraw – Hill, ISBN 978-0-07-046649-4. („[F] unctional úplnost [a] množiny logických operátorů“).

[Smith2003-3] Smith, Peter (2003), Úvod do formální logiky, Cambridge University Press, ISBN 978-0-521-00804-4. (Definuje „výslovně adekvátní“, v záhlaví sekce zkráceno na „adekvátní sadu spojovacích prostředků“.)

[Wesselkamper1975a-4] Wesselkamper, T.C. (1975), „Jediný dostatečný operátor“, Deník Notre Dame formální logiky, 16: 86–88, doi:10.1305 / ndjfl / 1093891614

[Massey1975-5] Massey, G.J. (1975), „O údajné Shefferově funkci“, Deník Notre Dame formální logiky, 16 (4): 549–550, doi:10.1305 / ndjfl / 1093891898

[Wesselkamper1975b-6] Wesselkamper, T.C. (1975), "Oprava mého příspěvku" A. Jediný dostatečný operátor ", Deník Notre Dame formální logiky, 16 (4): 551, doi:10.1305 / ndjfl / 1093891899

[Martin1989-7] Termín byl původně omezen na binární operace, ale od konce 20. století se používá obecněji. Martin, N.M. (1989), Logické systémy, Cambridge University Press, str. 54, ISBN 978-0-521-36770-7.

[Scharle1965-8] Scharle, T.W. (1965), „Axiomatizace výrokového počtu pomocí Shefferových funktorů“, Notre Dame J. Formální logika, 6 (3): 209–217, doi:10.1305 / ndjfl / 1093958259.

[Wernick-9] A ^b Wernick, William (1942) „Kompletní sady logických funkcí“ Transakce Americké matematické společnosti 51: 117–32. Ve svém seznamu na poslední stránce článku Wernick nerozlišuje mezi ← a → nebo mezi ${displaystyle leftarrow}$ a ${displaystyle rightarrow}$ .

[10] "NAND Gate Operations" ve společnosti http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nand.html

[11] "NOR Gate Operations" ve společnosti http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nor.html

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]