Bounded Boolean and bit-vector reasoning with small-circuit planning in MoonBit
moon add Lyhdsba/fusekitemoon -C examples/status-indicator run .let spec = TruthSpec::new(3, [1, 3, 5, 7], [])
let solution = minimize_sop(spec.unwrap())
println(solution.patterns()) // ["--1"]let spec = TruthSpec::new(2, [0, 2, 3], []).unwrap()
let solution = minimize_pos(spec)
println(solution.patterns()) // ["01"]: (A OR NOT B)
solution.evaluate(1) // Some(false)
solution.evaluate(3) // Some(true)
solution.evaluate(4) // None: out of rangemoon run cmd/main| Example task | Input | Steps | Expected result |
|---|---|---|---|
| Compare two forms of a sensor interlock. | door_closed, sensor_clear; 2 inputs, on-set [3], no don't-cares; active-high enable. | Run the demo; read the interlock block; decode SOP 1 as a positive literal and POS 0 as a positive literal; check all four specified rows and BDD/SAT results. | SOP 11 is door_closed AND sensor_clear (1 term, 2 literals). POS -0, 0- is (sensor_clear) AND (door_closed) (2 clauses, 2 literals). Both output 0,0,0,1; each direct form uses one AND2 gate / one HC08 package. |
| Compare an active-high BCD segment with don't-cares. | D8,D4,D2,D1; 4 inputs, on-set [0,2,3,5,6,7,8,9], don't-cares [10,11,12,13,14,15]; common-cathode segment a, valid BCD source. | Run the demo; read the BCD block; compare cost counts and the ten specified rows; inspect the separately labeled unspecified rows. | SOP --1-, -0-0, -1-1, 1--- has 4 terms / 6 literals. POS -100, 0001 has 2 clauses / 7 literals: (!D4 OR D2 OR D1) AND (D8 OR D4 OR D2 OR !D1). Digits 1 and 4 output 0, the other valid digits 1; BDD/SAT confirm cared-row equivalence. SOP estimates 1 HC04, 1 HC08, 1 HC32; POS estimates 1 HC04, 1 HC08, 2 HC32 packages. |
| Study a two-of-three alarm predicate. | sensor_A,sensor_B,sensor_C; 3 inputs, on-set [3,5,6,7], no don't-cares; equal, active-high sensor inputs. | Run the demo; read the alarm block; compare the pairwise products and sums; check all eight specified rows and both package estimates. | SOP -11, 1-1, 11- is BC OR AC OR AB; POS -00, 0-0, 00- is (B OR C) AND (A OR C) AND (A OR B). Both have 3 terms/clauses and 6 literals, assert exactly when at least two inputs are 1, and pass BDD/SAT checks. SOP uses 3 AND2 and 2 OR2 gates / one HC08 and one HC32 package; POS uses 2 AND2 and 3 OR2 gates / one HC08 and one HC32 package. |
| Module | Role and bounds | Source |
|---|---|---|
| Reduced ordered BDD (ROBDD) | Canonical Boolean operations and equivalence within one fixed-order manager; 1–32 variables. Node IDs belong to their manager; diagram size can grow exponentially. | BDD implementation |
| SAT | Conjunctive normal form (CNF) validation, DIMACS parsing, shared Tseitin encoding, and bounded Davis–Putnam–Logemann–Loveland (DPLL) search with two-watched-literal propagation and chronological backtracking. CNF accepts up to 4,096 variables; budget exhaustion returns Unknown. No conflict learning. | SAT package |
| Bounded bit-vectors | Quantifier-free fixed-size bit-vector (QF_BV) constraints, 1–8 bits, lowered to the SAT backend. Supports bitwise operations, wrapping add/subtract, low-product multiplication, equality, and signed/unsigned comparison. | Bit-vector front end |
let manager = BddManager::new(2).unwrap()
let a = manager.variable(0).unwrap()
let b = manager.variable(1).unwrap()
let both = manager.apply(BddOp::And, a, b).unwrap()
manager.evaluate(both, [true, false]) // Some(false)let expr = @sat.BoolExpr::Xor(
@sat.BoolExpr::Variable(1),
@sat.BoolExpr::Variable(2),
)
let formula = @sat.CnfFormula::from_expression(2, expr).unwrap()
let report = formula.solve(@sat.SolverConfig::new(10_000).unwrap())moon fmt --check
moon check --deny-warn
moon test
moon build
moon run cmd/main
moon -C examples/status-indicator fmt --check
moon -C examples/status-indicator check --deny-warn
moon -C examples/status-indicator run .
moon doc
moon package --listpython -m pip install -r tests/requirements.txt
python -B -m unittest discover -s tests -p 'test_*.py' -v
python -B tests/qfbv_z3_oracle.pymoon publishpub struct BddManager {
// private fields
}pub struct Cube {
width : Int
value : Int
wildcard : Int
}pub struct GateCost {
inverters : Int
and2_gates : Int
or2_gates : Int
}pub struct PosClause {
// private fields
}pub struct PosSolution {
clause_count : Int
literal_count : Int
explored_states : Int
// private fields
}pub struct TruthSpec {
// private fields
}fn verify_pos_with_sat(spec : TruthSpec, solution : PosSolution, config : SolverConfig) -> SatEquivalencefn verify_sop_with_sat(spec : TruthSpec, solution : CoverSolution, config : SolverConfig) -> SatEquivalenceInstall
Download zipBounded Boolean and bit-vector reasoning with small-circuit planning in MoonBit