{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eEstás inscrito en el curso de Organización y Arquitectura de Computadoras en tu universidad. Decides escribir un programa para ayudar a verificar tu trabajo calculando el valor de salida de un circuito digital combinacional, dado sus entradas.\u003c/p\u003e\n \u003cdiv id\u003d\"circuitmath:1\" class\u003d\"figure\"\u003e\n \u003ccenter\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/ecdefacde026d12b5944a1028fb06c69?v\u003d1713479429\" alt\u003d\"\\includegraphics[width\u003d0.4\\textwidth ]{example_circuit}\" style\u003d\"width:40.00%\"\u003e\n \u003cdiv class\u003d\"caption\"\u003e\n \u003cb\u003eFigura 1\u003c/b\u003e: Un ejemplo de un circuito digital combinacional. Consulta el texto para una explicación.\n \u003c/div\u003e\n \u003c/center\u003e\n \u003c/div\u003e\n \u003cp\u003eConsidera el circuito mostrado en la Figura\u0026nbsp;1, que usamos para ilustración. Este circuito tiene cuatro entradas (letras A a través de D a la izquierda), cada una de las cuales es verdadera o falsa. Hay cuatro \u0027puertas\u0027, cada una de las cuales es uno de tres tipos: AND, OR o NOT. Cada puerta produce un valor verdadero o falso, dependiendo de sus entradas. La última puerta (la OR a la derecha) produce la salida de todo el circuito. Podemos escribir estos tres tipos de puertas en texto por sus equivalentes \u003cem\u003eoperadores lógicos\u003c/em\u003e: \u003ctt\u003e*\u003c/tt\u003e para AND, \u003ctt\u003e+\u003c/tt\u003e para OR, y \u003ctt\u003e-\u003c/tt\u003e para NOT. En lo que sigue, usaremos los operadores en lugar de las puertas para describir circuitos.\u003c/p\u003e\n \u003cp\u003eAsí es como funcionan estos operadores. Dada una asignación de verdadero (\u003ctt\u003eT\u003c/tt\u003e) o falso (\u003ctt\u003eF\u003c/tt\u003e) para cada entrada, los operadores producen el valor de verdad indicado en las siguientes tablas:\u003c/p\u003e\n \u003ccenter\u003e\n \u003ctable cellspacing\u003d\"0\" class\u003d\"tabular\"\u003e\n \u003ctbody\u003e\u003ctr\u003e\n \u003ctd style\u003d\"border-top-style:solid; border-left:1px solid black; border-right:1px solid black; border-top-color:black; border-top-width:1px; text-align:center\"\u003e\n \u003cp\u003e\u003ctt\u003eA\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"border-top-style:solid; text-align:center; border-top-color:black; border-top-width:1px; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eB\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"border-top-style:solid; text-align:center; border-top-color:black; border-top-width:1px; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eA B *\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"border-top-style:solid; text-align:center; border-top-color:black; border-top-width:1px; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eA B +\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd style\u003d\"border-top-style:solid; border-left:1px solid black; border-right:1px solid black; border-top-color:black; border-top-width:1px; text-align:center\"\u003e\n \u003cp\u003e\u003ctt\u003eT\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"border-top-style:solid; text-align:center; border-top-color:black; border-top-width:1px; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eT\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"border-top-style:solid; text-align:center; border-top-color:black; border-top-width:1px; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eT\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"border-top-style:solid; text-align:center; border-top-color:black; border-top-width:1px; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eT\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd style\u003d\"text-align:center; border-right:1px solid black; border-left:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eF\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"text-align:center; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eT\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"text-align:center; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eF\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"text-align:center; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eT\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd style\u003d\"text-align:center; border-right:1px solid black; border-left:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eT\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"text-align:center; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eF\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"text-align:center; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eF\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"text-align:center; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eT\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd style\u003d\"border-bottom-style:solid; border-bottom-width:1px; border-left:1px solid black; border-right:1px solid black; text-align:center; border-bottom-color:black\"\u003e\n \u003cp\u003e\u003ctt\u003eF\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"border-bottom-color:black; border-bottom-width:1px; text-align:center; border-bottom-style:solid; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eF\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"border-bottom-color:black; border-bottom-width:1px; text-align:center; border-bottom-style:solid; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eF\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"border-bottom-color:black; border-bottom-width:1px; text-align:center; border-bottom-style:solid; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eF\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\u003c/table\u003e \n \u003ctable cellspacing\u003d\"0\" class\u003d\"tabular\"\u003e\n \u003ctbody\u003e\u003ctr\u003e\n \u003ctd style\u003d\"border-top-style:solid; border-left:1px solid black; border-right:1px solid black; border-top-color:black; border-top-width:1px; text-align:center\"\u003e\n \u003cp\u003e\u003ctt\u003eA\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"border-top-style:solid; text-align:center; border-top-color:black; border-top-width:1px; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eA -\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd style\u003d\"border-top-style:solid; border-left:1px solid black; border-right:1px solid black; border-top-color:black; border-top-width:1px; text-align:center\"\u003e\n \u003cp\u003e\u003ctt\u003eT\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"border-top-style:solid; text-align:center; border-top-color:black; border-top-width:1px; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eF\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd style\u003d\"border-bottom-style:solid; border-bottom-width:1px; border-left:1px solid black; border-right:1px solid black; text-align:center; border-bottom-color:black\"\u003e\n \u003cp\u003e\u003ctt\u003eF\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"border-bottom-color:black; border-bottom-width:1px; text-align:center; border-bottom-style:solid; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eT\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\u003c/table\u003e\n \u003c/center\u003e\n \u003cp\u003eObserva que AND y OR toman dos entradas, mientras que NOT opera solo con una entrada. Además, usamos \u003cem\u003enotación postfix\u003c/em\u003e para escribir expresiones que involucran operadores (como \u003cspan class\u003d\"tex2jax_process\"\u003e$\\verb|A B *|$\u003c/span\u003e), donde el operador viene \u003cem\u003edespués\u003c/em\u003e de su(s) entrada(s) (así como en la Figura\u0026nbsp;1, cada puerta en el diagrama del circuito viene después de sus entradas).\u003c/p\u003e\n \u003cp\u003eCuando describimos un circuito válido en notación postfix, usamos la siguiente sintaxis.\u003c/p\u003e\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eUna letra mayúscula (\u003ctt\u003eA\u003c/tt\u003e a través de \u003ctt\u003eZ\u003c/tt\u003e) es un circuito válido. En otras palabras, una entrada sola (sin ninguna puerta) es un circuito válido (que produce como salida su propio valor de entrada).\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eSi \u003ctt\u003e\u0026lt;C1\u0026gt;\u003c/tt\u003e y \u003ctt\u003e\u0026lt;C2\u0026gt;\u003c/tt\u003e son circuitos válidos, entonces ‘\u003ctt\u003e\u0026lt;C1\u0026gt; \u0026lt;C2\u0026gt; *\u003c/tt\u003e’ es un circuito válido que produce el AND de las salidas de los dos subcircuitos.\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eSi \u003ctt\u003e\u0026lt;C1\u0026gt;\u003c/tt\u003e y \u003ctt\u003e\u0026lt;C2\u0026gt;\u003c/tt\u003e son circuitos válidos, entonces ‘\u003ctt\u003e\u0026lt;C1\u0026gt; \u0026lt;C2\u0026gt; +\u003c/tt\u003e’ es un circuito válido que produce el OR de las salidas de los dos subcircuitos.\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eSi \u003ctt\u003e\u0026lt;C1\u0026gt;\u003c/tt\u003e es un circuito válido, entonces ‘\u003ctt\u003e\u0026lt;C1\u0026gt; -\u003c/tt\u003e’ es un circuito válido que produce el NOT de la salida de \u003ctt\u003e\u0026lt;C1\u0026gt;\u003c/tt\u003e.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n \u003cp\u003eNinguna otra descripción es un circuito válido.\u003c/p\u003e\n \u003cp\u003eAsí, una de las formas en que el circuito en la Figura 1 podría ser descrito usando notación postfix es como la cadena:\u003c/p\u003e\n \u003ccenter\u003e\n \u003ctt\u003eA B * C D + - +\u003c/tt\u003e\n \u003c/center\u003e\n \u003cp\u003eDado un valor de verdad (\u003ctt\u003eT\u003c/tt\u003e o \u003ctt\u003eF\u003c/tt\u003e) para cada una de las entradas (\u003ctt\u003eA\u003c/tt\u003e, \u003ctt\u003eB\u003c/tt\u003e, \u003ctt\u003eC\u003c/tt\u003e, y \u003ctt\u003eD\u003c/tt\u003e en este ejemplo), sus valores se propagan a través de las puertas del circuito, y el valor de verdad producido por la última puerta es la salida del circuito. Por ejemplo, cuando al circuito anterior se le dan las entradas \u003ctt\u003eA\u003dT\u003c/tt\u003e, \u003ctt\u003eB\u003dF\u003c/tt\u003e, \u003ctt\u003eC\u003dT\u003c/tt\u003e, \u003ctt\u003eD\u003dF\u003c/tt\u003e, la salida del circuito es \u003ctt\u003eF\u003c/tt\u003e.\u003c/p\u003e\n \u003cp\u003eDada una asignación a las variables y una descripción del circuito, tu software debería imprimir la salida del circuito.\u003c/p\u003e\n \u003ch2\u003eEntrada\u003c/h2\u003e\n \u003cp\u003eLa primera línea de la entrada consiste en un solo entero\n \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e, que satisface\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq n \\leq 26$\u003c/span\u003e,\n denotando el número de variables de entrada. Luego sigue una línea\n con \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e caracteres separados por espacios.\n Cada carácter es o bien \u003cspan class\u003d\"tex2jax_process\"\u003e$\\verb|T|$\u003c/span\u003e o \u003cspan class\u003d\"tex2jax_process\"\u003e$\\verb|F|$\u003c/span\u003e, con el \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003evo carácter indicando el\n valor de verdad de la entrada que está etiquetada con la \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003eva letra del alfabeto.\u003c/p\u003e\n \u003cp\u003eLa última línea de la entrada contiene una descripción del circuito, que\n sigue la sintaxis descrita anteriormente. Cada circuito es válido, utiliza\n solo las primeras \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e letras\n del alfabeto como etiquetas de entrada, y contiene al menos\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e y como máximo\n \u003cspan class\u003d\"tex2jax_process\"\u003e$250$\u003c/span\u003e caracteres totales sin espacios.\u003c/p\u003e\n \u003cp\u003eTen en cuenta que aunque a cada variable se le proporciona solo un valor de verdad, una variable puede aparecer varias veces en la descripción del circuito y servir como entrada a más de una puerta.\u003c/p\u003e\n \u003ch2\u003eSalida\u003c/h2\u003e\n \u003cp\u003eImprime un solo carácter, la salida del circuito (ya sea\n \u003ctt\u003eT\u003c/tt\u003e o \u003ctt\u003eF\u003c/tt\u003e), cuando se evalúa usando los valores de entrada dados.\u003c/p\u003e\n \u003ch2\u003eEjemplo 1\u003c/h2\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\nT F T F\nA B * C D + - +\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eF\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}