Task 2: DNF

Question

Here is my approach of DNF, but at the end I received one AND, can you please give me a hint:

~(~a ∨ ((a -> b) <-> (b ∧ c)) )

~(~a ∨ ((~a ∨ b) <-> (b ∧ c)) )

~(~a ∨ [ {(~a ∨ b) ∧ (b ∧ c)} V {~(~a ∨ b) ∧ ~(b ∧ c)}  ])

~(~a ∨ [ {(~a ∨ b) ∧ (b ∧ c)} V {(a ∧ ~b) ∧ (~b V ~c)}  ])

~([~a ∨ {(~a ∨ b) ∧ (b ∧ c)}] V [~a V {(a ∧ ~b) ∧ (~b V ~c)} ])

~([{~a ∨ (~a ∨ b)} ∧ {~a V (b ∧ c)}] V [{~a V (a ∧ ~b)} ∧ {~a V (~b V ~c)} ])

~([{~a ∨ ~a ∨ b} ∧ {(~a V b) ∧ (~a V c)}] V [{(~a V a) ∧ (~a V ~b)} ∧ {~a V ~b V ~c)} ])

~([(~a ∨ b) ∧ (~a V b) ∧ (~a V c)] V [(~a V a) ∧ (~a V ~b) ∧ (~a V ~b V ~c) ])

[(a ∧ ~b) V (a ∧ ~b) V (a ∧ ~c)] ∧ [(a ∧ ~a) V (a ∧ b) V (a ∧ b ∧ c) ]

Answer 1

There seems to be a small typo in the last line:
[(a ∧ ¬b) V (a ∧ ¬b) V (a ∧ ¬c)] ∧ [(a ∧ ¬a) V (a ∧ b) V (a ∧ b ∧ c) ]
There might be other minor mistakes as well.

Let me give you three and a half options:

1. Brute Force: Multiplying out

Well. You could solve that with brute force by further multiplying out. Your last line is a conjunction of two DNF of three co-clauses each. If you multiply it out, each of the co-clauses of one of the two DNF will be conjuncted to each of the co-clauses of the other DNF.

1.5. Multiply out after simplifying

If you multiply out two DNF with three clauses, you get nine clauses that you then could simplify. You can save some work by multiplying out first.

[(a ∧ ¬b) V (a ∧ ¬b) V (a ∧ ¬c)] ∧ [(a ∧ ¬a) V (a ∧ b) V (a ∧ b ∧ c) ]

The DNF on the left contains the same co-clause twice. You can remove one occurrence.
The DNF on the right contains an unsatisfiable co-clause that can be removed, and a co-clause implying another one. The co-clause (a ∧ b ∧ c) contains the co-clause (a ∧ b)  syntactically, it implies it. This means that every assignment satisfying (a ∧ b ∧ c) also satisfies (a ∧ b) which is already covered. Hence, the formula shrinks to:

[(a ∧ ¬b) V (a ∧ ¬c)] ∧ [(a ∧ b) ]

From here, do the same thing as in option 1. but with much less co-clauses.

2. Use the CNF-form of ↔

The outer negation eventually negates your the subformula of the ↔-connective. You decided on the DNF version of ↔ (i.e. the two min-terms). Instead, you can use the CNF variant (i.e. A ↔B = (A → B) ∧ (B → A)).

3. Apply De-Morgan's rule earlier

In the end, it's the outer negation that ruins your day. How about applying De-Morgan earlier to get rid of the outer negation?

¬(¬a ∨ ((a → b) ↔ (b ∧ c)) )
(a ∧ ¬((a → b) ↔ (b ∧ c)) )
(a ∧ ((a → b) ⊕ (b ∧ c)) )
(a ∧ (¬(a → b) ∧ (b ∧ c)) ∨ ((a → b) ∧ ¬(b ∧ c)) )
…

Comments

Corrected the typo.

---

After applying De-Morgan's law, ended up with this:

~(~a ∨ ((a → b) ↔ (b ∧ c)) )
(a ∧ ~((a → b) ↔ (b ∧ c)) )
(a ∧ ((a → b) ⊕ (b ∧ c)) )
(a ∧ (~(a → b) ∧ (b ∧ c)) ∨ ((a → b) ∧ ~(b ∧ c)) )
(a ∧ (~(~a ∨ b) ∧ (b ∧ c)) ∨ ((~a ∨ b) ∧ ~(b ∧ c)) )
(a ∧ ((a ∧ ~b) ∧ (b ∧ c)) ∨ ((~a ∨ b) ∧ (~b ∨ ~c)) )
(a ∧ a ∧ ~b ∧ b ∧ c) ∨ ( a ∧ ((~a ∨ b) ∧ (~b ∨ ~c)) )

here,
a ∧ a = a
~b ∧ b = false
a ∧ false ∧ c = false

therefore,
false ∨ (a ∧ ((~a ∨ b) ∧ (~b ∨ ~c)) )
(a ∧ ((~a ∨ b) ∧ (~b ∨ ~c)) )
(a ∧ (~a ∨ b)) ∧ (a ∧ (~b ∨ ~c) )
((a ∧ ~a) ∨ (a ∧  b)) ∧ ((a ∧ ~b) ∨ (a ∧ ~c)) // a ∧ ~a = false
(a ∧  b) ∧ ((a ∧ ~b) ∨ (a ∧ ~c))
(a ∧  b ∧ a ∧ ~b) ∨ (a ∧  b ∧a ∧ ~c)
(a ∧  b ∧ a ∧ ~b) ∨ (a ∧  b ∧a ∧ ~c) // a ∧ a = a, b ∧ ~b = false, false ∧ a = false
(a ∧  b ∧a ∧ ~c) // a ∧ a = a
(a ∧  b ∧ ~c)

// Can you please give a lead where to fix? Thanks.
UPDATE: CORRECTED. ANSWER ABOVE IS CORRECT NOW.

---

It looks like you dropped the parenthesis around the former XOR-subformula in line four.
Hence, in line 7, there's there's "a ∧" missing in front of "((¬a ∨ b) ∧ (¬b ∨ ¬c))". That'd continue the formula like this:
a ∧ (¬a ∨ b) ∧ (¬b ∨ ¬c)
We distribute a over the co-clauses:
 (a ∧ ¬a ∨ a ∧  b) ∧ (a ∧ ¬b ∨ a ∧  ¬c)
(a ∧  b) ∧ (a ∧ ¬b ∨ a ∧  ¬c)
(a ∧  b ∧ a ∧ ¬b ∨ a ∧  b ∧ a ∧  ¬c)
a ∧  b ∧ ¬c

---

Now I get the error. One more question:

a ∧ ((¬a ∨ b) ∧ (¬b ∨ ¬c))

let, (¬a ∨ b)  = X and (¬b ∨ ¬c) = Y, then:

a ∧ (X ∧ Y)

but you mentioned to distribute a over the co-clauses which I did not get. Shouldn't it be:

a ∧ X ∧ Y

---

(a ∧ X) ∧ (a ∧ Y) = a ∧ X ∧ Y
Doesn't make a difference whether you apply it once or twice. Sometimes, applying it twice eliminates sometimes eliminates some subformulas containing ¬a. In the end, it doesn't matter here, as we later multiply out either X ∧ (a ∧ Y) or (a ∧ X) ∧ Y, so we'll multiply a definitely to the terms of X and Y (if that hasn't happened before).

---

Understood, thank you.