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

-
The reading order of the first proposition is unclear, could you add parenthesis to clarify what is connected by the implication? –  Asaf Karagila Jan 16 '12 at 22:42
I've added the parenthesis, although it should have been clear simply from precedence. –  gsingh2011 Jan 16 '12 at 22:57
Do you have any sort of proof system at hand here? If you do, you could show the first proposition a theorem, and then invoke soundness. –  Doug Spoonwood Jan 17 '12 at 1:14
@gsingh2011: Unfortunately there is no universally observed convention for what the precedence rules for logical connectives are. Unless one is working within a particular context where specific rules have explicitly been adopted, it is recommended to err on the side of too many parentheses. –  Henning Makholm Jan 17 '12 at 2:23
@HenningMakholm I don't see how you can err on the side of too many parentheses to begin with. After all, if you fully parenthesize a statement, you end up writing the actual wff instead of a shorthand for one. –  Doug Spoonwood Jan 17 '12 at 20:51

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.

-
Sorry I made a mistake with the second question. I think your logic is actually correct; it should be false. –  gsingh2011 Jan 16 '12 at 23:21
@gsingh2011 Ah, that makes sense. It shouldn't be too hard to come up with an counterexample along the lines of the reasoning I gave. –  Alex Becker Jan 16 '12 at 23:30

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.

-
It may be a bit more clear if you specify the first sentence more abstractly, that is, you don't confuse the variables (not sure if that's the proper term in this context, perhaps propositions is better??). $p$ and $q$ are in the actual problem, but you're using them differently to represent the general principle. So, maybe it would be better to replace $p \implies q \equiv \neg p \lor q$ with $A \implies B \equiv \neg A \lor B$. Just a suggestion, your answer looks perfectly fine to me. –  000 Jan 16 '12 at 22:56
@user22144 You're quite right, that definitely could be confusing. Thanks for the suggestion! –  yunone Jan 16 '12 at 22:58
You're welcome. I'm glad I can contribute where I would otherwise have no clue how, lol. –  000 Jan 16 '12 at 22:59

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.

-

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.

-