Simplification of a multi-index Boolean expression towards computation in fewer steps
-
29-11-2019 - |
سؤال
Let $x_{ij} \in \{0,1\}$, $1 \leq i \leq M$ (typically, $M = 2000$), $1 \leq j \leq N$ (typically, $N = 10$), be Boolean variables. If possible at all, I would like to simplify the following expression $$ \bigvee_{i_1,\dots,i_N} \left(\bigwedge_{k=1}^N x_{i_k k} \right), $$ where the join operation is taken over all indices $(i_1,\dots,i_N) \in \{1,\dots,M \}^N$, so that it can be computed faster instead of looping through all multi-indices.
Apologies if this is a well-known problem (with or without solution). This is very much outside of my field of expertise, so I am hoping someone around here could give some feedback on it. Feel free to edit the tags as you see more appropriate.
Thanks!
المحلول
It is equivalent to
$$\bigwedge_{k=1}^{N} \bigvee_{i_k=1}^{M} x_{i_k k}.$$
This is a much simpler expression: $NM$ terms instead of $M^N$ terms, if you expand everything out.