{"id":4708,"date":"2019-02-14T06:00:26","date_gmt":"2019-02-14T04:00:26","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=4708"},"modified":"2019-02-21T07:27:58","modified_gmt":"2019-02-21T05:27:58","slug":"simplificacion-de-expresiones-booleanas","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/simplificacion-de-expresiones-booleanas\/","title":{"rendered":"Simplificaci\u00f3n de expresiones booleanas"},"content":{"rendered":"<p>El siguiente tipo de dato algebraico representa las expresiones booleanas construidas con una variable (X), las constantes verdadera (V) y falsa (F), la negaci\u00f3n (Neg) y la disyunci\u00f3n (Dis):<\/p>\n<pre lang=\"text\"> \n   data Expr = X\n             | V\n             | F\n             | Neg Expr\n             | Dis Expr Expr\n             deriving (Eq, Ord)\n<\/pre>\n<p>Por ejemplo, la f\u00f3rmula (\u00acX v V) se representa por (Dis (Neg X) V).<\/p>\n<p>Definir las funciones<\/p>\n<pre lang=\"text\"> \n   valor      :: Expr -> Bool -> Bool \n   simplifica :: Expr -> Expr\n<\/pre>\n<p>tales que (valor p i) es el valor de la f\u00f3rmula p cuando se le asigna a X el valor i. Por ejemplo,<\/p>\n<pre lang=\"text\"> \n   valor (Neg X) True           ==  False\n   valor (Neg F) True           ==  True\n   valor (Dis X (Neg X)) True   ==  True\n   valor (Dis X (Neg X)) False  ==  True\n<\/pre>\n<p>y (simplifica p) es una expresi\u00f3n obtenida aplic\u00e1ndole a p las siguientes reglas de simplificaci\u00f3n:<\/p>\n<pre lang=\"text\"> \n   Neg V       = F\n   Neg F       = V\n   Neg (Neg q) = q\n   Dis V q     = V\n   Dis F q     = q\n   Dis q V     = V\n   Dis q F     = F\n   Dis q q     = q\n<\/pre>\n<p>Por ejemplo,<\/p>\n<pre lang=\"text\"> \n   simplifica (Dis X (Neg (Neg X)))                      ==  X\n   simplifica (Neg (Dis (Neg (Neg X)) F))                ==  Neg X\n   simplifica (Dis (Neg F) F)                            ==  V\n   simplifica (Dis (Neg V) (Neg (Dis (Neg X) F)))        ==  X\n   simplifica (Dis (Neg V) (Neg (Dis (Neg (Neg X)) F)))  ==  Neg X\n<\/pre>\n<p>Comprobar con QuickCheck que para cualquier f\u00f3rmula p y cualquier booleano i se verifica que (valor (simplifica p) i) es igual a (valor p i).<\/p>\n<p>Para la comprobaci\u00f3n, de define el generador<\/p>\n<pre lang=\"text\"> \n   instance Arbitrary Expr where\n     arbitrary = sized expr\n       where expr n | n <= 0    = atom\n                    | otherwise = oneof [ atom\n                                        , liftM Neg subexpr\n                                        , liftM2 Dis subexpr subexpr ]\n               where atom    = oneof [elements [X,V,F]]\n                     subexpr = expr (n `div` 2)\n<\/pre>\n<p>que usa las funciones liftM y liftM2 de la librer\u00eda Control.Monad que hay que importar al principio.<\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Test.QuickCheck\nimport Control.Monad \n\ndata Expr = X\n          | V\n          | F\n          | Neg Expr\n          | Dis Expr Expr\n          deriving (Eq, Ord, Show)\n\nvalor :: Expr -> Bool -> Bool \nvalor X i         = i\nvalor V _         = True\nvalor F _         = False\nvalor (Neg p) i   = not (valor p i)\nvalor (Dis p q) i = valor p i || valor q i\n\nsimplifica :: Expr -> Expr\nsimplifica X = X\nsimplifica V = V\nsimplifica F = F\nsimplifica (Neg p) = negacion (simplifica p)\n  where negacion V       = F\n        negacion F       = V\n        negacion (Neg p) = p\n        negacion p       = Neg p\nsimplifica (Dis p q) = disyuncion (simplifica p) (simplifica q)\n  where disyuncion V q = V\n        disyuncion F q = q\n        disyuncion q V = V\n        disyuncion q F = q\n        disyuncion p q | p == q    = p\n                       | otherwise = Dis p q\n\n-- La propiedad es\nprop_simplifica :: Expr -> Bool -> Bool\nprop_simplifica p i =\n  valor (simplifica p) i == valor p i\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_simplifica\n--    +++ OK, passed 100 tests.\n\n-- Generador de f\u00f3rmulas\ninstance Arbitrary Expr where\n  arbitrary = sized expr\n    where expr n | n <= 0    = atom\n                 | otherwise = oneof [ atom\n                                     , liftM Neg subexpr\n                                     , liftM2 Dis subexpr subexpr ]\n            where atom    = oneof [elements [X,V,F]]\n                  subexpr = expr (n `div` 2)\n<\/pre>\n<h4>Pensamiento<\/h4>\n<blockquote><p>\n\u00bfDices que nada se pierde?<br \/>\nSi esta copa de cristal<br \/>\nse me rompe, nunca en ella<br \/>\nbeber\u00e9, nunca jam\u00e1s.<\/p>\n<p>Antonio Machado\n<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"<p>El siguiente tipo de dato algebraico representa las expresiones booleanas construidas con una variable (X), las constantes verdadera (V) y falsa (F), la negaci\u00f3n (Neg) y la disyunci\u00f3n (Dis): data Expr = X | V | F | Neg Expr | Dis Expr Expr deriving (Eq, Ord) Por ejemplo, la f\u00f3rmula (\u00acX v V) se&#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":[7],"tags":[6,146,133],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4708"}],"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=4708"}],"version-history":[{"count":5,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4708\/revisions"}],"predecessor-version":[{"id":4754,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4708\/revisions\/4754"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=4708"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=4708"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=4708"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}