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, se requiere que la expresión utilice solo las operaciones de conjunción lógica , disyunción lógica y negación . Al aplicar las leyes de De Morgan , una expresión de este tipo se puede transformar en una en la que la negación se utiliza solo en variables individuales (aún con cada variable apareciendo solo una vez). Al reemplazar cada variable negada con una nueva variable positiva que representa su negación, una función de este tipo se puede transformar en una función booleana positiva de lectura única equivalente, representada por una expresión de lectura única sin negaciones. [1]
Por ejemplo, para tres variables a , b y c , las expresiones
son todas de lectura única (al igual que las demás funciones obtenidas al permutar las variables en estas expresiones). Sin embargo, la operación de mediana booleana , dada por la expresión
no se lee una sola vez: esta fórmula tiene más de una copia de cada variable y no existe una fórmula equivalente que use cada variable solo una vez. [2]
La forma normal disyuntiva de una función (positiva) de lectura única no es generalmente 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 ocurren 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 camarilla máxima 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 en conjuntos de vértices de su grafo de coocurrencia, una función de lectura única es verdadera para conjuntos de vértices que contienen una camarilla máxima, y falsa en caso contrario. Por ejemplo, la función mediana tiene el mismo gráfico de coocurrencia que la conjunción de tres variables, un gráfico triangular , pero el subgrafo completo de tres vértices de este gráfico (el gráfico 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 gráfico 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 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 en 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 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 función. [9]
