[TechSyndrome]

Hi. I've been given a question where I need to transform a Formula into a disjunctive normal form (DNF) using the Rewrite rules (inserted below):

Formula:

1. (P ∨¬R) → ¬(¬Q ∨ R)

Rewrite rules to obtain a disjunctive normal form (DNF):

1. F → G → ¬F ∨ G

2. F ↔ G → (F → G) ∧ (G → F)

3. ¬(F ∨ G) → ¬F ∧ ¬G

4. ¬(F ∧ G) → ¬F ∨ ¬G

5. ¬¬F → F

6. F∧(G ∨ H) → (F ∧ G) ∨ (F ∧ H) % DNF

7. (F ∨ G) ∧ H → (F ∧ H) ∨ (G ∧ H) % DNF

I am having problems applying the rewrite rules to the given formula. In the rules, I can't see a rewrite rule equivalent to the first part of the given formula, "P or not R" 1. (P ∨¬R) → ¬(¬Q ∨ R).

Can someone point me to where I am going wrong? It's clear I'm having problems starting the rewrite, but if I can do that I'm confident that the rest will be a lot easier.

This post has been edited by TechSyndrome: 08 July 2012 - 04:33 PM

[sepp2k]

You should start by applying a rewrite rule (the first one) to the whole term - not a subterm. Once you've applied that, you should end up with something where you can see how to work with it further.

PS: Note that the term "P or not R" on its own already is in CNF.

[TechSyndrome]

sepp2k, on 08 July 2012 - 04:31 PM, said:

You should start by applying a rewrite rule (the first one) to the whole term - not a subterm. Once you've applied that, you should end up with something where you can see how to work with it further.

PS: Note that the term "P or not R" on its own already is in CNF.

So for the first rewrite rule 1. F → G → ¬F ∨ G applied to the formula 1. (P ∨¬R) → ¬(¬Q ∨ R), would that result in (P → R) → ¬(Q → R)? If it's totally wrong, I'll explain my reasoning. The first part of the rewrite rule F → G is logically equivalent to ¬F ∨ G, therefore if we substitute those variables for P and Q, the second part of the given formula inside the parentheses not (¬Q ∨ R) is equivalent to ¬F ∨ G and I did that with the first part of the formula (P ∨¬R), but I switched the variables around. So for example this is what I did with the second part of the formula:

F → G → ¬F ∨ G
(¬Q ∨ R) → Q → R

Do you see how I switched it?

This post has been edited by TechSyndrome: 08 July 2012 - 04:54 PM

[sepp2k]

F and G in the rewrite rule don't correspond to P and Q, they correspond to (P ∨¬R) (the left side of ->) and ¬(¬Q ∨ R) (the right side of ->) respectively. Note that the placeholders in the rewrite rules can stand for any subexpression - not just single variables.

So the correct replacement would be "¬(P ∨¬R) ∨ ¬(¬Q ∨ R)". And from this you can hopefully see that one of the rewrite rules can now be applied both to "¬(P ∨¬R)" and to "¬(¬Q ∨ R)".

Anyway, I'm off to sleep now, so I hope you can figure the rest out without me.

[TechSyndrome]

sepp2k, on 08 July 2012 - 05:00 PM, said:

F and G in the rewrite rule don't correspond to P and Q, they correspond to (P ∨¬R) (the left side of ->) and ¬(¬Q ∨ R) (the right side of ->) respectively. Note that the placeholders in the rewrite rules can stand for any subexpression - not just single variables.

So the correct replacement would be "¬(P ∨¬R) ∨ ¬(¬Q ∨ R)". And from this you can hopefully see that one of the rewrite rules can now be applied both to "¬(P ∨¬R)" and to "¬(¬Q ∨ R)".

Anyway, I'm off to sleep now, so I hope you can figure the rest out without me.

Thank you very much for your help. I appreciate it. Ok, I tried to figure it out, but I couldn't. I know I'll get it because this has happened with everything in Propositional Logic so far.

I'm having a look at the solutions to see if I can get my understanding from that:

Solutions

(P ∨ ¬R) → ¬(¬Q ∨ R) =⇒ ( replacing → with ∨)
¬(P ∨ ¬R) ∨ ¬(¬Q ∨ R) =⇒ (De Morgan’s laws)
(¬P ∧ ¬¬R) ∨ (¬¬Q ∧ ¬R) =⇒ (removing double negations)
(¬P ∧ R) ∨ (Q ∧ ¬R) (DNF)

I am trying to understand what rule the first line corresponds to. Can you tell me why the implication sign is replaced with a disjunction sign? I feel there is something elementary I am missing in my understanding but I can't pin point. I'm still looking through different resources to find out where.

[sepp2k]

The implication is replaced with a disjunction because that's what the first rewrite rule does: It replaces -> with v and adds a negation in front of the left term (the comment doesn't mention the negation, but if you look at the second line, you see that a negation has indeed been added).

[TechSyndrome]

sepp2k, on 09 July 2012 - 01:29 PM, said:

The implication is replaced with a disjunction because that's what the first rewrite rule does: It replaces -> with v and adds a negation in front of the left term (the comment doesn't mention the negation, but if you look at the second line, you see that a negation has indeed been added).

So, for example, we start with the given formula, (P ∨¬R) → ¬(¬Q ∨ R, on the first line and apply the first rewrite rule on the second line.

The first rewrite rules shows that F → G is equivalent to ¬F ∨ G i.e. implication on the left hand-side of the rewrite rule is replaced with disjunction symbol, ∨, on the right-hand side of the rewrite rule, and then a negation is added on the left-hand side.

Did I just say exactly what you said?

This post has been edited by TechSyndrome: 09 July 2012 - 01:49 PM

[sepp2k]

Yes, that's right.

[TechSyndrome]

sepp2k, on 09 July 2012 - 01:54 PM, said:

Yes, that's right.

Ok, thanks, so do I need to go on to the second rewrite rule now?

[sepp2k]

The second rule is "F ↔ G → (F → G) ∧ (G → F)". Since your formula doesn't actually contain a ↔ anywhere, that rule can't possibly apply.

[TechSyndrome]

sepp2k, on 09 July 2012 - 02:11 PM, said:

The second rule is "F ↔ G → (F → G) ∧ (G → F)". Since your formula doesn't actually contain a ↔ anywhere, that rule can't possibly apply.

Thank you. Can you tell me whether my English reading of the first rewrite rule is correct as I have had to go back to it. I don't want to leave it until I have completely comfortable with it (although I'm not trying to imply that I expect you to help me).

My Interpretation

The first rewrite rule says, "wherever there is a disjunction symbol in the middle, replace it with an implication symbol, and vice versa".

And it also says, "add a negation symbol to the left side of the formula".

I'm sorry if I'm repeating myself, I think I haven't, but if I have, again I apologise.

This post has been edited by TechSyndrome: 09 July 2012 - 02:25 PM

[sepp2k]

It doesn't say "vice versa". The rewrite rules are only meant to be applied in one direction, i.e. you replace the pattern on the left side of the red -> with the pattern on the right side - never the other way around. If it were meant to be used in both directions, it would be a red <->, not ->.

I mean, it is logically valid to apply the rules in both directions. But only one of the directions will move you in the direction of the DNF. If you replace the right side with the left, you'll move away from the DNF. So if the goal is to get to the DNF, the rules need to be applied left-to-right.

Other than that, your interpretation looks fine.

[TechSyndrome]

sepp2k, on 09 July 2012 - 02:32 PM, said:

It doesn't say "vice versa". The rewrite rules are only meant to be applied in one direction, i.e. you replace the pattern on the left side of the red -> with the pattern on the right side - never the other way around. If it were meant to be used in both directions, it would be a red <->, not ->.

I mean, it is logically valid to apply the rules in both directions. But only one of the directions will move you in the direction of the DNF. If you replace the right side with the left, you'll move away from the DNF. So if the goal is to get to the DNF, the rules need to be applied left-to-right.

Other than that, your interpretation looks fine.

One of the problems I have with that is that the negation on the right hand-side pattern of the first rewrite rule is not in parentheses, so I was tempted to put the negation symbol INSIDE the parentheses. Is that not what should have happened?

So, I would have written this:
¬(P ∨ ¬R) ∨ ¬(¬Q ∨ R) =⇒ (De Morgan’s laws)

as

(¬P ∨ ¬R) ∨ ¬(¬Q ∨ R) =⇒ (De Morgan’s laws)

This post has been edited by TechSyndrome: 09 July 2012 - 02:41 PM

[sepp2k]

When you do that the negation only applies to P, but that's not correct. It should apply to the whole term "P ∨ ¬R".

The proper way to think about this is that in the pattern F -> G, the F stands for (P ∨ ¬R) and the G for ¬(¬Q ∨ R). Since the negation in the replacement pattern is applied to F, you need to apply it to the whole term (P ∨ ¬R).

[TechSyndrome]

sepp2k, on 09 July 2012 - 02:49 PM, said:

When you do that the negation only applies to P, but that's not correct. It should apply to the whole term "P ∨ ¬R".

The proper way to think about this is that in the pattern F -> G, the F stands for (P ∨ ¬R) and the G for ¬(¬Q ∨ R). Since the negation in the replacement pattern is applied to F, you need to apply it to the whole term (P ∨ ¬R).

Thank you. I've done it on paper - does this look right?

Because nothing happens on the G side of the replacement, I don't do anything to the G side of the replacement?

This post has been edited by TechSyndrome: 09 July 2012 - 03:18 PM