how does $(p\to q)\lor r \lor s$ effect $(p\leftrightarrow q) \lor r \oplus s$

Question

If we know that $\lnot p \lor q \lor r \lor s=\top$, then what is the value of: $(\lnot p \land \lnot q) \lor (p \land q) \lor(r \land \lnot s) \lor (\lnot r \land s)$

I tried doing it with a truth table but the answer is not apparent, the answer of course is not "True" or "False" but it will be something with $p,q,r,s$

I also tried deducing it using identities but it gets very complicated. I would appreciate any help, thank you.

Answer 1

Something like this?

$(\lnot p \land \lnot q) \lor (p \land q) \lor(r \land \lnot s) \lor (\lnot r \land s)$

Distribute:

$((\lnot p\lor p)\land(\lnot p\lor q)\land(\lnot q\lor p)\land(\lnot q \lor q))\lor ((r\lor \lnot r)\land(r\lor s)\land(\lnot s\lor \lnot r)\land(\lnot s\lor s))$

Use Identity Rules:

$((\lnot p\lor q)\land(\lnot q\lor p))\lor ((r\lor s)\land(\lnot s\lor \lnot r))$

Distribute:

$(\lnot p\lor q\lor r\lor s)\land(\lnot p\lor q\lor\lnot r\lor\lnot s)\land(p\lor\lnot q\lor r\lor s)\land(p\lor \lnot q\lor \lnot r\lor \lnot s)$:

Because $(\lnot p\lor q\lor r\lor s) = \top$ is known:

$(((\lnot p\lor q)\land(p\lor\lnot q))\lor\lnot r\lor\lnot s)\land(p\lor\lnot q\lor r\lor s)$

Use Implication Equivalence to put it in the same style as the original:

$((p\leftrightarrow q)\lor (\lnot r\lor \lnot s))\land((q\to p)\lor r\lor s))$

Answer 2

It’s not clear just what kind of answer you want, so I don’t know whether this will be helpful or not: I’ll look at the effect that the hypothesis has on the conjunctive and disjunctive normal forms of the expression $(p\leftrightarrow q)\lor(r\oplus s)$.

It’s helpful to the intuition to let $t=\neg p$, so that we’re assuming that $t\lor q\lor r\lor s=\top$ and investigating $(t\oplus q)\lor(r\oplus s)$. The latter is false in exactly four cases: $t,q,r$, and $s$ all true; $t$ and $q$ true, and $r$ and $s$ false; $t$ and $q$ false, and $r$ and $s$ true; and $t,q,r$, and $s$ all false. The hypothesis rules out the last, so we have $(t\oplus q)\lor(r\oplus s)$ equivalent to

$$\neg\big((t\land q\land r\land s)\lor(t\land q\land\neg r\land\neg s)\lor(\neg t\land\neg q\land r\land s)\big)\;.$$

A few applications of De Morgan reduce this to

$$(\neg t\lor\neg q\lor\neg r\lor\neg s)\land(\neg t\lor\neg q\lor r\lor s)\land(t\lor q\lor\neg r\lor\neg s)\;,$$

and replacing $t$ and $\neg t$ by $\neg p$ and $p$, respectively, yields

$$(p\lor\neg q\lor\neg r\lor\neg s)\land(p\lor\neg q\lor r\lor s)\land(\neg p\lor q\lor\neg r\lor\neg s)$$

in conjunctive normal form. Without the hypothesis the conjunctive normal form would have a fourth conjunct, $\neg p\lor q\lor r\lor s$.

The hypothesis has no effect on the disjunctive normal form, since it rules out only the potential disjunct $p\land\neg q\land\neg r\land\neg s$, which does not appear in the disjunctive normal form of $(p\leftrightarrow q)\lor(r\oplus s)$: the latter is false when $p\land\neg q\land\neg r\land\neg s$ is true.