# Count the number of part expressions of an arithmetic expression

The problem:

Define the recursive function numexprs that returns the number of part expressions when given an arithmetic expression. Note that even bool is a part expression.(Individual parentheses are not counted as part expressions.) Evaluate your function on the expression below, and verify that it returns the expected value of 8.

I don't understand how I should define the recursive function. The question states that I should count the number of part expression in a given arithmetic expression, but the example I'm supposed to verify isn't even an arithmetic expression? I feel very confused.

I was thinking of using something similar to this when defining the function:

• Count subformulas: every atom ($\text {bool}$) in the example is a subf; every part enclosed between a pair of parentheses is a subf; the formula itself is a subf. Nov 28 '21 at 12:18
• Something along the line of the inductive def: (i) if $\varphi$ is atomic then $\text {num}(\varphi)=1$; (ii) if $\varphi := (\lnot \psi)$ then $\text {num}(\varphi)=\text {num}(\psi)+1$, and so on. Nov 28 '21 at 12:20

Let's provide indices to the different bool's so we can see better what is going on. OK, so you have the expression:

$$((bool_1 \land (bool_2 \lor bool_3)) \land (\neg bool_4))$$

The $$8$$ subexpressions of this expression are:

$$bool_1$$

$$bool_2$$

$$bool_3$$

$$bool_4$$

$$(bool_2 \lor bool_3)$$

$$(bool_1 \land (bool_2 \lor bool_3))$$

$$(\neg bool_4)$$

$$((bool_1 \land (bool_2 \lor bool_3)) \land (\neg bool_4))$$