{"id":5545,"date":"2020-02-12T05:30:28","date_gmt":"2020-02-12T03:30:28","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=5545"},"modified":"2020-02-19T18:35:35","modified_gmt":"2020-02-19T16:35:35","slug":"evaluacion-de-fnc-formulas-en-forma-normal-conjuntiva","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/evaluacion-de-fnc-formulas-en-forma-normal-conjuntiva\/","title":{"rendered":"Evaluaci\u00f3n de FNC (f\u00f3rmulas en forma normal conjuntiva)"},"content":{"rendered":"<p>Una FNC (<a href=\"http:\/\/bit.ly\/2UHJqZB\">f\u00f3rmula en forma normal conjuntiva<\/a>) es una conjunci\u00f3n de cl\u00e1usulas, donde una cl\u00e1usula es una disyunci\u00f3n de literales y un literal es un \u00e1tomo o su negaci\u00f3n. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   (x(1) v -x(3)) & x(2) & (-x(2) v x(3) v x(1))\n<\/pre>\n<p>es una FNC con tres cl\u00e1sulas tales que la primera cl\u00e1usula tiene 2 literales (x(1) y -x(3)), la segunda tiene 1 (x(2)) y la tercera tiene 3 (-x(2), x(3) y x(1)).<\/p>\n<p>Usaremos las siguientes representaciones:<\/p>\n<ul>\n<li>Los \u00e1tomos se representan por enteros positivos. Por ejemplo, 3 representa x(3). <\/li>\n<li>Los literales se representan por enteros. Por ejemplo, 3 representa el literal positivo x(3) y -5 el literal negativo -x(5).<\/li>\n<li>Una cl\u00e1usula es una lista de literales que representa la disyunci\u00f3n se sus literales. Por ejemplo, [3,2,-4] representa a (x(3) v x(2) v -x(4)).<\/li>\n<li>Una f\u00f3rmula en forma normal conjuntiva (FNC) es una lista de cl\u00e1usulas que representa la conjunci\u00f3n de sus cl\u00e1usulas. Por ejemplo, [[3,2],[-1,2,5]] representa a ((x(3) v x(2)) &amp; (-x(1) v x(2) v x(5))).<\/li>\n<\/ul>\n<p>Una interpretaci\u00f3n I es un conjunto de \u00e1tomos. Se supone que los \u00e1tomos de I son verdaderos y los restantes son falsos. Por ejemplo, en la interpretaci\u00f3n [2,5]<\/p>\n<ul>\n<li>el literal x(2) es verdadero (porque 2 \u2208 [2,5])<\/li>\n<li>el literal x(3) es falso (porque 3 \u2209 [2,5])<\/li>\n<li>el literal -x(4) es verdadero (porque 4 \u2209 [2,5])<\/li>\n<li>la cl\u00e1usula (x(2) v x(3)) es verdadera (porque x(2) es verdadero)<\/li>\n<li>la cl\u00e1usula (x(3) v x(4)) es falsa (porque x(3) y x(4) son falsos)<\/li>\n<li>la FNC ((x(2) v x(5)) &amp; (-x(4) v x(3)) es verdadera porque lo son sus dos cl\u00e1usulas<\/li>\n<\/ul>\n<p>En el ejercicio se usar\u00e1n los siguientes tipos de datos<\/p>\n<pre lang=\"text\">\n   type Atomo          = Int\n   type Literal        = Int\n   type Clausula       = [Literal]\n   type FNC            = [Clausula]\n   type Interpretacion = [Atomo]\n<\/pre>\n<p>Definir las siguientes funciones<\/p>\n<pre lang=\"text\">\n   valorLiteral  :: Interpretacion -> Literal -> Bool\n   valorClausula :: Interpretacion -> Clausula -> Bool\n   valor         :: Interpretacion -> FNC -> Bool\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(valorLiteral i l) es el valor del literal l en la interpretaci\u00f3n i. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">  \n     valorLiteral [3,5] 3     ==  True\n     valorLiteral [3,5] 4     ==  False\n     valorLiteral [3,5] (-3)  ==  False\n     valorLiteral [3,5] (-4)  ==  True\n<\/pre>\n<ul>\n<li>(valorClausula i c) es el valor de la cl\u00e1usula c en la interpretaci\u00f3n i. Por ejemplo, <\/li>\n<\/ul>\n<pre lang=\"text\">  \n     valorClausula [3,5] [2,3,-5]  ==  True\n     valorClausula [3,5] [2,4,-1]  ==  True\n     valorClausula [3,5] [2,4,1]   ==  False\n<\/pre>\n<ul>\n<li>(valor i f) es el valor de la f\u00f3rmula en FNC f en la interpretaci\u00f3n i. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">  \n     valor [1,3] [[1,-2],[3]]  ==  True\n     valor [1]   [[1,-2],[3]]  ==  False\n     valor [1]   []            ==  True\n<\/pre>\n<p><strong>Nota<\/strong>: Escribir la soluci\u00f3n en el m\u00f3dulo Evaluacion_de_FNC para poderlo usar en los siguientes ejercicios.<\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nmodule Evaluacion_de_FNC where\n\ntype Atomo          = Int\ntype Literal        = Int\ntype Clausula       = [Literal]\ntype FNC            = [Clausula]\ntype Interpretacion = [Atomo]\n\n-- Definici\u00f3n de valorLiteral\n-- ==========================\n\nvalorLiteral :: Interpretacion -> Literal -> Bool\nvalorLiteral i l\n  | l > 0     = l `elem` i\n  | otherwise = negate l `notElem` i\n\n-- Definiciones de valorClausula\n-- =============================\n\n-- 1\u00aa definici\u00f3n\nvalorClausula :: Interpretacion -> Clausula -> Bool\nvalorClausula i c = or [valorLiteral i l | l <- c]\n\n-- 2\u00aa definici\u00f3n\nvalorClausula2 :: Interpretacion -> Clausula -> Bool\nvalorClausula2 i = any (valorLiteral i)\n\n-- Definiciones de valor de FNC\n-- ============================\n\n-- 1\u00aa definici\u00f3n\nvalor :: Interpretacion -> FNC -> Bool\nvalor i f = and [valorClausula i c | c <- f]\n\n-- 2\u00aa definici\u00f3n\nvalor2 :: Interpretacion -> FNC -> Bool\nvalor2 i = all (valorClausula i)\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=\u00bbhaskell\u00bb&#62; y otra con &#60;\/pre&#62;\n<\/ul>\n<h4>Pensamiento<\/h4>\n<blockquote><p>\n\u00abTodo buen matem\u00e1tico es al menos medio fil\u00f3sofo, y todo buen fil\u00f3sofo es al menos medio matem\u00e1tico.\u00bb <\/p>\n<p><a href=\"https:\/\/en.wikipedia.org\/wiki\/Gottlob_Frege\">Gottlob Frege<\/a>.\n<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"<p>Una FNC (f\u00f3rmula en forma normal conjuntiva) es una conjunci\u00f3n de cl\u00e1usulas, donde una cl\u00e1usula es una disyunci\u00f3n de literales y un literal es un \u00e1tomo o su negaci\u00f3n. Por ejemplo, (x(1) v -x(3)) &#038; x(2) &#038; (-x(2) v x(3) v x(1)) es una FNC con tres cl\u00e1sulas tales que la primera cl\u00e1usula tiene 2&#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":[5],"tags":[41,100,163,8,26,27,169,11],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5545"}],"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=5545"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5545\/revisions"}],"predecessor-version":[{"id":5607,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5545\/revisions\/5607"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=5545"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=5545"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=5545"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}