Construir una puerta OR cuando falta información de entrada

Question

¿Hay alguna forma de construir una puerta OR cuando se desconoce la entrada de una combinación?

Por ejemplo, supongamos que la puerta, $X$ para las siguientes entradas, $x_1$ y $x_2$ , $x_1 = T$ , $x_2 = T$ : $X= T$ ; $x_1 = T$ , $x_2 = F$ : $X = F$ ; $x_1 = F$ , $x_2 = T$ , $X = F$ . Para la entrada $x_1 = F$ y $x_2 = F$ la puerta elige aleatoriamente la salida $T$ ou $F$ . ¿Hay alguna forma de construir una puerta OR utilizando $X$ ? Supongamos que las entradas y salidas pueden duplicarse y negarse y que podemos utilizar múltiples $X$ puertas. Se supone que no se pueden utilizar otras puertas (como AND, XOR...etc.). Las entradas y salidas sólo pueden duplicarse y negarse.

Answer 1

Escriba a $X*Y$ para el conectivo descrito en la pregunta.

Supongamos que sólo hay dos entradas, $X$ y $Y$ . Digamos que una puerta con un resultado determinado para cada entrada posible es determinado . Entonces todas las puertas determinadas construibles a partir de $\neg$ y $*$ serán funciones de $X$ y $Y$ o simplemente $X$ o simplemente $Y$ o ninguna de las dos. Digamos que una puerta determinada es degenerado si no depende tanto de $X$ y $Y$ . $\phi(X,Y)$ es degenerado si $\phi(X,1)=\phi(X,0)$ para $X=0,1$ ou $\phi(0,Y)=\phi(1,Y)$ para $Y=0,1$ . (Así, por ejemplo $\neg X, X\vee X, X\wedge \neg X$ y $X\wedge (Y\vee \neg Y)$ son degenerados pero $X\vee Y$ no es degenerado. Por definición ninguna puerta degenerada es indeterminada por lo que $X*X$ no es degenerado).

Demostraremos que toda puerta determinada (construida a partir de $*$ y $\neg$ ) es degenerada. (Y, por tanto, que $\vee$ no puede definirse).

Caso base: $X*Y, Y*Y$ y $X*X$ no están determinados, y $\neg X$ y $\neg Y$ son degenerados.

Paso inductivo:

Si $\neg\phi(X,Y)$ es determinada, entonces $\phi(X,Y)$ también debe ser determinada. Por hipótesis inductiva esto significa que $\phi(X,Y)$ es degenerada, lo que implica que $\neg \phi(X,Y)$ es degenerada.

Supongamos que $\psi(X,Y) * \chi(X,Y)$ es una puerta lógica determinada. Esto implica que tanto $\psi$ y $\chi$ están determinadas (véase el lema a continuación).

Así pues, por hipótesis inductiva, tanto $\psi$ y $\chi$ son degenerados. Si $\psi$ y $\chi$ ambas dependen como máximo de $X$ (o como máximo en $Y$ ) entonces $\psi * \chi$ es degenerada dependiendo como máximo de $X$ únicamente (como máximo $Y$ únicamente). Supongamos, sin pérdida de generalidad, que $\phi$ depende de $X$ y $\psi$ en $Y$ . Desde $\psi(X) *\chi(Y)$ es determinada, sabemos que no hay elección de $X$ y $Y$ tal que $\psi(X)=\chi(Y)=0$ . Así que $\psi(X)=1$ pase lo que pase $X$ en cuyo caso $\psi(X)*\chi(Y)$ es degenerada en función de $Y$ solamente, o $\chi(Y)=1$ pase lo que pase $Y$ es, lo que significa que $\psi(X)*\chi(Y)$ es degenerada en función de $X$ sólo.

( Lema : Si $\phi=\psi * \chi$ es determinante tanto $\psi$ y $\chi$ están determinados.

Si $\psi$ no estuviera determinada, por ejemplo, entonces para alguna elección de $X,Y\in\{0,1\}$ podemos hacer $\psi(X,Y)$ al azar. Sin embargo, en la pregunta se estipulaba que los resultados de los procesos aleatorios se producen siempre de forma independiente, por lo que para esta elección de $X$ y $Y$ , $\phi(X,Y)$ es independiente del valor de $\chi(X,Y)$ (si este último valor es aleatorio o no). En función de $\chi(X,Y)=1$ , $\psi(X,Y)$ tiene posibilidades de ser $1$ ou $0$ y, del mismo modo, condicionado a $\chi(X,Y)=0$ . Si $\chi(X,Y)=1$ puis $\psi(X,Y)*\chi(X,Y) = \psi(X,Y)$ que puede ser 1 o 0. Si $\chi(X,Y)=0$ puis $\psi(X,Y)*\chi(X,Y) = 0$ si $\psi(X,Y)=1$ y tiene posibilidades de ser $1$ si $\psi(X,Y)=0$ . Así que en este caso $\psi(X,Y)*\chi(X,Y)$ también es aleatorio).