Construct a propositional formula for the ZDD (Simplify)

Question

Please someone elaborate how above be simplified exactly on red highlighted?

Thanks in advance.

Answer 1

For the simplification, the distributive law is used

    a∧b ∨ a∧¬b = a∧(b∨¬b)

and then the simplification

    (b∨¬b) = true  and  a∧true = a

Altogether, this yields the following law:

    a∧b ∨ a∧¬b = a

which can also be used by applying associative and commutative laws in between, e.g.

    a∧b∧c ∨ a∧¬b∧c = a∧c

Comments

Noted with thanks. I am clear on your explanation but I can not apply such laws on this example.

1. (¬a ∧ b ∧ c) ∨ (¬a ∧ ¬b ∧ c) ∨(¬ a ∧ ¬ b ∧ ¬ c) = (¬a ∧ c) ∨ (¬ a ∧ ¬ b)
for this part we must add (¬a ∧ ¬b ∧ c) one more and we will have
   (¬a ∧ b ∧ c) ∨ (¬a ∧ ¬b ∧ c) ∨ (¬a ∧ ¬b ∧ c) ∨(¬ a ∧ ¬ b ∧ ¬ c)
then based on laws we can have (¬a ∧ c) ∨ (¬ a ∧ ¬ b) as result.

am I right? if yes, how we can add (¬a ∧ ¬b ∧ c)  one more?


2. (a) ∨ (¬a ∧ c) ∨ (¬ a ∧ ¬ b) = a ∨ c ∨ ( ¬ b)
how can we conclude this?

Thank you.

---

For point 1: Yes, you are absolutely right. And this is justified by just another law of Boolean algebra, namely a∧a = a which you can, of course, also apply the other way around, i.e., a = a∧a.

For point 2: As Martin pointed out, you can add first redundant clause, using the mentioned simplification law from the other direction, i.e., a = a∧b ∨ a∧¬b. This works as follows:

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

where yet another law was used, namely a ∨ a∧b = a which is the absorption law of boolean algebra.

Answer 2

KS pointed out a simplification law. It is applied once for the green co-clauses, and twice for the purple co-clauses. It is applied to the left and center, and to the center and right of the purple co-clauses.

In order to get to the last line, this law is applied too. Here, the implicit co-clauses a ∧ c as well as a ∧ ¬b are used. We can add them as x = x ∨ (x ∧ y) for any x, y with x → y (in simple words: It doesn't harm to redundantly add cases that are already covered).