0
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.