1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.