Descargar

LOGICA COMPUTACIONAL
LA LOGICA PROPOSICIONAL
Contenido
 Introducción al cálculo proposicional (Álgebra de Boole)
 Expresiones lógicas
 Tablas de verdad (Conjunción, Disyunción, Negación, Implicación)
 Aplicación de la lógica en el diseño de circuitos electrónicos.
Ing. Celso Javier Rodriguez Pizza
LOGICA PROPOSICIONAL
INTRODUCCION AL CALCULO
PROPOSICIONAL
Ing. Celso Javier Rodriguez Pizza
Proposiciones
 La lógica utiliza un lenguaje exacto que no da lugar a imprecisiones,
para tal fin toma como elemento básico de análisis a la proposición.
 Proposición, es un enunciado del cual se puede dar un valor de
verdad. Para simplificar la escritura de argumentos lógicos
complicados, crea un lenguaje simbólico artificial.
 Es importante tener en cuenta que las proposiciones representan
oraciones declarativas, las cuales contienen un sujeto
perfectamente definido o dado por el contexto, un predicado y una
conjugación del verbo ser.
Ing. Celso Javier Rodriguez Pizza
Proposiciones Simples
 Las proposiciones se representan simbólicamente mediante el uso
de letras minúsculas del alfabeto, las cuales reciben el nombre de
letras o variables proposicionales, de esta forma, el lenguaje
proposicional se hace más simple y exacto que el lenguaje natural.
 Ejemplos:
 p : Hoy es sábado.
 q : Yo estudio Ingeniería.
 r : New York es llamada la capital del mundo.
 s : 1 no es un número primo.
 x : 4 + 3 = 10.
Ing. Celso Javier Rodriguez Pizza
Proposiciones Compuestas
 En el lenguaje cotidiano se encuentran expresiones como:
 Las rosas son rojas y tienen espinas.
 ¿La selección Colombia ganó o perdió?
 En el país no hay violencia.
 Si estudio lógica computacional entonces seré un destacado ingeniero
 4 es un número par si y sólo si se puede dividir por 2.
 Estas expresiones se denominan oraciones y para su formación se
utilizaron las letras y, o, no, si … entonces, sí y sólo si, que
sirvieron para unir o enlazar los enunciados.
Ing. Celso Javier Rodriguez Pizza
Conectores lógicos
 Los anteriores términos de enlace reciben el nombre de conectores
lógicos y al igual que a las proposiciones, también se les asignan
un lenguaje simbólico, así:
Lenguaje Natural
Lenguaje Formal
Descripción
y
Λ
Conjunción
o
V
Disyunción
No
~
Negación
Si…entonces

Implicación o
Condicional
Si y solo si

Doble implicación o
Bicondicional
Ing. Celso Javier Rodriguez Pizza
Conectores lógicos: Ejemplos
 p : Las rosas son rojas.
 q : Las rosas tienen espinas.
 p Λ q : Las rosas son rojas y tienen espinas.
 r: La selección Colombia ganó?.
 s: La selección Colombia perdió?.
 r V s : La selección Colombia ganó o perdió?.
 t : En el país hay violencia.
 ~ t : En el país no hay violencia.
Ing. Celso Javier Rodriguez Pizza
Conectores lógicos: Ejemplos
 x : Estudio lógica computacional
 y : Seré un destacado ingeniero
 x  y : Si estudio lógica computacional entonces seré un destacado
ingeniero.
 u : 4 es un número par.
 v : 4 es divisible por 2.
 u  v : 4 es un número par si y sólo si es divisible por 2.
Ing. Celso Javier Rodriguez Pizza
LOGICA PROPOSICIONAL
TABLAS DE VERDAD
Ing. Celso Javier Rodriguez Pizza
Tablas de verdad
 Una tabla de verdad es una representación esquemática de las
relaciones entre proposiciones; sirve para determinar los valores de
verdad de proposiciones compuestas, las cuales dependen de los
conectivos utilizados y de los valores de verdad de sus
proposiciones simples.
 En la elaboración de una tabla de verdad, los términos de enlace
tales como la negación (~), la disyunción (V) y la conjunción (Λ) se
consideran conectores fundamentales; por tal razón, sus valores de
verdad constituyen base para establecer bajo qué condiciones una
proposición compuesta es verdadera o falsa.
Ing. Celso Javier Rodriguez Pizza
Tablas de verdad
Ing. Celso Javier Rodriguez Pizza
Tablas de verdad
 Para simbolizar los valores de verdad de una proposición, se utiliza
el sistema binario, mediante el cual se le asigna 1 al valor
verdadero y 0 al valor falso. La siguiente tabla resume los valores
de verdad de los conectivos lógicos:
Ing. Celso Javier Rodriguez Pizza
Construcción de tablas de verdad
 Para determinar el valor de verdad de una proposición compuesta
es necesario elaborar la correspondiente tabla de verdad; para tal
fin y mediante el siguiente ejemplo se enuncian los pasos a seguir:
 Ejemplo 1. Construir la tabla de verdad para la proposición ~(p Λ q)
 Paso 1. Se hace un recorrido de izquierda a derecha teniendo en
cuenta los paréntesis.
 Paso 2. Se identifica el conectivo que aparece dentro del
paréntesis, en este ejemplo la conjunción.
Ing. Celso Javier Rodriguez Pizza
Construcción de tablas de verdad
 Paso 3. Se precisa el término de enlace que precede al paréntesis,
en el ejemplo la negación.
 Paso 4. Se elabora la tabla con el número de columnas
determinado por:
 Proposiciones que intervienen
 Conectivos utilizados dentro del paréntesis
 Conectivo utilizado fuera del paréntesis.
 La siguiente tabla ilustra el paso 4:
Ing. Celso Javier Rodriguez Pizza
Construcción de tablas de verdad
 Paso 5. Se fijan los valores de verdad en las columnas de las
proposiciones p y q. Se ilustra en la siguiente tabla:
 Paso 6. Se completa la tabla por columnas, teniendo en cuenta el
conectivo y el valor de verdad de cada proposición simple. La
finalización de la elaboración de la tabla de verdad es:
Ing. Celso Javier Rodriguez Pizza
Construcción de tablas de verdad
 Ejemplo 2. Construir la tabla de verdad para la proposición
(p V q) Λ (p Λ q)
 Solución:
Ing. Celso Javier Rodriguez Pizza
Tautologías y Contradicciones
 Entre las proposiciones compuestas existen unas muy importantes
por ser siempre verdaderas, independientemente del valor de
verdad de las proposiciones que la conforman, este tipo de
proposiciones reciben el nombre de tautologías.
 Ejemplo 1. Demostrar que la proposición ( p V q )  (~ q  p ) es
verdadera.
Ing. Celso Javier Rodriguez Pizza
Tautologías y Contradicciones
 Ejemplo 2. ¿Es ( p Λ ~ q ) Λ q una tautología?
 Para responder la pregunta se hace necesario hacer la tabla de
verdad, así:
 Por lo tanto esta proposición no es una tautología, es una
contradicción.
Ing. Celso Javier Rodriguez Pizza
Leyes del cálculo proposicional

Las siguientes son las leyes de la lógica. Se caracterizan porque
todas son tautologías:

Ley del tercio excluido:


Ley de separación:


(pΛ(pq))q
Ley de simplificación:


p v ~p
(pΛq)p
Ley de la adición:

p(pVq)
Ing. Celso Javier Rodriguez Pizza
Leyes del cálculo proposicional

Ley de la disyunción por casos:


Ley de separación:


(pΛ(pq))q
Ley de simplificación:


(pq)
(pΛq)p
Ley de la adición:

p(pVq)
Ing. Celso Javier Rodriguez Pizza
LOGICA PROPOSICIONAL
EXPRESIONES LOGICAS
Ing. Celso Javier Rodriguez Pizza
Expresiones Lógicas
 Una expresión lógica es una proposición (simple o compuesta) en la
cual se establece una comparación entre datos, utilizando:
 Operadores de relación: >, <, >=, <=, =, <> (Proposiciones simples)
 Operadores lógicos: Y, O, NO (Proposiciones compuestas)
 Ejemplo 1: Escriba una proposición que permita conocer si una
persona es mayor de edad
 Solución: Se creará un dato denominado EDAD el cual representa
la edad de una persona
 p: EDAD >= 18
Ing. Celso Javier Rodriguez Pizza
Expresiones Lógicas
 Ejemplo 2: Escriba una proposición que permita conocer si una
persona gana mas de un salario mínimo.
 Solución: Se creará un dato denominado SALARIO el cual
representa el salario que devenga una persona
 q: SALARIO >= 496900
 Ejemplo 3. Escriba una proposición que permita determinar si una
variable a tiene un valor mayor a b y c.
Ing. Celso Javier Rodriguez Pizza
Expresiones Lógicas
 Solución:
 p: a > b
 q: a > c
 p Λ q: a > b Y a > c
 Prueba.
 Suponga que a = 20, b = 10, c = 15
 p: 20 > 10 (V)
 q: 20 > 15 (V)
 p Λ q: (20 > 10) Λ ( 20 > 15 ) (V Λ V = V)
Ing. Celso Javier Rodriguez Pizza
Expresiones Lógicas
 Ejemplo 4: Escribir una proposición que permita conocer si 3 lados
de un triángulo (LADO1, LADO2 y LADO3 ) forman un triángulo
equilátero
 Solución. Se creará tres datos denominado LADO1, LADO2 y
LADO3 el cual representa los lados de un triángulo
 p: LADO1 = LADO2
 q: LADO2 = LADO3
 p Λ q: ( LADO1 = LADO2 ) Λ ( LADO2 = LADO3 )
Ing. Celso Javier Rodriguez Pizza
Expresiones Lógicas
 Ejemplo 5: Escribir una proposición que permita conocer si 3 lados
de un triángulo (LADO1, LADO2 y LADO3 ) forman un triángulo
isóceles.
 Solución. Se creará tres datos denominado LADO1, LADO2 y
LADO3 el cual representa los lados de un triángulo
 p: LADO1 = LADO2
 q: LADO2 = LADO3
 r: LADO1 = LADO3
 p V q V r: ( LADO1 = LADO2 ) V ( LADO2 = LADO3 ) V
( LADO1 = LADO3)
Ing. Celso Javier Rodriguez Pizza
Expresiones Lógicas
 Ejemplo 6: Escribir una proposición que permita conocer si un
número se encuentra en el intervalo [-5, 7]
 Solución. Se creará un dato denominado NUM el cual representa el
número a evaluar
 p: NUM >= -5
 q: NUM <= 7
 p Λ q: ( NUM >= -5 ) Λ ( NUM <= 7 )
Ing. Celso Javier Rodriguez Pizza
Expresiones Lógicas
 Ejercicios:
 Escribir una proposición que permita conocer si un número está en el




intervalo [-5, 7] o en el intervalo [9, 11].
Escriba una proposición que determine si tres variables llamadas DIA,
MES y AÑO son valores correctos.
Escriba una proposición que determine si dos variables llamadas RAIZ1
y RAIZ2 corresponden a la solución de la ecuación (x2+3x+5=0).
Escriba una proposición que permita determinar si un carácter pulsado
es alfabético.
Escribir una proposición que permita determinar si en una elección
entre 3 candidatos, alguno obtuvo la mayoría absoluta (más del 50% de
los votos).
Ing. Celso Javier Rodriguez Pizza
LOGICA PROPOSICIONAL
APLICACIONES DE LA LOGICA EN EL
DISEÑO DE CIRCUITOS
ELECTRONICOS
Ing. Celso Javier Rodriguez Pizza
Circuitos electrónicos
 Circuito lógico es aquel que maneja la información en forma de "1" y
"0", dos niveles lógicos de voltaje fijos. "1" nivel alto o "high" y "0"
nivel bajo o "low".
 Los circuitos lógicos están compuestos por elementos digitales
como la compuerta AND (Y), compuerta OR (O), compuerta NOT
(NO)...... y combinaciones poco o muy complejas de los circuitos
antes mencionados.
 Estas combinaciones dan lugar a otros tipos de elementos digitales
como los compuertas, entre otros.
Ing. Celso Javier Rodriguez Pizza
Circuitos electrónicos
 La electrónica moderna usa electrónica digital para realizar muchas
funciones. Aunque los circuitos electrónicos podrían parecer muy
complejos, en realidad se construyen de un número muy grande de
circuitos muy simples.
 En un circuito lógico digital se transmite información binaria (ceros y
unos) entre estos circuitos y se consigue un circuito complejo con la
combinación de bloques de circuitos simples.
Ing. Celso Javier Rodriguez Pizza
Circuitos electrónicos
 La información binaria se representa en la forma de:
 "0" o "1",
 "abierto" o "cerrado" (interruptor),
 "On" y "Off",
 "falso" o "verdadero", etc.
Ing. Celso Javier Rodriguez Pizza
Compuerta AND
 La compuerta AND o Y lógica es una de las compuertas más
simples dentro de la Electrónica Digital.
 Su representación es la que se muestra en las siguientes figuras. La
primera es la representación de una compuerta AND de 2 entradas
y la segunda de una compuerta AND de 3 entradas.
 La compuerta Y lógica más conocida tiene dos entradas A y B,
aunque puede tener muchas más (A, B, C, etc.) y sólo tiene una
salida.
Ing. Celso Javier Rodriguez Pizza
Compuerta AND
 La compuerta AND de 2 entradas
tiene la siguiente tabla de verdad:
 Se puede ver claramente que la salida X solamente es "1" (1 lógico,
nivel alto) cuando la entrada A como la entrada B están en "1". En
otras palabra: La salida X es igual a 1 cuando la entrada A y la
entrada B son 1.
 Esta situación se representa en el álgebra booleana como: X = A*B
o X = AB.
Ing. Celso Javier Rodriguez Pizza
Compuerta AND
 Una compuerta AND de 3 entradas se puede implementar con
interruptores, como se muestra en el siguiente diagrama.
 La tabla de verdad se muestra al lado derecho donde: A = Abierto y
C = Cerrado.
Ing. Celso Javier Rodriguez Pizza
Compuerta AND
 Una compuerta AND puede tener muchas entradas. Una AND de
múltiples entradas puede ser creada conectando compuertas
simples en serie.
 Si se necesita una AND de 3 entradas y no una hay disponible, es
fácil crearla con dos compuertas AND en serie o cascada como se
muestra en el siguiente diagrama.
Ing. Celso Javier Rodriguez Pizza
Compuerta OR
 La compuerta OR o O lógica es una de las compuertas más simples
dentro de la Electrónica Digital.
 Su representación es la que se muestra en las siguientes figuras. La
primera es la representación de una compuerta OR de 2 entradas y
la segunda de una compuerta OR de 3 entradas.
 La compuerta OR lógica más conocida tiene dos entradas A y B,
aunque puede tener muchas más (A, B, C, etc.) y sólo tiene una
salida.
Ing. Celso Javier Rodriguez Pizza
Compuerta OR
 La compuerta OR de 2 entradas
tiene la siguiente tabla de verdad:
 Se puede ver claramente que la salida X solamente es "1" (1 lógico,
nivel alto), cuando en cualquiera de sus entradas haya un "1".
 Esta situación se representa en el álgebra booleana como: X = A+B
o X = B+A.
Ing. Celso Javier Rodriguez Pizza
Compuerta OR
 Una compuerta OR de 3 entradas se puede implementar con
interruptores, como se muestra en el siguiente diagrama.
 La tabla de verdad se muestra al lado derecho donde: 0 = Abierto y
1 = Cerrado.
Ing. Celso Javier Rodriguez Pizza
Compuerta OR
 Una compuerta OR puede tener muchas entradas. Una OR de
múltiples entradas puede ser creada conectando compuertas
simples en serie.
 Si se necesita una OR de 3 entradas y no una hay disponible, es
fácil crearla con dos compuertas OR en serie o cascada como se
muestra en el siguiente diagrama.
Ing. Celso Javier Rodriguez Pizza
Compuerta NOT
 La compuerta NOT o NO lógica (inversora) es una de las
compuertas más simples dentro de la Electrónica Digital.
 La compuerta NOT entrega en su salida el inverso (opuesto) de la
entrada. El símbolo y la tabla de verdad son los siguientes:
 La compuerta NOT lógica tiene una sola entrada A y sólo tiene una
salida. La salida de una compuerta NOT tiene el valor inverso al de
su entrada. En el caso del gráfico anterior la salida X = A.
Ing. Celso Javier Rodriguez Pizza
Compuerta NOT
 Esto significa que si a la entrada tenemos un "1" lógico, a la salida
hará un "0" lógico y si a la entrada tenemos un "0" a la salida habrá
un "1"
 El apóstrofe en la siguiente expresión significa "negado": X = A’ y
es igual a X = A. Las compuertas NOT se pueden conectar en
cascada, logrando después de dos compuertas, la entrada original.
Ing. Celso Javier Rodriguez Pizza
Otras Compuertas: NAND
 Una compuerta NAND (NO Y) de dos entradas, se puede
implementar con la concatenación de una compuerta AND o "Y" de
dos entradas y una compuerta NOT o "No" o inversora.
 Al igual que en el caso de la compuerta AND, ésta se puede
encontrar en versiones de 2, 3 o más entradas.
Ing. Celso Javier Rodriguez Pizza
Otras Compuertas: NAND
 Ejemplo de una compuerta NAND de 3 entradas:
 Como se puede ver la salida X sólo será "0" cuando todas las
entradas sean "1".
Ing. Celso Javier Rodriguez Pizza
Otras Compuertas: NAND
 Una forma alternativa de lograr el mismo resultado de una
compuerta NAND, es utilizar las leyes de D’Morgan:
Ing. Celso Javier Rodriguez Pizza
Otras Compuertas: NOR
 Una compuerta NOR (NO O) de dos entradas, se puede
implementar con la concatenación de una compuerta OR o “O" de
dos entradas y una compuerta NOT o "No" o inversora.
 Al igual que en el caso de la compuerta OR, ésta se puede
encontrar en versiones de 2, 3 o más entradas.
Ing. Celso Javier Rodriguez Pizza
Otras Compuertas: NOR
 Ejemplo de una compuerta NOR de 3 entradas:
 Como se puede ver la salida X sólo será “1" cuando todas las
entradas sean “0".
Ing. Celso Javier Rodriguez Pizza
Otras Compuertas: NOR
 Una forma alternativa de lograr el mismo resultado de una
compuerta NOR, es utilizar las leyes de D’Morgan:
Ing. Celso Javier Rodriguez Pizza
Otras Compuertas: XOR
 La compuerta XOR representa a la compuerta OR Exclusiva. A
diferencia de la compuerta OR, la compuerta XOR tiene una salida
igual a 0 cuando sus entradas son iguales a 1.
 Si se comparan las tablas de verdad de ambas compuertas se
observa que la compuerta XOR es uno ("1") a su salida cuando la
suma de los unos "1" a las entradas es igual a un número impar.
 La ecuación se puede escribir de dos maneras:
Ing. Celso Javier Rodriguez Pizza
Otras Compuertas: XOR
 Ejemplo de una compuerta
XOR de 2 entradas:
 Ejemplo de compuerta
XOR de 3 entradas:
 Se puede ver como se cumple que X = 1 sólo cuando la suma de
las entradas en "1" es impar.
Ing. Celso Javier Rodriguez Pizza
Circuitos Combinacionales
 Un circuito combinacional, como su nombre lo sugiere es un circuito
cuya salida depende solamente de la "combinación" de sus
entradas en el momento que se está realizando la medida en la
salida.
 Analizando el circuito, con compuertas digitales, que se muestra a
continuación, se ve que la salida de cada una de las compuertas
que se muestran, depende únicamente de sus entradas.
Ing. Celso Javier Rodriguez Pizza
Circuitos Combinacionales
 La salida F (salida final o total del circuito) variará si alguna de las
entradas A o B o las dos a la vez cambian.
 Los circuitos de lógica combinacional son hechos a partir de las
compuertas básicas compuerta AND, compuerta OR, compuerta
NOT. También pueden ser construidos con compuertas NAND,
compuertas NOR, compuerta XOR, que son una combinación de las
tres compuertas básicas.
 La operación de los circuitos combinacionales se entienden
escribiendo las ecuaciones booleanas y sus tablas de verdad.
Ing. Celso Javier Rodriguez Pizza
Ejercicios
 Determinar la función combinacional de los siguientes circuitos
combinacionales:
Ing. Celso Javier Rodriguez Pizza
Algebra Booleana
 Cuando se trabaja con circuitos digitales es muy común que al final
de un diseño se tenga un circuito con un número de partes
(compuertas y otros) mayor al necesario.
 Para lograr que el circuito tenga la cantidad de partes correcta (la
menor posible) hay que optimizarlo (reducirlo).
 Un diseño óptimo causará que:
 El circuito sea más simple
 El número de componentes sea el menor
 El precio de proyecto sea el más bajo
Ing. Celso Javier Rodriguez Pizza
Algebra Booleana
 La demanda de potencia del circuito sea menor
 El mantenimiento del circuito sea más fácil.
 Es
espacio necesario (en el circuito
implementación del circuito será menor.
impreso)
para
la
 En consecuencia que el diseño sea el más económico posible.
 Una herramienta para reducir las expresiones lógicas de circuitos
digitales es la matemáticas de expresiones lógicas, que fue
presentada por George Boole en 1854, herramienta que desde
entonces se conoce como álgebra de Boole.
Ing. Celso Javier Rodriguez Pizza
Algebra Booleana
 Las reglas del Algebra Booleana son:
 . (punto): significa producto lógico
 + (signo de suma): significa suma lógica
Ing. Celso Javier Rodriguez Pizza
Algebra Booleana
 Las reglas del Algebra Booleana son:
 . (punto): significa producto lógico
 + (signo de suma): significa suma lógica
Ing. Celso Javier Rodriguez Pizza
Bibliografía
 Impresa:
 GONZÁLEZ Acevedo, Georffrey. Lógica Matemática
 LIPSCHUTZ, Seymour. Matemáticas para computación.
 En Internet:
 http://www.unicrom.com
 http://profesormolina1.webcindario.com/electronica/componentes/int/co
mp_log.htm
 http://www.unibague.edu.co/~gustavo.martinez/cursos/lc/generalidades.
html
 http://es.wikipedia.org/wiki/Circuito_combinacional
Ing. Celso Javier Rodriguez Pizza