0
$\begingroup$

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.

enter image description here

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:

enter image description here

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ Nov 28 '21 at 12:18
  • 1
    $\begingroup$ 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. $\endgroup$ Nov 28 '21 at 12:20
1
$\begingroup$

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))$

OK, now follow the hint left by Mauro in the Comments

$\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.