Libro computación cuántica

Libro computación cuántica

6 Lógica clásica, puertas y circuitos Capítulo 6 Lógica clásica, puertas y circuitos © Massachusetts Institute of Technology Todos los derechos reservados En este capítulo estudiamos brevemente la computación clásica, presentando las ideas en orden cronológico aproximado. Comenzamos con las funciones booleanas y la lógica, introducidas por primera vez por George Boole a fines del siglo XIX. En la década de 1930, Claude Shannon estudió álgebra booleana y se dio cuenta de que las funciones booleanas podían describirse mediante interruptores eléctricos. Los componentes eléctricos que corresponden a funciones booleanas se denominan puertas lógicas. La composición de funciones booleanas se convierte en el estudio de circuitos que involucran estas puertas. Comenzaremos estudiando las funciones booleanas en términos de lógica; luego mostraremos cómo traducir todo en circuitos y puertas. El material, hasta este punto, ahora se considera estándar y está contenido en cada texto introductorio de ciencias de la computación. Pero después de esto, analizamos algunas ideas que generalmente no forman parte de la introducción estándar. En la década de 1970, el físico ganador del Premio Nobel Richard Feynman se interesó en la informática y, durante unos años a principios de la década de 1980, Dio un curso de computación en el Instituto de Tecnología de California. Estas conferencias finalmente se redactaron como Conferencias Feynman sobre Computación. El interés de Feynman en la computación se debió en parte a su interacción con los puntos de vista idiosincrásicos de Edward Fredkin y Fredkin sobre la física y la computación. Fredkin cree que el universo es una computadora, y que desde las leyes de la física son reversibles, deberíamos estudiar la computación reversible y las puertas reversibles. Pero a pesar de que la tesis general de Fredkin es no es ampliamente aceptado en la comunidad de la física, es reconocido por tener algunas ideas brillantes y poco convencionales. Uno de estos es el billar. computadora de pelota. El libro de Feynman incluye una discusión de puertas reversibles y muestra cómo se puede realizar cualquier cálculo rebotando bolas entre sí Adoptamos el enfoque de Feynman. Resulta que las puertas reversibles son exactamente lo que necesitamos para la computación cuántica. La computadora de la bola de billar llevó al hombre de Feyn a pensar en partículas interactuando en lugar de bolas. Fue la inspiración por su trabajo en computación cuántica, pero lo incluimos aquí principalmente porque de su pura simplicidad e ingenio.

Lógica

A finales del siglo XIX, George Boole se dio cuenta de que ciertas partes de La lógica podía tratarse algebraicamente, que había leyes de la lógica que podían expresarse en términos de álgebra. Adoptamos la forma ahora estándar de introducir la lógica booleana mediante el uso de tablas de verdad para las tres operaciones básicas no, y, y o.

Negación

 Si un enunciado es verdadero, entonces su negación es falsa y, a la inversa, si un enunciado es falso, entonces su negación es verdadera. Por ejemplo, la declaración 2 + 2 = 4 es verdadero y su negación 2 + 2 ≠ 4 es falso. En lugar de dar concreto ejemplos de enunciados, a menudo dejamos que los símbolos P, Q y R representen ellos. Entonces, por ejemplo, 2 + 2 = 4 podría estar representado por P. El símbolo ¬ significa no; si P representa el enunciado 2 + 2 = 4, entonces ¬P representa             2 + 2 ≠4. Entonces podemos resumir las propiedades básicas de la negación usando nuestro símbolos: si P es verdadero, entonces ¬P es falso. Si P es falso, entonces ¬P es verdadero. Para hacer las cosas aún más concisas, podemos usar los símbolos T y F para denotan verdadero y falso respectivamente. Luego podemos definir las propiedades usando una mesa.

[pic 1]

Y

El símbolo de y es ∧. Si tenemos dos enunciados P y Q, podemos combinarlos para formar P Q∧. El enunciado P Q∧ es verdadero si y solo si ambos los enunciados componentes P y Q son verdaderos. Definimos y por lo siguiente tabla, donde las dos primeras columnas dan las posibilidades para los valores de verdad de P y Q y la tercera columna nos da el correspondiente valor de verdad de P Q∧.

[pic 2]

O

 El símbolo para o es ∨ y se define en la siguiente tabla

[pic 3]

Observe que P Q∨ es verdadero si tanto P como Q son verdaderos, entonces P Q∨ es verdadero si cualquiera uno de P o Q es verdadero y también si ambos son verdaderos. Este es el o que se usa en matemáticas y a veces se llama inclusivo o. El exclusivo o es definido como verdadero si cualquiera de los dos, pero no ambos, de P y Q es verdadero. Es falso si ambos son falsos, pero también es falso si ambos son verdaderos. El exclusivo o es denotado por ⊕. Su tabla de verdad está debajo.

...