Task about Conjunctive and Disjunctive normal form.

Question

Happy new year to all!

I have a question related to my Discrete Mathematics examination:

Consider the following (parametrized) propositional formula $_$:

($p_1$V$p_{2n+1}$) & (!$p_1$V!$p_2$) & (!$p1$V$p_2$V$p_3$) & (!$p_1$V$p_2$V!$p_3$V!$p_4$) &

& (!$p_1$V$p_2$V!$p_3$V$p_4$V$p_5$) & ... & (!$p_1$V$p_2$V!$p_3$V$p_4$V!$p_5$V ... V!$p_{2n}$) &

& (!$p_1$V$p_2$V!$p_3$V$p_4$V!$p_5$V ... V$p_{2n}$V$p_{2n+1}$)

where ≥0 and all $_1$, ... $_{2+1}$ are propositional variables.

Question: For which ≥0 the formula $_$ is satisfiable? What method for checking the satisfiability do you use? (-Please name it.) Do you know any other method? (-Please name it.)

I understand how to deal with CNF and DNF, but in this case I do not know that to do with infinity terms, could you provide detailed solution?

Thanks in advance!

Answer 1

Let's see if I understand the pattern correctly.

For $n=0$ the formula would be:

$(p_1 \lor p_1) \land (\neg p_1 \lor p_1)$

Note that that one is satisfiable by setting $p_1=1$

For $n=1$ the formula would be:

$(p_1 \lor p_3) \land (\neg p_1 \lor \neg p_2) \land (\neg p_1 \lor p_2 \lor \neg p_2) \land (\neg p_1 \lor p_2 \lor p_3)$

That one is also satisfiable: Set $p_1=1$ to satisfy the first conjunct, then set $p_2=0$ to satisfy the second conjunct (which will also satisfy the third), and finally set $p_3=1$ to satisfy the last conjunct.

OK ... starting to maybe see a pattern here, but let's do one more:

For $n=2$ the formula would be:

$(p_1 \lor p_5) \land (\neg p_1 \lor \neg p_2) \land (\neg p_1 \lor p_2 \lor p_3) \land (\neg p_1 \lor p_2 \lor \neg p_3 \lor \neg p_4) \land (\neg p_1 \lor p_2 \lor \neg p_3 \lor p_4 \lor p_5)$

Again, this is easily satisfied: $p_1=1$, $p_2=0$, $p_3=1$, $p_4=0$, and $p_5=1$ will satisfy the $5$ conjuncts in order.

Well, now the pattern is clear: we can satisfy the expression for any $n$, because we can satisfy each of the individual conjuncts in order. That is, we can set the $i$-th conjunct true simply by giving $p_i$ the correct truth-value. To be specific: we just need to set $p_{2i-1}=1$ and $p_{2i}=0$ for $1 \leq i \leq n$

Question: For which $n \geq 0$ the formula $_$ is satisfiable? What method for checking the satisfiability do you use? (-Please name it.) Do you know any other method? (-Please name it.)

It is satisfiable for all $n \geq 0$

The 'method' is simply to find a truth-value assignment for which it is easily shown that it makes all conjuncts, and thus the whole expression, true.