Question

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?

Answer 1

hmm, looks like this expression is true after all.

Answer 2

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. :)

Answer 3

(((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.

Answer 4

https://en.wikipedia.org/wiki/Constructive_dilemma