-2

$[ (¬p ∨ s) ∧ (¬ t ∨ ( s ∧ r)) ∧ ( ¬q ∨ r) ∧ ( p ∨ q ∨ t)] \rightarrow ( r ∨ s)$.

I have no idea how to go about this proof. I don't see any way to simply to prove that it is correct, truth table is too many rows. What do I do?

Jean Marie
  • 81,803
lollol12345
  • 67
  • 3
  • 2
    do you know how to use Karnaugh maps? – trying Sep 10 '17 at 22:31
  • 1
    do you know what logically valid means versus say logically sound ? –  Sep 10 '17 at 22:32
  • Eliminate the $p \vee q \vee t$ term: then in the first case, the first term implies $s$; in the second case, the third term implies $r$; and in the third case, the second term implies $s \wedge r$ so $r \vee s$. – Daniel Schepler Sep 10 '17 at 23:14

1 Answers1

1

Let $A$ be the statement

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

and let $B$ be the statement $r \lor s$.

To prove $A \rightarrow B$, we can instead prove the contrapositive $\lnot B \rightarrow \lnot A$.

Thus, assume $\lnot B$. Then $r \lor s$ is false, hence $r,s$ must both be false. \begin{align*} \text{Then}\;\;A &=(\lnot p \lor s) \land (\lnot t \lor (s \land r)) \land ( \lnot q \lor r) \land ( p \lor q \lor t)\\[4pt] &=(\lnot p \lor \bot) \land (\lnot t \lor (\bot \land \bot)) \land ( \lnot q \lor \bot) \land ( p \lor q \lor t)\\[4pt] &=(\lnot p) \land (\lnot t) \land (\lnot q) \land (p \lor q \lor t)\\[4pt] &=(\lnot p \land \lnot q \land \lnot t) \land (p \lor q \lor t)\\[4pt] &=\lnot (p \lor q \lor t) \land (p \lor q \lor t)\\[4pt] &=\bot \end{align*} hence $\lnot A$, as was to be shown.

quasi
  • 58,772