MathB.in - Share Mathematics with LaTeX and Markdown

We have boolean variables $X_i$ we want a small set of clauses which indicate if exactly one of them is true.

Idea, if we can build an adder which keeps up to 2 bits then it should work.

\begin{align*}
00 &= \text{all false} \\
01 &= \text{exactly one} \\
10 &= \text{more than 1} \\
11 &= \text{invalid output}
\end{align*}

Combinations
\begin{align*}
M(00, 00) &= 00 \\
M(00, 01) &= 01 \\
M(01, 00) &= 01 \\
M(01, 01) &= 10 \\
M(10, y) &= 10 \\
M(x, 10) &= 10 \\
\end{align*}

$M\big((x_1, x_0), (y_1, y_0)\big) = (z_1, z_0)$

\begin{align*}

z_0 &= \bar x_1 x_0 + \bar y_1 y_0 \\

\bar z_1 &= \text{not} (\bar x_1 \bar x_0 \bar y_1 \bar y_0 + z_0)

\end{align*}

So new convention, flip first bit:

\begin{align*}
10 &= \text{all false} \\
11 &= \text{exactly one} \\
00 &= \text{more than 1} \\
01 &= \text{invalid output}
\end{align*}

Combinations
\begin{align*}
M(10, 10) &= 10 \\
M(10, 11) &= 11 \\
M(11, 10) &= 11 \\
M(11, 11) &= 00 \\
M(00, y) &= 00 \\
M(x, 00) &= 00 \\
\end{align*}

$M\big((x_1, x_0), (y_1, y_0)\big) = (z_1, z_0)$

\begin{align*}

z_0 &= 1011 + 1110 \\

z_1 &= 1010 + 1011 + 1110

\end{align*}

Now let us figure out smallest group to make group outputs. We can do with 1 :

\begin{align*}
0 &\rightarrow 10 \\
1 &\rightarrow 11
\end{align*}

With 2:
\begin{align*}
00 &\rightarrow 10 \\
01 &\rightarrow 11 \\
10 &\rightarrow 11 \\
11 &\rightarrow 00
\end{align*}

With 3:
\begin{align*}
000 &\rightarrow 10 \\
001 &\rightarrow 11 \\ 
010 &\rightarrow 11 \\
011 &\rightarrow 00 \\
100 &\rightarrow 11 \\
101 &\rightarrow 00 \\
110 &\rightarrow 00 \\
111 &\rightarrow 00 \\
\end{align*}

Fri, 22 Dec 2023 03:45 GMT