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}.}
Iniziamo a dimostrare questo teorema per una funzione a una sola variabile booleana
x
1
{\displaystyle x_{1}}
f
(
x
1
)
=
x
1
⋅
f
(
1
)
+
x
1
¯
⋅
f
(
0
)
{\displaystyle f(x_{1})=x_{1}\cdot f(1)+{\overline {x_{1}}}\cdot f(0)}
Se
f
(
x
1
)
=
k
{\displaystyle f(x_{1})=k\ }
f
(
x
1
)
=
x
1
⋅
k
+
x
1
¯
⋅
k
=
k
(
x
1
+
x
1
¯
)
=
k
{\displaystyle f(x_{1})=x_{1}\cdot k+{\overline {x_{1}}}\cdot k=k(x_{1}+{\overline {x_{1}}})=k}
Se
f
(
x
1
)
=
x
1
{\displaystyle f(x_{1})=x_{1}\ }
f
(
x
1
)
=
x
1
⋅
1
+
x
1
¯
⋅
0
=
x
1
{\displaystyle f(x_{1})=x_{1}\cdot 1+{\overline {x_{1}}}\cdot 0=x_{1}}
Se
f
(
x
1
)
=
x
1
¯
{\displaystyle f(x_{1})={\overline {x_{1}}}}
f
(
x
1
)
=
x
1
⋅
0
+
x
1
¯
⋅
1
=
x
1
¯
{\displaystyle f(x_{1})=x_{1}\cdot 0+{\overline {x_{1}}}\cdot 1={\overline {x_{1}}}}
Le operazioni di somma logica, prodotto logico o complementazione non annullano le proprietà di Shannon delle funzioni booleane. Infatti, se sommiamo logicamente alla funzione di una variabile
f
(
x
1
)
=
x
1
+
k
{\displaystyle f(x_{1})=x_{1}+k}
k
=
0
→
f
(
x
1
)
=
x
1
;
k
=
1
→
f
(
x
1
)
=
1
{\displaystyle k=0\rightarrow f(x_{1})=x_{1}\quad ;\quad k=1\rightarrow f(x_{1})=1}
infatti
f
(
x
1
)
=
f
(
x
1
=
1
)
⋅
x
1
+
f
(
x
1
=
0
)
⋅
x
1
¯
=
1
⋅
x
1
+
k
⋅
x
1
¯
=
x
1
+
k
⋅
x
1
¯
.
{\displaystyle f(x_{1})=f(x_{1}=1)\cdot x_{1}+f(x_{1}=0)\cdot {\overline {x_{1}}}=1\cdot x_{1}+k\cdot {\overline {x_{1}}}=x_{1}+k\cdot {\overline {x_{1}}}.}
Nel caso di
f
(
x
1
)
=
x
1
⋅
k
{\displaystyle f(x_{1})=x_{1}\cdot k}
k
=
0
→
f
(
x
1
)
=
0
{\displaystyle k=0\rightarrow f(x_{1})=0}
k
=
1
→
f
(
x
1
)
=
x
1
{\displaystyle k=1\rightarrow f(x_{1})=x_{1}}
f
(
x
1
)
=
f
(
x
1
=
1
)
⋅
x
1
+
f
(
x
1
=
0
)
⋅
x
1
¯
=
k
⋅
x
1
+
0
⋅
x
1
¯
=
k
⋅
x
1
,
{\displaystyle f(x_{1})=f(x_{1}=1)\cdot x_{1}+f(x_{1}=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},\dots ,x_{n})=[x_{1}+f(0,x_{2},\dots ,x_{n})]\cdot [{\overline {x_{1}}}+f(1,x_{2},\dots ,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},\dots ,x_{n})=[x_{1}+f(0,x_{2},\dots ,x_{n})]\cdot [{\overline {x_{1}}}+f(1,x_{2},\dots ,x_{n})],}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4ca02f44a72df374fd2387ed7a17f5e1f22e43ac)
