Lista tautológica de literales
En lógica matemática, un literal http://bit.ly/1RQ5yJU es una fórmula atómica o su negación. Se puede definir por el tipo de dato
|
1 2 3 |
data Literal = Atom String | Neg Literal deriving (Eq, Show) |
Por ejemplo, el literal los literales p y ¬q se representan por las expresiones (Atom «p») y (Neg (Atom «q»)), respectivamente.
Una lista de literales (que se interpreta como su disyunción) es un tautología si contiene a una fórmula atómica y su negación.
Definir la función
|
1 |
tautologia :: [Literal] -> Bool |
tal que (tautologia xs) se verifica si la lista de literales xs es una tautología. Por ejemplo,
|
1 2 3 4 5 6 |
λ> tautologia [Atom "p", Neg (Atom "q"), Neg (Atom "p")] True λ> tautologia [Atom "p", Neg (Atom "q"), Neg (Atom "r")] False λ> tautologia [Atom "p", Neg (Atom "q"), Neg (Atom "q")] False |
Soluciones
[schedule expon=’2016-01-21′ expat=»06:00″]
- Las soluciones se pueden escribir en los comentarios hasta el 21 de enero.
- El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>
[/schedule]
[schedule on=’2016-01-21′ at=»06:00″]
|
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 |
import Data.List (intersect) data Literal = Atom String | Neg Literal deriving (Eq, Show) -- 1ª solución -- =========== tautologia1 :: [Literal] -> Bool tautologia1 xs = or [elem x xs && elem (Neg x) xs | x <- xs] -- 2ª solución -- =========== tautologia2 :: [Literal] -> Bool tautologia2 xs = not (null (intersect ns (map neg ps))) where (ps,ns) = span esPositivo xs neg x = Neg x esPositivo :: Literal -> Bool esPositivo (Atom _) = True esPositivo _ = False -- Comparación de eficiencia -- ========================= -- λ> tautologia1 (replicate 4000 (Atom "p")) -- False -- (6.70 secs, 1031428 bytes) -- λ> tautologia2 (replicate 4000 (Atom "p")) -- False -- (0.01 secs, 1061604 bytes) |
[/schedule]