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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143

------------------------------------------------------------------------------
--- This module defines some operation to support the construction
--- of Boolean formulas.
---
--- @author Sven Hueser
--- @version September 2017
------------------------------------------------------------------------------

module Dimacs.Build where

import List (nub)

import Dimacs.Types

infixr 3 ./\
infixr 2 .\/

--- A Boolean variable with an index. Note that the index should be
--- a positive number.
va :: Int -> Boolean
va = Var

--- Boolean negation.
no :: Boolean -> Boolean
no = Not

--- Negated variable with an index. Note that the index should be
--- a positive number.
nv :: Int -> Boolean
nv = no . va

--- Conjunction.
(./\) :: Boolean -> Boolean -> Boolean
a ./\ b = case (a, b) of
  (Var _, Var _) -> And [a,b]
  (Var _, Not _) -> And [a,b]
  (Var _, And l) -> And $ a:l
  (Var _, Or  _) -> And [a,b]
  (_    , Var _) -> b ./\ a
  (Not _, Not _) -> And [a,b]
  (Not _, And l) -> And $ a:l
  (Not _, Or  _) -> And [a,b]
  (_    , Not _) -> b ./\ a
  (And p, And q) -> And $ p ++ q
  (And l, Or  _) -> And $ b:l
  (Or  _, Or  _) -> And [a,b]
  (Or  _, And _) -> b ./\ a

--- Disjunction.
(.\/) :: Boolean -> Boolean -> Boolean
a .\/ b = case (a, b) of
  (Var _, Var _) -> Or [a,b]
  (Var _, Not _) -> Or [a,b]
  (Var _, And _) -> Or [a,b]
  (Var _, Or  l) -> Or $ a:l
  (_    , Var _) -> b .\/ a
  (Not _, Not _) -> Or [a,b]
  (Not _, And _) -> Or [a,b]
  (Not _, Or  l) -> Or $ a:l
  (_    , Not _) -> b ./\ a
  (And _, And _) -> Or [a,b]
  (And _, Or  l) -> Or $ a:l
  (Or  p, Or  q) -> Or $ p ++ q
  (Or  _, And _) -> b .\/ a

--- Exclusive or.
xor :: Boolean -> Boolean -> Boolean
a `xor` b = (no a ./\ b) .\/ (a ./\ no b)

--------------------------------------------------------------------------------

nnf :: Boolean -> Boolean
nnf (Var x) = Var x
nnf n@(Not f) = case f of
  (Var _)  -> n
  (Not g)  -> nnf g
  (And fs) -> Or  (map (nnf . Not) fs)
  (Or  fs) -> And (map (nnf . Not) fs)
nnf (And fs) = And (map nnf fs)
nnf (Or  fs) = Or  (map nnf fs)

cnf :: Boolean -> Boolean
cnf (Var x) = Or [Var x]
cnf (Not v) = Or [Not v]
cnf (And fs) = And (map cnf fs)
cnf (Or  []) = Or  []
cnf (Or  [f]) = cnf f
cnf (Or  (f1:f2:fs)) = dist (cnf f1) (cnf (Or (f2:fs)))

dist :: Boolean -> Boolean -> Boolean
dist xs ys = case (xs, ys) of
  (And [], _)       -> And []
  (_, And [])       -> And []
  (And [f1], f2)    -> dist f1 f2
  (f1, And [f2])    -> dist f1 f2
  (And (f1:fs), f2) -> And [dist f1 f2, dist (And fs) f2]
  (f1, And (f2:fs)) -> And [dist f1 f2, dist f1 (And fs)]
  (f1, f2)          -> Or  [f1,f2]


flatten :: Boolean -> Boolean
flatten f = case f of
  (And fs) -> And (flattenAnd fs)
  (Or  fs) -> Or  (flattenOr  fs)
  _        -> f

flattenAnd :: [Boolean] -> [Boolean]
flattenAnd cs = case cs of
  []            -> []
  ((And fs):gs) -> flattenAnd (fs ++ gs)
  (f:fs)        -> flatten f : flattenAnd fs

flattenOr :: [Boolean] -> [Boolean]
flattenOr ds = case ds of
  []            -> []
  ((Or  fs):gs) -> flattenOr (fs ++ gs)
  (f:fs)        -> f: flattenOr fs

nubB :: Boolean -> Boolean
nubB bs = case bs of
  (And fs) -> And (map nubB fs)
  (Or  fs) -> Or  (nub fs)
  _        -> bs

toCNF :: Boolean -> Boolean
toCNF = filterTauts . nubB . flatten . cnf . nnf

filterTauts :: Boolean -> Boolean
filterTauts b = case b of
  (And ls)  -> And $ filter (not . isTaut) ls
  _         -> b

isTaut :: Boolean -> Bool
isTaut b = case b of
    (Or ls) -> isTaut' ls
    _       -> False
  where
    isTaut' []     = False
    isTaut' (x:xs) = containsInverted x xs || isTaut' xs
    containsInverted x xs = case x of
      (Var i)       -> nv i `elem` xs
      (Not (Var i)) -> va i `elem` xs
      _             -> False