Thread: [SOLVED] Stuck in Proof of Laws of Syllogism and Absorption in Propositional Logic!

Hello everyone, great this forum exists, I was just getting so hopeless...

Well I am badly stuck with the following problem, both problems are from Rosen section 1.2, I can't continue any further and am only still in section 1.2.
Please help(Later I'll also post my steps towards solution, I would like to know what went wrong.)

1) Prove that following statement is a tautology

(A -> B) /\ (B -> C) -> (A -> C)

Prove without using Truth Tables.

2) A \/ (A /\ B) = A

Please help, I am badly stuck, specially had given a lot of time to the first one.

Thanx Angel White! Thanx a lot! But where are the references from! I mean Table references and page references! Is it from Rosen itself.?

Originally Posted by natarajchakraborty

Thanx Angel White! Thanx a lot! But where are the references from! I mean Table references and page references! Is it from Rosen itself.?

they are from Rosen's Discrete Mathematics and it's applications 6th edition. I assumed we were using the same book. I can scan the pages for you if we are not, I expect you should have something similiar in your book. Also, if you have a rule called the "chain rule" in yours, you can skip the majority of the steps I did and do

(A -> B) /\ (B -> C) -> (A -> C)

= (A->C)->(A->C)

= ~(A -> C) V (A -> C)

= T

Edit: I have done something wrong in my proof, I am looking it over now.

angel.white Thanx again for the clarification:

Unfortunately I am using Rosen 4th Edition,

anyways that version difference does not much matters if I understand it :

But I am having some doubts:

My derivation would go like this

(A -> B) /\ (B -> C) -> (A -> C)

~[(~A V B) /\ (~B V C)] V (A -> C)
[~(~A V B) V ~(~B V C)] V (A -> C)
[(A /\ ~B) V (B /\ ~C)] V (A -> C)

Here on I get AND in the statement and thus on distributing it further it gets very complicated leading me no where.
Where am I wrong here?


Also I don't have that chain rule in any table, could you please mention it here.

About absorption law Table 6 mention in my version of my book something else, and no where it does mentions any absorption law in fact full question is following:

Prove:
a) [p V (p /\ q)] <=> p
b) [p /\ (p V q)] <=> p

Thus I have to prov both of them, I can;t use one for the other until I first prove the first one.


Thanx a lot man for the help....

Okay, I am not sure how to fix the first proof, but it is wrong, do not use it.

(A->B) ^ (B->C)

is equivalent to (A->C)

unfortunately Rosen doesn't give me much to work with to prove this (since we can't use a truth table, and I'm assuming you can't use hypothetical syllogism from 1.6, which is what we called the "chain rule" in my logic class).

If we were doing logic, we could use an assumption, where you assume A, which gives you B with modus ponens, which gives you C with modus ponens. So if A then C. But I don't know how to prove it with the tools Rosen has given.

If anyone else can prove (A->B) ^ (B->C) using only the attached tables, I would appreciate the aid.

Originally Posted by natarajchakraborty

In the second line how you are converting the implication to OR without negating the left hand proposition?

No, my proof was wrong, I have removed it.

Can you tell me what tools you have available to you in 1.1 - 1.2? Without truth tables, hypothetical syllogism, and assumption (I don't know what Rosen calls assumptions, if he uses it at all), I do not know how to prove this. Perhaps some of those tools are available to me but I do not realize it due to version differences, or perhaps someone more capable than I will be able to prove it using only the tables I have attached.

Thanx for the tables Man... Huh I realize my book is too old, well I will keep on trying with these new tables.... and I also realize I pretty poor in Logic.... I need a detailed course....


Thanx again for the help Angel White

[IMG]file:///C:/DOCUME%7E1/nataraj/LOCALS%7E1/Temp/moz-screenshot.jpg[/IMG][IMG]file:///C:/DOCUME%7E1/nataraj/LOCALS%7E1/Temp/moz-screenshot-1.jpg[/IMG][IMG]file:///C:/DOCUME%7E1/nataraj/LOCALS%7E1/Temp/moz-screenshot-2.jpg[/IMG]I have attached all the tables found in section 1.2

In fact there are nones in section 1.1 and mainly it deals with logical puzzles and inconsistency I enjoyed solving those problems and was very excited... but....

With your tables I guess we can go a bit further... I'll post them here...

I don't see hypothetical syllogism in section 1.1 and 1.2 (In fact I still don't know what it is!)
but it's okay if you can prove it by using your own tools.... I will refer to other resources......

Thanx again...

I was just wandering Angle White! Is the same question removed from the exercises of Rosen of section 1.2 in 6th Edition of the book. In my book, its there as question no 8, b) where he asks to prove this with truth table, and in question number 9 he asks each of the proposition of question no 8 to be proved tautology without using truth tables.

Originally Posted by natarajchakraborty

I don't see hypothetical syllogism in section 1.1 and 1.2 (In fact I still don't know what it is!)
but it's okay if you can prove it by using your own tools.... I will refer to other resources......

Thanx again...

Okay, I can prove it in my own words

First, let us examine the antecedent as it's own proposition:

1. (A -> B) ^ (B -> C)

This is saying that these two are true, which means that each must be true individually, using simplification we break the and statement into it's component parts.

2. A->B ...by simplification
3. B->C ...by simplification

Now let us assume that A is true and see what this would mean. We place an "a" in front of the step number to show that this is an assumption, it is true only if the assumption is true where steps without the "a" are true always. We cannot mix these steps after we finish assuming A is true, that is why we mark them.

a4. A ...assumption

Because A is true, and we know that if A is true, then B is true, we know B must be true. This is called modus ponens.

a5. B ...modus ponens of 2 and 4
a6. C ...modus ponens of 3 and 5

So now we know that when we assume A is true, C must be true as well. But we don't actually know that A is true, so we must place it into a conditional statement

7. A->C ...conditional proof steps 4-6

-----

Okay, now that we know when (A -> B) ^ (B -> C) is true, A->C is also true. Let us name this "hypothetical syllogism" (we called it "chain rule" in my logic class) meaning that if the antecedent (the "then" part) in one if-then statement is the same as the consequent (the "if" part) in another if-then statement, then we can consolidate the statements as we have.

Now let us examine Rosen's tautology.

1. (A -> B) ^ (B -> C) -> (A->C)

we know that if the antecedent is true, then A->C must be true, that is what we just proved up above. So we can replace them.

2. (A->C) -> (A->C) ...hypothetical syllogism

3. ~(A->C) V (A->C) ...logical equivalence (this is the first step on table 7 that I attached, I can go into more detail about it if you like. If you have a hard time seeing it, replace A->C with a single character, and examine the step again, it should be more obvious)

And this statement is saying that A->C is either not true, or it is true. This is a tautology, because it can only be true or false, and both of these options will make the (or) statement true.

4. T ...Negation laws (Table 6 that I attached in the last post)



Okay, so that is how I would explain it in my own words, I don't know what Rosen wanted you to do, it may be possible to prove it using the tools that he provided, but I seemed to keep getting stuck when I tried. If this is for your own edification, and you understand it, then thats probably good enough (up to you, I suppose, you'll get at least two more opportunities to revisit logic in this book, because set theory and boolean algebra are basically just alternative notations with simplified operators), but if it is for a course in school, your instructor may not accept it as it uses tools that Rosen hasn't taught yet.

Thanx Angle White! Thanx a lot! Atleast I have a prove. Its not for my homework, but for my own understanding, I am actually doing a self study! Great! Thanx a lot.
But I have another additional question related to this?

The rules you used, that is assumption and modus ponens etc. are not there in Rosen, why they are not there? I mean is it not the most basic of Logic, symbolic logic. Basically I never studied Logic in High School, so this is my first introduction, but I get surprised by the various ways the meterial is presented in various books and sites.

For ex.
a) Rosen don't have all these rules you used to do the derivation.
b) Schaum's outline in logic also don't have these rules, but they do have other things, about building the tree and branches to solve the logic problem.
c) While in another book I found they mentioned 12 rules similar to the ones you used.

So where I stand, do I need to start somewhere else.
I am confused by so many terms, not knowing their difference, like "Symbolic Logic", "Propositional Logic", "Predicate Logic" etc.

What are the differences and which is a good place to start considering no preveious background in Logic.

Thanx a lot

Nataraj

Originally Posted by natarajchakraborty

Thanx Angle White! Thanx a lot! Atleast I have a prove. Its not for my homework, but for my own understanding, I am actually doing a self study! Great! Thanx a lot.
But I have another additional question related to this?

The rules you used, that is assumption and modus ponens etc. are not there in Rosen, why they are not there? I mean is it not the most basic of Logic, symbolic logic. Basically I never studied Logic in High School, so this is my first introduction, but I get surprised by the various ways the meterial is presented in various books and sites.

For ex.
a) Rosen don't have all these rules you used to do the derivation.
b) Schaum's outline in logic also don't have these rules, but they do have other things, about building the tree and branches to solve the logic problem.
c) While in another book I found they mentioned 12 rules similar to the ones you used.

So where I stand, do I need to start somewhere else.
I am confused by so many terms, not knowing their difference, like "Symbolic Logic", "Propositional Logic", "Predicate Logic" etc.

What are the differences and which is a good place to start considering no preveious background in Logic.

Thanx a lot

Nataraj

I do not know the differences between those names, but my experience is that all logic courses are basically similar. My philosophy logic course had tools that the discrete mathematics course did not (we also focused more heavily on logical proofs in that class), but then varied towards how to use the logic in sentences and arguing. In Discrete math and other CS courses, it has been used to enhance understanding, ie sets make much more sense when you understand logic, creating circuits is essentially an exercise in basic logic (though they introduce some new operators, but these operators can be expressed through the operators you already know).

Some of what I talked about will be in Rosen's book in later sections, modus ponens will surely be in there, though I don't think the conditional proof (the assumption) will be, I don't remember it, at least.

Also, some courses differ in how they introduce the domain of the variable. In Rosen's course, you use quantifiers, in my logic class, we introduced a new variable.

For example, Rosen might say "for every x, if x is y then x is z" where x is defined as "all humans"

But in my philosophy course, we would say "if x is (a human) and x is y, then x is z"

I personally prefer Rosen's method, here, not only is it useful later on with what you will learn, but it seems to result in simpler notation (once you understand how it works, at least).

I think your logic will be fine with Rosen's book, he does a pretty good job, once you understand it, you will not need to reference the tables, if you practice it a little you will be able to see it (note that seeing it and proving it don't always go hand in hand). If your goal is to learn logic, it might be wiser to find a book which teaches logic specifically for the purpose of learning logic, whereas Rosen's book teaches it for the specific purpose of it's use in Mathematics. This different focus doesn't change the logic, but it does change how the material is presented, and what is emphasized. The nice thing about Rosen's book is that it does a good job of hitting logic in one chapter, I took logic as a philosophy course at the same time I took Discrete Mathematics 1, we hit that chapter and moved on in discrete math, while the philosophy course took the entire first half of the semester to cover it. In some ways it was nice, because the philosophy course was mostly review after that, but in other ways it was frustrating, because they used different notation and did somethings a little differently that kept messing me up.

If you're learning for your own benefit, I'll also suggest using a mix of notation, there are a number of ways to represent each operator, and I think some are easier to see than others. For example I always get confused when using \/ for or and /\ for and, that was part of my problem earlier, so when I do my own logic now (it is actually quite useful for daily life) I use a multiplication sign * to represent it, this is consistent with Boolean operators. I also prefer a tilde ~ for not, it is easier to get the proportions correct and takes less time to write. Sometimes I use a bar for not, also, which is also consistent with boolean operators, the nice thing about a bar is that it makes it very clear what is being negated, which is quite useful when you have nested negations.

Don't get too bogged down by Rosen's book, some chapters are a bit heavy, I found it helpful to keep it light, don't focus on learning every single thing absolutely thoroughly, but instead on getting a breadth of knowledge, being able to do most of the work, having general understanding. It is not always easy to tell what is important, but this approach seems to be more effective (for me at least, because otherwise my obsessiveness bogs me down and I never move on). The more you do in the book, and the more you use some of these things, the knowledge catches up nicely. Also, there is very little flow between chapters, meaning 1 and 2 aren't necessarily related, I think he has a hierarchy of what chapter's are required for what other chapters, but this allows you to skip around some if you are more interested in one over another. The other nice thing about chapters which are not directly related is that if you are frustrated with the chapter you are on, you know you only have to finish it before you will move on to other material. Also, the later chapters are much easier than the earlier chapters, so you have that to look forward to as well But then again, the later chapters are much more computer science oriented, while the earlier chapters are much more mathematically oriented, so depending on your goals, you may choose not to focus on the later chapters. At my school, Discrete Math 1 is both a Math and a CS course, but Discrete Math 2 is only a CS course.

Anyway, good luck!

Thanx for you such a detailed explanation Angel White! It was wonderful, thanx a lot again... as you say I'll continue with Rosen, and won't get bogged down... you are right there....

Thanx a lot.

Ha I proved it!
I think I was going in right direction but giving up too soon...
I should have continued expansion.....

T stands for true/ tautology

(A -> B) /\ (B -> C) -> (A -> C)

<=> ~[(~A V B) /\ (~B V C)] V (A -> C)
<=> [~(~A V B) V ~(~B V C)] V (A -> C)
<=> [(A /\ ~B) V (B /\ ~C)] V (A -> C)
<=> [(A /\ ~B) V (B /\ ~C)] V (~A V C)
<=> [{B V (A /\ ~B)} /\ {~C V (A /\ ~B)}] V (~A V C)
<=> [(B V A) /\ (B V ~B) /\ (~C V A) /\ (~C V ~B)] V (~A V C)
<=> [(B V A) /\ T /\ (~C V A) /\ (~C V ~B)] V (~A V C)
<=> [(B V A) /\ (~C V A) /\ (~C V ~B)] V (~A V C)
<=> [{~A V (B V A)} /\ {~A V (~C VA)} /\ {~A V (~C V ~B)}] V [{C V (B V A)} /\ {C V (~C V A)} /\ {C V (~C V ~B)}]
<=> [T /\ T /\ {~A V (~C V ~B)}] V [{C V (B V A)} /\ T /\ T]
<=> [~A V (~C V ~B)] V [C V (B V A)]
<=> ~A V (~C V ~B) V C V (B V A)
<=> ~A V ~C V ~B V C V B V A
<=> (~A V A) V (~B V B) V (~ C V C)
<=> T V T V T
<=> T
QED