Trabajo Final de Lógica y Semánticas Formales

Indice1. Introducción 2. Qué Es Un Álgebra De Boole 3. Funciones De Boole – Formas Normales 4. Minimización De Funciones Booleanas 5. Conclusión 6. Bibliografía

1. Introducción

Las álgebras booleanas, estudiadas por primera vez en detalle por George Boole (ver apéndice), constituyen un área de las matemáticas que ha pasado a ocupar un lugar prominente con el advenimiento de la computadora digital. Son usadas ampliamente en el diseño de circuitos de distribución y computadoras, y sus aplicaciones van en aumento en muchas otras áreas. En el nivel de lógica digital de una computadora, lo que comúnmente se llama hardware, y que está formado por los componentes electrónicos de la máquina, se trabaja con diferencias de tensión, las cuales generan funciones que son calculadas por los circuitos que forman el nivel. Éstas funciones, en la etapa de diseña del hardware, son interpretadas como funciones de boole. En el presente trabajo se intenta dar una definición de lo que es un álgebra de boole; se tratan las funciones booleanas, haciendo una correlación con las fórmulas proposicionales. Asimismo, se plantean dos formas canónicas de las funciones booleanas, que son útiles para varios propósitos, tales como el de determinar si dos expresiones representan o no la misma función. Pero para otros propósitos son a menudo engorrosas, por tener más operaciones que las necesarias. Particularmente, cuando estamos construyendo los circuitos electrónicos con que implementar funciones booleanas, el problema de determinar una expresión mínima para una función es a menudo crucial. No resultan de la misma eficiencia en dinero y tiempo, principalmente, dos funciones las cuales calculan lo mismo pero donde una tiene menos variables y lo hace en menor tiempo. Como solución a este problema, se plantea un método de simplificación, que hace uso de unos diagramas especiales llamados mapas o diagramas de Karnaugh, y el cual tiene la limitación de poder trabajar adecuadamente sólo con pocas variables. Se realizan estas presentaciones con el fin de demostrar la afinidad existente entre el álgebra de boole y la lógica proposicional, y con el objeto de cimentar el procedimiento de simplificación presentado en la lógica de proposiciones. El material utilizado ha sido el proporcionado en la bibliografía consignada en el programa de la asignatura. Para la información presentada en el anexo, se ha recurrido a Internet.

2. Qué Es Un Álgebra De Boole

Un álgebra de Boole B es un conjunto B en el cual se pueden distinguir dos elementos notados 0 y 1 y donde dos operaciones binarias notadas + y . y una operación unaria notada ¨’¨ verifican los siguientes axiomas: sean x, y, z tres elementos cualesquiera de B.

• Conmutatividad:

x + y = y + x x . y = y . x

• Asociatividad:

x + (y + z) = (x + y) + z x . (y . z) = (x . y) . z

• Idempotencia:

x + x = x x . x = x

• Absorción:

x + (x . y) = x x . (x + y) = x

• Distributividad doble:

x . (y + z) = (x . y) + (x . z) x + (y . z) = (x + y) . (x + z)

• Elementos neutros:

x + 0 = x x . 1 = x

• Elemento absorbente:

x . 0 = 0 x + 1 = 1

• Complementación:

x + x’ = 1 x . x’ = 0

Otras propiedades básicas

• Leyes de De Morgan:

(x . y)’ = x’ + y’ (x + y)’ = x’ . y’

• 0’ = 1

1’ = 0

3. Funciones De Boole – Formas Normales

En el álgebra de Boole abstracta se usan denominaciones análogas a las del Álgebra elemental. Así, un monomio es una letra que representa un elemento de B, con o sin tilde de complemento, o bien un producto (intersección) de tales símbolos; ejemplos: a, b’, a’b (o sea, a’ . b), a . b . ’c; un polinomio es un monomio o una unión de monomios (términos del polinomio), ejemplo: a’ + b + ab’c términos a’, b, ab’c.

Una forma lineal es un polinomio cuyos términos se reducen a una sola letra con o sin tilde. Ejemplos: a, a’ + b pero no a + b.c, (a + b)’ . Una función de Boole es el resultado de efectuar un número finito de veces operaciones de Boole sobre constantes a, b, … (elementos determinados de B) y variables o indeterminadas x, y, … (elementos genéricos, indeterminados o arbitrarios de B, pero siempre el mismo siempre que aparezca una misma variable). A causa de las relaciones que existen entre las operaciones, es posible que una función booleana tome muchas formas. Por ejemplo, si f(x,y) = x’y’ y g(x,y) = (x+y)’, entonces, por las leyes de De Morgan sabemos que f y g son la misma función; es decir, toman idénticos valores para valores idénticos de las variables. Así pues, para determinar mejor si dos expresiones representan o no la misma función booleana, es deseable tener una forma canónica estándar en que podamos expresar las distintas funciones. Por tal motivo, ofrecen especial interés las funciones (duales) siguientes:

Definición:

• Una función de Boole se llama forma normal disyuntiva o polinomio normal en n variables x1, x2, … , xn (n>0) si es una de las constantes 0 , o bien un polinomio en cada uno de cuyos términos figuran las n variables xi y ninguna otra letra (y en particular, no hay constantes); y cada uno de los términos es único. Ejemplos: x +y’ , x’y + xy’ .
• Una función de Boole se llama forma normal conjuntiva o producto normal en n variables x1, x2, … , xn (n>0) si es una de las constantes 0 , o bien una forma lineal o un producto de formas lineales en cada uno de cuyos factores figuran las n variables xi y ninguna otra letra (y en particular, no hay constantes); y cada uno de los términos es único. Ejemplos: xy’, (x’ + y) . (x + y’).

Teorema: Toda función de Boole f(x1, x2, … , xn), sin constantes, se reducirá a una

• forma normal disyuntiva o polinomio normal o bien, a una
• forma normal conjuntiva o producto normal.

Una función de Boole en forma normal conjuntiva (o disyuntiva) en n variables, puede contener hasta 2n términos (o factores), pues en cada uno, cada letra xk puede aparecer en dos formas, xk o xk’ . Si contiene los 2n se llama completa. Es inmediato el siguiente

teorema:

• La forma normal completa disyuntiva en n variables x1, x2, …,xn resulta desarrollando (x1 + x1’). … .(xn + xn’) = 1 y para cada sistema de reemplazos de las variables x1, x2, …,xn por las constantes 0 y 1, uno y uno sólo de los términos da 1 y los demás 0.
• La forma normal completa conjuntiva en n variables x1, x2, …,xn resulta desarrollando (x1 . x1’)+ … +(xn . xn’) = 0 y para cada sistema de reemplazos de las variables x1, x2, …,xn por las constantes 0 y 1, uno y uno sólo de los factores da 0 y los demás 1.

Por ejemplo, en la forma normal disyuntiva completa en x, y, z, el reemplazo de x = z = 1, y = 0 , reduce a 1 el término xy’z, y a 0 los 7 restantes. De aquí resulta el siguiente

Teorema: Dos funciones de Boole son iguales si y sólo si coinciden sus respectivas formas normales de igual clase, y también si y sólo si coinciden para todo sistema de reemplazos de las variables por 0 y 1.

Aplicación al cálculo proposicional Si en el álgebra de enunciados se interpretan todas las equivalencias como igualdades, entonces el álgebra de enunciados pasa a ser un álgebra de Boole. Para ver esto, redefina 0,1,+ y ., y la complementación según se muestra en la siguiente tabla:

Un álgebra de Boole bivaluada (como la definida) tiene una interpretación dual. En esta interpretación dual se utiliza 0 como V, 1 como F, + en lugar de  y . en lugar de . La correlación hecha entre el álgebra de Boole y la Lógica, permite trasladar los conceptos previos al Cálculo proposicional. A las funciones de Boole corresponden las fórmulas proposicionales, que resultan de efectuar un número finito de veces las operaciones lógicas de negación, ´, disyunción, , y conjunción, , sobre proposiciones particulares dadas (representadas por letras de constantes a, b, …) y variables proposicionales p, q, … (que designan proposiciones simples arbitrarias no especificadas) . Por ejemplo: a = Juan mintió p  a , o sea : p´  a de la forma p’  a donde "a" es la constante (proposición dada) "Juan mintió".

Definición: Se dice que una expresión lógica está en forma normal disyuntiva si está escrita como una disyunción, en la cual todos los términos son conjunciones de letras de variables proposicionales. De modo similar, se dice que una expresión lógica está en forma normal conjuntiva si está escrita como una conjunción de disyunciones de letras de variables proposicionales. Entre los ejemplos de formas normales disyuntivas se cuentan las disyunciones (p.q) v (p . ~ q), p v (q. r) y ~p v V. La disyunción ~ (p . q) v r, por otra parte, no está en forma normal porque contiene una subexpresión no atómica negada. Sólo se puede negar las subexpresiones subatómicas, y las expresiones atómicas negadas son letras de variables proposicionales. Entre los ejemplos de formas normales conjuntivas se cuentan p .(q v r) y p .F. Sin embargo, p . (r v (p . q)) no está en forma normal conjuntiva, porque la disyunción (r v (p. q)) contiene una conjunción como subexpresión. Para poder calificarse como forma normal conjuntiva, las disyunciones no deben de tener ninguna conjunción como subexpresión . Los literales, tales como p v ~ p son simultáneamente formas normales conjuntivas y formas normales disyuntivas, y también lo son V y F.

definición: Toda fórmula proposicional sin constantes es una forma enunciativa.

Teorema: Toda forma enunciativa es reducible a forma normal disyuntiva o forma normal conjuntiva. Se requieren tres pasos para obtener una forma normal conjuntiva a través de manipulaciones algebraicas. 1. Eliminar todas las  y  . 2. Si la expresión en cuestión contiene cualquier subexpresión compuesta negada, elimine la negación utilizando la ley de doble negación o use las leyes de De Morgan para reducir el alcance de la negación. 3. Una vez encontrada la expresión sin ninguna subexpresión compuesta negada, use las dos leyes siguientes para reducir el alcance de V. x v (y.z ) = (x v y). (x v z) (1.1) (x.y) v z = (x v y). (y v z) (1.2)

Las leyes 1.1 y 1.2 se infieren de las leyes conmutativas y distributivas Ejemplo: A partir de la fórmula ~((p v ~q) . ~r) su forma normal conjuntiva puede hallarse a través de la siguiente derivación: ~ ((p v ~ q) . ~r) = ~ (p v ~ q ) v ~ ~r De Morgan = ~ (p v ~ q ) v r Doble negación = (~p . ~ ~ q ) v r De Morgan = (~p . q ) v r Doble negación = (~p v r) . (q v r) Por (1.2)

Tablas de verdad y formas normales disyuntivas Las conectivas determinan funciones de verdad simples. Usando las tablas de verdad de las conectivas, podemos construir una tabla de verdad para cualquier forma enunciativa dada. Nos referimos a una tabla que indique, para cualquier asignación dada de valores de verdad a las variables proposicionales que aparezcan en la forma enunciativa, el valor de verdad que tome ésta. Ésta tabla de verdad es una representación gráfica de una función de verdad. Así pues, toda forma enunciativa da lugar a una función de verdad, cuyo número de argumentos es igual al número de variables proposicionales distintas que aparezcan en la forma enunciativa. Se puede transformar cualquier tabla de verdad en una expresión lógica. La expresión obtenida de esta forma está ya en una forma normal disyuntiva. De hecho, el método conceptualmente más fácil para encontrar la forma normal de una expresión es el uso de las tablas de verdad. Desdichadamente, las tablas de verdad crecen exponencialmente con el numero de variables, lo que hace que este método no sea atractivo para expresiones con muchas variables. En general una tabla de verdad proporciona los valores de verdad de alguna proposición para todas las posibles asignaciones. El valor de verdad de f depende de n variables p, q, …. Esto convierte a f en función de verdad, con las variables como argumentos. Para convertir una función dada por su tabla de verdad en una expresión lógica se utilizan términos mínimos (minterm). Un término mínimo (minterm) es una conjunción de literales en los cuales cada variable se representa exactamente una sola vez. Todo término mínimo es verdadero exactamente para una asignación. Cualquier desviación de esta asignación daría falso este término mínimo particular. Una disyunción de términos mínimos es verdadera sólo si al menos uno de sus términos mínimos constituyentes es verdadero. Si una función, tal como f, está dada por una tabla de verdad, sabemos exactamente para qué asignaciones es verdadera. Por consiguiente, podemos seleccionar los términos mínimos que hacen a la función verdadera y formar la disyunción de estos términos mínimos. Debido a que los términos mínimos son conjunciones, se puede expresar la función en forma normal disyuntiva. Realmente, tenemos un tipo especial de forma normal, la forma normal disyuntiva completa o plena.

Definición: Una fórmula proposicional en n variables proposicionales en forma normal, puede contener hasta 2n términos, pues en cada término, cada letra puede aparecer en dos formas: p o p´. Si contiene los 2n términos se llama completa. La forma normal disyuntiva completa no suele ser la disyunción de conjunciones mas corta posible para expresar una función dada. De hecho se puede simplificar esta en la forma habitual. En el ejemplo anterior sería: f = (p  r) v (~ q  r)

Formas normales conjuntivas y complementación Si A es una expresión cualquiera se obtiene el complementario de A formando primero el dual de A y reemplazando todos las letras de variables proposicionales por sus complementarias. De hecho el complementario de A es siempre la negación de A, y la complementación es un modo eficiente de negar una expresión. Si dos expresiones A y B son lógicamente equivalentes, también lo son sus negaciones y, con ellas sus complementarios. Para encontrar el dual a partir del complementario, sólo se necesita reemplazar todos los literales por sus complementarios. Esta operación convierte tautologías en tautologías. En resumen, si A  B, entonces comp. A  comp. B y como su consecuencia el dual de A  B es una equivalencia lógica. La complementación puede utilizarse para hallar la forma normal conjuntiva a partir de una tabla de verdad de cualquier función f. Primero se determina la forma normal disyuntiva de ~ f. Si la forma normal disyuntiva resultante es A, entonces A  ~ f , y el complementario de A, siendo la negación de A, debe ser lógicamente equivalente a f .

Teorema:

• La forma normal completa disyuntiva en n variables proposicionales p1,…, pn resulta desarrollando por las propiedades distributivas la tautología (p1 v p1’)  …  (pn v pn’) y para cada sistema de reemplazos de las variables proposicionales p1, … pn por constantes (proposiciones dadas), uno y sólo uno de los términos del desarrollo de una proposición verdadera, y las demás proposiciones falsas.
• La forma normal completa conjuntiva en n variables proposicionales p1,…,pn resulta desarrollando por las propiedades distributivas la contradicción (p1  p1’) v … v (pn  pn’) y para cada sistema de reemplazos de las variables proposicionales p1, …, pn por constantes (proposiciones dadas), uno y sólo uno de los términos del desarrollo de una proposición falsa, y las demás proposiciones verdaderas

Por ejemplo, desarrollando (p v p´)  (q v q´), se obtiene la forma normal disyuntiva completa en p, q: (p  q) v (p´  q) v (p  q´) v (q´  q´) Haciendo en ella el reemplazo p = El Sol es un astro y q = Colón era japonés resulta el valor de verdad V para el tercer término, y valor de verdad F para los otros tres.