If you could have ever been accountable for managing complex business logic, you understand how nested if-else statements is usually a jungle: painful to navigate and simple to wander off. With regards to mission-critical tasks, for instance formal verification or satisfiability, many developers reach for classy tools similar to automated theorem provers or SMT solvers. Although powerful, these approaches could be overkill and a headache to implement. What if all you would like is an easy, transparent rules engine?
The important thing idea for constructing such a light-weight engine relies on an idea that we were taught to be insightful but impractical: . Exponential growth, their fatal flaw, makes them unfit for real-world problems. So we were told.
An easy commentary changes all the things: In just about all practical cases, the “impossibly large” truth table is definitely not dense with information; it’s in reality a sparse matrix in disguise.
This reframing makes the reality tables each conceptually clear and computationally tractable.
This text shows you the best way to turn this insight into a light-weight and powerful rules engine. We’ll guide you thru all of the needed steps to construct the engine from scratch. Alternatively, you should utilize our open-source library vector-logic to begin constructing applications on day one. This tutorial gives you all of the needed details to know what’s under the hood.
While all of the theoretical background and mathematical details could be present in our research paper on the [1], here, we deal with the hands-on application. Let’s roll up our sleeves and begin constructing!
A Quick Refresher on Logic 101
Truth Tables
We’ll start with a fast refresher: logical formulas are expressions which might be built from Boolean variables and logical connectors like AND, OR, and NOT. In a real-world context, Boolean variables could be considered representing events (e.g. “the coffee cup is full”, which is if the cup is definitely full and whether it is empty). For instance, the formula (f = (x_1 vee x_2)) is true if (x_1) is true, (x_2) is true, or each are. We will use this framework to construct a comprehensive brute-force map of each possible reality — the reality table.
Using 1 for “true” and 0 for “false”, the table for (x_1 vee x_2) looks like this:
[ begin{Bmatrix}
x_1 & x_2 & x_1 vee x_2 hline
0 & 0 & 0
0 & 1 & 1
1 & 0 & 1
1 & 1 & 1
end{Bmatrix} ]
Every little thing we’d like to perform logical inference is encoded in the reality table. Let’s see it in motion.
Logical Inference
Consider a classic example of the . Suppose we all know that… By the best way, all the things we are saying “we all know” is named a premise. Suppose now we have two premises:
- If (x_1) is true, then (x_2) have to be true ((x_1 to x_2))
- If (x_2) is true, then (x_3) have to be true ((x_2 to x_3))
It’s easy to guess the conclusion: “If (x_1) is true, then (x_3) have to be true” ((x_1 to x_3)). Nonetheless, we may give a proper proof using truth tables. Let’s first label our formulas:
[begin{align*}
& f_1 = (x_1 to x_2) && text{premise 1}
& f_2 = (x_2 to x_3) && text{premise 2}
& f_3 = (x_1 to x_3) && text{conclusion}
end{align*}]
Step one is to construct a truth table covering all combos of the three base variables (x_1), (x_2), and (x_3):
[begin{align*}
begin{Bmatrix}
x_1 & x_2 & x_3 & f_1 & f_2 & f_3 hline
0 & 0 & 0 & 1 & 1 & 1
0 & 0 & 1 & 1 & 1 & 1
0 & 1 & 0 & 1 & 0 & 1
0 & 1 & 1 & 1 & 1 & 1
1 & 0 & 0 & 0 & 1 & 0
1 & 0 & 1 & 0 & 1 & 1
1 & 1 & 0 & 1 & 0 & 0
1 & 1 & 1 & 1 & 1 & 1
end{Bmatrix}
end{align*}]
This table accommodates eight rows, one for every project of truth values to the bottom variables. The variables (f_1), (f_2) and (f_3) are derived, as we compute their values directly from the (x)-variables.
Notice how large the table is, even for this easy case!
The subsequent step is to let our premises, represented by (f_1) and (f_2), act as a filter on reality. We’re on condition that they’re each true. Subsequently, any row where either (f_1) or (f_2) is fake represents an not possible scenario which needs to be discarded.
After applying this filter, we’re left with a much smaller table:
[begin{align*}
begin{Bmatrix}
x_1 & x_2 & x_3 & f_1 & f_2 & f_3 hline
0 & 0 & 0 & 1 & 1 & 1
0 & 0 & 1 & 1 & 1 & 1
0 & 1 & 1 & 1 & 1 & 1
1 & 1 & 1 & 1 & 1 & 1
end{Bmatrix}
end{align*}]
And here we’re: In every remaining valid scenario, (f_3) is true. We have now proven that (f_3) logically follows from (or is entailed by) (f_1) and (f_2).
A chic and intuitive method indeed. So, why don’t we use it for complex systems? The reply lies in easy maths: With only three variables, we had (2^3=8) rows. With 20 variables, we might have over 1,000,000. Take 200, and the variety of rows would exceed the variety of atoms within the solar system. But wait, our article doesn’t end here. We will fix that.
The Sparse Representation
The important thing idea for addressing exponentially growing truth tables lies in a enabling lossless compression.
Beyond just compressing the reality tables, we are going to need an efficient option to perform logical inference. We are going to achieve this by introducing “state vectors” — which represent sets of states (truth table rows) — and adopting set theory operations like union and intersection to control them.
The Compressed Truth Table
First, we return to formula (f = (x_1 to x_2)). Let’s discover the rows that make the formula true. We use the symbol (sim) to represent the correspondence between the formula and a table of its “valid” truth assignments. In our example of (f) for implication, we write:
[begin{align*}
fquadsimquad
begin{Bmatrix}
x_1 & x_2 hline
0 & 0
0 & 1
1 & 1
end{Bmatrix}
end{align*}]
Note that we dropped the row ((1, 0)) because it invalidates (f). What would occur to this table, if we now prolonged it to involve a 3rd variable (x_3), that (f) doesn’t rely on? The classic approach would double the scale of the reality table to account for (x_3) being 0 or 1, even though it doesn’t add any latest details about (f):
[begin{align*}
fquadsimquad
begin{Bmatrix}
x_1 & x_2 & x_3 hline
0 & 0 & 0
0 & 0 & 1
0 & 1 & 0
0 & 1 & 1
1 & 1 & 0
1 & 1 & 1
end{Bmatrix}
end{align*}]
What a waste! Uninformative columns might be compressed, and, for this purpose, we introduce a touch (–) as a “wildcard” symbol. You may consider it as a logical Schrödinger’s cat: the variable exists in a superposition of each 0 and 1 until a constraint or a measurement (within the context of learning, we call it “evidence”) forces it right into a definite state, removing certainly one of the chances.
Now, we will represent (f) across a universe of (n) variables with none bloat:
[begin{align*}
fquadsimquad
begin{Bmatrix}
x_1 & x_2 & x_3 & ldots & x_n hline
0 & 0 & – & ldots & –
0 & 1 & – &ldots & –
1 & 1 & – &ldots & –
end{Bmatrix}
end{align*}]
We will generalise this by postulating that any row containing dashes is akin to the set of multiple rows obtained by all possible substitutions of 0s and 1s within the places of dashes. For instance (try it with pencil and paper!):
[begin{align*}
begin{Bmatrix}
x_1 & x_2 & x_3 hline
– & 0 & –
– & 1 & 1
end{Bmatrix} =
begin{Bmatrix}
x_1 & x_2 & x_3 hline
0 & 0 & 0
0 & 0 & 1
1 & 0 & 0
1 & 0 & 1
0 & 1 & 1
1 & 1 & 1
end{Bmatrix}
end{align*}]
That is the essence of sparse representation. Let’s introduce a number of definitions for basic operations: We call replacing dashes with 0s and 1s expansion. The reverse process, through which we spot patterns to introduce dashes, is named reduction. The best type of reduction, replacing two rows with one, is named atomic reduction.
An Algebra of States
Now, let’s give these ideas some structure.
- A state is a single, complete project of truth values to all variables — one row in a totally expanded truth table (e.g. ((0, 1, 1))).
- A state vector is a set of states (consider it as a subset of the reality table). A logical formula can now be regarded as a state vector containing all of the states that make it true. Special cases are an empty state vector (0) and a vector containing all (2^n) possible states, which we call a trivial vector and denote as (mathbf{t}). (As we’ll see, this corresponds to a t-object with all wildcards.)
- A row in a state vector’s compact representation (e.g. ((0, -, 1) )) is named a t-object. It’s our fundamental constructing block — a pattern that may represent one or many states.
Conceptually, shifting the main focus from tables to sets is an important step. Remember how we carried out inference using the reality table method: we used premises (f_1) and (f_2) as a filter, keeping only the rows where each premises were true. This operation, by way of the language of set theory, is an intersection.
Each premise corresponds to a state vector (the set of states that satisfy the premise). The state vector for our combined knowledge is the intersection of those premise vectors. This operation is on the core of the brand new model.
For friendlier notation, we introduce some “syntax sugar” by mapping set operations to easy arithmetic operations:
- Set Union ((cup)) (rightarrow) Addition ((+))
- Set Intersection ((cap)) (rightarrow) Multiplication ((*))
The properties of those operations (associativity, commutativity, and distributivity) allow us to make use of high-school algebra notation for complex expressions with set operations:
[
begin{align*}
& (Acup B) cap (Ccup D) = (Acap C) cup (Acap D) cup (Bcap C) cup (Bcap D)
& rightarrow
& (A+B)cdot(C+D) = A,C + A,D + B,C + B,D
end{align*}
]
Let’s take a break and see where we’re. We’ve laid a powerful foundation for the brand new framework. Truth tables at the moment are represented sparsely, and we reinterpret them as sets (state vectors). We also established that logical inference could be achieved by multiplying the state vectors.
We’re nearly there. But before we will apply this theory to develop an efficient inference algorithm, we’d like yet one more ingredient. Let’s take a more in-depth have a look at operations on t-objects.
The Engine Room: Operations on T-Objects
We at the moment are able to go to the following phase — creating an algebraic engine to control state vectors efficiently. The basic constructing block of our construction is the t-object — our compact, wildcard-powered representation of a single row in a state vector.
Note that to explain a row, we only must know the positions of 0s and 1s. We denote a t-object as (mathbf{t}^alpha_beta), where (alpha) is the set of indices where the variable is 1, and (beta) is the set of indices where it’s 0. As an example:
[
begin{Bmatrix}
x_1 & x_2 & x_3 & x_4 hline
1 & 0 & – & 1
end{Bmatrix} = mathbf{t}_2^{14}
]
A t-object consisting of all of the dashes (mathbf{t} = { -;; – ldots -}) represents the previously mentioned trivial state vector that accommodates all possible states.
From Formulas to T-Objects
A state vector is the union of its rows or, in our latest notation, the sum of its t-objects. We call this row decomposition. For instance, the formula (f=(x_1to x_2)) could be represented as:
[begin{align*}
fquadsimquad
begin{Bmatrix}
x_1 & x_2 & ldots & x_n hline
0 & 0 & ldots & –
0 & 1 & ldots & –
1 & 1 & ldots & –
end{Bmatrix} = mathbf{t}_{12} + mathbf{t}_1^2 + mathbf{t}^{12}
end{align*}]
Notice that this decomposition doesn’t change if we add more variables ((x_3, x_4, dots)) to the system, which shows that our approach is inherently scalable.
The Rule of Contradiction
The identical index cannot appear in each the upper and lower positions of a t-object. If this happens, the t-object is null (an empty set). As an example (we highlighted the conflicting index):
[
mathbf{t}^{1{color{red}3}}_{2{color{red}3}} = 0
]
That is the algebraic equivalent of a logical contradiction. A variable ((x_3) on this case) can’t be each true (superscript) and false (subscript) at the identical time. Any such t-object represents an not possible state and vanishes.
Simplifying Expressions: Atomic Reduction
Atomic reduction could be expressed cleanly using the newly introduced t-object notation. Two rows could be reduced in the event that they are an identical, apart from one variable, which is 0 in a single and 1 in the opposite. As an example:
[
begin{align*}
begin{Bmatrix}
x_1 & x_2 & x_3 & x_4 & x_5 hline
1 & – & 0 & 0 & –
1 & – & 0 & 1 & –
end{Bmatrix} =
begin{Bmatrix}
x_1 & x_2 & x_3 & x_4 & x_5 hline
1 & – & 0 & – & –
end{Bmatrix}
end{align*}
]
In algebraic terms, that is:
[
mathbf{t}^1_{34} + mathbf{t}^{14}_3 = mathbf{t}^1_3
]
The rule for this operation follows directly from the definition of the t-objects: If two t-objects have index sets which might be an identical, apart from one index that may be a superscript in a single and a subscript in the opposite, they mix. The clashing index (4 in this instance) is annihilated, and the 2 t-objects merge.
By applying atomic reduction, we will simplify the decomposition of the formula (f = (x_1 to x_2)). Noticing that (mathbf{t}_{12} + mathbf{t}_1^2 = mathbf{t}_1), we get:
[
f quad simquad mathbf{t}_{12} + mathbf{t}_1^2 + mathbf{t}^{12} = mathbf{t}_1 + mathbf{t}^{12}
]
The Core Operation: Multiplication
Finally, allow us to discuss an important operation for our rules engine: intersection (by way of set theory), represented as multiplication (by way of algebra). How will we find the states common to the 2 t-objects?
The rule governing this operation is simple: to multiply two t-objects, one forms the union of their superscripts, in addition to the union of their subscripts (we leave the proof as an easy exercise for a curious reader):
[
mathbf{t}^{alpha_1}_{beta_1},mathbf{t}^{alpha_2}_{beta_2} = mathbf{t}^{alpha_1 cup alpha_2}_{beta_1cupbeta_2}
]
The rule of contradiction still applies. If the resulting superscript and subscript sets overlap, the product vanishes:
[
mathbf{t}^{alpha_1 cup alpha_2}_{beta_1cupbeta_2} = 0 quad iff quad
(alpha_1 cup alpha_2) cap (beta_1cupbeta_2) not = emptyset
]
For instance:
[
begin{align*}
& mathbf{t}^{12}_{34},mathbf{t}^5_6 = mathbf{t}^{125}_{346} && text{Simple combination}
& mathbf{t}^{12}_{34} ,mathbf{t}^{4} = mathbf{t}^{12{color{red}4}}_{3{color{red}4}} = 0 && text{Vanishes, because 4 is in both sets}
end{align*}
]
A vanishing product implies that the 2 t-objects haven’t any states in common; subsequently, their intersection is empty.
These rules complete our construction. We defined a sparse representation of logic and algebra for manipulating the objects. These are all of the theoretical tools that we’d like. We’re able to assemble them right into a practical algorithm.
Putting It All Together: Inference With State Algebra
The engine is prepared, it’s time to show it on! In its core, the concept is straightforward: to seek out the set of valid states, we’d like to multiply all state vectors corresponding to premises and evidences.
If now we have two premises, represented by the state vectors ((mathbf{t}_{(1)} + mathbf{t}_{(2)})) and ((mathbf{t}_{(3)} + mathbf{t}_{(4)})), the set of states through which each are true is their product:
[
left(mathbf{t}_{(1)} + mathbf{t}_{(2)}right),left(mathbf{t}_{(3)} + mathbf{t}_{(4)}right) =
mathbf{t}_{(1)},mathbf{t}_{(3)} +
mathbf{t}_{(1)},mathbf{t}_{(4)} +
mathbf{t}_{(2)},mathbf{t}_{(3)} +
mathbf{t}_{(2)},mathbf{t}_{(4)}
]
This instance could be easily generalised to any arbitrary variety of premises and t-objects.
The inference algorithm is simple:
- Decompose: Convert each premise into its state vector representation (a sum of t-objects).
- Simplify: Use atomic reduction on each state vector to make it as compact as possible.
- Multiply: Multiply the state vectors of all premises together. The result’s a single state vector representing all states consistent together with your premises.
- Reduce Again: The ultimate product could have reducible terms, so simplify it one last time.
Example: Proving Transitivity, The Algebraic Way
Let’s revisit our classic example of implication transitivity: if (f_1 = (x_1to x_2)) and (f_2 = (x_2to x_3)) are true, prove that (f_3=(x_1to x_3)) must even be true. First, we write the simplified state vectors for our premises as follows:
[
begin{align*}
& f_1 quad sim quad mathbf{t}_1 + mathbf{t}^{12}
& f_2 quad sim quad mathbf{t}_2 + mathbf{t}^{23}
end{align*}
]
To prove the conclusion, we will use a proof by contradiction. Let’s ask: does a scenario exist where our premises are true, but our conclusion (f_3) is fake?
The states that invalidate (f_3 = (x_1 to x_3)) are those through which (x_1) is true (1) and (x_3) is fake (0). This corresponds to a single t-object: (mathbf{t}^1_3).
Now, let’s see if this “invalidating” state vector can coexist with our premises by multiplying all the things together:
[
begin{gather*}
(text{Premise 1}) times (text{Premise 2}) times (text{Invalidating State Vector})
(mathbf{t}_1 + mathbf{t}^{12}),(mathbf{t}_2 + mathbf{t}^{23}), mathbf{t}^1_3
end{gather*}
]
First, we multiply by the invalidating t-object, because it’s essentially the most restrictive term:
[
(mathbf{t}_1 mathbf{t}^1_3 + mathbf{t}^{12} mathbf{t}^1_3),(mathbf{t}_2 + mathbf{t}^{23}) = (mathbf{t}^{{color{red}1}}_{{color{red}1}3} + mathbf{t}^{12}_3),(mathbf{t}_2 + mathbf{t}^{23})
]
The primary term, (mathbf{t}^{{color{red}1}}_{{color{red}1}3}), vanishes because of contradiction. So we’re left with:
[
mathbf{t}^{12}_3,(mathbf{t}_2 + mathbf{t}^{23}) =
mathbf{t}^{12}_3 mathbf{t}_2 + mathbf{t}^{12}_3 mathbf{t}^{23} =
mathbf{t}^{1{color{red}2}}_{{color{red}2}3} + mathbf{t}^{12{color{red}3}}_{{color{red}3}} =
0 + 0 = 0
]
The intersection is empty. This proves that there isn’t a possible state where (f_1) and (f_2) are true, but (f_3) is fake. Subsequently, (f_3) must follow from the premises.
Proof by contradiction shouldn’t be the one option to solve this problem. One can find a more elaborate evaluation within the “State Algebra” paper [1].
From Logic Puzzles to Fraud Detection
This isn’t nearly logic puzzles. A lot of our world is governed by rules and logic! For instance, consider a rule-based fraud-detection system.
Your knowledge base is a algorithm like
IF card_location is overseas AND transaction_amount > $1000, THEN risk is highThe whole knowledge base could be compiled right into a single large state vector.
Now, a transaction occurs. That is your evidence:
card_location = overseas, transaction_amount > $1000, user_logged_in = falseThis evidence is a single t-object, assigning 1s to observed facts which might be true and 0s to facts which might be false, leaving all unobserved facts as wildcards.
To make a choice, you just multiply:
[
text{Knowledge Base Vector}times text{Evidence T-object}
]
The resulting state vector immediately tells you the worth of the goal variable (similar to risk) given the evidence. No messy chain of “if-then-else” statements was needed.
Scaling Up: Optimisation Strategies
As with mechanical engines, there are a lot of ways to make our engine more efficient.
Let’s face the fact: logical inference problems are computationally hard, meaning that the worst-case runtime is non-polynomial. Put simply, irrespective of how compact the representation is, or how smart the algorithm is, within the worst-case scenario, the runtime shall be extremely long. So long that most definitely, you should have to stop the computation before the result’s calculated.
The rationale SAT solvers are doing an awesome job shouldn’t be because they alter reality. It’s because nearly all of real-life problems are usually not worst-case scenarios. The runtime on an “average” problem shall be extremely sensitive to the heuristic optimisations that your algorithm uses for computation.
Thus, optimisation heuristics might be some of the essential components of the engine to realize meaningful scalability. Here, we just hint at possible places where optimisation could be considered.
Note that when multiplying many state vectors, the variety of intermediate t-objects can grow significantly before eventually shrinking, but we will do the next to maintain the engine running easily:
- Constant Reduction: After each multiplication, run the reduction algorithm on the resulting state vector. This keeps intermediate results compact.
- Heuristic Ordering: The order of multiplication matters. It’s often higher to multiply smaller or more restrictive state vectors first, as this may cause more t-objects to fade early, pruning the calculation.
Conclusion
We have now taken you on a journey to find how propositional logic could be forged into the formalism of state vectors, such that we will use basic algebra to perform logical inference. The elegance of this approach lies in its simplicity and efficiency.
At no point does inference require the calculation of giant truth tables. The knowledge base is represented as a set of sparse matrices (state vector), and the logical inference is reduced to a set of algebraic manipulations that could be implemented in a number of straightforward steps.
While this algorithm doesn’t aim to compete with cutting-edge SAT solvers and formal verification algorithms, it offers a phenomenal, intuitive way of representing logic in a highly compact form. It’s a strong tool for constructing lightweight rules engines, and an awesome mental model for fascinated with logical inference.
Try It Yourself
One of the best option to understand this method is to make use of it. We’ve packaged your entire algorithm into an open-source Python library called vector-logic. It could possibly be installed directly from PyPI:
pip install vector-logicThe total source code, together with more examples and documentation, is accessible on
We encourage you to explore the repository, try it on your individual logic problems, and contribute.
For those who’re keen on delving deeper into mathematical theory, try the unique paper [1]. The paper covers some topics which we couldn’t include on this practical guide, similar to canonical reduction, orthogonalisation and lots of others. It also establishes an abstract algebraic representation of propositional logic based on t-objects formalism.
We welcome any comments or questions.
Who We Are
References
[1] Dmitry Lesnik and Tobias Schäfer, “State Algebra for Propositional Logic,” arXiv preprint arXiv:2509.10326, 2025. Available at: https://arxiv.org/abs/2509.10326
