I'm struggling in converting this problem to Conjunctive Normal Form. I'd appreciate any help or guiding.

There are $n$ stones in the river. Every stones has two states: above or below the water. There are $m$ switches. Every switch has two states: open and close. These switches can control the states of the stones. Every time you change the state of a switch, the states of the corresponding stones also change. Each switch control one or two stones.

First of all, I use $P_1$ to $P_n$ to denote stone states and $Q_1$ to $Q_m$ to denote switch states.

The problem is I don't know how should I interpret switch control the states of the stone relationship to proposition logic.

Thank so much in advance!


Say switch $i$ controls stones $j$ and $k$. In particular, suppose that if switch $i$ is open then stone $j$ goes above water, and stone $k$ goes under water, and when we close switch $i$, then stone $j$ goes under water, and stone $k$ goes above water.

Let's use $P_j$ for stone $j$ being above water, $\neg P_k$ for stone $k$ being under water, and $S_i$ for switch $i$ being open.

Then we have:

$$(S_i \to (P_j \land \neg P_k)) \land (\neg S_i \to (\neg P_j \land P_k))$$

which transforms to CNF:

$$(\neg S_i \lor (P_j \land \neg P_k)) \land (S_i \lor (\neg P_j \land P_k)) = (\neg S_i \lor P_j) \land (\neg S_i \lor \neg P_k)) \land (S_i \lor \neg P_j) \land (S_i \lor P_k))$$

  • $\begingroup$ Thank you so much! $\endgroup$ – One Piece Nov 10 '19 at 4:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.