PFH: La semana en Exercitium (3 de diciembre de 2022)
Esta semana he publicado en Exercitium las soluciones de los siguientes problemas:
- 1. El tipo de las listas
- 2. El tipo de los árboles binarios
- 3. El tipo de las fórmulas proposicionales: Variables de una fórmula
- 4. El tipo de las fórmulas proposicionales: Valor de una fórmula
- 5. El tipo de las fórmulas proposicionales: Interpretaciones de una fórmula
A continuación se muestran las soluciones.
1. El tipo de las listas
El tipo de las listas, con elementos de tipo a, se puede definir por
|
1 |
data Lista a = Nil | Cons a (Lista a) |
Por ejemplo, la lista [4,2,5] se representa por Cons 4 (Cons 2 (Cons 5 Nil)).
Definir la función
|
1 |
longitud :: Lista a -> Int |
tal que longitud xs es la longitud de la lista xs. Por ejemplo,
|
1 |
longitud (Cons 4 (Cons 2 (Cons 5 Nil))) == 3 |
1.1. Soluciones en Haskell
|
1 2 3 4 5 |
data Lista a = Nil | Cons a (Lista a) longitud :: Lista a -> Int longitud Nil = 0 longitud (Cons _ xs) = 1 + longitud xs |
1.2. Soluciones en Python
|
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 |
from dataclasses import dataclass from typing import Generic, TypeVar A = TypeVar("A") @dataclass class Lista(Generic[A]): pass @dataclass class Nil(Lista[A]): pass @dataclass class Cons(Lista[A]): x: A xs: Lista[A] def longitud(xs: Lista[A]) -> int: match xs: case Nil(): return 0 case Cons(_, xs): return 1 + longitud(xs) assert False |
2. El tipo de los árboles binarios
El árbol binario
|
1 2 3 4 5 6 |
5 / \ / \ 3 7 / \ / \ 1 4 6 9 |
se puede representar por
|
1 2 3 |
ejArbol = Nodo (Nodo (Hoja 1) 3 (Hoja 4)) 5 (Nodo (Hoja 6) 7 (Hoja 9)) |
El tipo de los árboles binarios se puede definir por
|
1 2 |
data Arbol = Hoja Int | Nodo Arbol Int Arbol |
Definir las funciones
|
1 2 |
ocurre :: Int -> Arbol -> Bool aplana :: Arbol -> [Int] |
tales que
ocurre m ase verifica simocurre en el árbola. Por ejemplo,
|
1 2 |
ocurre 4 ejArbol == True ocurre 10 ejArbol == False |
aplana aes la lista obtenida aplanando el árbola. Por ejemplo,
|
1 |
aplana ejArbol == [1,3,4,5,6,7,9] |
2.1. Soluciones en Haskell
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
data Arbol = Hoja Int | Nodo Arbol Int Arbol ejArbol :: Arbol ejArbol = Nodo (Nodo (Hoja 1) 3 (Hoja 4)) 5 (Nodo (Hoja 6) 7 (Hoja 9)) ocurre :: Int -> Arbol -> Bool ocurre m (Hoja n) = m == n ocurre m (Nodo i n d) = m == n || ocurre m i || ocurre m d aplana :: Arbol -> [Int] aplana (Hoja n) = [n] aplana (Nodo i n d) = aplana i ++ [n] ++ aplana d |
2.2. Soluciones en Python
|
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 |
from dataclasses import dataclass @dataclass class Arbol: pass @dataclass class Hoja(Arbol): x: int @dataclass class Nodo(Arbol): i: Arbol x: int d: Arbol ejArbol = Nodo(Nodo(Hoja(1), 3, Hoja(4)), 5, Nodo(Hoja(6), 7, Hoja(9))) def ocurre(m: int, a: Arbol) -> bool: match a: case Hoja(n): return m == n case Nodo(i, n, d): return m == n or ocurre(m, i) or ocurre(m, d) assert False def aplana(a: Arbol) -> list[int]: match a: case Hoja(n): return [n] case Nodo(i, n, d): return aplana(i) + [n] + aplana(d) assert False |
3. El tipo de las fórmulas proposicionales: Variables de una fórmula
El tipo de las fórmulas proposicionales se puede definir por
|
1 2 3 4 5 6 |
data FProp = Const Bool | Var Char | Neg FProp | Conj FProp FProp | Impl FProp FProp deriving Show |
de modo que la fórmula A → ⊥ ∧ ¬B se representa por
|
1 |
Impl (Var 'A') (Conj (Const False) (Neg (Var 'B'))) |
Definir la función
|
1 |
variables :: FProp -> [Char] |
tal que variables p es la lista de las variables de la fórmula p. Por ejemplo,
|
1 2 3 4 |
λ> variables (Impl (Var 'A') (Conj (Const False) (Neg (Var 'B')))) "AB" λ> variables (Impl (Var 'A') (Conj (Var 'A') (Neg (Var 'B')))) "AAB" |
3.1. Soluciones en Haskell
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
data FProp = Const Bool | Var Char | Neg FProp | Conj FProp FProp | Impl FProp FProp deriving Show variables :: FProp -> [Char] variables (Const _) = [] variables (Var x) = [x] variables (Neg p) = variables p variables (Conj p q) = variables p ++ variables q variables (Impl p q) = variables p ++ variables q |
3.2. Soluciones en Python
|
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 |
from dataclasses import dataclass @dataclass class FProp: pass @dataclass class Const(FProp): x: bool @dataclass class Var(FProp): x: str @dataclass class Neg(FProp): x: FProp @dataclass class Conj(FProp): x: FProp y: FProp @dataclass class Impl(FProp): x: FProp y: FProp def variables(f: FProp) -> list[str]: match f: case Const(_): return [] case Var(x): return [x] case Neg(p): return variables(p) case Conj(p, q): return variables(p) + variables(q) case Impl(p, q): return variables(p) + variables(q) assert False |
4. El tipo de las fórmulas proposicionales: Valor de una fórmula
El tipo de las fórmulas proposicionales se puede definir por
|
1 2 3 4 5 6 |
data FProp = Const Bool | Var Char | Neg FProp | Conj FProp FProp | Impl FProp FProp deriving Show |
de modo que la fórmula A → ⊥ ∧ ¬B se representa por
|
1 |
Impl (Var 'A') (Conj (Const False) (Neg (Var 'B'))) |
Una interpretación de una fórmula es una función de sus variables en los booleanos. Por ejemplo, la interpretación que a la variable A le asigna verdadero y a la B falso se puede representar por
|
1 |
[('A', True), ('B', False)] |
El tipo de las intepretaciones de puede definir por
|
1 |
type Interpretacion = [(Char, Bool)] |
El valor de una fórmula en una interpretación se calcula usando las funciones de verdad de las conectivas que se muestran a continuación
|
1 2 3 4 5 6 7 8 |
|---+----| |---+---+-------+-------| | p | ¬p | | p | q | p ∧ q | p → q | |---+----| |---+---+-------+-------| | T | F | | T | T | T | T | | F | T | | T | F | F | F | |---+----| | F | T | F | T | | F | F | F | T | |---+---+-------+-------| |
Definir la función
|
1 |
valor :: Interpretacion -> FProp -> Bool |
tal que valor i p es el valor de la fórmula p en la interpretación i. Por ejemplo,
|
1 2 3 4 5 |
λ> p = Impl (Var 'A') (Conj (Var 'A') (Var 'B')) λ> valor [('A',False),('B',False)] p True λ> valor [('A',True),('B',False)] p False |
4.1. Soluciones en Haskell
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
data FProp = Const Bool | Var Char | Neg FProp | Conj FProp FProp | Impl FProp FProp deriving Show type Interpretacion = [(Char, Bool)] valor :: Interpretacion -> FProp -> Bool valor _ (Const b) = b valor i (Var x) = busca x i valor i (Neg p) = not (valor i p) valor i (Conj p q) = valor i p && valor i q valor i (Impl p q) = valor i p <= valor i q -- (busca c t) es el valor del primer elemento de la lista de asociación -- t cuya clave es c. Por ejemplo, -- busca 2 [(1,'a'),(3,'d'),(2,'c')] == 'c' busca :: Eq c => c -> [(c,v)] -> v busca c t = head [v | (c',v) <- t, c == c'] |
4.2. Soluciones en Python
|
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 46 47 48 49 50 51 |
from dataclasses import dataclass @dataclass class FProp: pass @dataclass class Const(FProp): x: bool @dataclass class Var(FProp): x: str @dataclass class Neg(FProp): x: FProp @dataclass class Conj(FProp): x: FProp y: FProp @dataclass class Impl(FProp): x: FProp y: FProp Interpretacion = list[tuple[str, bool]] # busca(c, t) es el valor del primer elemento de la lista de asociación # t cuya clave es c. Por ejemplo, # >>> busca('B', [('A', True), ('B', False), ('C', True)]) # False def busca(c: str, i: Interpretacion) -> bool: return [v for (d, v) in i if d == c][0] def valor(i: Interpretacion, f: FProp) -> bool: match f: case Const(b): return b case Var(x): return busca(x, i) case Neg(p): return not valor(i, p) case Conj(p, q): return valor(i, p) and valor(i, q) case Impl(p, q): return valor(i, p) <= valor(i, q) assert False |
5. El tipo de las fórmulas proposicionales: Interpretaciones de una fórmula
El tipo de las fórmulas proposicionales se puede definir por
|
1 2 3 4 5 6 |
data FProp = Const Bool | Var Char | Neg FProp | Conj FProp FProp | Impl FProp FProp deriving Show |
de modo que la fórmula A → ⊥ ∧ ¬B se representa por
|
1 |
Impl (Var 'A') (Conj (Const False) (Neg (Var 'B'))) |
Una interpretación de una fórmula es una función de sus variables en los booleanos. Por ejemplo, la interpretación que a la variable A le asigna verdadero y a la B falso se puede representar por
|
1 |
[('A', True), ('B', False)] |
El tipo de las intepretaciones de puede definir por
|
1 |
type Interpretacion = [(Char, Bool)] |
Definir la función
|
1 |
interpretaciones :: FProp -> [Interpretacion] |
tal que interpretaciones p es la lista de las interpretaciones de la fórmula p. Por ejemplo,
|
1 2 3 4 5 |
λ> interpretaciones (Impl (Var 'A') (Conj (Var 'A') (Var 'B'))) [[('A',False),('B',False)], [('A',False),('B',True)], [('A',True),('B',False)], [('A',True),('B',True)]] |
5.1. Soluciones en Haskell
|
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 |
import Data.List (nub) data FProp = Const Bool | Var Char | Neg FProp | Conj FProp FProp | Impl FProp FProp deriving Show type Interpretacion = [(Char, Bool)] interpretaciones :: FProp -> [Interpretacion] interpretaciones p = [zip vs i | i <- interpretacionesVar (length vs)] where vs = nub (variables p) -- (interpretacionesVar n) es la lista de las interpretaciones de n -- variables. Por ejemplo, -- λ> interpretacionesVar 2 -- [[False,False], -- [False,True], -- [True,False], -- [True,True]] interpretacionesVar :: Int -> [[Bool]] interpretacionesVar 0 = [[]] interpretacionesVar n = map (False:) bss ++ map (True:) bss where bss = interpretacionesVar (n-1) -- (variables p) es la lista de las variables de la fórmula p. Por -- ejemplo, -- λ> variables (Impl (Var 'A') (Conj (Const False) (Neg (Var 'B')))) -- "AB" -- λ> variables (Impl (Var 'A') (Conj (Var 'A') (Neg (Var 'B')))) -- "AAB" variables :: FProp -> [Char] variables (Const _) = [] variables (Var x) = [x] variables (Neg p) = variables p variables (Conj p q) = variables p ++ variables q variables (Impl p q) = variables p ++ variables q |
5.2. Soluciones en Python
|
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 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
from dataclasses import dataclass @dataclass class FProp: pass @dataclass class Const(FProp): x: bool @dataclass class Var(FProp): x: str @dataclass class Neg(FProp): x: FProp @dataclass class Conj(FProp): x: FProp y: FProp @dataclass class Impl(FProp): x: FProp y: FProp Interpretacion = list[tuple[str, bool]] # variables(p) es la lista de las variables de la fórmula p. Por # ejemplo, # >>> variables (Impl(Var('A'), Conj(Const(False), Neg (Var('B'))))) # ['A', 'B'] # >>> variables (Impl(Var('A'), Conj(Var('A'), Neg (Var('B'))))) # ['A', 'A', 'B'] def variables(f: FProp) -> list[str]: match f: case Const(_): return [] case Var(x): return [x] case Neg(p): return variables(p) case Conj(p, q): return variables(p) + variables(q) case Impl(p, q): return variables(p) + variables(q) assert False # interpretacionesVar(n) es la lista de las interpretaciones de n # variables. Por ejemplo, # >>> interpretacionesVar 2 # [[False, False], # [False, True], # [True, False], # [True, True]] def interpretacionesVar(n: int) -> list[list[bool]]: if n == 0: return [[]] bss = interpretacionesVar(n-1) return [[False] + x for x in bss] + [[True] + x for x in bss] def interpretaciones(f: FProp) -> list[Interpretacion]: vs = list(set(variables(f))) return [list(zip(vs, i)) for i in interpretacionesVar(len(vs))] |