1
$\begingroup$

I would like to know how to alter/add NOTs when applying Duality principle.

Suppose I have P = XY(X+Y) + NOT(Y), how to find its dual?

My book says that while applying Duality Principle to a relation:

  • Change all 0s to 1s
  • Change all ORs to ANDs
  • Change all ANDs to ORs

But it doesn't say anything about NOTs.

$\endgroup$
3
$\begingroup$

In the dual boolean algebra, NOT is the same NOT operation we have in the original boolean algebra.

Your book does not say anything to handle NOT because there's nothing that needs to be done. Simply leave the NOTs unaffected in your formula.

$\endgroup$
2
$\begingroup$

Let's start with the definition:

The dual of a Boolean function $f(x_1,\ldots,x_n)$ is the function $f' = \lnot f(\lnot x_1,\ldots,\lnot x_n)$.

Here $\lnot$ is negation. The idea of the definition is to switch True and False, both for the input variables and for the output.

Suppose now that the function $f$ is given over the "de Morgan basis". This is the smallest collection $F$ of functions such that:

  • $0,1 \in F$.
  • $x_i \in F$ for every variable $x_i$.
  • If $g \in F$ then $\lnot g \in F$.
  • If $g,h \in F$ then $g \lor h, g \land h \in F$.

Here $\lor$ is OR and $\land$ is AND.

We can now give a recursive procedure for dualizing a function:

  • If $f = 0$ then $f' = \lnot 0 = 1$.
  • If $f = 1$ then $f' = \lnot 1 = 0$.
  • If $f = x_i$ then $f' = \lnot \lnot x_i = x_i$.
  • If $f = \lnot g$ then $f' = \lnot \lnot g = \lnot g'$.
  • If $f = g \lor h$ then $f' = \lnot (g \lor h) = \lnot g \land \lnot h = g' \land h'$.
  • If $f = g \land h$ then $f' = \lnot (g \land h) = \lnot g \lor \lnot h = g' \lor h'$.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.