TITLE: Task about Conjunctive and Disjunctive normal form.
QUESTION [0 upvotes]: 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!

REPLY [1 votes]: 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.
{"set_name": "stack_exchange", "score": 0, "question_id": 3493948}