Funkce jednorázového čtení - Read-once function - Wikipedia

V matematice, a funkce jen pro čtení je speciální typ Booleovská funkce které lze popsat a Booleovský výraz ve kterém každý proměnná se zobrazí pouze jednou.

Přesněji řečeno, výraz je vyžadován pouze k použití operací logická spojka, logická disjunkce, a negace. Aplikováním De Morganovy zákony, takový výraz lze transformovat do takového, ve kterém se negace použije pouze na jednotlivé proměnné (stále se každá proměnná objevuje pouze jednou). Nahrazením každé negované proměnné novou pozitivní proměnnou představující její negaci lze takovou funkci transformovat na ekvivalent pozitivní read-once booleovská funkce, představovaná výrazem jen pro čtení bez negací.[1]

Příklady

Například pro tři proměnné A, b, a C, výrazy

, a

jsou všechny pro jednorázové čtení (stejně jako ostatní funkce získané permutací proměnných v těchto výrazech). Nicméně booleovský medián operace, daná výrazem

není přečteno jednou: tento vzorec obsahuje více než jednu kopii každé proměnné a neexistuje ekvivalentní vzorec, který používá každou proměnnou pouze jednou.[2]

Charakterizace

The disjunktivní normální forma (pozitivní) funkce pro čtení jednou není obvykle sama pro čtení. Přesto s sebou nese důležité informace o funkci. Zejména pokud jeden tvoří a graf společného výskytu ve kterém vrcholy představují proměnné a hrany spojují páry proměnných, které se vyskytují ve stejné klauzi konjunktivní normální formy, pak je graf společného výskytu funkce pro čtení jednou nutně cograph. Přesněji řečeno, pozitivní booleovská funkce je přečtena pouze tehdy a jen tehdy, pokud je jejím grafem společného výskytu cograph, a navíc každý maximální klika grafu společného výskytu tvoří jednu ze spojek (hlavních implikantů) disjunktivní normální formy.[3] To znamená, že když je interpretován jako funkce na sadách vrcholů grafu společného výskytu, funkce read-once platí pro sady vrcholů, které obsahují maximální kliku, a jinak false. Například mediánová funkce má stejný graf společného výskytu jako spojení tří proměnných, a trojúhelníkový graf, ale úplný vrchol tří grafů tohoto grafu (celý graf) tvoří podmnožinu klauze pouze pro konjunkci a ne pro medián.[4]V grafu společného výskytu sousedí dvě proměnné pozitivního výrazu jen pro čtení jednou a jen tehdy, pokud jsou nejnižší společný předek ve výrazu je spojka,[5] takže výrazový strom může být interpretován jako kotré pro příslušný graf.[6]

Další alternativní charakterizace pozitivních funkcí jednorázového čtení kombinuje jejich disjunktivní a konjunktivní normální forma. Pozitivní funkce daného systému proměnných, která využívá všechny své proměnné, je jednou přečtena, pouze pokud každý primární implikant disjunktivní normální formy a každá klauzule normální formy spojky mají právě jednu společnou proměnnou.[7]

Uznání

Je možné rozpoznat funkce jen pro čtení z jejich disjunktivních výrazů normální formy v polynomiální čas.[8]Je také možné najít výraz jen pro čtení pro pozitivní funkci jen pro čtení, který má přístup k funkci pouze prostřednictvím „černé skříňky“, která umožňuje její vyhodnocení kdykoli přiřazení pravdy, používající pouze kvadratický počet vyhodnocení funkcí.[9]

Poznámky

  1. ^ Golumbic & Gurvich (2011), str. 519.
  2. ^ Golumbic & Gurvich (2011), str. 520.
  3. ^ Golumbic & Gurvich (2011), Věta 10.1, str. 521; Golumbic, Mintz & Rotics (2006).
  4. ^ Golumbic & Gurvich (2011), Příklady F2 a F3, str. 521.
  5. ^ Golumbic & Gurvich (2011), Lemma 10.1, s. 529.
  6. ^ Golumbic & Gurvich (2011), Poznámka 10.4, s. 540–541.
  7. ^ Gurvič (1977); Mundici (1989); Karchmer a kol. (1993).
  8. ^ Golumbic & Gurvich (2011), Věta 10.8, s. 541; Golumbic, Mintz & Rotics (2006); Golumbic, Mintz & Rotics (2008).
  9. ^ Golumbic & Gurvich (2011), Věta 10.9, s. 548; Angluin, Hellerstein & Karpinski (1993).

Reference

  • Angluin, Dana; Hellerstein, Lisa; Karpinski, Marek (1993), „Learning formulas for read-once with queries“, Deník ACM, 40 (1): 185–210, CiteSeerX  10.1.1.7.5033, doi:10.1145/138027.138061, PAN  1202143.
  • Golumbic, Martin C.; Gurvich, Vladimir (2011), "Funkce jednorázového čtení" (PDF)v Crama, Yves; Hammer, Peter L. (eds.), Booleovské funkceEncyklopedie matematiky a její aplikace, 142, Cambridge University Press, Cambridge, str. 519–560, doi:10.1017 / CBO9780511852008, ISBN  978-0-521-84751-3, PAN  2742439.
  • Golumbic, Martin Charles; Mintz, Aviad; Rotics, Udi (2006), „Factoring and recognition of read-once functions using cographs and normalality and the readability of functions associated with partial k-stromy ", Diskrétní aplikovaná matematika, 154 (10): 1465–1477, doi:10.1016 / j.dam.2005.09.016, PAN  2222833.
  • Golumbic, Martin Charles; Mintz, Aviad; Rotics, Udi (2008), „Zlepšení složitosti factoringových jednorázových booleovských funkcí“, Diskrétní aplikovaná matematika, 156 (10): 1633–1636, doi:10.1016 / j.dam.2008.02.011, PAN  2432929.
  • Gurvič, V. A. (1977), "Logické funkce bez opakování", Uspekhi Matematicheskikh Nauk, 32 (1(193)): 183–184, PAN  0441560.
  • Karchmer, M .; Linial, N.; Newman, I .; Saks, M.; Wigderson, A. (1993), „Kombinatorická charakterizace vzorců pro jednorázové čtení“, Diskrétní matematika, 114 (1–3): 275–282, doi:10.1016 / 0012-365X (93) 90372-Z, PAN  1217758.
  • Mundici, Daniele (1989), „Funkce počítané monotónními booleovskými vzorci bez opakovaných proměnných“, Teoretická informatika, 66 (1): 113–114, doi:10.1016/0304-3975(89)90150-3, PAN  1018849.