Conteo de Modelos en Fórmulas Booleanas Guillermo De Ita Luna1, Alejandro Ramírez Cruz, Salvador Márquez Salazar Ingeniería en Informática, Universidad Politécnica de Puebla [email protected], [email protected], [email protected]

Resumen. En este trabajo se presenta una reducción polinomial del problema de conteo del número de conjuntos independientes de un grafo al conteo de modelos de una Fórmula Booleana en dos forma conjuntiva. Esta reducción permite aplicar una ecuación de recurrencia al conteo del número de modelos que hay en una Fórmula Lógica en base a la topología que se presenta en el grafo de dependencias de la fórmula. Se diseñó un algoritmo eficiente que nos permite determinar nuevas clases polinomiales para el problema de conteo del número de modelos en Fórmulas Booleanas. Palabras Clave. Grafos, Conteo de modelos, Algoritmos eficientes.

1. INTRODUCCIÓN Los problemas de conteo de objetos discretos ha sido un área de relevancia para el desarrollo de aplicaciones prácticas en la Inteligencia Artificial y, en las Ciencias de la Computación en general. La gran dificultad, sobre todo en el tiempo computacional, que requieren los métodos algorítmicos que cuentan objetos combinatorios, ha significado un reto para la comunidad científica. En este artículo, se trata el problema de contar los modelos que hay en una Fórmula de Lógica Proposicional, expresada en dos Forma Conjuntiva (conjunciones de cláusulas con dos literales), es decir, se quiere contar el número de asignaciones que construidas en base a las variables de la fórmula, satisfagan a la misma fórmula. Este problema ha sido reconocido por su carácter eminentemente exponencial en tiempo, pero la importancia práctica que tiene en el área de la lógica Matemática y de la Inteligencia Artificial, motiva a la búsqueda de algoritmos para su solución [1,2,10,11]. 2. ESTADO DEL ARTE El problema de contar el número de modelos de una fórmula proposicional F es denotado como #SAT(F). Este problema es un problema #P-completo [9], lo que significa que es uno de los problemas más difíciles, en cuanto al tiempo que se requiere para su solución. Un área de investigación, es determinar las clases de fórmulas

1

Trabajo parcialmente apoyado por la Universidad Autónoma de Puebla vía permiso de Superación Académica

Booleanas F en donde #SAT(F) pudiese resolverse de manera eficiente, es decir, en tiempos polinomiales de cómputo de acuerdo a la longitud de la fórmula F [11]. Para diseñar algoritmos líderes en la solución de estos problemas, tenemos primero que analizar las instancias básicas que puedan resolverse de manera eficiente, diseñando estrategias ad-hoc a las restricciones de estas instancias, y posteriormente, extender estas técnicas básicas considerando instancias generales del problema. 3. METODOLOGIA Un conjunto independiente de un grafo G es un subconjunto (S, V) tal que ninguno de dos vértices en S es conectado por una arista de G. al conjunto de todos los conjuntos independientes de G se le denota por I(G) y a la cardinalidad de I(G) se le denota por NI(G)=|I(G)|= Número total de conjuntos independientes que hay en G. Ejemplo: Sea G el siguiente grafo:

1

5

6

3 2

4 Figura 1 Grafo G

En este grafo se forman los siguientes conjuntos independientes: I(G)={∅,{1},{2},{3},{4},{5},{6},{1,3},{1,4},{1,6},{2,4},{2,5},{2,6},{3,5},{3,6},{5, 6},{1,3,6},{2,5,6},{3,5,6}} NI(G) = |I(G)| = 19. ¿Habrá una forma de calcular NI(G) sin tener que construir el conjunto I(G)?. Nosotros mostraremos que si hay forma de calcular NI(G), en base a la topología del grafo G. La serie de Fibonacci es una secuecnia de números, donde cada nuevo número, se forma de la suma de los dos anteriores valores de le serie. Por ejemplo: 0, 1, 1, 2, 3, 5, 8, 13, 21, y así sucesivamente. Esta sucesión fue descubierta por el matemático italiano Leonardo Fibonacci. Los números de Fibonacci tienen interesantes propiedades y se utilizan mucho en matemáticas. Las estructuras naturales, como el crecimiento de hojas en espiral en algunos árboles, presentan con frecuencia la forma de la sucesión de Fibonacci. La técnica para calcular el numero de conjuntos independientes NI(G) sobre este tipo de grafos se basa en asociar un par de valores (αi , βi) a cada nodo Vi donde i= 1,…n

conforme se va visitando cada nodo en un recorrido a lo profundo. El recorrido inicia en uno de los extremos visitando a su nodo adyacente hasta llegar al otro nodo extremo de la cadena. El primer par de valores (α1 , β1) inicia con los valores: (1,1). La relación de recurrencia a aplicar al contar el número de conjuntos independientes sobre la cadena G, considera que se conoce el valor (αi , βi) asociado al subgrafo inducido Gi de G y tal que NI(Gi)= αi + βi. El subgrafo Gi se “extiende” al adicionarle el nodo Vi+1, creándose el subgrafo inducido Gi+1 de G, por lo que se une Vi+1 con una sóla arista que va de Vi a Vi+1. Y el nuevo par de valores (αi+1, βi+1) se construye en base a (αi , βi) al aplicar la recurrencia que genera a los números de Fibonacci: αi+1 = αi + βi y βi+1 = αi La sucesión de valores (αi , βi), i=1,….,n nos permite contar NI(Gi)= αi + βi, al almacenar en αi el número de conjuntos independientes de I(Gi) en donde el nodo Vi no aparece, mientras que βi llevará el número de conjuntos independientes de I(Gi) en donde el nodo vi si aparece. Nótese que el par de números: (αi , βi) corresponde con dos consecutivos números de Fibonacci: (Fi,Fi-1), siendo Fi el i-ésimo número de Fibonacci. 3.1 Grafo de Árbol Libre. Ejemplo: Sea G un grafo dado por:

Figura 2. Grafo G representado como árbol libre La técnica para contar el número de conjuntos independientes para este tipo de grafo es la siguiente:

a]

Hay que recorrer el árbol libre G en el orden de hijos a padres (en post-orden)

b] A cada nodo V que pertenezca a G se le asocia un par de valores: (αv, βv) de la forma siguiente: c]

Si V es un nodo hoja de G entonces (αv, βv)=(1,1,)

d] Al avanzar de hijo a padre se aplica la recurrencia: αv= αu + βu , βu = αu. e]

Si el nodo V es un nodo padre de más de un hijo, por ejemplo sus nodos hijos son U1,U2…Uk. entonces al aplicar el paso (b) se obtiene una lista de parejas (αv1, βv1), (αv2, βv2)… (αvk, βvk). Cada una de ellas proviene de la aplicación de la recurrencia en (b), al avanzar de Ui a Vi, i=1,…,k la pareja final (αu, βv) que se asocial al nodo padre V, se calcula como: k

α v = ∏α vj j =1

y

β

k

v

= ∏β j =1

vj

4. PROBLEMA A RESOLVER Diseñar un algoritmo que dada como entrada una fórmula Booleana en dos forma conjuntiva (una 2-FC) nos indique cuantos modelos tiene tal fórmula. Contaremos el número de modelos que tiene una 2-FC, considerando primero las formulas monótonas (que son formas conjuntivas donde toda variable aparecerá sólo de forma positiva). Por ejemplo, supongamos una formula F monótona en 2-FC dada por F={(X1, X2), (X2, X3)} = {(X1V X2), (X2VX3)}. Dada una 2-FC F, se construye el grafo Gf de dependencias de la formula dada por: Gf=(V,E) y construida de la forma siguiente: V= var(F), cada variable de F es un nodo en Gf y E= {{v(X), v(Y)}/(X, Y) es una cláusula en F}, esto es, los vértices de Gf son las variables de F y para cada cláusula (X, Y) en F se tiene una arista que une a la variable v(X) con la variable v(Y). Diremos que una formula Booleana F es un cadena, un ciclo o un árbol libre si es que su grafo de dependencia Gf es una cadena, un ciclo o un árbol libre, respectivamente. Teorema: contar el número de modelos de una formula monótona F en 2-FC es equivalente a contar el número de conjuntos independientes en su grafo de dependencia Gf. El hecho de que si SI es un conjunto independiente de Gf nos implica que las variables que no aparecen en SI se les asigne valor lógico de “verdad” y por lo tal, cada cláusula (arista) tiene al menos una variable (vértice) que al no estar en SI toma valor verdadero.

4.1. Construcción de las ecuaciones de recurrencia para el conteo de modelo sobre 2-cláusulas Supongamos que para una variable Xi-1 se tienen αi-1 valores lógicos ‘verdad’ y βi-1 valores lógicos ‘falsos’, además que se tiene la cláusula:

C

i

=

(X E , X S ) i

i −1

i

i

Donde Ei, Si € {0,1}, es decir, la cláusula Ci puede estar en uno de cuatro diferentes casos, según los valores de Ei, Si. Para cada uno de estos casos, inferiremos la ecuación que nos permite contar el número de veces que Xi toma valor lógico ‘verdad’ y el numero de veces que Xi toma valor lógico ‘falso’ de tal forma que la cláusula Ci sea satisfecha. En general, las ecuaciones de recurrencia para el conteo de modelos, se basa en el signo de las 2 literales que aparecen en la cláusula, y que pueden expresarse como:

(αi-1, βi-1)

(βi-1, αi-1 + βi-1) Si Ci = (~Xi-1V~Xi) (αi-1 + βi-1, βi-1) Si Ci = (Xi-1VXi ) (αi-1, αi-1 + βi-1) Si Ci = (Xi-1V~Xi ) (αi-1 + βi-1, βi-1) Si Ci = (~Xi-1VXi)

Aplicando estas ecuaciones de recurrencia, se puede realizar el conteo del numero de modelos de una formula Booleana conforme se visite en una búsqueda a lo profundo cada nodo del grafo de dependencias de la formula. • El conteo de modelos inicia asignándole a la primera variable el par (1,1)= (αi βi). • Cada una de la variables Xi que aparece en la formula se le asocia un par de valores (αi βi). • Cada par (αi βi) se calcula en base a los valores del par anterior (αi-1 βi-1) según se aplique uno de los 4 casos de la ecuación de recurrencia anterior.

5. CONCLUSIONES Se presentó una aplicación del conteo de conjuntos independientes sobre un grafo no dirigido, para contar el número de modelos de formulas Booleanas. Es decir, se tuvo que dar un enfoque diferente a la solución de satisfactibilidad de una forma normal conjuntiva haciendo uso del grado del grafo de dependencias de la Fórmula Booleana y de la serie de fibonacci. Hemos presentado una transformación de complejidad polinomial del problema del conteo de conjuntos independientes al problema de contar modelos en una fórmula Bolean en dos Forma Conjuntiva. Hemos desarrollado una técnica para el conteo de modelos en base al grafo de dependencias de la fórmula. La técnica desarrollada se

basa en la aplicación de una ecuación de recurrencia conforme se visita en profundidad a cada nodo del grafo de dependencias de la fórmula, lo que nos proporciona un algoritmo de complejidad lineal en tiempo para contar modelos en caso de que el grafo de dependencias pueda recorrerse en tiempo lineal, que es el caso en que la búsqueda a lo profundo del grafo nos genere un árbol libre. Con la técnica que hemos diseñado, hemos podido establecer nuevas clases de complejidad polinomial para instancias restringidas de un conocido problema de la clase #P-completo, que es el problema #SAT(F) consistente en contar el número de modelos de una fórmula proposicional F. 6. Referencias [1] Dahllôf V., Jonsonn P., Wahlstrôm M., Counting models for 2SAT and 3SAT formulae., Theoretical Computer Sciences 332, (1-3): 265-291, 2005. [2] Darwiche Adnan, On the Tractability of Counting Theory Models and its Application to Belief Revision and Truth Maintenance, Jour. of Applied Non-classical Logics, 11(1-2), (2001), 11-34. [3] De Ita G., Polynomial Classes of Boolean Formulas for Computing the Degree of Belief, Advances in Artificial Intelligence LNAI 3315, 2004, 430-440. [4] Dyer M., Greenhill C., Some \#P-completeness Proofs for Coulorings and Independent Sets, Research Report Series, University of Leeds, 1997. [5] Eiter T., Gottlob G., The complexity of logic-based abduction, Journal of the ACM 42(1), (1995), 3-42. [6] Greenhill Catherine , The complexity of counting colourings and independent sets in sparse graphs and hypergraphs, Computational Complexity, 1999. [7] Goran Gogic, Christos H. Papadimitriou, Marta Sideri, Incremental Recompilation of Knowledge, Journal of Artificial Intelligence Research 8, (1998), 23-37. [8] Koppel M., Feldman R., Maria Segre A., Bias-Driven Revision of Logical Domain Theories, Jour. of Artificial Intelligence Research 1, (1994), 159-208. [9] Roth D., On the hardness of approximate reasoning, Artificial Intelligence 82, (1996), 273302. [10] Russ B., Randomized Algorithms: Approximation, Generation, and Counting, Distingished dissertations Springer, 2001. [11] Vadhan Salil P., The complexity of Counting in Sparse, Regular, and Planar Graphs, SIAM Journal on Computing, Vol. 31, No.2, (2001), 398-427.