Proving Conclusion of R: Using Rules of Inference and Given Premises

[Panphobia]

Homework Statement

(p \wedge t)\rightarrow (r \vee s),q \rightarrow (u \wedge t), u \rightarrow p, \neg s, q, show that these premises imply the conclusion of r

The Attempt at a Solution

The question calls for rules for inference to solve this problem, how would I go about doing that? Do I need to use more than one? Or can it be proven without using rules of inference. So the only thing I know that happens from here is that (p \wedge t)\rightarrow (r \vee s) turns into (p \wedge t)\rightarrow r

 

[scurty]

It's been awhile since I took a Logic course, but this looks like a standard problem that just involves using the 18 rules, have you covered all of them yet? If not, how many of the 18 are you allowed to use?

 

[Panphobia]

I think we have 8 or 10

 

[scurty]

Which ones do you have available to use? I can try to steer you in the right direction. Listing the names of the rules of inference is fine, you don't need to write out the symbols.

 

[Panphobia]

modus ponens, addition, modus tollens, simplification,hypothetical syllogism, conjunction, disjunctive syllogism, resolution

 

[scurty]

modus ponens, addition, modus tollens, simplification,hypothetical syllogism, conjunction, disjunctive syllogism, resolution

Okay, good. A good strategy is to find where you want to end up and look for ways to get there.

In this case we want r. The only statement that has r in it is statement 1. In order to conclude $r \vee s$, we need $p \wedge t$. I can give you the hint that to form $p \wedge t$, that you need to use Conjunction. Look for ways to obtain both p and t starting with statement 5: q.

 

[Panphobia]

I know that, the second statement gives me u and t, and then the third gives me p, but do I need to use rules of inference for these or...

 

[scurty]

I know that, the second statement gives me u and t, and then the third gives me p, but do I need to use rules of inference for these or...

Not quite. You have implications, you don't necessarily have the results. I'll give an example. The second statement is $q \implies u \wedge t$. You also have in the fifth statement: q.

Using Modus ponens:

$q \implies u \wedge t$
$q$
____________
$u \wedge t$

You now have $u \wedge t$ to use at your disposal (because you had q to use modus ponens). Does this make sense or was I too unclear?

 

[Panphobia]

Does this let us use u -> p? What rule of inference would you use for this, so confusing!

 

[scurty]

Does this let us use u -> p? What rule of inference would you use for this, so confusing!

You now have $u \wedge t$. What rule of inference can you use to reduce that conjunction down to just u? Then you could use u in a modus ponens with $u \to p$.

 

[Panphobia]

The only one that takes in only a conjunction is the simplification inference

 

[scurty]

Let me try explaining the process in a different way. You are given 5 statements/propositions. These are assumed to be true, so you can use any of them as you like. You have the rules of implication at your disposal. Each ones of the rules has premises and a conclusion. If your statements in the proof satisfy the premises, then you can conclude whatever each rule says. For example, if anywhere in your proof you have a $p \to q$ and also a $p$, then you can logically conclude $q$ by modus ponens.

 

[scurty]

The only one that takes in only a conjunction is the simplification inference

Correct. So, $u \wedge t$ becomes $u$ by simplification. Now you can use $u$ and $u \to p$...

 

[Panphobia]

u→p implies p right? So we have p did we already get t?

 

[scurty]

u→p implies p right? So we have p did we already get t?

You're getting the hang of it, you even know what the next thing is to get. You should be writing down every step in your proof and what rule you used for which lines right next to it just to keep track. We don't have $t$ yet, but we have $u \wedge t$... and once we have $p$ and $t$, we can...

 

[Panphobia]

Wait wait, I am kind of lost here, if it was u \wedge t by the truth table doesn't it mean that this whole statement is true only if both u and t are true. By the way, most of these steps we don't even use the rules of inference, just regular logic, is that ok?

 

[scurty]

Wait wait, I am kind of lost here, if it was u \wedge t by the truth table doesn't it mean that this whole statement is true only if both u and t are true. By the way, most of these steps we don't even use the rules of inference, just regular logic, is that ok?

Okay, perhaps the way I was taught was different than the way you are being taught. We needed to write out every step and why, you might not need to. You are correct that if we know the proposition $u \wedge t$ is true, then both $u$ and $t$ are true. I would have need to write down two different steps for this to get credit. Let me summarize what we have so far.

1. $p \wedge t \to r \vee s$
2. $q \to u \wedge t$
3. $u \to p$
4. ~$s$
5. $q$
6. $u \wedge t$, MP, 2,5
7. $u$, Simp, 6
8. $p$, MP, 3,7
9. $t$, Simp, 6
...

The abbreviation is what we used (modus ponens, simplification, etc) and the numbers are the lines we used in the proof. You are three steps away from the end at this point.

 

[Panphobia]

ahh fair enough, but now we have p and t, and we know that s is negated so r or s simplifies to, r, so (p ^ t) implies r, am I correct?

 

[scurty]

ahh fair enough, but now we have p and t, and we know that s is negated so r or s simplifies to, r, so (p ^ t) implies r, am I correct?

Yes! I would just mention that we have $r \vee s$ before the negated $s$, but those are the last steps.

I might be biased because it's the only way I learned, but I would highly recommend following the procedure I did above for writing out your proofs. It's easy to refer to later on when studying and you won't become disorganized during the actual proof. Here would be my last three steps:

10. $p \wedge t$, Conj., 8,9
11. $r \vee s$, MP, 1,10
12. $r$, DS, 4,11

I hope I did a decent job explaining. This is definitely something easier to explain in person than over the internet.

 

[Panphobia]

Yea but now I have to learn to use quantifiers in these proofs. Can they be used in this proof? I don't think so but you know more about this subject so I will just ask.

 

[scurty]

The 18 rules were the last topic area we covered in my course; quantifiers were the next section after it but we didn't get to it. I can't help you there, sorry. I think I recal it was rewriting the statements like $\forall x, P(x)$... or something like that. I don't know, sorry.