3.2: Forma Normal Disyuntiva

Última actualización
Guardar como PDF

Page ID: 118435

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

A menudo se desea (por ejemplo, en programación informática o diseño de circuitos lógicos) revertir el proceso: comenzando con una tabla de verdad deseada, ¿podemos construir un polinomio booleano con las mismas salidas?

Ejemplo\(\PageIndex{1}\)

Determinar un polinomio booleano\(p(x,y)\) que tenga la tabla de verdad a continuación.

\(x\)	\(y\)	\(p(x,y)\)
\ (x\) ">\(1\)	\ (y\) ">\(1\)	\ (p (x, y)\) ">\(1\)
\ (x\) ">\(1\)	\ (y\) ">\(0\)	\ (p (x, y)\) ">\(0\)
\ (x\) ">\(0\)	\ (y\) ">\(1\)	\ (p (x, y)\) ">\(0\)
\ (x\) ">\(0\)	\ (y\) ">\(0\)	\ (p (x, y)\) ">\(1\)

Solución

Queremos una salida “verdadera” cuando las entradas coincidan con la primera o cuarta fila, y sólo entonces. Las entradas coinciden con la primera fila precisamente cuando ambas\(x\) y\(y\) son verdaderas (es decir, cuando la conjunción\(x \land y\) es verdadera), y coinciden con la cuarta fila precisamente cuando ambas\(x\) no son verdaderas y no son verdaderas (\(y\)es decir, cuando la conjunción\(x' \land y'\) es verdadera). Así que toma la disyunción de estas dos conjunciones:\(p(x,y) = (x \land y) \lor (x' \land y')\text{.}\)

Observación\(\PageIndex{1}\)

En la solución al ejemplo trabajado anterior, podría parecer que deberíamos tomar una conjunción de las dos conjunciones en lugar de una disyunción, ya que vemos una salida de\(1\) en la primera fila y en la cuarta fila. No obstante, no podemos estar en el “estado” de entrada descrito por esas dos filas simultáneamente, ya que\(x\) ni ni\(y\) podemos estar ambas\(1\) y\(0\) simultáneamente. Entonces deberías pensarlo de esta manera en su lugar: si vemos un estado de salida de\(1\text{,}\) entonces sabemos que debemos estar en el estado de entrada de la primera fila o de la cuarta fila.

Definición: Forma Normal Disyuntiva

un polinomio booleano en variables\(x_1,x_2,\ldots,x_n\) que es la disyunción de términos distintos de la forma\(a_1 \land a_2 \land \cdots \land a_n\text{,}\) donde cada uno\(a_i\) es\(x_i\) o\(x_i'\text{.}\)

Convención\(\PageIndex{1}\)

También se considera que el polinomio cero está en forma normal disyuntiva.

Nota\(\PageIndex{1}\)

La forma normal disjuntiva no suele ser el polinomio booleano “más bonito” o “más simple” con una tabla de verdad deseada, pero existe un procedimiento relativamente sencillo para producirla.

Procedimiento\(\PageIndex{1}\): To Produce the Disjunctive Normal Form Polynomial for a Given Boolean Truth Table

Dada una tabla de verdad con salida distinta de cero, podemos obtener un polinomio booleano en forma normal disyuntiva con esa tabla de verdad de la siguiente manera.

Identificar filas de la tabla en verdad para la cual es la salida deseada\(1\)
Para cada una de esas filas, formar la conjunción de todas las variables, pero negar aquellas variables que tengan valor de entrada\(0\) para esa fila.
Formar un polinomio tomando la disyunción de todas esas conjunciones.

Ejemplo\(\PageIndex{2}\)

Determinar un polinomio booleano\(p(x,y,z)\) que tenga la tabla de verdad a continuación.

\(x\)	\(y\)	\(z\)	\(p(x,y,z)\)
\(1\)	\(1\)	\(1\)	\(0\)
\(1\)	\(1\)	\(0\)	\(0\)
\(1\)	\(0\)	\(1\)	\(0\)
\(1\)	\(0\)	\(0\)	\(1\)
\(0\)	\(1\)	\(1\)	\(1\)
\(0\)	\(1\)	\(0\)	\(0\)
\(0\)	\(0\)	\(1\)	\(1\)
\(0\)	\(0\)	\(0\)	\(1\)

Solución

Las filas cuarta, quinta, séptima y octava tienen resultado\(1\text{.}\) Las conjunciones correspondientes son

cuarta fila

\(x \land y' \land z'\text{;}\)

quinta fila

\(x' \land y \land z\text{;}\)

séptima fila

\(x' \land y' \land z\text{;}\)y

Eigésima fila

\(x' \land y' \land z'\text{.}\)

Por lo tanto, el polinomio booleano

\ comenzar {ecuación*} p (x, y, z) = (x\ tierra y'\ tierra z')\ lor (x'\ tierra y\ tierra z)\ lor (x'\ tierra y'\ tierra z)\ lor (x'\ tierra y'\ tierra z')\ end {ecuación*}

está a la vez en forma normal disyuntiva y tendrá la tabla de verdad deseada.

Ejemplo\(\PageIndex{3}\)

Determinar un polinomio booleano\(q(x,y,z)\) que tenga la tabla de verdad a continuación.

\(x\)	\(y\)	\(z\)	\(q(x,y,z)\)
\(1\)	\(1\)	\(1\)	\(1\)
\(1\)	\(1\)	\(0\)	\(1\)
\(1\)	\(0\)	\(1\)	\(0\)
\(1\)	\(0\)	\(0\)	\(1\)
\(0\)	\(1\)	\(1\)	\(1\)
\(0\)	\(1\)	\(0\)	\(1\)
\(0\)	\(0\)	\(1\)	\(1\)
\(0\)	\(0\)	\(0\)	\(1\)

Solución 1

Cada fila, excepto la tercera, tiene resultado\(1\text{,}\) por lo que debemos formar conjunciones para todas las filas excepto esa:

primera fila
\(x \land y \land z\text{;}\)

segunda fila
\(x \land y \land z'\text{;}\)

cuarta fila
\(x \land y' \land z'\text{;}\)

quinta fila
\(x' \land y \land z\text{;}\)

sexta fila
\(x' \land y \land z'\text{;}\)

séptima fila
\(x' \land y' \land z\text{;}\) y

Eigésima fila
\(x' \land y' \land z'\text{.}\)

Por lo tanto, el polinomio booleano

\ comenzar {alinear*} q (x, y, z) & = (x\ tierra y\ tierra z)\ lor (x\ tierra y\ tierra z')\ lor (x\ tierra y'\ tierra z')\ lor (x'\ tierra y\ tierra z)\\ &\ fantasma {=}\ lor (x'\ tierra y\ tierra z')\ lor (x'\ tierra y'\ tierra\ z)\ lor (x'\ tierra y'\ tierra z')\ final {alinear*}

está a la vez en forma normal disyuntiva y tendrá la tabla de verdad deseada.

Solución. 2 Solución alternativa

Podemos obtener una expresión mucho más simple para\(q(x,y,z)\) al no usar el procedimiento (aunque por supuesto el resultado no estará en forma normal disyuntiva).

Observe que queremos que la tercera fila tenga valor de salida\(0\text{.}\) En términos lógicos, queremos que esa combinación (y solo esa combinación) de valores de entrada dé como resultado una salida que “no es verdadera”. Así que el polinomio booleano

\ begin {ecuación*} q (x, y, z) = (x\ land y'\ land z) '= x'\ lor y\ lor z'\ end {ecuación*}

producirá la tabla de verdad deseada.

Nota\(\PageIndex{2}\)

Los polinomios en las soluciones a los ejemplos precedentes están en forma normal disyuntiva, pero la solución alternativa al segundo ejemplo no lo es.

Hecho\(\PageIndex{1}\)

Desde Procedimiento\(\PageIndex{1}\), es fácil ver que cualquier polinomio booleano puede expresarse en forma normal disyuntiva.

Ejemplo\(\PageIndex{4}\): Converting a Polynomial into Disjunctive Normal Form

Reescribir el polinomio booleano\(p(x,y,z) = (x \land z)' \lor (x'\land y)\) en forma normal disyuntiva.

Solución

Primero, producir la tabla de la verdad.

\(x\)	\(y\)	\(z\)	\(x\land z\)	\(x' \land y\)	\(p(x,y,z)\)
1	\(1\)	\(1\)	\(1\)	\(0\)	0
1	\(1\)	\(0\)	\(0\)	\(0\)	1
1	\(0\)	\(1\)	\(1\)	\(0\)	0
1	\(0\)	\(0\)	\(0\)	\(0\)	1
0	\(1\)	\(1\)	\(0\)	\(1\)	1
0	\(1\)	\(0\)	\(0\)	\(1\)	1
0	\(0\)	\(1\)	\(0\)	\(0\)	1
0	\(0\)	\(0\)	\(0\)	\(0\)	1

A continuación, aplicar el procedimiento de forma normal disyuntiva para obtener

\ begin {align*} p (x, y, z) =& (x\ tierra y\ tierra z')\ lor (x\ tierra y'\ tierra z')\ lor (x'\ tierra y\ tierra z)\\ &\ lor (x'\ tierra y\ tierra z')\ lor (x'\ tierra y' tierra z)\ lor (x'\ tierra y'\ tierra z')\ text {.} \ end {alinear*}

Verifica tu comprensión

¿Qué crees que debería significar la forma normal conjuntiva? ¿Se puede llegar a un procedimiento que tome una tabla de verdad y determine un polinomio booleano en forma normal conjuntiva con la tabla de verdad deseada?

Insinuación: Amplíe la idea de la solución alternativa para el Ejemplo Trabajado\(\PageIndex{3}\)