{"id":7767,"date":"2023-01-04T06:00:02","date_gmt":"2023-01-04T04:00:02","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=7767"},"modified":"2022-12-29T09:26:24","modified_gmt":"2022-12-29T07:26:24","slug":"04-ene-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/04-ene-23\/","title":{"rendered":"Valor de un \u00e1rbol booleano"},"content":{"rendered":"

Se consideran los \u00e1rboles con operaciones booleanas definidos por<\/p>\n

\n   data Arbol = H Bool\n              | Conj Arbol Arbol\n              | Disy Arbol Arbol\n              | Neg Arbol\n<\/pre>\n
Por ejemplo, los \u00e1rboles<\/p>\n
\n               Conj                            Conj\n              \/   \\                           \/   \\\n             \/     \\                         \/     \\\n          Disy      Conj                  Disy      Conj\n         \/   \\       \/  \\                \/   \\      \/   \\\n      Conj    Neg   Neg True          Conj    Neg   Neg  True\n      \/  \\    |     |                 \/  \\    |     |\n   True False False False          True False True  False\n<\/pre>\n
se definen por<\/p>\n
\n   ej1, ej2:: Arbol\n   ej1 = Conj (Disy (Conj (H True) (H False))\n                    (Neg (H False)))\n              (Conj (Neg (H False))\n                    (H True))\n\n   ej2 = Conj (Disy (Conj (H True) (H False))\n                    (Neg (H True)))\n              (Conj (Neg (H False))\n                    (H True))\n<\/pre>\n
Definir la funci\u00f3n<\/p>\n
\n   valor :: Arbol -> Bool\n<\/pre>\n
tal que valor a<\/code>) es el resultado de procesar el \u00e1rbol a<\/code> realizando las operaciones booleanas especificadas en los nodos. Por ejemplo,<\/p>\n
\n   valor ej1 == True\n   valor ej2 == False\n<\/pre>\n
Soluciones<\/b><\/p>\n
A continuaci\u00f3n se muestran las soluciones en Haskell<\/a> y las soluciones en Python<\/a>.<\/p>\n
<\/a>
\nSoluciones en Haskell<\/b><\/p>\n
\ndata Arbol = H Bool\n           | Conj Arbol Arbol\n           | Disy Arbol Arbol\n           | Neg Arbol\n\nej1, ej2 :: Arbol\nej1 = Conj (Disy (Conj (H True) (H False))\n                 (Neg (H False)))\n           (Conj (Neg (H False))\n                 (H True))\n\nej2 = Conj (Disy (Conj (H True) (H False))\n                 (Neg (H True)))\n           (Conj (Neg (H False))\n                 (H True))\n\nvalor :: Arbol -> Bool\nvalor (H x)      = x\nvalor (Neg a)    = not (valor a)\nvalor (Conj i d) = valor i && valor d\nvalor (Disy i d) = valor i || valor d\n<\/pre>\n
<\/a>
\nSoluciones en Python<\/b><\/p>\n
\nfrom dataclasses import dataclass\n\n@dataclass\nclass Arbol:\n    pass\n\n@dataclass\nclass H(Arbol):\n    x: bool\n\n@dataclass\nclass Conj(Arbol):\n    i: Arbol\n    d: Arbol\n\n@dataclass\nclass Disy(Arbol):\n    i: Arbol\n    d: Arbol\n\n@dataclass\nclass Neg(Arbol):\n    a: Arbol\n\nej1: Arbol = Conj(Disy(Conj(H(True), H(False)),\n                       (Neg(H(False)))),\n                  (Conj(Neg(H(False)),\n                        (H(True)))))\n\nej2: Arbol = Conj(Disy(Conj(H(True), H(False)),\n                       (Neg(H(True)))),\n                  (Conj(Neg(H(False)),\n                        (H(True)))))\n\ndef valor(a: Arbol) -> bool:\n    match a:\n        case H(x):\n            return x\n        case Neg(b):\n            return not valor(b)\n        case Conj(i, d):\n            return valor(i) and valor(d)\n        case Disy(i, d):\n            return valor(i) or valor(d)\n    assert False\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
Se consideran los \u00e1rboles con operaciones booleanas definidos por data Arbol = H Bool | Conj Arbol Arbol | Disy Arbol Arbol | Neg Arbol Por ejemplo, los \u00e1rboles Conj Conj \/ \\ \/ \\ \/ \\ \/ \\ Disy Conj Disy Conj \/ \\ \/ \\ \/ \\ \/ \\ Conj Neg Neg True…<\/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":[581],"tags":[269],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7767"}],"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=7767"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7767\/revisions"}],"predecessor-version":[{"id":7768,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7767\/revisions\/7768"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=7767"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=7767"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=7767"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}