viernes, 17 de junio de 2011

Evaluación de expresiones lógicas booleanas en cortocircuito

Cuando un compilador o intérprete evalúa una expresión booleana, la mayoría de ellos lo hacen aplicando una optimización conocida como cortocircuito. Esta optimización, en la mayoría de los casos ahorra bastante trabajo en la evaluación de la expresión, pero si alguno de los términos implicados debe tener un efecto colateral, es muy posible que no lo obtengamos. No es elegante incluir términos con efectos colaterales en expresiones booleanas.
Antes de nada, vamos a conocer qué es la evaluación en cortocircuito.
Imagina que tenemos cuatro variables booleanas: a, b, c y d, y operamos con ellas de esta manera:











Es decir,  asignamos unos valores a a, b y c, y a d le asignamos la operación AND de las otras tres. Para que d tuviera un valor true, sería necesario que tanto a como b como c tuvieran un valor true.
Pues bien, cuando el compilador o el intérprete resuelven la cuarta línea y comprueban que a tiene un valor false no siguen comprobando b ni c, ya que si a es falso, d también lo será, sin necesidad de terminar de evaluar la expresión. Eso es una evaluación en cortocircuito.
Análogamente también se puede aplicar con la operación OR. Mira este ejemplo:

 








Cuando el compilador o el intérprete resuelven la cuarta línea, al comprobar que a es true no siguen comprobando b ni c, ya que el resultado será true independientemente de sus valores.
Esta optimización es muy sensata, y la aplican prácticamente todos los compiladores e intérpretes modernos. Sin embargo, tiene un cierto peligro.
En los ejemplos anteriores hemos utilizado variables booleanas en la expresión. Sin embargo, también podíamos haber utilizado funciones o métodos que devolvieran un booleano. Si esa función o método tuviera algún efecto colateral, no se puede garantizar su ejecución, ya que dependerá de si el compilador aplica el cortocircuito o no.
Observa este ejemplo, como de costumbre, en C#:
 
 Al hacer esta prueba con el compilador de C#, y tal y como esperábamos, sale un 1 por la consola. Se ha aplicado el cortocircuito. A la vista del código, cualquiera podría esperar un 2, y sin embargo no es así. Pero lo peor de todo no es eso... es que NO PODEMOS GARANTIZAR si se ejecutará prueba () o no. Quizá coja este código, lo meta en otro compilador que no aplique el cortocircuito y resulta que si se ejecuta prueba ().
La cuestión no tendría importancia si en el contexto de mi programa, la ejecución o no del método prueba () en ese momento no influyera en ningún otro aspecto. Pero en este caso, el método prueba () tiene un EFECTO COLATERAL: cambia el valor de una variable.
Obviamente, y como programadores elegantes, no podemos dejar que ese efecto se produzca unas veces sí y otras no, según el compilador aplique la optimización o no.
Así pues, si un método tiene efectos colaterales, no estará involucrado en expresiones booleanas.
Una forma más elegante de lograr lo mismo es esta:


jueves, 16 de junio de 2011

Tablas de verdad

Las tablas nos manifiestan los posibles valores de verdad de cualquier proposición molecular, así como el análisis de la misma en función de las proposiciones que la integran, encontrándonos con los siguientes casos:
Verdad Indeterminada o Contingencia
Se entiende por verdad contingente, o verdad de hecho, aquella proposición que puede ser verdadera o falsa, según los valores de las proposiciones que la integran. Sea el caso:      A /\ (A \/ C).
Su tabla de verdad se construye de la siguiente manera:
Ocho filas que responden a los casos posibles que pueden darse según el valor V o F de cada una de las proposiciones A, B, C. (Columnas 1, 2, 3)
Una columna (Columna 4) en la que se establecen los valores de B \/ C aplicando la definición del disyuntor a los valores de B y de C en cada una de las filas. (Columnas 2,3 → 4)
Una columna (columna 5) en la que se establecen los valores resultantes de aplicar la definición de la conjunción entre los valores de A (columna 1) y valores de la columna B \/ C, (columna 4) que representarán los valores de la proposición completa A /\ (B \/ C), cuyo valor de verdad es V o F según la fila de los valores de A, B, y C que consideremos. (Columnas 1,4 → 5)
Donde podemos comprobar cuándo y por qué la proposición A /\ (B \/ C) es V y cuándo es F.
Contradicción
Se entiende por proposición contradictoria, o contradicción, aquella proposición que en todos los casos posibles de su tabla de verdad su valor siempre es F. Dicho de otra forma, su valor F no depende de los valores de verdad de las proposiciones que la forman, sino de la forma en que están establecidas la relaciones de unas con otras. Sea el caso: [(A/\B)/\¬ (A\/B)]/\C

Procederemos de manera similar al caso anterior. Aplicamos (Columna 4) la definición de conjunto a los valores de A y B. (columnas 1,2 → 4) Después aplicamos la definición de disyuntor a los valores de A y B. (columnas 1,2 → 5) Aplicamos en la columna siguiente (Columna 6) el negador a los valores de la columna anterior. Aplicamos el conjunto a los valores de la columna (A/\B) (Columna 4) con los de la columna ¬(A\/B).(Columna 6) Por último (Columna 8) aplicamos el conjunto a los valores de la columna de C (Columna 3) con la columna última (Columna 7) cuyo resultado nos da los valores de [(A/\B)/\¬ (A\/B)]/\C, siempre falsos cualquiera que sea la fila que consideremos.
Tautologías
Se entiende por proposición tautológica, o tautología, aquella proposición que en todos los casos posibles de su tabla de verdad su valor siempre es V. Dicho de otra forma, su valor V no depende de los valores de verdad de las proposiciones que la forman, sino de la forma en que están establecidas las relaciones sintácticas de unas con otras. Sea el caso: [(A→B)/\ (B→C)] → (A→C)




Siguiendo la mecánica algorítmica de la tabla anterior construiremos su tabla de verdad:

lunes, 13 de junio de 2011

Simplificación de expresiones

 Una expresión es una colección significativa de números, variables y signos de operación.
Ejemplos de Expresiones
    2p + 5
    4a -  6
    3x-9+2
No son expresiones:
    -4  -  · c        No tiene sentido la resta y multiplicación
    3b + 4= 9     El signo de "=" hace que no sea expresión. Esto es una oración matemática.
Las variables son expresadas por letras, que tienen un valor desconocido.
Ej: 4a        a es la variable
      3b        b es la variable
El coeficiente es el número que está siempre localizado antes de la variable; significa que el número está multiplicado por la variable.
Por ejemplo:
                      3a;   3 es la coeficiente
                     -2c;  -2 es la coeficiente
                       X   ;   1 es la coeficiente
 Un término es un grupo de variables y coeficientes dividido por signos de suma y resta.
Ej. 4x + 2y
       4x es un término
       2y es un término
Término Semejante:
    Un término es  semejante a otro término si tiene la misma variable o variables con el mismo exponente o exponentes.
Ej.  2a  + 3a     son términos semejantes
      3b  + 4d     no son términos semejantes
       3c + 3a      no son términos semejantes
Simplificación de Expresiones:
La simplificación de expresiones consiste en agrupar los términos semejantes y simplificarlo, si es posible.
Para simplificar la expresión se suman o restan los coeficientes de los términos semejantes.
Por ejemplo:    4a - 3b + 2a
4a y 2a son términos semejantes
-3b   no es término semejante
4a + 2a - 3b   (Se agrupan los términos semejantes)
6a - 3b           (Se resuelve la expresión)
Ejemplo:
2a + 4c
La expresión no se puede simplificar, ya que 2a y 4c no son términos  semejantes.  Entonces, la expresión ya está simplificada.
Otro ejemplo:
3x + 2y - 9 + 4x +6
3x, 4x son términos semejantes
2y
 -9, 6 son términos semejantes
Reagrupar términos semejantes:
3x + 4x  + 2y  -  9 + 6
7x  + 2y - 3
Ejemplo:
2xy + 4z -9 + 2y -xy
2xy y 2y No son términos semejantes.  Para ser términos semejantes, deben tener exactamente las mismas variables con los mismos exponentes.
2xy, -xy           son términos semejantes
4z
9x
2y
2xy - xy + 4z - 9x+ 2y
      xy + 4z - 9x + 2y
 Ejercicios:
Determinar el coeficiente.
                    Coeficiente
1.    4x               ____
2.    -9z              ____
3.    x                 ____
4.    -c                ____

Determinar si es expresión o no.
1.     3p + 6
2.     4x +  · 3
3.     2a - 9
4.    4x + 2 = 8

Determinar si son términos semejantes.
                          Sí o No
1. 4a, 3a             _____
2. -2c, p              _____
3.  3a,  3x           _____
4. 4d, 3d             _____
 
Simplifica las siguientes expresiones.
1. 4z + 3y - z
2.  9x + 6y - 9x
3.  4x + 5z + 4
4.  9xy + 3x - 2y
5.  4c + 5d - c + d
6.  9x - 7 + 3 + z
7. 4xy + 9x - 3y + z + xy
8.9p + 3q +r - 9 pqr
9. 4ws + 7wx - 3wx + 4
10. 9x - 3xyz + y + 7x + 5
  Soluciones
Determinar la coeficiente.
 1. 4x,  la coeficiente es 4.
 2. -9z, la coeficiente es -9
 3. x , la coeficiente es 1
 4. -c, la coeficiente es -1
Determinar si es expresión o no.
1. 3p + 6, es una expresión
2. 4x + · 3, no es una expresión, ya que contiene suma y multiplicación, y no tiene sentido.
3. 2a - 9, es una expresión
4. 4x + 2 = 8, no es expresión, ya que contiene un signo de igual " = " y esto hace que no sea expresión
 
Determinar si son términos semejantes.
1. 4a y 3a  son términos semejantes.
2. -2c y p no son términos semejantes, c y p son variables diferentes.
3. 3a y 3x no son términos semejantes, parecen serlo por tener los coeficientes iguales, pero las variables son diferentes.
4. 4d y 3d son términos semejantes.
 
Simplifica las siguientes expresiones.
1. 4z + 3y - z
    4z - z + 3y    (Se agruparon los términos semejantes)
    3z + 3y        (Solución)
2. 9x + 6y - 9x
 9x - 9x + 6y  (Se agruparon los términos semejantes)
 0x + 6y
  6y    (Solución)
 

Evaluación con expresiones con paréntesis

Cuando en una expresión concurre más de una operación, los paréntesis indicarán prioridad, es decir, la operación encerrada entre paréntesis se realizará en primer lugar. Además, algunos operadores tendrán preferencia sobre otros. Por ejemplo, en la operación a + b / c, primero se realizará b / c y posteriormente se le sumará a. En caso de que el programador quiera que se sume primero a y b para posteriormente dividir por c, tendríamos que hacer (a + b) / c. Si todos los operadores de una expresión tienen la misma prioridad, la operación se hará de izquierda a derecha, salvo cuando tengamos exponenciales, en tal caso, el orden será de derecha a izquierda, por ejemplo, al hacer 2**3**2 resulta el valor 2**9 = 512.
En la siguiente tabla veremos las prioridades que existen entre los operadores:

Hacer a + b + c + d es lo mismo que hacer (a + b) + (c + d) pero en el primer caso el ordenador sumaría a y b, el resultado se lo sumaría a c y este a d, sin embargo en el segundo caso haría a + b y c + d y sumaría ambos resultados.
Al realizar operaciones hay que tener cuidado con el tipo y la clase de las variables a operar, ya que por ejemplo, la división de dos enteros truncaría el resultado, es decir, 3 / 2 no daría 1.5 sino 1. El motivo de esto es que el resultado de dividir dos enteros es un entero. Por tanto, no sería lo mismo i / 2 que 0.5 * i, siendo i un entero.

domingo, 12 de junio de 2011

Leyes Basicas de Boole

Leyes del álgebra de Boole 
  La manera más obvia para simplificar expresiones booleanas es manipular de la misma manera como normal expresiones algebraicas son manipulados. En cuanto a las relaciones de la lógica en forma digital, un conjunto de reglas para la manipulación simbólica es necesario para resolver las incógnitas.
Un conjunto de normas formuladas por el matemático George Boole Inglés describir ciertas proposiciones cuyo resultado podría ser verdadera o falsa. Con respecto a la lógica digital, estas normas se utilizan para describir los circuitos cuyo estado puede ser, 1 (verdadero) o 0 (falso). Para entender plenamente este, la relación entre la puerta, la puerta OR y NOT puerta debe ser apreciado. Una serie de normas se pueden derivar de estas relaciones en el Cuadro 1 se muestra.
P1: X = 0 o X = 1
P2: 0. 0 = 0
P3: 1 + 1 = 1
P4: 0 + 0 = 0
P5: 1. 1 = 1
P6: 1. 0 = 0. 1 = 0
P7: 1 + 0 = 0 + 1 = 1

Leyes del álgebra de Boole
las leyes básicas booleanas. Tenga en cuenta que cada ley tiene dos expresiones, (a) y (b). Esto se conoce como dualidad. Estos se obtienen cambiando cada Y (.) A O (+), todos los O (+) para Y (.) Y un todo a 0 y vice versa.
Se ha convertido en convencionales para la gota. (Y el símbolo), es decir AB se escribe como AB.
T1: Ley conmutativa
 (A) A + B = B + A
 (B) AB = BA
 T2: Ley Asociado
 (A) (A + B) + C = A + (B + C)
 (B) (AB) C = A (BC)
 T3: Derecho de distribución
 (A) A (B + C) = AB + AC
 (B) A + (BC) = (A + B) (A + C)
 T4: Ley de Identidad
 (A) A + A = A
 (B) AA = A  
 T5: 
(A)
 (B)
 T6: Ley de Redundancia
 (A) AB = A +
 (B) A (A + B) = A
T7: 
 (A) 0 + A = A
 (B) 0 A = 0
 T8:
 (A) 1 + A = 1
 (B) 1 A = A  
 T9: 
 (A) 
 (B)   
 T10: 
 (A) 
 (B) 

 T11: Teorema de De Morgan
 (A)  
 (B) 
 Ejemplos
 Demostrar T10: (a) 
 (1) Algebraicamente:
 (2) Uso de la tabla de verdad:

 Uso de las leyes dadas anteriormente, expresiones complicadas se puede simplificar.

Los Elementos AND, OR, NOt

 Los Elementos de Circuitos Lógicos AND, OR, NOt
Los circuitos de conmutación y temporización, o circuitos lógicos, forman la base de cualquier dispositivo en el que se tengan que seleccionar o combinar señales de manera controlada. Entre los campos de aplicación de estos tipos de circuitos pueden mencionarse la conmutación telefónica, las transmisiones por satélite y el funcionamiento de las computadoras digitales.
La lógica digital es un proceso racional para adoptar sencillas decisiones de ‘verdadero’ o ‘falso’ basadas en las reglas del álgebra de Boole. El estado verdadero se representado por un 1, y falso por un 0, y en los circuitos lógicos estos numerales aparecen como señales de dos tensiones diferentes. Los circuitos lógicos se utilizan para adoptar decisiones específicas de ‘verdadero-falso’ sobre la base de la presencia de múltiples señales ‘verdadero-falso’ en las entradas. Las señales se pueden generar por conmutadores mecánicos o por transductores de estado sólido. La señal de entrada, una vez aceptada y acondicionada (para eliminar las señales eléctricas indeseadas, o ruidos), es procesada por los circuitos lógicos digitales. Las diversas familias de dispositivos lógicos digitales, por lo general circuitos integrados, ejecutan una variedad de funciones lógicas a través de las llamadas puertas lógicas, como las puertas OR, AND y NOT y combinaciones de las mismas (como ‘NOR’, que incluye a OR y a NOT). Otra familia lógica muy utilizada es la lógica transistor-transistor. También se emplea la lógica de semiconductor complementario de óxido metálico, que ejecuta funciones similares a niveles de potencia muy bajos pero a velocidades de funcionamiento ligeramente inferiores. Existen también muchas otras variedades de circuitos lógicos, incluyendo el hoy obsoleta lógica reóstato-transistor y la lógica de acoplamiento por emisor, utilizada para sistemas de muy altas velocidades.
Los bloques elementales de un dispositivo lógico se denominan puertas lógicas digitales. Una puerta Y (AND) tiene dos o más entradas y una única salida. La salida de una puerta Y es verdadera sólo si todas las entradas son verdaderas. Una puerta O (OR) tiene dos o más entradas y una sola salida. La salida de una puerta O es verdadera si cualquiera de las entradas es verdadera, y es falsa si todas las entradas son falsas. Una puerta INVERSORA (INVERTER) tiene una única entrada y una única salida, y puede convertir una señal verdadera en falsa, efectuando de esta manera la función negación (NOT). A partir de las puertas elementales pueden construirse circuitos lógicos más complicados, entre los que pueden mencionarse los circuitos biestables (también llamados flip-flops, que son interruptores binarios), contadores, comparadores, sumadores y combinaciones más complejas.
En general, para ejecutar una determinada función es necesario conectar grandes cantidades de elementos lógicos en circuitos complejos. En algunos casos se utilizan microprocesadores para efectuar muchas de las funciones de conmutación y temporización de los elementos lógicos individuales. Los procesadores están específicamente programados con instrucciones individuales para ejecutar una determinada tarea o tareas. Una de las ventajas de los microprocesadores es que permiten realizar diferentes funciones lógicas, dependiendo de las instrucciones de programación almacenadas. La desventaja de los microprocesadores es que normalmente funcionan de manera secuencial, lo que podría resultar demasiado lento para algunas aplicaciones. En tales casos se emplean circuitos lógicos especialmente diseñados.
Ejemplos de aquellos sistemas analógicos que ahora se han vuelto digitales.
Fotografías. La mayoría de las cámaras todavía hacen uso de películas que tienen un recubrimiento de haluros de plata para grabar imágenes. Sin embargo, el incremento en la densidad de los microcircuitos o "chips" de memoria digital ha permitido el desarrollo de cámaras digitales que graban una imagen como una matriz de 640 x 480, o incluso arreglos más extensos de pixeles donde cada pixel almacena las intensidades de sus componentes de color rojo, verde y azul de 8 bits cada uno. Esta gran cantidad de datos, alrededor de siete millones de bits en este ejemplo puede ser procesada y comprimida en un formato denominado JPEG y reducirse a un tamaño tan pequeño como el equivalente al 5% del tamaño original de almacenamiento dependiendo de la cantidad de detalle de la imagen. De este modo las cámaras digitales dependen tanto del almacenamiento como del procesamiento digital.
Grabaciones de video. Un disco versátil digital de múltiples usos (DVD por las siglas de digital versatile disc) almacena video en un formato digital altamente comprimido denominado MPEG-2. Este estándar codifica una pequeña fracción de los cuadros individuales de video en un formato comprimido semejante al JPEG y codifica cada uno de los otros cuadros como la diferencia entre éste y el anterior. La capacidad de un DVD de una sola capa y un solo lado es de aproximadamente 35 mil millones de bits suficiente para grabar casi 2 horas de video de alta calidad y un disco de doble capa y doble lado tiene cuatro veces esta capacidad.
Grabaciones de audio. Alguna vez se fabricaron exclusivamente mediante la impresión de formas de onda analógicas sobre cinta magnética o un acetato (LP), las grabaciones de audio utilizan en la actualidad de manera ordinaria discos compactos digitales (CD. Compact Discs). Un CD almacena la música como una serie de números de 16 bits que corresponden a muestras de la forma de onda analógica original se realiza una muestra por canal estereofónico cada 22.7 microsegundos. Una grabación en CD a toda su capacidad (73 minutos) contiene hasta seis mil millones de bits de información.
Carburadores de automóviles. Alguna vez controlados estrictamente por conexiones mecánicas (incluyendo dispositivos mecánicos "analógicos" inteligentes que monitorean la temperatura, presión. etc.), en la actualidad los motores de los automóviles están controlados por microprocesadores integrados.
Ejemplo de un sistema electrónico analógico
Un ejemplo de sistema electrónico analógico es el altavoz, que se emplea para amplificar el sonido de forma que éste sea oído por una gran audiencia. Las ondas de sonido que son analógicas en su origen, son capturadas por un micrófono y convertidas en una pequeña variación analógica de tensión denominada señal de audio. Esta tensión varía de manera continua a medida que cambia el volumen y la frecuencia del sonido y se aplica a la entrada de un amplificador lineal. La salida del amplificador, que es la tensión de entrada amplificada, se introduce en el altavoz. Este convierte, de nuevo, la señal de audio amplificada en ondas sonoras con un volumen mucho mayor que el sonido original captado por el micrófono.