# Help with a few propositional logic proofs

1. Philosophy Forum
2. » Logic
3. » Help with a few propositional logic proofs

Sun 8 Feb, 2009 03:33 pm
I'm having a really hard time solving the following proofs in Tomassi's Logic book.

1)
P v Q : (P v R) -> (P v(Q & R))

2)
P : Q -> (P <->Q)

3)

P v (Q v R) : Q v (P v R)

VideCorSpoon

Sun 8 Feb, 2009 08:50 pm
@unprocessed9,
Hi unprocessed9!

These are definitely some hard problems. I got through the first problem, though I don't know how many rules you can use at this point for your class yet. I only used the conjunction inference, distribution replacement rule, and an overall conditional proof (i.e. Indent, assume P, derive Q, and assert P-->Q)

I'm going to have a crack at the others tomorrow. I'm having difficulties with both of them as well. If you want, you can post the points to which you have gotten to so we can see if that illuminates the problem any.

Victor Eremita

Wed 11 Feb, 2009 03:48 am
@unprocessed9,
1. P
-------------------
2. Q -> (P <-> Q)

3. ~(Q -> (P <-> Q)) (Assumption)
4. ~(~Q V (P <-> Q)) (Implication)
5. Q ^ ~(P <-> Q) (De Morgan's)
6. Q (From 5, Simplification)
7. ~(P <-> Q) (From 5, Simplification)
8. ~((P ^ Q) V (~P ^ ~Q)) (From 7, Equivalence)
9. ~(P ^ Q) ^ ~(~P ^ ~Q)) (From 8, De Morgan's)
10. ~P V ~Q (From 9, Simplication, De Morgan's)
11. ~P (From 6 and 10, Disjunction)
12. P ^ ~P (From 1 and 11, Conjunction)

Therefore
2. Q -> (P <-> Q)

1. P V (Q V R)
-------------------
2. Q V (P V R)

3. ~(Q V (P V R)) (Assumption)
4. ~Q ^ ~(P V R) (De Morgan's)
5. ~Q (From 4, Simplification)
6. ~(P V R) (From 4, Simplification)
7. ~P ^ ~R (From 6, De Morgan's)
8. ~R (From 7, Simplification)
9. ~P (From 7, Simplification)
10. Q V R (From 1 and 9, Disjunction)
11. Q (From 8 and 10, Disjunction)
12. Q ^ ~Q (From 5 and 11, Conjunction)

Therefore
Q V (P V R)

I'm not sure if you can use De Morgan's, but I'll be damned if I couldn't use it.

nerdfiles

Wed 11 Feb, 2009 09:17 am
@unprocessed9,
P v Q : (P v R) -> (P v(Q & R))

1. PvQ | Premise
2. PvR | Provisional Assumption
3. -P > R | Arrow Rule, 2
4. -P > Q | Arrow Rule, 1
5. -(Pv(Q&R)) | Provisional Assumption
6. -P & -(Q&R) | DeMorgan's Law, 5
7. -P | Conj. Out, 6
8. R | Modus Ponens, 3, 7
9. Q | Modus Ponens, 4, 7
10. -(Q&R) | Conj. Out, 6
11. Q&R | Conj. In, 8, 9
12. -(Q&R) & (Q&R). | Conj. In, 10, 11
13. Pv(Q&R) | Indirect proof, 5-12
14. Therefore, (PvR) > (Pv(Q&R)) | Conditional proof, 2-13

P : Q -> (P <->Q)

1. P | Premise
2. Q | Provisional Assumption
3. P | Provisional Assumption
4. Q | Copy Provisional Assumption (Q)
5. P > Q | Conditional Proof
6. Q | Provisional Assumption
7. P | Copy Premise (P)
8. Q > P | Conditional proof
9. P <> Q | Conjunction IN, 5, 8
10. Q > (P <> Q) | Conditional Proof

P v (Q v R) : Q v (P v R)

Ew, I've always hated this one. Doing it the "primitive" way is a nightmare. In fact, just about any "OR"-centered argument is a tedious task to prove.

1. P v ( Q v R) | Premise
2. -P > (Q v R) | Arrow, 1
3. -P > (-Q > R) | Arrow, 2
4. -Q & -(P v R) | Provisional Assumption
5. -Q & (-P & -R) | DeMorgan's, 4
6. -Q | Conj Out, 5
7. -P & -R | Conj. Out, 5
8. -P | Conj. Out, 7
9. -R | Conj. Out, 7
10. -Q > R | Modus Ponens, 3, 8
11. R | Modus Ponens, 10, 6
11. R & -R | Conj In11, 9
13. -(-Q & -(P v R)) | Indirect proof/reductio ad absurdum, 4-11
14. Therefore, Q v (P v R) | DeMorgan's, 13

If you can't use derived rules or if you're using some conservative/restrictive/artificial system imposed by your professor for "educational"/"academic" purposes, sorry.

Basically, every "rule" or "law" means the formula from which the subsequent formula was derived is logically equivalent with that derived formula. Derived rules take two logically equivalent formulas and permit you to interchange them.

VideCorSpoon

Wed 11 Feb, 2009 09:25 am
@unprocessed9,
Nerdfiles, on problem 2, are you using nested proofs without discharging them?

EDIT: It's nice to see a logic thread buzzing with activity again! Thanks guys!

nerdfiles

Wed 11 Feb, 2009 09:41 am
@unprocessed9,
ViceCorSpoon,

Well, I'm not quite sure what "discharging" means. Let me know if we're on the same page. It might just be the way I was taught.

Indirect Proof/Reduction is discharged once you find your contradiction. Conditional proof is discharged once you show that from the provisional assumption (which is the antecedent--the IF--in the IF...THEN...) you can get your consequent.

So for P > Q; P is the provisional assumption and Q is the consequent. But if Q is your premise (which is given), then you can just copy it. They're nested by the conditional proof and discharged so long as the consequent is accounted for.

VideCorSpoon

Wed 11 Feb, 2009 09:57 am
@nerdfiles,
Discharging as far as I was taught it has to be used for any provisional assumption you make. If you cite a provisional assumption, you have to discharge it before you can finish the proof. From what I see in your problem # 2, you indent for premise, provisional assumption, and another provisional assumption which requires at least three lines to discharge before the conclusion.

It probably is the way we were taught it. I am only familiar with three systems of propositional logic (authors Herrick, Prospesel, and Bergmann) all of which are greatly different from each other.

Your Indirect Proof/Reduction is to me just plain Indirect proof. The way I was taught it, to prove P, assume ~P, derive a contradiction, end indentation and assert P. But I think we have the same conception.

For conditional proof, your ultimate P-->Q is done by indenting, assuming P, derive Q, end indentation and assert P -->Q. But in this as well, I think we have the same conception. Also, thank you for elaborating on the nature of the antecedent in a conditional.

My main issue is the fact that for any assumed premise, it initiates its own proof that has to be accounted for, otherwise it becomes axiomatic.

nerdfiles

Wed 11 Feb, 2009 10:13 am
@unprocessed9,
I'm only familiar with Prospesel, and even then, I haven't played around with propositional logic in a while. By the way, I hope I didn't come off as condescending with that stuff about the antecedent. When I do explanations in logic, I tend to explain obvious concepts primarily for my own purpose (I use my explanation as a kind of marker for not glossing over things).

I admit, the "copy" rule I used seems a bit "magical." Or perhaps "axiomatic." I was taught this rule from Dr. James Garson. From those provisional assumptions in the conditional proof, it doesn't really look like anything is being proved. I admit, it looks a bit mysterious. It kind of makes it look as though one is merely "going through the motions" of logic. It's almost a vacuous use of conditional proof. I'm not sure if it's an invalid move, though.

It seems right that the nature of conditional proof only requires that one assume the antecedent of the conditional and "account for" the consequent. I said "from the provisional assumption you can get your consequent" which can be misleading because one is not technically getting the consequent from the provisional assumption. The consequent is pretty much just hanging out in the "premises" lounge.

However, my professor argues that so long as your copied premise is not within the nest itself, it's fine to copy it.

So, if

Premise
Premise
Provisional Assumption
Nest {
Antecedent/Provisional Assumption
Consequent*
}
Conditional Proof

It would be fine to take one of the preceding outside premises and simply copy them to the * location. It's essential, of course, that the premise be logically outside the nest. So, you couldn't just assume another provisional or premise. Since you're not assuming your premises that are outside the nest (they're already given by broader proofs or the argument itself), then they're kosher. Admittedly, this is a vacuous use of conditional proof, but I think it not invalid, just awkward and rather useless.

A dog is an animal. | Premise
It is raining. | Provisional Assumption
A dog is an animal. | Copied premise*
If it is raining, then a dog is an animal. | Conditional proof

This is likely what you're concerned with. It doesn't follow from the provisional assumption that a dog is an animal. However, "a dog is an animal" was your given premise anyway (presuming its truth, for our logical purposes). So it doesn't so much show the invalidity in the proof. It just shows that the proof was pretty much unnecessary anyway.

Perhaps we should ban copy? Heh.

nerdfiles

Wed 11 Feb, 2009 10:25 am
@unprocessed9,
But check this out. The rain/dog argument in symbol form.

P | Premise
Q & -P | Provisional assumption
-P | Conj out
P&-P | Conj in
-(Q & -P) | Indirect proof
Q > P | Arrow rule

Also, if you need me to prove any rules (such as Arrow) I'd be more than willing.

VideCorSpoon

Wed 11 Feb, 2009 10:48 am
@nerdfiles,

VideCorSpoon

Wed 11 Feb, 2009 10:54 am
@unprocessed9,
In regards to the proof in post #9, I don't follow how line #5 is derived. It seems to me there are a few missing derivations, inferences, and replacements missing.

nerdfiles

Wed 11 Feb, 2009 05:54 pm
@unprocessed9,
Had class, my apologies; coincidentally that class was logic. Anyway...adding a visual element may help.

| 1. P | Premise
|---------------------------- (start the indirect proof)
| 2. Q & -P | Provisional assumption (really, this is --(Q & -P), but double negation gives us what is at 2)
| 3. -P | Conj out (from 2)
| 4. P&-P | Conj in (from 1 and 3)
|---------------------
| 5. -(Q & -P) | Indirect proof, 2-4
| 6. Q > P | Arrow rule, 5

I took a shortcut. But the provisional assumption at 2 is the provisional assumption for 5. So I assumed 5's negation and got a contradiction from the premise at 1 and the right conjunct in 2.

nerdfiles

Wed 11 Feb, 2009 06:18 pm
@VideCorSpoon,
VideCorSpoon;47992 wrote:

When I hinted at the truth of the premise, I did not at all mean to say that we, as logicians, are actually concerned with the truth of the premise. All I meant is that if true, we'd nevertheless have a peculiar use of the conditional proof by way of the copy rule.

I am highlighting the peculiarity of the rules, not so much the assumption of truth. The rule is still odd even when we symbolize. And we can certainly run the all the combinatorial possibles on the truth table. The row on the truth table that has the premise listed as "T" will nevertheless leave us wondering, "Is the copy rule even valid? Nothing about dog's being animals follows from it raining outside."

We can suppose the premise true not in the sense that we wish to talk about the actual state of affairs. We can suppose the premise true because if we want to do the truth table, that would be one of the rows...where the premise is true. We don't have to "suppose it" so much as its merely one of the possibilities. Plus, we could take any actual true state of affairs (where the premises become necessarily true or a fact about the past), and we'd still end up with an awkward logical procedure (the copy rule combined with the conditional proof in just the way I've demonstrated).

1. Philosophy Forum
2. » Logic
3. » Help with a few propositional logic proofs