P47 - 通用逻辑门

2026-09-07 00:00    #Haskell   #99题   #逻辑  

P47 - 通用逻辑门

Universal logic gates

官方模块：Problems.P47　核心函数：evaluateCircuit, buildCircuit

← P46 二元逻辑真值表 | P48 n 元布尔函数真值表 →

题目描述

NAND 门是通用门——任意布尔函数都能用 NAND 门实现。给定电路描述（NAND 门列表），模拟电路输出；反之，给定一个布尔函数，构造出等价电路。

实现

方法一：递归计算电路

 1evaluateCircuit :: [(Int, Int)] -> Bool -> Bool -> Bool
 2evaluateCircuit gates x y = last outputs
 3  where
 4    inputs = [(-1, x), (-2, y)]
 5    outputs = build 1 inputs gates
 6    build _ env [] = map snd (drop 2 (reverse env))
 7    build i env ((a,b):gs) =
 8      let value = not (lookupValue a env && lookupValue b env)
 9      in build (i + 1) ((i,value):env) gs
10
11lookupValue :: Int -> [(Int, Bool)] -> Bool
12lookupValue n ((k,v):rest)
13  | n == k    = v
14  | otherwise = lookupValue n rest
15lookupValue _ [] = error "invalid gate reference"

(-1)、(-2) 分别代表两个输入。列表中第 ii 对 (a,b) 表示第 ii 个 NAND 门读取编号 aa、bb，最后一个门就是电路输出。

方法二：使用 fold 计算电路

1evaluateCircuit :: [(Int, Int)] -> Bool -> Bool -> Bool
2evaluateCircuit gates x y = lookupResult
3  where
4    inputs = [(-1, x), (-2, y)]
5    env = foldl step inputs (zip [1..] gates)
6    step env (i, (a, b)) = (i, not (lookupValue a env && lookupValue b env)) : env
7    lookupResult = case lookup (length gates) env of
8                     Just v -> v
9                     Nothing -> error "circuit evaluation failed"

用 foldl 替代显式递归，逐步更新环境变量。

两种求值写法采用相同的电路模型：方法一突出递归过程，方法二把每个门看成一次环境更新。

方法三：穷举构造 NAND 电路

 1buildCircuit :: (Bool -> Bool -> Bool) -> [(Int, Int)]
 2buildCircuit f = head
 3  [ gates
 4  | gateCount <- [1..]
 5  , gates <- circuits gateCount
 6  , equivalent gates f
 7  ]
 8  where
 9    equivalent gates target =
10      and [evaluateCircuit gates x y == target x y
11          | x <- [False, True], y <- [False, True]]
12
13circuits :: Int -> [[(Int, Int)]]
14circuits gateCount = go 1
15  where
16    go gate
17      | gate > gateCount = [[]]
18      | otherwise =
19          [ (left, right) : rest
20          | left <- inputs gate
21          , right <- inputs gate
22          , rest <- go (gate + 1)
23          ]
24
25    inputs gate = [-2, -1] ++ [1 .. gate - 1]

第 ii 个门只能引用两个外部输入或编号小于 ii 的门，因此枚举出的电路一定无环。对四组输入比较真值表，就能找到与目标函数等价的第一个 NAND 电路。穷举速度不快，但对二元布尔函数是完整且可运行的构造方法。

测试

1>>> let orCircuit = [(-1,-1),(-2,-2),(1,2)]
2>>> evaluateCircuit orCircuit True False
3True
4>>> and [evaluateCircuit (buildCircuit (&&)) x y == (x && y)
5...     | x <- [False, True], y <- [False, True]]
6True

参考