1
$\begingroup$

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:

  1. 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} )$$
  2. 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.
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thank you for your response. Could I ask why in the first formula, you have deleted the big disjunction? And also for second formula I also taught something that you wrote but isn't it correct the thing that I wrote? $\endgroup$
    – mrjamaisvu
    Commented Oct 31, 2020 at 8:58
  • $\begingroup$ Your first proposition is for a fixed $b$, so the formula should not include a disjunction over arbitrary $b$. Your second proposition is fundamentally a disjunction because you want $abc$ to appear in at least one position. Consider $ababc$, which is acceptable but does not satisfy your formula. $\endgroup$
    – RobPratt
    Commented Oct 31, 2020 at 11:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .