¿Alguien podría explicarme cómo (p ∨ q) = (p NAND p) NAND (q NAND q)?

Question

Puedo probarlo todo el camino a:

¿Cuál es la prueba de que ambos son iguales?

Hasta ahora tengo:

(p q) = (p ^ p) (q ^ q)

¡Negarlo...

~((p ^ p) (q ^ q))

Obtienes...

~(p ^ p) ^ ~(q ^ q) = (p NAND p) ^ (q NAND q)

¡CASI! ¿Cómo sigo desde aquí?

Answer 1

Para empezar, ten en cuenta que

$$\text{NAND} (p_1, p_2) = \neg (p_1 \land p_2)$$

Por lo tanto $\text{NAND} (p, p) = \neg (p \land p) \equiv \neg p$ porque $p \land p \equiv p$. Por lo tanto,

$$ \text{NAND} (\text{NAND} (p, p), \text{NAND} (q, q)) = \text{NAND} (\neg p, \neg q) = \neg (\neg p \land \neg q) \equiv \neg\neg p \lor \neg\neg q \equiv p \lor q$$

donde utilicé una de las leyes de De Morgan y la eliminación de la doble negación (es decir, $\neg \neg p \equiv p$).

Answer 2

Escribe la tabla de verdad para $p\lor q$.

Luego encuentra la tabla de verdad para $(p\:\text{NAND}\:p)\:\text{NAND}\:(q\:\text{NAND}\:q)$ y compara. Fin.

Answer 3

Aquí tienes una prueba a través del probador de teoremas automatizado Prover9: En primer lugar, ingresamos las suposiciones (lógica booleana estándar, y definimos una función como NAND):

formulas(assumptions).

% asociatividad de "or" y "and"
x v (y v z) = (x v y) v z.
x ^ (y ^ z) = (x ^ y) ^ z.

% conmutatividad de "or" y "and"
x v y = y v x.
x ^ y = y ^ x.

% distributividad
x ^ (y v z) = (x ^ y) v (x ^ z).
x v (y ^ z) = (x v y) ^ (x v z).

% idempotencia
x v x = x.
x ^ x = x.

% absorción
x ^ (x v y) = x.
x v (x ^ y) = x.

% a = falso; b = verdadero
x v a = x.
x v b = b.
x ^ b = x.
x ^ a = a.

% leyes de negación
x ^ (-x) = a.
x v -x = b.
-(-x) = x.

% leyes de De Morgan
(-x) ^ (-y) = -(x v y).
(-x) v (-y) = -(x ^ y).

% definir * = NAND
x * y = -(x ^ y).

end_of_list.

formulas(goals).

x v y = (x * x) * (y * y).

end_of_list.

Y ingresar esto en Prover9, que devuelve:

============================== PROOF =================================

% Prueba 1 en 0.01 (+ 0.00) segundos.
% Longitud de la prueba es 9.
% Nivel de la prueba es 3.
% Peso máximo de la cláusula es 10.
% Cláusulas dadas 0.

1 x v y = (x * x) * (y * y) # label(non_clause) # label(goal).  [goal].
11 x v x = x.  [assumption].
21 --x = x.  [assumption].
24 -x v -y = -(x ^ y).  [assumption].
25 -(x ^ y) = -x v -y.  [copy(24),flip(a)].
26 x * y = -(x ^ y).  [assumption].
27 x * y = -x v -y.  [copy(26),rewrite([25(3)])].
28 c1 v c2 != (c1 * c1) * (c2 * c2).  [deny(1)].
29 $F.  [copy(28),rewrite([27(6),11(8),27(8),11(10),27(8),21(6),21(7)]),xx(a)].

============================== end of proof ==========================

Lo cual recupera la prueba de Rod Carvalho. Nota: En realidad, no se usaron la mayoría de los axiomas booleanos.

Answer 4

En tu segunda línea, deberías haberlo doble negado para mantenerlo igual.

~[~[(p $\wedge$ p) $\vee$ (q $\wedge$ q)]] = ~[~(p $\wedge$ p) $\wedge$ ~(q $\wedge$ q)]=~[pNANDp $\wedge$ qNANDq]

como mencionó Rod, $p_1$ NAND $p_2$ = ~($x$ $\wedge$ $y$).

Por lo tanto,

~[pNANDp $\wedge$ qNANDq]= (pNANDp) NAND (qNANDq).