Logical transforms
Logical normal forms and Boolean simplification operate on symbolic relations. They do not coerce an unknown proposition into a host Boolean.
These transforms treat syntactically distinct atoms as independent Boolean variables; they do not reason about relations among atoms, which is constraint satisfaction. Every transform is logically equivalent to its input by construction. The connectives, constants, and the three-valued host query are described in Boolean algebra and logic.
Normal forms and Boolean simplification#
disjunctive_normal_form#
api::logic::Session method
pub fn disjunctive_normal_form(
&self,
input_expression: &Expression,
) -> Result<Expression, ApiError>Calling forms
api::expression_operations::Expression method: api::expression_operations::Expression::disjunctive_normal_form
pub fn disjunctive_normal_form(&self) -> Result<Expression, ApiError>Rewrite a propositional formula into a reduced disjunctive normal form (an OR of AND-terms over literals): derived connectives are eliminated, negations are pushed to the atoms, the formula is distributed, and contradictory, duplicate, and subsumed terms are dropped.
conjunctive_normal_form#
api::logic::Session method
pub fn conjunctive_normal_form(
&self,
input_expression: &Expression,
) -> Result<Expression, ApiError>Calling forms
api::expression_operations::Expression method: api::expression_operations::Expression::conjunctive_normal_form
pub fn conjunctive_normal_form(&self) -> Result<Expression, ApiError>The dual of disjunctive_normal_form: a reduced conjunctive normal form (an
AND of OR-clauses over literals).
minimize_logical#
api::logic::Session method
pub fn minimize_logical(
&self,
input_expression: &Expression,
) -> Result<Expression, ApiError>Calling forms
api::expression_operations::Expression method: api::expression_operations::Expression::minimize_logical
pub fn minimize_logical(&self) -> Result<Expression, ApiError>The smaller of the minimum sum-of-products and product-of-sums two-level forms. Within a practical atom bound this is the exact Quine–McCluskey minimum (prime implicants, essential extraction, and Petrick's method on the residual chart); above it, an Espresso-style heuristic returns a good — not provably minimal — cover.
simplify_logical#
api::logic::Session method
pub fn simplify_logical(
&self,
input_expression: &Expression,
) -> Result<Expression, ApiError>Calling forms
api::expression_operations::Expression method: api::expression_operations::Expression::simplify_logical
pub fn simplify_logical(&self) -> Result<Expression, ApiError>Return whichever of the original form, the disjunctive and conjunctive normal forms, and the two minimal two-level forms has the smallest weighted size.
Directed basis conversion#
simplify_logical, minimize_logical, and the two normal forms all answer a
cost question. The two transforms below answer a presentation question
instead: they convert between the derived connectives and the and/or/not basis
in a fixed direction, whatever that does to the size of the formula. They are
deliberately separate operations — simplify_logical is not changed to invoke
either of them, and neither performs hidden normal-form work.
eliminate_derived_logical_connectives#
api::logic::Session method
pub fn eliminate_derived_logical_connectives(
&self,
input_expression: &Expression,
) -> Result<Expression, ApiError>Calling forms
api::expression_operations::Expression method: api::expression_operations::Expression::eliminate_derived_logical_connectives
pub fn eliminate_derived_logical_connectives(
&self,
) -> Result<Expression, ApiError>Rewrite every implies, equivalent, and exclusive_or occurrence in a
propositional formula into the logical_and / logical_or / logical_not
basis. The result is propositionally equivalent to the input for every
assignment of its atoms, and carries no derived connective.
The defining identities are
implies(a, b) = logical_or(logical_not(a), b)
equivalent(a, b) = logical_or(logical_and(a, b),
logical_and(logical_not(a), logical_not(b)))
exclusive_or(a, b) = logical_or(logical_and(a, logical_not(b)),
logical_and(logical_not(a), b))Symi's equivalent and exclusive_or are n-ary, and the conversion
preserves those semantics exactly. equivalent(a, b, c, ...) is the all-equal
predicate — true exactly when every operand has the same truth value — so it
becomes "all operands true, or all operands false", which stays linear in the
operand count. exclusive_or(a, b, c, ...) is odd parity, and is expanded by
splitting the operand list into balanced halves, which keeps the edge-expanded
result quadratic rather than exponential in the operand count.
Because the direction is fixed, the result may be larger than the input.
That is the contract: implies(a, b) has three nodes and its and/or/not form
has four, and this operation returns the four-node form where
simplify_logical correctly keeps the three-node one.
Every non-connective leaf is an opaque atom. A relation such as x^2 < y is
carried across untouched, never rewritten arithmetically, and a connective call
whose arity the grammar does not admit is likewise preserved exactly rather
than being given an invented interpretation.
The operation is bounded by fixed, deterministic ceilings on input size, nesting depth, derived-connective count, and expanded output size — not by a wall clock, so native and WebAssembly admit exactly the same formulas. Refusal is atomic: a formula whose conversion would cross a ceiling comes back unchanged, and no partially converted tree is ever returned. A formula that is already in the basis also comes back unchanged.
let converted = symi::logic::eliminate_derived_logical_connectives(&mut context, &formula);introduce_derived_logical_connectives#
api::logic::Session method
pub fn introduce_derived_logical_connectives(
&self,
input_expression: &Expression,
) -> Result<Expression, ApiError>Calling forms
api::expression_operations::Expression method: api::expression_operations::Expression::introduce_derived_logical_connectives
pub fn introduce_derived_logical_connectives(
&self,
) -> Result<Expression, ApiError>The inverse presentation direction. Recognise the exact canonical definitions of implication, equivalence, and exclusive-or inside an and/or/not formula and replace each match with the corresponding derived connective, but only where the replacement strictly reduces the size of the formula.
The recognised families are
logical_or(logical_not(a), b) -> implies(a, b)
logical_or(logical_and(a, b),
logical_and(logical_not(a), logical_not(b))) -> equivalent(a, b)
logical_and(logical_or(logical_not(a), b),
logical_or(logical_not(b), a)) -> equivalent(a, b)
logical_or(logical_and(a, logical_not(b)),
logical_and(logical_not(a), b)) -> exclusive_or(a, b)Matching is insensitive to canonical commutative child order, and a flattened
n-ary parent is accepted whenever the matched clauses can be replaced without
disturbing the other children, so logical_or(A, B, c) compresses to
logical_or(equivalent(a, b), c) when A and B are the two equivalence
clauses. The disjunctive equivalence family also generalises to the n-ary
all-equal predicate: logical_or(logical_and(a, b, c), logical_and(not a, not b, not c)) compresses to equivalent(a, b, c).
This is a local structural compressor, not Boolean synthesis. It does not
solve a truth table for a globally minimal derived-connective formula, and it
leaves alone any formula that is merely equivalent to a definition without
matching it structurally — including anything that would first need absorption,
distribution, consensus, or reasoning about relations among atoms. Call
disjunctive_normal_form, conjunctive_normal_form, or minimize_logical
explicitly first when those transformations are wanted.
The proof of each replacement is the exact structural definition it matched: names, rendering order, numeric samples, and the assumption engine are never consulted. A second call changes nothing.
let compressed = symi::logic::introduce_derived_logical_connectives(&mut context, &formula);