nLab logic gate

Contents

Contents

Idea

Broadly, a logic gate is a function of tuples of truth values, hence a map between cartesian products Bool n\mathrm{Bool}^n of Booleans Bool{false,true}{0,1}Bool \,\coloneqq\, \{false, true\} \;\simeq\; \{0,1\}.

Specifically, one calls such a function a logic gate if it is thought of as potentially implemented as a basic operation performed by a computing machine – in which case the truth values are also called bits.

As such, typical logic gates are Boolean functions between a small number of bits, with more complicated such functions thought as obtained by composing a given set of logic gates into logic circuits.

Analogously there are quantum logic gates compiled into quantum circuits.

Examples

A list of some basic logic and gates and their reversible and quantum logic gate versions:


NOT:



XOR and CNOT:



AND:

(…)

References

Textbook accounts:

  • Jan Friso Groote, Rolf Morel, Julien Schmaltz, Adam Watkins, Logic Gates, Circuits, Processors, Compilers and Computers, Springer (2021) [doi:10.1007/978-3-030-68553-9]

  • John Bird, Chapter 7 of: Bird’s Higher Engineering Mathematics, Routledge (2021) [ISBN:9781003124221]

See also:

Last revised on February 24, 2023 at 07:51:38. See the history of this page for a list of all contributions to it.