I am trying to create CNF formula for manipulation of a word. word is a sequence of letters from a $\Sigma$ alphabet. A word is encoded by variables like $x_{i,a}$ which means that the letter $a$ is at position $i$.
So there is these two questions that I am interested in:
- How to write a formula in CNF that expresses that the word does not contain any $b$ on it?
So far I have come up with thise but I am not sure if it is true:
$$\bigwedge_{i=1}^n \; (\bigvee_{b \in \Sigma} \neg x_{i,b} )$$ - How to write a formula (not necessarily in CNF) that expresses that the word has $abc$ on it in consecutive positions?
I have come up with this but again I am not sure:
$$\bigwedge_{i=1}^{n-2} \; ((x_{i,a} \rightarrow x_{i+1,b}) \rightarrow x_{i+2,c})$$
I would be appreciated if someone could help me.
The first one is $$\lnot \bigvee_{i=1}^n x_{i,b} = \bigwedge_{i=1}^n \lnot x_{i,b}$$
The second one is $$\bigvee_{i=1}^{n-2} \left(x_{i,a} \land x_{i+1,b} \land x_{i+2,c}\right)$$