4 Replies - 1621 Views - Last Post: 02 June 2012 - 10:53 AM

#1 TechSyndrome  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 3
  • View blog
  • Posts: 135
  • Joined: 06-May 12

Decomposition Tree - How to simplify?

Posted 01 June 2012 - 11:41 AM

Hello. I've hit a wall in understanding this part of Logic, called Syntactic Decomposition Tree. Here is the image of the tree that I am looking at from my lecture slides:

Posted Image

I'll try my best to explain what I've understood of it so far, and at each step I'll ask a question (marked in blue) just so you guy can understand my thought process.

Ok, first the expression (P ∧ (Q ∨ R)) → ((Q ↔ R)) is split into two branches P ∧ (Q ∨ R) and (Q ↔ R) and the parentheses are removed. Q1: Why are the parentheses removed?

Ok, next, now that the two expressions have been split, I noticed stuff going on in the left and right tree. Ok, starting with the left. Ok the auxiliary symbol "→" which was in between the two expressions has now disappeared. I understand that you won't really be able to branch them separately unless you remove it as the "→" doesn't belong to either expression. But, just incase my assumption is wrong, I'm going to ask the question. Q2: Why has the "→" been removed?

Ok, now we start with the left expression P ∧ (Q ∨ R). Remove the conjunction ∧, as it doesn't belong to either expression. The left side of the expression, P, is branched out to the left, and the right side of the expression, (Q ∨ R), is branched out the right. They've now been separated, so P is reduced to P (for some reason the auxiliary symbol has been removed), and on the right branch, the auxiliary symbol from Q ∨ R has been separated as it doesn't belong to either expression, so we're left with Q and R. Everything down to its simplest form.

Ok, now for the tree on the right branch. Parentheses are removed. Then, for some reason one of the auxiliary symbol is removed from the expression, and the same expression is repeated below with one less . Q3: Why has one of the symbols been removed from the expression, and why from the left hand side. Is there a rule which says remove auxiliary symbols outside the parentheses first, one by one? Ok, next the parentheses are removed and it is reduced to Q ↔ R. The implication symbol ↔ is removed as it doesn't belong to either expression and we're left with Q R. The only way we can simplify it further is by removing the negation symbol from R which leaves just R. As Q has already been reduced to its simplest form, we cannot reduce it any further.

Ok, the tree on the FAR right shows the tree in its simplest form. For some reason, the auxiliary symbols which I said were removed, were not actually removed at all!!! Instead, they were "sleeping" in a chamber, giving me space to simplify the rest of the expression. Once I have the simplified versions of the P, Q and R on the left branch, and the Q and R on the right branch, it's just a case of "awakening" those auxiliary symbols.

I've just done it on a white board and it looks like I've answered my own question by asking questions. Q4: But, surely, I'm over-complicating things? Q4 (part 2): There must be a quicker and simpler way of doing this? Does anyone know how?

Is This A Good Question/Topic? 0
  • +

Replies To: Decomposition Tree - How to simplify?

#2 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2117
  • View blog
  • Posts: 3,242
  • Joined: 21-June 11

Re: Decomposition Tree - How to simplify?

Posted 01 June 2012 - 12:24 PM

Q1: If you only consider only the expression (P ∧ (Q ∨ R)), the parentheses are not needed. You can just write "P ∧ (Q ∨ R)" without any ambiguity. Basically there's never a reason to surround a whole expression with parentheses.

Q2: That's one way to look at it. An alternative way would be like this:

Your goal is to build the tree that's shown at the right side of the image. To that end you need to decide at which place (or "sleeping chamber") in the tree to store each part of the expression. Once you've decided where a certain piece goes, you no longer need to look at it. Since the -> is the outermost operator (i.e. the only one not inside any parentheses), it will be the root node of the tree. And its left and right side will be used to build the left and right subtrees of the tree. So since we now have decided that the -> goes at the root, we no longer need to look at it. We only need to look at the left and right subexpressions to decide which part of them goes inside which part of the left and right subtrees.

Q3: At each step we take one of the parts of the expression and store it in the result tree. In the first part we've stored the -> operator. In this step we store the not-operator. Like the -> operator we no longer look at it after storing it in the tree.
Was This Post Helpful? 1
  • +
  • -

#3 TechSyndrome  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 3
  • View blog
  • Posts: 135
  • Joined: 06-May 12

Re: Decomposition Tree - How to simplify?

Posted 01 June 2012 - 12:52 PM

View Postsepp2k, on 01 June 2012 - 12:24 PM, said:

Q1: If you only consider only the expression (P ∧ (Q ∨ R)), the parentheses are not needed. You can just write "P ∧ (Q ∨ R)" without any ambiguity. Basically there's never a reason to surround a whole expression with parentheses.

Q2: That's one way to look at it. An alternative way would be like this:

Your goal is to build the tree that's shown at the right side of the image. To that end you need to decide at which place (or "sleeping chamber") in the tree to store each part of the expression. Once you've decided where a certain piece goes, you no longer need to look at it. Since the -> is the outermost operator (i.e. the only one not inside any parentheses), it will be the root node of the tree. And its left and right side will be used to build the left and right subtrees of the tree. So since we now have decided that the -> goes at the root, we no longer need to look at it. We only need to look at the left and right subexpressions to decide which part of them goes inside which part of the left and right subtrees.

Q3: At each step we take one of the parts of the expression and store it in the result tree. In the first part we've stored the -> operator. In this step we store the not-operator. Like the -> operator we no longer look at it after storing it in the tree.


Hi, thank you for your reply. The problem is, I don't know how the question would be made. Would I just be given the expression (P ∧ (Q ∨ R)) → ((Q ↔ R)), and then told to simply this expression? Or, is it likely that I would be given the tree at the right side of the image first (as Q2 of your answer implied)? I thought that's what I had to make. I hope I have been able to express my point, and also hope I understood your answer.
Was This Post Helpful? 0
  • +
  • -

#4 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2117
  • View blog
  • Posts: 3,242
  • Joined: 21-June 11

Re: Decomposition Tree - How to simplify?

Posted 01 June 2012 - 12:59 PM

View PostTechSyndrome, on 01 June 2012 - 09:52 PM, said:

Hi, thank you for your reply. The problem is, I don't know how the question would be made. Would I just be given the expression (P ∧ (Q ∨ R)) → ((Q ↔ R)), and then told to simply this expression?


You're question is missing a verb. But yes, you'd be given the expression and you'd be told to create the tree on the right side (I imagine).

Quote

Or, is it likely that I would be given the tree at the right side of the image first (as Q2 of your answer implied)?


I didn't mean to imply that. You'd probably be given the expression and be told to create the tree on the right side of the image. It's not entirely impossible that you'd be given the tree and be told to write down the expression, but that seems somewhat less likely.

Quote

I thought that's what I had to make.


No, you're right. I think you misunderstood my answer to Q2.
Was This Post Helpful? 2
  • +
  • -

#5 TechSyndrome  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 3
  • View blog
  • Posts: 135
  • Joined: 06-May 12

Re: Decomposition Tree - How to simplify?

Posted 02 June 2012 - 10:53 AM

View Postsepp2k, on 01 June 2012 - 12:59 PM, said:

View PostTechSyndrome, on 01 June 2012 - 09:52 PM, said:

Hi, thank you for your reply. The problem is, I don't know how the question would be made. Would I just be given the expression (P ∧ (Q ∨ R)) → ((Q ↔ R)), and then told to simply this expression?


You're question is missing a verb. But yes, you'd be given the expression and you'd be told to create the tree on the right side (I imagine).

Quote

Or, is it likely that I would be given the tree at the right side of the image first (as Q2 of your answer implied)?


I didn't mean to imply that. You'd probably be given the expression and be told to create the tree on the right side of the image. It's not entirely impossible that you'd be given the tree and be told to write down the expression, but that seems somewhat less likely.

Quote

I thought that's what I had to make.


No, you're right. I think you misunderstood my answer to Q2.


I think I understand it now. Thank you.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1