I've got (((P → Q) ∧ (R → S) ∧ (¬Q ∨ ¬S)) → (¬P ∨ ¬R)). Are there any quick and dirty ways to prove that it's a tautology/contradiction/neither without drawing a huge truth table?
Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga.
Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus.
Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
hmm, looks like this expression is true after all.
I haven't studied boolean algebra/formal logic so here's layman's perspective on what this expression is really trying to say.
We don't care about what happens if the left-hand-side turns out false because then the whole expression is true anyway but we're interested in the case where the left-hand-side is true.
So suppose that one of \(Q\) or \(S\) is false (\(\neg Q \wedge \neg S\)). The only way, then, that this left-hand-side can be true is when one of \(P\) or \(Q\) is false, because implication means that if the right-hand-side is false, then the left has to be false too!
And that is indeed the right-hand-side of the whole expression. :)
(((P → Q) ∧ (R → S) ∧ (¬Q ∨ ¬S)) → (¬P ∨ ¬R))
assume P -> Q, R -> S, ~Q | ~S.
now consider if ~Q. it follows then by contraposition that P -> Q is equivalent to ~Q -> ~P and so we can conclude ~P.
otherwise, consider if ~S. similarly, by contraposition we have that R -> S is equivalent to ~S -> ~R so it follows that we can conclude ~R.
so it follows that we can conclude ~P | ~R.