# Number of logic formulas I can create with n uses of certain symbols

In the first lesson of a course in logic we defined as a logical formula the following:

• propositional variables $$p_0,p_1,...$$

• if $$\phi$$ is a formula then $$\lnot\phi$$ is a formula too

• if $$\phi$$ and $$\psi$$ are formulas then $$(\phi \lor \psi)$$ , $$(\phi \land \psi)$$ , $$(\phi \rightarrow \psi)$$ , $$(\phi \leftrightarrow \psi)$$ are formulas

and nothing else is a formula.

Now by using only one propositional variable $$p$$,

and $$0$$ times any of the symbols $$\lnot, \lor, \land, \rightarrow, \leftrightarrow$$ we can create only $$1$$ logical formula

and $$1$$ time any of the symbols $$\lnot, \lor, \land, \rightarrow, \leftrightarrow$$ we can create $$5$$ logical formulas: $$\lnot p$$ and $$(p*p)$$ ,where $$*$$ can stand for any of the symbols $$\lor, \land, \rightarrow, \leftrightarrow$$ (I write it this way to write less)

and $$2$$ times any of the symbols $$\lnot, \lor, \land, \rightarrow, \leftrightarrow$$ we can create the following logical formulas: $$\lnot\lnot p$$, $$(\lnot p * p)$$, $$(p*\lnot p)$$, $$\lnot (p*p)$$, $$(p*(p*p))$$, $$((p*p)*p)$$ which are $$1+4+4+4+4^2+4^2=45$$

My question is how many logical formulas can we create using only one variable and $$n$$ times any of the symbols $$\lnot, \lor, \land, \rightarrow, \leftrightarrow$$? I can calculate it(I think) for very small $$n$$ as above but for larger $$n$$ the thing gets more complicated.

Every formula with $$n$$ symbols is an incomplete binary tree. It has:

• exactly $$n$$ internal nodes (incl. the root),

• each internal node having $$1$$ or $$2$$ children,

• any internal node having $$2$$ children being decorated with any of $$4$$ symbols ($$\lor, \land, \rightarrow, \leftrightarrow$$),

• any internal node having $$1$$ child being decorated with $$\lnot$$,

• all the leaves decorated with the variable $$p$$.

The related problem where every internal node has $$2$$ children (i.e. complete binary tree), and there are no decorations, has a neat solution, but generalizing it to counting incomplete binary trees probably makes it very hairy, and adding decorations will make it even hairier.

Anyway here's an alternative: Let $$f(n)$$ be the number you seek.

• If the root has $$1$$ child (the formula has a leading $$\lnot$$), then there are $$f(n-1)$$ ways to complete the tree.

• If the root has $$2$$ children, i.e. $$2$$ subtrees, they can have $$a, b$$ internal nodes respectively as long as $$a+b = n-1$$, so there are $$f(a)$$ ways to make the left subtree and $$f(b)$$ ways to make the right subtree. And of course, need to multiply by $$4$$ for the $$4$$ binary op symbols.

Therefore:

$$f(n) = f(n-1) + 4 \times \sum_{a=0}^{n-1} f(a) f(n-1-a)$$

I am not sure how to turn this into something better (either closed-form, or at least some summation/product).

UPDATE: Just found this excellent CS.SE answer which suggests there is a way to count these using generating functions. Sadly, I'm out of my depth.