Result of ANDing & ORing functions expressed as CDNF & CCNF

Question

I came across following fact:

If we AND two functions expressed as CDNF (Canonical Disjunctive Normal Form), then the result contains sum of commont minterms.

For example consider two functions $f_1$ and $f_2$ on three variables $A,B$ and $C$ expressed in CDNF. Then they will have eight minterms: $m_0$ to $m_7$.

If

$f_1 = \sum ({m_1,m_2,m_3}) = m_1+m_2+m_3$ and

$f_1 = \sum ({m_2,m_3,m_4})=m_2+m_3+m_4$

then,

$f_1.f_2=m_2+m_3$ as $m_2$ and $m_3$ are common in both $f_1$ and $f_2$.

However now I am thinking about what will be the result of

1. $f_1+f_2$

   If we consider $F_1$ and $F_2$ on three variables $A,B$ and $C$ expressed in CCNF (Canonical Conjuctive Normal Form) as follows:

   $F_1 = \prod ({M_1,M_2,M_3}) = M_1.M_2.M_3$ and

   $F_1 = \prod ({M_2,M_3,M_4}) = M_2.M_3.M_4$

   then what will be the result of

2. $F_1.F_2$

3. $F_1+F_2$

After some thinking, I came up with following:

1. $f_1+f_2$ will be

   union of minterms in both functions, that is sum of all minterms with the common minterm appearing only once.

   Thus, $f_1+f_2 = m_1+m_2+m_3+m_4$

2. $F_1.F_2$ will also be

   union of the maxterms in both functions. That is the product of all maxterms with the common maxterms appearing only once.

   Thus, $F_1.F_2=M_1.M_2.M_3.M_4$

3. I found it very tricky to think about $F_1+F_2$. In the end I felt it should be

   AND of OR of two different maxterms with no OR of same and common maxterms.

   $\therefore F_1+F_2= (M_1+M_2)(M_1+M_3)(M_1+M_4)(M_2+M_3)(M_2+M_4)(M_3+M_4)$ So $(M_2+M_2)$ and $(M_3+M_3)$ will not be there.

   as $f_1.f_2$ was

   OR of AND of two same and common minterms with no AND of different minterms.

   So above $f_1.f_2$ was actually $m_2.m_2+m_3.m_3$. This because AND of different terms will be $0 (false)$ and $0+a=a$

   However, if I am correct with $(M_2+M_2)$ and $(M_3+M_3)$ being not part of $F_1+F_2$, I don't understand why that would be. If I think as dual of "AND of different terms will be $0 (false)$ and $0+a=a$", it would be "OR of same terms will be $1 (true)$ and $1.a=a$". But I dont get how OR of same terms will be 1?

   I am just trying to find some pattern here and didnt found this explained anywhere.

Q. Am I correct with these three guessings?

Q. If yes then I will like to know about above bold-faced question: how OR of same terms will be 1?

Answer 1

There is no need to guess. Try to prove your guesses. If $f$ is the disjunction of minterms $\{m_i : i \in I\}$ and $g$ is the disjunction of minterms $\{m_j : j \in J\}$ then it is definitely the case that $f + g$ is the disjunction of $\{m_k : k \in I \cup J\}$, but not all $m_k$ are necessarily minterms. For example, $x + xy = x$.

Regarding $F+G$, try to use de Morgan's rules twice to reduce it to the case of $fg$, which is identical other than the operators involved. In Boolean algebra addition and multiplication are dual (via de Morgan's rules), so anything you can with CNFs you can also do with DNFs.