Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I was given this on a practice exam:

Decide whether each of the following expressions is valid or invalid. Justify your answers (i.e.,if invalid, give an interpretation for which the expression is false;if valid explain why the expression is true for all interpretations.

(a) $[(\forall x)P(x) \vee (\exists x)Q(x)] \implies (\forall x)[P(x) \vee Q(x) ]$

(b) $[(\exists x)Q(x) \implies (\forall x)P(x)] \implies (\exists x)[P(x) \vee Q(x)]$

The answers are:

a. False: Let P(x)= "x != x" and Q(x) = "x=1"

b. False: Let "There exists x Q(x)" be false and "There exists x P(x)" be false.

I don't understand what he's doing. What am I not seeing?

share|improve this question

2 Answers 2

up vote 2 down vote accepted

Okay, let's start with part a.

$$[(\forall x)P(x) \vee (\exists x)Q(x)] \implies (\forall x)[P(x) \vee Q(x) ]$$

That $P(x)$ is true for all $x$ or that there exists a $x$ such that $Q(x)$ is true implies that for all $x$, at least one of $P(x)$ or $Q(x)$ is true.

For the examples given, $P(x)$ is never true (since $x = x$ always) and $Q(x)$ is true whenever $x = 1$. So we see that the part before the implication is true (since there exists a $x$ such that $Q(x)$ is true). The part after the implication is of course false, since for all $x \neq 1$, neither $P(x)$ nor $Q(x)$ is true. So the statement is false. For the statement to be true, the part to the right should always be true whenever the part to the left is true (if $A \Rightarrow B$, then $B$ should always be true when $A$ is true).

Part b.

$$[(\exists x)Q(x) \implies (\forall x)P(x)] \implies (\exists x)[P(x) \vee Q(x)]$$

If it is true that $Q(x)$ is true for at least one $x$ implies that $P(x)$ is true for all $x$, then there exists a $x$ such that at least one of $P(x)$ and $Q(x)$ is true.

In the example given, $Q(x)$ and $P(x)$ are never true, for any $x$. Thus the first implication can be taken to be true, but the last part is never true. The statement is false, by the same reasoning as in part a.

share|improve this answer

For each statement, we have $\text{TRUE} \implies \text{FALSE}$ which makes both statements invalid. In other words, the premises are true but the conclusion is false (hence both statements are invalid).

An argument is valid if and only if whenever its premises are true its conclusion must also be true. Consider the following argument:

Suppose I have a black cat Timmy. If all cats are black, then Timmy is black. Timmy is black. Therefore all cats are black. This is an instance of the following argument form:

  • If $p$ then $q$
  • $q$
  • Therefore $p$

This is invalid.

share|improve this answer
    
I don't see why, could you explain a little more @PEV? –  lampShade Feb 2 '11 at 21:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.