Data una funzione booleana
f
{\displaystyle f}
n
{\displaystyle n}
variabili booleane
x
1
,
x
2
,
…
,
x
n
,
{\displaystyle x_{1},x_{2},\dots ,x_{n},}
f
(
x
1
,
x
2
,
…
,
x
n
)
=
x
1
⋅
f
(
1
,
x
2
,
…
,
x
n
)
+
x
1
¯
⋅
f
(
0
,
x
2
,
…
,
x
n
)
.
{\displaystyle f(x_{1},x_{2},\dots ,x_{n})=x_{1}\cdot f(1,x_{2},\dots ,x_{n})+{\overline {x_{1}}}\cdot f(0,x_{2},\dots ,x_{n}).}
Le due funzioni sommate al secondo membro sono dette residui della funzione al primo membro rispetto alla variabile
x
1
.
{\displaystyle x_{1}.}
Si consideri una funzione
f
(
x
1
,
x
2
,
…
,
x
n
)
{\displaystyle f(x_{1},x_{2},\ldots ,x_{n})}
x
1
{\displaystyle x_{1}}
0
{\displaystyle 0}
1.
{\displaystyle 1.}
Caso
x
1
=
0
{\displaystyle x_{1}=0}
f
(
0
,
x
2
,
…
,
x
n
)
{\displaystyle f(0,x_{2},\ldots ,x_{n})}
0
⋅
f
(
1
,
x
2
,
…
,
x
n
)
+
0
¯
⋅
f
(
0
,
x
2
,
…
,
x
n
)
=
0
⋅
f
(
1
,
x
2
,
…
,
x
n
)
+
1
⋅
f
(
0
,
x
2
,
…
,
x
n
)
=
f
(
0
,
x
2
,
…
,
x
n
)
.
{\displaystyle 0\cdot f(1,x_{2},\ldots ,x_{n})+{\overline {0}}\cdot f(0,x_{2},\ldots ,x_{n})=0\cdot f(1,x_{2},\ldots ,x_{n})+1\cdot f(0,x_{2},\ldots ,x_{n})=f(0,x_{2},\ldots ,x_{n}).}
Caso
x
1
=
1
{\displaystyle x_{1}=1}
f
(
1
,
x
2
,
…
,
x
n
)
{\displaystyle f(1,x_{2},\ldots ,x_{n})}
1
⋅
f
(
1
,
x
2
,
…
,
x
n
)
+
1
¯
⋅
f
(
0
,
x
2
,
…
,
x
n
)
=
1
⋅
f
(
1
,
x
2
,
…
,
x
n
)
+
0
⋅
f
(
0
,
x
2
,
…
,
x
n
)
=
f
(
1
,
x
2
,
…
,
x
n
)
.
{\displaystyle 1\cdot f(1,x_{2},\ldots ,x_{n})+{\overline {1}}\cdot f(0,x_{2},\ldots ,x_{n})=1\cdot f(1,x_{2},\ldots ,x_{n})+0\cdot f(0,x_{2},\ldots ,x_{n})=f(1,x_{2},\ldots ,x_{n}).}
Per espandere rispetto a più variabili si reitera la precedente. Si consideri un'espansione rispetto a
x
1
{\displaystyle x_{1}}
x
2
{\displaystyle x_{2}}
f
(
x
1
,
x
2
,
…
,
x
n
)
=
x
2
⋅
[
x
1
⋅
f
(
1
,
1
,
…
,
x
n
)
+
x
1
¯
⋅
f
(
0
,
1
,
…
,
x
n
)
]
+
x
2
¯
⋅
[
x
1
⋅
f
(
1
,
0
,
…
,
x
n
)
+
x
1
¯
⋅
f
(
0
,
0
,
…
,
x
n
)
]
.
{\displaystyle f(x_{1},x_{2},\ldots ,x_{n})=x_{2}\cdot [x_{1}\cdot f(1,1,\ldots ,x_{n})+{\overline {x_{1}}}\cdot f(0,1,\dots ,x_{n})]+{\overline {x_{2}}}\cdot [x_{1}\cdot f(1,0,\ldots ,x_{n})+{\overline {x_{1}}}\cdot f(0,0,\ldots ,x_{n})].}
Le operazioni di somma logica, prodotto logico o complementazione non annullano le proprietà di Shannon delle funzioni booleane. Infatti, se sommiamo logicamente
k
{\displaystyle k}
g
(
x
1
)
=
x
1
{\displaystyle g(x_{1})=x_{1}}
f
(
x
1
)
=
x
1
+
k
{\displaystyle f(x_{1})=x_{1}+k}
se
k
=
0
,
{\displaystyle k=0,}
f
(
x
1
)
=
x
1
,
{\displaystyle f(x_{1})=x_{1},}
se
k
=
1
,
{\displaystyle k=1,}
f
(
x
1
)
=
1.
{\displaystyle f(x_{1})=1.}
Infatti
f
(
x
1
)
=
f
(
1
)
⋅
x
1
+
f
(
0
)
⋅
x
1
¯
=
1
⋅
x
1
+
k
⋅
x
1
¯
=
x
1
+
k
⋅
x
1
¯
,
{\displaystyle f(x_{1})=f(1)\cdot x_{1}+f(0)\cdot {\overline {x_{1}}}=1\cdot x_{1}+k\cdot {\overline {x_{1}}}=x_{1}+k\cdot {\overline {x_{1}}},}
che fornisce proprio
f
(
x
1
)
=
x
1
{\displaystyle f(x_{1})=x_{1}}
f
(
x
1
)
=
1
{\displaystyle f(x_{1})=1}
k
=
0
,
1
{\displaystyle k=0,1}
Nel caso di
f
(
x
1
)
=
x
1
⋅
k
{\displaystyle f(x_{1})=x_{1}\cdot k}
se
k
=
0
,
{\displaystyle k=0,}
f
(
x
1
)
=
0
,
{\displaystyle f(x_{1})=0,}
se
k
=
1
,
{\displaystyle k=1,}
f
(
x
1
)
=
x
1
.
{\displaystyle f(x_{1})=x_{1}.}
Quindi
f
(
x
1
)
=
f
(
1
)
⋅
x
1
+
f
(
0
)
⋅
x
1
¯
=
k
⋅
x
1
+
0
⋅
x
1
¯
=
k
⋅
x
1
,
{\displaystyle f(x_{1})=f(1)\cdot x_{1}+f(0)\cdot {\overline {x_{1}}}=k\cdot x_{1}+0\cdot {\overline {x_{1}}}=k\cdot x_{1},}
che fornisce proprio
f
(
x
1
)
=
0
{\displaystyle f(x_{1})=0}
f
(
x
1
)
=
x
1
{\displaystyle f(x_{1})=x_{1}}
k
=
0
,
1
{\displaystyle k=0,1}
Applicazione alle porte logiche
modifica
Applicando il teorema una seconda volta su ognuno dei residui rispetto alla variabile
x
1
{\displaystyle x_{1}}
f
(
x
1
,
x
2
,
…
,
x
n
)
=
x
1
x
2
⋅
f
(
1
,
1
,
…
,
x
n
)
+
x
1
¯
x
2
⋅
f
(
0
,
1
,
…
,
x
n
)
+
x
1
x
2
¯
⋅
f
(
1
,
0
,
…
,
x
n
)
+
x
1
x
2
¯
⋅
f
(
0
,
0
,
…
,
x
n
)
,
{\displaystyle f(x_{1},x_{2},\dots ,x_{n})=x_{1}x_{2}\cdot f(1,1,\dots ,x_{n})+{\overline {x_{1}}}x_{2}\cdot f(0,1,\dots ,x_{n})+x_{1}{\overline {x_{2}}}\cdot f(1,0,\dots ,x_{n})+{\overline {x_{1}x_{2}}}\cdot f(0,0,\dots ,x_{n}),}
iterando il procedimento a tutte le
n
{\displaystyle n}
f
{\displaystyle f}
Per il principio di dualità si ottiene inoltre:
f
(
x
1
,
x
2
,
…
,
x
n
)
=
[
x
1
+
f
(
0
,
x
2
,
…
,
x
n
)
]
⋅
[
x
1
¯
+
f
(
1
,
x
2
,
…
,
x
n
)
]
,
{\displaystyle f(x_{1},x_{2},\ldots ,x_{n})=[x_{1}+f(0,x_{2},\dots ,x_{n})]\cdot [{\overline {x_{1}}}+f(1,x_{2},\ldots ,x_{n})],}
che è detto teorema duale. Anche sfruttando tale teorema si ottiene l'espressione algebrica della funzione in forma canonica AND-OR.
Il risultato finale è l'implementazione della funzione in una struttura di porte logiche semplici AND, OR e NOT, detta multiplexer .
^ (EN Proposition II An Investigation of the Laws of Thought: On which are Founded the Mathematical Theories of Logic and Probabilities , 1854, p. 73. 
![{\displaystyle f(x_{1},x_{2},\ldots ,x_{n})=x_{2}\cdot [x_{1}\cdot f(1,1,\ldots ,x_{n})+{\overline {x_{1}}}\cdot f(0,1,\dots ,x_{n})]+{\overline {x_{2}}}\cdot [x_{1}\cdot f(1,0,\ldots ,x_{n})+{\overline {x_{1}}}\cdot f(0,0,\ldots ,x_{n})].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4a6b41ac8f41a9d897443f12049a5737a3b8ec65)
![{\displaystyle f(x_{1},x_{2},\ldots ,x_{n})=[x_{1}+f(0,x_{2},\dots ,x_{n})]\cdot [{\overline {x_{1}}}+f(1,x_{2},\ldots ,x_{n})],}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7f5d877910d758bd59f8118ae1e11f4404fa1d2c)
