Algorithms and Theory
/
Circuits
Search
Duplicate
Notion
Circuits
Functional Completeness
The gates
N
O
T
NOT
NOT

and any one from
{
A
N
D
,
O
R
}
\{AND, OR\}
{
A
N
D
,
OR
}

are functionally complete. In other words, we can use these to represent any boolean function
f
:
(
{
0
,
1
}
n
)
→
{
0
,
1
}
f: (\{0, 1\}^n) \to \{0, 1\}
f
:
({
0
,
1
}
n
)
→
{
0
,
1
}

.
Thus, they for a universal set of gates.
