在 Haskell 中生成逻辑表达式的真值表

Question

第一部分是具有以下类型签名的求值函数：

evaluate :: Logic Expr -> [(Variable, Bool)] -> Bool

它采用逻辑表达式和赋值对列表作为输入，并根据提供的布尔赋值返回表达式的值。 赋值列表是一个不同的对列表，其中每对包含一个变量及其布尔赋值。 也就是说，如果将表达式 A ∧ B 和赋值 A = 1 且 B = 0 传递给函数，则函数必须返回 0（这来自数字逻辑设计，0 对应于 false，1 对应于 true）。

这就是我到目前为止所做的：

type Variable =  Char

data LogicExpr = V Variable
                 | Negation  LogicExpr
                 | Conjunction LogicExpr LogicExpr
                 | Disjunction  LogicExpr LogicExpr 
                 | Implication  LogicExpr LogicExpr 


evaluate :: LogicExpr -> [(Variable,Bool)] -> Bool

evaluate (V a) ((x1,x2):xs) | a==x1 = x2
                            | otherwise = (evaluate(V a)xs)

evaluate (Negation a) l | (evaluate a l)==True = False
                        | otherwise = True

evaluate (Conjunction a b) l = (evaluate a l)&&(evaluate b l)

evaluate (Disjunction a b) l = (evaluate a l)||(evaluate b l)

evaluate (Implication a b) l
    | (((evaluate b l)==False)&&((evaluate a l)==True)) = False
    | otherwise = True

下一部分是定义generateTruthTable，它是一个函数，它将逻辑表达式作为输入并以列表的形式返回表达式的真值表作业对列表。 也就是说，如果将表达式 E = A ∧ B 传递给函数，则函数必须返回 A = 0, B = 0, E = 0 | A = 0，B = 1，E = 0 | A = 1，B = 0，E = 0 | A = 1，B = 1，E = 1。

我不太熟悉语法，所以我不知道如何返回列表。

Answer 1

标准库函数，代码复用。 另外，你的括号用法和间距真的很糟糕。

evaluate (V a) l =
    case lookup a l
      of Just x -> x
         Nothing -> error $ "Unbound variable: " ++ show a
-- same as
evaluate (V a) l = maybe (error $ "Unbound variable: " ++ show a) id $ lookup a l

evaluate (Negation a) l = not $ evaluate a l

evaluate (Implication a b) l = evaluate (Negation a `Disjunction` b) l

现在，您想要一个generateTruthTable吗？ 这很简单，只需获取布尔变量的所有可能状态，并将计算的表达式附加到每个变量的末尾即可。

generateTruthTable :: [Variable] -> LogicExpr -> [[(Variable, Bool)]]
generateTruthTable vs e = [l ++ [('E', evaluate e l)] | l <- allPossible vs]

如果你有一个函数来生成所有这些可能的状态就好了。

allPossible :: [Variable] -> [[(Variable, Bool)]]

根据我的功能性直觉，这感觉应该是一种变形。 毕竟，它确实需要查看列表中的所有内容，但返回不同结构的内容，并且它可能可以以简单的方式分解，因为这是一个入门级 CS 类。 （我不在乎课程编号是什么，这是介绍性的东西。）

allPossible = foldr step initial where
    step v ls = ???; initial = ???

现在，foldr :: (a -> b -> b) -> b-> [一]-> b，所以前两个参数必须是step::a -> b-> b 和 initial :: b。 现在，allPossible :: [Variable] -> [[(Variable, Bool)]] =foldr 步骤初始 :: [a] -> b。 嗯，这肯定意味着 a = Variable 和 b = [[(Variable, Bool)]]。 这对于 step 和 initial 意味着什么？

    step :: Variable -> [[(Variable, Bool)]] -> [[(Variable, Bool)]]
    initial :: [[(Variable, Bool)]]

有趣的。 无论如何，需要有一种方法从变量状态列表中step并向其中添加单个变量，以及一些根本没有变量的initial列表。

如果您已经成功地“点击”了函数式编程范例，那么这应该已经足够了。 如果没有，那么无论您在这里收到什么指示，在作业到期时的几个小时内您都会被搞砸。 祝你好运，如果你在作业到期后仍然遇到困难，你应该询问你的教授，或者在这里问一个不紧急的问题。

---

如果您对该语言有基本的可用性问题（“语法是什么”、“运行时语义是什么”、“xxx 是否有预先存在的功能”等） ：

• Haskell 98 语言和库 是基础语言和库的免费提供的规范定义。 更多链接可在 Haskell wiki 上找到。
• 有关 98 后语言扩展，请参阅 GHC文档。
• GHC、Hugs 和其他现代 Haskell 实现还提供了比 Haskell 98 中指定的更丰富的标准库。 分层库也可以在线获取。
• Hoogλe 是扩展 Haskell 标准库的专用搜索引擎。 Hayoo! 类似，但也涵盖 HackageDB，远远超出标准发行版的 Haskell 库的集合。

我希望你们的班级提供了类似的资源，但如果没有，以上所有内容都可以通过 Google 搜索轻松找到。

如果有适当的参考，任何值得自己salt的程序员都应该能够掌握语法在几个小时内掌握任何新语言，并在几天内对运行时有一个有效的理解。 当然，掌握一种新范式可能需要很长时间，而且让学生遵守相同的标准有些不公平，但这就是课程的目的。

关于 Stack Overflow 上更高级别问题的问题可能会得到更少的答案，但他们也会得到更少的脾气:)家庭作业问题被归类为“为我做我的工作！” 在大多数人眼里。

---

剧透

请不要作弊。 然而，只是为了让您体验一下 Haskell 可以完成多么出色的事情......

{-# LANGUAGE FlexibleInstances, UndecidableInstances #-}
{-# LANGUAGE OverlappingInstances, PatternGuards #-}

module Expr (Ring(..), (=:>), Expr(..), vars, eval, evalAll) where

import Control.Monad.Error

infixl 5 =:>, :=>
infixl 6 +:, -:, :+, :-
infixl 7 *:, :*

class (Eq a) => Ring a where
    (+:) :: a -> a -> a; (-:) :: a -> a -> a; x -: y = x +: invert y
    (*:) :: a -> a -> a; invert :: a -> a; invert x = zero -: x
    zero :: a; one :: a
(=:>) :: (Ring a) => a -> a -> a
(=:>) = flip (-:)

instance (Num a) => Ring a where
    (+:) = (+); (-:) = (-); (*:) = (*)
    invert = negate; zero = 0; one = 1

instance Ring Bool where
    (+:) = (||); (*:) = (&&)
    invert = not; zero = False; one = True

data Expr a b
  = Expr a b :+ Expr a b | Expr a b :- Expr a b
  | Expr a b :* Expr a b | Expr a b :=> Expr a b
  | Invert (Expr a b) | Var a | Const b

paren :: ShowS -> ShowS
paren ss s = '(' : ss (')' : s)

instance (Show a, Show b) => Show (Expr a b) where
    showsPrec _ (Const c) = ('@':) . showsPrec 9 c
    showsPrec _ (Var v) = ('
$ ghci
GHCi, version 6.10.2: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer ... linking ... done.
Loading package base ... linking ... done.
Prelude> :l Expr.hs
[1 of 1] Compiling Expr             ( Expr.hs, interpreted )
Ok, modules loaded: Expr.
*Expr> mapM_ print . evalAll [1..3] 'C' $ Var 'A' :* Var 'B'
Loading package mtl-1.1.0.2 ... linking ... done.
[('A',1),('B',1),('C',1)]
[('A',1),('B',2),('C',2)]
[('A',1),('B',3),('C',3)]
[('A',2),('B',1),('C',2)]
[('A',2),('B',2),('C',4)]
[('A',2),('B',3),('C',6)]
[('A',3),('B',1),('C',3)]
[('A',3),('B',2),('C',6)]
[('A',3),('B',3),('C',9)]
*Expr> let expr = Var 'A' :=> (Var 'B' :+ Var 'C') :* Var 'D'
*Expr> expr

:) . showsPrec 9 v
    showsPrec _ (Invert e) = ('!':) . showsPrec 9 e

    showsPrec n e@(a:=>b)
      | n > 5 = paren $ showsPrec 0 e
      | otherwise = showsPrec 7 a . ('=':) . ('>':) . showsPrec 5 b

    showsPrec n e@(a:*b)
      | n > 7 = paren $ showsPrec 0 e
      | otherwise = showsPrec 7 a . ('*':) . showsPrec 7 b

    showsPrec n e | n > 6 = paren $ showsPrec 0 e
    showsPrec _ (a:+b) = showsPrec 6 a . ('+':) . showsPrec 6 b
    showsPrec _ (a:-b) = showsPrec 6 a . ('-':) . showsPrec 6 b

vars :: (Eq a) => Expr a b -> [a]
vars (a:+b) = vars a ++ vars b
vars (a:-b) = vars a ++ vars b
vars (a:*b) = vars a ++ vars b
vars (a:=>b) = vars a ++ vars b
vars (Invert e) = vars e; vars (Var v) = [v]; vars _ = []

eval :: (Eq a, Show a, Ring b, Monad m) => [(a, b)] -> Expr a b -> m b
eval m (a:+b) = return (+:) `ap` eval m a `ap` eval m b
eval m (a:-b) = return (-:) `ap` eval m a `ap` eval m b
eval m (a:*b) = return (*:) `ap` eval m a `ap` eval m b
eval m (a:=>b) = return (=:>) `ap` eval m a `ap` eval m b
eval m (Invert e) = return invert `ap` eval m e
eval m (Var v)
  | Just c <- lookup v m = return c
  | otherwise = fail $ "Unbound variable: " ++ show v
eval _ (Const c) = return c

namedProduct :: [(a, [b])] -> [[(a, b)]]
namedProduct = foldr (\(v, cs) l -> concatMap (\c -> map ((v, c):) l) cs) [[]]

evalAll :: (Eq a, Show a, Ring b) => [b] -> a -> Expr a b -> [[(a, b)]]
evalAll range name e =
    [ vs ++ [(name, either error id $ eval vs e)]
    | vs <- namedProduct $ zip (vars e) (repeat range)
    ]


A'=>(
:) . showsPrec 9 v
    showsPrec _ (Invert e) = ('!':) . showsPrec 9 e

    showsPrec n e@(a:=>b)
      | n > 5 = paren $ showsPrec 0 e
      | otherwise = showsPrec 7 a . ('=':) . ('>':) . showsPrec 5 b

    showsPrec n e@(a:*b)
      | n > 7 = paren $ showsPrec 0 e
      | otherwise = showsPrec 7 a . ('*':) . showsPrec 7 b

    showsPrec n e | n > 6 = paren $ showsPrec 0 e
    showsPrec _ (a:+b) = showsPrec 6 a . ('+':) . showsPrec 6 b
    showsPrec _ (a:-b) = showsPrec 6 a . ('-':) . showsPrec 6 b

vars :: (Eq a) => Expr a b -> [a]
vars (a:+b) = vars a ++ vars b
vars (a:-b) = vars a ++ vars b
vars (a:*b) = vars a ++ vars b
vars (a:=>b) = vars a ++ vars b
vars (Invert e) = vars e; vars (Var v) = [v]; vars _ = []

eval :: (Eq a, Show a, Ring b, Monad m) => [(a, b)] -> Expr a b -> m b
eval m (a:+b) = return (+:) `ap` eval m a `ap` eval m b
eval m (a:-b) = return (-:) `ap` eval m a `ap` eval m b
eval m (a:*b) = return (*:) `ap` eval m a `ap` eval m b
eval m (a:=>b) = return (=:>) `ap` eval m a `ap` eval m b
eval m (Invert e) = return invert `ap` eval m e
eval m (Var v)
  | Just c <- lookup v m = return c
  | otherwise = fail $ "Unbound variable: " ++ show v
eval _ (Const c) = return c

namedProduct :: [(a, [b])] -> [[(a, b)]]
namedProduct = foldr (\(v, cs) l -> concatMap (\c -> map ((v, c):) l) cs) [[]]

evalAll :: (Eq a, Show a, Ring b) => [b] -> a -> Expr a b -> [[(a, b)]]
evalAll range name e =
    [ vs ++ [(name, either error id $ eval vs e)]
    | vs <- namedProduct $ zip (vars e) (repeat range)
    ]

B'+ :) . showsPrec 9 v showsPrec _ (Invert e) = ('!':) . showsPrec 9 e showsPrec n e@(a:=>b) | n > 5 = paren $ showsPrec 0 e | otherwise = showsPrec 7 a . ('=':) . ('>':) . showsPrec 5 b showsPrec n e@(a:*b) | n > 7 = paren $ showsPrec 0 e | otherwise = showsPrec 7 a . ('*':) . showsPrec 7 b showsPrec n e | n > 6 = paren $ showsPrec 0 e showsPrec _ (a:+b) = showsPrec 6 a . ('+':) . showsPrec 6 b showsPrec _ (a:-b) = showsPrec 6 a . ('-':) . showsPrec 6 b vars :: (Eq a) => Expr a b -> [a] vars (a:+b) = vars a ++ vars b vars (a:-b) = vars a ++ vars b vars (a:*b) = vars a ++ vars b vars (a:=>b) = vars a ++ vars b vars (Invert e) = vars e; vars (Var v) = [v]; vars _ = [] eval :: (Eq a, Show a, Ring b, Monad m) => [(a, b)] -> Expr a b -> m b eval m (a:+b) = return (+:) `ap` eval m a `ap` eval m b eval m (a:-b) = return (-:) `ap` eval m a `ap` eval m b eval m (a:*b) = return (*:) `ap` eval m a `ap` eval m b eval m (a:=>b) = return (=:>) `ap` eval m a `ap` eval m b eval m (Invert e) = return invert `ap` eval m e eval m (Var v) | Just c <- lookup v m = return c | otherwise = fail $ "Unbound variable: " ++ show v eval _ (Const c) = return c namedProduct :: [(a, [b])] -> [[(a, b)]] namedProduct = foldr (\(v, cs) l -> concatMap (\c -> map ((v, c):) l) cs) [[]] evalAll :: (Eq a, Show a, Ring b) => [b] -> a -> Expr a b -> [[(a, b)]] evalAll range name e = [ vs ++ [(name, either error id $ eval vs e)] | vs <- namedProduct $ zip (vars e) (repeat range) ]

C')* :) . showsPrec 9 v showsPrec _ (Invert e) = ('!':) . showsPrec 9 e showsPrec n e@(a:=>b) | n > 5 = paren $ showsPrec 0 e | otherwise = showsPrec 7 a . ('=':) . ('>':) . showsPrec 5 b showsPrec n e@(a:*b) | n > 7 = paren $ showsPrec 0 e | otherwise = showsPrec 7 a . ('*':) . showsPrec 7 b showsPrec n e | n > 6 = paren $ showsPrec 0 e showsPrec _ (a:+b) = showsPrec 6 a . ('+':) . showsPrec 6 b showsPrec _ (a:-b) = showsPrec 6 a . ('-':) . showsPrec 6 b vars :: (Eq a) => Expr a b -> [a] vars (a:+b) = vars a ++ vars b vars (a:-b) = vars a ++ vars b vars (a:*b) = vars a ++ vars b vars (a:=>b) = vars a ++ vars b vars (Invert e) = vars e; vars (Var v) = [v]; vars _ = [] eval :: (Eq a, Show a, Ring b, Monad m) => [(a, b)] -> Expr a b -> m b eval m (a:+b) = return (+:) `ap` eval m a `ap` eval m b eval m (a:-b) = return (-:) `ap` eval m a `ap` eval m b eval m (a:*b) = return (*:) `ap` eval m a `ap` eval m b eval m (a:=>b) = return (=:>) `ap` eval m a `ap` eval m b eval m (Invert e) = return invert `ap` eval m e eval m (Var v) | Just c <- lookup v m = return c | otherwise = fail $ "Unbound variable: " ++ show v eval _ (Const c) = return c namedProduct :: [(a, [b])] -> [[(a, b)]] namedProduct = foldr (\(v, cs) l -> concatMap (\c -> map ((v, c):) l) cs) [[]] evalAll :: (Eq a, Show a, Ring b) => [b] -> a -> Expr a b -> [[(a, b)]] evalAll range name e = [ vs ++ [(name, either error id $ eval vs e)] | vs <- namedProduct $ zip (vars e) (repeat range) ]

D' *Expr> mapM_ print $ evalAll [True, False] 'E' expr [('A',True),('B',True),('C',True),('D',True),('E',True)] [('A',True),('B',True),('C',True),('D',False),('E',False)] [('A',True),('B',True),('C',False),('D',True),('E',True)] [('A',True),('B',True),('C',False),('D',False),('E',False)] [('A',True),('B',False),('C',True),('D',True),('E',True)] [('A',True),('B',False),('C',True),('D',False),('E',False)] [('A',True),('B',False),('C',False),('D',True),('E',False)] [('A',True),('B',False),('C',False),('D',False),('E',False)] [('A',False),('B',True),('C',True),('D',True),('E',True)] [('A',False),('B',True),('C',True),('D',False),('E',True)] [('A',False),('B',True),('C',False),('D',True),('E',True)] [('A',False),('B',True),('C',False),('D',False),('E',True)] [('A',False),('B',False),('C',True),('D',True),('E',True)] [('A',False),('B',False),('C',True),('D',False),('E',True)] [('A',False),('B',False),('C',False),('D',True),('E',True)] [('A',False),('B',False),('C',False),('D',False),('E',True)] :) . showsPrec 9 v showsPrec _ (Invert e) = ('!':) . showsPrec 9 e showsPrec n e@(a:=>b) | n > 5 = paren $ showsPrec 0 e | otherwise = showsPrec 7 a . ('=':) . ('>':) . showsPrec 5 b showsPrec n e@(a:*b) | n > 7 = paren $ showsPrec 0 e | otherwise = showsPrec 7 a . ('*':) . showsPrec 7 b showsPrec n e | n > 6 = paren $ showsPrec 0 e showsPrec _ (a:+b) = showsPrec 6 a . ('+':) . showsPrec 6 b showsPrec _ (a:-b) = showsPrec 6 a . ('-':) . showsPrec 6 b vars :: (Eq a) => Expr a b -> [a] vars (a:+b) = vars a ++ vars b vars (a:-b) = vars a ++ vars b vars (a:*b) = vars a ++ vars b vars (a:=>b) = vars a ++ vars b vars (Invert e) = vars e; vars (Var v) = [v]; vars _ = [] eval :: (Eq a, Show a, Ring b, Monad m) => [(a, b)] -> Expr a b -> m b eval m (a:+b) = return (+:) `ap` eval m a `ap` eval m b eval m (a:-b) = return (-:) `ap` eval m a `ap` eval m b eval m (a:*b) = return (*:) `ap` eval m a `ap` eval m b eval m (a:=>b) = return (=:>) `ap` eval m a `ap` eval m b eval m (Invert e) = return invert `ap` eval m e eval m (Var v) | Just c <- lookup v m = return c | otherwise = fail $ "Unbound variable: " ++ show v eval _ (Const c) = return c namedProduct :: [(a, [b])] -> [[(a, b)]] namedProduct = foldr (\(v, cs) l -> concatMap (\c -> map ((v, c):) l) cs) [[]] evalAll :: (Eq a, Show a, Ring b) => [b] -> a -> Expr a b -> [[(a, b)]] evalAll range name e = [ vs ++ [(name, either error id $ eval vs e)] | vs <- namedProduct $ zip (vars e) (repeat range) ]

Answer 2

基本的评估非常简单：

import Data.Maybe (fromJust)
import Data.List (nub)

type Variable = Char
data LogicExpr
   = Var Variable
   | Neg LogicExpr
   | Conj LogicExpr LogicExpr
   | Disj LogicExpr LogicExpr
   | Impl LogicExpr LogicExpr
   deriving (Eq, Ord)

-- evaluates an expression
evaluate :: LogicExpr -> [(Variable, Bool)] -> Bool
evaluate (Var v) bs      = fromJust (lookup v bs)
evaluate (Neg e) bs      = not (evaluate e bs)
evaluate (Conj e1 e2) bs = evaluate e1 bs && evaluate e2 bs
evaluate (Disj e1 e2) bs = evaluate e1 bs || evaluate e2 bs
evaluate (Impl e1 e2) bs = not (evaluate e1 bs) || evaluate e2 bs

要生成真值表，您首先必须找到表达式中的所有变量，然后为这些变量生成所有可能的赋值。 使用已经实现的 evaluate 函数可以轻松确定这些赋值的真值：

-- get variables in an expression
varsp :: LogicExpr -> [Variable]
varsp (Var v)      = [v]
varsp (Neg e)      = varsp e
varsp (Conj e1 e2) = varsp e1 ++ varsp e2
varsp (Disj e1 e2) = varsp e1 ++ varsp e2
varsp (Impl e1 e2) = varsp e1 ++ varsp e2

-- get variables in an expression without duplicates
vars :: LogicExpr -> [Variable]
vars = nub . varsp

-- possible boolean values
bools = [True, False]

-- all possible combinations of variable assignments
booltable :: [Variable] -> [[(Variable, Bool)]]
booltable [] = [[]]
booltable (a:as) = [(a,b) : r | b <- bools, r <- booltable as]

-- variable assignments and corresponding evaluation of an expression
truthtable :: LogicExpr -> [([(Variable, Bool)], Bool)]
truthtable e = [(bs, evaluate e bs) | bs <- booltable (vars e)]

如果您想探索标准库的黑暗角落，您还可以编写一个 Read用于轻松输入 LogicExpr 的实例：

-- read a right-associative infix operator
readInfix opprec constr repr prec r
   = readParen (prec > opprec)
     (\r -> [(constr e1 e2, u) |
             (e1,s) <- readsPrec (opprec+1) r,
             (op,t) <- lex s,
             op == repr,
             (e2,u) <- readsPrec (opprec) t]) r

instance Read LogicExpr where
   readsPrec prec r
      =  readInfix 1 Impl "->" prec r
      ++ readInfix 2 Disj "|" prec r
      ++ readInfix 3 Conj "&" prec r
      ++ readParen (prec > 4)
         (\r -> [(Neg e, t) |
                 ("!",s) <- lex r,
                 (e,t)   <- readsPrec 4 s]) r
      ++ readParen (prec > 5)
         (\r -> [(Var v, s) |
                 ([v], s) <- lex r]) r

并且可以漂亮地打印真值表：

showcell :: (Variable, Bool) -> String
showcell (v,b) = v : "=" ++ show b

showrow :: [(Variable, Bool)] -> Bool -> String
showrow []     b = show b
showrow [a]    b = showcell a ++ " => " ++ show b
showrow (a:as) b = showcell a ++ " && " ++ showrow as b

printrow :: ([(Variable, Bool)], Bool) -> IO ()
printrow = putStrLn . uncurry showrow

printtbl :: [([(Variable, Bool)], Bool)] -> IO ()
printtbl = mapM_ printrow

可以像这样生成所有真值表：

Prelude Main> printtbl $ truthtable $ read "(a -> b) & (b -> a)"
a=True && b=True => True
a=True && b=False => False
a=False && b=True => False
a=False && b=False => True

Prelude Main> printtbl $ truthtable $ read "(a | b) | (!a & !b)"
a=True && b=True => True
a=True && b=False => True
a=False && b=True => True
a=False && b=False => True