3

I was just wondering if some helpful person wouldnt mind helping me with this discrete maths question that has had be stuck for about a day now.

The argument is:

p or q
q implies ~p
q implies r
conclusion: r

I cant for the life of me figure out how to prove this.

Thanks heaps for any help you can give.

Thanks Corey

Fishingfon
  • 559
  • 1
    If I am reading correctly, you intend to start with the assumption that $p$ or $q$ is valid (maybe $p$ and not $q$, maybe $q$ and not $p$, or maybe $q$ and $p$), with the conditions that $q\Rightarrow \sim p$ and $q\Rightarrow r$. What if $p$ is true but $q$ and $r$ are false? – JMoravitz Apr 22 '15 at 01:40
  • Hey, this is the exact argument I copied from a previous exam for the course I am taking at university. I just can't seem to see any way of proving it. – Fishingfon Apr 22 '15 at 01:49
  • 2
    One way is by a truth table with eight rows, and a column for each of $p$, $q$, $r$, and a column of each of the premises, and a column for the conclusion. The argument is valid if the conclusion is true in every row in which all of the premises are true. Otherwise it's not valid. ${}\qquad{}$ – Michael Hardy Apr 22 '15 at 02:28

3 Answers3

5

The argument looks invalid.

Counterexample in natural language:

Look at this being, call it Purrty: http://thumbs.dreamstime.com/z/cat-1092150.jpg

Then consider three statements, $P$: Purrty is a cat. $Q$: Purrty is a dog. $R$: Purrty is a canine.

Clearly $Q$ implies not $P$ and $Q$ implies $R$.

Also clear is that $P$ or $Q$, since Purrty is a cat, so Purrty is a cat or a dog. This does not imply Purrty is a canine ($R$) (since it isn't) even though all three statements are assumed true.

Counterexample in mathematics:

Suppose for example we have three sets $A$, $B$ and $C$.

Then let $P$ be the statement $x\in A$ and $Q$ the statement $x\in B$ and $R$ be the statement $x \in C$.

Then $P$ or $Q$ is the statement $x \in A\cup B$.

$Q$ implies not $P$ is the statement $A$ and $B$ are disjoint.

$Q$ implies $R$ is the statement $B\subseteq C$.

But we can easily construct sets that all these are true, and yet $R$ isn't.

e.g. $A = (1,2)$, $B = (4,5)$ and $C=(3,5)$. We see that the second and third statements are true.

Now take $x=1.5$. Then $x \in (1,2) \cup (4,5)$. So $P$ or $Q$ is true. We also know $A$ and $B$ are disjoint (so $Q$ implies not $P$ is true) and $B \subseteq C$, so $Q$ implies $R$ is true). This however, does not imply $x \in (3,5)$ ($R$).

Since this argument does not result in true conclusions everytime we give it true premises, it is invalid.

Edit: A good way to see it logically is via the truth table as mentioned in the comments.

Ilham
  • 1,567
3

The argument is invalid. All you can show is that: $p$ and $q$ cannot both be true and $r$ is true whenever $q$ is.

A valid argument would be

$$\left|\begin{align*} p\vee q\\ \color{red}{\neg} q\to \neg p\\ q\to r \\ \hline r \end{align*}\right.$$

Are you sure that you did not miscopy the question?

Graham Kemp
  • 129,094
  • Hey, no I copied it exactly as it was in the exam paper. At least I now know why I couldn't prove it valid :p. Thanks heaps to everyone who posted. Corey :) – Fishingfon Apr 22 '15 at 04:41
2

We can apply Resoulution to the three clauses (the premises) :

1) $p \lor q$

2) $\lnot q \lor \lnot p$ (equivalent to : $q \to \lnot p$)

3) $\lnot q \lor r$ (equivalent to : $q \to r$)

and the negation of the purported conclusion :

4) $\lnot r$.

Applying the procedure we get :

i) $p \lor r$ --- from 1) and 3)

ii) $\lnot q \lor r$ --- from i) and 2)

iii) $\lnot q$ --- from ii) and 4).

We have concluded the procedure without having derived the empty clause; thus, the argument is invalid.

Mauro ALLEGRANZA
  • 94,169