Operaciones Logicas

FÓRMULA LÓGICA

Una fórmula lógica es la representación simbólica de una proposición compuesta, las cuales están conformadas por proposiciones simples, conectivos lógicos y signos de agrupación.

Al evaluar una fórmula se confecciona su tabla de verdad. Ejemplo:

Se tiene las siguientes proposiciones:

p: Abigail Alcalde Flores gana la partida de damas.

q: Abigail Alcalde Flores recibe el premio.

Una proposición compuesta empleando p y q será:

"Si Abigail Alcalde Flores gana la partida entonces recibe el premio", la cual se representa simbólicamente así: p Þ q.

Expresiones como: ~ p Þ ~ q

(p Ú q) Þ ~ q

~ (p Ù q) Û (~ p Ú q)

reciben el nombre de fórmulas lógicas.

Al evaluar una Fórmula se confecciona su Tabla de Verdad.

•Si en esta tabla todos los valores de verdad son V, tal fórmula es una TAUTOLOGÍA.
•Si en esta tabla todos los valores de verdad son F, tal fórmula es una CONTRADICCIÓN.
•Si en esta tabla, algunos de los valores de verdad son V y otros son F, tal fórmula es una CONTINGENCIA.
Al evaluar una fórmula debemos tener en cuenta un orden en las operaciones lógicas a realizarse. Empezamos con las operaciones encerradas por los paréntesis interiores, siguen todas las negaciones y luego se avanza de izquierda a derecha.

Es recomendable identificar el conectivo principal de la fórmula que representa la operación final a realizarse. Si en el interior de un paréntesis alguna proposición simple esta precedida por una negación, primero se opera ésta.

He aquí algunos ejemplos resueltos:

v v v v v v Desarrollamos (1) condicional

v v f v f f Desarrollamos (2) conjunción

v f v f v f Desarrollamos (3) Bicondicional del resultados de

v f f f v f (1) y (2)

f v v v v v

f v f v f f

f f v v f f

f f f v f f

(1) (3) (1)

1.p q r ( p Þ q ) Û ( q Ù r )
v v f v v v Desarrollamos (1) conjunción

v f v v v v (2) después de haber negado (1)

f v v f v v Desarrollamos (3) disyunción

f v v f f f Desarrollamos (4) condicional del resultado de

(2) (1) (4) (3) (2) y (3)

CUANTIFICADORES

Es convertir en un enunciado abierto en proposición.

Enunciado abierto.-

•Es aquel enunciado (frase u oración) que incluye una o varias variables, y de acuerdo a la que emplee podrá ser falso o verdadero.
•Es aquella expresión que tiene al menos una variable la que al ser reemplazada por constantes transforma el enunciado abierto en una proposición.
•Si empleamos x como variable, un enunciado abierto se representa así: p(x), lo que leemos como " p de x ".
Ejemplo:

Sea el enunciado abierto:

P(x) = "x +1 es un número múltiplo de 2 "

Ahora damos valores a x:

•Si x = 3, P (3) = 3 + 1 = 4 "4 es múltiplo de 2", proposición verdadera.
•Si x = 4, P (4) = 4 + 1 = 5 "5 es múltiplo de 2", proposición falsa.
•Si x = 5, P (5) = 5 + 1 = 6 "6 es múltiplo de 2", proposición verdadera.
Al enunciado abierto también se le llama Función Proposicional.

Existen dos tipos de cuantificadores:

•Cuantificador Universal
El enunciado abierto es p(x): "x + 1 es un número múltiplo de 2 "; si cuantificamos universalmente escribimos:

•" todo x + 1 es un número múltiplo de 2 "
•" para todo x + 1 es un número múltiplo de 2 "
•" para cualquier x + 1 es un número múltiplo de 2 "
Esta ya es una proposición pero FALSA porque hay números x + 1 que no necesariamente son múltiplos de 2.

" significa "para todo", "todo" o "para cualquier"


•Cuantificador Existencial
El enunciado abierto es p(x): "x + 1 es un número múltiplo de 2 "; si cuantificamos existencialmente escribimos:

•" Existe por lo menos un número x + 1 es un múltiplo de 2 "
Esta ya es una proposición aunque ahora si VERDADERA porque por lo menos existe un número que reemplazado por x en x + 1 nos da un múltiplo de 2.

$ significa "existe por lo menos" o "existe"

PROPOSICIONES LÓGICAS EQUIVALENTES

Si dos proposiciones p y q tienen tablas de verdad idénticas entonces podemos afirmar que tales proposiciones son equivalentes:

Esto se simboliza p º q

Ejemplo: La proposición compuesta p Þ q es equivalente a la proposición compuesta.

( ~ p) Ú q

p Þ q º (~ p) Ú q

Entonces en una fórmula lógica podemos ahorrar tiempo y espacio si reemplazamos:

p Þ q º ( ~ p) Ú q o viceversa.

Las equivalencias lógicas más importantes son:

1.p Ú p º p
2.p Ú V º V
3.p Ú F º p
4.p Ú q º q Ú p
5.p Ú (~ p) º V
6.~ (~ p) º p
7.( p Ú q ) Ú r º p Ú ( q Ú r )
8.p Ú ( q Ù r ) º ( p Ú q ) Ù ( p Ú r )
9.p Ù p º p
10.( p Ù q ) Ù r º p Ù ( q Ù r )
11.p Ù ( q Ú r ) º ( p Ù q ) Ú ( p Ù r )
12.p Ù F º F
13.p Ù V º p
14.p Ù (~ p) º F
15.p Ù q º q Ù p
16.~ ( p Ú q ) º (~ p) Ù (~ q)
17.~ ( p Ù q ) º (~ p) Ú (~ q)
18.p Þ q º (~ p) Ú q
19.p Þ q Þ ( ~ q) Þ ( ~ p)
20.p Ù ( p Ú q ) º p
21.p Ú ( p Ù q ) º p
22.p Û q º ( p Þ q ) Ù ( q Þ p )
23.p Û q º ( p Ù q ) Ú [ ( ~ p ) Ù ( ~ q ) ]
24.~ V º F ; ~ F º V

PROBLEMAS PROPUESTOS

a.Los números pares son divisible por 2.
b.Los números impares son divisibles por 2.
c.La semana tiene 8 días.
d.Cuan profundo es mi amor.
e.Mario Vargas Llosa es español.
f.¡Tú puedes, no desistas!
g.Lima, la tres veces coronada ciudad de los reyes.
h.El cuadrado es un cuadrilátero.
i.No todo número primo es impar.
j.Alberto Fujimori, por qué has llegado tarde.
k.¡Has ganado una computadora!
l.El año tiene 12 meses.
m.Todas las semanas tiene 7 días.
n.Alan García Pérez viajo a Roma o Brasil.
o.Si me caso, entonces no seré soltero.
p.No es cierto que la ciudad de Lima está en la costa.
q.El Sol es un astro o el día tiene 24 horas.
r.2 + 3 = 7 ó 22 + 32 = 52
s.6 es mayor que 7, ó 5 es menor que 8.
t.El triángulo tiene 3 lados o el cuadrado solo 3 lados.
II.Indique cuál de las siguientes expresiones es una proposición, si fuera así cual de ellas son proposiciones simples y cuales son proposiciones compuestas. Señale además su valor de verdad correspondiente.
[ ( ~ p Ú ~ q ) Þ ( ~ r Ú q ) ] Þ ( p Þ ~ r )

III.Sean p, q y r proposiciones tales que p es verdadera (v), q es falsa (F) y r es falsa (F). Indique el valor de verdad de la proposición:
IV.De las siguientes proposiciones ¿Cuáles son tautologías?
a.( p Þ q ) Þ [ ( ~ p ) Ú q ]
b.[ ~ ( p Ù q ) Þ ( ~ q Ù q ) ] Þ p
c.[ ( p Ù q ) Ú ( ~ q ) ] Þ ~ p

i.( p Û q ) Þ ( r Ù s )
ii.( p Ù q ) Þ ( r Û s )
iii.~ p Û ( r Ù q )
iv.~ q Û ( p Ù s )
v.~ s Û ( p Ú q )
II.Sabiendo que las proposiciones p y r son proposiciones verdaderas y las proposiciones q y s son proposiciones falsas; indicar cuantas de las siguientes proposiciones son falsas:
◦( p Ú q )
◦( p Þ q ) Ù q
◦[ ( p Ú q ) Þ ( p Ù q ) ] Û ( p Þ ~ q )
◦( ~ p ) Þ ( p Ú q )
◦( ~ q ) Û ( p Ù ~ p )

Tipos de proposiciones

En adelante cuando hablemos de proposiciones, éstas serán lógicas. Si son abiertas, significará que el conjunto de sustituciones está bien definido y la harán verdadera o falsa. Para operar con las proposiciones, éstas se clasifican en dos tipos: Simples y Compuestas, dependiendo de como están conformadas.
Proposiciones Simples
Son aquellas que no tienen oraciones componentes afectadas por negaciones ("no") o términos de enlace como conjunciones ("y"), disyunciones ("o") o implicaciones ("si . . . entonces"). Pueden aparecer términos de enlace en el sujeto o en el predicado, pero no entre oraciones.

Proposiciones Compuestas
Una proposición será compuesta si no es simple. Es decir, si está afectada por negaciones o términos de enlace entre oraciones componentes.

Ejemplos
Ensayemos una lista clasificada y luego algunas aclaraciones:
1) Carlos Fuentes es un escritor. (Simple)
2) Sen(x) no es un número mayor que 1. (Compuesta)
3) El 14 y el 7 son factores del 42. (Simple)
4) El 14 es factor del 42 y el 7 también es factor del 42. (Compuesta)
5) El 2 o el 3 son divisores de 48. (Simple)
6) El 2 es divisor de 48 o el 3 es divisor de 48. (Compuesta)
7) Si x es número primo, entonces x impar. (Compuesta)
8) Si x > 10, entonces 2x - 3 > 16. (Compuesta)
9) No todos los números primos son impares. (Compuesta)

Algunas aclaraciones

a) No obstante que los ejemplos 3) y 4) gramaticalmente significan lo mismo, operativamente se consideran distintos. Similarmente 5) y 6).
b) A veces proposiciones como la 8), aparecen escritas de la forma: 2x - 3 > 16, si x > 10.

Logica Combinatoria

La lógica combinatoria

La lógica combinatoria es la lógica última y como tal puede ser un modelo simplificado del cómputo, usado en la teoría de computabilidad (el estudio de qué puede ser computado) y la teoría de la prueba (el estudio de qué se puede probar matemáticamente.)

La teoría, a causa de su simplicidad, captura las características esenciales de la naturaleza del cómputo. La lógica combinatoria (LC) es el fundamento del cálculo lambda, al eliminar el último tipo de variable de éste: la variable lambda. En LC las expresiones lambda (usadas para permitir la abstracción funcional) son substituidas por un sistema limitado de combinadores, las funciones primitivas que no contienen ninguna variable libre (ni ligada). Es fácil transformar expresiones lambda en expresiones combinatorias, y puesto que la reducción de un combinador es más simple que la reducción lambda, LC se ha utilizado como la base para la puesta en práctica de algunos lenguajes de programación funcionales no-estrictos en software y hardware.

Puesto que la abstracción es la única manera de fabricar funciones en el cálculo lambda, algo debe sustituirlo en el cálculo combinatorio. En vez de la abstracción, el cálculo combinatorio proporciona un conjunto limitado de funciones primitivas y de las cuales las otras funciones pueden ser construidas.

Términos combinatorios
Un término combinatorio tiene una de las formas siguientes:

V
P
(E1 E2)
donde V es una variable, P es una de las funciones primitivas, E1 y E2 son términos combinatorios. Las funciones primitivas mismas son combinadores, o funciones que no contienen ninguna variable libre.

Ejemplos de combinadores
El ejemplo más simple de un combinador es I, el combinator identidad, definido por

(I x) = x
para todos los términos x. otro combinator simple es K, que produce funciones constantes: (K x) es la función que, para cualquier argumento, devuelve x, así que decimos

((K x) y) = x
para todos los términos x y y. O, siguiendo la misma convención para el uso múltiple que en el cálculo lambda,

(K x y) = x
Un tercer combinador es S, que es una versión generalizada de la aplicación:

(S x y z) = (x z (y z))
S aplica x a y después de substituir primero a z en cada uno de ellos.

Dados S y K, aun el mismo I es innecesario, puesto que puede ser construido por los otros dos:

((S K K) x)
= (S K K x)
= (K x (K x))
= x
para cualquier término x. Nótese que aunque ((S K K) x) = (I x) para cualquier x, (S K K) en sí mismo no es igual a I. Decimos que los términos son extensionalmente iguales.

Compuertas Logicas

Las computadoras digitales utilizan el sistema de números binarios, que tiene dos dígitos 0 y 1. Un dígito binario se denomina un bit. La información está representada en las computadoras digitales en grupos de bits. Utilizando diversas técnicas de codificación los grupos de bits pueden hacerse que representen no solamente números binarios sino también otros símbolos discretos cualesquiera, tales como dígitos decimales o letras de alfabeto. Utilizando arreglos binarios y diversas técnicas de codificación, los dígitos binarios o grupos de bits pueden utilizarse para desarrollar conjuntos completos de instrucciones para realizar diversos tipos de cálculos.

La información binaria se representa en un sistema digital por cantidades físicas denominadas señales, Las señales eléctricas tales como voltajes existen a través del sistema digital en cualquiera de dos valores reconocibles y representan una variable binaria igual a 1 o 0. Por ejemplo, un sistema digital particular puede emplear una señal de 3 volts para representar el binario "1" y 0.5 volts para el binario "0". La siguiente ilustración muestra un ejemplo de una señal binaria.

La lógica binaria tiene que ver con variables binarias y con operaciones que toman un sentido lógico. La manipulación de información binaria se hace por circuitos lógicos que se denominan Compuertas.

Las compuertas son bloques del hardware que producen señales en binario 1 ó 0 cuando se satisfacen los requisitos de entrada lógica. Las diversas compuertas lógicas se encuentran comúnmente en sistemas de computadoras digitales. Cada compuerta tiene un símbolo gráfico diferente y su operación puede describirse por medio de una función algebraica. Las relaciones entrada - salida de las variables binarias para cada compuerta pueden representarse en forma tabular en una tabla de verdad.

A continuación se detallan los nombres, símbolos, gráficos, funciones algebraicas, y tablas de verdad de las compuertas más usadas.

Compuerta NOT
Se trata de un inversor, es decir, invierte el dato de entrada, por ejemplo; si pones su entrada a 1 (nivel alto) obtendrás en su salida un 0 (o nivel bajo), y viceversa. Esta compuerta dispone de una sola entrada. Su operación lógica es s igual a a invertida

Compuerta AND
Una compuerta AND tiene dos entradas como mínimo y su operación lógica es un producto entre ambas, no es un producto aritmético, aunque en este caso coincidan.
*Observa que su salida será alta si sus dos entradas están a nivel alto*



Compuerta OR
Al igual que la anterior posee dos entradas como mínimo y la operación lógica, será una suma entre ambas... Bueno, todo va bien hasta que 1 + 1 = 1, el tema es que se trata de una compuerta O Inclusiva es como a y/o b
*Es decir, basta que una de ellas sea 1 para que su salida sea también 1*

Compuerta OR-EX o XOR
Es OR EXclusiva en este caso con dos entradas (puede tener mas, claro...!) y lo que hará con ellas será una suma lógica entre a por b invertida y a invertida por b.
*Al ser O Exclusiva su salida será 1 si una y sólo una de sus entradas es 1*

Algebra Booleana

Álgebra Booleana

El álgebra booleana es un sistema matemático deductivo centrado en los valores cero y uno (falso y verdadero). Un operador binario " º " definido en éste juego de valores acepta un par de entradas y produce un solo valor booleano, por ejemplo, el operador booleano AND acepta dos entradas booleanas y produce una sola salida booleana.
Para cualquier sistema algebraico existen una serie de postulados iniciales, de aquí se pueden deducir reglas adicionales, teoremas y otras propiedades del sistema, el álgebra booleana a menudo emplea los siguientes postulados:

•Cerrado. El sistema booleano se considera cerrado con respecto a un operador binario si para cada par de valores booleanos se produce un solo resultado booleano.
•Conmutativo. Se dice que un operador binario " º " es conmutativo si A º B = B º A para todos los posibles valores de A y B.
•Asociativo. Se dice que un operador binario " º " es asociativo si (A º B) º C = A º (B º C) para todos los valores booleanos A, B, y C.
•Distributivo. Dos operadores binarios " º " y " % " son distributivos si A º (B % C) = (A º B) % (A º C) para todos los valores booleanos A, B, y C.
•Identidad. Un valor booleano I se dice que es un elemento de identidad con respecto a un operador binario " º " si A º I = A.
•Inverso. Un valor booleano I es un elemento inverso con respecto a un operador booleano " º " si A º I = B, y B es diferente de A, es decir, B es el valor opuesto de A.
Para nuestros propósitos basaremos el álgebra booleana en el siguiente juego de operadores y valores:
- Los dos posibles valores en el sistema booleano son cero y uno, a menudo llamaremos a éstos valores respectivamente como falso y verdadero.
- El símbolo · representa la operación lógica AND. Cuando se utilicen nombres de variables de una sola letra se eliminará el símbolo ·, por lo tanto AB representa la operación lógica AND entre las variables A y B, a esto también le llamamos el producto entre A y B.
- El símbolo "+" representa la operación lógica OR, decimos que A+B es la operación lógica OR entre A y B, también llamada la suma de A y B.
- El complemento lógico, negación ó NOT es un operador unitario, en éste texto utilizaremos el símbolo " ' " para denotar la negación lógica, por ejemplo, A' denota la operación lógica NOT de A.
- Si varios operadores diferentes aparecen en una sola expresión booleana, el resultado de la expresión depende de la procedencia de los operadores, la cual es de mayor a menor, paréntesis, operador lógico NOT, operador lógico AND y operador lógico OR. Tanto el operador lógico AND como el OR son asociativos por la izquierda. Si dos operadores con la misma procedencia están adyacentes, entonces se evalúan de izquierda a derecha. El operador lógico NOT es asociativo por la derecha.
Utilizaremos además los siguientes postulados:

•P1 El álgebra booleana es cerrada bajo las operaciones AND, OR y NOT
•P2 El elemento de identidad con respecto a · es uno y con respecto a + es cero. No existe elemento de identidad para el operador NOT
•P3 Los operadores · y + son conmutativos.
•P4 · y + son distributivos uno con respecto al otro, esto es, A· (B+C) = (A·B)+(A·C) y A+ (B·C) = (A+B) ·(A+C).
•P5 Para cada valor A existe un valor A' tal que A·A' = 0 y A+A' = 1. Éste valor es el complemento lógico de A.
•P6 · y + son ambos asociativos, ésto es, (AB) C = A (BC) y (A+B)+C = A+ (B+C).
Es posible probar todos los teoremas del álgebra booleana utilizando éstos postulados, además es buena idea familiarizarse con algunos de los teoremas más importantes de los cuales podemos mencionar los siguientes:

•Teorema 1: A + A = A
•Teorema 2: A · A = A
•Teorema 3: A + 0 = A
•Teorema 4: A · 1 = A
•Teorema 5: A · 0 = 0
•Teorema 6: A + 1 = 1
•Teorema 7: (A + B)' = A' · B'
•Teorema 8: (A · B)' = A' + B'
•Teorema 9: A + A · B = A
•Teorema 10: A · (A + B) = A
•Teorema 11: A + A'B = A + B
•Teorema 12: A' · (A + B') = A'B'
•Teorema 13: AB + AB' = A
•Teorema 14: (A' + B') · (A' + B) = A'
•Teorema 15: A + A' = 1
•Teorema 16: A · A' = 0
Los teoremas siete y ocho son conocidos como Teoremas de DeMorgan en honor al matemático que los descubrió.

Características:
Un álgebra de Boole es un conjunto en el que destacan las siguientes características:
1- Se han definido dos funciones binarias (que necesitan dos parámetros) que llamaremos aditiva (que representaremos por x
+ y) y multiplicativa (que representaremos por xy) y una función monaria (de un solo parámetro) que representaremos por x'.
2- Se han definido dos elementos (que designaremos por 0 y 1)
Y 3- Tiene las siguientes propiedades:

•Conmutativa respecto a la primera función: x + y = y + x
Conmutativa respecto a la segunda función: xy = yx
Asociativa respecto a la primera función: (x + y) + z = x + (y +z)
Asociativa respecto a la segunda función: (xy)z = x(yz)
Distributiva respecto a la primera función: (x +y)z = xz + yz
Distributiva respecto a la segunda función: (xy) + z = (x + z)( y + z)
Identidad respecto a la primera función: x + 0 = x
Identidad respecto a la segunda función: x1 = x
Complemento respecto a la primera función: x + x' = 1
Complemento respecto a la segunda función: xx' = 0
Propiedades Del Álgebra De Boole

1.Idempotente respecto a la primera función: x + x = x
Idempotente respecto a la segunda función: xx = x
Maximalidad del 1: x + 1 = 1
Minimalidad del 0: x0 = 0
Involución: x'' = x
Inmersión respecto a la primera función: x + (xy) = x
Inmersión respecto a la segunda función: x(x + y) = x
Ley de Morgan respecto a la primera función: (x + y)' = x'y'
Ley de Morgan respecto a la segunda función: (xy)' = x' + y'
Función Booleana
Una función booleana es una aplicación de A x A x A x....A en A, siendo A un conjunto cuyos elementos son 0 y 1 y tiene estructura de álgebra de Boole.
Supongamos que cuatro amigos deciden ir al cinesi lo quiere la mayoría. Cada uno puede votar si o no. Representemos el voto de cada uno por xi. La función devolverá sí (1) cuando el numero de votos afirmativos sea 3 y en caso contrario devolverá 0.
Si x1 vota 1, x2 vota 0, x3 vota 0 y x4 vota 1 la función booleana devolverá 0.
Producto mínimo (es el número posible de casos) es un producto en el que aparecen todas las variables o sus negaciones.

El número posible de casos es 2n.
Siguiendo con el ejemplo anterior. Asignamos las letras A, B, C y D a los amigos. Los posibles casos son:
Votos Resultado
ABCD
1111 1
1110 1
1101 1
1100 0
1011 1
1010 0
1001 0
1000 0
0111 1
0110 0
0101 0
0100 0
0011 0
0010 0
0001 0
0000 0

Las funciones booleanas se pueden representar como la suma de productosmínimos (minterms) iguales a 1.

En nuestro ejemplo la función booleana será:
f(A,B,C,D) = ABCD + ABCD' + ABC'D + AB'CD + A'BCD

Diagramas De Karnaugh
Los diagramas de Karnaugh se utilizan para simplificar las funciones booleanas.
Se construye una tabla con las variables y sus valores posibles y se agrupan los 1 adyacentes, siempre que el número de 1 sea potencia de 2.
En esta página tienes un programa para minimización de funciones booleanas mediante mapas de Karnaugh.