Läs en gång funktion

Inom matematik är en read-once-funktion en speciell typ av boolesk funktion som kan beskrivas med ett booleskt uttryck där varje variabel endast förekommer en gång.

Mer exakt krävs att uttrycket endast använder operationerna logisk konjunktion , logisk disjunktion och negation . Genom att tillämpa De Morgans lagar kan ett sådant uttryck omvandlas till ett där negation endast används på individuella variabler (fortfarande med varje variabel endast en gång). Genom att ersätta varje negerad variabel med en ny positiv variabel som representerar dess negation, kan en sådan funktion transformeras till en ekvivalent positiv läs-en gång boolesk funktion, representerad av ett read-once uttryck utan negationer.

Exempel

Till exempel, för tre variabler a , b och c , uttrycken

$a\wedge b\wedge c$

$a\wedge (b\vee c)$

$(a\wedge b)\vee c$ och

$a\vee b\vee c$

är alla lästa en gång (liksom de andra funktionerna som erhålls genom att permutera variablerna i dessa uttryck). Den booleska medianoperationen , som ges av uttrycket

$(a\vee b)\wedge (a\vee c)\wedge (b\vee c)$

är inte läs en gång: den här formeln har mer än en kopia av varje variabel, och det finns ingen likvärdig formel som använder varje variabel bara en gång.

Karakterisering

Den disjunktiva normala formen av en (positiv) read-once-funktion är i allmänhet inte i sig read-once. Ändå innehåller den viktig information om funktionen. I synnerhet, om man bildar en graf för samtidig förekomst där hörnen representerar variabler, och kanter förbinder par av variabler som båda förekommer i samma sats i den konjunktiva normalformen, så är grafen för samtidig förekomst för en engångsfunktion. nödvändigtvis en kograf . Mer precist, en positiv boolesk funktion läses en gång om och endast om dess samförekomstgraf är en kograf, och dessutom bildar varje maximal klick av samförekomstgrafen en av konjunktionerna (primära implikanter) av den disjunktiva normalformen . Det vill säga, när den tolkas som en funktion på uppsättningar av hörn i dess graf med samtidig förekomst, är en läs-en gångsfunktion sann för uppsättningar av hörn som innehåller en maximal klick, och i övrigt falsk. Till exempel har medianfunktionen samma graf med samtidig förekomst som konjunktionen av tre variabler, en triangelgraf , men den fullständiga subgrafen med tre vertex i denna graf (hela grafen) bildar en delmängd av en sats endast för konjunktionen och inte för medianen. Två variabler för ett positivt läs-engångsuttryck finns intill i grafen för samtidig förekomst om och endast om deras lägsta gemensamma förfader i uttrycket är en konjunktion, så uttrycksträdet kan tolkas som ett samträd för motsvarande kograf.

En annan alternativ karaktärisering av positiva read-once-funktioner kombinerar deras disjunktiva och konjunktiva normala form . En positiv funktion av ett givet system av variabler, som använder alla dess variabler, läses en gång om och endast om varje primimplikant av den disjunktiva normalformen och varje sats i den konjunktiva normalformen har exakt en variabel gemensam.

Erkännande

Det är möjligt att känna igen read-once-funktioner från deras disjunktiva normala formuttryck i polynomtid . Det är också möjligt att hitta ett läs-engångsuttryck för en positiv läs-engångsfunktion, med tillgång till funktionen endast genom en "svart låda" som tillåter dess utvärdering vid vilken sanningsuppgift som helst , med endast ett kvadratiskt antal funktionsutvärderingar .

Anteckningar

•     Angluin, Dana ; Hellerstein, Lisa; Karpinski, Marek (1993), "Learning read-once formulas with queries", Journal of the ACM , 40 (1): 185–210, CiteSeerX 10.1.1.7.5033 , doi : 10.1145/138027.138061 , 621 MR 4061 , 612 4061 , 612 4061 .
•    Golumbic, Martin C .; Gurvich, Vladimir (2011), "Read-once functions" (PDF) , i Crama, Yves; Hammer, Peter L. (red.), Boolean functions , Encyclopedia of Mathematics and its Applications, vol. 142, Cambridge University Press, Cambridge, s. 519–560, doi : 10.1017/CBO9780511852008 , ISBN 978-0-521-84751-3 , MR 2742439 .
•   Golumbic, Martin Charles ; Mintz, Aviad; Rotics, Udi (2006), "Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial k -trees", Discrete Applied Mathematics , 154 (10): 1465–1477, doi : 10.1016/ j.dam.2005.09.016 , MR 2222833 .
•   Golumbic, Martin Charles ; Mintz, Aviad; Rotics, Udi (2008), "An improvement on the complexity of factoring read-once Boolean functions", Discrete Applied Mathematics , 156 (10): 1633–1636, doi : 10.1016/j.dam.2008.02.011 , MR 2322994 .
•   Gurvič, VA (1977), "Repetitionsfria booleska funktioner" , Uspekhi Matematicheskikh Nauk , 32 (1(193)): 183–184, MR 0441560 .
•   Karchmer, M.; Linial, N .; Newman, I.; Saks, M .; Wigderson, A. (1993), "Combinatorial characterization of read-once formulae", Discrete Mathematics , 114 (1–3): 275–282, doi : 10.1016/0012-365X(93)90372-Z , MR 5 8 121777 .
•   Mundici, Daniele (1989), "Funktioner beräknade av monotona booleska formler utan upprepade variabler", Theoretical Computer Science , 66 (1): 113–114, doi : 10.1016/0304-3975(89)90150-3 , MR 490 18 .