0 order Logic Construction Sequence

I am asked to exhibit a construction sequence to show whether the following is a well-formed formula;

Let S = {A, B, C, D}

$\alpha = ((A\land C) \rightarrow (((\lnot A) \land (\lnot C)) \lor B)))$

I know how to draw the tree and I think it is sufficient to show it is a wff.(is it?) But I couldn't see any examples of how to exhibit a construction sequence. Any ideas?

1 Answer

You can draw a tree, starting from the "innermost" subformulas.

The terminal nodes must be obviously the atoms : $A,B,C$.

To $A$ add $(\lnot A)$ and to $C$ add $(\lnot C)$. Then both will produce $((\lnot A) \land (\lnot C))$ and with $B$ we have : $(((\lnot A) \land (\lnot C)) \lor B)$.

In the same way, you have to generate the other branch starting from $A$ and $C$ and producing $(A \land C)$.

Finally, use both branches to join them in the final formula, the root of the tree.

You can use instead the definition :

A sequence $\varphi_0, \ldots, \varphi_n$ is called a formation sequence of $\varphi$ if

$\varphi_n = \varphi$ and for all $i ≤ n$ $\varphi_i$ is atomic, or

$\varphi_i = (\varphi_j \square \varphi_k)$ for certain $j, k <i$, where $\square$ is a binary conncetive, or

$\varphi_i = (¬ \varphi_j)$ for certain $j < i$.

Again, you have to start from atoms :

$A,B,C,(\lnot A),(\lnot C), (A \land C), \ldots$