Algebraická normální forma - Algebraic normal form
tento článek potřebuje další citace pro ověření.červenec 2013) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) ( |
v Booleova algebra, algebraická normální forma (ANF), běžná forma kruhového součtu (RSNF nebo RNF), Zhegalkin normální forma nebo Reed – Mullerova expanze je způsob psaní logických vzorců v jedné ze tří podformulí:
- Celý vzorec je čistě pravdivý nebo nepravdivý:
- 1
- 0
- Jedna nebo více proměnných jsou ANDed společně do termínu, pak jeden nebo více termínů je XORed společně do ANF. Ne NE jsou povoleny:
- a ⊕ b ⊕ ab ⊕ abc
- nebo ve standardních výrokových logických symbolech:
- Předchozí podformulář s čistě pravdivým výrazem:
- 1 ⊕ a ⊕ b ⊕ ab ⊕ abc
Vzorce napsané v ANF jsou také známé jako Zhegalkinové polynomy (ruština: полиномы Жегалкина) a pozitivní polarita (nebo parita) Reed-Mullerovy výrazy (PPRM).[1]
Běžné použití
ANF je normální forma, což znamená, že dva ekvivalentní vzorce budou převedeny na stejný ANF, což snadno ukáže, zda jsou dva vzorce ekvivalentní pro automatizované dokazování věty. Na rozdíl od jiných běžných forem jej lze reprezentovat jako jednoduchý seznam seznamů názvů proměnných. Spojovací a disjunktivní normální formy také vyžadují záznam, zda je každá proměnná negována nebo ne. Negativní normální forma je pro tento účel nevhodný, protože nepoužívá rovnost jako svůj vztah ekvivalence: a ∨ ¬a není redukováno na stejnou věc jako 1, i když jsou stejné.
Vložení vzorce do ANF také usnadňuje identifikaci lineární funkce (používané například v posuvné registry lineární zpětné vazby ): lineární funkce je funkce, která je součtem jednotlivých literálů. Vlastnosti nelineární zpětné vazby posuvné registry lze také odvodit z určitých vlastností zpětnovazební funkce v ANF.
Provádění operací v algebraické normální formě
Existují přímé způsoby, jak provádět standardní booleovské operace se vstupy ANF, abyste získali výsledky ANF.
XOR (logická výlučná disjunkce) se provádí přímo:
- (1 x x) ⊕ (1 ⊕ x ⊕ y)
- 1 x x ⊕ 1 ⊕ x ⊕ y
- 1 ⊕ 1 ⊕ x ⊕ x ⊕ y
- y
NOT (logická negace) je XORing 1:[2]
- ¬(1 ⊕ x ⊕ y)
- 1 ⊕(1 ⊕ x ⊕ y)
- 1 ⊕ 1 ⊕ x ⊕ y
- x ⊕ y
AND (logická spojka) je distribuován algebraicky[3]
- (1 ⊕ X)(1 ⊕ x ⊕ y)
- 1(1 ⊕ x ⊕ y) ⊕ X(1 ⊕ x ⊕ y)
- (1 ⊕ x ⊕ y) ⊕ (x ⊕ x ⊕ xy)
- 1 ⊕ x ⊕ x ⊕ x ⊕ y ⊕ xy
- 1 ⊕ x ⊕ y ⊕ xy
NEBO (logická disjunkce) používá buď 1 ⊕ (1 ⊕ a) (1 ⊕ b)[4] (jednodušší, když mají oba operandy čistě pravdivé výrazy) nebo a ⊕ b ⊕ ab[5] (jednodušší jinak):
- (1 x x) + (1 ⊕ x ⊕ y)
- 1 ⊕ (1 ⊕ 1 x x)(1 ⊕ 1 ⊕ x ⊕ y)
- 1 ⊕ x (x ⊕ y)
- 1 ⊕ x ⊕ xy
Převod do algebraické normální formy
Každá proměnná ve vzorci je již v čistém ANF, takže k provedení celého vzorce do ANF stačí provést booleovské operace vzorce, jak je uvedeno výše. Například:
- x + (y · ¬z)
- x + (y (1 ⊕ z))
- x + (y ⊕ yz)
- x ⊕ (y ⊕ yz) ⊕ x (y ⊕ yz)
- x ⊕ y ⊕ xy ⊕ yz ⊕ xyz
Formální zastoupení
ANF je někdy popsán ekvivalentním způsobem:
- kde plně popisuje .
Rekurzivní odvození víceznačkových booleovských funkcí
Existují pouze čtyři funkce s jedním argumentem:
K reprezentaci funkce s více argumenty lze použít následující rovnost:
- , kde
Vskutku,
- -li pak a tak
- -li pak a tak
Protože oba a mít méně argumentů než z toho vyplývá, že pomocí tohoto procesu rekurzivně skončíme s funkcemi s jednou proměnnou. Například postavme ANF z (logické nebo):
- od té doby a
- z toho vyplývá, že
- distribucí získáme konečný ANF:
Viz také
- Reed – Mullerova expanze
- Zhegalkin normální forma
- Booleovská funkce
- Logický graf
- Zhegalkinový polynom
- Negativní normální forma
- Spojovací normální forma
- Disjunktivní normální forma
- Karnaugh mapa
- Booleovský prsten
Reference
- ^ Steinbach, Bernd; Posthoff, Christian (2009). "Předmluva". Logické funkce a rovnice - příklady a cvičení (1. vyd.). Springer Science + Business Media B. V. str. xv. ISBN 978-1-4020-9594-8. LCCN 2008941076.
- ^ WolframAlpha NOT-ekvivalenční demonstrace: ¬a = 1 ⊕ a
- ^ Demonstrace ekvivalence WolframAlpha AND: (a ⊕ b) (c ⊕ d) = ac ⊕ ad ⊕ bc ⊕ bd
- ^ Z De Morganovy zákony
- ^ WolframAlpha OR-ekvivalenční demonstrace: a + b = a ⊕ b ⊕ ab
Další čtení
- Wegener, Ingo (1987). Složitost booleovských funkcí. Wiley-Teubner. str. 6. ISBN 3-519-02107-2.
- „Prezentace“ (PDF) (v němčině). University of Duisburg-Essen. Archivováno (PDF) od originálu na 2017-04-20. Citováno 2017-04-19.
- Maxfield, Clive "Max" (29. 11. 2006). „Reed-Mullerova logika“. Logika 101. EETimes. Část 3. Archivováno z původního dne 2017-04-19. Citováno 2017-04-19.