How can Boolean functions be defined recursively?

Question

I found this line in Kenneth H. Rosen.

How can $x_1, x_2, x_3, ..., x_n$ be boolean expressions? aren't they boolean variables and not expressions? I am confused with this whole paragraph.

Answer 1

A variable is a special form of a boolean expression. Each boolean expression can be created by using these rules.

Let's investigate the expression $$(\overline{(\overline{x_1}+x_2)}x_1)$$ This is a boolean expression because it can be constructed by applying the following rules

1. $0,1,x_1,x_2$ are Boolean expressions
2. if $E_1$ is a Boolean expressions, then $\overline E_1$ is a Boolean Expression
3. if $E_1$ and $E_2$ are Boolean expressions, then $(E_1 +E_2)$ is a Boolean Expression
4. if $E_1$ and $E_2$ are Boolean expressions, then $(E_1 E_2)$ is a Boolean Expression

So the following steps show why the expression above is a boolean expression.

1. $x_1$ is a Boolean epression by applying rule 1
2. $x_2$ is a Boolean epression by applying rule 1
3. $\overline {x_1}$ is a boolean expression by applying rule 2 to the result of step 1 $[E_1\equiv x_1]$
4. $(\overline {x_1}+x_2)$ is a boolean expression by applying rule 3 to to the result of step 3 $[E_1\equiv \overline {x_1}]$ and to the result of step 2 $[E_2\equiv x_2]$
5. $\overline {(\overline {x_1}+x_2)}$ is a boolean expression by applying rule 2 to to the result of step 4 $[E_1 \equiv (\overline {x_1}+x_2)]$
6. $(\overline {(\overline {x_1}+x_2)} x_1) $ is a boolean expression by applying rule 4 to to the result of step 5 $[E_1 \equiv \overline {(\overline {x_1}+x_2)}]$ and to the result of step 1 $[E_2\equiv x_1]$

The character strings $(x_1 + x_2+)$, $x_1+x_2$, $(x+ y)$, $(x_1\overline {+x_2})$, $(x_1+(x_2x_3)$ are not Boolean expressions according to these rules.

If $x_1,...,x_n$ in rule 1 is not meant literally but $x_i$ stands for arbitrary letters or valid variable names, then $(x+ y)$ is a Boolean expression.

Such recursive descriptions are frequently used to describe the syntax of programming languages.

Answer 2

You misunderstand what an expression is meant to be: it's any term (with possibly (and very often) variables) where we can replace any variables by $0$ or $1$ and we get something that can be evaluated to $0$ or $1$.