Download - Modulo de Logica
Módulo de Lógica matemática
Favián Arenas A. y Amaury Camargo .
Índice
1. Generalidades. 5
1.1. Objetivos generales . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2. Introducción a la lógica matemática . . . . . . . . . . . . . . . 7
1.3. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.4. Competencias . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.5. Estrategias pedagógicas o actividades de aprendizaje . . . . . 10
1.6. Recursos de aprendizaje . . . . . . . . . . . . . . . . . . . . . 10
1.7. Proposiciones . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.8. Clases de proposiciones . . . . . . . . . . . . . . . . . . . . . 12
1.8.1. Proposiciones conjuntivas, p ^ q . . . . . . . . . . . . . 13
1.8.2. Proposiciones disyuntivas, p _ q . . . . . . . . . . . . . 15
1.8.3. Proposiciones disyuntivas exclusivas p Y q . . . . . . . . 16
1.8.4. Proposiciones condicionales, p! q . . . . . . . . . . . 16
1.8.5. Proposiciones bicondicionales, p$ q . . . . . . . . . . 17
1.8.6. Proposiciones negativas:� p . . . . . . . . . . . . . . . 19
1.8.7. Validación de leyes lógicas . . . . . . . . . . . . . . . . 21
1
ÍNDICE Lógica Matemática
1.9. Cuanti�cadores . . . . . . . . . . . . . . . . . . . . . . . . . . 26
1.10. Actividades . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2. Introducción a los Conjuntos 33
2.1. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.2. Competencias . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.3. Estrategias pedagógicas o actividades de aprendizaje . . . . . 35
2.4. Recursos de aprendizaje . . . . . . . . . . . . . . . . . . . . . 35
2.5. Teoría de conjuntos . . . . . . . . . . . . . . . . . . . . . . . . 36
2.6. Clases de conjuntos . . . . . . . . . . . . . . . . . . . . . . . . 37
2.7. Determinación de un conjunto . . . . . . . . . . . . . . . . . . 38
2.8. Algebra de conjuntos . . . . . . . . . . . . . . . . . . . . . . . 40
2.9. Propiedades de los Conjuntos . . . . . . . . . . . . . . . . . . 43
2.10. Actividades . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3. Introducción al Álgebra de Boole 48
3.1. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.2. Competencias . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.3. Estrategias pedagógicas o actividades de aprendizaje . . . . . 50
3.4. Recursos de aprendizaje . . . . . . . . . . . . . . . . . . . . . 50
3.5. Clases de operaciones . . . . . . . . . . . . . . . . . . . . . . . 51
3.6. Álgebra de Boole . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.7. Principio de dualidad . . . . . . . . . . . . . . . . . . . . . . . 55
3.8. Funciones booleanas . . . . . . . . . . . . . . . . . . . . . . . 58
3.8.1. Funciones reales y funciones booleanas . . . . . . . . . 58
Favián Arenas. 2 Camargo Benítez.
ÍNDICE Lógica Matemática
3.8.2. Funciones booleanas y tablas de verdad . . . . . . . . . 61
3.9. Actividades . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4. Introducción al método de Karnaugh 65
4.1. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.2. Competencias . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.3. Estrategias pedagógicas o actividades de aprendizaje . . . . . 67
4.4. Recursos de aprendizaje . . . . . . . . . . . . . . . . . . . . . 67
4.5. Método de Karnaugh para la Simpli�cación de circuitos . . . . 68
4.5.1. Método Karnaugh de simpli�cación de expresiones booleanas 87
4.6. Actividades . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
4.7. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
4.8. Recursos de aprendizaje . . . . . . . . . . . . . . . . . . . . . 101
4.9. Actividades . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
4.9.1. Proposiciones conjuntivas, p ^ q . . . . . . . . . . . . . 103
4.9.2. Proposiciones disyuntivas, p _ q . . . . . . . . . . . . . 104
4.9.3. Proposiciones condicionales, p! q . . . . . . . . . . . 105
4.9.4. Proposiciones bicondicionales, p$ q . . . . . . . . . . 106
4.9.5. Negación de Proposiciones :� p . . . . . . . . . . . . . 106
4.10. Actividades . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
4.11. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
4.12. Recursos de aprendizaje . . . . . . . . . . . . . . . . . . . . . 109
4.13. Algebra de conjuntos . . . . . . . . . . . . . . . . . . . . . . . 110
4.14. Actividades . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
4.15. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
4.16. Recursos de aprendizaje . . . . . . . . . . . . . . . . . . . . . 115
Favián Arenas. 3 Camargo Benítez.
ÍNDICE Lógica Matemática
4.17. Clases de operaciones . . . . . . . . . . . . . . . . . . . . . . . 116
4.18. Álgebra de Boole . . . . . . . . . . . . . . . . . . . . . . . . . 117
4.18.1. Funciones reales y funciones booleanas . . . . . . . . . 120
4.19. Actividades . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
4.20. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
4.21. Recursos de aprendizaje . . . . . . . . . . . . . . . . . . . . . 125
4.22. Actividades . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
Favián Arenas. 4 Camargo Benítez.
Lógica Matemática
1. Generalidades.
Nombre del curso:
Programa:
Area:
Semestre:
Créditos:
Prerrequisitos:
Favián Arenas. 5 Camargo Benítez.
1.1 Objetivos generales Lógica Matemática
1.1. Objetivos generales
Proporcionar una formación sólida en los fundamentos de la lógica de
proposiciones.
Desarrollar las habilidades y destrezas para la representación formal
del conocimiento y para la transcripción de frases del lenguaje natural
en lenguaje formal.
Introducir el manejo simbólico de sistemas formales y la demostración
de teoremas
Describir qué es una interpretación, cómo se calcula el valor de una
fórmula en una interpretación y los tipos de fórmulas en función de las
diferentes interpretaciones.
Fomentar al alumno para que se enfrente a la resolución de problemas
de forma lógica, analítica y estructurada.
Comprender los mecanismos computacionales asociados a las prob-
lemáticas de la demostración automática de teoremas y la Progra-
mación Lógica.
Mostrar el contexto de la lógica en la Informática y captar su relación
con ramas especí�cas como: Programación, Ingeniería del Software,
Bases de Datos, Diseño de Circuitos, etc.
Favián Arenas. 6 Camargo Benítez.
1.2 Introducción a la lógica matemática Lógica Matemática
UNIDAD DE APRENDIZAJE I
1.2. Introducción a la lógica matemática
La verdad y la mentira, palabras opuestas que utilizamos a diario para tomar
decisiones, sean estas correctas o no. Debemos valorar cada cosa; pero es
razonable que no todas las expresiones se pueden valorar, o...¿Alguien se
atrevería a contradecir a quien pregunte por la hora?, por supuesto que no, y
aunque a usted no le guste algún color ¿signi�ca que por ello a nadie mas le
gustará?.¡Claro que no! En este caso podemos decir que es una situación sub-
jetiva o dependiente del individuo que lo exprese. También hay expresiones
que para la mayoría de las personas tiene un valor único, por ejemplo .la rosa
es una �or, en algunas tendremos que ser bien explícitos para evitar malos
entendidos, por ejemplo: �Jesús tiene cinco letras�. ¿a quien nos referimos al
hombre llamado Jesús ó a la palabra Jesús?. Por lo tanto una proposición es
una a�rmación de la cual se puede a�rmar que es cierta o que es falsa. Para
expresarnos con claridad utilizamos conjuntos de palabras con sentido �lógi-
co�, sin embargo, ¿qué es en realidad lógica? Cuando escuchamos expresiones
como:
�Su respuesta fue lógica�
�Es ilógico pensar que no lo notará�
�Lógicamente...�
En realidad estamos expresando lo que la mayoría de las personas haría
o escogería como correcto, o dicho de otra forma, el sentido común.
¿será cierto que el sentido común es el menos común de los sentidos?
Favián Arenas. 7 Camargo Benítez.
1.3 Objetivos Lógica Matemática
1.3. Objetivos
El alumno estará en la capacidad conocer, utilizar y aplicar los siguientes
elementos básicos para la solución de un problema:
Resolver proposiciones compuestas utilizando los conectivos lógicos.
Hallar el valor de verdad de una proposición a través de la conjunción,
disyunción, condicional, bicondicional y negación a través de proposi-
ciones simples.
Construir la tabla de verdad de una proposición compuesta, y decidir
si es una ley.
Favián Arenas. 8 Camargo Benítez.
1.4 Competencias Lógica Matemática
1.4. Competencias
Sustenta una proposición compuesta como una tautología a partir de
su tabla de verdad.
Identi�ca en un teorema el antecedente y el consecuente.
Desarrolla el proceso de síntesis a partir de la construcción de proposi-
ciones compuestas utilizando los conectivos lógicos.
Favián Arenas. 9 Camargo Benítez.
1.5 Estrategias pedagógicas o actividades de aprendizajeLógica Matemática
1.5. Estrategias pedagógicas o actividades de apren-
dizaje
Mesa redonda.
Presentación de trabajos.
Sesión de Chat.
Sesión Foro.
Talleres
Encuentro presencial
1.6. Recursos de aprendizaje
Aula de clases,
Laboratorios
Auditorios.
Videobeam
Retroproyector.
Favián Arenas. 10 Camargo Benítez.
1.7 Proposiciones Lógica Matemática
1.7. Proposiciones
La lógica es toda una disciplina en la que las re�exiones y el razonamien-
to son fundamentales. Es estudiada también por la �losofía, pero, aquí nos
referiremos por lógica a la Lógica matemática. El elemento básico sobre el
que se desarrolla toda esta teoría se llama proposición.
De todo lo anterior una proposición es una a�rmación con sentido com-
pleto de la cual se puede a�rmar que es cierta o que es falsa.
Ejemplo 1.
1. �La sal es un compuesto químico�
2. 10 < 14
3. �13 es un número impar�
4. �El sol sale de noche�
5. 45 + 5 = 30
6. �¿De que color es la pared?�
Las a�rmaciones 1, 2, 3, 4 y 5. son proposiciones aunque no todas son
verdaderas siguen siendo proposiciones.
A esta propiedad de las proposiciones de ser verdadera o falsa se le llama
valor de verdad.
Las proposiciones se representan con letras minúsculas, usualmente p, q,
r, s, t,..
Favián Arenas. 11 Camargo Benítez.
1.8 Clases de proposiciones Lógica Matemática
Existen casos donde el sujeto del que se habla en la proposición no está
de�nido o no se conoce, por lo que tiene una incógnita.
A estos casos les llamamos frases proposicionales. (Suele llamarles proposi-
ciones abiertas)
1. x+ 12 = 20
2. �Alguien es un ingeniero famoso�
3. Mi nombre es "fulano de tal"
4. �Tengo x dinero en el banco�
1.8. Clases de proposiciones
1. Proposiciones simples o atómicas: Son aquellas que no se pueden frag-
mentar en proposiciones menores.
a) �La luna es un satélite natural�
�Los dígitos son nueve�
�4 es un número par�
�Todos los números impares son primos�
�Los pingüinos son aves�
2. Proposiciones compuestas o moleculares: Las proposiciones simples se
pueden conectar, y construir proposiciones llamadas compuestas. Ésta
operación puede hacer que cambie su valor de verdad.
Favián Arenas. 12 Camargo Benítez.
1.8 Clases de proposiciones Lógica Matemática
"Las rosas son rojas y las violetas azules"es un enunciado com-
puesto por los subenunciados "las rosas son rojas 2"las violetas
son azules".
"El es inteligente o estudia todas las noches"es, implícitamente,
un enunciado compuesto por los subenunciados "El es inteligente 2
"estudia todas las noches".
La propiedad fundamental de un enunciado compuesto es que su valor
de verdad está completamente determinado por los valores de verdad
de sus subenunciados junto con la manera como están conectados para
formar el enunciado compuesto. Comenzamos con un estudio de algunas
de estos conectivos.
Utilizaremos las letras p; q; r(en minúsculas) para denotar proposiciones.
Además una proposición puede tomar el valor de 1 si es verdadera,
0 si es falsa, esto también se espera que ocurra en las proposiciones
compuestas, por esto es necesario una tabla que de la oportunidad
de veri�car todas las posibles combinaciones, la llamaremos Tablas de
verdad
1.8.1. Proposiciones conjuntivas, p ^ q
Dos enunciados cualesquiera se pueden combinar con la palabra 2"para
formar un enunciado compuesto llamado la conjunción de los enunciados
originales. Simbólicamente, p^ q denota la conjunción de los enunciados p y
q, que se lee "p y q".
Favián Arenas. 13 Camargo Benítez.
1.8 Clases de proposiciones Lógica Matemática
el valor de esta proposición conjuntiva dependerá de que las dos proposi-
ciones que la conforman sean verdaderas
1. p : El dos es un número par (V)
2. q : Siete es un número primo (V)
3. r : El ocho es un número primo (F)
así que :
p ^ q : El dos es un número par y siete es un número primo (V)
En caso de que una de las dos sea falsa entonces toda la proposición conjun-
tiva lo será.
r ^ q : El ocho es un número primo y siete es un número primo (F)
La tabla de verdad del enunciado compuesto p ^ q está dada por la sigu-
iente tabla:
p q p ^ q
1 1 1
1 0 0
0 1 0
0 0 0
Para ilustrarlo: en una tubería de acueducto se han colocado 2 grifos
numerados p y q respectivamente si se abre p escribimos 1, si la cerramos
escribimos 0. la única forma en que salga agua es p = 1 y q = 1 en cualquier
otro caso no saldrá agua.
Favián Arenas. 14 Camargo Benítez.
1.8 Clases de proposiciones Lógica Matemática
1.8.2. Proposiciones disyuntivas, p _ q
Dos enunciados se combinan con la palabra .o"para formar un enunciado
compuesto llamado la disyunción de los enunciados originales. Simbólica-
mente, p _ q denota la disyunción de los enunciados p y q, que se lee "p o
q".
El valor de esta proposición conjuntiva dependerá de que las dos proposi-
ciones que la conforman sean no sean falsas.
La tabla de verdad del enunciado compuesto p _ q está dada por la sigu-
iente tabla:
p q p _ q
1 1 1
1 0 1
0 1 1
0 0 0
En este caso la única manera en que no salga agua es que ambos grifos
estén cerrados
q
p
Favián Arenas. 15 Camargo Benítez.
1.8 Clases de proposiciones Lógica Matemática
1.8.3. Proposiciones disyuntivas exclusivas p Y q
Dos enunciados se pueden combinar con la palabra .o"para formar un
enunciado compuesto llamado la disyunción de los enunciados originales.
Simbólicamente, p Y q denota la disyunción de los enunciados p y q, quese lee "p o q".
La tabla de verdad del enunciado compuesto p Y q está dada por la sigu-iente tabla:
p q p Y q
1 1 0
1 0 1
0 1 1
0 0 0
1.8.4. Proposiciones condicionales, p! q
Cuando se unen dos proposiciones con el conectivo �entonces�, se forma
una proposición que solo es falsa si las primera es verdadera y la segunda es
falsa (solo en este orden).
Ejemplo 2.
Sea p : El canguro es marsupial ( 1 )
q : America es habitat de todos los marsupiales ( 0 )
El canguro es marsupial entonces América es habitat de todos los marsu-
piales.
en forma simbólica
Favián Arenas. 16 Camargo Benítez.
1.8 Clases de proposiciones Lógica Matemática
p q p! q
1 0 0
En las proposiciones condicionales llamamos a la primera proposición
que la compone �antecedente�y a la segunda �consecuente�. Cuando el an-
tecedente tiene una relación directa con el consecuente podemos utilizar el
símbolo de la implicación �=)�
La suma de dos números naturales es un número natural esto implica que
2+3 es número natural
La tabla de verdad de la proposición compuesta p ! q está dada por la
siguiente tabla:
p q p! q
1 1 1
1 0 0
0 1 1
0 0 1
Ahora el grifo p tiene un problema, se encuentra mal y cuando alguien
la abre esta se cierra, cuando alguien la cierra esta se abre, por eso la única
forma en que no salga agua es que se abra p (en realidad se cierra) y se cierre
q
1.8.5. Proposiciones bicondicionales, p$ q
Cuando se unen dos proposiciones con el conectivo �si y solo si�, se forma
una proposición que solo es falsa si las dos tienen valores de verdad diferentes.
Favián Arenas. 17 Camargo Benítez.
1.8 Clases de proposiciones Lógica Matemática
q
p
Ejemplo 3.
Sea p : todo número impar es primo ( 0 )
q : 9 es menor que 6 ( 0 )
Todo número impar es primo si y solo si 9 es menor que 6, es como decir:
Todo número impar es primo única y exclusivamente si 9 es menor que 6
Como ambas proposiciones son falsas se cumple la a�rmación compuesta
La tabla de verdad del enunciado compuesto p $ q está dada por la
siguiente tabla:
p q p$ q
1 1 1
1 0 0
0 1 0
0 0 1
La proposición bicondicional p$ q es equivalente por su tabla de verdad a
(p! q) ^ (q ! p)
Favián Arenas. 18 Camargo Benítez.
1.8 Clases de proposiciones Lógica Matemática
q
p
q
p
Compruebe la tabla de verdad para este circuito de acueducto:
p q (p! q) ^ (q ! p)
1 1
1 0
0 1
0 0
1.8.6. Proposiciones negativas:� p
Aunque no es un conectivo lógico (como _;^;Y ,=);,) genera nuevasproposiciones con solo cambiarle el valor de verdad y se simboliza anteponien-
do ���a la letra de la proposición:
Ejemplos:
p : todo número impar es primo
� p : no todo número impar es primo
q : 9 es menor que 6
� q : 9 no es menor que 6
La tabla de verdad de la negación de p : � p está dada por la siguiente tabla:
Favián Arenas. 19 Camargo Benítez.
1.8 Clases de proposiciones Lógica Matemática
Problema 1.
p
p � p
1 0
0 1
Problema 2. Supóngase que en este circuito de acueducto llamamos abrir
con el 1 y cerrar con el 0. Si sale agua 1 y si no sale 0. Completa la
siguiente tabla de acuerdo a la grá�ca.
p
r
q
Favián Arenas. 20 Camargo Benítez.
1.8 Clases de proposiciones Lógica Matemática
grifo p grifo q grifo r ¿Sale?
1 1 1
1 1 0
1 0 1
1 0 0
0 1 1
0 1 0
0 0 1
0 0 0
1.8.7. Validación de leyes lógicas
A partir de las tablas de verdad anteriores se pueden calcular la tabla de
verdad de proposiciones mas complejas.
Ejemplo 4. Hallar La tabla de verdad de la proposición: (p! q)^ (q_ � p)
para esto se determinan inicialmente las tablas de:p; q;� p; p! q; q_ � p
y por último (p! q) ^ (q_ � p)
p q � p p! q q_ � p (p! q) ^ (q_ � p)
1 1 0 1 1
1 0 0 0 0
0 1 1 1 1
0 0 1 1 1
Favián Arenas. 21 Camargo Benítez.
1.8 Clases de proposiciones Lógica Matemática
El número de líneas de la tabla de verdad depende del número de variables
de la expresión y se puede calcular por medio de la siguiente formula.
No de líneas = 2n
Donde n = número de variables distintas.
El propósito de estas tablas de verdad consiste en probar si dos proposi-
ciones son equivalentes o no, o tal vez si una implica a la otra.
Ejemplo 5. Veamos, se desea probar que (p! q) es equivalente a (� p_ q)
para eso validamos la proposición (p! q), (� p _ q) mediante su tabla de
verdad
Ejemplo 6.
p q � p p! q � p _ q (p! q), (� p _ q)
1 1 0 1 1 1
1 0 0 0 0 1
0 1 1 1 1 1
0 0 1 1 1 1
Nótese que el valor de verdad es en todo caso verdadero, cuando esto
ocurre le llamamos TAUTOLOGÍA, cuando tenemos una tautología ten-
emos una ley lógica.
Veamos otro ejemplo: (p! q) ^ (p! r)) p! (q ^ r)
Favián Arenas. 22 Camargo Benítez.
1.8 Clases de proposiciones Lógica Matemática
p q r (p! q) (p! r) (q ^ r)
1 1 1 1 1 1
1 1 0 1 0 0
1 0 1 0 1 0
1 0 0 0 0 0
0 1 1 1 1 1
0 1 0 1 1 0
0 0 1 1 1 0
0 0 0 1 1 0
(p! q) ^ (p! r) p! (q ^ r) (p! q) ^ (p! r)) p! (q ^ r)
1 1 1
0 0 1
0 0 1
0 0 1
1 1 1
1 1 1
1 1 1
1 1 1
Un ejemplo de las leyes lógicas son :
Leyes de Idempotencia
p ^ p, p
p _ p, p
Favián Arenas. 23 Camargo Benítez.
1.8 Clases de proposiciones Lógica Matemática
Leyes conmutativas
p ^ q , q ^ p
p _ q , q _ p
p Y q , q Y p
p$ q , q $ p
Leyes asociativas
p ^ (q ^ r), (p ^ q) ^ r
p _ (q _ r), (p _ q) _ r
p$ (q $ r), (p$ q)$ r
Leyes distributivas
p ^ (q _ r), (p ^ q) _ (p ^ r)
p _ (q ^ r), (p _ q) ^ (p _ r)
Leyes de absorción
p ^ (p _ q), p
p _ (p ^ q), p
Leyes de Morgan
Favián Arenas. 24 Camargo Benítez.
1.8 Clases de proposiciones Lógica Matemática
� (p ^ q), � p_ � q
� (p _ q), � p^ � q
Leyes de Involución
� (� p), p
Problema 3. aplica la validación de tablas para probar las anteriores leyes.
Tambien hay ocasiones en que lo que se desea probar es que dos proposi-
ciones no pueden ser simultáneamente verdaderas. veamos
Ejemplo 7. pruebe que las proposiciones p es excluyente con � p
se debe validar (p^ � q)
p q � q (p^ � q)
1 1 0 0
1 0 1 0
0 1 0 0
0 0 1 0
Ejemplo 8. pruebe que las proposiciones (p^ � q) es excluyente con (p! q)
se debe validar (p^ � q) ^ (p! q)
Favián Arenas. 25 Camargo Benítez.
1.9 Cuanti�cadores Lógica Matemática
p q � q p! q (p^ � q) (p^ � q) ^ (p! q)
1 1 0 1 0 0
1 0 1 0 1 0
0 1 0 1 0 0
0 0 1 1 0 0
A casos como estos donde la tabla termina solo con ceros se le llama
CONTRADICCIÓN
1.9. Cuanti�cadores
Si, en una condición dada p(x), atribuimos a la variable x los valores
de su dominio, obtendremos, como vimos, una proposición. Otra forma, ex-
tremadamente importante en Matemática, de obtener proposiciones a partir
de una condición p(x), es anteponerle a esta los símbolos 8x; 9x y 9!x que
se llaman cuanti�cadores (cuanti�cador universal , cuanti�cador existencial
y cuanti�cador existencial de unicidad respectivamente).
La proposición 8x : p(x) se lee �para todo x, tal que p(x)�y signi�ca
que p(x) es verdadera, atribuyendo a x cualquier valor de su dominio.
La proposición 9x : p(x) se lee �existe un x, tal que p(x)�y signi�ca que
p(x) es verdadera, para algún x de su dominio, ün"no signi�ca "único". por
ejemplo "María Teresa tiene una amiga que la quiere mucho"es posible que
tenga más de una, es por esto que la proposición 9!x : p(x) se lee �existe un
único x, tal que p(x)�y signi�ca que p(x) es verdadera si y solo si x toma
un único valor de su dominio.
Favián Arenas. 26 Camargo Benítez.
1.9 Cuanti�cadores Lógica Matemática
Por ejemplo, siendo x una variable real, son verdaderas las proposiciones:
1) 8x : x2 + 1 > 0
2) 9x : x2 � 4 = 0
3) 9!x : 8x� 4 = 0
Justi�cación:
1) Como ningún número al cuadrado es negativo
8x : x2 � 0
8x : x2 + 1 � 0 + 1
8x : x2 + 1 � 1 y como 1 > 0
8x : x2 + 1 > 0
2) Mostremos los valores de x en los cuales:x2 � 4 = 0 ;
x2 = 4
x = �p4
x = �2
solo con lo valores �2 y 2 la proposición es verdadera
3) Se pide 8x� 4 = 0 así que el valor de x es:
8x� 4 = 0
8x = 4
x = 48
x = 2
y este es el único valor de x que lo hace verdadero
Favián Arenas. 27 Camargo Benítez.
1.10 Actividades Lógica Matemática
1.10. Actividades
Ejercicio 1. 1. ¿Cuáles de los enunciados siguientes pueden considerarse
como proposiciones
a) Si llueve es porque estamos en invierno.
b) Un triángulo es una �gura plana con tres lados.
c) Un triángulo es un polígono de tres ángulos.
d) La �losofía es triangular
e) 52 = 21
f) Un cuadrado es una �gura plana de cuatro lados.
g) Un cuadrado es un polígono de cuatro ángulos rectos
h) Un rectángulo es un polígono de cuatro ángulos rectos.
i) Medellín es ciudad de eterna primavera.
j) Un rectángulo es una �gura verde.
k) x2 + 3x� 4 = 0
l) Todas las naranjas son amarillas.
m) Algunas manzanas son rojas.
2. Para que la proposición abierta x+5 < 10 tenga valor de verdad falso,
x debe reemplazarse por:
a) 2
b) 3
Favián Arenas. 28 Camargo Benítez.
1.10 Actividades Lógica Matemática
c) 4
d) 5
3. En la proposición: � Sí respetamos la vida entonces Colombia será un
país feliz�. Podemos escoger:
p : Respetamos la vida
q :Colombia será un país feliz
Se construyó la tabla de verdad para esta proposición compuesta, pero
tiene un error. Localízalo, marcando con x el renglón correcto
p q p! q
1 0 1
0 0 1
1 1 1
0 1 1
4. �Una �gura de 4 lados se llama cuadrilátero, si tiene 5 lados se llama
pentágono, si tiene 6 lados se llama hexágono�En el enunciado anterior
identi�ca todas las proposiciones cerradas.
(Represéntalas con las letras p, q, r).
5. Con las proposiciones clasi�cadas en el ejercicio anterior. escribe en
palabras las proposiciones compuestas siguientes:
a) p!� q
b) � (p$ q)
Favián Arenas. 29 Camargo Benítez.
1.10 Actividades Lógica Matemática
c) (p! q )! (p! r)
6. Supón que p es verdadera, q es falsa y r es falsa ¿cómo es el valor de
verdad de las siguientes proposiciones
a) p^ � q
b) � (p! q)
c) (p _ q ) Y (p! r)
7. Completa las siguientes tablas de verdad
a)
p q � q � p � p^ � q p Y q (p Y q) _ (� p^ � q)
1 1 1
1 0 0
0 1 0
0 0 1
b)
p q � q p$ q p^ � q (p$ q)! (p^ � q)
1 1 1
1 0 0
0 1 0
0 0 1
Favián Arenas. 30 Camargo Benítez.
1.10 Actividades Lógica Matemática
c)
p q r ((p! r) ^ (q ! r))! r
1 1 1
1 1 0
1 0 1
1 0 0
0 1 1
0 1 0
0 0 1
0 0 0
8. Construye 3 frases que no sean proposiciones, 3 proposiciones, luego
niega las tres proposiciones.
9. Ana y José apostaron al marcador entre sus equipos favoritos de fútbol.
Al iniciarse el partido José le dice a Ana: �si mi equipo gana entonces
yo pago el almuerzo� La situación puede tener los resultados que se
muestran en la tabla. ¿En cual de todos José habrá mentido? Escríbelo
en la tabla.
p q ¿José cumplió?
Ganó el equipo de José v José pagó el almuerzo v
Ganó el equipo de José v José no pagó el almuerzo f
Perdió el equipo de José f José pagó el almuerzo v
Perdió el equipo de José f José no pagó el almuerzo f
10. Encuentre una expresión que solo contenga ^;_ y la negación �;para
representar:
Favián Arenas. 31 Camargo Benítez.
1.10 Actividades Lógica Matemática
a) p! q
b) p$ q
c) p Y q:
11. En el siguiente circuito eléctrico cada interruptor está representado por
una letra , encuentra la tabla de verdad que representa este circuito y
diseña otro circuito que tenga la misma tabla de verdad.
Favián Arenas. 32 Camargo Benítez.
Lógica Matemática
UNIDAD DE APRENDIZAJE II
2. Introducción a los Conjuntos
Las ideas esenciales de la teoría de conjuntos fue introducida por George.
Cantor, en la parte �nal del siglo XIX. Desde entonces la teoría dos con-
juntos no ha dejado de desarrollarse intensamente, de tal forma que ahora
puede decirse que todas las ramas de la Matemática fueron profundamente
in�uenciados y enriquecidos por esa teoría. Procuraremos en esta unidad de
aprendizaje introducir algunas de las ideas básicas de teoría de conjuntos,
evitando un tanto una formulación demasiado abstracta, o rigurosa.
La noción de conjunto es una de las que tiene la Matemática Moderna
(¿recuerda que es un punto en geometría? eso también es una noción) , en
donde los conceptos y no las de�niciones son adoptados como punto de par-
tida y sirven base para la de�nición de otros conceptos introducidos en el
desarrollo de la teoría. Intuitivamente, un conjunto es entendido como una
colección de objetos de cualquier natureza , los cuales se dicen elementos del
conjunto.
Favián Arenas. 33 Camargo Benítez.
2.1 Objetivos Lógica Matemática
2.1. Objetivos
El alumno conocerá, utilizará y aplicará los siguientes elementos básicos
para la solución de un problema:
Generalidades sobre que es un conjunto y sus Clases.
Generalidades sobre el álgebra de conjuntos y problemas.
Razonamiento sobre cardinalidad de conjuntos..
2.2. Competencias
Determina conjuntos por extensión y comprensión.
Mani�esta habilidad en la representación grá�ca de conjuntos y sus
operaciones.
Muestra interés participando en la construcción de proposiciones com-
puestas y nuevos conjuntos.
Reconoce a partir de una proposición el conjunto equivalente.
Comprende y demuestra las leyes logicas y de conjuntos.
Favián Arenas. 34 Camargo Benítez.
2.3 Estrategias pedagógicas o actividades de aprendizajeLógica Matemática
2.3. Estrategias pedagógicas o actividades de apren-
dizaje
Mesa redonda.
Presentación de trabajos.
Sesión de Chat.
Sesión Foro.
Talleres
Encuentro presencial
2.4. Recursos de aprendizaje
Aula de clases,
Laboratorios
Auditorios.
Videobeam
Retroproyector.
Favián Arenas. 35 Camargo Benítez.
2.5 Teoría de conjuntos Lógica Matemática
2.5. Teoría de conjuntos
Elementos: la mínima parte de un objeto se denomina elementos, son
elementos los integrantes de una familia, son elementos los días de la semana,
son elementos los números de teléfonos de montería, son elementos las hojas
de un árbol, claro está esta es una noción que has escuchado antes y está
muy relacionado con otro objeto matemático llamado CONJUNTO.
Conjunto: se suele decir que una agrupación de elementos es un conjun-
to, pero también es conjunto aunque tenga solo un elemento o aunque no
tenga elementos; por lo tanto son conjuntos: la familia, la semana, el direc-
torio telefónico, un árbol, el grupo de presidentes de Colombia, el grupo de
mamíferos que ponen huevos.
Símbolos: Los conjuntos se representan con letras mayúsculas: A;B;C;...
Los elementos con letras minúsculas: a; b; c; :::
Al representarlos , para agrupar los elementos utilizamos llaves f g, tam-
bién podemos usar un diagrama de Venn, a veces es más fácil , por eso debes
utilizar las dos formas.
Ejemplo:
Representa el conjunto de los números dígitos
D = f0; 1; 2; 3; 4; 5; 6; 7; 8; 9g
o también
Relación de pertenencia. Si se tiene un conjunto A y un elemento a
y ocurre que a es un miembro de A, se dice, entonces, a pertenece a A y se
escribe a 2 A (a es un elemento de A).
Pero si se tiene un elemento c que no pertenece al conjunto A ,se escribe
Favián Arenas. 36 Camargo Benítez.
2.6 Clases de conjuntos Lógica Matemática
c =2 A (c no es un elemento de A).
2.6. Clases de conjuntos
Los conjuntos se clasi�can según el número de elementos que posean,
veamos:
Conjunto vacío:
Es aquel conjunto que no tiene elementos, como una bolsa vacía, se sim-
boliza con �
El conjunto de los números pares que terminan en 3
Representémoslo así:
P = flos números pares que terminan en 3 g = �
Conjunto unitario: es el que tiene un solo elemento.
B = { la capital de Colombia}
M = {Lucy}
C = f0g
Conjunto �nito: es aquel que tiene un número �nito de elementos .
También es �nito el conjunto unitario.
Favián Arenas. 37 Camargo Benítez.
2.7 Determinación de un conjuntoLógica Matemática
S = {lunes, martes, miércoles, jueves, viernes, sábado, domingo}
N = f3; 13; 23; 33; 34; 35g
T = {Miguel, José}
A = fa; b; c; d; :::; x; y; zg
Conjunto in�nito: si tiene tantos elementos que es imposible contarlos
se le llama conjunto in�nito.
N = f1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19; 20; 21; :::g
¿Conoces otro conjunto que sea in�nito? ¿Cuantos?
¿Que signi�ca los puntos suspensivos?
2.7. Determinación de un conjunto
Para determinar o identi�car un conjunto existen dos maneras:
Por extensión, que consiste en escribir todos y cada uno de los elementos
que lo conforman, así conociendo todos sus elementos conocemos el conjunto.
Por comprensión, esta consiste en indicar una característica especial y
común que tienen los elementos de un conjunto.
Ejemplo 9.
por extensión:
V = fa; e; i; o; ug
F = f1; 11; 21; 31; 41; 51; 61; 71; 81; 91; 101; 111; ::::g
Y = �
Por comprensión:
Favián Arenas. 38 Camargo Benítez.
2.7 Determinación de un conjuntoLógica Matemática
V={las vocales}
F={los números naturales que terminan en 1}
Y={los números impares que terminan en 0}
Subconjunto:
Si un conjunto B está contenido en un conjunto A, es porque todos los
elementos de B están en A; pero es posible que existan elementos en A, que
no estén en B.
Entonces B es un Subconjunto de A, o también se puede decir � B está
contenido en A�. Se representa con los símbolos: B � A
Así que:
(B � A)() (x 2 B =) x 2 A)
Favián Arenas. 39 Camargo Benítez.
2.8 Algebra de conjuntos Lógica Matemática
2.8. Algebra de conjuntos
Unión de Conjuntos Los conjuntos A = fa; b; c; d; eg y B = fa; e; i; o; ug
se combinan para formar un nuevo conjunto, donde ningún elemento puede
estar repetido fa; b; c; d; e; i; o; ug, a este conjunto lo llamaremos unión de A
y B.
M = f1; 2; 3; 4; 5g y J = f1; 3; 5; 7; 9g entonces
M [ J = f1; 2; 3; 4; 5; 7; 9g
En forma grá�ca la unión es la región resaltada
Simbólicamente la unión de A y B es:
AUB = fx : x 2 A _ x 2 Bg
Intersección de Conjuntos En esta operación de conjuntos se trata de
encontrar los elementos comunes a ambos conjuntos, es decir los repetidos,
veamos:
M = f1; 2; 3; 4; 5g y J = f1; 3; 5; 7; 9g entonces
Favián Arenas. 40 Camargo Benítez.
2.8 Algebra de conjuntos Lógica Matemática
La intersección la representamos por:
M \ J = f1; 3; 5g pues son los que se repiten. En forma grá�ca la inter-
sección es la región resaltada
Simbólicamente la intercepción de A y B es:
A \B = fx : x 2 A ^ x 2 Bg
Diferencia de Conjuntos En los conjuntos V = fa; e; i; o; ug y A =
fa; e; og
La diferencia de V � A es el conjunto formado por los elementos de V
que no están en A así:
V � A = fi; og
M = f1; 2; 3; 4; 5g y J = f1; 3; 5; 7; 9g entonces
La diferencia la representamos por:
M � J = f2; 4g pues son los que están en M y no en J .
También se puede calcular J �M
J �M = f7; 9g pues son los que están en J y no en M .
Favián Arenas. 41 Camargo Benítez.
2.8 Algebra de conjuntos Lógica Matemática
En forma grá�ca la diferencia es la región sombreada
Simbólicamente es:
M � J = fx : x 2M ^ x =2 Jg
J �M = fx : x 2 J ^ x =2Mg
Complemento Para esta operación debemos de�nir primero un conjunto
que nos sirva como base o referencia, lo simbolizarán con la letra U, se llamará
universal o referencial.
Si U = f0; 1; 2; 3; 4; 5; 6; 7; 8; 9g y el conjunto A = f0; 1; 2; 3g
Llamaremos complemento de A , al conjunto formado por todos los el-
ementos de U que no están en A, o sea f4; 5; 6; 7; 8; 9g, a este conjunto lo
denotaremos con A0
Notese que A0 = U � A
U = f1; 3; 5; 7; 11; 13; 17; 19; 23; 29g
Si B = f1; 11; 29g entonces B0 = f3; 5; 7; 13; 17; 19; 23g
Si C = f3; 5; 7; 17; 23g entonces C0 = f1; 11; 13; 19; 29g
Si D = f1; 3; 5; 7; 11; 13; 17; 19; 23; 29g entonces D0 = �
Simbólicamente es:
A0 = fx : x 2 U ^ x =2 Ag
Favián Arenas. 42 Camargo Benítez.
2.9 Propiedades de los ConjuntosLógica Matemática
2.9. Propiedades de los Conjuntos
Existen ciertas analogías entre los conectivos de las proposiciones y las
operaciones con conjuntos, una de ellas consiste en que todos los operadores
de conjuntos se pueden poderse reducir a combinaciones de intercepciones
y uniones, así como los conectivos de proposiciones se pueden reducir a los
conectivos 2"(^), .o"(_) y la negación (�).
La intersección de conjuntos es análoga a la conjunción de proposiciones \ � ^
La unión de conjuntos es análoga a la disyunción de proposiciones [ � _
El complemento de conjuntos es análogo a la negación de proposiciones A0 � � p
La contenencia de conjuntos es análoga a la implicación de proposiciones A � B � p! q
La diferencia de conjuntos es análoga a la implicación de proposicionesA�B = A \B0 �
p! q ,� p _ q
Por lo tanto gozan de propiedades semejantes a las proposiciones:
Leyes de Idempotencia
A \ A = A
A [ A = A
Leyes conmutativas
Favián Arenas. 43 Camargo Benítez.
2.9 Propiedades de los ConjuntosLógica Matemática
A \B = B \ A
A [B = B [ A
Leyes asociativas
p ^ (q ^ r), (p ^ q) ^ r
p _ (q _ r), (p _ q) _ r
p$ (q $ r), (p$ q)$ r
Leyes distributivas
A \ (B [ C) = (A \B) [ (A \ C)
A [ (B \ C) = (A [B) \ (A [ C)
Leyes de absorción
A \ (A [B) = A
A [ (A \B) = A
Leyes de Morgan
(A [B)0 = A0 \B0
(A \B)0 = A0 [B0
Leyes de Involución
(A0)0 = A
Favián Arenas. 44 Camargo Benítez.
2.10 Actividades Lógica Matemática
Veamos grá�camente la ley de Morgan (A [B)0 = A0 \B0
2.10. Actividades
1. Completa en el dibujo las cantidades correspondientes a cada sección
de la �gura y con esa información responde las preguntas a, b, c y d
36 personas fueron a Europa, visitaron España, Inglaterra o Francia, sin
embargo, no todas fueron a los tres lugares, para identi�car la cantidad exacta
Favián Arenas. 45 Camargo Benítez.
2.10 Actividades Lógica Matemática
de personas que fueron a cierto país, se especi�ca cada cantidad en el siguiente
diagrama de Venn.
21 personas fueron a Francia
17 personas fueron a España
16 personas fueron a Inglaterra
9 personas fueron a Francia y a España
8 personas fueron a España y a Inglaterra
6 personas fueron a Francia y a Inglaterra
1. a) El número de personas que fue a Francia y España pero no a
Inglaterra es:_______
b) El número de personas que fue a España o Inglaterra es:______
c) El número de persona que fue a Inglaterra, España y Francia
es:________
d) El número de personas que fue a España o Inglaterra pero no a
Francia es:______
2. Después de medir su peso en una balanza, se obtienen los siguientes
resultados:
Favián Arenas. 46 Camargo Benítez.
2.10 Actividades Lógica Matemática
Andrés es más liviano que Fernando, pero más pesado que Gabriela
Esteban es más liviano que Andrés, pero más pesado que Gabriela
Pedro es más liviano que Jorge, pero más pesado que Miguel
Jorge es más liviano que Gabriela
Ordena los jóvenes según su peso, comenzando con el más pesado.
(Paradoja de Russell) En un pueblo chico hay solo un barbero, y los
hombres del pueblo, por lo que se re�ere a la rasurada, se dividen en
dos grupos: los que se rasuran con el barbero, y los que se rasuran solos.
¿A cual de los dos grupos pertenece el barbero?
Explica.
Favián Arenas. 47 Camargo Benítez.
Lógica Matemática
UNIDAD DE APRENDIZAJE III
3. Introducción al Álgebra de Boole
En las dos unidades anteriores se vió que las leyes para las proposiciones
y para los conjuntos son semejantes. Podemos ahora demostrar que cada uno
de estos sistemas es un álgebra de Boole. Esta estructura algebraica mas
general es una de las partes del Algebra abstracta, que a pesar del nombre se
aplica podríamos decir que "demasiado.a la computación y a la inteligencia
Arti�cial. Esta unidad es fundamental, sobre todo para la simpli�cación de
circuitos (Unidad 4 ).
Favián Arenas. 48 Camargo Benítez.
3.1 Objetivos Lógica Matemática
3.1. Objetivos
El alumno conocerá, utilizará y aplicará los siguientes elementos básicos
para la solución de un problema:
Generalidades sobre que es un álgebra de Boole y como se prueba.
Generalidades sobre las leyes del álgebra de Boole y demostraciones.
Generalidades sobre las funciones de Boole con una o mas variables.
3.2. Competencias
Interpretará las demostraciones de las leyes del álgebra de Boole.
Compruebará si el conjunto en cuestión veri�ca las leyes del álgebra de
Boole.
Aplicará las leyes del álgebra de Boole para simpli�car funciones booleanas.
Armonizará los conocimientos de Tablas de verdad con las funciones
booleanas.
Favián Arenas. 49 Camargo Benítez.
3.3 Estrategias pedagógicas o actividades de aprendizajeLógica Matemática
3.3. Estrategias pedagógicas o actividades de apren-
dizaje
Mesa redonda.
Presentación de trabajos.
Sesión de Chat.
Sesión Foro.
Talleres
Encuentro presencial
3.4. Recursos de aprendizaje
Aula de clases,
Laboratorios
Auditorios.
Videobeam
Retroproyector.
Favián Arenas. 50 Camargo Benítez.
3.5 Clases de operaciones Lógica Matemática
3.5. Clases de operaciones
Hasta el momento hemos hablado de operaciones entre proposiciones y
entre conjuntos
Vale la pena clasi�car en general las operaciones
El primer tipo se llama operación binaria, y no sólo enlaza dos elementos,
sino que determina un tercero (el resultado de los otros dos) que pertenece al
conjunto que consideramos. Por lo tanto una OPERACIÓN BINARIA
� es una .operación tal que:
si a; b 2 X,entonces también la es a� b
Ejemplo 10. la Suma en el conjunto de los naturales es una operación bi-
naria
pues si m;n 2 N;entonces m+ n 2 N:
Ejemplo 11. la Resta en el conjunto de los naturales no es una operación
binaria pues existen elementos de N; como por ejemplo 7 y 12 tal que 7�12 =
�5 =2 N:
Ejemplo 12. la división en el conjunto de los naturales no es una operación
binaria pues existen elementos de N; como por ejemplo 9 y 2 tal que 9�2 =9
2=2 N:
Ejemplo 13. La operación > en el conjuntofa; b; cg se de�ne como sigue en
la siguiente tabla:
> a b c
a a b a
b b a c
c a c a
Favián Arenas. 51 Camargo Benítez.
3.5 Clases de operaciones Lógica Matemática
El segundo tipo de operación se llama operación unitaria, esta en reali-
dad transforma un número en otro, por lo tanto unaOPERACIÓN UNI-
TARIA ' sobre un conjunto B es una .operación tal que:
Si a 2 B, entonces '(a) 2 B
Ejemplo 14. el operador menos (�) el conjunto de los enteros es una op-
eración binaria
pues si m 2 Z;entonces �m 2 Z:
Ejemplo 15. la Radicación en el conjunto de los números reales es una
operación binaria si y solo si es raíz impar; es decir el operador 2n+1p� es
una operación binaria con n 2 N
pero el operador 2np� no es una operación binaria con n 2 N
nótese que �1 2 R pero 2np�1 =2 R:
1. Dígase cuáles de las siguientes son operaciones unitarias
a) la operación "tomar el inverso de"en el conjunto de los números
reales.
b) la operación "tomar el inverso de"en el conjunto de los números
enteros.
c) encuéntrese otro conjunto sobre el cual "tomar el inverso de"sea
una operación unitaria.
2. En qué circunstancias son +;�;�;�; operaciones binarias:
Favián Arenas. 52 Camargo Benítez.
3.6 Álgebra de Boole Lógica Matemática
a) En el sistema de los números reales o subconjuntos de este sistema.
b) En el sistema de los números complejos.
3.6. Álgebra de Boole
Un conjunto B, junto con las operaciones binarias �;� de�nidas sobre éles un álgebra de Boole,
si se veri�can las siguientes Propiedades:
Ley conmutativa
1. a) 1) 8a; b 2 B; a� b 2 B
2) 8a; b 2 B; a� b 2 B
Ley distributiva
1. a) 1) 8a; b; c 2 B; a� (b� c) = (a� b)� (a� c)
2) 8a; b; c 2 B; a� (b� c) = (a� b)� (a� c)
Elementos neutros
1. a) 1) 8a 2 B; 9e 2 B; a� e = a (Neutro Aditivo o cero)
2) 8a 2 B; 9i 2 B; a � i = a (Neutro Multiplicativo o
unidad)
Complementación
1. a) 1) 8a 2 B; 9ac 2 B; a� ac = i (complemento a la unidad)
Favián Arenas. 53 Camargo Benítez.
3.6 Álgebra de Boole Lógica Matemática
2) 8a 2 B; 9ac 2 B; a� ac = e (complemento al cero)mas adelante se probará que ac es el mismo en ambos casos.
Ejemplo 16. Sea D26 = f1; 2; 13; 26g el conjunto de los divisores positivos
del 26; de�namos las operaciones binarias así:
a� b =MCM(a; b) ( Mínimo Común múltiplo)
a� b = mcd(a; b) ( Máximo Común divisor)
observe que para que a � b = a; b tiene que ser 1(Neutro Aditivo o
cero)
y para que a � b = a; b tiene que ser 26(Neutro Multiplicativo o
unidad)
por otra parte:
para que a�b = 26; tiene que ser b = 26
a(complemento de la unidad)
y para que a� b = 1; depende de quien sea a así:si a = 1 entonces b = 26
si a = 2 entonces b = 13
si a = 13 entonces b = 2
si a = 26 entonces b = 1
Para representar estas operaciones utilizaremos tablas algo parecidas a las
de la escuela.
� 1 2 13 26
1 1 2 13 26
2 2 2 26 26
13 13 26 13 26
26 26 26 26 13
� 1 2 13 26
1 1 1 1 1
2 1 2 1 2
13 1 1 13 13
26 1 2 13 26
Favián Arenas. 54 Camargo Benítez.
3.7 Principio de dualidad Lógica Matemática
3.7. Principio de dualidad
Si en un teorema válido intercambiamos � por � y e por i, obtenemos
otro teorema válido.
La demostración de que esto es cierto se obtiene haciendo este intercambio
en todos los pasos de la demostración del teorema original.
Solo por comodidad cambiaremos los signos de las operaciones a� b pora + b; a � b por ab; aclaramos que estos signos representarán las dos op-eraciones del álgebra de Boole las cuales pueden ser cualesquier operación
binaria. Ademas cambiaremos los elementos neutros e por 0; i por 1; sin
querer con esto confundirlos.
A continuación se plantearán otras Propiedades de las Algebras de Boole,
se realizarán las pruebas de estas propiedades para uno de ellas y la otra la
realizará el estudiante con el principio de dualidad.
Ley de idempotencia
1. a) 1) 8a 2 B; a+ a = a
2) 8a 2 B; aa = a
Prueba (i): Sea a 2 B a = a + 0 = a + (aac) = (a+ a) (a+ ac) =
(a+ a) (1) = a+ a �
Ley de acotamiento
1. a) 1) 8a 2 B; a+ 1 = 1
Favián Arenas. 55 Camargo Benítez.
3.7 Principio de dualidad Lógica Matemática
2) 8a 2 B; a0 = 0
Prueba (i): Sea a 2 B a+1 = (a+ 1) 1 = (a+ 1) (a+ac) = a+(1ac) =
a+ ac = 1 �Ley de absorción
1. a) 1) 8a; b 2 B; a+ ab = a
2) 8a; b 2 B; a(a+ b) = a
Prueba (i): Sea a; b 2 B a+ ab = a1 + ab = a(1 + b) = a(1) = a �Ley asociativa
1. a) 1) 8a; b; c 2 B; a+ (b+ c) = (a+ b) + c
2) 8a; b; c 2 B; a(bc) = (ab)c
Prueba (i): Sea a; b; c 2 B
a+ (b+ c) = 1 [a+ (b+ c)]
= aca [a+ (b+ c)]
= ac [aa+ a (b+ c)]
= ac [a+ a (b+ c)]
= aca
= ac [a+ ac]
= ac [a (a+ b) + ac]
= aca [(a+ b) + c]
= 1 [(a+ b) + c]
= (a+ b) + c �
Favián Arenas. 56 Camargo Benítez.
3.7 Principio de dualidad Lógica Matemática
Unicidad del complemento
1. a) 1) 8a 2 B; (a+ x = 1) ^ (ax = 0)) x = ac
Prueba (i): Sea a 2 B supóngase a+ x = 1 y ax = 0
ac = ac1 = ac (a+ x) = aca + acx = 0 + acx = acx = ac(x + 0) =
acx+ ax = (ac + a)x = 1x = x �Ley de involución
1. a) 1) 8a 2 B; (ac)c = a
Prueba (i): Sea a 2 B a + ac = 1; esto signi�ca que a es el
complemento de ac; es decir a = (ac)c �
Ley de Morgan
a) 1) 8a; b 2 B; (a+ b)c = acbc
2) 8a; b 2 B; (ab)c = ac + bc
Prueba (i): Sea a; b 2 B (a+ b) + acbc = a + (b+ acbc) = a +
(b+ ac)(b+ bc)
= a + (b + ac)1 =
a+ b+ ac = a+ ac + b = 1 + b = 1
con esto por la unicidad del complemento (a+ b)c = acbc �
Favián Arenas. 57 Camargo Benítez.
3.8 Funciones booleanas Lógica Matemática
3.8. Funciones booleanas
3.8.1. Funciones reales y funciones booleanas
Hasta ahora se ha mostrado en qué operaciones se basa el Algebra de
Boole y algunas de sus
propiedades.
Utilizando expresiones booleanas, vamos a de�nirFunciones booleanas,
que son muy parecidas a las funciones matemáticas a las que estamos acos-
tumbrados pero con la particularidad de que las variables son booleanas y
que los valores devueltos por la función también son booleanos, es decir, una
función booleana sólo puede tomar los valores �0�ó �1�.
Como hemos hecho antes, vamos a ver un ejemplo utilizando una función
matemática de las
que todos conocemos. Por ejemplo esta:
f(x) = 2x+ 1
Se trata de una función Real que tiene una variable Real (x) es decir el
dominio de f es R
Favián Arenas. 58 Camargo Benítez.
3.8 Funciones booleanas Lógica Matemática
52.50-2 .5-5
10
5
0
-5
x
y
x
y
hay una in�nidad de valores en el dominio de f por esto se obtiene una
in�nidad de puntos en forma de una recta.
También podemos de�nir funciones reales de 2 ó más variables, como por
ejemplo:
f(x; y) = 2x+ y2
f(x; y; z) = z2 � sen(x+ y)
f(x1; x2; x3; :::; xn) = 3px1 + x2 + x3 + :::+ xn
Como estamos acostumbrados a trabajar con este tipo de funciones, nos
resultan claras. Ahora
vamos a de�nir funciones booleanas. Para ello hay que tener presente que
trabajaremos con
variables booleanas y que por tanto usaremos las operaciones + y � del
Algebra de Boole.
Favián Arenas. 59 Camargo Benítez.
3.8 Funciones booleanas Lógica Matemática
Ejemplo 17. sea la siguiente función booleana de una variable:
f(x) = xc
El valor devuelto por la función es el complemento del valor de la variable.
Como la variable x es booleana, sólo puede tomar los valores �0�y �1�.
Los que la función F toma son:
f(0) = 0c = 1
f(1) = 1c = 0
Ejemplo 18.
Ejemplo 19. Sea la siguiente función booleana se dos variables:
f(x; y) = xc � (x+ y)
obtenemos:
f(0; 0) = 0c � (0 + 0) = 1 � 0 = 0
f(0; 1) = 0c � (0 + 1) = 1 � 1 = 1
f(1; 0) = 1c � (1 + 0) = 0 � 1 = 0
f(1; 1) = 1c � (1 + 1) = 0 � 0 = 0
Antes de calcular los valores que toma la función, se pueden aplicar algu-
nas propiedades para obtener una función más simpli�cada:
del ejemplo anterior
f(x; y) = xc � (x+ y)
= xcx+ xcy (ley distributiva)
= 0 + xcy (complemento al cero)
= x0y
Favián Arenas. 60 Camargo Benítez.
3.8 Funciones booleanas Lógica Matemática
en el cual también obtenemos:
f(0; 0) = 00 � 0 = 1 � 0 = 0
f(0; 1) = 00 � 1 = 1 � 1 = 1
f(1; 0) = 10 � 0 = 0 � 1 = 0
f(1; 1) = 10 � 1 = 0 � 0 = 0
3.8.2. Funciones booleanas y tablas de verdad
Existe otra manera de representar una función booleana. es mediante las
tablas de verdad, pero cambiando las proposiciones por expresiones booleanas:
utilizaremos nuevamente el ejemplo anterior:
f(x; y) = xc � (x+ y)
su tabla es:
x y f(x; y)
1 1 0
1 0 0
0 1 1
0 0 0
El número de �las de la tabla de verdad depende del número de variables
que usemos.
consideremos h(x; y; z) = x+ yz
Favián Arenas. 61 Camargo Benítez.
3.8 Funciones booleanas Lógica Matemática
x y z yz x+ yx
1 1 1 1 1
1 1 0 0 1
1 0 1 0 1
1 0 0 0 1
0 1 1 1 1
0 1 0 0 0
0 0 1 0 0
0 0 0 0 0
Favián Arenas. 62 Camargo Benítez.
3.9 Actividades Lógica Matemática
3.9. Actividades
Ejercicio 2. Probar las siguientes equivalencias de expresiones por los méto-
dos de:
1. a) Tablas de verdad.
b) Transformaciones algebraicas(propiedades del álgebra de Boole)
abc + acb+ acbc = ac + bc
acbc + ac+ bcc = accc + bcc+ ab
acbc + bd+ abc = d+ dcbc
(a+ bc + ab)(ac + b)abc = 0
(a+ bc + abc)(ab+ bcc + acc) = ab+ acbcc
(ab+ c+ d)(cc + d)(cc + d+ e) = abcc + d
Ejercicio 3. 1. Demostrar las siguientes propiedades de la función lógica
O-exclusiva:
f(p; q) = p Y q
a) Asociativa
b) Conmutativa
c) Existencia de elemento neutro e tal que x Ye = x
d) Existencia de Inverso (A todo elemento x se le puede hacer corre-
sponder un elemento x tal que x Y y = e
Favián Arenas. 63 Camargo Benítez.
3.9 Actividades Lógica Matemática
e) Distributiva del Producto respecto a la O-exclusiva
f) que mediante la O-exclusiva y la función y : f(p; q) = p^q se pueden
realizar las otras dos operaciones fundamentales del álgebra de Boole:
negación y suma(disyunción)
Nota: Calcular el valor de 1 Yx y de 1 Y ((1 Y x)(1 Y y))
Una función de tres variables f(a,b,c) debe tomar el valor cero cuando la
variable b esté a uno y la variable a no está en estado uno. En los demás
casos posibles debe estar en estado uno.
a) Realizar la tabla de verdad de la función.
Discurso sobre los estudios de Informática en clase de Lógica:
Señoras y señores, buenas tardes:
Es hora de que recapacitemos sobre los estudios de informática en vísperas
del asentamiento de la titulación en nuestra Universidad. Se sabe que si los
ordenadores hablasen los informáticos no existirían. Por otra parte, en la últi-
ma reunión del Consejo de Universidades, éste a�rmó que: "...la Universidad
titulará informáticos mientras los ordenadores no hablen ..."; a�rmación que
nos parece muy correcta, si bien lo cierto es que los ordenadores no hablan
pero los informáticos existen.
A la vista de todo ello nos preguntamos: ¿Es, por tanto, coherente que la
Universidad expida títulos de informática en la actualidad?.
Demuestre las leyes del algebra de Boole que no se probaron aplicando el
principio de dualidad.
Favián Arenas. 64 Camargo Benítez.
Lógica Matemática
UNIDAD DE APRENDIZAJE IV
4. Introducción al método de Karnaugh
El método de Karnaugh convierte una expresión booleana a otra más simpli-
�cada. En nuestro caso, convierte una suma de productos en otra minimal .
Tiene como características:
Un mínimo número de términos en la expresión.
Un mínimo número de variables en cada término de dicha expresión.
Inicialmente se tiene una expresión booleana constituida por una suma
de productos de variables, que pueden tomar únicamente los valores de cero
[0] o uno [1]. El resultado de esta expresión es un valor booleano para cada
uno de los valores que tomen dichas variables.
Favián Arenas. 65 Camargo Benítez.
4.1 Objetivos Lógica Matemática
4.1. Objetivos
El alumno conocerá, utilizará y aplicará los siguientes elementos básicos
para la solución de un problema:
Entradas y salidas de las compuertas lógicas.
tablas de verdad a partir de mediciones en compuertas lógicas.
Simpli�cación Tabular mediante Mapas de Karnaugh
4.2. Competencias
Deduce la relación existente entre las entradas y salidas de las com-
puertas lógicas.
Construye tablas de verdad a partir de mediciones en compuestos lógi-
cos.
Representa funciones lógicas mediante simbología electrónica normal-
izada y de uso tradicional.
Reconoce por su símbolo, forma o nomenclatura las diferentes funciones
lógicas.
Favián Arenas. 66 Camargo Benítez.
4.3 Estrategias pedagógicas o actividades de aprendizajeLógica Matemática
4.3. Estrategias pedagógicas o actividades de apren-
dizaje
Mesa redonda.
Presentación de trabajos.
Sesión de Chat.
Sesión Foro.
Talleres
Encuentro presencial
4.4. Recursos de aprendizaje
Aula de clases
Laboratorios
Auditorios.
Videobeam
Retroproyector.
Favián Arenas. 67 Camargo Benítez.
4.5 Método de Karnaugh para la Simpli�cación de circuitosLógica Matemática
4.5. Método de Karnaugh para la Simpli�cación de cir-
cuitos
Las señales de tensión alta ( mas de 1 voltio) o bajas (menos de 1 voltio)
han dado lugar a su vez a representaciones electrónicas que se utilizan en el
diseño de los circuitos integrados. Estos circuitos se conocen como çircuitos
lógicos"pues basan su función en condiciones presenciales o no de los pulsos
altos o bajos.
En los circuitos digitales todos los voltajes, a excepción de las fuentes de
alimentación, se agrupan en dos posibles categorías: voltaje altos y voltajes
bajos. Entre estos dos rangos de voltajes existen existe una denominada zona
prohibida o de incertidumbre que los separa. Una tensión alta signi�ca un 1
binario y una tensión baja signi�ca un 0 binario. Todos los sistemas digitales
se construyen utilizando básicamente tres puertas lógicas básicas. Estas son
las puertas AND, la puerta OR y la puerta NOT; o la combinación de estas.
El recurso a las tablas para la simpli�cación de ecuaciones booleanas
es, como ya se ha dicho, fruto de su mayor simplicidad. Aunque existen
otros métodos (como las tablas de Quine- McCluskey), nos limitaremos a
explicar someramente el método conocido como �mapas de Karnaugh�. Éstos
se pueden utilizar para simpli�car funciones de dos a seis variables, aunque
habitualmente sólo se los emplee para funciones de dos a cinco variables.
El método grá�co de Karnaugh, desarrollado en The Map Method for
Synthesis of Combinatorial Logic Circuits (AIEE, vol. 72, 1953), se basa en
otro de E. W. Veitch publicado en A Chart Method for Simplifying Truth
Functions (ACM, 1952). Esta técnica se convirtió rápidamente en la her-
ramienta más potente entre los diseñadores de computadores y expertos en
Favián Arenas. 68 Camargo Benítez.
4.5 Método de Karnaugh para la Simpli�cación de circuitosLógica Matemática
lógica digital durante la década de los 50.
LA COMPUERTA AND
BA
El esquema de la �gura, da una idea de funcionamiento de la compuerta
AND. Examinando de cerca el circuito, notamos que la lámpara encenderá
solo si ambos interruptores se cierran o se activan simultáneamente. Si uno
de los interruptores esta abierto, el circuito se interrumpe y la lámpara no se
enciende. Todas las posibles combinaciones para los interruptores A y B se
muestran en la tabla de verdad.
A B Lampara
1 1 1
1 0 0
0 1 0
0 0 0
Favián Arenas. 69 Camargo Benítez.
4.5 Método de Karnaugh para la Simpli�cación de circuitosLógica Matemática
La tabla de esta �gura es la misma que la de la conjunción, es decir dos
interruptores en serie se representan con la compuerta AND
Para representar una compuerta AND se utilizará el símbolo siguiente
Esta compuerta AND es un dispositivo que posee dos entradas A y B y
una salida A �B.
El álgebra booleana es una forma de lógica simbólica que muestra como
operan las compuertas lógicas. Una expresión booleana es un método de
mostrar que ocurre en un circuito lógico.
A� B = Y es la expresión booleana de la compuerta AND se lee .A AND
B igual a la salida Y"
El punto (�) signi�ca la función lógica AND en álgebra booleana, y no la
operación de multiplicar como en el álgebra corriente.
En caso de que el circuito lógico tenga tres variables.
la expresión A �B � C se lee " A AND B AND C" y se representa con la
�gura:
Favián Arenas. 70 Camargo Benítez.
4.5 Método de Karnaugh para la Simpli�cación de circuitosLógica Matemática
La tabla de verdad de esta última coincide con el conjuntivo múltiple
p ^ q ^ r
es decir:
p q r p ^ q ^ r
1 1 1 1
1 1 0 0
1 0 1 0
1 0 0 0
0 1 1 0
0 1 0 0
0 0 1 0
0 0 0 0
LA COMPUERTA OR El grá�co de este circuito ilustra el fun-
cionamiento de la compuerta OR, en el cual los interruptores han sido conec-
tados en paralelo. El encendido de la lámpara se producirá si se cierra
Favián Arenas. 71 Camargo Benítez.
4.5 Método de Karnaugh para la Simpli�cación de circuitosLógica Matemática
cualquiera de los dos interruptores o ambos. Todas las posibles combina-
ciones de los interruptores se muestran en la tabla siguiente.
A B Lampara
1 1 1
1 0 1
0 1 1
0 0 0
La tabla de esta �gura es la misma que la de la disyunción, es decir dos
interruptores en serie se representan con la compuerta OR
Para representar una compuerta OR se utilizará el símbolo siguiente:
Esta compuerta OR es un dispositivo que posee dos entradas A y B y
una salida A+B.
Favián Arenas. 72 Camargo Benítez.
4.5 Método de Karnaugh para la Simpli�cación de circuitosLógica Matemática
A + B = Y es la expresión booleana de la compuerta OR se lee .A OR
B igual a la salida Y"
El signo mas (+) signi�ca la función lógica OR en álgebra booleana, y no
la operación de sumar como en el álgebra corriente.
En caso de que el circuito lógico tenga tres variables.
la expresión A+B+C se lee A OR B OR C y se representa con la �gura:
COMPUERTA INVERSORA En este circuito cuando se cierra el inter-
Favián Arenas. 73 Camargo Benítez.
4.5 Método de Karnaugh para la Simpli�cación de circuitosLógica Matemática
ruptor A, la bombilla se apaga,(¿Por qué?), al abrir el interruptor la bombilla
se enciende.
La tabla es:
A lámpara
1 0
0 1
Es la misma tabla de la negación � p; a este esquema se le llama La
compuerta inversora,
esta posee una entrada y una salida como se muestra en la �gura. Su fun-
ción es producir una salida inversa o contraria a su entrada es decir convertir
unos a ceros y ceros a unos.
El círculo inversor puede estar en la parte de entrada o de salida del
símbolo triangular.
Favián Arenas. 74 Camargo Benítez.
4.5 Método de Karnaugh para la Simpli�cación de circuitosLógica Matemática
este tiene el mismo sentido de el complemento a la unidad del álgebra de
Boole.
con solo estas tres compuertas se pueden conformar otras como las sigu-
ientes:
LA PUERTANAND Una compuerta NAND es un dispositivo lógico que
opera en forma exactamente contraria a, una compuerta, AND, entregando
una salida baja cuando todas sus entradas son altas y una salida alta mientras
exista por lo menos un bajo a cualquiera de ellas:
En forma proposicional � (p ^ q).
En forma de expresión booleana (AB)0.
Observar que el símbolo NAND es símbolo AND con un pequeño círculo
a la salida.
Favián Arenas. 75 Camargo Benítez.
4.5 Método de Karnaugh para la Simpli�cación de circuitosLógica Matemática
LA PUERTA NOR Se ha conectado un inversor a la salida de una puerta
OR, obsérvese que se ha añadido un pequeño circulo inversor al símbolo OR
para formar el símbolo NOR.
Debido a que los interruptores A y B están en paralelo entre si y con
la lámpara (Y) esta ultima solo enciende cuando ambos interruptores están
abiertos y permanece apagada mientras cualquiera de ellos , o ambos estén
cerrados.
Símbolo lógico de una compuerta NOR es:
Podemos decir que este dispositivo lógico opera en forma exactamente
opuesta a una compuerta OR , entregando una salida alta cuando todas sus
entradas son bajas y una salida baja cuando existe por lo menos un alto en
Favián Arenas. 76 Camargo Benítez.
4.5 Método de Karnaugh para la Simpli�cación de circuitosLógica Matemática
cualquiera de ellas.
En forma proposicional � (p _ q).
En forma de expresión booleana (A+B)c.
LA COMPUERTA OR EXCLUSIVA O XOR La OR exclusiva, se
denomina la puerta comparadora OR, La tabla de verdad para la función
XOR se muestra en la tabla
A B A XOR B
1 1 0
1 0 1
0 1 1
0 0 0
la cual es equivalente a la disyunción exclusiva
Favián Arenas. 77 Camargo Benítez.
4.5 Método de Karnaugh para la Simpli�cación de circuitosLógica Matemática
p q p Y q
1 1 0
1 0 1
0 1 1
0 0 0
Note que XOR es combinación de los anteriores:
apliquemos el calculo proposicional:
p Y q = � (p, q)
= � [(p! q) ^ (q ! p)] aplicando la ley de Morgan
= � (p! q)_ � (q ! p) negación del condicional
= (p^ � q) _ (q^ � p) ley distributiva
= (p _ q) ^ (p_ � p) ^ (� q _ q) ^ (� p_ � q) siempre (p_ � p) = 1
= (p _ q) ^ 1 ^ 1 ^ (� p_ � q) simplificando
= (p _ q) ^ (� p_ � q) Ley de Morgan
= (p _ q)^ � (p ^ q) c ley distributiva
= (p^ � p) _ (p^ � q) _ (q^ � p) _ (q^ � q) complemento a cero
= 0 _ (p^ � q) _ (q^ � p) _ 0 suma del modulo
= (p^ � q) _ (q^ � p) Listo!
Con c probamos que p Y q equivale a tres compuertas una de (p _ q);otra de � (p ^ q) y otra que las relacione con la conjunción ^; así pues: A
XOR B equivale a: (A OR B) AND (A NAND B) es decir:
(A+B)(AB)0
con la parte �nal del cálculo proposicional anteriorAXORB = A0B+AB0
VERIFICACIÓN:
Favián Arenas. 78 Camargo Benítez.
4.5 Método de Karnaugh para la Simpli�cación de circuitosLógica Matemática
A=1 y B=1
A=1 y B=0
A=0 y B=1
A=0 y B=0
Favián Arenas. 79 Camargo Benítez.
4.5 Método de Karnaugh para la Simpli�cación de circuitosLógica Matemática
Favián Arenas. 80 Camargo Benítez.
4.5 Método de Karnaugh para la Simpli�cación de circuitosLógica Matemática
Ejemplo 20. construya un circuito con compuertas lógicas que exprese la
siguiente función booleana de dos variables:
Ejemplo 21. f(x; y) = x0 + xy + xy0
se comienza con cada sumando
x0
X
Y
X’
Y
xy
X
Y
XY
xy0
Favián Arenas. 81 Camargo Benítez.
4.5 Método de Karnaugh para la Simpli�cación de circuitosLógica Matemática
X
Y
XY’
X
Y
X’+XY+XY’
Favián Arenas. 82 Camargo Benítez.
4.5 Método de Karnaugh para la Simpli�cación de circuitosLógica Matemática
La suma de todos ellas es una compuerta OR de tres entradas:
El lector puede probar que la tabla de verdad de esta función booleana es
una tautología:
Observación: debido a que xyz = (xy)z = x(yz) y que
x+ y + z = (x+ y) + z = x+ (y + z)
una compuerta OR de tres entradas puede reemplazarse por dos com-
puertas OR de dos entradas
así:
es equivalente a:
De manera semejante ocurre para la compuerta AND.
Ejemplo 22. Encuentre un circuito de compuertas lógicas para: F (x; y; z) =
xyz + x0z0
Ejemplo 24. Encontrar una representación booleana del siguiente circuito
de compuertas lógicas.
Favián Arenas. 83 Camargo Benítez.
4.5 Método de Karnaugh para la Simpli�cación de circuitosLógica Matemática
(X+Y)+Z
Ejemplo 23.
x
y
zxyz+x’y’
Favián Arenas. 84 Camargo Benítez.
4.5 Método de Karnaugh para la Simpli�cación de circuitosLógica Matemática
x
y
z
x
y
z
xyz
yc
zc
(xyz)NOR(yzc+ycz)=[(xyz)+(yzc+ycz)]c
yc XOR zc=(yc)c(zc)+(yc)(zc)c
=yzc+ycz
Favián Arenas. 85 Camargo Benítez.
4.5 Método de Karnaugh para la Simpli�cación de circuitosLógica Matemática
solución: en cada parte del circuito hay un mensaje:
en conclusión F (x; y; z) = [xyz + (yzc + ycz)]c
Es posible que la expresión F (x; y; z) = [xyz + (yzc + ycz)]c se pueda
simpli�car mas para lo cual se aplicarán todas las propiedades del álgebra de
Boole veamos:
[xyz + (yzc + ycz)]c = (xyz)c(yzc + ycz)c ley de Morgan
= (xc + yc + zc)((yzc)c(ycz)c) ley de Morgan
= (xc + yc + zc)((yc + (zc)c)((yc)c + zc) ley de involución
= (xc + yc + zc)(yc + z)(y + zc) ley distributiva
= (xc + yc + zc)(yz + yyc + zzc + yczc) Complemento al cero
= (xc + yc + zc)(yz + 0 + 0 + yczc) ley de Morgan
= (xc + yc + zc)(yz + yczc) ley de Morgan
= yzxc + yzyc + yzzc + xcyczc + yczczc + zcycyc ley distributiva
= yzxc + 0 + 0 + xcyczc + yczczc + zcycyc Complemento al cero
= yzxc + xcyczc + zcyc ley de idempotencia
= yzxc + zcyc ley de absorción
Existen métodos más prácticos y rápidos para simpli�car expresiones
booleanas:
Favián Arenas. 86 Camargo Benítez.
4.5 Método de Karnaugh para la Simpli�cación de circuitosLógica Matemática
4.5.1. Método Karnaugh de simpli�cación de expresiones booleanas
Entrando en materia, los mapas están constituidos por una cuadrícula en
forma de encasillado cuyo número de casillas depende del número de variables
que tenga la función a simpli�car.
Caso de dos variables
Se utiliza una tabla en donde una variable y su complemento va en la
primera �la, la otra variable y su complemento va en la primera columna
x xc
y
yc
Ejemplo 25. : Simpli�ca la función de dos variables f(x; y) = xcy+xyc+xy
Lo primero que se debe hacer es representarlo en un mapa de dos variables.
Se representa como una tabla. Para llenar la tabla, se coloca un uno (1) donde
la intersección forme un producto de la función, así:
para el primer término de la función: xcy, se marca con el uno (1) en la
tabla.
para el segundo término de la función: xyc, se marca con el uno (1) en
la tabla.
por ultimo el tercer término de la función: xy, se marca con el uno (1)
en la tabla. y lo demás con ceros
Favián Arenas. 87 Camargo Benítez.
4.5 Método de Karnaugh para la Simpli�cación de circuitosLógica Matemática
Favián Arenas. 88 Camargo Benítez.
4.5 Método de Karnaugh para la Simpli�cación de circuitosLógica Matemática
formando grupos con los unos se observa que: se ocupa todo el renglón de la
x y toda la columna de la y; no mas.
la función f(x; y) = xcy + xyc + xy; se simpli�ca f(x; y) = x+ y
Reglas de simpli�cación (1)Las agrupaciones son exclusivamente de
unos. Esto implica que ningún grupo puede contener ningún cero.
Correcta Incorrecta
(2) Las agrupaciones únicamente pueden hacerse en horizontal y vertical.
Las diagonales están prohibidas.
Favián Arenas. 89 Camargo Benítez.
4.5 Método de Karnaugh para la Simpli�cación de circuitosLógica Matemática
Correcta Incorrecta
(3) Los grupos deben contener 1; 2; 4; 8; 9; :::; 2n número de unos.
Correcta Incorrecta
(4) Cada grupo ha de ser tan grande como sea posible.
Correcta Incorrecta
Favián Arenas. 90 Camargo Benítez.
4.5 Método de Karnaugh para la Simpli�cación de circuitosLógica Matemática
(6) Pueden existir traslapamiento de grupos.
Correcta Incorrecta
(7) La formación de grupos también se puede producir con las celdas
extremas de la tabla. De tal forma que la parte inferior se podría agrupar
con la superior y la izquierda con la derecha.
Correcta
(8) Tiene que resultar el menor número de grupos posibles (ser minimal
) siempre y cuando no contradiga ninguna de las reglas anteriores.
Caso de tres variables
Favián Arenas. 91 Camargo Benítez.
4.5 Método de Karnaugh para la Simpli�cación de circuitosLógica Matemática
Se utiliza una tabla en donde una variable y su complemento va en la
primera columna, las otras dos variables y sus complementos se acomodan
como productos de ellas en la primera �la
yz ycz yzc yczc
x
xc
F (x; y; z) = xcyczc + xcycz + xcyzc + xyczc + xyzc
Los pasos a seguir para conseguir reducir esta expresión son:
1. Convertir la expresión a una suma de productos si es necesario.
en este caso no lo es.
2. se construye un mapa de karnaugh
3. Cubrir todos los unos del mapa mediante rectángulos de 2n elemen-
tos, donde n = 1; 2:::número de variables. Ninguno de esos rectángulos debe
contener ningún cero
Para minimizar el número de términos resultantes se hará el mínimo
número posible de rectángulos que cubran todos los unos.
Favián Arenas. 92 Camargo Benítez.
4.5 Método de Karnaugh para la Simpli�cación de circuitosLógica Matemática
Para minimizar el número de variables se hará cada rectángulo tan grande
como sea posible.
Para encontrar la suma de productos minimal preguntese lo siguiente:
¿Cada rectángulo pertenece a un término producto?
¿que variables hay en común en tal rectángulo? a estos se llamarán im-
plicantes primos.
En el cubrimiento mas grande predomina zc
En el cubrimiento mas pequeño no predomina , pero contiene a xcycz:
entonces los implicantes primos son:
zc y xcycz:,sin embargo como zc contiene a xcyczc;no es necesario incluir en
los implicantes primos a xcycz:; pues será su�ciente con xcyc; : en conclusión
f(x; y; z) se simpli�ca en:
f(x; y; z) = zc + xcyc
Caso de cuatro variables
Se utiliza una tabla en donde dos variables se acomodan como productos
de ellas y sus complementos en la primera columna, las otras dos variables y
sus complementos se acomodan como productos de ellas en la primera �la
Favián Arenas. 93 Camargo Benítez.
4.5 Método de Karnaugh para la Simpli�cación de circuitosLógica Matemática
zw zcw zwc zcwc
xy
xcy
xyc
xcyc
Ejemplo 26. sea f(x; y; z; w) = xyzw + xyzwc + xyzcw + xcyzwc+
xcyzcw+xcyzcwc+xyczwc+xcyczw+xcyczwc+xcyczcw
primero se marcan con unos las reguiones de la función
ahora se agrupan los unos con tal que tengan 2n unos
entonces los implicantes primos son:
a) xyz
b) zwc
Favián Arenas. 94 Camargo Benítez.
4.5 Método de Karnaugh para la Simpli�cación de circuitosLógica Matemática
c) yzcw
d) xcycz
e) xcyzc
f) xcyczw
Por lo tanto f(x; y; z; w) se simpli�ca en:
f(x; y; z; w) = xyz + zwc + yzcw + xcycz + xcyzc + xcyczw
Favián Arenas. 95 Camargo Benítez.
4.6 Actividades Lógica Matemática
4.6. Actividades
Ejercicio 4. . Simpli�car las siguientes expresiones booleanas utilizando
mapas de Karnaugh
ab0(a+ b0)c0+ b
a+ b+ (a0+ b+ c)0
bc+ da+ c+ (dc(ab+ dc))
Ejercicio 5. Mostrar con un ejemplo que el mínimo en dos niveles no es
único Sugerencia: utilizar mapas de Karnaugh.
Ejercicio 6. Un misionero está perdido en alguna esquina de Punta Car-
retas. Enfrente de él tiene dos calles que nacen de la esquina de la cual se
encuentra. En este lugar también hay dos pescadores uno de los cuales siem-
pre dice la verdad y el otro siempre miente. El misionero quiere saber como
llegar al tren fantasma que se encuentra en el Parque Rodó. ¿Qué pregunta
debe realizar para llegar correctamente a destino? .
Ejercicio 7. Probar que los dos circuitos siguientes realizan la misma fun-
ción lógica:
Ejercicio 8. . Obtenga una forma minimal en suma de productos las
siguientes expresiones:
(a) f(a; b; c) = (ab+ ac)(ab)
(b) f(x; y; v; w) = xy(v + w)[(x+ y)v]
(c) f(x; y; z) = x+ yz
(d) f(a; b; c) = (a+ b+ c)(d+ a) + bc+ ac
Favián Arenas. 96 Camargo Benítez.
4.6 Actividades Lógica Matemática
Ejercicio 9. Obtenga la tabla de verdad de las siguientes expresiones:
1. (a) f(x; y; z; w) = wyz + xy + wy
(b) f(x; y; z; w) = (w + x+ y)(x+ z)(w + x)
(c) Las funciones del problema anterior.
Ejercicio 10. Construya un circuito de compuertas lógicas que esté repre-
sentado por la función:
1. (a) f(x; y; z) = x+ yc + z
(b) f(x; y) = [(x+ y)c (x+ y)]c
(c) f(x; y; z; w) = (xy + yzwc)c + xczwc
Ejercicio 11. Simpli�que los circuitos anteriores aplicando el método de
Karnaugh
Ejercicio 12. A partir de las tablas de verdad de las siguientes funciones,
obtenga las expresiones algebraicas de dichas funciones y los circuitos lógicos
que las realizan:
1.
Favián Arenas. 97 Camargo Benítez.
4.6 Actividades Lógica Matemática
1.
x y f(x; y)
1 1 1
1 0 0
0 1 1
0 0 0
x y f(x; y)
1 1 0
1 0 0
0 1 0
0 0 1
x y f(x; y)
1 1 0
1 0 1
0 1 1
0 0 0
Ejercicio 13. Construya un circuito de compuertas lógicas para cada una de
las tablas anteriores.
Favián Arenas. 98 Camargo Benítez.
4.6 Actividades Lógica Matemática
Ejercicio 14. Dibuja el diagrama de un circuito para una función OR de
dos entradas utilizando solamente
1. (a) compuertas NAND
(b) compuertas NOR.
Ejercicio 15. Convertir el siguiente circuito en uno que solo utilice com-
puertas NAND
1.
Ejercicio 16. Convertir el circuito anterior a uno que solo contenga com-
puertas NAND de dos entradas
Ejercicio 17. Encuentre los implicantes primos de este mapa de Karnaugh
Favián Arenas. 99 Camargo Benítez.
4.7 Objetivos Lógica Matemática
Guía de trabajo 1
4.7. Objetivos
El alumno estará en la capacidad conocer, utilizar y aplicar los siguientes
elementos básicos para la solución de un problema:
Resolver proposiciones compuestas utilizando los conectivos lógicos.
Hallar el valor de verdad de una proposición a través de la conjunción,
disyunción, condicional, bicondicional y negación a través de proposi-
ciones simples.
Construir la tabla de verdad de una proposición compuesta, y decidir
si es una ley.
Favián Arenas. 100 Camargo Benítez.
4.8 Recursos de aprendizaje Lógica Matemática
4.8. Recursos de aprendizaje
Aula de clases,
Auditorios.
Videobeam
Retroproyector.
Foro
Chat
Correo electrónico
ProposicionesLa lógica es toda una disciplina en la que las re�exiones y el razonamien-
to son fundamentales. Es estudiada también por la �losofía, pero, aquí nos
referiremos por lógica a la Lógica matemática. El elemento básico sobre el
que se desarrolla toda esta teoría se llama proposición.
De todo lo anterior una proposición es una a�rmación con sentido completo
de la cual se puede a�rmar que es cierta o que es falsa.
Ejemplo:
1. �La sal es un compuesto químico�
2. 10 < 14
3. �13 es un número impar�
4. �El sol sale de noche�
Favián Arenas. 101 Camargo Benítez.
4.9 Actividades Lógica Matemática
5. 45 + 5 = 30
6. �¿De que color es la pared?�
Las a�rmaciones 1, 2, 3, 4 y 5. son proposiciones aunque no todas son ver-
daderas siguen siendo proposiciones.
A esta propiedad de las proposiciones de ser verdadera o falsa se le llama
valor de verdad.
Las proposiciones se representan con letras minúsculas, usualmente p, q, r,
s, t,..
Existen casos donde el sujeto del que se habla en la proposición no está
de�nido o no se conoce, por lo que tiene una incógnita.
A estos casos les llamamos frases proposicionales. (Suele llamarles proposi-
ciones abiertas)
1. x+ 12 = 20
2. �Alguien es un ingeniero famoso�
4.9. Actividades
¿Cuáles de los enunciados siguientes pueden considerarse como proposiciones
Ejercicio 18. 1. a) Un triángulo es un polígono de tres ángulos.
b) La �losofía es triangular
c) 52 = 21
d) Un cuadrado es una �gura plana de cuatro lados.
e) Un cuadrado es un polígono de cuatro ángulos rectos
Favián Arenas. 102 Camargo Benítez.
4.9 Actividades Lógica Matemática
f) Un rectángulo es un polígono de cuatro ángulos rectos.
g) Medellín es ciudad de eterna primavera.
h) Un rectángulo es una �gura verde.
i) x2 + 3x� 4 = 0
j) Todas las naranjas son amarillas.
k) Algunas manzanas son rojas.
2. Para que la proposición abierta x+5 < 10 tenga valor de verdad falso,
x debe reemplazarse por:
a) 2
b) 3
c) 4
d) 5
4.9.1. Proposiciones conjuntivas, p ^ q
Dos enunciados cualesquiera se pueden combinar con la palabra 2"para for-
mar un enunciado compuesto llamado la conjunción de los enunciados orig-
inales. Simbólicamente, p ^ q denota la conjunción de los enunciados p y q,
que se lee "p y q".
El valor de esta proposición conjuntiva dependerá de que las dos proposi-
ciones que la conforman sean verdaderas,es decir, que solo es verdadera si las
dos proposiciones son verdaderas
nota: recordemos que V es simbolizado por (1) y F por (0)
La tabla de verdad del enunciado compuesto p ^ q está dada por:
Favián Arenas. 103 Camargo Benítez.
4.9 Actividades Lógica Matemática
p q p ^ q
1 1 1
1 0 0
0 1 0
0 0 0
1. p : El dos es un número par (1)
2. q : Siete es un número primo (1)
3. r : El ocho es un número primo (0)
así que :
p ^ q : El dos es un número par y siete es un número primo (1)
En caso de que una de las dos sea falsa entonces toda la proposición conjun-
tiva lo será.
r ^ q : El ocho es un número primo y siete es un número primo (0)
4.9.2. Proposiciones disyuntivas, p _ q
Dos enunciados se combinan con la palabra .o"para formar un enunciado com-
puesto llamado la disyunción de los enunciados originales. Simbólicamente,
p _ q denota la disyunción de los enunciados p y q, que se lee "p o q".
El valor de esta proposición conjuntiva dependerá de que las dos proposi-
ciones que la conforman sean no sean falsas,es decir, que solo es falsa si las
dos proposiciones son falsas.
La tabla de verdad del enunciado compuesto p _ q está dada por:
Favián Arenas. 104 Camargo Benítez.
4.9 Actividades Lógica Matemática
p q p _ q
1 1 1
1 0 1
0 1 1
0 0 0
4.9.3. Proposiciones condicionales, p! q
Cuando se unen dos proposiciones con el conectivo �entonces�, se forma una
proposición que solo es falsa si las primera es verdadera y la segunda es falsa
(solo en este orden).
La tabla de verdad de la proposición compuesta p! q está dada por:
p q p! q
1 1 1
1 0 0
0 1 1
0 0 1
Ejemplo 27.
Sea p : El canguro es marsupial ( 1 )
q : America es habitat de todos los marsupiales ( 0 )
El canguro es marsupial entonces América es habitat de todos los marsupiales.(0)
Favián Arenas. 105 Camargo Benítez.
4.9 Actividades Lógica Matemática
4.9.4. Proposiciones bicondicionales, p$ q
Cuando se unen dos proposiciones con el conectivo �si y solo si� , se forma
una proposición que solo es falsa si las dos tienen valores de verdad diferentes.
La tabla de verdad del enunciado compuesto p$ q está dada por:
p q p$ q
1 1 1
1 0 0
0 1 0
0 0 1
4.9.5. Negación de Proposiciones :� p
Aunque no es un conectivo lógico (como _;^;Y ,=);,) genera nuevasproposiciones con solo cambiarle el valor de verdad y se simboliza anteponien-
do ���a la letra de la proposición:
Ejemplos:
p : todo número impar es primo
� p : no todo número impar es primo
q : 9 es menor que 6
� q : 9 no es menor que 6
La tabla de verdad de la negación de p : � p está dada por:
p � p
1 0
0 1
Favián Arenas. 106 Camargo Benítez.
4.10 Actividades Lógica Matemática
4.10. Actividades
4. �Una �gura de 4 lados se llama cuadrilátero, si tiene 5 lados se llama
pentágono, si tiene 6 lados se llama hexágono�En el enunciado anterior
identi�ca todas las proposiciones cerradas.
(Represéntalas con las letras p, q, r).
5. Con las proposiciones clasi�cadas en el ejercicio anterior. escribe en
palabras las proposiciones compuestas siguientes:
a) p!� q
b) � (p$ q)
c) (p! q )! (p! r)
6. Supón que p es verdadera, q es falsa y r es falsa ¿cómo es el valor de
verdad de las siguientes proposiciones
a) p^ � q
b) � (p! q)
7. Completa las siguientes tablas de verdad
a)
p q � q � p � p^ � q p Y q (p Y q) _ (� p^ � q)
1 1 1
1 0 0
0 1 0
0 0 1
Favián Arenas. 107 Camargo Benítez.
4.10 Actividades Lógica Matemática
b)
p q � q p$ q p^ � q (p$ q)! (p^ � q)
1 1 1
1 0 0
0 1 0
0 0 1
c)
p q r ((p! r) ^ (q ! r))! r
1 1 1
1 1 0
1 0 1
1 0 0
0 1 1
0 1 0
0 0 1
0 0 0
8. Construye 3 frases que no sean proposiciones, 3 proposiciones, luego
niega las tres proposiciones.
Favián Arenas. 108 Camargo Benítez.
4.11 Objetivos Lógica Matemática
Guía de trabajo 2
4.11. Objetivos
El alumno estará en la capacidad conocer, utilizar y aplicar los siguientes
elementos básicos para la solución de un problema:
Generalidades sobre que es un conjunto y sus Clases.
Generalidades sobre el álgebra de conjuntos y problemas.
Razonamiento sobre cardinalidad de conjuntos..
4.12. Recursos de aprendizaje
Aula de clases,
Auditorios.
Videobeam
Retroproyector.
Foro
Chat
Correo electrónico
Favián Arenas. 109 Camargo Benítez.
4.13 Algebra de conjuntos Lógica Matemática
4.13. Algebra de conjuntos
Unión de Conjuntos Los conjuntos A = fa; b; c; d; eg y B = fa; e; i; o; ug
se combinan para formar un nuevo conjunto, donde ningún elemento puede
estar repetido fa; b; c; d; e; i; o; ug, a este conjunto lo llamaremos unión de A
y B.
M = f1; 2; 3; 4; 5g y J = f1; 3; 5; 7; 9g entonces
M [ J = f1; 2; 3; 4; 5; 7; 9g
Simbólicamente la unión de A y B es:
AUB = fx : x 2 A _ x 2 Bg
Intersección de Conjuntos En esta operación de conjuntos se trata de
encontrar los elementos comunes a ambos conjuntos, es decir los repetidos,
veamos:
M = f1; 2; 3; 4; 5g y J = f1; 3; 5; 7; 9g entonces
La intersección la representamos por:
M \ J = f1; 3; 5g pues son los que se repiten.
Simbólicamente la intercepción de A y B es:
A \B = fx : x 2 A ^ x 2 Bg
Diferencia de Conjuntos En los conjuntos V = fa; e; i; o; ug y A =
fa; e; og
La diferencia de V � A es el conjunto formado por los elementos de V
que no están en A así:
V � A = fi; og
M = f1; 2; 3; 4; 5g y J = f1; 3; 5; 7; 9g entonces
Favián Arenas. 110 Camargo Benítez.
4.13 Algebra de conjuntos Lógica Matemática
La diferencia la representamos por:
M � J = f2; 4g pues son los que están en M y no en J .
También se puede calcular J �M
J �M = f7; 9g pues son los que están en J y no en M .
Simbólicamente es:
M � J = fx : x 2M ^ x =2 Jg
J �M = fx : x 2 J ^ x =2Mg
Complemento Para esta operación debemos de�nir primero un conjunto
que nos sirva como base o referencia, lo simbolizarán con la letra U, se llamará
universal o referencial.
Si U = f0; 1; 2; 3; 4; 5; 6; 7; 8; 9g y el conjunto A = f0; 1; 2; 3g
Llamaremos complemento de A , al conjunto formado por todos los el-
ementos de U que no están en A, o sea f4; 5; 6; 7; 8; 9g, a este conjunto lo
denotaremos con A0
Notese que A0 = U � A
U = f1; 3; 5; 7; 11; 13; 17; 19; 23; 29g
Si B = f1; 11; 29g entonces B0 = f3; 5; 7; 13; 17; 19; 23g
Si C = f3; 5; 7; 17; 23g entonces C0 = f1; 11; 13; 19; 29g
Si D = f1; 3; 5; 7; 11; 13; 17; 19; 23; 29g entonces D0 = �
Simbólicamente es:
A0 = fx : x 2 U ^ x =2 Ag
Favián Arenas. 111 Camargo Benítez.
4.14 Actividades Lógica Matemática
4.14. Actividades
1. Sea A el conjunto de los números naturales divisibles entre 6 menores
que 50, B el conjunto de los números naturales divisibles entre 2 menores
que 50 y C el conjunto de los números naturales divisibles entre 5
menores que 50.Encuentre.
a AUB
b AUC
c BUC
d A \B
e A \ C
f B \ C
g A�B
h A� C
i B � C
2. Representar gra�camente las anteriores operaaciones
3. Si A y B son dos conjuntos no vacios.Encuentra las condiciones que
deben cumplir para que se veri�quen las siguientes operaciones:
a (AUB) � A
b AUB = B
Favián Arenas. 112 Camargo Benítez.
4.14 Actividades Lógica Matemática
c A \B = B
d A � (A \B)
e A � (A�B)
4. Completa en el dibujo las cantidades correspondientes a cada sección
de la �gura y con esa información responde las preguntas a, b, c y d
36 personas fueron a Europa, visitaron España, Inglaterra o Francia, sin
embargo, no todas fueron a los tres lugares, para identi�car la cantidad exacta
de personas que fueron a cierto país, se especi�ca cada cantidad en el siguiente
diagrama de Venn.
21 personas fueron a Francia
Favián Arenas. 113 Camargo Benítez.
4.14 Actividades Lógica Matemática
17 personas fueron a España
16 personas fueron a Inglaterra
9 personas fueron a Francia y a España
8 personas fueron a España y a Inglaterra
6 personas fueron a Francia y a Inglaterra
1. a) El número de personas que fue a Francia y España pero no a
Inglaterra es:_______
b) El número de personas que fue a España o Inglaterra es:______
c) El número de persona que fue a Inglaterra, España y Francia
es:________
d) El número de personas que fue a España o Inglaterra pero no a
Francia es:______
Favián Arenas. 114 Camargo Benítez.
4.15 Objetivos Lógica Matemática
Guía de trabajo 3
4.15. Objetivos
El alumno estará en la capacidad conocer, utilizar y aplicar los siguientes
elementos básicos para la solución de un problema:
Generalidades sobre que es un álgebra de Boole y como se prueba.
Generalidades sobre las leyes del álgebra de Boole y demostraciones.
Generalidades sobre las funciones de Boole con una o mas variables.
4.16. Recursos de aprendizaje
Aula de clases,
Auditorios.
Videobeam
Retroproyector.
Foro
Chat
Correo electrónico
Favián Arenas. 115 Camargo Benítez.
4.17 Clases de operaciones Lógica Matemática
4.17. Clases de operaciones
Hasta el momento hemos hablado de operaciones entre proposiciones y
entre conjuntos
Vale la pena clasi�car en general las operaciones
El primer tipo se llama operación binaria, y no sólo enlaza dos elementos,
sino que determina un tercero (el resultado de los otros dos) que pertenece al
conjunto que consideramos. Por lo tanto una OPERACIÓN BINARIA
� es una .operación tal que:
si a; b 2 X,entonces también la es a� b
Ejemplo 28. la Suma en el conjunto de los naturales es una operación bi-
naria
Ejemplo 29. pues si m;n 2 N;entonces m+ n 2 N:
Ejemplo 30. la Resta en el conjunto de los naturales no es una operación
binaria pues existen elementos de N; como por ejemplo 7 y 12 tal que 7�12 =
�5 =2 N:
El segundo tipo de operación se llama operación unitaria, esta en reali-
dad transforma un número en otro, por lo tanto unaOPERACIÓN UNI-
TARIA ' sobre un conjunto B es una .operación tal que:
Si a 2 B, entonces '(a) 2 B
Ejemplo 31. el operador menos (�) el conjunto de los enteros es una op-
eración binaria
pues si m 2 Z;entonces �m 2 Z:
Favián Arenas. 116 Camargo Benítez.
4.18 Álgebra de Boole Lógica Matemática
Ejemplo 32. la Radicación en el conjunto de los números reales es una
operación binaria si y solo si es raíz impar; es decir el operador 2n+1p� es
una operación binaria con n 2 N
pero el operador 2np� no es una operación binaria con n 2 N
nótese que �1 2 R pero 2np�1 =2 R
4.18. Álgebra de Boole
Un conjunto B, junto con las operaciones binarias �;� de�nidas sobre éles un álgebra de Boole,
si se veri�can las siguientes Propiedades:
Ley conmutativa
1. a) 1) 8a; b 2 B; a� b 2 B
2) 8a; b 2 B; a� b 2 B
Ley distributiva
1. a) 1) 8a; b; c 2 B; a� (b� c) = (a� b)� (a� c)
2) 8a; b; c 2 B; a� (b� c) = (a� b)� (a� c)
Elementos neutros
1. a) 1) 8a 2 B; 9e 2 B; a� e = a (Neutro Aditivo o cero)
2) 8a 2 B; 9i 2 B; a � i = a (Neutro Multiplicativo o
unidad)
Complementación
Favián Arenas. 117 Camargo Benítez.
4.18 Álgebra de Boole Lógica Matemática
1. a) 1) 8a 2 B; 9ac 2 B; a� ac = i (complemento a la unidad)
2) 8a 2 B; 9ac 2 B; a� ac = e (complemento al cero)mas adelante se probará que ac es el mismo en ambos casos.
Ejemplo 33. Sea D26 = f1; 2; 13; 26g el conjunto de los divisores positivos
del 26; de�namos las operaciones binarias así:
Ejemplo 34. a� b =MCM(a; b) ( Mínimo Común múltiplo)
a� b = mcd(a; b) ( Máximo Común divisor)
observe que para que a � b = a; b tiene que ser 1(Neutro Aditivo o
cero)
y para que a � b = a; b tiene que ser 26(Neutro Multiplicativo o
unidad)
por otra parte:
para que a�b = 26; tiene que ser b = 26
a(complemento de la unidad)
y para que a� b = 1; depende de quien sea a así:si a = 1 entonces b = 26
si a = 2 entonces b = 13
si a = 13 entonces b = 2
si a = 26 entonces b = 1
Para representar estas operaciones utilizaremos tablas algo parecidas a las
de la escuela.
Favián Arenas. 118 Camargo Benítez.
4.18 Álgebra de Boole Lógica Matemática
� 1 2 13 26
1 1 2 13 26
2 2 2 26 26
13 13 26 13 26
26 26 26 26 13
� 1 2 13 26
1 1 1 1 1
2 1 2 1 2
13 1 1 13 13
26 1 2 13 26
A continuación se plantearán otras Propiedades de las Algebras de Boole,
se realizarán las pruebas de estas propiedades para uno de ellas y la otra la
realizará el estudiante con el principio de dualidad.
Ley de idempotencia 8a 2 B; a+ a = a
1. a) 1) 8a 2 B; aa = a
Ley de acotamiento
1. a) 1) 8a 2 B; a+ 1 = 1
2) 8a 2 B; a0 = 0
Ley de absorción
1. a) 1) 8a; b 2 B; a+ ab = a
2) 8a; b 2 B; a(a+ b) = a
Ley asociativa
1. a) 1) 8a; b; c 2 B; a+ (b+ c) = (a+ b) + c
2) 8a; b; c 2 B; a(bc) = (ab)c
Unicidad del complemento
Favián Arenas. 119 Camargo Benítez.
4.18 Álgebra de Boole Lógica Matemática
1. a) 1) 8a 2 B; (a+ x = 1) ^ (ax = 0)) x = ac
Ley de involución
1. a) 1) 8a 2 B; (ac)c = a
Ley de Morgan
1. a) 1) 8a; b 2 B; (a+ b)c = acbc
2) 8a; b 2 B; (ab)c = ac + bc
4.18.1. Funciones reales y funciones booleanas
Hasta ahora se ha mostrado en qué operaciones se basa el Algebra de
Boole y algunas de sus
propiedades.
Utilizando expresiones booleanas, vamos a de�nirFunciones booleanas,
que son muy parecidas a las funciones matemáticas a las que estamos acos-
tumbrados pero con la particularidad de que las variables son booleanas y
que los valores devueltos por la función también son booleanos, es decir, una
función booleana sólo puede tomar los valores �0�ó �1�.
Como hemos hecho antes, vamos a ver un ejemplo utilizando una función
matemática de las
que todos conocemos. Por ejemplo esta:
f(x) = 2x+ 1
Se trata de una función Real que tiene una variable Real (x) es decir el
dominio de f es R
Favián Arenas. 120 Camargo Benítez.
4.18 Álgebra de Boole Lógica Matemática
52.50-2 .5-5
10
5
0
-5
x
y
x
y
hay una in�nidad de valores en el dominio de f por esto se obtiene una
in�nidad de puntos en forma de una recta.
También podemos de�nir funciones reales de 2 ó más variables, como por
ejemplo:
f(x; y) = 2x+ y2
f(x; y; z) = z2 � sen(x+ y)
f(x1; x2; x3; :::; xn) = 3px1 + x2 + x3 + :::+ xn
Como estamos acostumbrados a trabajar con este tipo de funciones, nos
resultan claras. Ahora
vamos a de�nir funciones booleanas. Para ello hay que tener presente que
trabajaremos con
variables booleanas y que por tanto usaremos las operaciones + y � del
Algebra de Boole.
Favián Arenas. 121 Camargo Benítez.
4.18 Álgebra de Boole Lógica Matemática
Ejemplo 35. sea la siguiente función booleana de una variable:
f(x) = xc
El valor devuelto por la función es el complemento del valor de la variable.
Como la variable x es booleana, sólo puede tomar los valores �0�y �1�.
Los que la función F toma son:
f(0) = 0c = 1
f(1) = 1c = 0
Ejemplo 36.
Ejemplo 37. Sea la siguiente función booleana se dos variables:
f(x; y) = xc � (x+ y)
obtenemos:
f(0; 0) = 0c � (0 + 0) = 1 � 0 = 0
f(0; 1) = 0c � (0 + 1) = 1 � 1 = 1
f(1; 0) = 1c � (1 + 0) = 0 � 1 = 0
f(1; 1) = 1c � (1 + 1) = 0 � 0 = 0
Antes de calcular los valores que toma la función, se pueden aplicar algu-
nas propiedades para obtener una función más simpli�cada:
del ejemplo anterior
f(x; y) = xc � (x+ y)
= xcx+ xcy (ley distributiva)
= 0 + xcy (complemento al cero)
= x0y
Favián Arenas. 122 Camargo Benítez.
4.19 Actividades Lógica Matemática
en el cual también obtenemos:
f(0; 0) = 00 � 0 = 1 � 0 = 0
f(0; 1) = 00 � 1 = 1 � 1 = 1
f(1; 0) = 10 � 0 = 0 � 1 = 0
f(1; 1) = 10 � 1 = 0 � 0 = 0
4.19. Actividades
1. Dígase cuáles de las siguientes son operaciones unitarias
a) la operación "tomar el inverso de"en el conjunto de los números
reales.
b) la operación "tomar el inverso de"en el conjunto de los números
enteros.
c) encuéntrese otro conjunto sobre el cual "tomar el inverso de"sea
una operación unitaria.
2. En qué circunstancias son +;�;�;�; operaciones binarias:
a) En el sistema de los números reales o subconjuntos de este sistema.
b) En el sistema de los números complejos.
2. Probar las siguientes equivalencias de expresiones por los métodos de:
a. Tablas de verdad.
Ejercicio 19. 1.
Favián Arenas. 123 Camargo Benítez.
4.19 Actividades Lógica Matemática
2. a) Transformaciones algebraicas(propiedades del álgebra de Boole)
abc + acb+ acbc = ac + bc
acbc + ac+ bcc = accc + bcc+ ab
acbc + bd+ abc = d+ dcbc
(a+ bc + ab)(ac + b)abc = 0
(a+ bc + abc)(ab+ bcc + acc) = ab+ acbcc
(ab+ c+ d)(cc + d)(cc + d+ e) = abcc + d
1.
Favián Arenas. 124 Camargo Benítez.
4.20 Objetivos Lógica Matemática
Guía de trabajo 4
4.20. Objetivos
El alumno estará en la capacidad conocer, utilizar y aplicar los siguientes
elementos básicos para la solución de un problema:
Entradas y salidas de las compuertas lógicas.
tablas de verdad a partir de mediciones en compuertas lógicas.
Simpli�cación Tabular mediante Mapas de Karnaugh
4.21. Recursos de aprendizaje
Aula de clases,
Auditorios.
Videobeam
Retroproyector.
Foro
Chat
Correo electrónico
Favián Arenas. 125 Camargo Benítez.
4.21 Recursos de aprendizaje Lógica Matemática
BA
LA COMPUERTA AND
El esquema de la �gura, da una idea de funcionamiento de la compuerta
AND. Examinando de cerca el circuito, notamos que la lámpara encenderá
solo si ambos interruptores se cierran o se activan simultáneamente. Si uno
de los interruptores esta abierto, el circuito se interrumpe y la lámpara no se
enciende. Todas las posibles combinaciones para los interruptores A y B se
muestran en la tabla de verdad.
A B Lampara
1 1 1
1 0 0
0 1 0
0 0 0
La tabla de esta �gura es la misma que la de la conjunción, es decir dos
interruptores en serie se representan con la compuerta AND
Para representar una compuerta AND se utilizará el símbolo siguiente
Favián Arenas. 126 Camargo Benítez.
4.21 Recursos de aprendizaje Lógica Matemática
Esta compuerta AND es un dispositivo que posee dos entradas A y B y
una salida A �B.
El álgebra booleana es una forma de lógica simbólica que muestra como
operan las compuertas lógicas. Una expresión booleana es un método de
mostrar que ocurre en un circuito lógico.
A� B = Y es la expresión booleana de la compuerta AND se lee .A AND
B igual a la salida Y"
El punto (�) signi�ca la función lógica AND en álgebra booleana, y no la
operación de multiplicar como en el álgebra corriente.
LA COMPUERTA OR El grá�co de este circuito ilustra el fun-
cionamiento de la compuerta OR, en el cual los interruptores han sido conec-
tados en paralelo. El encendido de la lámpara se producirá si se cierra
cualquiera de los dos interruptores o ambos. Todas las posibles combina-
ciones de los interruptores se muestran en la tabla siguiente.
Favián Arenas. 127 Camargo Benítez.
4.21 Recursos de aprendizaje Lógica Matemática
A B Lampara
1 1 1
1 0 1
0 1 1
0 0 0
La tabla de esta �gura es la misma que la de la disyunción, es decir dos
interruptores en serie se representan con la compuerta OR
Para representar una compuerta OR se utilizará el símbolo siguiente:
Esta compuerta OR es un dispositivo que posee dos entradas A y B y
una salida A+B.
A + B = Y es la expresión booleana de la compuerta OR se lee .A OR
B igual a la salida Y"
Favián Arenas. 128 Camargo Benítez.
4.21 Recursos de aprendizaje Lógica Matemática
El signo mas (+) signi�ca la función lógica OR en álgebra booleana, y no
la operación de sumar como en el álgebra corriente.
COMPUERTA INVERSORA En este circuito cuando se cierra el inter-
ruptor A, la bombilla se apaga,(¿Por qué?), al abrir el interruptor la bombilla
se enciende.
La tabla es:
A lámpara
1 0
0 1
Favián Arenas. 129 Camargo Benítez.
4.21 Recursos de aprendizaje Lógica Matemática
Es la misma tabla de la negación � p; a este esquema se le llama La
compuerta inversora,
esta posee una entrada y una salida como se muestra en la �gura. Su fun-
ción es producir una salida inversa o contraria a su entrada es decir convertir
unos a ceros y ceros a unos.
LA PUERTANAND Una compuerta NAND es un dispositivo lógico que
opera en forma exactamente contraria a, una compuerta, AND, entregando
una salida baja cuando todas sus entradas son altas y una salida alta mientras
exista por lo menos un bajo a cualquiera de ellas:
En forma proposicional � (p ^ q).
En forma de expresión booleana (AB)0.
Favián Arenas. 130 Camargo Benítez.
4.21 Recursos de aprendizaje Lógica Matemática
Observar que el símbolo NAND es símbolo AND con un pequeño círculo
a la salida.
LA PUERTA NOR Se ha conectado un inversor a la salida de una puerta
OR, obsérvese que se ha añadido un pequeño circulo inversor al símbolo OR
para formar el símbolo NOR.
Debido a que los interruptores A y B están en paralelo entre si y con
la lámpara (Y) esta ultima solo enciende cuando ambos interruptores están
abiertos y permanece apagada mientras cualquiera de ellos , o ambos estén
cerrados.
Símbolo lógico de una compuerta NOR es:
Favián Arenas. 131 Camargo Benítez.
4.21 Recursos de aprendizaje Lógica Matemática
Podemos decir que este dispositivo lógico opera en forma exactamente
opuesta a una compuerta OR , entregando una salida alta cuando todas sus
entradas son bajas y una salida baja cuando existe por lo menos un alto en
cualquiera de ellas.
En forma proposicional � (p _ q).
En forma de expresión booleana (A+B)c.
Ejemplo 38. construya un circuito con compuertas lógicas que exprese la
siguiente función booleana de dos variables:
Ejemplo 39. f(x; y) = x0 + xy + xy0
se comienza con cada sumando
x0
xy
xy0
La suma de todos ellas es una compuerta OR de tres entradas:
El lector puede probar que la tabla de verdad de esta función booleana es
una tautología:
Favián Arenas. 132 Camargo Benítez.
4.21 Recursos de aprendizaje Lógica Matemática
debido a que xyz = (xy)z = x(yz) y que x+y+z = (x+y)+z =
x+ (y + z)
una compuerta OR de tres entradas puede reemplazarse por dos com-
puertas OR de dos entradas
así:
es equivalente a:
(X+Y)+Z
De manera semejante ocurre para la compuerta AND.
Favián Arenas. 133 Camargo Benítez.
4.22 Actividades Lógica Matemática
Ejemplo 40. Encontrar una representación booleana del siguiente circuito
de compuertas lógicas.
solución: en cada parte del circuito hay un mensaje:
en conclusión F (x; y; z) = [xyz + (yzc + ycz)]c
Es posible que la expresión F (x; y; z) = [xyz + (yzc + ycz)]c se pueda
simpli�car más.
4.22. Actividades
1. Probar que los dos circuitos siguientes realizan la misma función lógica:
Ejercicio 20. 1.
Favián Arenas. 134 Camargo Benítez.
4.22 Actividades Lógica Matemática
2. Simpli�car las siguientes expresiones booleanas utilizando mapas de
Karnaugh
ab0(a+ b0)c0+ b
a+ b+ (a0+ b+ c)0
bc+ da+ c+ (dc(ab+ dc))
3. Construya un circuito de compuertas lógicas que esté representado por
la función:
Ejercicio 21. 1.
2. (a) f(x; y; z) = x+ yc + z
(b) f(x; y) = [(x+ y)c (x+ y)]c
(c) f(x; y; z; w) = (xy + yzwc)c + xczwc
4. Simpli�que los circuitos anteriores aplicando el método de Karnaugh
5. Convertir el siguiente circuito en uno que solo utilice compuertas NAND
6. Encuentre los implicantes primos de este mapa de Karnaugh
Favián Arenas. 135 Camargo Benítez.
4.22 Actividades Lógica Matemática
Favián Arenas. 136 Camargo Benítez.