{"id":2520,"date":"2013-02-19T16:43:05","date_gmt":"2013-02-19T16:43:05","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=2520"},"modified":"2013-03-08T05:47:34","modified_gmt":"2013-03-08T05:47:34","slug":"i1m2012-un-programa-en-haskell-para-decidir-tautologias","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2012-un-programa-en-haskell-para-decidir-tautologias\/","title":{"rendered":"I1M2012: Un programa en Haskell para decidir tautolog\u00edas"},"content":{"rendered":"

En la segunda parte de la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> se ha estudiado c\u00f3mo definir el tipo de las f\u00f3rmulas proposicionales y, trabajando con dicho tipo, construir un programa para determinar si una f\u00f3rmula es una tautolog\u00eda.<\/p>\n

El c\u00f3digo correspondiente es
\n<\/p>\n

\r\n-- Las f\u00f3rmulas proposicionales se definen por:\r\n--    * Las constantes booleanas son f\u00f3rmulas proposicionales.\r\n--    * Las f\u00f3rmulas at\u00f3micas son f\u00f3rmulas proposicionales.\r\n--    * Si F es una f\u00f3mula proposicional, entonces -F tambi\u00e9n los es.\r\n--    * Si F y F son f\u00f3rmulas proposicionales, entonces (F \/\\ G) y \r\n--      (F -> G) tambi\u00e9n lo son.\r\ndata Prop = Const Bool\r\n          | Var Char\r\n          | Neg Prop\r\n          | Conj Prop Prop\r\n          | Impl Prop Prop\r\n          deriving Show\r\n\r\n-- Ejemplos de representaci\u00f3n de f\u00f3rmulas proposicionales: Las f\u00f3rmulas\r\n--    * p1 := A \/\\ -A\r\n--    * p2 := (A \/\\ B) -> A\r\n--    * p3 := A -> (A \/\\ B)\r\n--    * p4 := (A -> (A -> B)) -> B\r\n-- se representan por\r\np1, p2, p3, p4 :: Prop\r\np1 = Conj (Var 'A') (Neg (Var 'A'))\r\np2 = Impl (Conj (Var 'A') (Var 'B')) (Var 'A')\r\np3 = Impl (Var 'A') (Conj (Var 'A') (Var 'B'))\r\np4 = Impl (Conj (Var 'A') (Impl (Var 'A') (Var 'B'))) (Var 'B')\r\n\r\n-- Las interpretaciones son listas formadas por el nombre de una\r\n-- variable proposicional y un valor de verdad. \r\ntype Interpretacion = Asoc Char Bool\r\n\r\n-- (valor i p) es el valor de la proposici\u00f3n p en la interpretaci\u00f3n\r\n-- i. Por ejemplo, \r\n--    valor [('A',False),('B',True)] p3  =>  True\r\n--    valor [('A',True),('B',False)] p3  =>  False\r\nvalor :: Interpretacion -> Prop -> Bool\r\nvalor _ (Const b)  = b\r\nvalor i (Var x)    = busca x i\r\nvalor i (Neg p)    = not (valor i p)\r\nvalor i (Conj p q) = valor i p && valor i q\r\nvalor i (Impl p q) = valor i p <= valor i q\r\n\r\n-- (variables p) es la lista de los nombres de las variables de la\r\n-- f\u00f3rmula p. Por ejemplo,\r\n--    variables p3  ==  \"AAB\"\r\nvariables :: Prop -> [Char]\r\nvariables (Const _)  = []\r\nvariables (Var x)    = [x]\r\nvariables (Neg p)    = variables p\r\nvariables (Conj p q) = variables p ++ variables q\r\nvariables (Impl p q) = variables p ++ variables q\r\n\r\n-- (interpretacionesVar n) es la lista de las interpretaciones con n\r\n-- variables. Por ejemplo, \r\n--    *Main> interpretacionesVar 2\r\n--    [[False,False],\r\n--     [False,True],\r\n--     [True,False],\r\n--     [True,True]]\r\ninterpretacionesVar :: Int -> [[Bool]]\r\ninterpretacionesVar 0     = [[]]\r\ninterpretacionesVar (n+1) = map (False:) bss ++ map (True:) bss\r\n    where bss = interpretacionesVar n\r\n\r\n-- (interpretaciones p) es la lista de las interpretaciones de la\r\n-- f\u00f3rmula p. Por ejemplo, \r\n--    *Main> interpretaciones p3\r\n--    [[('A',False),('B',False)],\r\n--     [('A',False),('B',True)],\r\n--     [('A',True),('B',False)],\r\n--     [('A',True),('B',True)]]\r\ninterpretaciones :: Prop -> [Interpretacion]\r\ninterpretaciones p =  \r\n    map (zip vs) (interpretacionesVar (length vs))\r\n    where vs = nub (variables p)\r\n\r\n-- Una definici\u00f3n alternativa es\r\ninterpretaciones' :: Prop -> [Interpretacion]\r\ninterpretaciones' p =  \r\n    [zip vs i | i <- is]\r\n    where vs = nub (variables p)\r\n          is = (interpretacionesVar (length vs))\r\n\r\n-- (esTautologia p) se verifica si la f\u00f3rmula p es una tautolog\u00eda. Por\r\n-- ejemplo, \r\n--    esTautologia p1  =>  False\r\n--    esTautologia p2  =>  True\r\n--    esTautologia p3  =>  False\r\n--    esTautologia p4  =>  True\r\nesTautologia :: Prop -> Bool\r\nesTautologia p = and [valor i p | i <- interpretaciones p]\r\n<\/pre>\n
 Las transparencias usadas en la clase son las del tema 9<\/a> (p\u00e1ginas 25-33):
\n