cómo hacer una tabla de verdad a partir de una expresión booleana

Question

Estoy tratando de hacer una tabla de verdad a partir de una expresión de álgebra booleana SOP. Entiendo las tablas de verdad AND, OR, NOT. Sólo que no entiendo estos tipos de tablas y sus salidas.

Esta es la expresión: $$A'BD' + BCD + ABC' + AB'D = A'BD' + BCD + ABC' + AB'D + BC'D' + A'BC + ABD.$$

Puedo usar cualquier lado, el que sea más fácil. Sólo hazme saber de qué lado.

¿Podría $A'$ ser un $1$ y los otros sean un cero? Tampoco estoy seguro de cómo obtienen la salida?

Entiendo las salidas de una tabla de verdad AND, OR.

Pero no puedo entender estas salidas. ¿Se consideraría esto una tabla OR ya que la expresión es $+$ ?

¿Simplemente construiría $A$ , $B$ y $D$ con nots = 1 o cero? Entonces, ¿cómo puedo determinar la salida?

 -----------------------
 A  | B  | D  |  output
-----------------------
| 1 | 0  | 1  |   1?    |  A'BD'
------------------------
| 0 | 0  | 0  |   0?    |  BCD
------------------------
| 0 | 0  | 1  |   1?    |  ABC'
-------------------------

algo así.

Lo que estoy tratando de lograr es cómo la expresión de abajo es verdadera usando teoremas.

$$A'BD' + BCD + ABC' + AB'D = A'BD' + BCD + ABC' + AB'D + BC'D' + A'BC + ABD$$

Answer 1

A, B, C y D son variables booleanas, lo que significa que cada una toma el valor "verdadero" o "falso". Las expresiones más complejas tienen valor "verdadero" o "falso" en función de los valores de estas variables, de modo que, por ejemplo, A'BD' es verdadera si A es falso, B es verdadero y D es falso, y C es verdadero o falso.

Decir que F = G, donde F y G son expresiones complejas, significa que, no valores de las variables booleanas, el valor de F es el mismo que el de G como el valor de G (es decir, F y G son ambos verdaderos o ambos falsos). Así, por ejemplo, tenemos

     AB + AC = A(B+C)

porque si A es verdadero y B o C son verdaderos, entonces ambos lados son verdaderos, y en cualquier otro caso ambos lados son falsos---no hay manera de asignar valores a A, B, C de forma que los dos lados salgan de forma diferente.

Como se ha mencionado en los carteles anteriores, siempre se puede probar (o refutar) una una igualdad pasando por todas las posibles asignaciones de "verdadero" y "falso" a las variables. El objetivo parece ser demostrar "por teoremas", es decir, utilizando operaciones previamente probadas como verdaderas. Como dices, podemos manipular un lado de la ecuación hasta que tenga la forma del otro lado, o bien podemos manipular ambos lados y ponerlos en una forma común.

En este caso, lo primero que hay que observar es que el lado derecho (RHS) es una copia del LHS con algunas cosas extra añadidas al final. Por esta razón, lo más sencillo es manipular sólo el lado derecho para eliminar el exceso de información. Podemos empezar con este teorema básico:

  if Q is true whenever P is true, then Q = Q + P

Podemos demostrar este teorema considerando sistemáticamente todas las posibilidades para P y Q. O míralo de esta manera: Si Q es verdadera, entonces ambos lados de la ecuación son verdaderos. Y si Q es falso, entonces P debe ser falso (ya que, por supuesto, si P fuera verdadera Q sería verdadera) por lo tanto ambos lados son falsos.

Dado este teorema demostramos:

  XY + X'Z = XY + X'Z + YZ     

Prueba: Sea P YZ y sea Q XY+X'Z. Supongamos que P es verdadero, es decir, que Y y Z son verdaderos. Pero si Y y Z son verdaderas, entonces XY+X'Z debe ser verdadera. (Razón: Si X es verdadero, entonces, como Y es verdadero, XY es verdadero. Y si X es falso entonces, como Z es verdadero, X'Z es verdadero. Así que en cualquier caso XY+X'Z es verdadero). Así que hemos demostrado que Q es verdadera siempre que P es verdadera, por lo tanto por el teorema anterior Q = Q + P, que en este caso es lo que queríamos demostrar.

Ahora podemos demostrar

 A'D' + AC' = A'D' + AC' + C'D'

Esto es lo mismo que el teorema anterior, poniendo A por X, D' por Y, y C' para Z.

Este último teorema implica

 B(A'D' + AC') = B(A'D' + AC' + C'D')

que es lo mismo que

 A'BD' + ABC' = A'BD' + ABC' + BC'D'

Dado esto, podemos tomar el lado derecho del original y sustituir A'BD' + ABC' por A'BD' + ABC' + BC'D', es decir, podemos eliminar el término BC'D'.

Con pasos similares a los anteriores podemos demostrar estos dos teoremas:

 A'BD' + BCD = A'BD' + BCD + A'BC
 BCD + ABC' = BCD + ABC' + ABD

que nos permiten eliminar los dos últimos términos del lado derecho del original, completando la prueba.

Answer 2

Tu tabla de verdad tendrá 2^4=16 líneas. Comienza con cuatro columnas etiquetadas como A,B,C,D. En cada línea pon una combinación diferente de valores de verdad para A,B,C y D. Luego añade más columnas para las piezas de tu expresión. Así que para construir el lado izquierdo, haz una columna A'B y pon los valores de verdad de esa combinación. El primo de A es no y el multiplicador es AND. Así que esta columna mostraría (NO A) Y B para los valores de A y B en esa línea. Continúa añadiendo columnas para otros términos hasta que hayas construido todo el lado izquierdo. A continuación, comience con los términos que componen el lado derecho. Cuando hayas construido el lado derecho, compara la columna del lado izquierdo y la del lado derecho. Si coinciden en las 16 líneas, tu ecuación es correcta. Para un ejemplo sencillo, digamos que queremos demostrar que (A+B)'=A'B' La tabla quedaría así

Como la columna (A+B)' y la columna A'B' coinciden en todas partes, la ecuación es correcta.

Answer 3

Esto es más bien un comentario extendido por curiosidad académica. Pensé en intentar utilizar Prover9 para demostrar la identidad dada. [aquí v denota "o" y ^ denota "y"]

Para probar esto, introduje los supuestos en Prover9 (esta es la lista de axiomas del OP de aquí ):

x v x' = y v y'.  % false
x ^ x' = y ^ y'.  % true

y v (x ^ x') = y.
y v (x v x') = y.
x v x = x.
x v y = y v x.
(x v y) v z = x v (y v z).
x ^ (x v y) = x.
(x ^ y) v (x ^ y') = x.

a partir del cual demostró la identidad del OP (y si entiendo bien, fue por contradicción):

((((w' ^ x) ^ z') v ((x ^ y) ^ z)) v ((w ^ x) ^ y')) v ((w ^ x') ^ z) = (((((((w' ^ x) ^ z') v ((x ^ y) ^ z)) v ((w ^ x) ^ y')) v ((w ^ x') ^ z)) v ((x ^ y') ^ z')) v ((w' ^ x) ^ y)) v ((w ^ x) ^ z).

Answer 4

Creo que la parte de la pregunta "usando teoremas" pretende evitar que uses la técnica exhaustiva de "probar todas las posibilidades" (así que no uses esta técnica si es una pregunta de deberes).

Sin embargo, esta técnica funcionará bien, puede pasar por el $2^4=16$ posibles valores de (A,B,C,D) y comprueba que ambos lados de la ecuación coinciden. Esta será una prueba rigurosa de la identidad, pero no especialmente inteligente.

Suponiendo que entienda la notación correctamente:

• La concatenación (es decir, escribir las letras una al lado de la otra) es la abreviatura de "y", por ejemplo, ABC es "A y B y C",
• la adición (es decir, +) es la abreviatura de "o", por ejemplo AB+CD es "(A y B) o (C y D)"
• añadir un guión ' es la notación para la negación, es decir, "no", por ejemplo AB' es "A y (no B)".

Así que A'BD' es lo mismo que (no A) y B y (no D). En tu tabla, la primera fila es incorrecta ya que (no A) es falso (porque A es verdadero=1). La segunda fila es correcta ya que B es falso=0 (independientemente del valor que tenga C). La tercera fila es incorrecta ya que A es falso=0 (de nuevo, independientemente de los valores que tenga C).

Answer 5

1. He coloreado en gris la tabla general. Este sería el punto de partida.
2. Se toma cada término y se calcula el valor de cada combinación.
3. Haces la SUMA o el PRODUCTO dependiendo de tu ecuación Y.