# Mathematical Foundation of a Functional Implementation of the CNF Algorithm
## 4 Associativity
* \(\alpha\equiv K\varphi\rho\) for certain \(\varphi,\rho\in\mathrm{K}(\mathrm{A}(X))\). Let us distinguish the following cases:
- \(\rho\in A(X)\); then: \[=\max\{-1,-1\} \text{induc. hyp.}\]2 \[=\max\{-1,-1\} \text{induc. hyp.}\]3 \[=\max\{-1,-1\} \text{induc. hyp.}\]4 \[=\max\{-1,-1\} \text{induc. hyp.}\]5 \[=\max\{-1,-1\} \text{induc. hyp.}\]6 \[=\max\{-1,-1\} \text{induc. hyp.}\]7 induc. hyp. and Lemma 4 \[=\max\{-1,-1\} \text{induc. hyp.}\]8 \[=\max\{-1,-1\} \text{induc. hyp.}\]9 \[=-1\]0 \[=-1\]1
* \(\rho\
ot\in A(X)\); then \(\alpha\equiv K\varphi K\varphi\zeta\) for certain \(\psi,\zeta\in\mathrm{K}(\mathrm{A}(X))\). In this case, \[=-1\]2 \[=-1\]3 \[=-1\]4 induc. hyp. \[=-1\]5 \[=-1\]6 \[=-1\]7 \[=-1\]8  
By the _second principle of finite induction_, for every natural number \(n\), \(Q(n)\) holds, hence the validity of statement 2. Statement 3 is immediate from statements 1 and 2, given that  
\[=-1\]9  
**Lemma 10**. : _Let \(\alpha\in\mathrm{A}(X)\). The following statements are equivalent:_  
1. \(\alpha\in\mathrm{al}(X)\)__
2. \(\mathrm{lasc}(\alpha)\equiv\alpha\)__
3. \(\mathrm{ar}(\alpha)\leq 0\)__  
Proof. : To show that statement 1 implies statement 2, we will reason by induction about the complexity of \(\alpha\) according to the predicate \(Q(n)\) of the literal content:  
\"for all \(\alpha\), if \(\alpha\in\mathrm{al}(X)\) and \(\mathrm{comp}(\alpha)=n\) then \(\mathrm{lasc}(\alpha)\equiv\alpha\)\"  
Suppose, as an induction hypothesis, that \(n\) is a natural number and that for any natural number \(k\) such that \(k<n\), \(Q(k)\) holds. We distinguish the following cases:  
* \(n=0\); must be \(\alpha\equiv x\in X\) and then \(\mathrm{lasc}(\alpha)\equiv\mathrm{lasc}(x)\equiv x\equiv\alpha\). * \(n>0\); let --as the only case of interest-- \(\alpha\equiv A\varphi x\), where \(\varphi\in\mathrm{al}(X)\) and \(x\in X\). Then \[-1 =\mathrm{ar}(\alpha)\]0 \[-1 =\mathrm{ar}(\alpha)\]1 \[-1 =\mathrm{ar}(\alpha)\]2 \[-1 =\mathrm{ar}(\alpha)\]3 hence, \[-1 =\mathrm{ar}(\alpha)\]4 holds. By the _second principle of finite induction_, for every natural number \(n\)\(Q(n)\) holds, hence the validity of statement 2. Let us now suppose that statement 2 is true, i.e., that \(\alpha\in\mathrm{A}(X)\) and that \(\mathrm{lasc}(\alpha)\equiv\alpha\); then, one has  
\[-1 =\mathrm{ar}(\alpha)\]5 \[-1 =\mathrm{ar}(\alpha)\]6 (Lemma 9)  
from which we deduce that \(\mathrm{ar}(\alpha)\in\{-1,0\}\), i.e., that statement 3 holds. Finally, suppose that \(\alpha\in\mathrm{A}(X)\) and that \(\mathrm{ar}(\alpha)\leq 0\). The following cases are possible (note that, according to statement 2 of Lemma 4, necessarily \(\mathrm{kr}(\alpha)=-1\)):  
1. \(\mathrm{ar}(\alpha)=-1\) and \(\mathrm{kr}(\alpha)=-1\); then \(\alpha\in X\subseteq\mathrm{al}(X)\) (see Lemma 5). 2. \(\mathrm{ar}(\alpha)=0\) and \(\mathrm{kr}(\alpha)=-1\); then \(\alpha\in\mathrm{al}(X)\setminus X\) (see Lemma 6). This proves that under the assumption of statement 3. the fact \(\alpha\in\mathrm{al}(X)\) is satisfied, as we sought to prove. In Theorem 4, the effects of alt and lasc are finally combined to characterise the formulas in \(\mathrm{lcnf}(X)\). **Theorem 4**. : _For all \(\alpha\in\mathrm{P}(\mathbf{L})\), the following statements are equivalent:_  
1. \(\alpha\in\mathrm{lcnf}(X)\) _._
2. \(\mathrm{dak}(\alpha)\equiv\alpha\) _and_ \(\mathrm{lasc}(\alpha)\equiv\alpha\) _._
3. \(\mathrm{alt}(\alpha)=0\) _and_ \(\mathrm{akr}(\alpha)\leq 0\)_._  
Proof. : Let \(\alpha\) be any formula in \(\mathrm{P}(\mathbf{L})\). Assume what statement 1 states, i.e., that \(\alpha\in\mathrm{lcnf}(X)\). We will reason by induction about the complexity of \(\alpha\) according to the predicate \(Q(n)\) of the literal content:  
\"for all \(\alpha\), if \(\alpha\in\mathrm{lcnf}(X)\) and \(\mathrm{comp}(\alpha)=n\), then \(\mathrm{dak}(\alpha)=\alpha\) and \(\mathrm{lasc}(\alpha)=\alpha\)\"Suppose, as an induction hypothesis, that \(n\) is a natural number and that for any natural number \(k\) such that \(k<n\), \(Q(k)\) holds.