I have two homework questions that I've been struggling with. For the first I need to prove that
$((p \lor q) \land (\lnot p \lor r)) \to (q \lor r)$
is a tautology.
I've tried two approaches. First I tried substituting other logically equivalent statements for the propositions on the LHS. Once that failed, I tried assuming that the LHS is true and I tried to show the RHS must also be true. I wasn't able to do that either. There is nothing saying I can't use a truth table, but I'd prefer not to. Any help would be appreciated.
The second question is to decide whether
$\forall x \exists y(P(x) \to P(y)) \to \exists y \forall x(P(x) \to P(y))$
is logically valid or not. Does logically valid mean tautology? If so, I don't even know where to start.
EDIT: This question originally asked to prove the second expression as true, which was incorrect.
Best Answer
For the first question, observe that $$(p \lor q) \land (\lnot p \lor r)\Leftrightarrow (p \land \lnot p) \lor (p\land r)\lor (q\land \lnot p)\lor (q\land r)$$ and that $(p\land \lnot p)$ is always false. I have omitted parentheses for convenience because $\lor$ is associative, but if you have not yet proven this then you must include them (it shouldn't cause a problem though).
For the second, I have always heard logically valid used to mean "always true" or in this case specifically "true for any P". Under this interpretation the second question appears to me to be false, as we could have a different $y$ for each $x$ such that $P(x)\to P(y)$, and so no $y$ would make the statement $\forall x(P(x)\to P(y))$ true.