{"id":5596,"date":"2020-02-26T05:30:50","date_gmt":"2020-02-26T03:30:50","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=5596"},"modified":"2020-03-04T07:58:05","modified_gmt":"2020-03-04T05:58:05","slug":"grafo-de-una-fnc-formula-en-forma-normal-conjuntiva","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/grafo-de-una-fnc-formula-en-forma-normal-conjuntiva\/","title":{"rendered":"Grafo de una FNC (f\u00f3rmula en forma normal conjuntiva)"},"content":{"rendered":"<p>Para reducir el problema del clique a SAT se comienza asociando a cada f\u00f3rmula F en FNC un grafo G de forma que F es saisfacible si, y s\u00f3lo si, G tiene un clique con tantos nodos como cl\u00e1usulas tiene F.<\/p>\n<p>Los nodos del grafo de F son los literales de las cl\u00e1usulas de F junto con el n\u00famero de la cl\u00e1usula. Por ejemplo, la lista de nodos de la FNC [[1,-2,3],[-1,2],[-2,3]] es<\/p>\n<pre lang=\"text\">\n   [(0,1),(0,-2),(0,3),\n    (1,-1),(1,2),\n    (2,-2),(2,3)]\n<\/pre>\n<p>En el grafo de F, hay un arco entre dos nodos si, y solo si, corresponden a cl\u00e1usulas distintas y sus literales no son complementarios. Por ejemplo,<\/p>\n<ul>\n<li>hay un arco entre (0,1) y (1,2) [porque son de cl\u00e1usulas distintas (0 y 1) y sus literales (1 y 2) no son complementarios.<\/li>\n<li>no hay un arco entre (0,1) y (1,-1) [porque sus literales (1 y -1) no son complementarios. <\/li>\n<li>no hay un arco entre (0,1) y (0,3) [porque son de la misma cl\u00e1usula (la 0)].<\/li>\n<\/ul>\n<p>Nota: En este ejercicio se usar\u00e1 los conceptos de los anteriores importando los m\u00f3dulos <code>Evaluacion_de_FNC<\/code> y <code>Grafo<\/code>.<\/p>\n<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   nodosFNC :: FNC -> [(Int,Literal)]\n   grafoFNC :: FNC -> Grafo (Int,Literal)\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(nodosFNC f) es la lista de los nodos del grafo de f. Por ejemplo,  <\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> nodosFNC [[1,-2,3],[-1,2],[-2,3]]\n     [(0,1),(0,-2),(0,3),(1,-1),(1,2),(2,-2),(2,3)]\n<\/pre>\n<ul>\n<li>(grafo FNC f) es el grafo de f. Por ejemplo, <\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> grafoFNC [[1,-2,3],[-1,2],[-2,3]]\n     [ ((0,1),(1,2)),  ((0,1),(2,-2)), ((0,1),(2,3)),\n       ((0,-2),(1,-1)),((0,-2),(2,-2)),((0,-2),(2,3)),\n       ((0,3),(1,-1)), ((0,3),(1,2)),  ((0,3),(2,-2)),((0,3),(2,3)),\n       ((1,-1),(2,-2)),((1,-1),(2,3)),\n       ((1,2),(2,3))]\n     \u03bb> grafoFNC [[1,2],[1,-2],[-1,2],[-1,-2]]\n     [((0,1),(1,1)),((0,1),(1,-2)),((0,1),(2,2)),((0,1),(3,-2)),\n      ((0,2),(1,1)),((0,2),(2,-1)),((0,2),(2,2)),((0,2),(3,-1)),\n      ((1,1),(2,2)),((1,1),(3,-2)),\n      ((1,-2),(2,-1)),((1,-2),(3,-1)),((1,-2),(3,-2)),\n      ((2,-1),(3,-1)),((2,-1),(3,-2)),\n      ((2,2),(3,-1))]\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nmodule Grafo_FNC where\n\nimport Evaluacion_de_FNC\nimport Grafo\nimport Data.List (tails)\n\nnodosFNC :: FNC -> [(Int,Literal)]\nnodosFNC f = \n  [(i,x) | (i,xs) <- zip [0..] f\n         , x <- xs]\n\ngrafoFNC :: FNC -> Grafo (Int,Literal)\ngrafoFNC f = \n  [ ((i,x),(i',x'))\n  | ((i,x),(i',x')) <- parejas (nodosFNC f)\n  , i' \/= i\n  , x' \/= negate x]\n\n-- (parejas xs) es la lista de las parejas formados por los elementos de\n-- xs y sus siguientes en xs. Por ejemplo, \n--    parejas [1..4] == [(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)]\nparejas :: [a] -> [(a,a)]\nparejas xs =\n  [(x,y) | (x:ys) <- tails xs\n         , y <- ys]\n<\/pre>\n<h4>Otras soluciones<\/h4>\n<ul>\n<li>Se pueden escribir otras soluciones en los comentarios.\n<li>El c\u00f3digo se debe escribir entre una l\u00ednea con &#60;pre lang=\"haskell\"&#62; y otra con &#60;\/pre&#62;\n<\/ul>\n<h4>Pensamiento<\/h4>\n<blockquote><p>\n\"Las matem\u00e1ticas tienen dos caras: son la ciencia rigurosa de Euclides, pero tambi\u00e9n son algo m\u00e1s. La matem\u00e1tica presentada a la manera euclidiana aparece como una ciencia sistem\u00e1tica y deductiva; pero la matem\u00e1tica en ciernes aparece como una ciencia experimental e inductiva. Ambos aspectos son tan antiguos como la propia ciencia de las matem\u00e1ticas.\" <\/p>\n<p><a href=\"https:\/\/en.wikipedia.org\/wiki\/George_P%C3%B3lya\">George P\u00f3lya<\/a>.\n<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"<p>Para reducir el problema del clique a SAT se comienza asociando a cada f\u00f3rmula F en FNC un grafo G de forma que F es saisfacible si, y s\u00f3lo si, G tiene un clique con tantos nodos como cl\u00e1usulas tiene F. Los nodos del grafo de F son los literales de las cl\u00e1usulas de F&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[4],"tags":[8,434,75,9],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5596"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=5596"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5596\/revisions"}],"predecessor-version":[{"id":5655,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5596\/revisions\/5655"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=5596"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=5596"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=5596"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}