Función de lectura única

En matemáticas, una función de lectura única es un tipo especial de función booleana que se puede describir mediante una expresión booleana en la que cada variable aparece solo una vez.

Más precisamente, la expresión debe utilizar únicamente las operaciones de conjunción lógica , disyunción lógica y negación . Aplicando las leyes de De Morgan , dicha expresión puede transformarse en una en la que la negación se utiliza solo en variables individuales (apareciendo cada variable solo una vez). Reemplazando cada variable negada por una nueva variable positiva que represente su negación, dicha función puede transformarse en una función booleana equivalente de lectura única positiva , representada por una expresión de lectura única sin negaciones. ^{[ 1 ]}

Por ejemplo, para tres variables a , b y c , las expresiones

${\displaystyle a\wedge b\wedge c}$

${\displaystyle a\wedge (b\vee c)}$

${\displaystyle (a\wedge b)\vee c}$, y

${\displaystyle a\vee b\vee c}$

Todas son de lectura única (al igual que las otras funciones obtenidas al permutar las variables en estas expresiones). Sin embargo, la operación mediana booleana , dada por la expresión

${\displaystyle (a\vee b)\wedge (a\vee c)\wedge (b\vee c)}$

no es de lectura única: esta fórmula tiene más de una copia de cada variable, y no existe una fórmula equivalente que utilice cada variable solo una vez. ^{[ 2 ]}

La forma normal disyuntiva de una función de lectura única (positiva) generalmente no es en sí misma de lectura única. Sin embargo, contiene información importante sobre la función. En particular, si se forma un grafo de coocurrencia en el que los vértices representan variables y las aristas conectan pares de variables que aparecen en la misma cláusula de la forma normal conjuntiva, entonces el grafo de coocurrencia de una función de lectura única es necesariamente un cografo . Más precisamente, una función booleana positiva es de lectura única si y solo si su grafo de coocurrencia es un cografo, y además cada clique maximal del grafo de coocurrencia forma una de las conjunciones (implicantes primos) de la forma normal disyuntiva. ^{[ 3 ]} Es decir, cuando se interpreta como una función sobre conjuntos de vértices de su grafo de coocurrencia, una función de lectura única es verdadera para conjuntos de vértices que contienen un clique maximal, y falsa en caso contrario. Por ejemplo, la función mediana tiene el mismo grafo de coocurrencia que la conjunción de tres variables, un grafo triangular , pero el subgrafo completo de tres vértices de este grafo (el grafo completo) forma un subconjunto de una cláusula solo para la conjunción y no para la mediana. ^{[ 4 ]} Dos variables de una expresión positiva de lectura única son adyacentes en el grafo de coocurrencia si y solo si su ancestro común más bajo en la expresión es una conjunción, ^{[ 5 ]} por lo que el árbol de la expresión puede interpretarse como un coárbol para el cografo correspondiente. ^{[ 6 ]}

Otra caracterización alternativa de las funciones positivas de lectura única combina su forma normal disyuntiva y conjuntiva . Una función positiva de un sistema de variables dado, que utiliza todas sus variables, es de lectura única si y solo si cada implicante primo de la forma normal disyuntiva y cada cláusula de la forma normal conjuntiva tienen exactamente una variable en común. ^{[ 7 ]}

Es posible reconocer funciones de lectura única a partir de sus expresiones de forma normal disyuntiva en tiempo polinomial . ^{[ 8 ]} También es posible encontrar una expresión de lectura única para una función de lectura única positiva, dado el acceso a la función solo a través de una "caja negra" que permite su evaluación en cualquier asignación de verdad , utilizando solo un número cuadrático de evaluaciones de la función. ^{[ 9 ]}