El tipo de las fórmulas proposicionales se puede definir por
data FProp = Const Bool
| Var Char
| Neg FProp
| Conj FProp FProp
| Impl FProp FProp
deriving Show |
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
Impl (Var 'A') (Conj (Const False) (Neg (Var 'B'))) |
Impl (Var 'A') (Conj (Const False) (Neg (Var 'B')))
Una fórmula es una tautología si es verdadera en todas sus interpretaciones. Por ejemplo,
(A ∧ B) → A
es una tautología
A → (A ∧ B)
no es una tautología
Definir la función
esTautologia :: FProp -> Bool |
esTautologia :: FProp -> Bool
tal que esTautologia p
se verifica si la fórmula p
es una tautología. Por ejemplo,
λ> esTautologia (Impl (Conj (Var 'A') (Var 'B')) (Var 'A'))
True
λ> esTautologia (Impl (Var 'A') (Conj (Var 'A') (Var 'B')))
False |
λ> esTautologia (Impl (Conj (Var 'A') (Var 'B')) (Var 'A'))
True
λ> esTautologia (Impl (Var 'A') (Conj (Var 'A') (Var 'B')))
False
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
Soluciones en Haskell
import Data.List (nub)
data FProp = Const Bool
| Var Char
| Neg FProp
| Conj FProp FProp
| Impl FProp FProp
deriving Show
type Interpretacion = [(Char, Bool)]
esTautologia :: FProp -> Bool
esTautologia p =
and [valor i p | i <- interpretaciones p]
-- (valor i p) es el valor de la fórmula p en la interpretación i. Por
-- ejemplo,
-- λ> p = Impl (Var 'A') (Conj (Var 'A') (Var 'B'))
-- λ> valor [('A',False),('B',False)] p
-- True
-- λ> valor [('A',True),('B',False)] p
-- False
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']
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 |
import Data.List (nub)
data FProp = Const Bool
| Var Char
| Neg FProp
| Conj FProp FProp
| Impl FProp FProp
deriving Show
type Interpretacion = [(Char, Bool)]
esTautologia :: FProp -> Bool
esTautologia p =
and [valor i p | i <- interpretaciones p]
-- (valor i p) es el valor de la fórmula p en la interpretación i. Por
-- ejemplo,
-- λ> p = Impl (Var 'A') (Conj (Var 'A') (Var 'B'))
-- λ> valor [('A',False),('B',False)] p
-- True
-- λ> valor [('A',True),('B',False)] p
-- False
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']
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
Soluciones en Python
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
# 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]
# interpretaciones(p) es la lista de las interpretaciones de la fórmula
# p. Por ejemplo,
# >>> interpretaciones(Impl(Var('A'), Conj(Var('A'), Var('B'))))
# [[('B', False), ('A', False)],
# [('B', False), ('A', True)],
# [('B', True), ('A', False)],
# [('B', True), ('A', True)]]
def interpretaciones(f: FProp) -> list[Interpretacion]:
vs = list(set(variables(f)))
return [list(zip(vs, i)) for i in interpretacionesVar(len(vs))]
def esTautologia(p: FProp) -> bool:
return all((valor(i, p) for i in interpretaciones(p))) |
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
# 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]
# interpretaciones(p) es la lista de las interpretaciones de la fórmula
# p. Por ejemplo,
# >>> interpretaciones(Impl(Var('A'), Conj(Var('A'), Var('B'))))
# [[('B', False), ('A', False)],
# [('B', False), ('A', True)],
# [('B', True), ('A', False)],
# [('B', True), ('A', True)]]
def interpretaciones(f: FProp) -> list[Interpretacion]:
vs = list(set(variables(f)))
return [list(zip(vs, i)) for i in interpretacionesVar(len(vs))]
def esTautologia(p: FProp) -> bool:
return all((valor(i, p) for i in interpretaciones(p)))