Hello I have this Boolean formula:1... (¬P ∨ Q) ∧ (¬Q ∨ R) ∧ (¬R ∨ S) ∧ (¬S ∨ P) ∧ M ∧ ¬N
I separated this into 5 pieces and I wrote the truth table, then from the truth table I found that DNF of this formula is:
2... ((¬P ∨ Q) ∧ (¬Q ∨ R) ∧ (¬R ∨ S) ∧ (¬S ∨ P) ∧ ¬M ∧ N ) ∨ ((P ∨ Q) ∧ (Q ∨ R) ∧ (R ∨ S) ∧ (S ∨ P) ∧ M ∧ N)
But we have to been told to arrive to this form of DNF:
3... (M ∧ ¬N ∧ ¬P ∧ ¬Q ∧ ¬R ∧ ¬S) ∨ (M ∧ ¬N ∧ ¬P ∧ R ∧ S) ∨ (M ∧ ¬N ∧ Q ∧ R ∧ S)
Now I took the formula 2... and I did this operation, but I do not know how to further derive in oder to arrive to formula 3...
Here is whay I did:
((¬P + Q) * (¬Q + R) * (¬R + S) * (¬S + P) * (¬M + N ) + ((P + Q) * (Q + R) * (R + S) * (S + P) * M * N)
((¬P¬Q + ¬PR + Q¬Q + QR) * (¬R¬S + ¬RP + S¬S + SP) * ¬M *N) + ((PQ + PR + QQ + QR) * (RS + RP +SS + SP) * M * N)
Now I know that Q¬Q = 0, S¬S = 0, QQ =Q and SS=S, then I substitute these in:
((¬P¬Q + ¬PR + QR) * (¬R¬S + ¬RP + SP) * ¬M *N) + ((PQ + PR + Q + QR) * (RS + RP +S + SP) * M * N)
But here I do not know how to derive this more in order to arrive at 3...
Can someone guide me how to actually arrive there ?
There is something wrong with the 'answer' given in 3, as 3. would be true if $Q$, $R$, $S$, and $M$ are true, and $P$ and $N$ are false (for it would make the third disjunct true), but the original statement is false in that case, as the conjunct $\neg S \lor P$ would be false. So 3. is not equivalent to 1.
Here's what I get (I'll use $P'$ for $\neg P$):
$$(P' + Q)(Q' + R)(R' + S)(S' + P)=$$
$$P'Q'R'S'+P'Q'R'P+P'Q'SS'+P'Q'SP+P'RR'S'+P'RR'P+P'RSS'+P'RSP+ QQ'R'S'+QQ'R'P+QQ'SS'+QQ'SP+QRR'S'+QRR'P+QRSS'+QRSP$$
Given $PP'=0$, $P0=0$, and $P+0=P$, we can eliminate any term that contains some atomic claim and its complement, and thus we get:
$$P'Q'R'S'+P'Q'R'P+P'Q'SS'+P'Q'SP+P'RR'S'+P'RR'P+P'RSS'+P'RSP+ QQ'R'S'+QQ'R'P+QQ'SS'+QQ'SP+QRR'S'+QRR'P+QRSS'+QRSP=$$
$$P'Q'R'S'+QRSP$$
(which makes sense if you look at those four original terms: as soon as you set one of $P$, $Q$, $R$, or $S$ to true to satisfy one of the terms, you are forced to chain through and set them all to true. Likewise, once you set one of the m to false, you'll have to set all of them to false. So there are indeed only two ways to satisfy this: either all true or all false)
Plugging that into the original expression, we thus get:
$$(P' + Q)(Q' + R)(R' + S)(S' + P)MN'=$$
$$(P'Q'R'S'+PQRS)MN'=$$
$$P'Q'R'S'MN'+PQRSMN'$$