Trabajo Final de Lógica y Semánticas Formales

Indice
1.
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.