0
$\begingroup$

I have a formula like this: $$\bigvee_{\substack{i \in [1,...,m] \\ j \in [1,...,m]}} x_{i} \wedge x_{j}$$ What is the equivalent formula in CNF (conjunctive normal form)?

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

HINT

First see how this goes for a simple concrete example, and then try and make out the general pattern from that.

So, for a simple example, suppose $m=2$. So that means that you are dealing with the following expression:

$(x_1 \land x_1) \lor (x_1 \land x_2) \lor (x_2 \land x_1) \lor (x_2 \land x_2)$

Now, note that by Idempotence, $(x_1 \land x_1)$ is equivalent to just $x_1$.

Also, by Absorption, you have that $x_1 \lor (x_1 \lor x_2)$ is equivalent to just $x_1$.

So, the whole expression is equivalent to simply $x_1 \lor x_2$ ... which is in CNF.

Now, what do you think happens if we do this for any $m$ in general?

$\endgroup$

You must log in to answer this question.

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