Valor de un árbol booleano
Se consideran los árboles con operaciones booleanas definidos por
|
1 2 3 4 |
data Arbol = H Bool | Conj Arbol Arbol | Disy Arbol Arbol | Neg Arbol |
Por ejemplo, los árboles
|
1 2 3 4 5 6 7 8 |
Conj Conj / \ / \ / \ / \ Disy Conj Disy Conj / \ / \ / \ / \ Conj Neg Neg True Conj Neg Neg True / \ | | / \ | | True False False False True False True False |
se definen por
|
1 2 3 4 5 6 7 8 9 10 |
ej1, ej2:: Arbol ej1 = Conj (Disy (Conj (H True) (H False)) (Neg (H False))) (Conj (Neg (H False)) (H True)) ej2 = Conj (Disy (Conj (H True) (H False)) (Neg (H True))) (Conj (Neg (H False)) (H True)) |
Definir la función
|
1 |
valor :: Arbol -> Bool |
tal que valor a) es el resultado de procesar el árbol a realizando las operaciones booleanas especificadas en los nodos. Por ejemplo,
|
1 2 |
valor ej1 == True valor ej2 == False |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
data Arbol = H Bool | Conj Arbol Arbol | Disy Arbol Arbol | Neg Arbol ej1, ej2 :: Arbol ej1 = Conj (Disy (Conj (H True) (H False)) (Neg (H False))) (Conj (Neg (H False)) (H True)) ej2 = Conj (Disy (Conj (H True) (H False)) (Neg (H True))) (Conj (Neg (H False)) (H True)) valor :: Arbol -> Bool valor (H x) = x valor (Neg a) = not (valor a) valor (Conj i d) = valor i && valor d valor (Disy i d) = valor i || valor d |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
from dataclasses import dataclass @dataclass class Arbol: pass @dataclass class H(Arbol): x: bool @dataclass class Conj(Arbol): i: Arbol d: Arbol @dataclass class Disy(Arbol): i: Arbol d: Arbol @dataclass class Neg(Arbol): a: Arbol ej1: Arbol = Conj(Disy(Conj(H(True), H(False)), (Neg(H(False)))), (Conj(Neg(H(False)), (H(True))))) ej2: Arbol = Conj(Disy(Conj(H(True), H(False)), (Neg(H(True)))), (Conj(Neg(H(False)), (H(True))))) def valor(a: Arbol) -> bool: match a: case H(x): return x case Neg(b): return not valor(b) case Conj(i, d): return valor(i) and valor(d) case Disy(i, d): return valor(i) or valor(d) assert False |
Aquí tienes una posible implementación de la función valor:
Esta función utiliza pattern matching para distinguir entre los diferentes tipos de nodos del árbol y aplicar la operación correspondiente. Por ejemplo, en el caso de un nodo Conj, se evalúan ambos hijos y se devuelve el resultado de la conjunción lógica && entre ellos. En el caso de un nodo Neg, se evalúa el único hijo y se devuelve el resultado de la negación lógica not.
Para probar esta función, puedes utilizar los ejemplos que has proporcionado: