Prove the proposition is a tautology 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.
 A: One way to break down the first question is to recall that $s\implies t\equiv \neg s\lor t$. So
$$
\begin{align*}
[(p \lor q) \land (\lnot p \lor r)] \to (q \lor r) &\equiv \neg[(p\lor q)\land (\neg p\lor r)]\lor(q\lor r)\\
&\equiv (\neg p\land\neg q)\lor(p\land \neg r)\lor (q\lor r)\\
\end{align*}
$$
by De Morgan's laws. If $(q\lor r)\equiv\top$, then you're done. Otherwise, $(q\lor r)\equiv\bot$, so $\neg q\equiv\neg r\equiv\top$. Then you only have to check the cases where $p\equiv\top$ and where $p\equiv\bot$, which isn't too bad since you're dealing with a disjunction.
A: 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.
A: The following is a semantic (model-theoretic) argument for the quantifiers question. (I cannot provide a syntactic argument, since I do not know what axioms, rules of inference are used in your course.  There is wide variability.)
So we use the following criterion: A sentence in a certain language $L$ is valid if it is true in every $L$-structure $M$.  Note that an $L$-structure has, by definition, a non-empty underlying set.
We will assume that $P$ has only one free occurrence of a variable. If in an $L$-structure $M$ for the appropriate language $L$, there really is a $b$ such that $P(b)$ is true in $M$, then $\exists y\forall x(P(x)\to P(y))$ is true in $M$, since $\forall x(P(x)\to P(b))$ is true in $M$. Thus the sentence you asked about is true in $M$.  The antecedent is irrelevant.
If there is no $n$ in $M$ such that $P(n)$ is true, then again $\exists y\forall x(P(x)\to P(y))$ is true in $M$. For let $b$ be some fixed element of $M$. 
Note that $P(b)$ is false in $M$. But for any $m$ in $M$, $P(m)$ is false in $M$.  It follows that for any $m$, $P(m)\to P(b)$ is true in $M$.  So again the sentence you asked about is true in $M$, and again the antecedent is irrelevant.
Comment: The whole thing hinges on the fact that $X\to Y$ is true whenever $Y$ is true, and also whenever $X$ is false.  The connective "implies" in ordinary English is not simply truth-functional. That is a frequent source of confusion.
Added: For the first part, we will use a variant of one of the approaches you tried.  You tried to show that if the left side is true, then the right side is true.  That can be done.  But to me it is somewhat easier to show (in this case) that if the right side of the implication is false, then the left side is false. 
We want to show that 
$$((p \lor q) \land (\lnot p \lor r)) \to (q \lor r)$$ 
is tautologous.  Think of your sentence as an implication $A \to B$.  For this to be false, we need $q\lor r$  false and $(p \lor q) \land (\lnot p \lor r)$ true. For $q\lor r$ to be false, we need $q$ false and $r$ false. So suppose $q$ and $r$ are false.
The only way then for $p\lor q$ to be true is if $p$ is true. The only way for $\lnot p \lor q$ to be true is if $p$ is false. So for both of them to be true, we need $p$ to be simultaneously true and false!  We conclude that if $p$ and $q$ are false, then $(p \lor q) \land (\lnot p \lor r)$ is false, so the implication is always true.
A: For the second question, it depends what set x and y can be chosen from.  If it's allowed to be the empty set, then the proposition is clearly false - the LHS is true because it starts with "for all x", and the RHS is false because it starts with "for some y".  Otherwise, reason as follows.  


*

*Case 1 - P(z) is false for all z, means that P(x) implies P(y) for
all x and y, so the RHS is always true.   

*Case 2 - P(z) is true for some z; then choose y to be that z and the RHS is true.


Since in both cases, RHS is true, the entire proposition is true.
Note that here, LHS and RHS refer to the two sides of the top level "implies" operation.
