<p>Boolean formulas are binary trees where internal nodes are gates and literals are leaves. Subexpressions correspond to choices of subtrees in which you pick a node and everything below it. Hence if you have $n$ literals, there are $n-1$ internal nodes in the tree, and hence $n-1$ total subexpressions, though there may be duplicates. If you want to count "bare literals" as subexpressions, then this climbs to $2n-1$ subexpressions with possible duplicates.</p>

<p>Depending on how you want to handle duplicate subexpressions, one of two things happens, though the answer is the same. If you count duplicates separately, then $n-1$ or $2n-1$ is your final answer no matter the expression you start with. If you want to only count distinct subexpressions, but only care about worst-case guarantees, then you can just pick the $n$ literals to be distinct, and this will force all the subexpressions to be distinct. Hence you still get $n-1$ or $2n-1$ many subexpressions.</p>

CC BY-SA 3.0
2016-08-04T02:40:43.237Z
Actually now after some thinking, I'm not sure this answers my questions. I see how this is correct for boolean formulas, but my question was about general boolean circuits. In the general case, gates can have fan-out > 1, which would result in a DAG and not a binary tree.
Cryptonaut
CC BY-SA 3.0
2016-08-04T03:09:05.723Z
I interpreted your use of "expression" and your example to mean you meant formulas. In any case, the same logic applies, where subexpressions are just subcircuits which corresponds to vertices in the underlying graph. You can get unlimited many (as a function of the number of variables) distinct subcircuits by just taking a sufficiently large circuit in the first place. If you parameterize also by the size of the circuit, you just get the size (minus number of input gates) many subcircuits.
Andrew Morgan
CC BY-SA 3.0
2016-08-03T15:56:04.183Z
2016-08-03T15:56:04.183Z
Andrew Morgan
<p>I am wondering what the exact (including hidden constants) worst case number of subexpressions in an arbitrary boolean expression with $n$ literals (not necessarily distinct) is.</p>

<p>For simplicity it is probably ok to consider boolean expressions with just AND and OR gates, since extending it to, for example, XOR will not affect this number I assume.</p>

<p>To clarify what I mean, here is a small example:</p>

<p>$$(A \land B) \lor (C \land D)$$ has the subexpressions 
$(A \land B)$,
$(C \land D)$,
$(A \land B) \lor (C \land D)$.</p>

<p>I purposely ignored subexpressions, which are just composed of bare literals.</p>

<boolean-functions>
Number of subexpressions in a boolean expression
Cryptonaut
# Number of subexpressions in a boolean expression

(Asked by: username_0 on 2016-08-03)

I am wondering what the exact (including hidden constants) worst case number of subexpressions in an arbitrary boolean expression with $n$ literals (not necessarily distinct) is.

For simplicity it is probably ok to consider boolean expressions with just AND and OR gates, since extending it to, for example, XOR will not affect this number I assume.

To clarify what I mean, here is a small example:

$$(A \land B) \lor (C \land D)$$ has the subexpressions
$(A \land B)$,
$(C \land D)$,
$(A \land B) \lor (C \land D)$.

I purposely ignored subexpressions, which are just composed of bare literals.

**Tags:** boolean-functions


---

## 1 answers

### Answer by username_1 on 2016-08-03. Score: 1

Boolean formulas are binary trees where internal nodes are gates and literals are leaves. Subexpressions correspond to choices of subtrees in which you pick a node and everything below it. Hence if you have $n$ literals, there are $n-1$ internal nodes in the tree, and hence $n-1$ total subexpressions, though there may be duplicates. If you want to count "bare literals" as subexpressions, then this climbs to $2n-1$ subexpressions with possible duplicates.

Depending on how you want to handle duplicate subexpressions, one of two things happens, though the answer is the same. If you count duplicates separately, then $n-1$ or $2n-1$ is your final answer no matter the expression you start with. If you want to only count distinct subexpressions, but only care about worst-case guarantees, then you can just pick the $n$ literals to be distinct, and this will force all the subexpressions to be distinct. Hence you still get $n-1$ or $2n-1$ many subexpressions.

> **Comments:**
> **username_0**: Actually now after some thinking, I'm not sure this answers my questions. I see how this is correct for boolean formulas, but my question was about general boolean circuits. In the general case, gates can have fan-out > 1, which would result in a DAG and not a binary tree.  
> **username_1**: I interpreted your use of "expression" and your example to mean you meant formulas. In any case, the same logic applies, where subexpressions are just subcircuits which corresponds to vertices in the underlying graph. You can get unlimited many (as a function of the number of variables) distinct subcircuits by just taking a sufficiently large circuit in the first place. If you parameterize also by the size of the circuit, you just get the size (minus number of input gates) many subcircuits.  

---

