Exercise 1: Question 2-part a

Question

I have a query regarding this task:
Convert to CNF:

!((b|b<->a&a)|(!a->c))

Here, my query is since, there are no brackets in this term:
(b|b<->a&a)

So, I am confused whether I should do equivalence operation on this part:
b<->a, considering, I will put brackets myself there.
(b| (b<->a) &a)

Or should I put brackets like this: ( (b|b) <-> (a&a) )

I have already submitted this task using the method of truth table. But, that can be very long method in exams, if there are 4-5 variables. Hence, I will prefer solving this with algorithm.

Any assistance in this questions is highly appreciated.

Thank you!

Answer 1

When I'm wondering how to evaluate a formula, I give the original formula and the variants to our teaching tool. Then I get a truth table:

a	b	b|b<->a&a	(b|b)<->(a&a)	b|(b<->a)&a
0	0	1	1	0
0	1	0	0	1
1	0	0	0	0
1	1	1	1	1

 The third variant differs from the others. Apparently, (b|b)<->(a&a) is the right way to read the formula. This is quite fortunate, as one can now simplify it to b<->a.

Answer 2

On page 5 of the chapter on propositional logic, you find also the preference rules of the operators: 

Answer 3

Thank you for your answers. I have been able to solve the question.

Attached is the solution, it might help someone.

Comments

But would the following not be a simpler computation?

    !((b|b<->a&a)|(!a->c))
    = !((b<->a)|(!a->c))
    = (!b<->a)&(!a&!c)
    = (!b->a) & (a ->!b) & !a & !c
    = (b|a) & (!a|!b) & !a & !c
    = b & !a & !c

or even

    !((b|b<->a&a)|(!a->c))
    = !((b<->a)|(!a->c))
    = (!b<->a)&(!a&!c)
    = (b<->!a) & !a & !c
    = b & !a & !c

Note that in a formula like "a & phi" you can replace all occurrences of a in phi by true, and in a formula like "!a & phi" you can replace all occurrences of a in phi by false. That often simplifies formulas a lot and safes a lot of work.

---

Hi, this is good, thanks but doesn't the order of operations matter here? like first solving equivalence and then moving negation inside, but here you didn't follow that (I guess because of the precedence), secondly, the third step, what property is that and how can we know about other rules like you mentioned in the last (setting a to true), TIA.

---

Hi KS,
Thank you for your reply.
I have a question:
If I do like this and follow the algorithm, can you please confirm, what am I doing wrong?

    !((b|b<->a&a)|(!a->c))
    = !((b<->a)|(!a->c))
    = !((b|!a) & (!b|a) | (a|c))
    = ((!b&a) | (b&!a)) & !a&!c)
    = ((!b&a | b) & (!b&a | !a)) & !a&!c)
    = (b| !b) & (b|a) & (!a|!b) & (!a|a) & !a&!c



Thank you!

---

Well, as long as operations are correct, you can apply them. However, you have to make sure that your work will terminate, e.g., you should not reintroduce operators that you have removed before. So, yes, the order of operations has to be considered carefully. What I did above is however okay in that sense.

Where to find these tricks? That is difficult to answer in general, but most of these are given in Boolean algebra like the absorption law etc. To simplify something like  "a & phi" you may also consider its Shannon decomposition: (a ? 1&phi[a=1] : 0&phi[a=0]) and here you quickly see that this boils down to (a ? phi[a=1] : 0) which means a & phi[a=1]. Same you can do for "!a & phi".

At the end, I admit, you need some practice and experience. That's why we need the exercises to make you see such things.

---

I don't see any mistake in the following:

    !((b|b<->a&a)|(!a->c))
    = !((b<->a)|(!a->c))
    = !((b|!a) & (!b|a) | (a|c))
    = ((!b&a) | (b&!a)) & !a&!c)
    = ((!b&a | b) & (!b&a | !a)) & !a&!c)
    = (b| !b) & (b|a) & (!a|!b) & (!a|a) & !a&!c
    
Even though that is already a CNF at the end, you may continue with simplifications

   = (b| !b) & (b|a) & (!a|!b) & (!a|a) & !a & !c
   = (b|a) & (!a|!b) & !a & !c
   = (b|false) & (true|!b) & !a & !c
   = b & !a & !c

Note CNF is not canonical. There are typically many solutions unless further restrictions are imposed.

---

Hi KS,
Thank you so much for all the answers.
Really appreciate your assistance!

---

I have another idea how you can compute CNF and also DFN efficiently. You may simply use the Shannon decomposition

  * phi = a & phi[a=1] | !a&phi[a=0]   for producing DNF
  * phi = (!a | phi[a=1]) & (a|phi[a=0])   for producing CNF

in your example, this would work as follows:

    !((b|b<->a&a)|(!a->c))
    = !((b<->a)|(!a->c))
    = a & !((b<->true)|(!true->c)) | !a & !((b<->false)|(!false->c))
    = a & !(b|(false->c)) | !a & !(!b|c)
    = a & false | !a & !(!b|c)
    = !a&b&!c

All you need here are the Shannon decompositions and the propagation of boolean constants.