Irredundant PDNF for Positive Boolean functions

As it is known, every Boolean function $f$ can be represented as a logical sum of logical products

$$f(x_1, \dots, x_n)=\bigvee_{i=1}^{m} \left( \bigwedge_{j \in J_i} x_j \bigwedge_{k \in K_i} \overline{x}_k \right)$$ (1)

where $J_i$ and $K_i$ are subsets of $I_n=\{1, \dots, n\}$ with $J_i \cap K_i = \emptyset$ for $i=1,\dots ,m$ and $\bigwedge_{j \in J_i} x_j=1$ if $J=\emptyset$.

The expression (1) is called Disjunctive Normal Form (DNF) of the function $f$.

Furthermore, if the Boolean function $f$ is positive, we have that $K_i= \emptyset$ for every index $i$ and, consequently, (1) reduces to

$$f(x_1, \dots, x_n)=\bigvee_{J \in \mathcal{J}}^{m} \bigwedge_{j \in J} x_j$$ (2)

where $\mathcal{J}$ is a collection of subsets of $I_n$, i.e.  $\mathcal{J} \subset 2^{I_n}$. The expression (2) is called Positive Disjunctive Normal Form (PDNF) of the function $f$.

An irredundant Positive Disjunctive Normal Form (irredundant PDNF) is an expression (2) where $\mathcal{J}$ doesn't contain pairs of sets $J$, $J'$ with $J \subset J'$.

It can be shown that the irredundant PDNF is unique for any positive Boolean function $f$ and that the terms $x_j$ inside it refer to all and only the relevant variables.