# Discrete math - show argument is valid using rules of inference and the logical equivalences

I'm doing a practice quiz for a quiz tomorrow on logical predicates and I'm stuck on figuring out how to solve this question below. Assuming all premises are true, I'm asked to prove that the following argument is valid using only the rules of inferences and logical equivalences.

The universe of discourse is all animals.

Given:

Animals that live in the swamp can swim.

Some rats live in the swamp.

All rats have large teeth.

Show:

There is a rat that has large teeth and can swim.

What I did so far:

Let W(x) be "x lives in a swamp", S(x) be "x can swim", R(x) be "x is a rat", and T(x) be "x has large teeth"

Translate premises:

1) ∀x(W(x) → S(x))

2) ∃x(R(x) ∧ W(x))

3) ∀x(R(x) → T(x))

Prove (not sure if this is wrong): ∃x(R(x) ∧ T(x) ∧ S(x))

My solution so far:

1) ∀x(W(x) → S(x))

2) ∃x(R(x) ∧ W(x))

3) ∀x(R(x) → T(x))

4) R(y) ∧ W(y) by existential instantiation (2)

5) W(y) → S(y) by universal instantiation (1)

6) W(y) by simplification (4)

7) S(y) by modus ponens (5, 6)

8) R(y) → T(y) by universal instantiation (3)

9) R(y) by simplification (4)

10) T(y) by modus ponens (8,9)

11) S(y) ∧ T(y) by conjunction (7, 10)

12) R(y) by simplification (4)

13) (S(y) ∧ T(y)) ∧ R(y) by conjunction (11, 12)

14) R(y) ∧ T(y) ∧ S(y) by commutativity (13)

15) ∃x(R(x) ∧ T(x) ∧ S(x)) by existential generalization (14)

UPDATE: Okay so I fixed some errors and I think I got an answer? I would appreciate if someone could confirm my new solution and tell me if I made any errors.

I'm still a little unsure about my proof statement "There is a rat that has large teeth and can swim." I got ∃x(R(x) ∧ T(x) ∧ S(x)) but was wondering if it could be ∃x(R(x) → (T(x) ∧ S(x))). What would be the difference between the two?

• If $S(x)$ means $x$ can swim, the translation of the second statement is wrong and should contain $W(x)$ instead. – Shubham Johri May 28 at 5:53
• sorry I should mention the universe of discourse is all animals – GilmoreGirling May 28 at 5:56
• Yes, that is understood. What I meant was the second statement should be translated as $\exists x(R(x)\wedge W(x))$ – Shubham Johri May 28 at 5:59
• There are tools such as proofs.openlogicproject.org where you can enter and check your proofs. – Derek Elkins May 28 at 7:29

Note that you can avoid commutation on line 14, because you can conjunct statement in any order. For example, it is ok to derive $$T(y) \land S(y)$$ on line 11 ... you just have to say "Conjunction 10,7" rather than "Conjunction 7,10".

In fact, if your book or instructor allows generalized conjunctions (i.e. if it allows a statement like $$\exists x (R(x) \land T(x) \land S(x))$$ without any further parentheses) then you are probably allowed to apply conjunction to any number of statements as well, i.e. you can go straight from 12, 10, and 7 to $$R(y) \land T(y) \land S(y)$$.

Finally, yes, $$\exists x (R(x) \land T(x) \land S(x))$$ is the correct statement to prove. Note that $$\exists x (R(x) \to (T(x) \land S(x)))$$ would be true if there is at least one object in the domain that is not a rat (for then for that object $$R(x)$$ is fklase, and hence the whole conditional $$R(x) \to (T(x) \land S(x))$$ would be true, and hence we would have $$\exists x (R(x) \to (T(x) \land S(x)))$$, even if there would be no rats that can swim and have large teeth .. clearly not what we want!

Your proof is correct. A quick note: 12) is redundant because you have 9).

You indeed have to prove $$\exists x: R(x) \land T(x) \land S(x)$$.

$$\exists x: R(x)\implies(T(x)\land S(x))$$ would translate to „there is something that is not a rat; or that something has large teeth and can swim.“ (The or in the latter sentence is, of course, inclusive.) This is because for two statements $$A$$, $$B$$, we have $$A\implies B \equiv \lnot A \lor B$$.

• Might be worth adding that you used the equivalence $P\to Q\equiv P'\vee Q$ to translate the second statement – Shubham Johri May 28 at 9:24
• @ShubhamJohri added; thanks for your comment – Maximilian Janisch May 28 at 9:28

You have translated the sentences correctly, made the correct assumption, and all the required steps, but the order of steps can be streamlined and the redundancy removed. (You do not need to derive $$R(y)$$ twice, and you can choose the order you introduce the conjuncts).

$$\def\fitch#1#2{\quad\begin{array}{|l}#1\\\hline #2\end{array}}\fitch{~1.~\forall x~(W(x) \to S(x))\\ ~2.~\exists x~(R(x) \wedge W(x))\\~3.~\forall x~(R(x) \to T(x))}{\fitch{~4.~[y]~R(y)\land W(y)}{~5.~W(y)\to S(y)\hspace{9ex}\forall~\text{E},1\\~6.~R(y)\to T(y)\hspace{9.5ex}\forall~\text{E},3\\~7.~R(y)\hspace{17ex}\wedge\text{E},4\\~8.~T(y)\hspace{17.5ex}{\to}~\text{E},7,6\\~9.~S(y)\hspace{17.5ex}{\to}~\text{E},7,5\\10.~R(y)\wedge T(y)\hspace{10ex}{\wedge}~\text{I},7,8\\11.~R(y)\wedge T(y)\wedge S(y)\hspace{3ex}{\wedge}~\text{I},10,9\\12.~\exists x~(R(x)\wedge T(x)\wedge S(x))\hspace{1ex}\exists~\text{I}, 11}\\13.~\exists x~(R(x)\wedge T(x)\wedge S(x))\hspace{1ex}\exists~\text{E}, 2,4{-}12}$$

"There is some animal that is a rat, has large teeth, and swims."

As others have stated, $$\exists x~(R(x)\to T(x)\wedge S(x))$$ asserts that "there is some animal that is not a rat or it has large teeth and swims", and this could be true if there were no rats with large teeth that swim. (If there were instead a hippopotamus in the swamp, for example.)

Because $$R(x)\to Q(x)$$ is equivalent to $$\lnot R(x)\vee Q(x)$$