Semantics Vs Syntactics
Simplification is a semantic problem. We essentially need to find a more concise formula with the same truth table as a larger one.
We accomplish simplification through term rewriting which is a syntactic technique. Term rewriting manipulates the AST without understanding the truth table.
Note
The problem we are trying to solve is NP-complete using a polynomial technique.
We stop simplifying when we reach a fixed-point! This is when we apply our rewriting rules and nothing happens.
Note
The order of operands does not change the truth table